一種剩余數(shù)到制圖中模集合的新方法

一種剩余數(shù)到制圖中模集合的新方法

剩余數(shù)據(jù)系統(tǒng)在通信系統(tǒng)、數(shù)據(jù)處理和數(shù)字數(shù)據(jù)處理等領(lǐng)域得到了前所未有的關(guān)注。余數(shù)系統(tǒng)是將一個位寬很長的二進制數(shù)轉(zhuǎn)換成一組兩兩互質(zhì)的模集合下位寬比較小剩余數(shù)來表示,而且每一個模通道之間的運算都是獨立的,在整個運算過程中保持位寬不變,從而大大降低了在傳統(tǒng)權(quán)重數(shù)電路中由于進位傳播而造成的延遲,并且保證了運算的精度,從而保證了超高速信息流的實時通信。一個典型的余數(shù)系統(tǒng)由三個部分組成,一是前置轉(zhuǎn)換(二進制數(shù)至神余數(shù)轉(zhuǎn)換,即前向轉(zhuǎn)換);二是運算模塊(模通道運算);三是后置轉(zhuǎn)換(剩余數(shù)至二進制數(shù)轉(zhuǎn)換,即后向轉(zhuǎn)換)。由于傳統(tǒng)的數(shù)字電路是二進制系統(tǒng),為了保證剩余數(shù)系統(tǒng)被二進制系統(tǒng)接受,后置轉(zhuǎn)換,即剩余數(shù)至二進制轉(zhuǎn)換電路的設(shè)計至關(guān)重要。模集合的形式直接決定了整個剩余數(shù)系統(tǒng)模通道運算單元和后置轉(zhuǎn)換器電路的復雜度;同時,模集合的選取也直接決定了基于該模集合的剩余數(shù)系統(tǒng)的處理能力。近年來,為了滿足對大動態(tài)范圍和高并行性的需求,一些動態(tài)范圍為5n位的模集合相繼被提出。針對需要高并行性和動態(tài)范圍的問題,本文提出四基數(shù)模集合{2n-1,2n+1,2n,22n-1-1},該模集合的動態(tài)范圍達到5n-1,每一個模均具有2n±1形式。另外,該模集合的乘法逆元均符合閉合形式,剩余數(shù)至二進制數(shù)轉(zhuǎn)換器的電路形式可以得到簡化。本研究所提出的剩余數(shù)至二進制轉(zhuǎn)換算法基于新中國剩余數(shù)定理2(NewCRT-IⅡ)實現(xiàn),硬件完全由基本的加法器構(gòu)成。1確定余數(shù)集作2m3m4設(shè)m1、m2,m3,m4為4個兩兩互素的正整數(shù)(mi為模,i=1,2,3,4)。設(shè)M=m1m2m3m4,|X|mi=xi定義為X取模mi所得到的余數(shù)。通過新中國余數(shù)定理2(NewCRT-Ⅱ),余數(shù)表示(x1,x2,x3,x4)RNS能得到權(quán)重數(shù)X在0~M區(qū)間有唯一解。即式中:k1、k2、k表示乘法逆元,滿足2模間的互質(zhì)當n為任意整數(shù)時,該4基數(shù)模集合(2n-1,2n+1,2n,22n-1-1)模之間必須兩兩互質(zhì)。根據(jù)k1、k2、k、4基數(shù)模集合{2n-1,2n+1,2n,22n-1-1}表示下的剩余數(shù)(x1,x2,x3,x4)RNS轉(zhuǎn)換為二進制數(shù)X:式(4)中:3實現(xiàn)電路在此設(shè)剩余數(shù)(x1,x2,x3,x4)RNS對應剩余數(shù)的二進制表示為:3.1旋轉(zhuǎn)進位保留加法器fao根據(jù)式(5),X12表示為式中:xn,i:j表示截取xn的第i位至第j位,ue0afn,i:j表示對xn的第i位至第j位按位取反,(1)k表示k個1。符號“&”表示拼接并置。t1、t2、t3通過圖1的操作數(shù)準備單元1實現(xiàn),只需要n+1個非門。t1、t2、t3通過一個n位進位回轉(zhuǎn)(EAC)的進位保留加法器(CSA)轉(zhuǎn)換成兩個操作數(shù),隨后通過模2n-1加法器實現(xiàn)A。由于t1最低位有n-1位’1’,所以該回旋進位保留加法器的低n-1位全加器(FA)可以用n-1個同或/或門對(XNOR/OR)代替。根據(jù)式(6),X34表示為式(8)中:同樣,t4、t5、t6通過操作數(shù)準備單元1,只需要n個非門即可實現(xiàn)。B用1個3輸入模2n加法器實現(xiàn),該模塊由1個n位寬進位保留加法器和1個模2n加法器實現(xiàn)。由于t6有n-1位‘0’和一位‘1’,進位保留加法器的n全加器(FA)可以用1個同或/或門對(XNOR/OR)和n-1個異或/與門對(XOR/AND)代替,以減小電路面積。3.3加法器的實現(xiàn)將式(7)和式(8)代入式(4),得到:則C表示為將X34、C代入式(9),X進一步表示為式(10)中:D=B+2nC=C2n-1:0&Bn-1:0=D3n-1:0。則最終得:操作數(shù)t7、t8、t9、t12通過一些簡單拼接移位和4n+1個反相器實現(xiàn),通過圖1操作數(shù)準備單元2完成。t7、t8、t9、t12通過一個兩級的進位可回轉(zhuǎn)的進位保留加法器(CSA)轉(zhuǎn)換成兩個操作數(shù),然后通過一個模22n-1加法器實現(xiàn)C。由于t8和t9分別n和n-1位’1’,該2級的回旋進位保留加法器的2n-1全加器(FA)可以用同樣個數(shù)的同或/或門對(XNOR/OR)代替,以減小電路面積。操作數(shù)準備單元3提供操作數(shù)D和E,該模塊通過簡單的移位拼接即可實現(xiàn)。最終X的實現(xiàn),即就是式(11)的實現(xiàn)通過一個5n-1位的補碼加法器完成。舉例:設(shè)n=4,則(m1,m2,m3,m4)分別為(15,17,16,127)。輸入X的剩余數(shù)表示為(10,12,15,122),其二進制表示分別為x1=(1010)2,x2=(01100)2,x3=(1111)2,x4=(1111010)2。根據(jù)前面的分析,t1=(0101)2,t2=(1111)2,t3=(1001)2,根據(jù)A=|t1+t2+t3|2n-1,得到A=(1110)2?；贐=|t4+t5+t6|2n,而t4=(1010)2,t5=0000,t6=(1)2,得到B=(1011)2。根據(jù)C=|(t7+t8+t9+t12)|22n-1,其中t7=(01001111)2,t8=(01001111)2,t9=(01111110)2,t12=(001000100)2,得C=(63)10。根據(jù)D=(1019)10,E=(130554)10。最終,根據(jù)式(16)得到X=E-D=(129535)10。4快速并行的編碼裝置為了進行定性評估,根據(jù)動態(tài)范圍,本文與文獻的理論模型進行對比。所有比較模型的面積和延遲均采用1位全加器(FA)作為基本單位進行比較。模加法器有多種實現(xiàn)方法,為了對比公平,本研究以及對比文獻全部采用具有0的唯一表示的快速并行前綴模2n-1加法器。在該模型中,每一級n位進位保留需要并行n個加法器實現(xiàn),其所占用面積為nAFA,而延時為tFA;普通二進制n位加法器由n個全加器級聯(lián)而成,所以其面積為nAFA,導致延時為ntFA;具有0的唯一表示的快速并行前綴模2n-1加法器的面積為nAFA,延時為2ntFA。本轉(zhuǎn)換器和其他模集合轉(zhuǎn)換器面積和延時對比如表1示。從中可以看出,無論是在硬件消耗還是延時,在論文上都是優(yōu)于文獻給出的轉(zhuǎn)換器模型。5動態(tài)范圍與加文中給出4基數(shù)模集合{2n-1,2n+1,2n,22n-1-1}的剩余數(shù)至二進制數(shù)轉(zhuǎn)換算法?；谛轮袊鄶?shù)定理Ⅱ轉(zhuǎn)換算法,實現(xiàn)了該剩余數(shù)系統(tǒng)的剩余數(shù)至二進制數(shù)轉(zhuǎn)換(后向轉(zhuǎn)換),該系統(tǒng)可處理數(shù)動態(tài)范圍達5n-1位。模形式簡單,乘法逆元全部具有閉合形式,使電路全部基于加法器實現(xiàn)。理論分析表明,在具有相同動態(tài)范圍的同類轉(zhuǎn)換器中,本研究的轉(zhuǎn)換器性能表現(xiàn)優(yōu)異。證明:已知2n,2n-1和2n+1之間兩兩互質(zhì)(n為任意整數(shù))。在此,根據(jù)歐幾里得定理,證明22n-1-1與2n,2n-1和