一种基于拉格朗日内插的低复杂度改进算法*

潘李云 孙前刚 刘 刚

（中国船舶集团有限公司第七二三研究所 扬州 225000）

1 引言

现如今，不同功能的电子设备与先进的电子信息技术相结合，构造出综合射频系统，使其兼备不同电子设备的功能，在具备通信功能的同时具有雷达，对抗等其他能力是一种趋势。可是，宽带综合信号经过采样后，过高的采样率不适合后续的信号处理，还需要对信号进行降速率，信道化，数字下变频等处理，进而才能对通信频带信号进行解调和提取通信信号的码元信息[1～2]。

然而，在经过这一系列处理后，此时的采样率很难和码元保持速率一致，且提取码元信息时，为了减弱码间串扰的影响，也需要在每个码元的最佳采样点来进行采样，这个时候传统的做法是将采样信号先经过DAC转换成模拟信号，然后再以码元速率在最佳采样点进行采样，从而提取码元信息。但是这个过程完全可以使用插值法来进行简化，其过程图1所示。

图1 插值过程

原本采样信号x（mTs）经过滤波器后得到模拟内插信号y（t）：

然后将模拟信号y（t）在最佳采样时刻t=KTi重采样，（Ti为符号速率，而Ti与Ts独立，未必匹配），得到：

以上两个步骤可以利用离散的插值滤波器合并成一个步骤，根据shannon采样理论[3]，采用正弦插值可以由输入的信号x（mTs）精确得到x（t）的任意时刻值，但这种理想的插值方法是非因果的，它需要无穷多的采样点，一般实际应用中将理想插值滤波器加窗截短，来模拟逼近最佳插值滤波器。然而，这种插值方式所插的点是均匀的，由于而Ti与Ts未必匹配，我们只能取距离最佳采样点kTi最近的点来近似y(kTi)。

2 拉格朗日插值法

相比于正弦插值法，拉格朗日多项式插值法有一个优点就是可以通过少数几个点，获得区间内任意一个点的插值估计，只需要知道所需插值点与实际采样点在时域上的位置关系即可[4]，图2显示了间隔为Ts的采样信号和间隔为Ti的码元之间的关系，设m为采样序列下标，定义滤波器指针为i=int[kTi/Ts]-m，设mk=int[kTi/Ts]，那么可以得到[5]

其中int[x]为不大于x的最大整数，rem[x]为x的小数部分。

根据图2所示可得：m=mk-i，KTi-mTs=(i+μk)Ts且KTi=(mk+μk)Ts，结合式（2）那么可以推导出插值的基本方程为[6]

设插值滤波器是FIR滤波器，那么只要知道滤波器系数结合采样点的值，就能够知道插值点的值。

滤波器的系数可以根据拉格朗日插值多项式求得，拉格朗日多项式法的核心思想是对所求曲线y（t）用一个次数不超过 n的代数多项式 p（t）来逼近。

如果已知n+1个点t0,t1…tn的采样值p0,p1…pn，且它们能满足关系：

那么就可以根据这些信息得出一个n+1元的线性方程组：

此方程组的系数矩阵为

此矩阵为范德蒙德矩阵，所以

所以此线性方程组的解存在且唯一，因此，该多项式插值算法是可行的，并且使用这种方法计算出的结果是唯一的。

根据上面的分析，如果知道某个函数y（t）的采样点t0，t1…tn及其采样值y（t0），y（t1）…y（tn）。那么可得其基函数为

而拉格朗日插值结果为

根据式（10）及式（11）易得，在拉格朗日插值法中，基函数Ci即为滤波器系数，即

如果取样点数为2，则为最简单的线性插值法，该方法计算简单，但准确性不高，为了兼顾准确性及算法复杂度，本文设置取样点数为4，插值点在中间两个点之间，插值滤波器为三次立方插值滤波器，易得其系数为

3 Farrow结构

根据前面的分析可知，插值滤波器是一种时变滤波器，其系数是μ的函数，而μ则是随时间变化的。若使用传统的滤波器结构，则需要实时计算滤波器系数C，这对资源会产生较大消耗，文献[7]提出的Farrow结构则比较适用于插值滤波器，使用这种结构来实现插值滤波器能减小计算的复杂度，根据之前的分析，插值滤波器冲激响应可以表示为式（12），当取样点数为4时，使用三次立方插值滤波器，其系数为式（13）。

vm(n)的系数与vm(n)无关，所以插值滤波器的系数不会随时间改变。Farrow结构滤波器结构如图3所示[8]。

图3 Farrow滤波器结构

由图3可知，利用Farrow结构，只需要储存一次μ的值即可以满足要求，不需要每次都计算滤波器系数[9～10]。

4 改进方法

利用Farrow结构实现式（13）虽然会节省一定资源，但还是不够简便，算法较为复杂，本文在此基础上提出了一种简化算法，进一步简化了算法复杂度，使算法复杂度接近线性插值，插值结果接近比三次立方插值滤波器，具体方法推导如下：

从式（23）可得，三次立方插值可以看成是距离插值点最近的两个点t1，t2的线性插值加上一部分修正值组成，且所加的部分是距离插值点最近的两个点的线性插值结果的一半乘以一个系数a和点t0，t3做线性插值结果的1/6乘以系数a。因为a=μ(1 -μ)，且μ∈(0,1)，容易得出，a的值在μ从0到0.5变化时单调递增，且关于a=0.5轴对称，其取值范围为0～0.25。

通过以上分析，我们可以对三次立方插值滤波器进行改进，如果将μ的值进行分段处理，每一段中取a的最小值来近似a，那么，就可以把三次立方滤波器的算法复杂程度近似于线性插值滤波器，且所得结果应该介于三次立方滤波器和线性滤波器之间，具体分段方法如下：

式（23）结合式（24）构成了更为简便的计算方法，利用这个方法，可以更简单地得出插值结果。

5 结果验证

为直观地观察效果，取正弦函数来分别进行线性插值、基于Farrow结构的三次立方插值和改进后的插值方法进行比较。

如图4所示，*和x分别是线性插值和基于Farrow结构的三次立方插值的结果，是改进后的插值滤波器所得结果，由图可见，改进后的插值滤波器所得结果介于线性插值和三次立方插值之间。

图4 改进后插值滤波器插值效果

图5和图6为分别取μ为0.1～0.5时的幅频响应及群延时，由图可见，改进后的插值滤波器在归一化角频率ω∈[0，0.4π]内幅度虽频率衰减较小，幅频特性平稳，且在这个频率范围内改进后的插值滤波器具备很精确的群延时响应，抖动很小。综上所述，该改进后的插值滤波器能够以较低的算法复杂度得出较高精度的插值结果，且该滤波器具备较好的幅频特性和群延迟特性。

图5 改进后插值滤波器幅频特性

图6 改进后插值滤波器群延时

6 结语

在全数字接收机中，需要通过插值来近似的计算出最佳采样点的值[11～12]。本文鉴于拉格朗日插值法及Farrow结构滤波器给出了一种改进方法，经过理论分析及仿真验证，证实该方法具有灵活、准确、可靠的效果，能够在降低算法难度的情况下同时满足任意分数插值的要求。改进算法通过对公式的迭代变换及滤波器系数的加权优化使得实际使用时滤波器系数的计算比Farrow结构滤波器更简便，仿真结果证实该方法具备一定的理论意义和实用优势。