農藥廠

[拼音]：shulun bianhuan

[英文]：number-theoretic transform

在快速傅立葉變換(FFT)中，變換因子

是一個複數，因而需要進行復數運算。但是，

，這表明WN是1的N次根。對於任意整數k，

是按k對N取模呈現週期性。在數論變換中，是以整數a代替複數WN實現正變換和反變換，要求這個整數是1的N次根。這一要求在一般的整數運算規則中不成立，只有採用同餘式的運算規則才能找到滿足這一要求的a和N。利用這樣的a和N可以構成數論變換公式為

(1)

顯然，這種變換在計算速度上比快速傅立葉變換快。

把一個給定的正整數M稱為模(mod)，如果用M去除任意兩個整數α和β，所得餘數相同，便稱作α和β對模M同餘，記作α 呏β(modM) (2)

因此，同餘式運算規則是以正整數M為模的整數環（域上所定義的一種線性正交變換。

在式(1)中，整數a、N、M三者之間必須滿足如下關係：aN呏1(modM) (3)

滿足上式的最小正整數N叫做a對模M的指數，a是1的N次根，或簡稱a是N 階的。例如，a為2時對模7的指數是3，對模11的指數是10。

在數論變換中要求找到合適的a、N和M值。所選擇的N應當是高複合數。但如採用2的乘方，就能構成像FFT演算法那樣的訊號流圖，並且希望選取的N值足夠大，以滿足實際需要。其次，所選取的a應當能用簡便的方法實現乘法運算，因為在計算機中乘法運算最花費時間；如果a是2的乘方，可以用移位操作實現a的乘方運算，因而比較方便。又由於是模運算，所以不存在舍入誤差。此外，M最好也是位數不太多的二進位制數，而且必須是大於2的素數。

麥森數論變換

在數論變換的一般公式 (1)中的模M採用麥森數時，就稱為麥森數論變換。麥森數為M=2k－1 (4)

它是一奇數。令k=PQ，P為素數，便有

在此情況下，最大可能的變換長度決定於（2P-1）。以(2P－1)為模，可以找到

（1）a＝2，N＝P，aN＝2P呏1[mod(2P－1)]，但P是素數，N=P也是素數，不是高複合數。

（2）a＝－2，N＝2P，(－2)

呏1[mod(2P－1)]，但由於N=2P，故不是高的複合數。因此，取麥森數作模是不合適的。

費馬數論變換

在數論變換中比較合理的模M是選用費馬數，即Ft=2b+1b=2t (5)

前幾個Ft的值是F0=3;F1=5;F2=17;F3=257；F4=65537；這五個費馬數都是素數，而F5和F6都是複合數：F5=4294967297=641×6700417F6=274177×67280421310721在t＞4的情況下，還沒有發現一個費馬數是素數。Ft稱為第t個費馬數，模Ft的計算可用b位算術運算來完成。訊號所佔用的位數和濾波器係數決定了在輸出中不引起溢位誤差所需用的b值，實際用的b值比訊號所佔用位數的兩倍稍大。為了能夠採用費馬數，如果以溢位條件得到的b值不是一個2的冪時，應該把它增加到接近的2的冪數。

因為是按模M=Ft費馬數進行算術運算，所以長為N=2m的序數的費馬數論變換及其反變換表示式可寫成

其中N是滿足式aN呏1(mod Ft) (7)

的最小正整數。

費馬數論變換和傅立葉變換相類似。當N =2m時，數論變換的快速計演算法的訊號流圖和 FFT的演算法訊號流圖也是一致的，只是把WN換成a。但是，費馬數論變換的基本函式是由2的方冪構成，不需要使用乘法，僅為移位操作，其運算速度快於 FFT演算法。加上費馬數論變換演算法是模算術運算，不存在舍入誤差，從而能得到高精度的褶積。此外，由於FFT的基本函式是三角函式，需要預先儲存這些基本函式，而費馬數論變換演算法卻不需要儲存基本函式。費馬數論變換的缺點主要是它沒有物理意義，在訊號處理中不能運用中間過程；運算需要的字長與變換點數之間存在著嚴格的關係，隨著輸入序列的增長往往需要很長的字長。

參考書目

何振亞著：《數字訊號處理的理論與應用》，人民郵電出版社，北京，1983。