一种余数系统基扩展算法及VLSI实现

马 上，汪陈浩，胡剑浩



一种余数系统基扩展算法及VLSI实现

马 上，汪陈浩，胡剑浩

(电子科技大学通信抗干扰技术国家级重点实验室 成都 611731)

基扩展是余数系统(RNS)在数字信号处理(DSP)系统中应用的关键问题之一。该文提出了一种新型基扩展算法，实现基为的余数系统到基为的余数系统的动态范围扩展。给出其VLSI实现结构，并基于的特性对该结构进行了优化，使该实现结构仅由普通二进制加法器和模加法器构成。基于单位门模型和ASIC的性能对比分析结果表明，在实现相同动态范围扩展时，该算法具有良好的VLSI实现性能。

基扩展; 数字信号处理; 余数系统; 超大规模集成电路

余数系统(residue number system，RNS)是一种非权重数值表征系统，它将传统的较大位宽的乘加运算分解为多个较小位宽的并行通道进行处理，从而降低了复杂度和计算的关键路径，可获得高速、低功耗的VLSI(very large scale integrated circuits)实现性能。因此，近年来余数系统在乘加密集型的数字信号处理(digital signal processing, DSP)系统中得到了广泛研究[1-3]。然而，在DSP系统的运算过程中，数值的动态范围会随着乘、加等基本运算而增加。这是RNS在DSP系统中应用面临的基本问题之一，如何高效地实现RNS动态范围的扩展对于其在DSP系统中应用有重要意义。

由于余数系统具有非权重的特性，故需要采用特殊的基扩展技术解决该问题。余数系统基扩展方法可以分为两类：第一类保留原余数基，通过增加新的余数基分量来扩大余数系统的动态范围[4-9]；第二类保留原余数系统的通道数量不变，通过增加原余数基的数据位宽来实现动态范围的扩大。

目前关于余数动态范围的扩展主要集中在第一类方法的研究上。文献[4]提出了Szabo-Tanaka算法，该算法利用了混合基转换(mixed radix conversion, MRC)和一个附加修正单元现基扩展，其实质为先做余数系统到二进制系统转换(residue to binary，R2B)，恢复出原数据后再对新余数基求模，算法复杂度较高。文献[5]讨论了两通道余数基向第三个余数基分量扩展的方法，同时，该算法可以推广至基为的余数系统基扩展(其中为正整数)。文献[6]在文献[5]的基础上提出了通用的两通道余数系统向三通道余数系统的扩展方法。文献[7]提出了以中国剩余定理(chinese remainder theorem, CRT)为基础并结合冗余基实现第一类基扩展的通用方法，但计算中仍包含完整的R2B转换。文献[8]提出一种基于改进中国剩余定理来实现第一类基扩展的方法，该算法首先改进了中国剩余定理，并利用查找表(look-up table，LUT)实现基扩展，再基于改进后的CRT同时可以实现缩放操作，该算法不需要冗余基。文献[9]提出了利用文献[8]中基扩展算法实现缩放，并认为比文献[4,7]提出的算法更加有效。

第一类基扩展方法的研究均采用余数系统后向转换算法为理论基础。在其实现中通常需要余数系统到二进制系统转换和二进制到余数系统转换(binary to residue，B2R)过程，算法复杂度太高。第二类余数基扩展方法则保留了原余数基的原有特点，仅增加各通道的位宽，保留了原余数基运算通道的电路结构，且不需要考虑扩展基与原始基的互质条件。另一方面，在DSP应用中如乘法级联为特征的离散付氏变换、离散余弦变换和离散小波变换等，需要方便高效地将余数通道的数据位宽扩大一倍。因此，第二类基扩展具有重要的应用价值，目前对这一方法的研究还较少。

1 背景知识

1.1 余数系统与混合基转换

1.2 基扩展定义

2 余数通道数据位增加的基扩展算法及其VLSI实现结构

(2)

对于式(3)，可进行适当优化，以简化VLSI实现结构。对于，有：

(4)

(6)

图1 通道扩展VLSI实现结构

(8)

(10)

(12)

图2 及通道扩展VLSI实现结构

由此，3个模减法器均转化为模加法器，具体实现电路如图2所示，其电路结构非常简单。

由2.1节和2.2节的分析可知，本文的扩展算法中，需先扩展出通道的值，然后扩展出其他两路的值，其整体实现框图如图3所示。

图3 整体设计VLSI实现结构

3 性能分析与对比

3.1 性能分析

综上所述，本文提出的基扩展需要的面积和关键时延分别为：

(15)

3.2 性能对比

对于Szabo-Tanaka算法，文献[7]及文献[8]均为第一类基扩展，而本文提出的算法为第二类基扩展。限定原始余数基均为，并设其扩展出的余数基分量为，那么可在扩展相同的比特位宽条件下进行性能对比。

表1给出了本文算法、Szabo-Tanaka算法，文献[7]及文献[8]提出的算法在扩展比特位宽的条件下的硬件消耗、时延性能对比(基于单位门模型)。

在集成电路实现中，查找表中每比特存储单元所需CMOS管为6个[15]，而相对应的单位门模型中简单门同样需要6个CMOS管，故可大致认为查找表中每比特存储单元的面积消耗对应于单位门模型的面积为；同时可设查找表的平均查找时延为。据此，可将查找表的硬件、时延性能转换为单位门模型进行分析。

表1 硬件性能及扩展基对比

图4 基于单位门模型的时延对比

图5 基于单位门模型的面积对比

由于Szabo-Tanaka算法为较经典的第一类基扩展算法，其他第一类基扩展算法大多基于该思想进行设计，因此其对第一类基扩展算法具有较好的代表性。为了进一步进行性能分析和对比，基于VHDL语言对本文所提出的基扩展算法和经典的Szabo-Tanaka算法进行设计，其中所需的模加法器的设计采用了端回进位法，模加法器设计采用了消“1”法。然后利用Synopsys公司的Design Compiler对这些设计进行面向ASIC的综合，综合中采用了DC的Class库，工艺为SMIC 130 nm，电压设置为1.08 V，温度为125 ℃。DC实现结果如表2所示。

表2 ASIC综合结果

由表2可见，本文提出的基扩展方法在时延方面占有较大优势，但面积与理论分析较为不同，分析原因是由于Szabo-Tanaka算法中的模加法器形式较为统一，因此综合软件采用了较多的复用，从而使得实际综合面积比理论分析面积小。

4 结 论

[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

国家自然科学青年基金(61101033)；特殊环境机器人技术四川省重点实验室开放基金(13zxtk02)

马上(1978-)，男，博士，副教授，主要从事电路理论、通信信号基带处理等方面的研究.