一種中國剩余定理權重預分配方法

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

?

一種中國剩余定理權重預分配方法

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

(1. 電子科技大學通信抗干擾技術國家級重點實驗室 成都 611731; 2. 成都信息工程大學電子工程學院 成都 610225)

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

; 混合基轉換; 權重預分配; 后向轉換; 余數系統

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

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

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

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

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

1 余數系統理論背景

RNS到權重系統的轉換被稱為混合基轉換，任何一個RNS都可同一個混合基系統(mixed radix system，MRS)相關聯，它是一個權重系統，其權重

2 轉換算法

2.1 基于預分配權重的中國剩余定理擴展算法

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

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

若式(7)運算成立，則運算結果保持不變。

顯然，

據此，可得到：

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

2.2 權重分配的約束條件

1) 可逆性約束

2) 存在性約束

2.3 數值計算舉例

3 基于CRT擴展算法的應用實例

下面給出一種基于本文CRT擴展算法的簡單應用實例，在該示例中將利用擴展算法實現RNS到MRS的并行轉換，并且消除CRT中的模運算。

3.1 權重預分配過程

其對應的余數矩陣為：

對應的混合基矩陣為：

對應的余數矩陣為：

3.2 轉換過程

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

其逆矩陣為：

根據式(8)，新的權重下的余數表示為：

由以上討論，該實例對余數基的限定形式為

下取值)都滿足該限定條件。本文所舉應用實例的實現框圖如圖1所示，其中為的符號，負數時為“1”，正數則為“0”。

3.3 數值計算實例

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

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

4 算法分析與比較

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

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

3) 根據特定的余數基形式，采用數值搜索的方法獲得需要指定的權重，簡化的后向轉換結構。

本文所提出的CRT擴展算法極其靈活，針對不同的應用場合可進行相應的權重分配，其目的在于消除CRT中較大的模運算，根據不同的權重分配方式其復雜度差別較大。表1給出了本文算法與MRC、CRT及其變型的定性比較。

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

本文所提算法復雜度與權重選擇具有較大關聯，因此表2給出了對余數系統進行后向轉換的復雜度的分析比較，其中余數基兩兩互質，因此表中不含有CRT-III，本文算法權重選擇如圖1所示，且選擇，由表2中可知本文所提算法具有最小的計算位寬與計算次數。

5 結 束 語

本文提出了一種中國剩余定理的擴展算法，該算法通過預先指定CRT中的權重來獲得靈活高效的余數系統到權重系統的轉換算法，降低VLSI實現復雜度。同時，本文還給出了該算法的權重指定的限定條件，滿足限定條件下的權重指定則可以保證運算結果的正確性。通過本算法，使得中國剩余定理成為本文算法的一個特例，增加了應用的靈活性。反過來，在權重分配過程中，結合限定條件可以對余數基進行一定優化限定，為余數基選擇給出了新的思路。

本文算法的提出為有關余數系統的應用增添了新的研究內容，在未來的研究工作中，可以對權重的預分配方法進一步討論，也可以針對已有余數基進行更優化的后向轉換設計，從而有助于解決余數系統應用中的有關后向轉換、大小比較、符號判斷、基擴展等棘手問題。

[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

國家自然科學基金(61571083)；中央高?；緲I務費(ZYGX2014J009)

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