一種基于拉格朗日內(nèi)插的低復(fù)雜度改進(jìn)算法*

潘李云 孫前剛 劉 剛

（中國(guó)船舶集團(tuán)有限公司第七二三研究所 揚(yáng)州 225000）

1 引言

現(xiàn)如今，不同功能的電子設(shè)備與先進(jìn)的電子信息技術(shù)相結(jié)合，構(gòu)造出綜合射頻系統(tǒng)，使其兼?zhèn)洳煌娮釉O(shè)備的功能，在具備通信功能的同時(shí)具有雷達(dá)，對(duì)抗等其他能力是一種趨勢(shì)。可是，寬帶綜合信號(hào)經(jīng)過(guò)采樣后，過(guò)高的采樣率不適合后續(xù)的信號(hào)處理，還需要對(duì)信號(hào)進(jìn)行降速率，信道化，數(shù)字下變頻等處理，進(jìn)而才能對(duì)通信頻帶信號(hào)進(jìn)行解調(diào)和提取通信信號(hào)的碼元信息[1～2]。

然而，在經(jīng)過(guò)這一系列處理后，此時(shí)的采樣率很難和碼元保持速率一致，且提取碼元信息時(shí)，為了減弱碼間串?dāng)_的影響，也需要在每個(gè)碼元的最佳采樣點(diǎn)來(lái)進(jìn)行采樣，這個(gè)時(shí)候傳統(tǒng)的做法是將采樣信號(hào)先經(jīng)過(guò)DAC轉(zhuǎn)換成模擬信號(hào)，然后再以碼元速率在最佳采樣點(diǎn)進(jìn)行采樣，從而提取碼元信息。但是這個(gè)過(guò)程完全可以使用插值法來(lái)進(jìn)行簡(jiǎn)化，其過(guò)程圖1所示。

圖1 插值過(guò)程

原本采樣信號(hào)x（mTs）經(jīng)過(guò)濾波器后得到模擬內(nèi)插信號(hào)y（t）：

然后將模擬信號(hào)y（t）在最佳采樣時(shí)刻t=KTi重采樣，（Ti為符號(hào)速率，而Ti與Ts獨(dú)立，未必匹配），得到：

以上兩個(gè)步驟可以利用離散的插值濾波器合并成一個(gè)步驟，根據(jù)shannon采樣理論[3]，采用正弦插值可以由輸入的信號(hào)x（mTs）精確得到x（t）的任意時(shí)刻值，但這種理想的插值方法是非因果的，它需要無(wú)窮多的采樣點(diǎn)，一般實(shí)際應(yīng)用中將理想插值濾波器加窗截短，來(lái)模擬逼近最佳插值濾波器。然而，這種插值方式所插的點(diǎn)是均勻的，由于而Ti與Ts未必匹配，我們只能取距離最佳采樣點(diǎn)kTi最近的點(diǎn)來(lái)近似y(kTi)。

2 拉格朗日插值法

相比于正弦插值法，拉格朗日多項(xiàng)式插值法有一個(gè)優(yōu)點(diǎn)就是可以通過(guò)少數(shù)幾個(gè)點(diǎn)，獲得區(qū)間內(nèi)任意一個(gè)點(diǎn)的插值估計(jì)，只需要知道所需插值點(diǎn)與實(shí)際采樣點(diǎn)在時(shí)域上的位置關(guān)系即可[4]，圖2顯示了間隔為Ts的采樣信號(hào)和間隔為Ti的碼元之間的關(guān)系，設(shè)m為采樣序列下標(biāo)，定義濾波器指針為i=int[kTi/Ts]-m，設(shè)mk=int[kTi/Ts]，那么可以得到[5]

其中int[x]為不大于x的最大整數(shù)，rem[x]為x的小數(shù)部分。

根據(jù)圖2所示可得：m=mk-i，KTi-mTs=(i+μk)Ts且KTi=(mk+μk)Ts，結(jié)合式（2）那么可以推導(dǎo)出插值的基本方程為[6]

設(shè)插值濾波器是FIR濾波器，那么只要知道濾波器系數(shù)結(jié)合采樣點(diǎn)的值，就能夠知道插值點(diǎn)的值。

濾波器的系數(shù)可以根據(jù)拉格朗日插值多項(xiàng)式求得，拉格朗日多項(xiàng)式法的核心思想是對(duì)所求曲線y（t）用一個(gè)次數(shù)不超過(guò) n的代數(shù)多項(xiàng)式 p（t）來(lái)逼近。

如果已知n+1個(gè)點(diǎn)t0,t1…tn的采樣值p0,p1…pn，且它們能滿足關(guān)系：

那么就可以根據(jù)這些信息得出一個(gè)n+1元的線性方程組：

此方程組的系數(shù)矩陣為

此矩陣為范德蒙德矩陣，所以

所以此線性方程組的解存在且唯一，因此，該多項(xiàng)式插值算法是可行的，并且使用這種方法計(jì)算出的結(jié)果是唯一的。

根據(jù)上面的分析，如果知道某個(gè)函數(shù)y（t）的采樣點(diǎn)t0，t1…tn及其采樣值y（t0），y（t1）…y（tn）。那么可得其基函數(shù)為

而拉格朗日插值結(jié)果為

根據(jù)式（10）及式（11）易得，在拉格朗日插值法中，基函數(shù)Ci即為濾波器系數(shù)，即

如果取樣點(diǎn)數(shù)為2，則為最簡(jiǎn)單的線性插值法，該方法計(jì)算簡(jiǎn)單，但準(zhǔn)確性不高，為了兼顧準(zhǔn)確性及算法復(fù)雜度，本文設(shè)置取樣點(diǎn)數(shù)為4，插值點(diǎn)在中間兩個(gè)點(diǎn)之間，插值濾波器為三次立方插值濾波器，易得其系數(shù)為

