244
D. Gorodecky and T. Villa
Hamming weight. This will reduce the number of terms (bits) being added. As an
illustration, for modulus 29, the various values of 2 x (mod 29) from 2 0 to 2 28 are as
follows [13]:
1, 2, 4, 8, 16, 3, 6, 12, 24, 19, 9, 18, 7, 14, 28, 27,
25, 21, 13, 26, 23, 17, 5, 10, 20, 11, 22, 15.
Given a 64-bit input word, the values repeat again from 2 29 till 2 57 , and once
more from 2 58 till 2 63 , with many of their bits being zero. Consider the residue 27,
i.e., 2 15 (mod 29) with Hamming weight 4. It can be written as (x 15 2 15 )(mod 29) =
(27 + 2x 15 ) so that when x 15 is zero, its value is (27 + 2)(mod 29) = 0. Since 2 has
Hamming weight smaller than 27, the number of bits to be added will be reduced.
This property applies to residues 19, 28, 27, 25, 21, 13, 26, 23, 11, and 15. Thus,
for a 64-bit input word, in a conventional design, 64 5-bit words should be added
in the general case; since many of their bits are zero, when deleting all these zero
bits, we would need to add 27, 28, 29, 31, and 30 bits in various columns. It can be
verified that the numbers of bits to be added in each column (corresponding to 2 i
for i = 4, 3, 2, 1, 0) are as follows (without Hamming weight optimization and with
Hamming weight optimization):
– without optimization: 27, 28, 29, 31, 30;
– with optimization: 17, 21, 25, 32, 18.
11.3.5 Approach Based on Special Moduli of the Type 2 n ± k
The approach based on special moduli of the type 2 n ± k is the most common
technique to design RNS [5, 13, 16]. The are two main reasons to use these values.
The first one is due to their simple forward conversion from the positional numerical
system to RNS. The second one is that backward conversion from RNS to the
positional system can be designed in hardware with smaller costs than using other
values of moduli.
Combinational approaches efficient with respect to performance and area exploit
special moduli sets [16], which are variations of 2 s ± v, where v = 1, 3, 5: {2 s −
1, 2 s , 2 s + 1}, {2 2·s − 1, 2 s , 2 2·s + 1}, {2 s − 1, 2 2·s , 2 s + 1, 2 s−1 − 1, 2 s+1 − 1},
etc. These moduli take advantage of the following identities (considering moduli
2 k ± 1):
2
k·n (mod (2
k
− 1)) = 1(mod (2
k
− 1))
and
2
k·n (mod (2
k
+ 1)) = (−1)
n−1 (mod (2
k
+ 1)).
D. Gorodecky and T. Villa
Hamming weight. This will reduce the number of terms (bits) being added. As an
illustration, for modulus 29, the various values of 2 x (mod 29) from 2 0 to 2 28 are as
follows [13]:
1, 2, 4, 8, 16, 3, 6, 12, 24, 19, 9, 18, 7, 14, 28, 27,
25, 21, 13, 26, 23, 17, 5, 10, 20, 11, 22, 15.
Given a 64-bit input word, the values repeat again from 2 29 till 2 57 , and once
more from 2 58 till 2 63 , with many of their bits being zero. Consider the residue 27,
i.e., 2 15 (mod 29) with Hamming weight 4. It can be written as (x 15 2 15 )(mod 29) =
(27 + 2x 15 ) so that when x 15 is zero, its value is (27 + 2)(mod 29) = 0. Since 2 has
Hamming weight smaller than 27, the number of bits to be added will be reduced.
This property applies to residues 19, 28, 27, 25, 21, 13, 26, 23, 11, and 15. Thus,
for a 64-bit input word, in a conventional design, 64 5-bit words should be added
in the general case; since many of their bits are zero, when deleting all these zero
bits, we would need to add 27, 28, 29, 31, and 30 bits in various columns. It can be
verified that the numbers of bits to be added in each column (corresponding to 2 i
for i = 4, 3, 2, 1, 0) are as follows (without Hamming weight optimization and with
Hamming weight optimization):
– without optimization: 27, 28, 29, 31, 30;
– with optimization: 17, 21, 25, 32, 18.
11.3.5 Approach Based on Special Moduli of the Type 2 n ± k
The approach based on special moduli of the type 2 n ± k is the most common
technique to design RNS [5, 13, 16]. The are two main reasons to use these values.
The first one is due to their simple forward conversion from the positional numerical
system to RNS. The second one is that backward conversion from RNS to the
positional system can be designed in hardware with smaller costs than using other
values of moduli.
Combinational approaches efficient with respect to performance and area exploit
special moduli sets [16], which are variations of 2 s ± v, where v = 1, 3, 5: {2 s −
1, 2 s , 2 s + 1}, {2 2·s − 1, 2 s , 2 2·s + 1}, {2 s − 1, 2 2·s , 2 s + 1, 2 s−1 − 1, 2 s+1 − 1},
etc. These moduli take advantage of the following identities (considering moduli
2 k ± 1):
2
k·n (mod (2
k
− 1)) = 1(mod (2
k
− 1))
and
2
k·n (mod (2
k
+ 1)) = (−1)
n−1 (mod (2
k
+ 1)).