4模集合余数系统比例变换*

吕晓兰，崔得龙

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

4模集合余数系统比例变换*

吕晓兰，崔得龙

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

数值缩放(scaling)和奇偶检测等的高效 VLSI实现已经成为剩余数系统(RNS)研究的瓶颈问题。该文基于4模集合{2n，22n+1，2n+1，2n-1}，在新中国余数定理的基础上，提出了该模集合优化的 2n比例变换优化算法，并基于VLSI实现其硬件结构。分析结果表明，该 2n比例变换的VLSI实现具有更好的面积和功耗特性。

新中国余数定理;反向转换;数值缩放;VLSI

0 引言

在大规模集成电路发展的今天，随着高精度、便携式电子器件的进一步发展，传统的信号处理技术已经逐步被大规模的并行处理技术所取代。剩余数系统以其特有的进位自由和并行运算特性，近年来已经成为高速、大规模数字信号处理的最好选择。

剩余数系统应用的意义已经被证明，尤其对于处理密集型加法、减法以及乘法等占有绝对的优势。然而，其他的运算例如除法、奇偶检测、比例变化、大小比较和符号检测等运算由于其运算的复杂性，在剩余数系统就失去了并行性的优势，这些运算有时不得不将余数转换成二进制数后再做运算，所以会浪费大量的电路面积和延迟。为了提高此类运算电路的性能，近年来许多研究人员开始对此领域进行研究，但是大部分研究针对比较常用的 3模集合{2n，2n+1，2n-1}[1-4]。

比例变化是余数系统研究最重要问题之一，比例变化尤其在防止溢出和内部乘积处理方面具有举足轻重的作用。和反向转换一样，比例缩放在剩余数系统实现也涉及到大的延迟和较高的硬件复杂度，涉及在每一个剩余数计算阶段。本文针对4模集合{2n，22n+1，2n+1，2n-1}，在分析反向转换和比例缩放算法的基础上，提出了一个新的基于2n的比例缩放算法，并基于加法器实现其VLSI结构。

1 算法描述

基于剩余数系统模集合{m1，m2，…，mn}的整数X，通过一个比例因子k做比例变化，设Y为比例变化的结果，则：

对上式两边做模mi运算，即得到该剩余数系统内部各个模通道的缩放结果 yi。

定理1:根据新中国余数定理1(New CRT-Ⅰ)，余数(x1，x2，x3，x4)RNS表示权重数 X具有 0至 M 区间有唯一解[4]，即：

ki表示乘法逆元。

对于模集合针对 4模集合{m1，m2，m3，m4}其对应于{2n，22n+1，2n+1，2n-1}，根据式(3)：

其中 k1=23n，k2=2n-1，k3=2n-2。Y进一步表示为：

取比例因子K=2n，设，i=1，2，3，4。对于的结果不存在。不能用式(2)直接计算y1，必须采用其他的方法解决。对于K与mi互质，直接计算得到结果。将 m2，m3，m4带入，K=2n。则：

关于 m1通道，由于不存在，不能用式(2)直接计算。将X=x1+2nY直接带入式(1)：

2 电路实现

2.1 y1的硬件实现

定理2:若0≤ν≤2n-2，则ν2i模2n-1的结果相当于将 n位宽二进制数 ν，即 νn-1νn-2…ν0循环左移 i位[5]。

定理 3:若 0≤ν≤2n-2，则(-ν)2i模 2n-1的结果相当于将ν乘以2i模 2n-1的结果按位取反[5]。

由前面的分析可知，对于模通道22n进行2n比例变化结果y1，直接取Y的低n位即可实现。应用定理1和2，通过进一步合并化简，Y最终转换为5个4n位操作数相加的形式，即：

通过3级进位保留加法器(CSA)，最终形成两个4n位宽的S、C，S和 C通过模24n-1加法器得到4n位模加法器的结果Y，如图1所示。

图1 文中提出的比例变换结构图

2.2 y2的硬件实现

对于模通道 m2=22n+1进行 2n比例变化，根据式(6)，为了进一步减少硬件复杂度，采用缩一码模 22n+1加法器，y2进一步表示为：

操作数在进入缩一码模22n+1加法器之前必须分别减1，而缩一码模22n+1加法器在输出以后必须加1才能得到真正的结果。两者合并，只要将进位加法器的输出减1即可。同时，根据定理4，进位保留加法器的最高有效位的进位输出将被直接取反加到下一级进位保留加法器的最低有效位的同时，需要加上一个补偿常数因子 2n。联合前面缩一码模 22n+1加法器的校正因子-1，总的校正项Cj为：

最终y2表示为：

直接将上面的三项输入法进位反转的回转进位保留加法器，得到进位2n位C和2n位和位S，将C和S直接输入到缩一码模2n+1加法器，该缩一码模2n+1加法器的输出即为实际的比例变换结果。

2.3 y3的硬件实现y3的实现和y2相似，同样通过进位保留加法器树和一个缩一码模 22n+1加法器实现。通过化简式(7)：

