基于新中国余数定理的高效并行转换算法

基于新中国余数定理的高效并行转换算法

随着数字信号的快速发展，传统的加权数据系统，如二进制数据系统，10输入数据系统由于进位链的存在，使信号单元的执行速度变慢。余数系统是将一个常规进制(如二进制)的数转换成一组两两互质的模集合下剩余数来表示。由于每个模数之间的运算都是独立的,这样就可以将一个位宽很长的数之间的运算转换到一组短位宽数的并行运算,大大降低了电路中由于进位传播造成的延迟。余数系统所特有的并行性和无权重特性,在超高速数字信号处理领域得到广泛的关注,如数字滤波、快速傅里叶变换、图像处理等。通常的数字电路是基于二进制数的,剩余数系统构建一个高速系统,必须进行剩余数与二进制数之间的转换。而剩余数至二进制数的转换要比二进制数至剩余数转化复杂的多,因此,高效的剩余数至二进制数的转换器是当前的一个研究热点。传统的剩余数至二进制数转换器设计主要基于中国余数定理(CRT)和混合基(MRC)这两种算法进行的。CRT具有一个大值的模运算,转换效率比较低。MRC算法是一个串行处理过程,延时比较大的。因此,结合各自的优缺点,在CRT和MRC算法的基础上,Wang在2000年提出了改进的新中国余数定理,即就是新中国余数定理1(NEWCRTⅠ)和新中国余数定理2(NEWCRTⅡ)。新中国余数定理继承了中国余数定理和混合基算法的优点,减少了硬件的复杂度,提高了运算了的速度。到目前为止,关于余数系统的很多模组已经被推荐,最著名的模组是三模组{2n-1,2n,2n+1}。为了进一步提高数字信号处理的速度和动态范围,则需要增加更多的模通道。因此在该三基数模集合的基础上扩展模集合的个数,并且增加动态范围。动态范围为3n和4n的模集合已经提出很多,仍不能满足实际对大范围数据处理的要求,于是又相继提出了动态范围为5n的模组。Zhang于2008提出的最早的6n+1动态范围的模组{2n-1,2n+1,22n-2,22n+1-3},2n-2和2n-3这两个模形式不具有2n和2n±1形式,增加了硬件,提高了反向转换的延时和开销。本研究是在4基数模集合{2n-1,2n+1,22n,22n+1-1}的基础上,研究剩余数至二进制数反向转换算法,并且实现硬件设计。该模集合动态范围达到6n+1,集合内的所有模均具有2n和2n±1的特殊形式,利用这些特殊的模形式来简化转换器的设计,使其可以完全用最简单,最基本的组合逻辑电路实现。根据新中国余数定理Ⅱ,提出新的反向转换算法,并给出了相应的硬件实现电路。乘法逆元均为1或者2的幂的形式,硬件实现仅通过简单的位移就能够得到,大大降低了硬件的复杂度,提高了转换效率。1模间的互质问题对于一个4模组(p1,p2,p3,p4),利用新中国余数定理2(NEWCRTⅡ)反向转换算法,从它的余数表示(x1,x2,x3,x4)能得到权重数X。计算过程如下:k1,k2,k3表示乘法逆元。当n为任意整数时,该4基数模集合(2n-1,2n+1,22n,22n+1-1)模之间必须两两互质。证明:由于已知当n为任意整数时,2n-1和2n+1之间是互质的,根据欧几里得定理:同理:GCD(22n,2n+1)=GCD(2n+1,1),GCD(22n,2n-1)=GCD(2n-1,1)=1证得2n+1,2n-1,22n,22n+1-1之间两两互质的。引理1在运算中,余数v的负数-v可以用v的反码形式表示,其中0≤v<2n-1。即:引理2在模2n-1运算中,当余数v与权重为2的数2r做模乘运算时,只需对v做r位的左旋移位操作。即:在此设P1=2n-1,P2=2n+1,P3=22n,P4=22n+1-1对应剩余数为(x1,x2,x3,x4)RNS,该对应剩余数的二进制表示为:2计算h5x计算将H,K,T代入式(13)最终得:2加法器的设计对于4模组(p1,p2,p3,p4)所对应余数组(x1,x2,x3,x4)向权重数X转换的硬件实现结构图如图1所示。基本单元的实现基于式(13),(15),(19),(24),(29)完成。操作数准备单元1准备式(16),(17),(20),(21)要求的操作数,式(21)的实现需要一个n位的2选1选择器,其余只是简单的对剩余数的取反,移位操作。H通过一个模22n加法器完成,该模22n加法即就是一个普通的2n位的二进制加法器。T通过一个模2n-1加法器完成,即式(15)的实现。操作数准备单元2准备式(25),(26),(27),(28)要求的操作数,该单元的所有操作数也是通过简单的移位得到,不占用任何硬件资源。5操作数模22n-1加法器单元,即式(24)的实现如图2所示。为了对比公平,本研究以及对比文献中所有的多操作数模2n-1加法器均采用多级带有反向回转进位(EAC)的进位保留加法器(CSA)和模2n-1加法器实现,模2n-1加法器采用具有0的唯一表示的快速并行前缀模2n-1加法器。在此设计中,由于v5包含n-1位的‘0’,回旋进位保留加法器1的高n-1个全加器可以由n-1个XOR/AND对代替。由于v71包含2n-1位的‘1’,所以回旋进位保留加法器2的高2n-1个全加器可以由2n-1对XNOR/OR门代替。至此,操作数准备单元3完成式(29)需要的操作数F和S,最终X的实现通过一个6n+1位的补码加法器完成。3面积和延迟的理论分析为进行定性的比较,采用文献推荐的理论模型作为对比的标准。1位全加器(FA)作为面积和延时的基本计算单位。在该模型中,n个1位全加器级联而成n位加法器,其面积按照n×AFA计算,延时按照n×tFA计算;n位进位保留加法器面积按照n×AFA计算,延时按照tFA计算;则采用的模2n-1加法器的面积为n×AFA,延时为2n×AFA。电路中有部分全加器采用异或/与门对或者同或/或门对代替,则电路的面积和延时需同样替换为这两种门对的面积和延时。表1示出了本研究和文献在面积和延迟的理论对比。从中可以看出,无论是在硬件消耗还是延时,在论文上都是优于文献给出的转换器模型。为了进行更准确地定量比较,对文中提出的转换器和文献推荐的转换器在相同n值下分别利用Verilog语言进行建模,并在ModeSim中进行全面的仿真,验证其正确性。利用中芯国际(SIMC)的标准单元库(0.18um,1.98V,0℃)和SynopsysDesignComplier对两种转换器进行综合。在综合过程中,保持所有的约束条件相同,利用面积迭代优化和延时迭代优化得到的两种转换器的最优面积和最优延时。表2给出两种转换器在不同n值时面积优化与延时优化的结果。从表2看出,在面积表现上,本研究的转换器平均比文献要节省39.4%;在电路的延时表现上,本文的转换器平均比文献的要快47.4%。4基于剩余数的转换文中给出4模集合(2n-1,2n+1,22n,22n+1-1)的剩余数至二进制数转换算法。利用新中国余