一種中國剩余定理權(quán)重預(yù)分配方法

馬 上，汪陳浩，陳紅艷，胡劍浩

?

一種中國剩余定理權(quán)重預(yù)分配方法

馬 上1，汪陳浩1，陳紅艷2，胡劍浩1

(1. 電子科技大學(xué)通信抗干擾技術(shù)國家級(jí)重點(diǎn)實(shí)驗(yàn)室 成都 611731; 2. 成都信息工程大學(xué)電子工程學(xué)院 成都 610225)

(CRT)是獲取余數(shù)系統(tǒng)(RNS)權(quán)重信息的基本理論之一。該文提出了一種CRT的權(quán)重預(yù)分配方法，通過在一定約束條件下預(yù)分配CRT中的權(quán)重，使之運(yùn)算結(jié)果保持不變，從而減小獲取RNS權(quán)重信息或后向轉(zhuǎn)換的復(fù)雜度。該方法使得CRT成為本文方法的一個(gè)特例，并可通過不同的預(yù)分配權(quán)重來獲得不同的電路實(shí)現(xiàn)結(jié)構(gòu)，較CRT方法具有更好的靈活性。此外，結(jié)合混合基轉(zhuǎn)換(MRC)還給出了基于這種方法的一個(gè)后向轉(zhuǎn)換應(yīng)用實(shí)例。分析結(jié)果表明基于本文方法的RNS后向轉(zhuǎn)換具有較好的靈活性，從而可優(yōu)化RNS后向轉(zhuǎn)換的實(shí)現(xiàn)結(jié)構(gòu)。

; 混合基轉(zhuǎn)換; 權(quán)重預(yù)分配; 后向轉(zhuǎn)換; 余數(shù)系統(tǒng)

RNS在進(jìn)行乘加等基本運(yùn)算時(shí)具有良好的并行特性[1]，在高速、低功耗數(shù)字信號(hào)處理(digital signal processing，DSP)應(yīng)用中得到了關(guān)注和研究[2-4]。權(quán)重?cái)?shù)字表征系統(tǒng)中，數(shù)值符號(hào)所在的位置被賦予了一定的數(shù)值意義，被稱為權(quán)重，數(shù)值的大小不僅與符號(hào)本身有關(guān)，還跟符號(hào)在數(shù)中的位置有關(guān)。余數(shù)系統(tǒng)是一種非權(quán)重?cái)?shù)值表征系統(tǒng)，它將動(dòng)態(tài)范圍較大的整數(shù)通過求模運(yùn)算映射到多個(gè)小動(dòng)態(tài)范圍的并行計(jì)算通道中，以此來減小乘加運(yùn)算的位寬。因此，在乘加密集型的數(shù)字信號(hào)處理系統(tǒng)中，基于余數(shù)系統(tǒng)的VLSI實(shí)現(xiàn)將帶來良好的時(shí)延和面積特性。

但由于余數(shù)系統(tǒng)是一個(gè)非權(quán)重系統(tǒng)，通過權(quán)重系統(tǒng)到余數(shù)系統(tǒng)的轉(zhuǎn)換，原本在權(quán)重系統(tǒng)中顯而易見的數(shù)值特性被隱藏起來了，給余數(shù)系統(tǒng)的應(yīng)用帶來了挑戰(zhàn)[5]。通常，在運(yùn)算中的大小比較[6]、符號(hào)檢測(cè)[7]、數(shù)值縮放[8]、奇偶檢測(cè)[9]、基擴(kuò)展[10]等基本問題都需要一定程度的獲取權(quán)重信息。因此，余數(shù)系統(tǒng)后向轉(zhuǎn)換(residue to binary conversion, R/B)是余數(shù)系統(tǒng)應(yīng)用中的關(guān)鍵之一，得到了廣泛而深入的研究。

