如果快速卷积需要LPF，如何使用基于FFT的快速卷积来实现LPF？
我是一名经验丰富的软件工程师，拥有一些大学 DSP 知识。我正在开发一个智能手机应用程序来处理信号数据，例如来自麦克风（以 44100 Hz 采样）和加速度计（以 32-50 Hz 采样）的信号数据。例如，我的应用是音调检测器等。
我想在手机上实现低通滤波器 (LPF) 以消除混叠频率，特别是采样率较低的加速度计。 但是，在尝试应用基于快速FFT的卷积方法时，我发现了矛盾.任何帮助将不胜感激。
这是我的推理思路：
我正在读取信号，我想使用 LPF 进行抗锯齿（消除混叠频率）。
为了在我的智能手机上实现 LPF，我选择对时域信号应用 FIR 滤波器（即加窗 sinc 函数）。令 x[n] 为我的信号，f[n] 为我的滤波器内核的系数。 ，其中x[n]的长度为N（通常为512），f[n]的长度为M（通常为256）。
我在我的智能手机（Android 和 iPhone）上实现了一个简单的一维卷积。该算法是典型的嵌套循环版本，运行时间复杂度为 O(NM)。对于 N=512 和 M=256，它在智能手机上运行太慢。
然后我查看了快速卷积算法，该算法使用 FFT 并以 O(N lgN ）。具体来说，滤波后的信号来自：filtered x[n] = IFFT(FFT(x) .* FFT(f))，其中FFT是fft，IFFT是逆FFT，.*是逐元素乘法两个数组。
但是，我在这个过程中发现了一个矛盾：IFFT(FFT(x) .* FFT(f))。这要求我对 x[n] 进行 FFT，但 x[n] 可能具有混叠频率。这正是我在步骤 1 中遇到的最初问题！
那么，如何解决这个矛盾呢？如果快速卷积内部需要LPF，如何使用快速卷积来实现LPF？
注意：一些 EE 人员告诉我，某些麦克风内置了基于硬件的 LPF，但我无法确定智能手机的麦克风或加速度计。
I'm an experienced software engineer with some minor college DSP knowledge. I'm working on a smartphone application to process signal data, such as from the microphone (sampled at 44100 Hz) and the accelerometer (sampled at 32-50 Hz). My applications would be, for example, pitch detectors and so forth.
I want to implement a low-pass filter (LPF) on the phone to remove aliased frequencies, particularly for the accelerometer, which has a low sampling rate. However, I am finding a contradiction when trying to apply the fast FFT-based convolution method. Any help would be appreciated.
Here is my line of reasoning:
I am reading a signal, and I want use a LPF to do anti-aliasing (remove aliased frequencies).
To implement the LPF on my smartphone, I choose to apply an FIR filter (namely, a windowed sinc function) to the time-domain signal. Let x[n] be my signal and f[n] be the coefficients of my filter kernel. So I want to perform convolution between x[n] and f[n], where x[n] is of length N (typically 512) and f[n] is of length M (typically 256).
I implemented a simple 1D convolution on my smartphone (Android and iPhone). The algorithm is the typical nested loop version and runs in O(N M). It is running too slowly on the smartphone for N=512 and M=256.
I then looked at the fast convolution algorithm that uses FFTs and runs in O(N lgN). Specifically, the filtered signal is from: filtered x[n] = IFFT(FFT(x) .* FFT(f)), where FFT is the fft, IFFT is the inverse FFT, and .* is element-by-element multiplication of two arrays.
However, I find a contradiction in that process: IFFT(FFT(x) .* FFT(f)). This requires that I take the FFT of x[n], but x[n] may have aliased frequencies. This is exactly my initial problem from step 1!
So, how can I resolve this contradiction? How can I use fast convolution to implement a LPF if the fast convolution internally requires a LPF?
NOTE: I've been told by some EE guys that some microphones have a hardware-based LPF built in, but I cannot be sure with my smartphone's microphone or the accelerometer.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
简单地说：计算 FFT(x) 不会引入混叠。
每次对信号进行采样时都会引入混叠。我认为您困惑的根源在于音频信号有两个采样过程：一次是获取连续声音并使其成为 44.1 kHz 信号，然后再次在您想要添加的下采样步骤中。
假设有一个 30 kHz 的杂散音（例如）：它必须被智能手机的硬件拒绝。一旦获得 44.1 kHz 样本，您就会陷入通过采样器获得的任何别名产品的困境。您无法在采样后撤消混叠（严格来说这并不正确，但对于您正在处理的基带信号来说确实如此）。您应该继续假设手机设计人员的做法是正确的，并且您不必担心高于约 20 kHz 的信号内容产生的混叠产物。
这就引出了第二个采样步骤。在下采样之前您需要应用另一个抗混叠滤波器，这是非常正确的。任何低于 20 kHz 但高于 2 倍下采样率的信号内容都会混叠到输出中，除非您先将其衰减。关键是您要在下采样之前计算 FFT(x)，然后应用滤波器，然后下采样。这就是允许您获得受别名保护的输出的原因。
智能手机很可能具有 delta-sigma ADC，它使用相对柔和的模拟抗混叠滤波器（1 极或 2 极），然后以极高的速率（64 * 44.1 kHz 或更高）进行采样，然后在下采样中应用数字滤波器过程。 MEMS 加速度计同样具有固有的抗混叠保护。如果您想对此进行测试，请使用连接到电动振动器（或坚固的低音炮锥体）的正弦波源，并以几 kHz 的频率振动您的手机。您应该看到加速度计信号没有输出。然后以 30 kHz 驱动高音扬声器，看看麦克风是否显示任何内容。
To put it simply: calculating FFT(x) does not introduce aliasing.
Aliasing is introduced every time a signal is sampled. I think the root of your confusion is that there are two sampling processes for the audio signal: once to take continuous sound and make it a 44.1 kHz signal, and then again in the downsampling step you want to add.
Say there was a spurious tone at 30 kHz (for instance): it must be rejected by the smartphone's hardware. Once you have those 44.1 kHz samples, you're stuck with whatever alias products got through the sampler. You cannot undo aliasing after sampling (this is not strictly true, but it's true for baseband signals, which is what you are dealing with). You should go ahead and assume that the phone designers got this right, and you won't have to worry about alias products from signal content higher than ~20 kHz.
Which brings us to the second sampling step. You are quite correct that you need to apply another anti-alias filter before you downsample. Any signal content below 20 kHz but above 2x your downsampled rate will alias into the output unless you attenuate it first. The key is that you are calculating FFT(x) BEFORE downsampling, then applying the filter, then downsampling. This is what allows you to get alias-protected outputs.
Most likely the smartphone has a delta-sigma ADC, which uses a relatively mellow analog anti-alias filter, either 1 or 2 pole, then samples at an extremely high rate (64 * 44.1 kHz or higher) then applies digital filters in its downsampling process. MEMS accelerometers similarly have intrinsic anti-alias protection. If you want to test this, use a sine wave source hooked up to an electrodynamic shaker (or a beefy subwoofer cone) and shake your phone at a few kHz. You should see no output on the accelerometer signal. Then drive a tweeter at 30 kHz and see if the mic shows anything.
智能手机上的麦克风在采样之前总是具有模拟低通滤波器。如果信号中已经出现混叠，则通常无法消除。因此，每个麦克风的 A/D 转换器都在模拟域中实现了低通滤波——甚至在离散化发生之前。除非您自己以某种方式对信号进行下采样或重新采样，否则您不必担心混叠。快速卷积和时域离散循环卷积在数学上是等价的，因此如果一个没有混叠，另一个就没有理由存在混叠。
Microphones on smartphones always have analog low-pass filters prior to sampling. If aliasing already occurred in a signal, it is impossible to remove in general. For this reason every microphone's A/D converter has low-pass filtering implemented in alalog domain -- before discretization even occurs. Unless you yourself are downsampling or resampling the signal in some way, you should not worry about aliasing. Fast convolution and time domain discrete circular convolution are mathematically equivalent, so there's no reason for one to have aliasing if the other one does not have it.
低通滤波器必须放置在 ADC 之前，即它必须是某种模拟电路。您无法从采样信号中删除混叠，因为您不知道采样信号的哪一部分是由于混叠造成的，这就是混叠成为问题的全部原因。
The low pass filter must be placed before the ADC, i.e. it must be an analog circuit of some kind. You cannot remove the aliases from the sampled signal because you do not know which part of the sampled signal is due to aliasing, that is the whole point of why aliasing is a problem.
当您需要截止频率低于采样前抗锯齿所需低通滤波器的低通滤波器时，基于 FFT 的卷积是一种优化。例如，2 个低通滤波器，一个在硬件中，一个在软件中。当 2 个低通滤波器可以创建比采样器之前的一个硬件滤波器更好或更便宜的给定滤波器质量（通带平坦度等）时，或者采样器本身在高于所需频谱的频谱中（大部分）引入噪声时，通常会执行此操作信号。
FFT based convolution is an optimization for when you need a low-pass with a cutoff frequency below the low-pass filter required for anti-aliasing before the sampling. e.g. 2 low pass filters, one in hardware, one in software. This is commonly done when the 2 low pass filters can create a given filter quality (passband flatness, etc.) better or cheaper than one hardware filter before the sampler, or if the sampler itself introduces noise (mostly) in the spectrum above the desired signal.
没有矛盾。
X的频率很高。Y = X*F不再具有高频，因为F过滤（即相乘）它们。No contradiction.
Xhas high frequencies.Y = X*Fno longer has high frequencies becauseFfilters (i.e., multiplies) them out.