馬 上，汪陳浩，胡劍浩

?

一種余數(shù)系統(tǒng)基擴(kuò)展算法及VLSI實(shí)現(xiàn)

馬 上，汪陳浩，胡劍浩

(電子科技大學(xué)通信抗干擾技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室 成都 611731)

基擴(kuò)展是余數(shù)系統(tǒng)(RNS)在數(shù)字信號處理(DSP)系統(tǒng)中應(yīng)用的關(guān)鍵問題之一。該文提出了一種新型基擴(kuò)展算法，實(shí)現(xiàn)基為的余數(shù)系統(tǒng)到基為的余數(shù)系統(tǒng)的動(dòng)態(tài)范圍擴(kuò)展。給出其VLSI實(shí)現(xiàn)結(jié)構(gòu)，并基于的特性對該結(jié)構(gòu)進(jìn)行了優(yōu)化，使該實(shí)現(xiàn)結(jié)構(gòu)僅由普通二進(jìn)制加法器和模加法器構(gòu)成?；趩挝婚T模型和ASIC的性能對比分析結(jié)果表明，在實(shí)現(xiàn)相同動(dòng)態(tài)范圍擴(kuò)展時(shí)，該算法具有良好的VLSI實(shí)現(xiàn)性能。

基擴(kuò)展; 數(shù)字信號處理; 余數(shù)系統(tǒng); 超大規(guī)模集成電路

余數(shù)系統(tǒng)(residue number system，RNS)是一種非權(quán)重?cái)?shù)值表征系統(tǒng)，它將傳統(tǒng)的較大位寬的乘加運(yùn)算分解為多個(gè)較小位寬的并行通道進(jìn)行處理，從而降低了復(fù)雜度和計(jì)算的關(guān)鍵路徑，可獲得高速、低功耗的VLSI(very large scale integrated circuits)實(shí)現(xiàn)性能。因此，近年來余數(shù)系統(tǒng)在乘加密集型的數(shù)字信號處理(digital signal processing, DSP)系統(tǒng)中得到了廣泛研究[1-3]。然而，在DSP系統(tǒng)的運(yùn)算過程中，數(shù)值的動(dòng)態(tài)范圍會隨著乘、加等基本運(yùn)算而增加。這是RNS在DSP系統(tǒng)中應(yīng)用面臨的基本問題之一，如何高效地實(shí)現(xiàn)RNS動(dòng)態(tài)范圍的擴(kuò)展對于其在DSP系統(tǒng)中應(yīng)用有重要意義。

由于余數(shù)系統(tǒng)具有非權(quán)重的特性，故需要采用特殊的基擴(kuò)展技術(shù)解決該問題。余數(shù)系統(tǒng)基擴(kuò)展方法可以分為兩類：第一類保留原余數(shù)基，通過增加新的余數(shù)基分量來擴(kuò)大余數(shù)系統(tǒng)的動(dòng)態(tài)范圍[4-9]；第二類保留原余數(shù)系統(tǒng)的通道數(shù)量不變，通過增加原余數(shù)基的數(shù)據(jù)位寬來實(shí)現(xiàn)動(dòng)態(tài)范圍的擴(kuò)大。

目前關(guān)于余數(shù)動(dòng)態(tài)范圍的擴(kuò)展主要集中在第一類方法的研究上。文獻(xiàn)[4]提出了Szabo-Tanaka算法，該算法利用了混合基轉(zhuǎn)換(mixed radix conversion, MRC)和一個(gè)附加修正單元現(xiàn)基擴(kuò)展，其實(shí)質(zhì)為先做余數(shù)系統(tǒng)到二進(jìn)制系統(tǒng)轉(zhuǎn)換(residue to binary，R2B)，恢復(fù)出原數(shù)據(jù)后再對新余數(shù)基求模，算法復(fù)雜度較高。文獻(xiàn)[5]討論了兩通道余數(shù)基向第三個(gè)余數(shù)基分量擴(kuò)展的方法，同時(shí)，該算法可以推廣至基為的余數(shù)系統(tǒng)基擴(kuò)展(其中為正整數(shù))。文獻(xiàn)[6]在文獻(xiàn)[5]的基礎(chǔ)上提出了通用的兩通道余數(shù)系統(tǒng)向三通道余數(shù)系統(tǒng)的擴(kuò)展方法。文獻(xiàn)[7]提出了以中國剩余定理(chinese remainder theorem, CRT)為基礎(chǔ)并結(jié)合冗余基實(shí)現(xiàn)第一類基擴(kuò)展的通用方法，但計(jì)算中仍包含完整的R2B轉(zhuǎn)換。文獻(xiàn)[8]提出一種基于改進(jìn)中國剩余定理來實(shí)現(xiàn)第一類基擴(kuò)展的方法，該算法首先改進(jìn)了中國剩余定理，并利用查找表(look-up table，LUT)實(shí)現(xiàn)基擴(kuò)展，再基于改進(jìn)后的CRT同時(shí)可以實(shí)現(xiàn)縮放操作，該算法不需要冗余基。文獻(xiàn)[9]提出了利用文獻(xiàn)[8]中基擴(kuò)展算法實(shí)現(xiàn)縮放，并認(rèn)為比文獻(xiàn)[4,7]提出的算法更加有效。

