數字訊號處理/離散傅立葉變換

數字訊號處理

顧名思義，離散傅立葉變換 (DFT) 純粹是離散的：離散時間資料集被轉換為離散頻率表示。這與使用離散時間的DTFT形成對比，但轉換為連續頻率。由於得到的頻率資訊本質上是離散的，所以計算機在需要頻率資訊時經常使用DFT（離散傅立葉變換）計算。

使用一系列數學技巧和推廣，存在一種在現代計算機上速度非常快的DFT計算演算法。該演算法被稱為快速傅立葉變換 (FFT)，它產生與普通DFT相同的結果，但計算時間只是普通DFT計算的一小部分。FFT將在後面的章節中詳細討論。

DFT

離散傅立葉變換是傅立葉變換的一種數值變體。具體來說，給定一個包含n個輸入幅度的向量，例如 {f₀, f₁, f₂, ... , f_n-2, f_n-1}，離散傅立葉變換會產生一組n個頻率幅度。

DFT 的定義如下

$X[k]=\sum _{n=0}^{N-1}x[n]e^{\frac {-j2\pi kn}{N}}$

這裡，k 用於表示頻域序數，n 用於表示時域序數。大“N”是待變換序列的長度。

逆DFT (IDFT) 由以下公式給出

$x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}X[k]W_{N}^{-kn}$

其中 $W_{N}$ 定義為

$W_{N}=e^{-j2\pi /N}$

同樣，“N”是待變換序列的長度。

矩陣計算

使用矩陣方程可以更容易地計算DFT

\mathbf {X} =\mathbf {D} _{N}\mathbf {x}

小“x”是時域序列，排列為Nx1的垂直向量。大“X”是得到的頻率資訊，它將排列為垂直向量（根據矩陣乘法的規則）。“D_N”項是定義為這樣的矩陣

\mathbf {D} _{N}={\begin{bmatrix}1&1&1&\cdots &1\\1&W_{N}&W_{N}^{2}&\cdots &W_{N}^{(N-1)}\\1&W_{N}^{2}&W_{N}^{4}&\cdots &W_{N}^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&W_{N}^{N-1}&W_{N}^{2(N-1)}&\cdots &W_{N}^{(N-1)(N-1)}\end{bmatrix}}

以類似的方式，可以使用矩陣計算 IDFT，如下所示

\mathbf {x} =\mathbf {D} _{N}^{-1}\mathbf {X}

我們將定義 $\mathbf {D} _{N}^{-1}$ 如下

