離散傅里葉變換及其應(yīng)用簡析

傅里葉變換（Fourier Transform）是一種數(shù)學(xué)工具，用于將一個(gè)函數(shù)（通常是時(shí)間域函數(shù)）轉(zhuǎn)換成另一個(gè)函數(shù)（通常是頻域函數(shù)），以分析該函數(shù)的頻率特性。傅里葉變換是工程、物理學(xué)、計(jì)算機(jī)科學(xué)、圖像處理、音頻信號(hào)處理以及量子物理等多個(gè)領(lǐng)域中常用的一種數(shù)學(xué)方法。

時(shí)間域和頻域是信號(hào)或函數(shù)的兩種不同表示方式，它們包含的是同樣的信息，只是從不同的角度進(jìn)行展示。傅里葉變換（Fourier Transform）和其逆變換（Inverse Fourier Transform）是從時(shí)間域到頻域、以及從頻域到時(shí)間域進(jìn)行轉(zhuǎn)換的數(shù)學(xué)工具。

通過傅里葉分析，你可以將一個(gè)時(shí)間域函數(shù)轉(zhuǎn)換到頻域來分析它，或者將一個(gè)頻域函數(shù)轉(zhuǎn)回時(shí)間域以重構(gòu)它。這兩種表示方式各有其優(yōu)點(diǎn)和應(yīng)用場景。例如，在信號(hào)處理、通信、圖像處理等多個(gè)領(lǐng)域，頻域分析提供了很多方便和高效的方法。

時(shí)間域函數(shù)

在時(shí)間域 (Time Domain) 中，信號(hào)或函數(shù)是按照時(shí)間變量 (通常表示為 t ) 來描述的。在這個(gè)表示中，你可以看到信號(hào)是如何隨著時(shí)間變化的。時(shí)間域表示是直觀的，因?yàn)樗俏覀冊(cè)诂F(xiàn)實(shí)世界中觀察信號(hào)的方式。例如，聲音波、電信號(hào)等都可以在時(shí)間域中表示。舉個(gè)簡單的例子，正弦波 Asin?(2πωt+?) 是一個(gè)時(shí)間域函數(shù)，其中 A 是振幅， ω 是頻率， ? 是相位角， t 是時(shí)間。

頻域函數(shù)

頻域（Frequency Domain）表示則是關(guān)注信號(hào)各個(gè)不同頻率成分的強(qiáng)度或相位。在頻域表示中，信號(hào)被表達(dá)為一系列正弦和余弦波的組合，這些正弦和余弦波有不同的頻率和振幅。這樣的表示使得我們能更容易地分析和理解信號(hào)的頻率特性。例如，傅里葉變換是一種常用的從時(shí)間域到頻域的轉(zhuǎn)換方法。在該變換后，將得到一個(gè)頻域函數(shù)，通常表示為 F(f) 或 F(ω) ，其中 f 或 ω 是頻率或角頻率。

我們知道，任何周期函數(shù)在滿足狄利克雷條件下 (連續(xù)或只有有限個(gè)間斷點(diǎn)，且都是第一類間斷點(diǎn)；只有有限個(gè)極值點(diǎn))，都可以展開成一組正交函數(shù)的無窮級(jí)數(shù)之和。使用三角函數(shù)集的周期函數(shù)展開就是傅里葉級(jí)數(shù)。對(duì)于周期為 T 的信號(hào) f(t) ，可以用三角函數(shù)集的線性組合來表示，即

式中 ω=2π/T 是周期信號(hào)的角頻率，也成基波頻率， nω 稱為 n 次諧波頻率; 為信號(hào)的直流分量，和分別是余弦分量和正弦分量幅度。根據(jù)級(jí)數(shù)理論，傅里葉系數(shù)、、的計(jì)算公式為:

若將式子中同頻率的正弦項(xiàng)和余弦項(xiàng)合并，得到另一種形式的周期信號(hào)的傅里葉級(jí)數(shù)，即

其中，為信號(hào)的直流分量;為信號(hào)的基頻分量，簡稱基波；為信號(hào)的 n 次諧波， n 比較大的諧波，稱為高次諧波。上式說明任何周 期信號(hào)只要滿足狄利克雷條件，都可以分解成直流分量和一系列諧波分量之和，這些諧波分量的頻率是周期信號(hào)基頻的整數(shù)倍。比較兩種三角函數(shù)形式的傅里葉級(jí)數(shù)，可以看出它們的系數(shù)有如下關(guān)系:

傅里葉變換適用于非周期性函數(shù)，將一個(gè)時(shí)間域函數(shù)轉(zhuǎn)換為其對(duì)應(yīng)的頻域函數(shù)?？梢詫⒏道锶~級(jí)數(shù)看作是傅里葉變換的一個(gè)特殊情況?？紤]一個(gè)周期為 T 的函數(shù)。如果 T 趨于無窮，這意味著函數(shù)是非周期性的，此時(shí)傅里葉級(jí)數(shù)會(huì)趨向于傅里葉變換。

