離散傅立葉轉換

離散傅立葉轉換（英語：Discrete Fourier Transform，縮寫為DFT），是傅立葉轉換在時域和頻域上都呈離散的形式，將信號的時域採樣轉換為其DTFT的頻域採樣。

在形式上，轉換兩端（時域和頻域上）的序列都是的，而實際上這兩組序列都應當被認為是離散週期信號的主值序列。即使對有限長的離散信號作DFT，也應當將其看作其週期延拓的轉換。在實際應用中通常採用快速傅立葉轉換計算DFT。

離散傅立葉轉換，是連續傅立葉轉換在離散樣本上的類比，目前廣泛應用於信號處理、數值分析、數位通信、音訊處理等領域，在快速演算法問世，以及硬體設備的提升後，能夠更廣泛的應用在人們的日常生活當中，也是個非常重要的學問之一。

定義

對於${\displaystyle N}$點序列${\displaystyle \left\{x[n]\right\}_{0\leq n<N}}$，它的離散傅立葉轉換（DFT）為

${\displaystyle {\hat {x}}[k]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}nk}x[n]\qquad k=0,1,\ldots ,N-1.}$

其中${\displaystyle e}$是自然對數的底數，${\displaystyle i}$是虛數單位。通常以符號${\displaystyle {\mathcal {F}}}$表示這一轉換，即

${\displaystyle {\hat {x}}={\mathcal {F}}x}$

離散傅立葉轉換的逆轉換（IDFT）為：

${\displaystyle x\left[n\right]={1 \over N}\sum _{k=0}^{N-1}e^{i{\frac {2\pi }{N}}nk}{\hat {x}}[k]\qquad n=0,1,\ldots ,N-1.}$

可以記為：

${\displaystyle x={\mathcal {F}}^{-1}{\hat {x}}}$

實際上，DFT和IDFT轉換式中和式前面的歸一化係數並不重要。在上面的定義中，DFT和IDFT前的係數分別為${\displaystyle 1}$和${\displaystyle {\frac {1}{N}}}$。有時會將這兩個係數都改成${\displaystyle {\frac {1}{\sqrt {N}}}}$。

從連續到離散

連續時間信號${\displaystyle x(t)}$以及對應的連續傅立葉轉換${\displaystyle {\hat {x}}(\omega )}$都是連續函數。由於數位系統只能處理有限長的離散信號，因此必須將${\displaystyle x}$和${\displaystyle {\hat {x}}}$都離散化，並且建立對應的傅立葉轉換。

假設${\displaystyle x(t)}$時限於${\displaystyle [0,L]}$，再通過時域採樣將${\displaystyle x(t)}$離散化，就可以得到有限長離散信號，記為${\displaystyle x_{discrete}(t)}$。設採樣週期為${\displaystyle T}$，則時域採樣點數${\displaystyle N={\frac {L}{T}}}$。

${\displaystyle x_{discrete}(t)=x(t)\sum _{n=0}^{N-1}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)\delta (t-nT)}$

它的傅立葉轉換為

${\displaystyle {\hat {x}}_{discrete}(\omega )=\sum _{n=0}^{N-1}x(nT){\mathcal {F}}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)e^{-in\omega T}}$

這就是${\displaystyle x(t)}$在時域採樣後的連續傅立葉轉換，也就是離散時間傅立葉轉換，它在頻域依然是連續的。

下面將頻域信號轉化為有限長離散信號。與對時域信號的處理類似，假設頻域信號是帶限的，再經過離散化，即可得到有限長離散信號。依據採樣定理，頻域採樣若要能完全重建原信號，頻域信號${\displaystyle {\hat {x}}(\omega )}$應當帶限於${\displaystyle (0,{\frac {1}{2T}})}$。由於時域信號時限於${\displaystyle [0,L]}$，由採樣定理以及時頻對偶的關係，頻域的採樣間隔應為${\displaystyle 1/L}$。故，頻域採樣點數為：

${\displaystyle {\frac {1/T}{1/L}}=N}$

即頻域採樣的點數和時域採樣同為${\displaystyle N}$，頻域採樣點為${\displaystyle \{\omega _{k}={2\pi }k/NT\}_{0\leq k<N}}$。 而DTFT在頻域上採樣：