有關(guān)余數(shù)系統(tǒng)到權(quán)重系統(tǒng)的轉(zhuǎn)換(或后向轉(zhuǎn)換)研究中，可按照通用性分為兩類，一類是通用的轉(zhuǎn)換算法，它適用于任何類型的余數(shù)基的后向轉(zhuǎn)換，但其結(jié)構(gòu)往往不是最優(yōu)化的[11-13]。因此，更多的研究集中在結(jié)合余數(shù)基的特點(diǎn)進(jìn)行優(yōu)化設(shè)計(jì)，這是主要的研究方法[14-25]，但通用性較差。無論何種類型的轉(zhuǎn)換，其理論基礎(chǔ)均為CRT或MRC。其中CRT應(yīng)用最為廣泛，它涉及一個(gè)較大的模運(yùn)算，而且其中的乘法操作數(shù)也較大，因此基于CRT的研究大多關(guān)注如何解決這兩個(gè)問題[11-26]；而混合基轉(zhuǎn)換通常是一個(gè)嚴(yán)格的迭代過程，降低了RNS的并行性，在多通道余數(shù)基后向轉(zhuǎn)換中，它常被用于完成最后一步轉(zhuǎn)換[15]。按照實(shí)現(xiàn)方法，余數(shù)系統(tǒng)到權(quán)重系統(tǒng)的轉(zhuǎn)換可分為基于查找表(look-up table，LUT)和組合邏輯兩種基本方法，基于查找表的設(shè)計(jì)方法可以實(shí)現(xiàn)通用的R/B轉(zhuǎn)換，但在大動(dòng)態(tài)范圍時(shí)需要巨大的硬件消耗[27]；而基于組合邏輯的設(shè)計(jì)方法主要結(jié)合余數(shù)基的具體形式進(jìn)行優(yōu)化設(shè)計(jì)，以減小轉(zhuǎn)換的時(shí)延和硬件消耗。

在通用的RNS后向轉(zhuǎn)換研究中，文獻(xiàn)[11-12]給出了它的幾種變型形式，稱為CRT-I、CRT-II和CRT-III。其中，CRT-I將MRC的轉(zhuǎn)換并行化，它仍需要類似CRT的模運(yùn)算和乘法運(yùn)算位寬。CRT-II用于實(shí)現(xiàn)多通道余數(shù)系統(tǒng)的后向轉(zhuǎn)換，它首先利用CRT進(jìn)行每兩個(gè)余數(shù)通道的后向轉(zhuǎn)換，然后將轉(zhuǎn)換后的通道合并成一個(gè)通道再進(jìn)行下一級(jí)的兩通道轉(zhuǎn)換，減小了CRT的模乘法運(yùn)算位寬，但同時(shí)也削弱了CRT的并行性。CRT-III針對(duì)特殊的非互質(zhì)的余數(shù)系統(tǒng)進(jìn)行后向轉(zhuǎn)換，它是CRT-II的擴(kuò)展。文獻(xiàn)[12]對(duì)CRT-I和CRT-II理論做了進(jìn)一步的闡述。文獻(xiàn)[13]基于CRT引入一個(gè)縮放因子來避免大的模運(yùn)算，采用了脈動(dòng)結(jié)構(gòu)，其優(yōu)點(diǎn)在于具有統(tǒng)一的實(shí)現(xiàn)結(jié)構(gòu)，但需要采用(為余數(shù)通道個(gè)數(shù))的處理單元陣列及控制邏輯，具有較高的延時(shí)和面積復(fù)雜度。

本文針對(duì)CRT基本理論，通過引入預(yù)分配權(quán)重的方法來獲得高效的RNS后向轉(zhuǎn)換，使得CRT這一經(jīng)典而古老的定理成為本文算法的一個(gè)特例，將該方法稱為extension of CRT(ECRT)。該方法在滿足一定限定條件下，針對(duì)不同的優(yōu)化目標(biāo)和余數(shù)基類型，改變CRT中固有計(jì)算權(quán)重，具有極好的靈活性?；谠撍惴ńo出了一個(gè)應(yīng)用實(shí)例，最后進(jìn)行了算法的對(duì)比分析。

1 余數(shù)系統(tǒng)理論背景

RNS到權(quán)重系統(tǒng)的轉(zhuǎn)換被稱為混合基轉(zhuǎn)換，任何一個(gè)RNS都可同一個(gè)混合基系統(tǒng)(mixed radix system，MRS)相關(guān)聯(lián)，它是一個(gè)權(quán)重系統(tǒng)，其權(quán)重