連續(xù)傅里葉變換

對(duì)于連續(xù)函數(shù) f(t) ，其連續(xù)傅里葉變換定義為:

逆變換是:

離散傅里葉變換

對(duì)于離散信號(hào)，有離散傅里葉變換 (DFT) :

其逆變換是:

離散傅里葉變換在多項(xiàng)式乘法中的應(yīng)用

對(duì)于n-1階多項(xiàng)式可以用n個(gè)點(diǎn)唯一表示（復(fù)數(shù)的點(diǎn)也是可以的）。令，，k=1,…,n-1

只要我們可以求出矩陣的逆，就能反推出這個(gè) Q 的系數(shù)。這個(gè)矩陣的逆的形式:

快速傅里葉變換（Fast Fourier Transform，簡稱FFT）是離散傅里葉變換（Discrete Fourier Transform，簡稱DFT）的一種高效算法。FFT能在 O(NlogN) 的時(shí)間復(fù)雜度內(nèi)完成這一變換，而直接計(jì)算 DFT需要 O(N^2^) 的時(shí)間復(fù)雜度。

FFT基于一種名為“分治法”的遞歸策略，它將一個(gè)大問題分解為幾個(gè)更小的子問題來解決。對(duì)于一個(gè) N 點(diǎn)的DFT，F(xiàn)FT會(huì)把它分成兩個(gè) N/2 點(diǎn)的DFT，并遞歸地進(jìn)行這個(gè)過程。

具體來說，F(xiàn)FT算法采用以下步驟:

1. 分解階段：原始 N 點(diǎn)DFT分解為兩個(gè) N/2 點(diǎn)的子序列，一個(gè)包含所有的偶數(shù)索引，另一個(gè)包含所有的奇數(shù)索引。
2. 遞歸階段: 對(duì)這兩個(gè) N/2 點(diǎn)子序列遞歸地應(yīng)用FFT。
3. 組合階段：使用遞歸解的結(jié)果，通過一系列的復(fù)數(shù)乘法和加法，組合得到原始N點(diǎn)DFT的結(jié)果。

原始的DFT定義為:

在FFT中，這個(gè)和會(huì)被分成兩部分：一部分是偶數(shù)索引，另一部分是奇數(shù)索引:

其中 E[k] 和 O[k] 是偶數(shù)和奇數(shù)序列的DFT。

具體例子

假設(shè)我們有一個(gè) 4 點(diǎn)的序列 x=[0,1,2,3] 。

1. 分解

偶數(shù)序列 e=[0,2]

奇數(shù)序列 o=[1,3]

2. 遞歸求解

3. 合并

所以 X=[6,0,-2,-4] ，這就是序列 x 的DFT。這個(gè)過程大大減少了計(jì)算量，當(dāng) N 是2 的冪時(shí)，效率最高。

我們總結(jié)一下該過程的時(shí)間復(fù)雜度如下：

1. DFT階段: 將兩個(gè) n 度的多項(xiàng)式 A(x) 和 B(x) 使用FFT轉(zhuǎn)換到點(diǎn)值表示，分別得到 A(k) 和 B(k) 。時(shí)間復(fù)雜度為 2×O(nlogn)=O(nlogn) 。
2. 乘法階段：在點(diǎn)值表示下，將 A(k) 和 B(k) 對(duì)應(yīng)點(diǎn)值相乘得到 C(k) 。這是個(gè) O(n) 時(shí)間復(fù)雜度的操作。
3. IDFT階段：再次使用FFT (實(shí)際上是其逆變換IDFT)將 C(k) 轉(zhuǎn)換回系數(shù)表示得到 C(x) ， 即 A(x)×B(x) 。時(shí)間復(fù)雜度是 O(nlogn) 。綜合這三個(gè)階段，總時(shí)間復(fù)雜度為 O(nlogn)+O(n)+O(nlogn)=O(nlogn) 。

數(shù)論變換（NTT）是有限域上離散傅里葉變化的一個(gè)變體。由于離散傅里葉變換是基于復(fù)數(shù)域上的變換，大多是浮點(diǎn)運(yùn)算，故存在著一定的精度和效率問題。在許多應(yīng)用中，需要對(duì)整數(shù)商環(huán)上的多項(xiàng)式進(jìn)行變換，在這種情況下離散傅里葉變換的性能無法滿足要求。而NTT直接對(duì)整數(shù)進(jìn)行處理而無需考慮浮點(diǎn)數(shù)中的存儲(chǔ)問題和精度問題，避免了浮點(diǎn)計(jì)算，大大提高了運(yùn)算效率，非常適合基于LWE或RLWE難題的密碼系統(tǒng)。

數(shù)論變換(NTT)是整數(shù)環(huán)上定義的線性正交變換。設(shè)x(i)，X(k)∈，i=0,1,2…,n-1，k=0,1,2,…,n-1，有如下公式：

公式中ω為模q的n次單位原根，滿足

n為整數(shù)并且存在n^-1^滿足