${\displaystyle {\hat {x}}[k]={\hat {x}}_{discrete}(\omega _{k})={\frac {1}{T}}\sum _{n=0}^{N-1}x[nT]e^{-i{\frac {2\pi }{N}}nk}}$

令${\displaystyle T=1}$，將其歸一化，就得到前面定義的離散傅立葉轉換。因此，DFT就是先將信號在時域離散化，求其連續傅立葉轉換後，再在頻域離散化的結果。

DFT與CFT

參見：連續傅立葉轉換

下面考察離散傅立葉轉換與連續傅立葉轉換（CFT，Continuous Fourier Transform）的關係。連續傅立葉轉換

${\displaystyle {\mathcal {F}}x(t)={\hat {x}}(\omega )={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega t}dt}$

的採樣為：

${\displaystyle {\hat {x}}(\omega _{k})={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega _{k}t}dt}$

將這個積分以黎曼和的形式近似，有：

${\displaystyle {\hat {x}}(\omega _{k})\approx {\frac {1}{L}}\sum _{n=0}^{N-1}x[n]e^{-i\omega _{k}nT}T={\frac {1}{N}}{\hat {x}}[k]}$

這一結論指出離散傅立葉轉換確實是連續傅立葉轉換在某種意義上的近似。不過必須注意以下兩點：

• 時域採樣必須滿足採樣定理
• 離散傅立葉轉換的處理物件是時限的

為此，通常對連續信號的時域採樣再做一次加窗處理（Windowing），這樣就得到帶限的有限長離散信號。

DFT與DTFT

參見：離散時間傅立葉轉換

離散時間傅立葉轉換（DTFT）是在時域上對連續傅立葉轉換的採樣。DFT則是在頻域上對DTFT的均勻採樣。離散信號${\displaystyle x[n]}$（n=0,...,N-1）的DTFT為：

${\displaystyle {\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }}$

對${\displaystyle {\hat {x}}(e^{i\omega })}$在離散的頻點${\displaystyle \{\omega _{k}=k{\frac {2\pi }{N}}\}_{0\leq k<N}}$上採樣