设校正项为 Cj，同理，总的校正因子Cj为：

上面得到的校正项与式(13)的第3项合并：

最终，y3表示为：

2.4 y4的硬件实现

对于模通道m4=2n-1进行 2n比例变化结果 y4，根据式(8)，应用定理2，进一步表示为：

该模通道比例变化y4的实现只需要将上面的两个n位操作数直接通过一个0唯一表示的模2n-1加法器，即可实现。

整个基于 4模集合{2n，22n+1，2n+1，2n-1}的反向转换以及比例转化的硬件结构图如图1所示。

3 性能评估和比较

为了进行定性评估，本文与同样对4模集合2n比例变换文献[4]的理论模型进行对比。采用文献[4]提出的门单位计算方法，用近似门单位模型方法计算其硬件以及信号处理延时，即 2输入异或门(XOR)或者同或门(XNOR)的面积和延迟按照2个单位计算，一个全加器(FA)等同于7个单位的面积和4个单位的延迟，非门(NOT)的面积和延迟都以 0计算，其他基本的二输入逻辑门面积和延迟按照1个单元计算。为了更加公平的对比，本研究和文献[4]所有的模 2n-1加法器均采用目前最优化的 0唯一表示的并行前缀模 2n-1加法器[6]，缩一码模2n+1加法器采用文献[7]提出的模加法器模型。提出的新的比例变换模型各个通道面积理论数据如表1所示，和其他模集合比例转换器面积和延时对比如表2所示。从中可以看出，本文所提出的4比例变换器模型，在动态范围大的情况下，在硬件复杂度方面占有绝对的优势。

表1 4个比例转换通道面积理论数据

表2 面积和延时的理论数据比较

4 结论

余数系统的比例变换是避免在剩余数系统的中间运算过程中发生溢出错误的主要方法。基于此，针对4模集合{2n，22n+1，2n+1，2n-1}，在分析反向转换和比例缩放算法的基础上，提出了一个新的反向转换和基于2n的比例缩放算法，并基于加法器实现其VLSI结构，使该模集合能够得到更加广泛的应用。理论分析结果表明，在具有相同模通道数的同类比例变换器中，本研究的算法更加优化，硬件性能表现更加优异。

[1]ANTONIO G，ANTONIO L.A look-up scheme for scaling in the RNS[J].IEEE Transactions on Computers，1999，48 (7)：748-751.

[2]TAY T，CHANG C H，LOW J.Efficient VLSI implementation of 2nscaling of signed integer in RNS{2n-1，2n，2n+1，}[J]. IEEE Transactions on Very Large Scale Integration(VLSI) Systems，2013，21(10)：1936-1940.

[3]YE Y，MA S，HU J.An efficient 2n RNS scaler for moduli set{2n-1，2n，2n+1，}[C].IEEE Symp.Inf.Sci.Eng.(ISISE)，Shanghai，China，2008.12：511-515.

[4]SOUSA L.2n RNS Scalers for Extended 4-Moduli Sets[J]. IEEE Transactions on Computers，2015，62(12)：1-14.

[5]CAO B，CHANG C H，SRIKANTHAN T.A residue-tobinary converter for a new five-moduli set[J].IEEE Transactions on Circuits and Systems-I，2007，54(5)：1041-1049.

[6]PATEL R A，BENAISSA M，BOUSSAKTA S.Fast parallelprefix architectures for modulo 2n-1 Addition with a single representation of zero[J].IEEE Transactions on Computers，2007，56(11)：1484-1492.

[7]VERGOS H，EFSTATHIOU C，NIKOLOS D.Diminished-one modulo 2n+1 adder design[J].IEEE Transactions on Computers，2002，51(12)：1389-1399.

[8]Wang Yuke.Residue-to-binary converters based on new Chinese remainder theorems[J].IEEE Transactions.on Circuits and Systems-II，2000，47(3)：197-205.

RNS scaler for the 4-moduli set RNS

Lv Xiaolan，Cui Delong
(College of Computer and Electronic Information，Guangdong University of Petrochemical Technology，Maoming 525000，China)

Scaling and parity check in RNS has always been conceived as a performance bottleneck similar to the residue system. In this paper，a simple and fast 2nscaling scheme for the four-moduli set{2n，22n+1，2n+1，2n-1}RNS is proposed baesd on the new Chinese remainder theorem.The analysis result shows that the proposed scaler has higher area and power consumption performances compared with the cascaded scaling scheme.

new Chinese remainder theorem(CRT);reverse converter;scaling;VLSI

TN47

A

10.16157/j.issn.0258-7998.2015.08.013

吕晓兰，崔得龙.4模集合余数系统比例变换[J].电子技术应用，2015，41(8)：47-49.

英文引用格式:Lv Xiaolan，Cui Delong.RNS scaler for the 4-moduli set RNS[J].Application of Electronic Technique，2015，41 (8)：47-49.

2015-05-04)

吕晓兰(1979-)，女，实验师，主要研究方向：VLSI数字信号处理芯片的设计研究。

国家自然科学基金面上项目(61473331)