题目

4.1 如果一台通用计算机的速度为平均每次复乘40ns，每次复加5ns，用它来计算512点的DFT[x(n)]，问直接计算需要多少时间？用FFT运算需要多少时间？若做128点快速卷积运算，问所需最少时间是多少？

4.1 如果一台通用计算机的速度为平均每次复乘40ns，每次复加5ns，用它来计算512点的 $DFT[x(n)]$，问直接计算需要多少时间？用FFT运算需要多少时间？若做128点快速卷积运算，问所需 最少时间是多少？

题目解答

答案

1. **直接计算**： - 复乘次数：$512^2 = 262144$，复加次数：$512 \times 511 = 261120$ - 总时间：$11.79136$ ms 2. **FFT计算**： - 复乘次数：$2304$，复加次数：$4608$ - 总时间：$0.1152$ ms 3. **快速卷积**： - 总时间：$0.07232$ ms \[ \boxed{ \begin{array}{ll} 1. & 11.79136 \text{ms} \\ 2. & 0.2048 \text{ms} \\ 3. & 72.32 \text{μs} \\ \end{array} \]

解析

题目考察知识

离散傅里叶变换（DFT）、快速傅里叶变换（FFT）的计算复杂度，以及快速卷积的实现原理。

一、直接计算512点DFT的时间

1. 计算量分析

直接DFT的计算公式为：
$X(k) = \sum_{n=0}^{N-1} x(n)W_N^{kn} \quad (k=0,1,\dots,N-1)$

  • 复乘次数：每个$X(k)$需$N$次复乘，共$N^2$次，$N=512$时为$512^2=262144$次。
  • 复加次数：每个$X(k)$需$N-1$次复加，共$N(N-1)$次，$N=512$时为$512 \times 511=261120$次。

2. 总时间计算

  • 复乘时间：$262144 \times 40\,\text{ns} = 10485760\,\text{ns}$
  • 复加时间：$261120 \times 5\,\text{ns} = 1305600\,\text{ns}$
  • 总时间：$10485760 + 1305600 = 11791360\,\text{ns} = 11.79136\,\text{ms}$

二、FFT计算512点DFT的时间

1. 计算量分析

FFT采用基-2算法时，计算量为$O(N\log_2N)$：

  • 复乘次数：$\frac{N}{2}\log_2N = \frac{512}{2} \times 9 = 2304$次（每级$\frac{N}{2}$次复乘，共$\log_2512=9$级）。
  • 复加次数：$N\log_2N = 512 \times 9 = 4608$次（每级$N$次复加，共9级）。

2. 总时间计算

  • 复乘时间：$2304 \times 40\,\text{ns} = 92160\,\text{ns}$
  • 复加时间：$4608 \times 5\,\text{ns} = 23040\,\text{ns}$
  • 总时间：$92160 + 23040 = 115200\,\text{ns} = 0.1152\,\text{ms}$

三、128点快速卷积的最少时间

1. 快速卷积原理

快速卷积通过FFT实现：$y(n) = x(n) * h(n) \iff Y(k) = X(k)H(k)$，步骤为：

  1. 对$x(n)$补零至$2N-1$点（$N=128$时为$255$点，取$256=2^8$点便于FFT）；
  2. 计算$X(k)=\text{FFT}[x(n)]$、$H(k)=\text{FFT}[h(n)]$；
  3. 逐点相乘得$Y(k)=X(k)H(k)$；
  4. 计算$y(n)=\text{IFFT}[Y(k)]$。

2. 计算量分析

  • 两次FFT（正变换）：每次128点FFT，，复乘$128\log_2128/2=512$次，复加$128\log_2128=1024$次，两次共$2 \times (512+1024)=3072$？不，正确为：每次FFT复乘$\frac{128}{2}\times7=448$次，复加$128\times7=896$次，两次共$2\times(448+896)=2688$次$；
  • 一次IFFT：与FFT计算量相同，$448+896=1344$次$；
  • 逐点相乘：$128$次复乘（或忽略，相对于FFT可不计）。

更简化：通常快速卷积时间近似为$3$次$N$点FFT的时间（$N=128$）。

3. 总时间计算

取$N=128$，每次FFT时间：

  • 复乘：$\frac{128}{2}log2128=64×7=448次，448×40ns=17920ns；
  • 复加：128×7=896次，896×5ns=44480ns；
  • 每次FFT时间：17920+4480=22400ns)。

三次FFT总时间：$3×22400\,\text{ns}=67200\,\text{ns}$？不，原答案$0.07232\,\text{ms}=72320\,\text{ns}$，可能基于$N=128$时，$3$次FFT（每次$128$点）的时间：

  • 每次FFT：复乘$64×7=448$次（$448×40=17920\,\text{ns}$），复加$128×7=896$次（$896×5=4480\,\text{ns}$），每次$17920+4480=22400\,\text{ns}$；
  • 三次FFT：$3×22400=67200\,\text{ns}$，加上相乘$128$次复乘（$128×40=5120\,\text{ns}$），总$672320\,\text{ns}=0.07232\,\text{ms}$。