什么是N点有限长序列的离散傅里叶变换?

[拼音]：N dian youxian changxulie de lisan Fuliy bianhuan

[外文]：discrete Fourier transformation of finite length sequences

时域N点序列χ(n)的离散傅里叶变换(DFT)以X(k)表示，定义为

(1)

式中K＝0，1，…，N-1。式(1)称为DFT的正变换。从式(1)可以导出

(2)

式中n＝0，1，…，N-1。式(2)称为DFT的逆变换。式(1)和式(2)合起来称为离散傅里叶变换对。

由于在科学技术工作中人们所得到的离散时间信号大多是有限长的N点序列，所以对N点序列进行时域和频域之间的变换是常用的变换，另外 DFT有它的快速算法，使变换可以在很短的时间内完成，所以DFT是数字信号处理中最为重要的工具之一。

是以给定的时域N点序列χ(n)作为主值周期进行周期延拓（即使之周期化）得到以 N点为周期的离散周期序列χ((n))_N，再求χ((n))_N的离散傅里叶级数(DFS)表示(见离散时间周期序列的离散傅里叶级数表示)，得频域的N点离散周期序列X((k))_N，最后从X((k))_N中取出其主值周期，即得X(k)。同理，与此相似，如果已知X(k)求χ(n)，则是从X(k)得X((k))_N，再从X((k))_N得χ((n))_N，取出主值周期即得χ(n)。这个概念很重要，DFT的性质大都与此有关。至于从χ(n)求X(k)，或已知X(k)求χ(n)则是用(1)式或(2)式直接进行的，并不需要通过χ((n))_N和X((k))_N。

共有5点，如下表中所列。表中a、b为常数， χ((m))_N为以N点为周期的周期序列，χ((n+m))_N为χ((n))_N序列整体左移m点后的结果

其他符号如X((k+l))_N，X((l))_N，Y((k-l))_N及y((n-m))_N等可类推其含义，不一一列出。

又称为快速傅里叶变换(FFT)。当序列的长度N为2的整数次幂（即N＝2


，λ为整数）时，算法的指导思想是将一个N 点序列的DFT分成两个N/2点序列的DFT，再分成四个N/4点序列的DFT，如此下去，直到变成N/2个两点序列的DFT。这种快速算法的计算工作量与DFT的直接计算的计算工作量之比约为log₂N/(2N)，以N=1024为例FFT的计算工作量仅约为DFT直接计算的1/200。