信号系统之FFT卷积

1 Overlap-Add 方法

在许多 DSP 应用中，长信号必须分段过滤。例如，高保真数字音频需要大约 5 MB/min 的数据速率，而数字视频需要大约 500 MB/min 的数据速率。在数据速率如此之高的情况下，计算机通常没有足够的内存来同时保存要处理的整个信号。还有一些系统可以逐段处理，因为它们是实时运行的。例如，电话信号的延迟不能超过几百毫秒，从而限制了在任何一个时刻可供处理的数据量。在其他应用中，处理可能需要对信号进行分段，一个例子是FFT卷积。

Overlap-Add 方法基于 DSP 中的基本技术：

将信号分解为简单的分量
以某种有用的方式处理每个分量
将处理后的分量重新组合成最终信号

图 18-1 显示了如何对 overlap-add 方法执行此操作的示例:

图（a）是要滤波的信号。
图（b）显示了要使用的滤波器内核，即windowed-sinc低通滤波器。
跳到图的底部，（i）显示了滤波后的信号，即（a）的平滑版本。这种方法的关键是卷积如何影响这些信号的长度。当 N 个样本信号与** M 个样本滤波器内核** 卷积时，输出信号长度为 N+M-1 个样本。例如，输入信号（a）为 300 个样本（从 0 到 299 个样本），滤波器内核（b）为 101 个样本（从 0 到 100 个样本），输出信号（i）为 400 个样本（从 0 到 399 个样本）。

换句话说，当 N 个样本信号被滤波时，它将向右扩展 M-1 点。（这是假设筛选器内核从索引 0 到 M 运行。如果在过滤器内核中使用负索引，则扩展也将在左侧）。在（a）中，在样本300和399之间的信号中添加了零，以说明这种扩展将发生的位置。不要被输出信号两端的小值（i）所迷惑。这仅仅是 windowed-sinc 滤波器内核在其末端附近具有较小值的结果。（i）中的所有 400 个样本都是非零的，即使其中一些样本太小而无法在图中看到。

图（c）、（d）和（e）显示了Overlap-Add中使用的分解:

信号被分成多个段，每个段有 100 个来自原始信号的样本。此外，每个段的右侧添加了 100 个零。
在下一步中，通过将每个段与过滤器内核卷积来单独过滤。这将产生（f）、（g）和（h）中所示的输出段。由于每个输入段的长度为 100 个样本，而过滤器内核的长度为 101 个样本，因此每个输出段的长度为 200 个样本。需要理解的重要一点是，将 100 个零添加到每个输入段，以允许在卷积期间进行扩展。

注意，扩展会导致输出段相互重叠。将这些重叠的输出段相加以提供输出信号（i）。例如，通过将（g）和（h）中的相应样本相加，可以找到（i）中的样本200至299。Overlap-Add产生的输出信号与直接卷积完全相同。缺点是跟踪重叠样本的程序复杂性要高得多。

2 FFT 卷积

FFT卷积使用的原理是频域中的乘法对应于时域中的卷积。输入信号使用DFT转换为频域，乘以滤波器的频率响应，然后使用逆DFT转换回时域。这种基本技术自傅立叶时代以来就广为人知。然而，没有人真正关心。这是因为计算 DFT 所需的时间比直接计算卷积所需的时间长。1965 年，随着快速傅里叶变换（FFT）的发展，这种情况发生了变化。通过使用 FFT 算法计算 DFT，通过频域卷积可以比直接卷积时域信号更快。最终结果是一样的，只有计算次数被更有效的算法改变了。因此，FFT卷积也称为高速卷积。

FFT卷积采用图18-1所示的Overlap-Add，仅更改了将输入段转换为输出段的方式。图 18-2 显示了如何通过 FFT 卷积将输入段转换为输出段的示例：

首先，通过使用FFT获取滤波器内核的DFT来找到滤波器的频率响应。例如，（a）显示了一个示例滤波器内核，即一个窗口化 sinc 带通滤波器。FFT将其转换为频率响应的实部和虚部，如（b）和（c）所示。这些频域信号可能看起来不像带通滤波器，因为它们是矩形的。请记住，极性形式通常最适合人类理解频域，而矩形形式通常最适合数学计算。这些实部和虚部都存储在计算机中，以便在计算每个段时使用。
图（d）显示了要处理的输入段。FFT用于查找其频谱，如（e）和（f）所示。然后，通过将滤波器的频率响应（b）和（c）乘以输入段的频谱（e）和（f）来找到输出段（h）和（i）的频谱。
然后使用反 FFT 从其频谱（h）和（i）中找到输出段（g）。重要的是要认识到，该输出段与输入段（d）和滤波器核（a）的直接卷积所获得的输出段完全相同。

