剩余数系统{2n+1,2n+1+1,2n}符号检测设计与优化*

吕晓兰,肖　明

(广东石油化工学院计算机与电子信息学院,广东 茂名 525000)



剩余数系统{2n+1,2n+1+1,2n}符号检测设计与优化*

吕晓兰*,肖明

(广东石油化工学院计算机与电子信息学院,广东 茂名 525000)

摘要:提出一个新的针对剩余数模集合{2n+1,2n+1+1,2n},快速的符号检测算法。该符号检测系统仅由3个单元组成,一个n位宽度的仅为保留加法器单元,一个n位比较器单元和一个n位前缀加法器单元,其中进位保留加法器和比较器单元是并行的。实验结果表明,相比于其他剩余数符号检测系统,平均速度提高了约36%,面积相对保留约63%。

关键词:剩余数系统;符号检测;VLSI;加法器

剩余数系统(RNS)以其特有无权重特性在当前超大规模数字信号处理领域得前所未有的关注[1]。而符号检测在剩余数系统的大小比较,溢出检测等领域起着不可缺少的作用。剩余数系统的符号检测相比权重数系统要复杂得多,剩余数系统符号检测近年来已成为剩余数系统研究的热点问题。

同其他剩余数系统研究一样,基于剩余数系统的符号检测电路也同样经历了从查找表到纯组合逻辑电路的实现过程[2-6]。Zenon D Ulman在1983年基于混合基算法首次提出了一种符号检测电路的算法,并基于查找表实现[2]。2003年,Al-Radadi E和Siy P基于新中国余数定理2提出一个新的符号检测算法,但是该方法基于多层转化完成,硬件复杂[5]。直到2008年,Tomczak T首次基于通用模集合{2n-1,2n,2n+1}提出了一个纯逻辑电路构成的符号检测电路,不依赖于查找表,但其不适合于其他的模集合符号检测实现[6],本文基于模集合{2n+1,2n+1+1,2n},在混合基-中国余数定理定理(MR-CRT)算法的基础上,实现该模集合下剩余数符号检测,硬件完全基于门级电路实现。

1　算法描述

根据RNS整数定义,余数系统中可唯一表示[0,M)之间定义任意正整数X,M为该剩余数系统的动态范围。根据数值所处的区间划分有符号RNS整数,当X的在区间[0,M/2)内时,表示正数,符号位为0;当X在区间[M/2,M)内时,则表示负数,符号位为1。符号检测函数Sgn(X):

(1)

根据混合基-中国余数定理[7],权重数X表示为:

(2)

其中:mi为两两互质的模,

对于给定模集合{2n+1,2n+1+1,2n},m1=2n+1,m2=2n+1+1,m3=2n,动态范围M=2n(2n+1)(2n+1+1),M/2=2n-1(2n+1)(2n+1+1),根据余数系统符号函数定义:

(3)

则根据式(2),模集合{2n+1,2n+1+1,2n}表示的权重数X为:

X=α2m1m2+α1m1+α0

(4)

其中:α0=x1,α1=|γ1x1+γ2x2|m2;

α2=┕γ1x1+γ2x2+γ3x3/m2」|m3

(5)

当X

(6)X

Sgn(x1,x2,x3)=MAX(α2)=

MAX(|┕γ1x1+γ2x2+γ3x3/m2」|m3)

(7)

2　硬件实现

根据式(7):

(8)

(9)

由于0≤x2≤2n+1,0≤x1≤2n,根据分析得到:

(10)

令:

(11)

(12)

最终的符号检测函数:

Sgn(x1,x2,x3)=MAX(α2)=

(13)符号“&”表示并置连接。整个符号检测系统的硬件实现由3个模块组成,一个3输入n位进位保留加法器(CSA)[8],一个n位比较器(w和f实现单元),一个n位前缀加法计算单元(符号位生成单元),进位保留加法器和比较器并行,系统实现结构如图1所示。

图1　符号检测架构图

图2　基本单元的逻辑实现

图3　n位比较器结构图

图4　w和f逻辑实现

图5　符号位生成模块逻辑实现

举例:设n=8,则(m1,m2,m3)分别为(257,513,256)。M=33751296,M/2=16875648。

例1:设X=6875776,其剩余数表示为(255,37,128),二进制表示为x1=(011111111)2,x2=(0000100101)2,x3=(10000000)2。根据式(11),w=0,f=0,则根据式(12),α2=(00110100)2,Sgn(x1,x2,x3)=MAX(α2)=0。

例2:设X=26875776,其剩余数表示为(1,0,128),即x1=(000000001)2,x2=(0000000000)2,x3=(10000000)2。根据式(11),w=0,f=0,根据式(12),α2=(10000000)2,Sgn(x1,x2,x3)=MAX(α2)=1。

3　性能评估和比较

