sinc插值和NUFFT小结.doc

FFT要求时域数据是均匀采样，频率是均匀分布于（-π，π）的。
一、插值原理：
设有函数，采样定理表明，在满足以下两个条件时，就可以从的等间隔离散样本中无失真的重建原始信号：
（1）信号是带限的，即信号的最高频率有界；
（2）采样频率满足奈奎斯特采样率。实信号的采样率必须大于信号最高频率的两倍，复信号的采样率必须大于信号的带宽。
当满足以上条件时，在基带信号下，其重建方程为：（式1），上式可以看成是和的卷积，其卷积核为（式2）是在时的采样值。
式（1）可以理解为所有输入样本的加权叠加，根据此式就可以计算任意点处函数值。为精确计算某一点上的需要覆盖无限多个点。实际上这是无法做到的，而且使用大量的数据点会使得插值非常耗时，但精度提高却很小。计算表明核值随着与x的间隔增大而降低，这意味着可以在不过度损失精度的同时对卷积核进行截断。在现有的计算资源下个8点的加权sinc函数比较适合数据处理。
当使用截断后的sinc函数对存在陡峭边缘的函数进行插值时，会出现一种称为Gibbs效应的振铃现象。为减少这种影响，应对插值进行加窗锐化，通常加入Kaiser窗的处理效果比较理想。对与加窗后的插值核，需要进行归一化处理，使其增益单位化，否则采样点上的权值和不再等于1，并且不同插值点之间会出现较大误差。
1、 功率谱估计的提出：主要是针对经典谱估计的分辨率低和方差性能不好的问题提出的。
二、非均匀离散傅里叶变换（NUDFT）
1、{}不均匀采样而{}均匀采样，即，则有，称为第一类非均匀DFT（nonuniform DFT，NUDFT）。
2、{}不均匀采样而{}均匀采样，即，则有，称为第二类NUDFT。
3、{}和{}都是均匀采样，即并且，则有，称为均匀DFT。特别是，如果，则有，这就是传统意义上的DFT。
为了方便，我们将两类NUFFT表示为完全离散的符号形式：

其中n=-N/2，-N/2+1，…N/2-1，表示非均匀采样位置。
三、NUFFT算法
1、第一类NUDFT可由NUFFT算法加速的流程
1）、由公式NUFFT算法采用最小均方误差的解计算插值系数，这里r=-q/2，-q/2+1，…q/2，m=0，1，…M-1。需要个乘数。
2）、计算Fourier系数。需要个乘法数。
3）、使用FFT计算。需要个乘法数。
4）、 。需要个乘法。
2、第二类NUDFT可由NUFFT算法加速的流程
1)、由公式由公式NUFFT算法采用最小军方误差的解计算插值系数，这里r=-q/2，-q/2+1，…q/2，m=0，1，…M-1。需要个乘数。
2）、计算。需要个乘法数。
3）、使用FFT计算。需要个乘法数。
4）、计算，需要个乘法数。
可以看出，NUFFT-1和NUFFT-2算法十分相似，并且具有相同的计算复杂度。他们的区别在于：NUFFT-1处理非均匀间隔的输入数据，所以为了使用FFT技术，需要首先将输入数据插值到均匀间隔上，如NUFFT-1流程第2步所示，NUFFT-2处理均匀间隔输入非均匀间隔输出变换，所以可以首先使用FFT得到在变换空间的均匀采样数据，然后将他们插值到期望的输出采样间隔上，该插值过程在NUFFT-2中的最后一步完成。

四、NUFFT 的优点：NUFFT是一种时频非均匀采样的变换的快速算法，把数据直接进行NUFFT变换，而不像传统方法需要先对数据进行插值才能用来成像，因此可以减少差值带来的误差以及所需花费的额外操作。