3 Farrow結(jié)構(gòu)

根據(jù)前面的分析可知，插值濾波器是一種時(shí)變?yōu)V波器，其系數(shù)是μ的函數(shù)，而μ則是隨時(shí)間變化的。若使用傳統(tǒng)的濾波器結(jié)構(gòu)，則需要實(shí)時(shí)計(jì)算濾波器系數(shù)C，這對(duì)資源會(huì)產(chǎn)生較大消耗，文獻(xiàn)[7]提出的Farrow結(jié)構(gòu)則比較適用于插值濾波器，使用這種結(jié)構(gòu)來(lái)實(shí)現(xiàn)插值濾波器能減小計(jì)算的復(fù)雜度，根據(jù)之前的分析，插值濾波器沖激響應(yīng)可以表示為式（12），當(dāng)取樣點(diǎn)數(shù)為4時(shí)，使用三次立方插值濾波器，其系數(shù)為式（13）。

vm(n)的系數(shù)與vm(n)無(wú)關(guān)，所以插值濾波器的系數(shù)不會(huì)隨時(shí)間改變。Farrow結(jié)構(gòu)濾波器結(jié)構(gòu)如圖3所示[8]。

圖3 Farrow濾波器結(jié)構(gòu)

由圖3可知，利用Farrow結(jié)構(gòu)，只需要儲(chǔ)存一次μ的值即可以滿足要求，不需要每次都計(jì)算濾波器系數(shù)[9～10]。

4 改進(jìn)方法

利用Farrow結(jié)構(gòu)實(shí)現(xiàn)式（13）雖然會(huì)節(jié)省一定資源，但還是不夠簡(jiǎn)便，算法較為復(fù)雜，本文在此基礎(chǔ)上提出了一種簡(jiǎn)化算法，進(jìn)一步簡(jiǎn)化了算法復(fù)雜度，使算法復(fù)雜度接近線性插值，插值結(jié)果接近比三次立方插值濾波器，具體方法推導(dǎo)如下：

從式（23）可得，三次立方插值可以看成是距離插值點(diǎn)最近的兩個(gè)點(diǎn)t1，t2的線性插值加上一部分修正值組成，且所加的部分是距離插值點(diǎn)最近的兩個(gè)點(diǎn)的線性插值結(jié)果的一半乘以一個(gè)系數(shù)a和點(diǎn)t0，t3做線性插值結(jié)果的1/6乘以系數(shù)a。因?yàn)閍=μ(1 -μ)，且μ∈(0,1)，容易得出，a的值在μ從0到0.5變化時(shí)單調(diào)遞增，且關(guān)于a=0.5軸對(duì)稱，其取值范圍為0～0.25。

通過(guò)以上分析，我們可以對(duì)三次立方插值濾波器進(jìn)行改進(jìn)，如果將μ的值進(jìn)行分段處理，每一段中取a的最小值來(lái)近似a，那么，就可以把三次立方濾波器的算法復(fù)雜程度近似于線性插值濾波器，且所得結(jié)果應(yīng)該介于三次立方濾波器和線性濾波器之間，具體分段方法如下：

式（23）結(jié)合式（24）構(gòu)成了更為簡(jiǎn)便的計(jì)算方法，利用這個(gè)方法，可以更簡(jiǎn)單地得出插值結(jié)果。

5 結(jié)果驗(yàn)證

為直觀地觀察效果，取正弦函數(shù)來(lái)分別進(jìn)行線性插值、基于Farrow結(jié)構(gòu)的三次立方插值和改進(jìn)后的插值方法進(jìn)行比較。

如圖4所示，*和x分別是線性插值和基于Farrow結(jié)構(gòu)的三次立方插值的結(jié)果，是改進(jìn)后的插值濾波器所得結(jié)果，由圖可見，改進(jìn)后的插值濾波器所得結(jié)果介于線性插值和三次立方插值之間。

圖4 改進(jìn)后插值濾波器插值效果

圖5和圖6為分別取μ為0.1～0.5時(shí)的幅頻響應(yīng)及群延時(shí)，由圖可見，改進(jìn)后的插值濾波器在歸一化角頻率ω∈[0，0.4π]內(nèi)幅度雖頻率衰減較小，幅頻特性平穩(wěn)，且在這個(gè)頻率范圍內(nèi)改進(jìn)后的插值濾波器具備很精確的群延時(shí)響應(yīng)，抖動(dòng)很小。綜上所述，該改進(jìn)后的插值濾波器能夠以較低的算法復(fù)雜度得出較高精度的插值結(jié)果，且該濾波器具備較好的幅頻特性和群延遲特性。

圖5 改進(jìn)后插值濾波器幅頻特性

圖6 改進(jìn)后插值濾波器群延時(shí)

6 結(jié)語(yǔ)

在全數(shù)字接收機(jī)中，需要通過(guò)插值來(lái)近似的計(jì)算出最佳采樣點(diǎn)的值[11～12]。本文鑒于拉格朗日插值法及Farrow結(jié)構(gòu)濾波器給出了一種改進(jìn)方法，經(jīng)過(guò)理論分析及仿真驗(yàn)證，證實(shí)該方法具有靈活、準(zhǔn)確、可靠的效果，能夠在降低算法難度的情況下同時(shí)滿足任意分?jǐn)?shù)插值的要求。改進(jìn)算法通過(guò)對(duì)公式的迭代變換及濾波器系數(shù)的加權(quán)優(yōu)化使得實(shí)際使用時(shí)濾波器系數(shù)的計(jì)算比Farrow結(jié)構(gòu)濾波器更簡(jiǎn)便，仿真結(jié)果證實(shí)該方法具備一定的理論意義和實(shí)用優(yōu)勢(shì)。