sinc插值和NUFFT小结

上传者：陶练敏
|
上传时间：2015-05-08
|
密次下载

sinc插值和NUFFT小结

FFT要求时域数据是均匀采样，频率是均匀分布于（-π，π）的。

一、Sinc插值原理：

设有函数f(x)，采样定理表明，在满足以下两个条件时，就可以从f(x)的等间隔离

内容需要下载文档才能查看

式（1）可以理解为所有输入样本的加权叠加，根据此式就可以计算任意点处f(x)函数值。为精确计算某一点上的f(x)需要覆盖无限多个点。实际上这是无法做到的，而且使用大量的数据点会使得插值非常耗时，但精度提高却很小。计算表明核值随着与x的间隔增大而降低，这意味着可以在不过度损失精度的同时对卷积核进行截断。在现有的计算资源下个8点的加权sinc函数比较适合数据处理。

当使用截断后的sinc函数对存在陡峭边缘的函数进行插值时，会出现一种称为Gibbs效应的振铃现象。为减少这种影响，应对插值进行加窗锐化，通常加入Kaiser窗的处理效果比较理想。对与加窗后的插值核，需要进行归一化处理，使其增益单位化，否则采样点上的权值和不再等于1，并且不同插值点之间会出现较大误差。

1、功率谱估计的提出：主要是针对经典谱估计的分辨率低和方差性能不好的问题提出的。二、非均匀离散傅里叶变换（NUDFT）

1、{tn}不均匀采样而{fn}均匀采样，即fm?m?f，则有F(wm)?

称为第一类非均匀DFT（nonuniform DFT，NUDFT）。

2、{fn}不均匀采样而{tn}均匀采样，即tn?n?t，则有F(wm)?

称为第二类NUDFT。

3、{fn}和{tn}都是均匀采样，即tn?n?t并且fm?m?f，则有?f(tn)en?0dN?1?j2?m?ftn，?fn?0N?1?j2?nm?t?m，(t)ednF(wm)??fd(tn)e

n?0

N?1

n?0N?1?j2?nm?t?f，称为均匀DFT。特别是，如果?f?1/(N?t)，则有F(wm)??fd(tn)e?j2?nm/N，这就是传统意义上的DFT。

为了方便，我们将两类NUFFT表示为完全离散的符号形式：

M?1

Hn?

m?0?hem

N/2

nj2?vmn Gm?

n??N/2?gej2?vmn

其中n=-N/2，-N/2+1，…N/2-1，vm?[?1/2,1/2]表示非均匀采样位置。

三、NUFFT算法

1、第一类NUDFT可由NUFFT算法加速的流程

1）、由公式NUFFT算法采用最小均方误差的解x(c)?(AHA)?1AHb(c)计算插值系数xr(cm)，这里r=-q/2，-q/2+1，…q/2，m=0，1，…M-1。需要O((q?1)M)个乘数。

2）、计算Fourier系数?l?mrm

r?[?q/2,q/2][ucm]?rml

j2?nl/uN2?hx(c)。需要O((q?1)M)个乘法数。。需要O(uNlog(uN))个乘法数。 l?uN/2

3）、使用FFT计算Tn?

?ll??uN/2??e

4）、 H?sn.Tn。需要O(N)个乘法。

2、第二类NUDFT可由NUFFT算法加速的流程

1)、由公式由公式NUFFT算法采用最小军方误差的解x(c)?(AA)Ab(c)计算插值系数xr(cm)，这里r=-q/2，-q/2+1，…q/2，m=0，1，…M-1。需要O((q?1)M)个乘数。

?1 2）、计算tn?sn.gn。需要O(N)个乘法数。

l?uN/2?1H?1H2

3）、使用FFT计算Tn?

?ll??uN/2??ej2?nl/uN。需要O(uNlog(uN))个乘法数。

4）、计算G?r

r?[?q/2,q/2]?x(cm)T[ucm]?r，需要O((q?1)M)个乘法数。可以看出，NUFFT-1和NUFFT-2算法十分相似，并且具有相同的计算复杂度。他们的区别在于：NUFFT-1处理非均匀间隔的输入数据，所以为了使用FFT技术，需要首先将输入数据插值到均匀间隔上，如NUFFT-1流程第2步所示，NUFFT-2处理均匀间隔输入非均匀间隔输出变换，所以可以首先使用FFT得到在变换空间的均匀采样数据，然后将他们插值到期望的输出采样间隔上，该插值过程在NUFFT-2中的最后一步完成。

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