信息处理 - 比较 FFT radix-2 和卷积的算术复杂度 - 吾爱随笔录

假设我们有一个离散线性时不变系统，并且我们有一个长度为 N=50 的实信号作为系统的输入。 $x[n]$

系统的脉冲响应也被认为是长度 M=10 的实信号。 $h[n]$

我们要计算输出信号。 $y[n]$

有两种方法可以做到这一点：我们可以在时域中对信号、进行卷积，或者使用 FFT radix-2 并在频域上工作。 $x[n]$ $h[n]$

我想比较这两种方法在实数乘法上的算术复杂度。我知道卷积的算术复杂度是因为实数乘法才能计算。但是，我对 FFT-radix 2 有点困惑。 $N \cdot M$ $N \cdot M$ $y[n]$

我知道它需要 $μ(Ν) = \frac{N}{2}\log _{2}N$ 复数乘法。每个复数乘法都等价于 4 个实数乘法。 $y[n]$ 需要多少次实数乘法？我是否必须先使用 real计算 $X[k]$ 和 $H[k]$ 乘法？如果是这样，我该如何继续？ $\frac{50}{2}\log _{2}50 + \frac{10}{2}\log _{2}10$