數論轉換

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

雖然使用數論轉換可以降低計算摺積的複雜度,不過由於只進行整數的運算,所以只能用於對整數的信號計算摺積,而利用快速傅立葉變換可以對任何複數的信號計算摺積,這是降低運算複雜度所要付出的代價。

轉換公式[编辑]

數論轉換的轉換式為

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

而數論轉換的反轉換式為

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) \pmod{M} 表示除以M的餘數

(3) N必須是M-1因數。(當N\ne 1NM互質)

(4)N^{-1}N對模數M模反元素

(5)\alpha為模M的N階單位根,即\alpha^N=1\pmod{M}而且\alpha^k \ne 1 \pmod{M}\ k=1,2,\ldots,N-1。若此時N=M-1,我們稱\alpha為模M的原根

舉一個例子:

一個M=5N=4點數論轉換與反轉換如下,取\alpha = 2,注意此時N^{-1}=4

正轉換 \begin{pmatrix} F[0] \\ F[1] \\ F[2] \\ F[3] \end{pmatrix}=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 3 \\1 & 4 & 1 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix}\begin{pmatrix} f[0] \\ f[1] \\ f[2] \\ f[3] \end{pmatrix}\pmod{M}

反轉換 \begin{pmatrix} f[0] \\ f[1] \\ f[2] \\ f[3] \end{pmatrix}=\begin{pmatrix} 4 & 4 & 4 & 4 \\ 4 & 2 & 1 & 3 \\4 & 1 & 4 & 1 \\ 4 & 3 & 1 & 2 \end{pmatrix}\begin{pmatrix} F[0] \\ F[1] \\ F[2] \\ F[3] \end{pmatrix}\pmod{M}

數論轉換的性質[编辑]

(1) 正交性質

數論轉換矩陣的每個列是互相正交的,即\sum_{n=0}^{N-1}\alpha^{nl}\alpha^{-nk}=\begin{cases} N \quad if\ k=l\\ 0 \quad if\ k\ne l\end{cases} \pmod{M}

(2) 對稱性

f[n]=f[N-n],則f[n]的數論轉換F[k]也會有F[k]=F[N-k]的特性。

f[n]=-f[N-n],則f[n]的數論轉換F[k]也會有F[k]=-F[N-k]的特性。

(3) 反數論轉換可由正數論轉換實現

f[n]=N^{-1}\sum_{k=0}^{N-1}F[k]\alpha^{-nk}=N^{-1}\sum_{-k=0}^{N-1}F[-k]\alpha^{nk},即N^{-1}F[-k]的數論轉換。

步驟一:把F[k]改寫成F[-k],若F[k]=F_0,F_1,,F_2\ldots,F_{N-1} ,則F[-k]=F_0,F_{N-1},\ldots,F_2,F_1

步驟二:求F[-k]的數論轉換。

步驟三:乘上N^{-1}

(4) 線性性質

f[n]\leftrightarrow F[k]g[n]\leftrightarrow G[k],(\leftrightarrow表互為數論轉換對)則有af[n]+bg[n]\leftrightarrow aF[k]+bg[k]\pmod{M}

(5) 平移性質

f[n]\leftrightarrow F[k],則f[n+l]\leftrightarrow \alpha^{-lk}F[k]\pmod{M},而且f[n]\alpha^{nl}\leftrightarrow F[k+l]

(6) 圓周摺積性質

f[n]\leftrightarrow F[k]g[n]\leftrightarrow G[k],則f[n]\otimes g[n]\leftrightarrow F[k]G[k]\pmod{M},而且f[n]g[n]\leftrightarrow \frac{1}{N}F[k]\otimes G[k]\pmod{M}。(\otimes代表圓形摺積。)

這個性質是數論轉換可以用來作為摺積的快速演算法的主要原因。

