RNS在进行乘加等基本运算时具有良好的并行特性^[1]，在高速、低功耗数字信号处理(digital signal processing，DSP)应用中得到了关注和研究^{[2, 3, 4]}。权重数字表征系统中，数值符号所在的位置被赋予了一定的数值意义，被称为权重，数值的大小不仅与符号本身有关，还跟符号在数中的位置有关。余数系统是一种非权重数值表征系统，它将动态范围较大的整数通过求模运算映射到多个小动态范围的并行计算通道中，以此来减小乘加运算的位宽。因此，在乘加密集型的数字信号处理系统中，基于余数系统的VLSI实现将带来良好的时延和面积特性。

但由于余数系统是一个非权重系统，通过权重系统到余数系统的转换，原本在权重系统中显而易见的数值特性被隐藏起来了，给余数系统的应用带来了挑战^[5]。通常，在运算中的大小比较^[6]、符号检测^[7]、数值缩放^[8]、奇偶检测^[9]、基扩展^[10]等基本问题都需要一定程度的获取权重信息。因此，余数系统后向转换(residue to binary conversion,R/B)是余数系统应用中的关键之一，得到了广泛而深入的研究。

有关余数系统到权重系统的转换(或后向转换)研究中，可按照通用性分为两类，一类是通用的转换算法，它适用于任何类型的余数基的后向转换，但其结构往往不是最优化的^{[11, 12, 13]}。因此，更多的研究集中在结合余数基的特点进行优化设计，这是主要的研究方法^{[14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]}，但通用性较差。无论何种类型的转换，其理论基础均为CRT或MRC。其中CRT应用最为广泛，它涉及一个较大的模运算，而且其中的乘法操作数也较大，因此基于CRT的研究大多关注如何解决这两个问题^{[11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]}；而混合基转换通常是一个严格的迭代过程，降低了RNS的并行性，在多通道余数基后向转换中，它常被用于完成最后一步转换^[15]。按照实现方法，余数系统到权重系统的转换可分为基于查找表(look-up table，LUT)和组合逻辑两种基本方法，基于查找表的设计方法可以实现通用的R/B转换，但在大动态范围时需要巨大的硬件消耗^[27]；而基于组合逻辑的设计方法主要结合余数基的具体形式进行优化设计，以减小转换的时延和硬件消耗。

在通用的RNS后向转换研究中，文献[11, 12]给出了它的几种变型形式，称为CRT-Ⅰ、CRT-Ⅱ和CRT-Ⅲ。其中，CRT-Ⅰ将MRC的转换并行化，它仍需要类似CRT的模运算和乘法运算位宽。CRT-Ⅱ用于实现多通道余数系统的后向转换，它首先利用CRT进行每两个余数通道的后向转换，然后将转换后的通道合并成一个通道再进行下一级的两通道转换，减小了CRT的模乘法运算位宽，但同时也削弱了CRT的并行性。CRT-Ⅲ针对特殊的非互质的余数系统进行后向转换，它是CRT-Ⅱ的扩展。文献[12]对CRT-Ⅰ和CRT-Ⅱ理论做了进一步的阐述。文献[13]基于CRT引入一个缩放因子来避免大的模运算，采用了脉动结构，其优点在于具有统一的实现结构，但需要采用L*L为余数通道个数)的处理单元阵列及控制逻辑，具有较高的延时和面积复杂度。

本文针对CRT基本理论，通过引入预分配权重的方法来获得高效的RNS后向转换，使得CRT这一经典而古老的定理成为本文算法的一个特例，将该方法称为extension of CRT(ECRT)。该方法在满足一定限定条件下，针对不同的优化目标和余数基类型，改变CRT中固有计算权重，具有极好的灵活性。基于该算法给出了一个应用实例，最后进行了算法的对比分析。

1 余数系统理论背景