${\displaystyle {\hat {x}}[k]={\hat {x}}(e^{i\omega _{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}\qquad k=0,\ldots ,N-1}$

即為${\displaystyle x}$的DFT。由於DTFT在頻域是週期的，所以在DTFT頻域上的均勻採樣也應是週期的。${\displaystyle {\hat {x}}[k]}$實際上是這個週期序列的主值序列。

柵欄效應

${\displaystyle N}$點序列的DFT只能在有限的${\displaystyle N}$個頻點上觀察頻譜，這相當於從柵欄的縫隙中觀察景色，對於了解信號在整個頻域上的特性是不夠的。為了觀察到其他頻率的資訊，需要對原信號${\displaystyle x[n]}$做一些處理，以便在不同的頻點上採樣。

將原來在DTFT頻域上的採樣點數增加到${\displaystyle M}$點，這樣採樣點位置變為${\displaystyle \{\omega '_{k}=e^{ik{\frac {2\pi }{M}}}\}_{0\leq k<M}}$。則對應的DFT成為

${\displaystyle {\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}}$

若在序列${\displaystyle x[n]}$之後補上M-N個零，設為${\displaystyle x'[n]}$，則上式變為

${\displaystyle {\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'}$

因此將${\displaystyle x[n]}$補零再做DFT就可以得到${\displaystyle x[n]}$的DTFT在其他頻率上的值，相當於移動了柵欄，因而能夠從其他位置進行觀察。

頻譜解析度

${\displaystyle N}$點DFT的頻譜解析度是${\displaystyle 2\pi /N}$。柵欄效應一節指出可以通過補零觀察到更多的頻點，但是這並不意味著補零能夠提高真正的頻譜解析度。這是因為${\displaystyle x[n]}$實際上是${\displaystyle x(t)}$採樣的主值序列，而將${\displaystyle x[n]}$補零得到的${\displaystyle x'[n]}$週期延拓之後與原來的序列並不相同，也不是${\displaystyle x(t)}$的採樣。因此${\displaystyle {\hat {x}}'}$與${\displaystyle {\hat {x}}}$是不同離散信號的頻譜。對於補零至${\displaystyle M}$點的${\displaystyle x'}$的DFT，只能說它的解析度${\displaystyle {\frac {2\pi }{M}}}$僅具有計算上的意義，${\displaystyle {\hat {x}}'}$並不是真正的、物理意義上的頻譜。頻譜解析度的提高只能在滿足採樣定理的條件下增加時域採樣長度來實現。

從空間的角度分析

週期為N的離散信號構成一個N維歐幾里得空間${\displaystyle \mathbb {C} ^{N}}$。在這一空間上兩個信號x和y的內積定義為

${\displaystyle \langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]}$

下面給出${\displaystyle \mathbb {C} ^{N}}$上的一組正交基：

${\displaystyle \{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k<N}}$

將信號x在這組正交基上分解，得

${\displaystyle x=\sum _{k=0}^{N-1}{\frac {\langle x,e_{k}\rangle }{\Vert e_{k}\Vert ^{2}}}e_{k}}$

令

${\displaystyle {\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}}$

此即為離散傅立葉轉換。又

${\displaystyle \|e_{k}\|^{2}=N}$

則有

${\displaystyle x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}}$

此即為離散傅立葉轉換的逆轉換。

由此可知，在正交分解的角度上說，離散週期信號${\displaystyle x}$的離散傅立葉轉換${\displaystyle {\hat {x}}}$實質上是${\displaystyle x}$在正交基${\displaystyle \{e_{k}\}}$上的分量。而從線性轉換的角度上說，${\displaystyle \{e_{k}\}}$是圓周摺積的特徵向量，${\displaystyle {\hat {x}}}$則是對應的特徵值。

DFT與圓周摺積

根據摺積定理，離散信號x與y的圓周摺積對偶於頻域上x與y離散傅立葉轉換的乘積。下面揭示DFT與圓周摺積的內在關係。

對長為N的離散信號${\displaystyle {\tilde {x}}}$與${\displaystyle {\tilde {y}}}$，如果要計算它們的摺積，就必須定義${\displaystyle {\tilde {x}}[n]}$與${\displaystyle {\tilde {y}}[n]}$在0≤n<N之外的值。如果將${\displaystyle {\tilde {x}}}$與${\displaystyle {\tilde {y}}}$作週期為N的延拓，則有

${\displaystyle x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]}$

如此，週期為N的圓周摺積：

${\displaystyle (x\otimes y)[n]=\sum _{m=0}^{N-1}x[m]y[n-m]=\sum _{m=0}^{N-1}x[n-m]y[m]}$

摺積的結果仍然是以N為週期的離散信號。

前面指出，${\displaystyle e_{k}}$是DFT的特徵向量，實際上它也是圓周摺積的特徵向量。定義x與y的圓周摺積算子：

${\displaystyle {L}x[n]=(x\otimes y)[n]}$

則${\displaystyle e_{k}}$與y的圓周摺積為

${\displaystyle {L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

顯然，y的DFT

${\displaystyle {\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]}$

就是圓周摺積的特徵值。

性質

完全性

離散傅立葉轉換是可逆的線性轉換

${\displaystyle {\mathcal {F}}:\mathbf {C} ^{N}\to \mathbf {C} ^{N}}$

其中C表示複數集。即，任意N-維複向量都存在DFT和IDFT，而且其DFT和IDFT也是N-維複向量。

正交性

向量組exp（2πi kn/N）是N-維複數空間上的一組正交基：

${\displaystyle \sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}}$

其中δ_kn是Kronecker delta。

移位定理

時域信號序列${\displaystyle x_{n}}$的相位移動${\displaystyle \exp(2\pi inm/N)}$（其中${\displaystyle m}$為整數）在頻域反映為「循環移位」，即：頻域信號序列${\displaystyle X_{k}}$變為${\displaystyle X_{((k-m))_{N}}}$，其中下標是指將k-m對N 取余。類似的，由對偶性，時域信號序列的循環移位對應於頻域信號序列的相移：

若${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$

則${\displaystyle {\mathcal {F}}(\{x_{n}e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}}$

且有${\displaystyle {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}e^{-{\frac {2\pi i}{N}}km}}$

週期性

上文中DFT與DTFT一節已經證明，離散序列的傅立葉轉換是週期的。有限長序列${\displaystyle x_{n}}$的離散傅立葉轉換${\displaystyle X_{k}}$可以被看作是它的週期延拓序列${\displaystyle {\tilde {x}}_{n}=x_{n\ mod\ N}}$的離散時間傅立葉轉換${\displaystyle {\tilde {X}}_{k}}$。由時頻對偶性可知${\displaystyle X_{k}}$也可以被看作它的週期延拓的主值。

上一節的移位定理隱含著DFT的週期性，因為DFT的幅度${\displaystyle |X_{k}|}$不受輸入信號的循環移位的影響，因為時移在頻域對偶於相移，循環移位僅僅使DFT的相位產生平移。週期性的邊界條件在DFT的許多應用中有重要作用。解差分方程式時，就假設邊界條件是滿足週期性的，這是一個很有用的性質（參見應用）。

普朗歇爾定理與帕塞瓦爾定理

如果X_k和Y_k分別是x_n和y_n的離散傅立葉轉換，那麼就有普朗歇爾定理：

${\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}}$

其中星號表示復共扼。帕塞瓦爾定理是普朗歇爾定理的一個特例：

${\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.}$

應用

DFT在諸多多領域中有著重要應用，下面僅是頡取的幾個例子。需要指出的是，所有DFT的實際應用都依賴於計算離散傅立葉轉換及其逆轉換的快速算法，即快速傅立葉轉換。

快速傅立葉轉換

主條目：快速傅立葉轉換

簡介

快速傅立葉轉換（Fast Fourier Transform，簡稱FFT）是一種用來高效計算離散傅立葉轉換（Discrete Fourier Transform，DFT）及其反轉換的演算法。傅立葉轉換是一種數學變換，用來將信號從時間域或空間域轉換到頻率域。這在信號處理、圖像處理、數據分析等領域有著廣泛的應用。傳統的DFT計算複雜度較高，約為${\displaystyle {\mathcal {O}}(n^{2})}$，而FFT將其降為${\displaystyle {\mathcal {O}}(n\log n)}$，大大提高了計算效率。高效的計算能力使其在各種實際應用中扮演著關鍵角色。理解和應用FFT不僅能解決具體的技術問題，還能幫助我們更深入地了解信號處理的基本原理和方法。FFT的出現和應用，無疑是數學和工程領域的一大突破。

常見用於執行離散傅立葉轉換的演算法:

1. 庫利-圖基演算法(Cooley-Tukey algorithm)

庫利－圖基演算法是一種用於快速計算離散傅立葉轉換的方法，通過分治法策略(Divide-and-conquer)將一個長度為N的DFT分解為多個較小長度的DFT。這使得它特別適合處理長度為2的冪次方的序列，但實際上也適用於其他因數分解形式的序列。庫利和圖基在1965年首次提出這個方法，但類似的概念早在1805年由高斯提出。

2.基數-4、8、16、……演算法(Radix-4, 8, 16, …. Algorithms)

可以視為庫利－圖基演算法的一種推廣，使用不只是以2作為基底，以其他數字做為基底的快速演算法。

3.互質因子算法(prime factor algorithm)

互質因子算法，又稱Good–Thomas算法，是一種用於快速傅立葉變換（FFT）的算法。它將大小為${\displaystyle N=N_{1}N_{2}}$的DFT轉換為${\displaystyle N_{1}\times \ N_{2}}$的二維DFT，前提是${\displaystyle N_{1}}$和${\displaystyle N_{2}}$必須是互質的。這種算法在此特殊情況下比傳統的Cooley–Tukey算法更有效。

4.格策爾演算法(Goertzel Algorithm)

此演算法在1958年被傑拉德 · 格策爾所提出。

此算法，使用數字濾波方法計算離散傅立葉轉換（DFT）係數和信號頻譜。修改後的格策爾演算法可以用來計算信號頻譜，而無需像DFT算法那樣涉及複雜的代數計算。

5. 啁啾-Z轉換(Chirp Z transform (CZT))

啁啾-Z轉換（Chirp-Z transform）是一種離散傅立葉轉換（DFT）的擴展算法，適用於當取樣頻率間隔與取樣時間間隔的乘積不等於信號的時頻分布面積時的情況。它利用摺積來實現任意大小的DFT，從而加快計算速度，是一種基於快速傅立葉轉換（FFT）的高效算法。

此外，啁啾-Z變換也是一種用於評估非單位圓上的Z變換的算法。

6.威諾格拉德演算法(Winograd algorithm)

由以色列裔美國計算機科學家Shmuel Winograd於1976年提出的，是一種改進型的快速傅立葉轉換（FFT）算法，旨在進一步提高計算效率和速度。此演算法使用的加法數量與庫利-圖基演算法大致相同，但其所需的乘法數量只有其演算法的約20%。

頻譜分析

前面指出，DFT是連續傅立葉轉換的近似。因此可以對連續信號x（t）均勻採樣並截斷以得到有限長的離散序列${\displaystyle \{x_{n}\}\,}$，對這一序列作離散傅立葉轉換，可以分析連續信號x（t）頻譜的性質。前面還提到DFT應用於頻譜分析需要注意的兩個問題：即採樣可能導致信號混疊和截斷信號引起的頻譜洩漏。可以通過選擇適當的採樣頻率（見奈奎斯特頻率）消減混疊。選擇適當的序列長度並加窗可以抑制頻譜洩漏。

數據壓縮

主條目：數據壓縮

由於人類感官的分辨能力存在極限，因此很多有損壓縮算法利用這一點將語音、音頻、圖像、視頻等信號的高頻部分除去。高頻信號對應於信號的細節，濾除高頻信號可以在人類感官可以接受的範圍內獲得很高的壓縮比。這一去除高頻分量的處理就是通過離散傅立葉轉換完成的。將時域或空域的信號轉換到頻域，僅儲存或傳輸較低頻率上的係數，在解壓縮端採用逆轉換即可重建信號。

解偏微分方程式

主條目：偏微分方程式

離散傅立葉轉換及其多維形式在偏微分方程式的求解中也有應用。此時DFT被看作傅立葉級數的近似。傅立葉級數將函數在複指數e^inx上展開，這正是微分算子的特徵方程式：d/dx e^inx = in e^inx。因此，通過傅立葉級數的形式，線性常微分方程式被轉換為代數方程式，而後者是很容易求解的。此時得到的結果是偏微分方程式解的級數表示，只要通過DFT逆轉換即可得到其一般表示。這種方法被稱作譜方法或級數解法。

長整數與多項式乘法

目前長整數或多項式乘法最快速的算法是基於離散傅立葉轉換的。由於整數（或多項式）乘法是逐位（或逐項）乘累加的形式，因此整數（或多項式）乘積的數字（或係數）可以用乘數數字（或乘式係數）的摺積表示。利用摺積定理，只要將數字（或係數）序列通過離散傅立葉轉換變到頻域，就可以將逐個乘累加的摺積變為對位的乘法，從而減少計算量，再以一次逆轉換便可以得到乘法結果。需要注意整數乘法還有進位的問題。下面以多項式乘法為例說明這一應用：

假設需要計算多項式乘法c(x) = a(x)·b（x），這一乘積結果的各項係數的表達式實際上是線性摺積的形式。由於離散傅立葉轉換對應於圓周摺積，因此需要將這兩個乘式的係數按照次數升序排列，序列後「補零」，使它們的長度d大於兩式最高項次數的和：d > deg(a(x)) + deg(b(x))。然後作圓周摺積：

${\displaystyle \mathbf {c} =\mathbf {a} \otimes \mathbf {b} }$

其中c就是c(x)係數的向量。由於圓周摺積的DFT是乘積，有：

${\displaystyle {\mathcal {F}}\mathbf {c} ={\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} }$

則

${\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} )}$

利用快速傅立葉轉換，這一算法的運算複雜度為${\displaystyle {\mathcal {O}}(N\log N)}$。

OFDM

主條目：OFDM

OFDM（正交頻分復用）在寬帶無線通信中有重要的應用。這種技術將帶寬分為N個等間隔的子載波，可以證明這些子載波相互正交。尤其重要的是，OFDM調製可以由IDFT實現，而解調可以由DFT實現。OFDM還利用DFT的移位性質，在每個幀頭部加上循環前綴（Cyclic Prefix），使得只要信道延時小於循環前綴的長度，就能消除信道延時對傳輸的影響。

特殊例子

數論轉換

主條目：數論轉換

數論轉換是一種可以計算摺積的快速演算法。計算摺積的快速演算法中最常用的一種是使用快速傅里葉變換，然而快速傅立葉變換具有一些實現上的缺點，舉例來說，資料向量必須乘上複數係數的矩陣加以處理，而且每個複數係數的實部和虛部是一個正弦及餘弦函數，因此大部分的係數都是浮點數，也就是說，必須做複數而且是浮點數的運算，因此計算量會比較大，而且浮點數運算產生的誤差會比較大。

而在數論轉換中，資料向量需要乘上的矩陣是一個整數的矩陣，因此不需要作浮點數的乘法運算，更進一步，在模數為的情況下，只有種可能的加法與種可能的乘法，這可以使用記憶體把這些有限數目的加法和乘法存起來，利用查表法來計算，使得數論轉換完全不須任何乘法與加法運算，不過需要較大的記憶體與消耗較大的存取記憶體量。

雖然使用數論轉換可以降低計算摺積的複雜度，不過由於只進行整數的運算，所以只能用於對整數的訊號計算摺積，而利用快速傅立葉變換可以對任何複數的訊號計算摺積，這是降低運算複雜度所要付出的代價，也不一定所有信號都可以找到適合做數論轉換的質數。

${\displaystyle F=Z/p}$，此運算是根據模運算 而取得的，${\displaystyle p}$需要是質數 ，如此可以建構出有限體，並且存在 ${\displaystyle n}$ 個可以整除 ${\displaystyle (p-1)}$ 的實數根。如此可以得到${\displaystyle p=k\cdot n+1}$，${\displaystyle k}$ 為正整數。令 ${\displaystyle \omega }$ 為第 ${\displaystyle (p-1)}$ 個單位根，則第 ${\displaystyle n}$ 個單位根 ${\displaystyle \alpha }$ 可以表示成 ${\displaystyle \alpha =\omega ^{k}}$ 。另外，再令${\displaystyle N}$ 為 ${\displaystyle \alpha }$ 次方 ${\displaystyle p}$ 模運算之循環個數。

數論轉換的公式

${\displaystyle F[k]=\sum _{n=0}^{N-1}f[n]\alpha ^{nk}{\pmod {M}}\quad k=0,1,2,\ldots ,N-1}$

${\displaystyle f[n]=N^{-1}\sum _{k=0}^{N-1}F[k]\alpha ^{-nk}{\pmod {M}}\quad n=0,1,2,\ldots ,N-1}$

其中有幾點限制以及應該注意的事項:

1.M應是一個質數

2.N應該是M-1的因數

3.${\displaystyle N^{-1}}$是滿足 ${\displaystyle N^{-1}}$${\displaystyle N}$ modM=1 的整數（當 N = M−1 時， ${\displaystyle N^{-1}}$ = M−1）。它也被稱為 N 的模 M 的反元素

4.${\displaystyle \alpha }$是 N 階的單位根。

舉個例子來說，當 ${\displaystyle p=5,\alpha =2}$ 則

${\displaystyle \alpha ^{1}=2\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{2}=4\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{3}=3\qquad (mod\quad 5)}$

${\displaystyle \alpha ^{4}=1\qquad (mod\quad 5)}$

因為 ${\displaystyle \alpha ^{4}}$ 經 ${\displaystyle 5}$ 的模運算為 ${\displaystyle 1}$ ，因此可以判定此情況為 ${\displaystyle 4}$ 個次方一循環，所以 ${\displaystyle N=4}$，${\displaystyle N}$可以整除 ${\displaystyle (p-1)}$。則數論矩陣可以表示成

${\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}$

在一些特殊的情況下，令 ${\displaystyle F=Z/m}$ ，而 ${\displaystyle m}$ 不是值數也是有意義的。像是 Fermat Number Transform 中${\displaystyle (m=2^{k}+1)}$，以及 Mersenne Number Transform 中 ${\displaystyle (m=2^{k}-1)}$.

數論轉換的數學性質

前面提到數論轉換是一種離散傅立葉轉換的特例，因此數論轉換具有許多離散傅立葉轉換的數學性質。

若F[k]為f[n]的數論轉換結果，即f[n]→F[k](NTT)

1.正交性質:

矩陣中的每個行或列，彼此正交，即任兩個行或列的內積為0

${\displaystyle \sum _{n=0}^{N-1}\alpha ^{nl}\alpha ^{-nk}=\sum _{n=0}^{N-1}\alpha ^{n(k-l)}=N\delta _{kt}}$

證明:

當${\displaystyle k=l}$，${\displaystyle S_{N}=\sum _{n=0}^{N-1}\alpha ^{n(0)}=N}$

當${\displaystyle k\neq 0}$，${\displaystyle (\alpha ^{n(k-l)}-1)S_{N}=(\alpha ^{n(k-l)}-1)\sum _{n=0}^{N-1}\alpha ^{n(k-l)}=\alpha ^{N(k-l)}-1=1-1=0}$

2.線性性質:

NTT 符合線性轉換，即：

${\displaystyle F[k_{1}+k_{2}]=f[n_{1}]+f[n_{2}]}$

並且對於常數 c 有：

${\displaystyle F[ck]=cF[k]}$

若${\displaystyle f[n]\leftrightarrow F[k]}$，則${\displaystyle -f[n]\leftrightarrow -F[k]}$。

3.平移性質:

若${\displaystyle f[n]\leftrightarrow F[k]}$，則${\displaystyle f[n+l]\leftrightarrow \alpha ^{-lk}F[k]}$，且${\displaystyle f[n]\alpha ^{nl}\leftrightarrow F[k+l]}$

4.可逆性質:

NTT 變換是可逆的，存在反轉換 INTT 使得：

INTT(NTT(n))=n

5.對稱性質:

若${\displaystyle f[n]}$具有對稱性質，即${\displaystyle f[n]=f[N-n]}$，則${\displaystyle f[n]}$的數論轉換${\displaystyle F[k]}$也會有對稱性質，即${\displaystyle F[k]=F[N-k]}$的特性。

若${\displaystyle f[n]=-f[N-n]}$，則${\displaystyle f[n]}$的數論轉換${\displaystyle F[k]}$也會有${\displaystyle F[k]=-F[N-k]}$的特性。

6.摺積性質:

此性質在線性非時變系統當中非常重要，NTT的主要應用多與此性質有關。

若考慮兩個信號，${\displaystyle f[n_{1}]\leftrightarrow F[k_{1}]}$，${\displaystyle f[n_{2}]\leftrightarrow F[k_{2}]}$

${\displaystyle f[n_{1}]*f[n_{2}]\leftrightarrow F[k_{1}]F[k_{2}]{\pmod {m}}}$

${\displaystyle f[n_{1}]f[n_{2}]\leftrightarrow F[k_{1}]*F[k_{2}]{\pmod {m}}}$

數論轉換的優缺點

優點:

1.使用整數進行計算，計算較容易，也可以節省記憶體空間。

2.使用整數不會像浮點數一樣產生誤差，可以非常精確地計算。

3.很多性質都跟離散傅立葉轉換相同。

缺點:

1.只能對整數做計算，若信號為非整數，可能需要事先處理。

2.不容易找到root of unity，即不容易找到合適的對數轉換。

3.相對而言缺乏物理意義。

參閱

• 傅立葉級數
• 傅立葉轉換
• 快速傅立葉轉換
• 數位訊號處理
• Chirp-Z轉換

參考文獻

1. Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., (1999). Discrete-time signal processing, Upper Saddle River, N.J. : Prentice Hall. ISBN 0137549202
2. Mallat, S., A Wavelet Tour of Signal Processing, Second Edition, Academic Press, ISBN 0-12-466606-x
3. Gill, J., Fourier Transform and Its Applications（[1] （頁面存檔備份，存於網際網路檔案館））
4. Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2024
5. Duhamel, Pierre, and Martin Vetterli. "Fast Fourier transforms: a tutorial review and a state of the art." Signal processing 19.4 (1990): 259-299.