设x[n]是一个在区间0≤n≤N₁-1以外为零的信号，对于N≥N1，x[n]的N点离散时间博里叶变换可为为

设x[n]是一个在区间0≤n≤N₁-1以外为零的信号，对于N≥N1，x[n]的N点离散时间博里叶变换可为

为了方便，将式(P5.54-1)改写为

其中

(a)计算X[k]的一个方法是直接计算式(P5.54-2)。对这利计算的复杂程度的一种有用度量是所需复数乘

法的总数。证明，对k=0，1，...，N-1，直接计算式(P5.54-2)所需的复数乘法次数是N²。假定x[n]是复数，且所需的值已经预先计算出来，并存放在一张表中.为简单起见，不计如下情况：对于某些n和k的值，等于1或 j，因而严格说来并不需要全都做复数乘法。

(b) 假设N是偶数。令f[n] =x[2n] 表示x [n] 的偶数下标样木， 令g[n] =x[2n+1] 表示x[n] 的奇数下标样本.

(i)证明f[n]和g[n]在区问0≤n≤(N/2)-1以外是零：

(if)证明：x[n]的N点离散时问博里叶变换X[k]可以表示为

其中，

(iii)证明：对所有k，有

注意：T[k]，k=0，1，...，(N/2)-1，和G[K]，k=0，1，...，(N/2)-1分别是.f[n]和g[n]的(N/2)点离散时间博里叶变换。因此，式(P5.54-3)表明，x[n]的长度为N点的离散时间傅里叶变换可以用两个长度为(N/2)的离散时问傅里叶变换来计算。

(iv)当根据式(P5.54-3)，通过先计算F[K]和G[k]来计算X[k]，k=0，1，...，N-1时，确定所需的复数乘法次数。[有关做乘法时的假定与(a)相同，且不计入式(P5.54-3)中乘1/2量的运算。]

(c)若像N一样，N/2还是偶数，则f[n]和g[n]都可以被分解为偶数下标和奇数下标的样本序列。因此，它们的离散时间傅里叶变换可以利用与式(P5.54-3)中相同的步骤来计算。进而，若N是2的整数幂，就可以继续重复这一过程，从而有效地节省计算时间。当N为32，256，1024和4096时，用这个过程来做，大约各需要多少次复数乘法？试将此方法与(a)中的直接计算法进行比较。