余数系统由一组两两互质的余数基$\left\{ {{m_1},{m_2},\cdots ,{m_L}} \right\}$($L > 1$)来定义，在其动态范围$M = \prod\nolimits_{i = 1}^L {{m_i}} $内的整数可以用余数向量$({x_1},{x_2},\cdots ,{x_L})$独一无二地表示，其中x_i为X模${m_i}$的余数，记为${x_i} = {\left\langle X \right\rangle _{{m_i}}}$，$i = 1,2,\cdots ,L$。令动态范围$[0,M)$的整数A，B和C在基为$\left\{ {{m_1},{m_2},\cdots ,{m_L}} \right\}$的余数系统中的表示分别为$({a_1},{a_2},\cdots ,{a_L})$，$({b_1},{b_2},\cdots ,{b_L})$和$({c_1},{c_2},\cdots ,{c_L})$，若${c_i} = {\left\langle {{a_i}\Delta {b_i}} \right\rangle _{{m_i}}}$，则$C = {\left\langle {A\Delta B} \right\rangle _M}$，其中，“$\Delta $”表示加、减或乘法运算。可见，在动态范围$[0,M)$内大整数的加、减或乘法运算被分解为几个较小的并行运算通道。

CRT是余数系统到权重系统转换的重要理论基础之一，基为$\{ {m_1},{m_2},\cdots ,{m_L}\} $的余数系统中的整数$({x_1},{x_2},\cdots ,{x_L})$值为：

$X = {\left\langle {\sum\nolimits_{i = 1}^L {{M_i}{{\left\langle {M_i^{ - 1}} \right\rangle }_{{m_i}}}{x_i}} } \right\rangle _M}$

(1)

式中，${M_i} = M/{m_i}$；${\left\langle {M_i^{ - 1}} \right\rangle _{{m_i}}}$为一个整数，称为${M_i}$对${m_i}$的模倒数，满足${\left\langle {{M_i}{{\left\langle {M_i^{ - 1}} \right\rangle }_{{m_i}}}} \right\rangle _{{m_i}}} = 1$。

RNS到权重系统的转换被称为混合基转换，任何一个RNS都可同一个混合基系统(mixed radix system，MRS)相关联，它是一个权重系统，其权重分别为$\left\{ {{m_{L - 1}}{m_{L - 2}} \cdots {m_1},{m_{L - 2}}{m_{L - 3}} \cdots {m_1},\cdots ,{m_1},1} \right\}$。MRS整数可表示为$({z_L},{z_{L - 1}},\cdots ,{z_1})$$(0 \le {z_i} < {m_i})$，同其对应的RNS具有相同的动态范围。RNS到MRS的转换即为由${x_i}$求解${z_i}$的过程，它是一个迭代过程：

${z_i} = {\left\langle {\left( {X - {z_{i - 1}}} \right)/{m_{i - 1}}} \right\rangle _{{m_i}}}\;\;\;2 \le i \le L,{z_{1 = {x_1}}}$

(2)

2 转换算法 2.1 基于预分配权重的中国剩余定理扩展算法

基于CRT的RNS后向转换如式(1)所示，令${w_i} = {M_i}{\left\langle {M_i^{ - 1}} \right\rangle _{{m_i}}}$，则：

$X = {\left\langle {\sum\nolimits_{i = 1}^L {{w_i}{x_i}} } \right\rangle _M}$

(3)

根据同余定理，对式(3)两边模${m_j}$，则：

${\left\langle X \right\rangle _{{m_j}}} = {\left\langle {{{\left\langle {\sum\nolimits_{i = 1}^L {{w_i}{x_i}} } \right\rangle }_M}} \right\rangle _{{m_j}}} = {\left\langle {\sum\nolimits_{i = 1}^L {{w_i}{x_i}} } \right\rangle _{{m_j}}}$

(4)

由于${M_i} = M/{m_i}$，${\left\langle {{M_i}{{\left\langle {M_i^{ - 1}} \right\rangle }_{{m_i}}}} \right\rangle _{{m_i}}} = 1$，因此对于式(4)，当$i = j$时${\left\langle {{w_i}} \right\rangle _{{m_j}}} = 1$，否则${\left\langle {{w_i}} \right\rangle _{{m_j}}} = 0$。式(4)的计算结果即为整数$X$的余数表示${x_i}$，这一计算过程等价为：