FFT 必须足够长，不会发生循环卷积。这意味着 FFT 的长度应与输出段（g）相同。例如，在图 18-2 的示例中，滤波器核包含 129 个点，每个段包含 128 个点，使输出段长 256 个点。这需要使用 256 点 FFT。这意味着过滤器内核（a）必须填充 127 个零，才能使其总长度为 256 个点。同样，每个输入段（d）必须填充 128 个零。再举一个例子，假设需要用一个具有 600 个样本的滤波器内核对一个非常长的信号进行卷积。一种替代方法是使用 425 点和 1024 点 FFT 的段。另一种选择是使用 1449 点和 2048 点 FFT 的段。

表 18-1 显示了执行 FFT 卷积的示例程序。该程序通过使用 400 点滤波器内核卷积来过滤 1000 万点信号。这是通过将输入信号分成 16000 个段来完成的，每个段有 625 个点。当这些段中的每一个都与滤波器核卷积时，会产生 625+400-1=1024 点的输出段。因此，使用了 1024 点 FFT。定义并初始化所有阵列（第 130 至 230 行）后，第一步是计算并存储滤波器的频率响应（第 250 至 310 行）。第 260 行调用一个神话般的子例程，该子例程将过滤器内核加载到 XX[0] 到 XX[399] 中，并将 XX[400] 到 XX[1023] 设置为零值。第 270 行中的子程序是 FFT，将 XX[ ] 中保存的 1024 个样本转换为 REX[ ] 和 IMX[ ] 中保存的 513 个样本，实数和频率响应的虚部。这些值被传输到数组REFR[ ]和IMFR[ ]（用于：REal和IMaginary Frequency Response）中，以便在程序的后面使用。

第 340 行和第 580 行之间的 FOR-NEXT 循环控制 16000 段的处理方式。在第 360 行中，子例程将要处理的下一段加载到 XX[0] 到 XX[624] 中，并将 XX[625] 到 XX[1023] 设置为零值。在第 370 行中，FFT 子程序用于查找该段的频谱，实部放置在 REX[] 的 513 个点中，虚部放置在 IMX[] 的 513 个点中。第 390 行至第 430 行显示了以 REX[] 和 IMX[] 保存的段频谱与以 REFR[] 和 IMFR[] 保存的滤波器频率响应的乘法。乘法的结果存储在 REX[] 和 IMX[] 中，覆盖之前的数据。由于这现在是输出段的频谱，因此可以使用IFFT来查找输出段。这是由第 450 行中神话般的 IFFT 子程序完成的，该子程序将 REX[] 和 IMX[] 中保存的 513 个点转换为输出段 XX[] 中保存的 1024 个点。

第 470 行到第 550 行处理段的重叠。每个输出段分为两个部分。前 625 个点（0 到 624）需要与前一个输出段的重叠相结合，然后写入输出信号。需要保存最后 399 个点（625 到 1023），以便它们可以与下一个输出段重叠。

要理解这一点，请回头看图 18-1。（g）中样本 100 至 199 需要与前一个输出段（f）的重叠组合，然后可以移动到输出信号（i）。相比之下，需要保存（g）中的样本 200 到 299，以便它们可以与下一个输出段（h）组合。

现在回到程序。数组 OLAP[] 用于保存从一个段到下一个段重叠的 399 个样本。在第 470 行到第 490 行中，此数组中的 399 个值（来自前一个输出段）被添加到当前正在处理的输出段中，保存在 XX[] 中。然后，第 550 行中的神话子程序将 XX[0] 到 XX[624] 中的 625 个样本输出到保存输出信号的文件中。然后，需要保留到下一个输出段的当前输出段的 399 个样本存储在 OLAP[] 的第 510 行到 530 行中。

处理完所有 0 到 15999 个段后，数组 OLAP[ ] 将包含段 15999 中的 399 个样本，这些样本应与段 16000 重叠。由于段 16000 不存在（或可以看作是包含所有零），因此 399 个样本被写入第 600 行的输出信号。这使得输出信号点的长度。这与输入信号的长度加上滤波器内核的长度减去 1 相匹配。

3 速度改进

FFT 卷积何时比标准卷积快？答案取决于过滤器内核的长度，如图 18-3 所示。时间过滤器内核。当过滤器内核有大约 40 到 80 个样本时（取决于使用的特定硬件），就会发生交叉。

重要思想是：短于大约 60 个点的滤波器内核可以通过标准卷积更快地实现，并且执行时间与内核长度成正比。使用 FFT 卷积可以更快地实现更长的滤波器内核。使用 FFT 卷积，过滤器内核可以随心所欲地制作，执行时间几乎没有损失。例如，一个 16,000 点的过滤器内核只需要大约两倍的时间来执行64个点。

卷积的速度也决定了计算的精度。这是因为输出信号中的舍入误差取决于计算总数，而计算总数与计算时间成正比。如果输出信号计算得更快，那么计算也会更精确。例如，想象一下，使用具有单精度浮点的 1000 点滤波器内核对信号进行卷积。使用标准卷积，典型的舍入噪声预计约为 20,000 分之一（来自第 4 章中的指南）。相比之下，FFT卷积可以预期要快一个数量级，精度要高一个数量级（即200,000分之一）。