[發(fā)明專利]一種利用數(shù)論變換計算循環(huán)卷積的電路結(jié)構(gòu)

有效

• 申請?zhí)枺?/td>: 201410062873.5
• 申請日: 2014-02-25
• 公開（公告）號: CN103870438A
• 公開（公告）日: 2014-06-18
• 發(fā)明（設(shè)計）人: 韓軍;楊春峰;曾曉洋
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: G06F17/14
• 分類號: G06F17/14;G06F7/72
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;王潔平

技術(shù)領(lǐng)域

本發(fā)明屬于集成電路設(shè)計技術(shù)領(lǐng)域，具體涉及一種新型利用數(shù)論變換計算循環(huán)卷積的電路結(jié)構(gòu)。?

背景技術(shù)

卷積是一種線性運算，其本質(zhì)是滑動平均思想，廣泛應(yīng)用于圖像濾波，圖像處理中常見的mask運算就是卷積。另外，卷積在工程和數(shù)學(xué)中還有很多其他應(yīng)用，統(tǒng)計學(xué)中，加權(quán)的滑動平均是一種卷積。概率論中，兩個統(tǒng)計獨立變量X與Y的和的概率密度函數(shù)是x與Y的概率密度函數(shù)的卷積。聲學(xué)中，回聲可以用源聲與一個反映各種反射效應(yīng)的函數(shù)的卷積表示。電子工程與信號處理中，任意一個線性系統(tǒng)的輸出都可以通過將輸入信號與系統(tǒng)函數(shù)做卷積獲得，物理學(xué)中，任意一個線性系統(tǒng)都存在卷積。?

所謂兩個序列xn（n=0,1,…,N-1）和hn(n=0,1,…,N-1)的循環(huán)卷積是指：?

上式中的符號<k>_N表示整數(shù)k模N的最小非負剩余，也就是整數(shù)k被正整數(shù)N?除所余的非負整數(shù)。

循環(huán)卷積可用變換法實現(xiàn)，一般常用的變換為快速傅里葉變換（FFT）。分別計算xn和hn（n=0,1,2,…,N-1）的FFT，即Xk，Hk，將它們相乘得到y(tǒng)n的FFT，即Yk=Xk*Hk（k=0,1,2,…,N-1），最后將Yk進行反變換（IFFT），就得到y(tǒng)n，示意圖如圖1所示。?

由圖1可知，利用FFT計算長度為N的序列的循環(huán)卷積，需要兩次正變換，一次擬變換和N次乘法，一個N點的FFT變換需要O(Nlog₂N)次乘法。?

以數(shù)論為基礎(chǔ)的計算循環(huán)卷積的方法叫做數(shù)論變換（NTT）。特別引人關(guān)注的是NTT中有一種Fermata數(shù)變換（FNT），這樣變換只需要加法（減法）及移位操作而不用乘法，從而提高了運算速度。FNT還消除了FFT帶來的舍入誤差，故能得到高精度的卷積，并且不需要基函數(shù)的存取，從而節(jié)省的存儲空間。但是，F(xiàn)NT也有缺點，主要是沒有明顯的物理意義；序列{xn}的變換{Xk}不再是頻譜，因此中間過程不能如FFT那樣用于測頻；在加上字長受限制，不夠靈活。?

數(shù)論變換（NTT）是一種有限域內(nèi)的運算，它和FFT一樣都是一種線性正交變換，具有FFT類似的性質(zhì)，具有循環(huán)卷積特性，因此可用于計算兩個序列的循環(huán)卷積，并且具有FFT一樣的快速算法。但不同之處有兩點，第一是以α代替FFT中的W_N，由于α是一正整數(shù)，不像FFT那樣要預(yù)先儲存基函數(shù)W_N；第二是每一步運算過程都要判斷一下中間量是否超過模M，如果超過模M，就應(yīng)去小于模M的同余值，以防溢出。由NTT計算序列循環(huán)卷積的過程示意圖如圖2所示。?

對序列xn進行數(shù)論變換的公式如下：?

其中變換矩陣T為：

對于費馬數(shù)論變換（FNT），模M為費馬數(shù)（M=2^N+1），整數(shù)α為M的N階本源單位根，N為序列xn的長度。

與快速傅里葉變換（FFT）一樣，數(shù)論變換（NTT）也有快速算法，快速算法的流程圖如圖6所示。?

這相當于FFT的按頻率抽取的算法，同樣可用按時間抽取的算法。用上述快速算法，可將原來所需的N²個乘法降為Nlog₂N次乘法。如果α是2或者2的冪，則只需要Nlog₂N次移位操作。?

為了使NTT具有快速演算的效果，通常對M、N、α的要求是：?

1.????變換長度N必須適合FFT類型的快速演算，因而要求N是高度復(fù)合的數(shù)。當

N=2^m時，就能滿足這樣的要求，同時，由于N表示輸入采樣點的個數(shù)，所以不能過小。

2.????數(shù)論變換的一個特點是用一個整數(shù)α代替FFT中的W_N，F(xiàn)FT需要大量的復(fù)乘，?

而NTT只需作α的方冪的乘法。如果能選擇α，使得α的冪是一種簡單運算，那就能起到節(jié)省運算的目的。如果選取α為2或2的冪，這時在作2的方冪的乘法時，僅為移位操作。

3.????為了便于模M的運算，當用二進制表示M時，其位數(shù)（一般稱為字長）越小?

越好。但M的值不能過小，以防止溢出。對于費馬數(shù)論變換（FNT），M取作費馬數(shù)：

M?=?Ft?=?2^b?+?1，其中b=2^t?(t=0,1,2,…)

對于FNT，N=2b=2^t+1，α=2，能滿足要求，例如當t=5時，M=2³²+1，N=64；