數論轉換

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

而在數論轉換中，資料向量需要乘上的矩陣是一個整數的矩陣，這使得我們不需要作浮點數的乘法運算，更進一步，在模數為 $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\neq 1$ 時 $N$ 和 $M$ 互質)

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

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

舉一個例子：

一個 $M=5$ 的 $N=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\neq 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 ^{k}H[k]\quad 0\leq k\leq {\frac {N}{2}}-1\\G[k-{\frac {N}{2}}]-\alpha ^{k}H[k-{\frac {N}{2}}]\quad {\frac {N}{2}}\leq k\leq 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\leq 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.