实验二 快速傅立叶变换及应用

一、实验目的

1、掌握利用 FFT 计算线性卷积的原理及具体实现方法。

2、加深理解重叠相加法和重叠保留法。

3、考察利用 FFT 计算线性卷积各种方法的适用范围。

二、实验原理

1、线性卷积与圆周卷积

设𝑥(𝑛)为𝐿点序列，ℎ(𝑛)为M点序列，x(n)和 h(n) 的线性卷积为

的长度为

x(n)和 h(n) 的N 点圆周卷积为

圆周卷积与线性卷积相等而不产生交叠的必要条件为

圆周卷积定理： 根据 DFT 的性质，𝑥(𝑛) 和ℎ(𝑛) 的𝑁 点圆周卷积的 DFT 等于它们 DFT 的乘积

2、快速卷积

快速卷积算法用圆周卷积实现线性卷积，根据圆周卷积定理利用 FFT 算法实现圆周卷积。可以将快速卷积的步骤归纳如下：

(1) 为了使线性卷积可以用圆周卷积来计算，必须选择 𝑁 ≥ 𝐿 + 𝑀 − 1: 同时为了能使用基-2FFT完成卷积运算，要求 。采用补零的办法使𝑥(𝑛)和ℎ(𝑛)的长度均为𝑁。

(2) 计算𝑥(𝑛)和ℎ(𝑛)的𝑁点FFT

 

(3) 组成乘积

(4) 利用 IFFT 计算𝑌(𝑘) 的 IDFT, 得到线性卷积

 

3、分段卷积

我们考察单位取样响应为ℎ(𝑛)的线性系统，输入为𝑥(𝑛),输出为𝑦(𝑛),则

当输入序列𝑥(𝑛)极长时，如果要等𝑥(𝑛)全部集齐时再开始进行卷积，会使输出相对输入有较大的延时，再者如果序列太长，需要大量的存储单元。为此，我们把𝑥(𝑛)分段，分别求出每段的卷积，合在一起得到最后总的输出。这种方法称为分段卷积。分段卷积可细分为重叠相加法和重叠保留法。

重叠保留法：

设𝑥(𝑛)的长度为 , ℎ(𝑛) 的长度为𝑀。我们把序列𝑥(𝑛) 分成多段 N 点序列 ，每段与前一段重叠𝑀 − 1个样本。由于第一段没有前一段保留信号，为了修正我们在第一个输入段前面填充𝑀 − 1个零。计算每一段与ℎ(𝑛) 的圆周卷积，则其每段卷积结果的前𝑀 − 1个样本不等于线性卷积值，不是正确的样本值。

所以我们将每段卷积结果的前𝑀 − 1个样本舍去，只保留后面的𝑁 − 𝑀 + 1个正确输出样本，把这些输出样本合起来，得到总得输出。

利用 FFT 实现重叠保留法的步骤如下：

(1) 在𝑥(𝑛)前面填充𝑀 − 1个零，扩大以后的序列为

                                       

(2) 将𝑥(𝑛)分为若干𝑁点子段，设𝐿 = 𝑁 − 𝑀 + 1为每一段的有效数据长度，则第𝑖 段𝑥𝑖(𝑛) (0 ≤ 𝑛 ≤ 𝑁 − 1)的数据为

(3) 计算每一段与ℎ(𝑛)的𝑁点圆周卷积，利用 FFT计算圆周卷积：

(4) 舍去每一段卷积结果的前𝑀 − 1个样本，连接剩下样本，得到卷积结果 𝑦(𝑛)

三、实验内容

假设要计算序列𝑥(𝑛) = 𝑢(𝑛) − 𝑢(𝑛 − 𝐿),    0 ≤ 𝑛 ≤ 𝐿和 ℎ(𝑛) = cos(0.2𝜋𝑛)，0 ≤𝑛 ≤ 𝑀的线性卷积，完成以下实验内容

1、设𝐿 = 𝑀 ,根据线性卷积的表达式和快速卷积的原理，分别编程实现计算两个序列线性卷积的方法，比较当序列长度分别为 8, 16, 32, 64, 256, 512, 1024 时，两种方法计算线性卷积所需时间。

2、当𝐿 = 2048且𝑀 = 256时，比较直接计算线性卷积和快速卷积所需的时间，进一步考察当𝐿 = 4096且𝑀 = 256时两种算法所需的时间。

3、编程实现利用重叠相加法计算两个序列的线性卷积，考察𝐿 = 2048且𝑀 =256 时计算线性卷积的时间，与第2题的结果进行比较。