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

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

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