2 轉(zhuǎn)換算法

2.1 基于預(yù)分配權(quán)重的中國剩余定理擴(kuò)展算法

的RNS后向轉(zhuǎn)換如式(1)所示，令，則：

因此，可以將CRT的運(yùn)算視為一矩陣運(yùn)算過程，只要保證式(5)的權(quán)重的余數(shù)矩陣與的運(yùn)算結(jié)果為，則可以改變和，特殊的或可能簡化后向轉(zhuǎn)換復(fù)雜度。

若式(7)運(yùn)算成立，則運(yùn)算結(jié)果保持不變。

顯然，

據(jù)此，可得到：

本文定義式(8)和式(9)為CRT運(yùn)算的前處理過程，其復(fù)雜度直接與所指定的相關(guān)。

2.2 權(quán)重分配的約束條件

1) 可逆性約束

2) 存在性約束

2.3 數(shù)值計(jì)算舉例

3 基于CRT擴(kuò)展算法的應(yīng)用實(shí)例

下面給出一種基于本文CRT擴(kuò)展算法的簡單應(yīng)用實(shí)例，在該示例中將利用擴(kuò)展算法實(shí)現(xiàn)RNS到MRS的并行轉(zhuǎn)換，并且消除CRT中的模運(yùn)算。

3.1 權(quán)重預(yù)分配過程

其對(duì)應(yīng)的余數(shù)矩陣為：

對(duì)應(yīng)的混合基矩陣為：

對(duì)應(yīng)的余數(shù)矩陣為：

3.2 轉(zhuǎn)換過程

根據(jù)式(17)以及前述的限定條件，新指定的余數(shù)矩陣為：

其逆矩陣為：

根據(jù)式(8)，新的權(quán)重下的余數(shù)表示為：

由以上討論，該實(shí)例對(duì)余數(shù)基的限定形式為

下取值)都滿足該限定條件。本文所舉應(yīng)用實(shí)例的實(shí)現(xiàn)框圖如圖1所示，其中為的符號(hào)，負(fù)數(shù)時(shí)為“1”，正數(shù)則為“0”。

3.3 數(shù)值計(jì)算實(shí)例

通過該實(shí)例使用本文所提出的CRT擴(kuò)展算法，消除了RNS到MRS轉(zhuǎn)換中的迭代過程，同時(shí)將所有運(yùn)算限定在較小的模運(yùn)算中，其對(duì)復(fù)雜度的降低顯而易見。這里所舉實(shí)例可能不是最優(yōu)化的，僅為了闡述利用本文的擴(kuò)展算法如何進(jìn)行權(quán)重指定等過程。

表1 本文的擴(kuò)展算法同MRC、CRT及其變型的比較

4 算法分析與比較

1) 指定比CRT的權(quán)重更小的權(quán)重，以簡化式(10)中的乘法運(yùn)算；

2) 可以從混合基轉(zhuǎn)換的角度，指定便于混合基運(yùn)算的權(quán)重，這種混合基的指定并不限于當(dāng)前的余數(shù)基形式，例如4中的應(yīng)用實(shí)例，若余數(shù)基為，進(jìn)行式(12)運(yùn)算的混合基可選擇為，則可以通過最高位的模運(yùn)算消除CRT中的模運(yùn)算并直接得到最后的十進(jìn)制表示；

3) 根據(jù)特定的余數(shù)基形式，采用數(shù)值搜索的方法獲得需要指定的權(quán)重，簡化的后向轉(zhuǎn)換結(jié)構(gòu)。

本文所提出的CRT擴(kuò)展算法極其靈活，針對(duì)不同的應(yīng)用場(chǎng)合可進(jìn)行相應(yīng)的權(quán)重分配，其目的在于消除CRT中較大的模運(yùn)算，根據(jù)不同的權(quán)重分配方式其復(fù)雜度差別較大。表1給出了本文算法與MRC、CRT及其變型的定性比較。