$\begin{array}{c} {{\bf{R}}^{\rm{T}}} = ({x_1},{x_2},\cdots ,{x_L})' = \\ \left( {\begin{array}{*{20}{l}} {{{\left\langle {{w_1}} \right\rangle }_{{m_1}}}}&{{{\left\langle {{w_2}} \right\rangle }_{{m_1}}}}& \ldots &{{{\left\langle {{w_L}} \right\rangle }_{{m_1}}}}\\ {{{\left\langle {{w_1}} \right\rangle }_{{m_2}}}}&{{{\left\langle {{w_2}} \right\rangle }_{{m_2}}}}& \ldots &{{{\left\langle {{w_L}} \right\rangle }_{{m_2}}}}\\ {{\rm{ }} \vdots }&{{\rm{ }} \vdots }& \ddots &{{\rm{ }} \vdots }\\ {{{\left\langle {{w_1}} \right\rangle }_{{m_L}}}}&{{{\left\langle {{w_2}} \right\rangle }_{{m_L}}}}& \ldots &{{{\left\langle {{w_L}} \right\rangle }_{{m_L}}}} \end{array}} \right)\left( {\begin{array}{*{20}{l}} {{x_1}}\\ {{x_2}}\\ {{\rm{ }} \vdots }\\ {{x_L}} \end{array}} \right) = \\ \left( {\begin{array}{*{20}{l}} 1&0& \ldots &0\\ 0&1& \ldots &0\\ \vdots & \vdots & \ddots & \vdots \\ 0&0& \ldots &1 \end{array}} \right)\left( {\begin{array}{*{20}{l}} {{x_1}}\\ {{x_2}}\\ {{\rm{ }} \vdots }\\ {{x_L}} \end{array}} \right) = \\ {W_{{\rm{RNS}}}}{X_W} \end{array}$

(5)

式中，${{\bf{R}}^{\rm{T}}}$表示整数X在余数基$\left\{ {{m_1},{m_2},\cdots ,{m_L}} \right\}$下的余数表示；${X_W}$为传统CRT权重下的整数X的余数表示；${W_{{\rm{RNS}}}}$为权重的余数表示矩阵，这里为一个单位阵。

因此，可以将CRT的运算视为一矩阵运算过程，只要保证式(5)的权重的余数矩阵${W_{{\rm{RNS}}}}$与${X_W}$的运算结果为${R^{\rm{T}}}$，则可以改变${W_{{\rm{RNS}}}}$和${X_W}$，特殊的${W_{{\rm{RNS}}}}$或${X_W}$可能简化后向转换复杂度。

本文对CRT做如下推广：若余数基为$\left\{ {{m_1},{m_2},\cdots ,{m_L}} \right\}$，整数X的余数表示为$({x_1},{x_2},\cdots ,{x_L})$，指定后向转换权重系数为${w'_i}$且新的权重系数下的余数表示为${x'_i}$：