为了对本文提出的模集合{2n+1,2n+1+1,2n}符号检测算法进行定性和定量的评估,本文与文献[5]提出的符号检测算法进行比较。文献[5]将模集合{2n+1,2n+1+1,2n}分成X12={2n+1+1,2n+1}和X={(2n+1+1)(2n+1),2n}2级进行处理,根据文献[5],Sgn(X)=maxL(X)=max(|x3-x2-Y|2n),其中Y=|2x2-2x1|2n+1+1,该硬件实现模块包括一个模2n+1+1加法器,一个3输入CSA和一个n位前缀加法计算单元。均采用Tyagi[9]提出的门单元计算方法作为面积和延时的计算标准。2输逻辑门(AND,OR,NOT)作为面积和延时上的1个单位计算,2输入异或门/同或门作为2个单位的面积和延时计算。表1示出了本文和文献[5]提出的算法针对模集合{2n+1,2n+1+1,2n}的符号检测在硬件面积和延迟的理论数据对比。从中可以看出,在n相同的情况下,无论在延时和硬件消耗方面,本文提出的算法明显优于文献[5]给出的算法模型。

表1　模2n+1加法器电路的面积和延迟对比

将本文和文献[5]提出的2种模型利用Verilog语言建模,ModeSim中仿真验证,并在保持约束条件相同条件下,分别设n=4,8,16,32,利用SIMC的标准单元库(0.18μm,1.98V,0 ℃)和SynopsysDesignComplier采用面积迭代优化和延时迭代优化进行综合,不同n值下面积优化与延时优化结果如表2所示。

表2　面积和延时优化的实验结果

从表2看出,文中提出的符号检测系统面积消耗平均比文献[5]的保留63%,运算速度比文献[5]平均要快36%。

4　结束语

针对模集合{2n+1,2n+1+1,2n},基于混合基-中国余数定理,提出了该模集合下剩余数的符号检测算法,并且基于组合电路实现了该模集合下剩余数系统符号检测电路设计。理论对比和实验结果表明,相比于近年提出的剩余数符号检测算法,文中提出的符号检测系统,在硬件消耗和速度方面都占有一定的优势。

参考文献:

[1]Miroslav D L,Dejan V T,Brian L E.信号处理滤波器设计——基于MATLAB和Mathematica的设计方法[M].朱义胜,董辉,等译.北京:电子工业出版社,2004:250-256.

[2]Ulman Z D.Sign Detection and Implicit-Explicit Conversion of Numbers in Residue Arithmetic[J]IEEE Trans.Comput.,1983,C-32(6):590-594.

[3]Vu T V.Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding[J].IEEE Trans Comput,1985,C-34(7):646-651.

[4]Kaushik S.Sign Detection in Residue Code[J].Comput and Elect Engineering,1986,12(1):65-71.

[5]Al-Radadi E,Siy P.RNS Sign Detector Based on Chinese Remainder Theorem Ⅱ(CRT Ⅱ)[J].Comput Math Appl,2003,46(10-11):1559-1570.

[6]Tomczak T.Fast Sign Detection for RNS(2n-1,2n,2n+1)[J].IEEE Trans Circuits Syst I,2008,55(6):1502-1511.

[7]Bi S Q,Gross W J.The Mixed-Radix Chinese Remainder Theorem and Its Applications to Residue Comparison[J].IEEE Trans Comput,2008,57(12):1624-1632.

[8]Piestrak S J.Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders[J].IEEE Trans Comput,1994,43(1):68-77.

[9]Tyagi A A.Reduced-Area Scheme for Carry-Select Adders[J].IEEE Trans Comp,1993,42(10):1163-1170.

吕晓兰(1979-),女,汉族,陕西岐山人,广东石油化工学院,实验师,主要从事VLSI数字信号处理芯片的设计研究,jingling220@126.com。

DesignandOptimizationofSignDetectioninResidueNumberSystem{2n+1,2n+1+1,2n}*

LÜXiaolan*,XIAOMing

(College of Computer and Electronic Information,Guangdong University of Petrochemical Technology,Maoming Guangdong 525000,China)

Abstract:We propose a fast algorithm for sign-extraction of a number given in the Residue Number System{2n+1,2n+1+1,2n}.The algorithm can be implemented using three units,one n-bit wide carry save adder,one n-bit wide comparator,and one prefix adder unit,two of which can be done in parallel.The experimental results indicate that the proposed circuit offers 63%,and 36% savings on average in terms of area,and delay,respectively,better than the unit based on previous sign detection algorithm.

Key words:RNS(residue number system);sign detection;VLSI;adder

doi:EEACC:257010.3969/j.issn.1005-9490.2014.04.007

中图分类号:TN47

文献标识码:A

文章编号:1005-9490(2014)04-0613-04

收稿日期:2014-03-12修改日期:2014-04-28

项目来源:广东省自然科学基金重点项目(S2011020002735)