對(duì)于CRT，由式(1)可知，它支持任意的傳統(tǒng)互質(zhì)余數(shù)基的R/B轉(zhuǎn)換，其乘法運(yùn)算中的操作數(shù)至少為，該值可能大于動(dòng)態(tài)范圍，且最后需要一個(gè)模運(yùn)算，但其運(yùn)算可以并行進(jìn)行，由CRT可知，使用CRT需要進(jìn)行次模乘法和次模加法，CRT對(duì)應(yīng)了本文算法為一個(gè)單位陣的情況。而對(duì)于其變型CRT-I，減小了CRT中的權(quán)重，從而減小了乘法運(yùn)算的復(fù)雜度，但仍然需要模運(yùn)算，而且增加了模加法運(yùn)算的次數(shù)，需要次，而需要次模乘法運(yùn)算，CRT-I對(duì)應(yīng)了本文算法預(yù)分配權(quán)重為的情況。而對(duì)于CRT-II，其本質(zhì)在于不斷地進(jìn)行兩通道R/B轉(zhuǎn)換來實(shí)現(xiàn)多通道余數(shù)系統(tǒng)到權(quán)重系統(tǒng)的轉(zhuǎn)換，因此降低了CRT的并行性，但該算法在每一次兩通道轉(zhuǎn)換中可以減小CRT運(yùn)算中的模運(yùn)算，最好情況下可以將最后模運(yùn)算和乘法運(yùn)算的位寬減至動(dòng)態(tài)范圍位寬的一半，而模加法和模乘法的次數(shù)分別大于和次。CRT-III則基于CRT-II來解決特殊的非互質(zhì)RNS的后向轉(zhuǎn)換問題，其復(fù)雜度與CRT-II類似。混合基轉(zhuǎn)換MRC則是一個(gè)迭代運(yùn)算過程，需要較大的時(shí)延和較多的模乘加運(yùn)算次數(shù)，其優(yōu)點(diǎn)在于具有較小的模運(yùn)算和乘法運(yùn)算位寬。本文所提出的ECRT算法包含了CRT及其變型，它們是本文算法的一個(gè)特例，通過不同應(yīng)用場(chǎng)合下的權(quán)重優(yōu)化可得到簡化的轉(zhuǎn)換過程。本文算法的重點(diǎn)在于給出RNS的后向轉(zhuǎn)換優(yōu)化途徑，而不在于針對(duì)具體余數(shù)基或者具體轉(zhuǎn)換算法進(jìn)行討論。

本文所提算法復(fù)雜度與權(quán)重選擇具有較大關(guān)聯(lián)，因此表2給出了對(duì)余數(shù)系統(tǒng)進(jìn)行后向轉(zhuǎn)換的復(fù)雜度的分析比較，其中余數(shù)基兩兩互質(zhì)，因此表中不含有CRT-III，本文算法權(quán)重選擇如圖1所示，且選擇，由表2中可知本文所提算法具有最小的計(jì)算位寬與計(jì)算次數(shù)。

5 結(jié) 束 語

本文提出了一種中國剩余定理的擴(kuò)展算法，該算法通過預(yù)先指定CRT中的權(quán)重來獲得靈活高效的余數(shù)系統(tǒng)到權(quán)重系統(tǒng)的轉(zhuǎn)換算法，降低VLSI實(shí)現(xiàn)復(fù)雜度。同時(shí)，本文還給出了該算法的權(quán)重指定的限定條件，滿足限定條件下的權(quán)重指定則可以保證運(yùn)算結(jié)果的正確性。通過本算法，使得中國剩余定理成為本文算法的一個(gè)特例，增加了應(yīng)用的靈活性。反過來，在權(quán)重分配過程中，結(jié)合限定條件可以對(duì)余數(shù)基進(jìn)行一定優(yōu)化限定，為余數(shù)基選擇給出了新的思路。

本文算法的提出為有關(guān)余數(shù)系統(tǒng)的應(yīng)用增添了新的研究內(nèi)容，在未來的研究工作中，可以對(duì)權(quán)重的預(yù)分配方法進(jìn)一步討論，也可以針對(duì)已有余數(shù)基進(jìn)行更優(yōu)化的后向轉(zhuǎn)換設(shè)計(jì)，從而有助于解決余數(shù)系統(tǒng)應(yīng)用中的有關(guān)后向轉(zhuǎn)換、大小比較、符號(hào)判斷、基擴(kuò)展等棘手問題。