$\left( {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ \vdots \\ {{x_L}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{{\left\langle {{{w'}_1}} \right\rangle }_{{m_1}}}}&{{{\left\langle {{{w'}_2}} \right\rangle }_{{m_1}}}}& \ldots &{{{\left\langle {{{w'}_L}} \right\rangle }_{{m_1}}}}\\ {{{\left\langle {{{w'}_1}} \right\rangle }_{{m_2}}}}&{{{\left\langle {{{w'}_2}} \right\rangle }_{{m_2}}}}& \ldots &{{{\left\langle {{{w'}_L}} \right\rangle }_{{m_2}}}}\\ \vdots & \vdots & \ddots & \vdots \\ {{{\left\langle {{{w'}_1}} \right\rangle }_{{m_L}}}}&{{{\left\langle {{{w'}_2}} \right\rangle }_{{m_L}}}}& \ldots &{{{\left\langle {{{w'}_L}} \right\rangle }_{{m_L}}}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{{x'}_1}}\\ {{{x'}_2}}\\ \vdots \\ {{{x'}_L}} \end{array}} \right)$

(6)

即：

$R = {W'_{{\rm{RNS}}}}{X'_W}$

(7)

若式(7)运算成立，则运算结果保持不变。

显然，

${x_j} = \sum\nolimits_{i = 1}^L {{{\left\langle {{{w'}_i}} \right\rangle }_{{m_j}}}{{x'}_i}} $

(8)

据此，可得到：

${X'_W} = {W'_{{\rm{RNS}}}}^{ - 1}{\bf{R}}$

(9)

本文定义式(8)和式(9)为CRT运算的前处理过程，其复杂度直接与所指定的${W'_{{\rm{RNS}}}}$相关。

2.2 权重分配的约束条件

为了保证算法的正确性，前面指定${W'_{{\rm{RNS}}}}$的方法必须满足式(9)的矩阵逆运算，且所涉及到的模倒数存在，下面讨论这种预分配权重的后向转换方法的约束条件。

1) 可逆性约束

由式(9)可知，新指定的权重${w'_i}$所确定的${W'_{{\rm{RNS}}}}$矩阵应具有可逆的性质。总可以找到合适的${W'_{{\rm{RNS}}}}$或${w'_i}$使${W'_{{\rm{RNS}}}}$可逆，实际应用中可以通过首先指定${W'_{{\rm{RNS}}}}$，保证它可逆，然后再得到对应的权重${w'_i}$。

2) 存在性约束

令${W^{inv}} = {W'_{{\rm{RNS}}}}^{ - 1}$，其矩阵各元素为$w_{i,j}^{inv}$($i,j = 1,2,\cdots ,L$)，根据CRT，在新指定的权重及余数表示下，整数X可表示为：

$X = {\left\langle {\sum\nolimits_{i = 1}^L {w'\sum\nolimits_{}^{} w _{i,j}^{inv}{x_i}} } \right\rangle _M} = {\left\langle {a/b} \right\rangle _M}$

(10)

式中，$a$、$b$满足$GCD(a,b) = 1$($GCD(a,b)$表示整数$a$和$b$的最大公约数，即该分数表示不可再约)。即式(10)的求和运算结果可能为一分数形式，它由所指定的权重${w'_i}$或权重的余数矩阵${W'_{{\rm{RNS}}}}$决定。

所指定的矩阵${W'_{{\rm{RNS}}}}$及对应的权重${w'_i}$应保证${\left\langle {a/b} \right\rangle _M}$存在(即${\left\langle {a{{\left\langle {{b^{ - 1}}} \right\rangle }_M}} \right\rangle _M}$存在)。按照模倒数的定义，${\left\langle {{b^{ - 1}}} \right\rangle _M}$存在的条件为$b$与$M$互质。因此，对于限定条件2)，所指定的${W'_{{\rm{RNS}}}}$或${w'_i}$需保证式(10)的运算中分母与 互质。

进一步，考虑式(10)，由于后向转换中${W'_{{\rm{RNS}}}}$或${w'_i}$预先指定，仅${x_i}$为变量且为整数。${W'_{{\rm{RNS}}}}$由模运算结果得到，因此它的元素为整数，若${W'_{{\rm{RNS}}}}$的行列式值为$\left| {{{{\bf{W'}}}_{{\rm{RNS}}}}} \right|$，则${W'_{{\rm{RNS}}}}^{ - 1}{X_{{\rm{RNS}}}}$的计算结果可能出现分母$\left| {{{{\bf{W'}}}_{{\rm{RNS}}}}} \right|$。考虑到${w'_i}$也可能指定为分数，令其为${a'_i}/{b'_i}$，则为了满足限定条件2)，则要求$\left| {{{W'}_{{\rm{RNS}}}}} \right|{b'_i}$与$M$互质。

如果$b = 1$，显然${\left\langle {a/b} \right\rangle _M}$存在；如果$b \ne 1$，则该运算为分数模运算，按照分数模运算的定义，令运算结果为$y$，即$y = {\left\langle {a/b} \right\rangle _M}$，则：

$by = kM + a$

(11)

式中，$k$为整数，适当的$k$和$y$即为式(11)的解，若限定$0 \le y < M$，且模运算存在，则$k$和$y$唯一。

经过以上扩展，CRT成为本文算法的一个特例，它所选取的${W_{{\rm{RNS}}}}$具有最简形式，即一个单位阵(如式(5)所示)。

2.3 数值计算举例

对于余数基为$\left\{ {3,5,7} \right\}$的余数系统，CRT的权重分别为70、21和15，$M = 105$。

例1：首先指定${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 111\\ 011\\ 001 \end{array}} \right)$，则${W'_{{\rm{RNS}}}}^{ - 1}{\rm{ = }}\left( {\begin{array}{*{20}{c}} 1{ - 1}{{\rm{ }}0}\\ 0{{\rm{ }}1}{ - 1}\\ 0{{\rm{ }}0}{{\rm{ }}1} \end{array}} \right)$，$({w'_1},{w'_2},{w'_3}) = (70,91,1)$。由式(9)可知，${X'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 1&{ - 1}&0\\ 0&1&{ - 1}\\ 0&0&1 \end{array}} \right)\left( \begin{array}{c} {x_1}\\ {x_2}\\ {x_3} \end{array} \right) = \left( \begin{array}{c} {x_1} - {x_2}\\ {x_2} - {x_3}\\ {x_3} \end{array} \right)$。对于整数23的余数表示为$(2,3,2)$，权重${w'_i}$下的CRT转换结果为${\left\langle {70 \times (2 - 3) + 91 \times (3 - 2) + 1 \times 2} \right\rangle _{105}} = 23$，转换正确。

例2：首先指定$({w'_1},{w'_2},{w'_3}) = (70,77,78)$，则${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 120\\ 023\\ 001 \end{array}} \right)$，${W'_{{\rm{RNS}}}}^{ - 1}{\rm{ = }}\left( {\begin{array}{*{20}{c}} 1{ - 1}{{\rm{ }}3}\\ 0{0.5}{ - 1.5}\\ 0{{\rm{ }}0}{{\rm{ }}1} \end{array}} \right)$。由式(9)可知，${X'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 1&{ - 1}&3\\ 0&{0.5}&{ - 1.5}\\ 0&0&1 \end{array}} \right)\left( \begin{array}{c} {x_1}\\ {x_2}\\ {x_3} \end{array} \right) = \left( \begin{array}{c} {x_1} - {x_2} - 3{x_3}\\ \frac{{{x_2} - 3{x_3}}}{2}\\ {x_3} \end{array} \right)$。对于整数22的余数表示$(1,2,1)$，权重${w'_i}$下的CRT转换结果为${\left\langle \begin{array}{l} 70 \times \left( {1 - 2 - 3 \times 1} \right) + \\ 77 \times \left( {2 - 3 * 1} \right)/2 + 78 \times 1 \end{array} \right\rangle _{105}} = {\left\langle { - 481/2} \right\rangle _{105}}$。按照模倒数的定义，${\left\langle {{2^{ - 1}}} \right\rangle _{105}} = 53$。因此，${\left\langle { - 481/2} \right\rangle _{105}} = {\left\langle { - 481 \times {{\left\langle {{2^{ - 1}}} \right\rangle }_{105}}} \right\rangle _{105}} = \left\langle { - 481 \times 53} \right\rangle = 22$，转换正确。

3 基于CRT扩展算法的应用实例

下面给出一种基于本文CRT扩展算法的简单应用实例，在该示例中将利用扩展算法实现RNS到MRS的并行转换，并且消除CRT中的模 运算。

3.1 权重预分配过程

对于三模余数系统$\{ {m_1},{m_2},{m_3}\} $，指定新的权重分别为${w'_1}$、${w'_2}$和${w'_3}$，其对应的余数矩阵和混合基矩阵分别为${W'_{{\rm{RNS}}}}$和${W'_{{\rm{MRS}}}}$。如果权重${w'_i}$和新的余数向量${x'_i}$用混合基$\left[{{m_1},{m_2},{m_3}} \right]$来表示，其权重为$({m_2}{m_3},{m_3},1)$。若指定${x'_i}$为新的权重下的余数表示，权重${w'_i}$的混合基表示分别为$({t_1},0,0)$、$({t_2},1,0)$和$({t_3},0,1)$。其最高位的自然溢出与模$M$运算等价，从而可消除CRT中的模运算，同时低两位不需要乘法运算，由式(10)可得：

$\begin{array}{c} X = {\left\langle {{{W'}_{{\rm{MRC}}}}{{X'}_{{\rm{RNS}}}}} \right\rangle _M} = \\ {\left\langle {({t_1},0,0){{x'}_1} + ({t_2},1,0){{x'}_2} + ({t_3},0,1){{x'}_3}} \right\rangle _M} = \\ {\left\langle {({t_1}{{x'}_1} + {t_2}{{x'}_2} + {t_3}{{x'}_3},{{x'}_2},{{x'}_3})} \right\rangle _M} = \\ ({\left\langle {{t_1}{{x'}_1} + {t_2}{{x'}_2} + {t_3}{{x'}_3}} \right\rangle _{{m_1}}},{{x'}_2},{{x'}_3}) \end{array}$

(12)

这里${x'_i}$并未表示成混合基形式，需要做一些特殊处理，将在后续详细介绍。

据此，根据${w'_i}$的混合基表示可得到指定的权重为：

$\left\{ {\begin{array}{*{20}{c}} {{{w'}_1} = {t_1}{m_2}{m_3}}\\ {{{w'}_2} = {t_2}{m_2}{m_3} + {m_3}}\\ {{{w'}_3} = {t_3}{m_2}{m_3} + 1} \end{array}} \right.$

(13)

其对应的余数矩阵为：

${W'_{{\rm{RNS}}}} = \left( \begin{array}{l} {\left\langle {{t_1}{m_1}{m_3}} \right\rangle _{{m_1}}}\;\;{\left\langle \begin{array}{l} {t_2}{m_2}{m_3}\\ + {m_3} \end{array} \right\rangle _{{m_1}}}\;\;{\left\langle \begin{array}{l} {t_3}{m_2}{m_3}\\ + 1 \end{array} \right\rangle _{{m_1}}}\\ \;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;\;{\left\langle {{m_3}} \right\rangle _{{m_2}}}\;\;\;\;\;\;\;\;\;\;\;\;1\\ \;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;\;\;\;0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 \end{array} \right)$

(14)

进一步，为了简化运算且使得${W'_{{\rm{RNS}}}}$可逆，令${\left\langle {{t_1}{m_2}{m_3}} \right\rangle _{{m_1}}} = 1$，${\left\langle {{m_3}} \right\rangle _{{m_2}}} = 1$，${t_2} = {t_3} = 0$，最后可得到指定的权重分别为：

$\left\{ {\begin{array}{*{20}{c}} {{{w'}_1} = {t_1}{m_2}{m_3}}\\ {{{w'}_2} = {m_3}}\\ {{{w'}_3} = 1} \end{array}} \right.$

(15)

对应的混合基矩阵为：

${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} {{{\left\langle {{t_1}{m_2}{m_3}} \right\rangle }_{{m_1}}}}&0&0\\ 0&1&0\\ 0&0&1 \end{array}} \right)$

(16)

对应的余数矩阵为：

${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} {{{\left\langle {{t_1}{m_2}{m_3}} \right\rangle }_{{m_1}}}}&{{{\left\langle {{m_3}} \right\rangle }_{{m_1}}}}&1\\ 0&{{{\left\langle {{m_3}} \right\rangle }_{{m_2}}}}&1\\ 0&0&1 \end{array}} \right)$

(17)

对于${\left\langle {{t_1}{m_2}{m_3}} \right\rangle _{{m_1}}} = 1$，${t_1}$即为${\left\langle {{{({m_2}{m_3})}^{ - 1}}} \right\rangle _{{m_1}}}$，由于$GCD({m_i},{m_j}) = 1$($i,j = 1,2,3$)，因此它一定存在；对于${\left\langle {{m_3}} \right\rangle _{{m_2}}} = 1$则对余数基的选择做了一定限制。这种权重指定方式，可以快速进行${\left\langle {{m_3}} \right\rangle _{{m_2}}} = 1$这类余数基的后向转换。

3.2 转换过程

根据式(17)以及前述的限定条件，新指定的余数矩阵为：

${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 1&{{{\left\langle {{m_3}} \right\rangle }_{{m_1}}}}&1\\ 0&1&1\\ 0&0&1 \end{array}} \right)$

(18)

其逆矩阵为：

${W'_{{\rm{RNS}}}} = \left( {\begin{array}{*{20}{c}} 1&{ - {{\left\langle {{m_3}} \right\rangle }_{{m_1}}}}&{{{\left\langle {{m_3}} \right\rangle }_{{m_1}}} - 1}\\ 0&1&{ - 1}\\ 0&0&1 \end{array}} \right)$

(19)

根据式(8)，新的权重下的余数表示为：

$\begin{array}{l} {{X'}_W} = \left( {\begin{array}{*{20}{c}} 1&{ - {{\left\langle {{m_3}} \right\rangle }_{{m_1}}}}&{{{\left\langle {{m_3}} \right\rangle }_{{m_1}}} - 1}\\ 0&1&{ - 1}\\ 0&0&1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}} \end{array}} \right) = \\ \;\;\;\;\;\;\;\;\;\left( \begin{array}{c} {x_1} - {x_2}{\left\langle {{m_3}} \right\rangle _{{m_1}}} + {x_3}{\left\langle {{m_3}} \right\rangle _{{m_1}}} - {x_3}\\ {x_2} - {x_3}\\ {x_3} \end{array} \right) \end{array}$

(20)

根据式(13)，可得到混合基$\left[{{m_1},{m_2},{m_3}} \right]$表示下的计算结果：

$Z = \left( {{{\left\langle {{t_1}\left( \begin{array}{l} {x_1} - {x_2}{\left\langle {{m_3}} \right\rangle _{{m_1}}} + \\ {x_3}\left( {{{\left\langle {{m_3}} \right\rangle }_{{m_1}}} - 1} \right) \end{array} \right)} \right\rangle }_{{m_1}}},{x_2} - {x_3},{x_3}} \right)$

(21)

式(22)的计算结果中，最低位$0 \le {x_3} \le {m_3} - 1$，符合MRS的表示规则，最高位进行模运算后也符合MRS的表示规则，对于中间位${x_2} - {x_3}$，讨论如下：由于$0 \le {x_2} \le {m_2} - 1$，$0 \le {x_3} \le {m_3} - 1$，因此$1 - {m_3} \le {x_2} - {x_3} \le {m_2} - 1$，可能出现负数。考虑到${\left\langle {{m_3}} \right\rangle _{{m_2}}} = 1$，若${m_3} - {m_2} = 1$，则$ - {m_2} \le {x_2} - {x_3} \le {m_2} - 1$，它表明在这种限定下MRS的表示中间位出现负数时，表明向最高位借一位且进行模运算，即可得到标准的MRS表示形式。

由以上讨论，该实例对余数基的限定形式为${\left\langle {{m_3}} \right\rangle _{{m_2}}} = 1$，且${m_3} - {m_2} = 1$，这种限定是实用的，它包含了一大类余数基，例如常见的形如${\rm{\{ }}{m_1},{2^n} - 1,{2^n}{\rm{\} }}$和${\rm{\{ }}{m_1},{2^n},{2^n} + 1{\rm{\} }}$的余数基(其中${m_1}$可在满足互质条件下取值)都满足该限定条件。本文所举应用实例的实现框图如图 1所示，其中$s$为${x_2} - {x_3}$的符号，负数时为“1”，正数则为“0”。

3.3 数值计算实例

例3：对于余数系统$\left\{ {{m_1},{m_2},{m_3}} \right\} = \left\{ {5,8,9} \right\}$，${t_1} = 3$，${\left\langle {{m_3}} \right\rangle _{{m_1}}} = 4$，整数121的余数表示为$\left\{ {1,1,4} \right\}$，$s = 1$。则根据图 1的计算结果的MRS表示为$({\left\langle {3 \times (1 - 1 \times 4 + 4 \times (4 - 1)) - 1} \right\rangle _5},{\left\langle {1 - 4} \right\rangle _8},4)$，即$(1,5,4)$，该混合基数值表示的整数为121，转换正确。

例4：对于余数系统$\left\{ {{m_1},{m_2},{m_3}} \right\} = \left\{ {5,7,8} \right\}$，${t_1} = 1$，${\left\langle {{m_3}} \right\rangle _{{m_1}}} = 3$，整数215的余数表示为$\left\{ {0,5,7} \right\}$，$s = 1$。则根据图 1的计算结果的MRS表示为$({\left\langle {1 \times (0 - 5 \times 3 + 7 \times (3 - 1)) - 1} \right\rangle _5},{\left\langle {5 - 7} \right\rangle _8},7)$，即$(3,6,7)$，它表示的整数为215，转换正确。

通过该实例使用本文所提出的CRT扩展算法，消除了RNS到MRS转换中的迭代过程，同时将所有运算限定在较小的模运算中，其对复杂度的降低显而易见。这里所举实例可能不是最优化的，仅为了阐述利用本文的扩展算法如何进行权重指定等过程。

4 算法分析与比较

本文所提出的算法是中国剩余定理的扩展，在权重的余数矩阵${{\bf{W}}_{{\rm{RNS}}}}$选择为单位阵时则与CRT完全相同。当${{\bf{W}}_{{\rm{RNS}}}}$不为单位阵时，由式(8)可知，将在CRT进行最后模运算时引入一些简单的乘加运算，称为预处理过程。这种预处理过程针对不同的设计目的以及不同的余数基类型可进行特殊设计，根据作者目前研究，可从以下几个方面考虑权重的分配：

1) 指定比CRT的权重更小的权重，以简化式(10)中的乘法运算；

2) 可以从混合基转换的角度，指定便于混合基运算的权重，这种混合基的指定并不限于当前的余数基形式，例如4中的应用实例，若余数基为${\rm{\{ }}3,4,5{\rm{\} }}$，进行式(12)运算的混合基可选择为$\left[{6,10} \right]$，则可以通过最高位的模运算消除CRT中的模$M$运算并直接得到最后的十进制表示；

3) 根据特定的余数基形式，采用数值搜索的方法获得需要指定的权重，简化的后向转换结构。

本文所提出的CRT扩展算法极其灵活，针对不同的应用场合可进行相应的权重分配，其目的在于消除CRT中较大的模运算，根据不同的权重分配方式其复杂度差别较大。表 1给出了本文算法与MRC、CRT及其变型的定性比较。

对于CRT，由式(1)可知，它支持任意的传统互质余数基的R/B转换，其乘法运算中的操作数至少为${M_i}$，该值可能大于动态范围$M$，且最后需要一个模$M$运算，但其运算可以并行进行，由CRT可知，使用CRT需要进行$n$次模乘法和$n - 1$次模加法，CRT对应了本文算法${W_{RNS}}$为一个单位阵的情况。而对于其变型CRT-Ⅰ，减小了CRT中的权重，从而减小了乘法运算的复杂度，但仍然需要模$M$运算，而且增加了模加法运算的次数，需要$2n - 2$次，而需要$n - 1$次模乘法运算，CRT-Ⅰ对应了本文算法预分配权重为${\rm{\{ }}1,{m_1},\cdots ,{m_1}{m_2} \cdot \cdot \cdot {m_{L - 1}}{\rm{\} }}$的情况。而对于CRT-Ⅱ，其本质在于不断地进行两通道R/B转换来实现多通道余数系统到权重系统的转换，因此降低了CRT的并行性，但该算法在每一次两通道转换中可以减小CRT运算中的模运算，最好情况下可以将最后模运算和乘法运算的位宽减至动态范围位宽的一半，而模加法和模乘法的次数分别大于$\left( {1 + \left| {\log n} \right|} \right)\left| {\log n} \right|/2$和$(1 + \left\lfloor {\log n} \right\rfloor )\left\lfloor {\log n} \right\rfloor $次。CRT-Ⅲ则基于CRT-Ⅱ来解决特殊的非互质RNS的后向转换问题，其复杂度与CRT-Ⅱ类似。混合基转换MRC则是一个迭代运算过程，需要较大的时延和较多的模乘加运算次数，其优点在于具有较小的模运算和乘法运算位宽。本文所提出的ECRT算法包含了CRT及其变型，它们是本文算法的一个特例，通过不同应用场合下的权重优化可得到简化的转换过程。本文算法的重点在于给出RNS的后向转换优化途径，而不在于针对具体余数基或者具体转换算法进行讨论。

本文所提算法复杂度与权重选择具有较大关联，因此表 2给出了对余数系统${\rm{\{ }}{m_1},{m_2},{m_3}{\rm{\} }} = {\rm{\{ }}{2^n} - 1,{2^n},{2^n} + 1{\rm{\} }}$进行后向转换的复杂度的分析比较，其中余数基两两互质，因此表中不含有CRT-Ⅲ，本文算法权重选择如图 1所示，且选择${t_1} = {2^{n - 1}}$，由表 2中可知本文所提算法具有最小的计算位宽与计算次数。

5 结 束 语

本文提出了一种中国剩余定理的扩展算法，该算法通过预先指定CRT中的权重来获得灵活高效的余数系统到权重系统的转换算法，降低VLSI实现复杂度。同时，本文还给出了该算法的权重指定的限定条件，满足限定条件下的权重指定则可以保证运算结果的正确性。通过本算法，使得中国剩余定理成为本文算法的一个特例，增加了应用的灵活性。反过来，在权重分配过程中，结合限定条件可以对余数基进行一定优化限定，为余数基选择给出了新的思路。

本文算法的提出为有关余数系统的应用增添了新的研究内容，在未来的研究工作中，可以对权重的预分配方法进一步讨论，也可以针对已有余数基进行更优化的后向转换设计，从而有助于解决余数系统应用中的有关后向转换、大小比较、符号判断、基扩展等棘手问题。