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

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

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

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

時間域函數(shù)

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

頻域函數(shù)

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

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

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

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

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

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

連續(xù)傅里葉變換

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

逆變換是:

離散傅里葉變換

對于離散信號，有離散傅里葉變換 (DFT) :

其逆變換是:

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

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

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

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

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

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

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

原始的DFT定義為:

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

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

具體例子

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

1. 分解

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

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

2. 遞歸求解

3. 合并

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

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

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

數(shù)論變換（NTT）是有限域上離散傅里葉變化的一個變體。由于離散傅里葉變換是基于復(fù)數(shù)域上的變換，大多是浮點運算，故存在著一定的精度和效率問題。在許多應(yīng)用中，需要對整數(shù)商環(huán)上的多項式進行變換，在這種情況下離散傅里葉變換的性能無法滿足要求。而NTT直接對整數(shù)進行處理而無需考慮浮點數(shù)中的存儲問題和精度問題，避免了浮點計算，大大提高了運算效率，非常適合基于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^滿足