[1] MA Shang, HU Jian-hao, WANG Chen-hao. A novel moduloadder for residue number system[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2013, 60(11): 2962-2972.

[2] LIU Y, LAI E M. Design and implementation of an RNS-based 2-D DWT processor[J]. IEEE Trans Consumer Electronics, 2004, 50(1): 376-385.

[3] PATRONIK P, BEREZOWSKI K, PIESTRAK S J, et al. Fast and energy-efficient constant-coefficient fir filters using residue number system[C]//International Symposium on Low Power Electronics and Design (ISLPED). Fukuoka: IEEE, 2011: 385-390.

[4] BAJARD J C, DIDIER L S, HILAIRE T. ρ-direct form transposed and residue number systems for filter implementations[C]//IEEE 54th International Midwest Symposium on Circuits and Systems (MWSCAS). Seoul: IEEE, 2011: 1-4.

[5] AMIR S M, SAEID S, AZADEH A E Z. Research challenges in next-generation residue number system architectures[C]//7th International Conference on Computer Science & Education (ICCSE). Melbourne, VIC: IEEE, 2012: 1658-1661.

[6] BANERJI D K, BRZOZOWSKI J A. Sign detection in residue number systems[J]. IEEE Transactions on Computers, 1969, 18(4): 313-320.

[7] DINA Y, PAVEL S. Universal approaches for overflow and sign detection in residue number system based on[C]//The Eighth International Conference on Systems (ICONS). Seville, Spain: ThinkMind, 2013: 77-81.

[8] MA Shang, HU Jian-hao, YE Yan-long, et al. Ascaling scheme for signed RNS integers and its VLSI implementation[J]. Science in China Series F: Information Sciences, 2010, 53(1): 203-212.

[9] MA S, HU J H, ZHANG L, et al. An efficient RNS parity checker for moduli setand its applications[J]. Science in China series F: Information Sciences, 2008, 51(10): 1563-1571.

[10] SHENOY M A P, KUMARESAN R. Fast base extension using a redundant modulus in RNS[J]. IEEE Transactions on Computers, 1989, 38(2): 292-297.

[11] WANG Y K. New Chinese remainder theorems[C]// Conference Record of the Thirty-Second Asilomar Conference on Signals, Systems & Computers. Pacific Grove: IEEE, 1998(1): 165-171.

[12] WANG Y K. Residue-to-binary converters based on new Chinese remainder theorems[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 2000, 47(3): 197-205.

[13] MEEHAN S J, O'NEIL S D, VACCARO J J. An universal input and output RNS converter[J]. IEEE Transactions on Circuits and Systems, 1990, 37(6): 799-803.

[14] CAO B, CHANG C H，SRIKANTHAN T. An efficient reverse converter for the 4-moduli setbased on the new Chinese remainder theorem[J]. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 2003, 50(10): 1296-1303.

[15] CAO B, SRIKANTHAN T, CHANG C H. Efficient reverse converters for four-moduli setsand[J]. IEEE Proceedings on Computers and Digital Techniques, 2005, 152(5): 687-696.

[16] WANG W, SWAMY M N S, Ahmad M O, et al. A comprehensive study of three moduli sets for residue arithmetic[C]//IEEE Canadian Conference on Electrical and Computer Engineering. Edmonton: IEEE, 1999(1): 513-518.

[17] MOHAN P V A. RNS-to-binary converter for a new three-moduli set[J]. IEEE Transactions on Circuits and Systems, 2007, 54(9): 775-779.

[18] WEY C L, LIN S Y. VLSI implementation of residue-to- binary converters for digital signal processing[C]//IEEE International Conference on Electro/Information Technology. Chicago: IEEE, 2007: 536-541.

[19] CAO B, CHANG C H，SRIKANTHAN T. A residue-to- binary converter for a new five-moduli set[J]. IEEE Transactions on Circuits and Systems, 2007, 54(5): 1041- 1049.

[20] WANG W, SWAMY M N S, AHMAD M O, et al. A study of the residue-to-binary converters for the three-moduli sets[J]. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 2003, 50(2): 235-243

[21] CAO B, SRIKANTHAN T, CHANG C H. Design of a high speed reverse converter for a new 4-moduli set residue number system[C]//Proceedings of the 2003 International Symposium on Circuits and Systems (ISCAS’03). Bangkok: IEEE, 2003(4): 520-523.

[22] WANG W, SWAMY M N S, AHMAD M O, et al. A high-speed residue-to-binary converter for three-moduliRNS and a scheme for its VLSI implementation[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 2000, 47(12): 1576-1581.

[23] WANG W, SWAMY M N S, AHMAD M O, et al. A parallel residue-to-binary converter for the moduli set[J]. VLSI Design, 2002, 14(2): 183-191.

[24] HIASAT A A. VLSI implementation of new arithmetic residue to binary decoders[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005, 13(1): 153-158.

[25] WANG Y, SONG X, ABOULHAMID M, et al. Adder based residue to binary number converters for[J]. IEEE Transactions on Signal Processing, 2002, 50(7): 1772-1779.

[26] GBOLAGADE K A, CHAVES R, Sousa L, et al. An improved RNS reverse converter for themoduli set[C]//Proceedings of 2010 IEEE International Symposium on Circuits and Systems (ISCAS). Paris: IEEE, 2010: 2103 - 2106.

[27] WEI L K, NICHOLAS C H V. Design of LUT based RNS reverse converters[C]//IEEE 17th International Symposium on Consumer Electronics (ISCE). Hsinchu: IEEE, 2013: 119-120.

[28] LIN S H, SHEU M H, LIN J S, et al. Efficient VLSI design for rns reverse converter based on new moduli set[C]//IEEE Asia Pacific Conference on Circuits and Systems. Singapore: IEEE, 2006: 2020-2023.

[29] AMIR S M, KEIVAN N, CHITRA D, et al. Efficient reverse converter designs for the new 4-moduli setsandbased on new CRTs[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2010, 57(4): 823-835.

[30] CHEN Shuang-ching, WEI Shu-gang. Weighted-to-residue and residue-to-weighted converters with three-modulisigned-digit architectures. Proceedings [C]//2006 IEEE International Symposium on Circuits and Systems(ISCAS). Island of Kos: IEEE, 2006: 3365-3368.

[31] ANDREAS P, LARS B. Reverse conversion architectures for signed-digit residue number systems[C]//2006 IEEE International Symposium on Circuits and Systems(ISCAS). Island of Kos: IEEE, 2006: 2701-2704.

[32] JIANG Chang-jun, WEI Shu-gang. Residue-weighted number conversion for moduli setusing signed-digit number[C]//IEEE 10th International New Circuits and Systems Conference (NEWCAS). Montreal: IEEE, 2012: 9-12.

編 輯 葉 芳

A Weight Pre-Assignment Scheme for Chinese Remainder Theorem

MA Shang1, WANG Chen-hao1, CHEN Hong-yan2, and HU Jian-hao1

(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China611731;2. School of Electronic Engineer,Chengdu 610255)

Chineseis one of the basic theorem in obtaining the weighted information for residue number system (RNS) integers. In this paper, a weight pre-assignment scheme for CRT is proposed, in which a weight pre-assignment procedure under a few constrains is introduced into CRT to get efficient residue to binary (R/B) conversion architectures.different pre-assigned weight can get different implementation architecture. As a result, CRT is covered by the proposed method. Furthermore, an example combined with mixed radix conversion (MRC) to demonstrate how to use the proposed scheme is also presented. The analysis and comparison results show that the proposed method has good flexibility in getting weighted information for RNS integers.

CRT; MRC; pre-assigned weight; R/B conversion; RNS

TM13

A

10.3969/j.issn.1001-0548.2016.03.001

2014 - 02 - 10；

2015 - 11 - 20

國家自然科學(xué)基金(61571083)；中央高?；緲I(yè)務(wù)費(fèi)(ZYGX2014J009)

馬上(1978 - )，男，博士，副教授，主要從事數(shù)字電路、通信信號(hào)基帶處理等方面的研究.