(7) 巴斯瓦定理(Parseval's Theorem)

f[n]\leftrightarrow F[k],則N\sum_{n=0}^{N-1}f[n]f[-n]=\sum_{k=0}^{N-1}F^2[k]\pmod{M},而且N\sum_{n=0}^{N-1}f^2[n]=\sum_{k=0}^{N-1}F[k]F[-k]\pmod{M}

快速數論轉換[编辑]

如果轉換點數N是一個2的次方,則可以使用類似基數-2快速傅立葉變換的蝴蝶結構來有效率的實現數論轉換。同樣的互質因子算法也可以應用在數論轉換上。

\begin{matrix}F[k]&=&\sum_{n=0}^{N-1}f[n]\alpha^{nk}\\ \ &=&\sum_{r=0}^{N/2-1}f[2r]\alpha^{2rk}+\sum_{r=0}^{N/2-1}f[2r+1]\alpha^{(2r+1)k} \\ \ & = & \sum_{r=0}^{N/2-1}f[2r](\alpha^2)^{rk}+\alpha^k\sum_{r=0}^{N/2-1}f[2r+1](\alpha^2)^{rk}\\ \ &=& \begin{cases} G[k]+\alpha^kH[k]\quad 0\le k\le \frac{N}{2}-1 \\ G[k-\frac{N}{2}]+\alpha^kH[k-\frac{N}{2}]\quad \frac{N}{2}\le k\le N-1 \end{cases}\end{matrix}

其中,G[k]=\sum_{r=0}^{N/2-1}f[2r](\alpha^2)^{rk}H[k]=\sum_{r=0}^{N/2-1}f[2r+1](\alpha^2)^{rk}。 因此一個N點數論轉換可以拆解成兩個\frac{N}{2}點的數論轉換。

N,\alpha ,M的選擇[编辑]

由於數論轉換可以擁有類似快速傅立葉變換的快速演算法,因此通常N會選擇適合使用快速演算的值,比如說取為2的次,或是可以分解成許多小質數相乘的數。

在數論轉換中,需要大量地和\alpha的冪次做乘法,因此,如果可以取\alpha為2或2的冪次,則每一次的乘法在二進制中只會是一個移位的操作,可以省下大量的乘法運算。

因為要做模M的運算,所以M的二進位表示法中,1的個數越少越好,同時M的值不能取太小,這是因為數論轉換後的值都小於M,因此當真實的摺積的結果會大於M時就會發生錯誤,所以必須謹慎選取M的大小。

特殊的數論轉換[编辑]

梅森質數數論轉換[编辑]

梅森質數是指形如2^p-1的質數記做M_p,其中p是一個質數。

在梅森質數數論轉換中,取M=M_p,可以證明\alpha , N可以如下選取:

(1) \alpha = 2, N=p, N^{-1}=M_p-\frac{M_p-1}{p}

(2) \alpha = -2, N=2p, N^{-1}=M_p-\frac{M_p-1}{2p}

在這兩種選取方式下,由於\alpha是2的冪次,所以只需移位運算,但N不是2的冪次,所以基數-2的蝴蝶結構不適用於此例中,同時N為質數或一個質數的兩倍,並不是一個可以拆解成很多質因數乘積的數,因此也無法由互質因子演算法得到太大的好處。梅森質數數論轉換通常用於較短序列的摺積運算

費馬數數論轉換[编辑]

費馬數是指形如2^{2^t}+1的數記做F_t

在費馬數數論轉換中,取M=F_t,可以證明在0<t\le 4之下\alpha , N可以如下選取:

(1) \alpha = 2, N=2^{t+1}

(2) \alpha = 3, N=F_t-1

在這兩種選取方式下,N是2的冪次,所以基數-2的蝴蝶結構適用於此例中,而若\alpha是2的冪次,只需移位運算。費馬數數論轉換通常用於較長序列的摺積運算。

參考資料[编辑]

[1] R.C. Agarval and C.S. Burrus,"Number Theoretic Transforms to Implement Fast Digital Convolution," Proc. IEEE, vol.63, no.4, pp. 550-560, Apr. 1975.

[2] I. Reed and T.K. Truong,"The use of finite fileds to compute convolution," IEEE Trans. Info. Theory, vol.21 ,pp.208-213, Mar. 1975.