第一類基擴(kuò)展方法的研究均采用余數(shù)系統(tǒng)后向轉(zhuǎn)換算法為理論基礎(chǔ)。在其實(shí)現(xiàn)中通常需要余數(shù)系統(tǒng)到二進(jìn)制系統(tǒng)轉(zhuǎn)換和二進(jìn)制到余數(shù)系統(tǒng)轉(zhuǎn)換(binary to residue，B2R)過程，算法復(fù)雜度太高。第二類余數(shù)基擴(kuò)展方法則保留了原余數(shù)基的原有特點(diǎn)，僅增加各通道的位寬，保留了原余數(shù)基運(yùn)算通道的電路結(jié)構(gòu)，且不需要考慮擴(kuò)展基與原始基的互質(zhì)條件。另一方面，在DSP應(yīng)用中如乘法級聯(lián)為特征的離散付氏變換、離散余弦變換和離散小波變換等，需要方便高效地將余數(shù)通道的數(shù)據(jù)位寬擴(kuò)大一倍。因此，第二類基擴(kuò)展具有重要的應(yīng)用價(jià)值，目前對這一方法的研究還較少。

1 背景知識

1.1 余數(shù)系統(tǒng)與混合基轉(zhuǎn)換

1.2 基擴(kuò)展定義

2 余數(shù)通道數(shù)據(jù)位增加的基擴(kuò)展算法及其VLSI實(shí)現(xiàn)結(jié)構(gòu)

(2)

對于式(3)，可進(jìn)行適當(dāng)優(yōu)化，以簡化VLSI實(shí)現(xiàn)結(jié)構(gòu)。對于，有：

(4)

(6)

圖1 通道擴(kuò)展VLSI實(shí)現(xiàn)結(jié)構(gòu)

(8)

(10)

(12)

圖2 及通道擴(kuò)展VLSI實(shí)現(xiàn)結(jié)構(gòu)

由此，3個(gè)模減法器均轉(zhuǎn)化為模加法器，具體實(shí)現(xiàn)電路如圖2所示，其電路結(jié)構(gòu)非常簡單。

由2.1節(jié)和2.2節(jié)的分析可知，本文的擴(kuò)展算法中，需先擴(kuò)展出通道的值，然后擴(kuò)展出其他兩路的值，其整體實(shí)現(xiàn)框圖如圖3所示。

圖3 整體設(shè)計(jì)VLSI實(shí)現(xiàn)結(jié)構(gòu)

3 性能分析與對比

3.1 性能分析

綜上所述，本文提出的基擴(kuò)展需要的面積和關(guān)鍵時(shí)延分別為：

(15)

3.2 性能對比

對于Szabo-Tanaka算法，文獻(xiàn)[7]及文獻(xiàn)[8]均為第一類基擴(kuò)展，而本文提出的算法為第二類基擴(kuò)展。限定原始余數(shù)基均為，并設(shè)其擴(kuò)展出的余數(shù)基分量為，那么可在擴(kuò)展相同的比特位寬條件下進(jìn)行性能對比。

表1給出了本文算法、Szabo-Tanaka算法，文獻(xiàn)[7]及文獻(xiàn)[8]提出的算法在擴(kuò)展比特位寬的條件下的硬件消耗、時(shí)延性能對比(基于單位門模型)。

在集成電路實(shí)現(xiàn)中，查找表中每比特存儲單元所需CMOS管為6個(gè)[15]，而相對應(yīng)的單位門模型中簡單門同樣需要6個(gè)CMOS管，故可大致認(rèn)為查找表中每比特存儲單元的面積消耗對應(yīng)于單位門模型的面積為；同時(shí)可設(shè)查找表的平均查找時(shí)延為。據(jù)此，可將查找表的硬件、時(shí)延性能轉(zhuǎn)換為單位門模型進(jìn)行分析。

表1 硬件性能及擴(kuò)展基對比

圖4 基于單位門模型的時(shí)延對比

圖5 基于單位門模型的面積對比