\mathbf {D} _{N}^{-1}={\begin{bmatrix}1&1&1&\cdots &1\\1&W_{N}^{-1}&W_{N}^{-2}&\cdots &W_{N}^{-(N-1)}\\1&W_{N}^{-2}&W_{N}^{-4}&\cdots &W_{N}^{-2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&W_{N}^{-(N-1)}&W_{N}^{-2(N-1)}&\cdots &W_{N}^{-(N-1)(N-1)}\end{bmatrix}}

離散傅立葉變換的視覺化

可以很容易地看到，該項

e^{-\pi t}

表示複平面上的一個單位向量，對於任何 j 和 k 的值。對於 $j=0$ 或 $k=0$ ，該向量的角度最初為 0 弧度（沿實軸）。隨著 j 和 k 的增加，該角度以圓周的 1/n 為單位遞增。因此，總角度變為 $2\pi *jk/n$ 弧度。

為了理解離散傅立葉變換的意義，將該變換寫成矩陣形式，以圖形方式描述複數項會很有效。

例如，當 $n=8$ 時，可以將傅立葉變換寫成

最上面一行（或最左邊一列）沒有變化；因此，F0 是當振幅互相增強時的結果。第二行變化了圓周的 1/n，從左到右。第三行變化了圓周的 2/n；第四行變化了圓周的 3/n；第五行，這裡，變化了 4/n = 4/8 = 圓周的 1/2。因此，F4 是當偶數項與奇數項相矛盾時的結果。

因此，我們從方陣中看到，DFT 是輸入振幅所有二維向量組合的結果。

與 DTFT 的關係

DFT 和 DTFT 之間的關係非常簡單。如果我們對給定的時間序列 x[n] 進行 DTFT，我們將得到一個連續頻率函式，稱為 $X(e^{j\omega })$ 。如果我們在 N 個等間隔的位置對 $X(e^{j\omega })$ 進行取樣，結果將是 DFT，X[k]。

迴圈時間移位

迴圈時間移位與常規的線性時間移位非常相似，只是當專案移過某個點時，它們會迴圈到序列的另一端。這個主題可能看起來有點離題，但當我們在下一章討論迴圈卷積操作時，這個主題的重要性將變得顯而易見。

假設我們有一個給定的序列 x[n]，如下所示

x[n] = [1& 2 3 4]

眾所周知，我們可以透過從自變數中減去或加上數字來將該序列向左或向右進行時間移位

x[n+1] = [1 2& 3 4 0]

x[n-1] = [0& 1 2 3 4]

在這裡，我們已經用零填充了兩個序列，以使下一個專案的來源變得顯而易見。現在，假設當我們移位一組時，不是用零填充，而是將第一個數字迴圈到周圍以填補空白。我們將使用符號 x[<n+A>] 來表示 A 點迴圈移位

x[<n+1>] = [2& 3 4 1]

請注意序列的長度最初是 4，最後是 4，我們不需要用零填充。還要注意，1“掉落”了組的左側，並“重新出現在”右側。就好像該組是一個圓圈，從一個方向旋轉出去的物件會從另一個方向回來。同樣，讓我們向另一個方向旋轉

x[<n-1>] = [4& 1 2 3]

如果我們旋轉 N 點，其中 N 是組的長度，我們將得到一個重要的恆等式

x[<n+N>] = x[<n-N>] = x[n]

時間反轉

現在，讓我們來看看一個更復雜的情況：將迴圈移位與時間反轉混合。讓我們定義示例集 x[n]

x[n] = [1& 2 3 4]

我們可以將時間反轉集定義如下

x[n] = [4 3 2 1&]

請注意，“4”從 n=3 變成了 n=-3，但“1”仍然位於零點。現在，讓我們嘗試將此與迴圈移位操作結合起來，以產生結果 x[<-n>]。我們知道“1”（位於零位置）沒有向任何方向移動，我們也沒有向左或向右移動，因為我們沒有向自變數（n）新增或減去任何東西。因此，我們可以將 1 放回與之前相同的位置。所有其他數字（2 3 和 4）都移到了序列的右側，因此我們將它們迴圈到另一側

x[<-n>] = [1& 4 3 2]

這是一個通用的迴圈時間反轉規則

x[<-n>]=\left\{{\begin{matrix}x[0],&{\mbox{if }}n=0\\x[<N-n>],&{\mbox{if }}n\neq 0\end{matrix}}\right.

迴圈卷積

迴圈卷積是一個重要的操作，因為在使用 DFT 時它起著重要的作用。

假設我們有兩個長度都為 N 的離散序列 x[n] 和 h[n]。我們可以將迴圈卷積操作定義如下

y[n]=\sum _{m=0}^{N-1}x[m]h[<n-m>_{N}]

請注意，我們使用的是迴圈時間移位操作，而不是常規線性卷積中使用的線性時間移位。

迴圈卷積定理

DFT 具有一定的屬性，使其與常規卷積定理不相容。但是，DFT 確實與迴圈卷積操作有著類似的關係，非常有用。我們將這種關係稱為迴圈卷積定理，並將其陳述如下

迴圈卷積定理: 離散時間域中的乘法在離散頻率域中變為迴圈卷積。離散時間域中的迴圈卷積在離散頻率域中變為乘法。

與線性卷積的關係

迴圈卷積與線性卷積有關，我們可以使用迴圈卷積操作來計算線性卷積結果。假設我們有兩個長度為 N 的集合 x[n] 和 h[n]

在右側用 N-1 個零填充這兩個集合。
對長度為 N+(N-1) 的新集合執行迴圈卷積
結果是原始兩個集合的線性卷積結果。

快速傅立葉變換 (FFT)

快速傅立葉變換指的是以數值有效的方式計算 DFT 的演算法。演算法如下：- 時間抽取和頻率抽取。這是一種在現代計算機上速度非常快的用於計算 DFT 的演算法。