由于Szabo-Tanaka算法為較經(jīng)典的第一類基擴(kuò)展算法，其他第一類基擴(kuò)展算法大多基于該思想進(jìn)行設(shè)計(jì)，因此其對第一類基擴(kuò)展算法具有較好的代表性。為了進(jìn)一步進(jìn)行性能分析和對比，基于VHDL語言對本文所提出的基擴(kuò)展算法和經(jīng)典的Szabo-Tanaka算法進(jìn)行設(shè)計(jì)，其中所需的模加法器的設(shè)計(jì)采用了端回進(jìn)位法，模加法器設(shè)計(jì)采用了消“1”法。然后利用Synopsys公司的Design Compiler對這些設(shè)計(jì)進(jìn)行面向ASIC的綜合，綜合中采用了DC的Class庫，工藝為SMIC 130 nm，電壓設(shè)置為1.08 V，溫度為125 ℃。DC實(shí)現(xiàn)結(jié)果如表2所示。

表2 ASIC綜合結(jié)果

由表2可見，本文提出的基擴(kuò)展方法在時(shí)延方面占有較大優(yōu)勢，但面積與理論分析較為不同，分析原因是由于Szabo-Tanaka算法中的模加法器形式較為統(tǒng)一，因此綜合軟件采用了較多的復(fù)用，從而使得實(shí)際綜合面積比理論分析面積小。

4 結(jié) 論

[1] CONWAY R, NELSON J. Improved RNS FIR filter architectures[J]. IEEE Transactions on Circuit and Systems II, 2004, 51(1): 26-28.

[2] MADHUKUMAR A S, CHIN F. Enhanced architecture for residue number system-based CDMA for high-rate data transmission[J]. IEEE Transactions on Wireless Communications, 2004, 3(5): 1363-1368.

[3] MA Shang, HU Jian-hao, LING Xiang, et al. The applications of RNS in SDR systems[C]//2008 International Workshop on Software Radio Technology (SRT2008). Beijing: [s.n.], 2008: 49-54.

[4] SZABO N S, TANAKA R I. Residue arithmetic and its applications to computer technology[M]. New York: McGraw-Hill, 1967.

[5] O’KEEFE K H, WRIGHT J L. Remarks on base extension for modular arithmetic[J]. IEEE Trans Comput, 1973, 22: 833-835.

[6] O’KEEFE K H. A note on fast base extension for residue number systems with three moduli[J]. IEEE Trans Comput, 1975, 24: 1132-1133.

[7] SHENOY A P, KUMARESAN R. Fast base extension using a redundant modulus in RNS[J]. IEEE Trans Comput, 1989, 38: 292-296.

[8] BARSI F, PINOTTI M C. Fast base extension and precise scaling in RNS for look-up table implementations[J]. IEEE Trans Signal Processing, 1995, 43: 2427-2430

[9] LAI Yu-feng, KONG Yi-nan. An implementation of a scaler in the residue number system[C]//International Symposium on Communications and Information Technologies. [S.l.]: [s.n.], 2012: 529-532

[10] WANG Yu-ke. New Chinese remainder theorems[C]// Conference Record of the Thirty-Second Asilomar Conference on Signals, Systems & Computers. Pacific Grove: [s.n.], 1998, 1: 165-171.

[11] MA Shang, HU Jian-hao, ZHANG Lin, 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.

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

[13] PATEL R A, BOUSSAKTA S. Fast parallel-prefix architectures for moduloaddition with a single representation of zero[J]. IEEE Trans on Computers, 2007, 56(11): 1484-1492.

[14] EFSTATHIOU C, VERGOS H T, NIKOLOS D. Fast parallel-prefix moduloadders[J]. IEEE Trans on Computers, 2004, 53(9): 1211-1216.

[15] WESTE H E, HARRIS D M. CMOS VLSI Design[M]. 2nd ed. [S.l.]: Addison Wesley, 2005.

編 輯 稅 紅

A New Base Extension Algorithm and VLSI Implement for Residue Number System

MA Shang, WANG Chen-hao, and HU Jian-hao

(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China Chengdu 611731)

The base extension operation for residue number systems (RNS) plays an important role in RNS-based digital signal processing (DSP) systems. In this paper, a new base extension algorithm is proposed which can extend the dynamic range from moduli setto moduli set. In this paper, the very large scale integrated (VLSI) circuits implement of the proposed algorithm is also presented, with the properties of moduli set, the implement is composed of binary adders and modular adders; The analysis result based on unit-gate model and ASIC (application specific integrated circuit) implementation shows that the VLSI implementation of the proposed base extension algorithm exhibits better performances for the same dynamic range extension.

base extension; digital signal processing; residue number system; VLSI circuits

TP33

A

10.3969/j.issn.1001-0548.2015.02.008

2013-09-04；

2015-01-21

國家自然科學(xué)青年基金(61101033)；特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室開放基金(13zxtk02)

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