ResidueNumberSystems_ieee_bangalore (1)(1).ppt

sdfghjkl

1. Residue Number systems
P.V. Ananda Mohan
FNAE, Fellow IEEE
[email protected]
IEEE CAS Chapter
8
th
March 2008
Bangalore

2. Why RNS
•Using several processors in parallel, some operations can be faster.
Mod m
1

Processor
r
1
O
1
Mod m
2

Processor
r
2
O
2
Mod m
j

Processor
r
j
O
j
RNS to Binary Converter
Result
Binary to
RNS
converter
Binary to
RNS
converter
Binary to
RNS
converter
Input Binary Number
Instruction

3. Points to be considered
•Choice of moduli set
•Computation time and area requirements for the
following blocks:
•Binary to RNS conversion
•RNS to Binary conversion
•Multiplication
•Scaling
•Base extension
•Sign detection
•Comparison

4. Binary to RNS conversion
•(a) Conventional method: division to get
residue throwing away quotient

•--Very time consuming.
•Example (1000 0001 1010) mod 13?
•2074 mod 13 = 7.

5. •(b) Iterative reduction mod m
i
•(Capocelli and Giancarlo)
•Start with LSBs. Store residues of powers of two in
memory go on accumulating till end mod 13:
•1,2,4,8,3,6,12,11,9,5,10,7
•Example (1000 0001 1010) mod 13?
•Last three bits you can skip.
•2+2
3
mod 13 = 2+8 = 10
•10+2
4
mod 13 = 10+3=0 and so on
•Hardware needed : a modulo adder, Memory containing
residues of Powers of 2 mod 13.

6. • (c) Use periodic properties of moduli
•For example consider modulus 18.
•Residues of powers of two are
(1,2,4,8,3,6), (12,11,9,5,10,7),(1,2,4,8..)
etc
•Note the periodic property
•(1,2,4,8,3,6), (-1,-2,-4,-8,-3,-6),
(1,2,4,8,3,6), (-1,-2,-4,-8,-3,-6)

7. Consider mod 89
•Residues of successive powers of two are
1,2,4,8,16,32,64,39,78,67,45,
1,2,4,8,16,32,64,39,78,67,45,
•Thus period (or order) is 11
•i.e. 2
11
mod 89=1

8. •Implementation: Group input bits based on
period or half period.
•If based on period, add all words with same
period mod 2
11
and have one Binary to RNS
converter of Capocelli and Giancarlo.
•If based on half-period add all odd fields and
add all even fields, Compute odd-even and use
Capocelli and Giancarlo method

9. •Example
•2074 mod 13= (100000 011010) mod 13
•= (26-32) mod 13 = -6 mod 13 = 7.
•2074 mod 7 = (100 000 011 010) mod7
•= (4+0+3+2) mod 7=2
•Use for full period case, Adders with end
around carry (EAC) and for half period
case, two adders with EAC

10. •Delay is (2+3+2)D
FA
1 0 0 0 0 0
0 1 1
0 1 0
0
0
100
000
011
-----
111Sum
0000 Carry
010
-------
101 Sum
0100 Carry
------
1001
1
------
010

11. Modulo adders and subtractors
•(X+Y) mod m
i = (X+Y) or (X+Y-m
i)
•(X-Y) mod m
i = (X-Y) or (X-Y+m
i)
(X+Y)
Two’s complement of m
i
or
(2
n
-m
i
)
X Y
2:1 MUX
select
Sign
bit
(X+Y) mod m
i
n bit Adder
(n +1) bit Adder
Delay = nD
FA
+(n+1)D
FA
+D
MUX
Area = nA
FA
+(n+1)A
FA
+n D
2:1MUX
Cascade of Adders

12. Faster Adder Implementations
•Subtractor is same bur two’s compliment
of input to be added.
X Y
select
n bit Adder
(X+Y)
Two’s complement of
m
i
or (2
n
-m
i
)
2:1 MUX
Sign
bit
(X+Y) mod m
i
(n +1) bit Adder
Delay = (n+2)D
FA
+D
MUX
Area = nA
FA
+2(n+1)A
FA
+n D
2:1MUX

13. Modulo Multipliers
•Area Multiplier+divider
•Delay Multiplier+divider
•Divider can be restoring or non-restoring.
•Word length of the processor 2n bits
X Y
Multiplier
XY
m
i
Divider
Quotient
Throw it.
Reminder

14. Brickell’s Algorithm based Modulo
Multipliers
•Maximum word length (n+1) bits for taking
one bit at a time.
•Higher radix feasible.
•Area intensive
•Other methods exist such as using
Redundant Arithmetic, non-overlapping
multibit recoding

15. •13.15 mod 23
•We do not want to do in a straight forward
manner .
•Write b = 13 in binary form:
• b
3
b
2
b
1
b
0
=1101
•Do repeatedly starting from MSB:
•Old= (2.Old + b
i.A) mod 23

16. EXAMPLE
•b
3b
2b
1b
0 =1101; A =15, m
i = 23
•P= (2.0 + 1.15) mod 23 = 15
•P=(2.15 + 1.15) mod 23 = 22
•P=(2.22 + 0.15) mod 23 = 21
•P=(2.21+ 1.15) mod 23 = 11
•Maximum value of P <3(23) i.e. 3m
i
•Modulo subtraction is by two comparisons:
•Is P>N? or Is P>2n?
•Answer is either P, P-m
i
, P-2m
i
; choose

based on sign of P-m
i
,
P-2m
i.
•Example 45 mod 23, anwers are 45,45-23=22,45-46=-1; since P-
2m
i is negative and P-m
i is positive, P-mi is the correct result.
•Multiple precision arithmetic to be used in PC based
implementations

17. Architecture for Modmul
LSB of
Zero
Old
2Old
A
b
i
(n+2) bit adder
Adder
TC of m
i
Adder
TC of 2m
i
3:1 Mux
Latch
Latch

18. ModMUL
•Computation time= n[(n+2)D
FA
+D
Mux
]
•Area = 3(n+2)A
FA+A
3:1MUX+nA
AND

19. Modmul for IDEA
•IDEA (International Data Encryption
Algorithm) uses (xy) mod (2
16
+1) as a
programmable S-Box (Substitution Box),
where x and y are 16 bit words.
•Ideal for DSPs
•Get P=xy a 32 bit word.
•Subtract MSB 16 bit word from LSB 16 bit
word. If negative, add (2
16
+1)

20. RNS to Binary Conversion
•CRT based
•MRC based
•CRT: RNS {m
1
,m
2
,m
3
} Residues {x
1
,x
2
,x
3
}
•Define M
i
=M/m
i
and M=m
1
m
2
m
3
•Decoded Binary number X
•= [M
1
{(1/M
1
) mod m
1
}x1+ {M
2
(1/M
2
) mod m
2
}x
2
+ M
3
{(1/M
3
) mod
m
3}x
3]mod M
•e.g. {3,5,7} M=105, M
1=35,M
2=21,M
3=15
•(1/35) mod 3 = 2, (1/21) mod 5=1, (1/15) mod 7=1.
•X= [70x
1+21x
2+15x
3] mod 105
•Consider (1,2,3), X = (70+42+45) mod 105 = 157 mod 105 = 52
•Generally, M
i are large, M
i{(1/M
i) mod m
i} are stored,involves
multiplication of these large numbers by x
i
in parallel and adding.

21. CRT Implementation
•Modulo M adder may involve n subtractions for a n
moduli system
•Delay = D
Mult
+ D
MODADD

X
1
[M
1
(1/M
1
) mod m
1
]
Multiplier
Multiplier
X
2
Multiplier
[M
3
(1/M
3
) mod m
3
]
[M2(1/M2) mod m2]
X
3
Mod M adder
X

22. MRC
•Note X
A
= (1/m
3
) mod m
1
and

•X
B= (1/m
3) mod m
2,
X
C= (1/m
2) mod m
1
•U
C, U
B and r
3 are known as MRC digits.
•
X = U
Cm
2m
3+U
Bm
3+r
3 is always less than M.
m
1
m
2
m
3


r
1 r
2 r
3

- r
3 - r
3

(r
1-r
3) mod m
1 = p (r
2-r
3) mod m
2 =q
X
A X
B
U
A U
B
-U
B
(U
A-U
B) mod m
1 =r
X
C
U
C
Example RNS {7,8,9}
7 8 9
12 3
-3 -3
57
x4 x1
67
-7
6
x1
6
X = 6.72+7.9+3 = 498

23. MRC versus CRT
•MRC is sequential but avoids reduction modulo a large
number needed in CRT .
•MRC needs storage of multiplicative inverses, Modulo
subtraction and modulo multiplication, final addition of n
numbers for a n moduli RNS,
•Multiplicative inverses can be powers of two small
numbers such as 6 or 9 for powers of two related moduli
sets.
•Moduli set with all MIs of value unity also suggested e.g
{3,7,22}, Only modulo subtractions will do for evaluating
MRC digits; But multipliers are cumbersome.
•Generally need ROMs.

24. Architecture for XY mod 17
x3 x2 x1 x0
y3 y2 y1 y0
y0x3 yox2 y0x1 yox0
y1x3 y1x2 y1x1 y1x0 (y1x3)′ added 1
y2x3 y2x2 y2x1 y2x0 (y2x3)′ (y2x2)′ added 3
y3x3 y3x2 y3x1 y3x0 (y3x3)′ (y3x2)′ (y3x1)′ added 7
Write MSBs b
i as (1- b
i′)
′
Modulo 17 adder
1011
1101
1011
00001
101101
1011010
Adding 4 words in a CSA
1011
0001
1101
0111
10010 Added 1
1010
1111
00101 Added 1
0100 add 4 (correction

0111 term in a modulo
17 adder)

25. Scaling
•Division by a number
•E.g. RNS given {3,5,7}. Divide 99 (0,4,1)
by 11 (2,1,4).
•If division is exact, multiply 99 by
multiplicative inverse of 11.
•(1/11) = (2,1,2) =86 (Note (1/11) mod 3 =
2 etc.
•(99/11) = (0,4,1)x(2,1,2)= (0,1,4) =9

26. Scaling by arbitrary number when
division is not exact
•Example 1 : 100/13 in RNS {3,5,7}
•100 = (1,0,2}
•Direct method by multiplying with (1/13) will not work.
•100 = 1,0,2
•(1/13) = 1,2,6
•100/13 = 1,0,5 = 40 wrong.
•First you need to find residue of 100mod 13 = 9.
•Subtract from 100 to get (100-9)=91
•100 = 1,0,2
• 9 = 0,4,2
• 91 = 1,1,0
•(1/13) = 1,2,6
•91/13 = 1,2,0 = 7.

27. Scaling by one modulus
•Divide 100/7
•100 = 1,0,2
•Subtract residue 100mod 7 first =2
•100 = 1, 0, 2
• 2 = 2, 2, 2
• 98 = 2, 3, 0
• x(1/7) = x1 x3
•= 2 4
•Now you need to do base extension to get RNS number again
(2,4,0)
•Scaling by another modulus aso feasible in the same way.
•Note that MRC does this.

28. Scaled Residue /Montgomery’s Modular Multiplication
•Example: To evaluate (5.6) mod 13 = 4.
•Prescaling by 16: 5 = (5.16) mod 13 = 2, (6.16) mod 13
= 5
•Montgomery step = [(5.16)(6.16)/16] mod 13 = (2.5/16)
mod 13 = (10/3) mod 13 = (10.9) mod 13 = 12.
•Result is obtained by post scaling: (12/16) mod 13 =
(12/3) mod 13 = 4.
•Prescaling is Binary to RNS conversion: Successive
multiplication by 2 and modulo reduction , (5.2) mod 13=
10, (10.2) mod 13 = (7.2) mod 13= 1, (1.2) mod 13 = 2.
•Post scaling is another Montgomery step.

29. •Montgomery step avoids modulo reduction. Only conditional addition. If
LSB is 1 add modulus, ignore LSB.
•Example (2.5/16) mod 13.
•Four steps are needed.
•Each step a partial product is added and result scaled by two.
•2 = 0010 (binary)
•Computation of (0010)x5/16:
•Formula: (old value+ bix5)/2
•Old value =0.
•(0+0.5)/2= 0
•(0+1x5)/2 = (5+13)/2 = 9 since LSB of current result in brackets is 1.
•(9+0.5)/2 = (9+13)/2 = 11
•(11+0.5)/2 = (11+13)/2 = 12.
•Addition of two numbers using a (n+1)-bit CPA, n AND gates, n Flip-flops
•

30. Higher Radix Montgomery’s
Technique
•Higher Radix possible.
•16 or 8 or 4 bits at a time can be considered.
•Example considering 4 bits at a time:
•Consider [(10001100)/16] mod 23
•Find (-1/23) mod 16=(-1/7) mod16 = 9 ((-1/m
i) mod 2
k
)
•Find 10001100 mod 16 = four LSBs= 12 (X mod 2
k
)
•Find (12x9) mod 16 = 12 α= [(-X/m
i) mod 2
k]
•Find 10001100+12(23) = 11010 0000 (X+ αm
i)
•Ignore last 4 bits to get 26. (X+ αm
i)/2
k

•Need a multiplier mod 16 to get the multiple to be added.
•Then addition of shifted versions of modulus (in this case of
radix 16, four shifted versions) using a CASA tree followed by
CPA.

31. Popular Powers-of-two related
moduli set
•(2
n
-1, 2
n
, 2
n
+1)
•Dynamic range <3n bits.
•Example 16 bit DSP needs n = 6; RNS
{63,64,65}
•RNS to binary conversion using CRT can
be done very fast.
•.

32. •The beauty is these are powers of two related
facilitating easy implementation.





  12122mod122
122
1
1212
1212
1
122
122
1
3
1
2
1
1
1

















 

















nnnnn
m
nn
m
nn
m
x
nn
x
nn
x
nn
B

212mod
122
1
1










nn
nn

12mod
1212
1










n
nn

 1212mod
122
1
1









nn
nn


The various multiplicative inverses used above are as follows:

33. •Example {7,8,9}
•[(32+4)x
1
-8x
2
+(36-1)x
3
] mod 63 yields 6
MSBs
    12122mod122)12(12121222
1
321
1

 nnnnnnnnnnn
xxxB
   12122mod122)12(21222)( 1
3
2
21
1
2 








 
 nnnnn
n
nnnn
xxxxB
    12mod12)12(2122
2
)(
21
321
12


 nnnnnn
n
xxx
xB
Subtract x
2
from both sides
Divide by 2
n
to get 2n MSBs of the result as

34. Realization
•Andraros and Ahmad : Four 2n-bit words to be added using
two levels of Adders of rotated bits.
•Piestrak suggested using CSA two level with CPA using end
around carry for adding four 2n-bit words
•Delay - (4n+2) D
FA, Area = (6n) A
FA
•Suggested Low delay version (2n+2) D
FA+D
MUX also, 2n
A
2:1MUXes needed.
•Dhurkadas (NPOL, Cochin) suggested simplification to three
2n-bit inputs to be added
•Delay – (4n+2) D
FA, Area = (4n) A
FA
•Bhardwaj, Premkumar, Srikanthan [1998] suggested using n-
bit adders e.g Carry select adders n-bit
•Wang et al [2002] 2n-bit as well as n-bit adders three
converters.

35. {7,8,9} example (x
1,x
2,x
3)
    12mod12)12(2122
2
)(
21
321
12


 nnnnnn
n
xxx
xB
x
1
, x
2
3 bit, x
3
4 bit
x
12
x
11
x
10
, x
22
x
21
x
20
, x
33
x
32
x
31
x
30
   12mod)122(2)22(
2
)(
2112
321
1122


 nnnnnn
n
xxx
xB
•[(32+4)x
1
-8x
2
+(36-1)x
3
] mod 63 :
x
10
x
12
x
11
x
10
x
12
x
11
x
22′ x
21′ x
20′ 1 1 1
X
3x
x
32
x
31
x
3x
x
32
x
31
1 1 x
33 ′ x
32 ′ x
31′ x
30 ′
X3x= x30+x33 since either x30 or
x33 exist
Dhurkadas Simplified as
x
10 x
12 x
11 x
10 x
12 x
11
x
22
′ x
21
′ x
20
′ y x
31
′ x
30
′
X
3x x
32 x
31 x
30 x
32 x
31
Y= (x
33
+x
32
)′

36. Other three, Four and Five moduli
sets
•{2
n
,2
n
-1,2
n-1
-1} Hiasat and Abdel-Aty-Zohdy, Wang, Wang, Swamy
and Ahmad: not better than popular moduli set, multipliers etc are
simpler
• {2
n
,2
n
-1,2
n+1
-1} Ananda Mohan better in area or time, multipliers
are simpler
• {2
n
,2
2n
-1,2
2n
+1} Ananda Mohan better than Cao et al four moduli
set, one large modulus
•{2
n
,2
n
-1,2
n
+1, 2
n+1
-1 } Vinod and Premkumar
•{2
n
,2
n
-1,2
n
+1, 2
n+1
-1 } Bhardwaj, Srikanthan, Ananda Mohan and
Premkumar Area and Time intensive
•{2
n
,2
n
-1,2
n
+1, 2
2n
+1} Cao et al better than other four moduli sets
but one modulus bigger in size.
•{2
n
-3,2
n
-1,2
n
+1,2
n
+3} Sheu et al uses ROM not attractive
•{2
n-1
-1, 2
n
-1,2
n
,2
n
+1,2
n+1
-1} Cao et al 2007 Increases cardinality to 5,
DR of 5n bits but RNS to Binary conversion is slower/area
consuming

38. •M2 {2
k
,2
k
-1,2
k-1
-1}, M1{2
k
-1,2
k
,2
k
+1},
•M4{2
k
,2
k
-1,2
k+1
-1}, M3{2
k
-1,2
k
,2
k
+1,2
k+1
-1}
Comparison of various converters for three
moduli sets
Converter Moduli set FA HA AND
/OR
XOR
/XNOR
Other Delay
[8] M2 6n-1 3n-7---- -----(n-1) MUX 4nD
FA
[5] M1 6n+1 ----n+3 n+1 2n MUX (n+2)D
FA
+D
MUX
[3,4] M1 4n --- 2 --- ---- (4n+1)D
FA
[6] CI M1 4n 1 ----- 1 2 MUX (4n+1)D
FA
[6] CII M1 6n 1 1 1 (2n+2) MUX (n+1)D
FA
[6] CIII M1 4n 1 (2n+2)(2n-1)(2n+2) MUX (n+1)D
FA
Converter I M4 4n+3 --- n n ----- (6n+5)D
FA
Converter II M4 14n+21 2n+3--- --- (2n+1) 3:1MUX (2n+7)D
FA
Converter III M4 12n+19 2n+2--- --- 10(2n+1)A
ROM
(2n+1) 2:1MUX
(2n+7)D
FA
[9] M3 37n+14 -- -- -- -- (14n+8)D
FA
[12,13] 4-stage CEM3 n
2
/2+11n+41 -- -- 2 MUX (11n+l+8)D
FA

39. Base Extension
•Needed in scaling or division.
•Uses MRC fist to divide followed by base
extension.
•CRT can be used but is cumbersome.
Example: {3,5,7} 52= (1,2,3) Scale by 7
3 5 7
1 2 3
-3 -3
14
x1 x3
12 2 First Base Extension step
-2
2
X2
1 +(1x5)mod 7 Base Extension step
0

40. RSA using RNS/ECC
•Needs computation of P
Q
mod N
•e.g 10
23
mod 37 = (10
16
)(10
4
)(10
2
)(10
1
) mod 37
•Successive squaring mod 37 and Multiplications mod 37 of selected
results.
•Needs (XY) mod N ass basic step where X,Y,N are 1024 bit
numbers.
•RNS can be used.
•Montgomery technique has been used to find (X′Y′/M) mod N where
M is the product of Moduli in RNS.
•Needs two RNS dynamic ranges M and M′ which are mutually
Prime and a redundant modulus
•Determine q such that (X′Y′+qN) is a multiple of M.
•Extend q to RNS with Dynamic range M′.
•Find r = (X′Y′+qN)/M in second RNS
•Do base extension to First RNS

41. Sign Detection and Comparison
•Is difficult
•Needed to go to Binary number to detect
sign
•Comparison is also difficult Needed to go
to Binary numbers or sequential
techniques such as comparing Mixed
Radix Digits.

42. Applications
•FIR Filters (ensure that RNS dynamic
range is larger than that of the filter)
•Digital Frequency Synthesis
•Video Filters
•2-D filters
•NTTs (Number Theoretic Transforms)
•Cryptography

43. Applications of RNS
•[5] Freking, W.L., and Parhi, K.K., "Low-power FIR digital filters using residue
arithmetic, " in Conf. Record 31st Asil. Conf. Signals, Syst. and Comput. (ACSSC
1997), vol. 1, Pacific Grove, CA USA [1997], 739-43.
•[6] D'Amora, A. et al., "Reducing power dissipation in complex digital filters by using
the quadratic residue number system, " in Conf. Record 34th Asil. Conf. Signals, Syst.
Comput. (ACSSC 2000), vol. 2, Pacific Grove, CA USA [2000], 879-83.
•[7] Cardarilli, G.C. et al., "Low-power implementation of polyphase filters in Quadratic
Residue Number system," in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS 2004), vol. 2,
Vancouver, BC, Canada [2004], 725-728.
•[8] Shanbag, N.R., and Siferd, R.E., A single-chip pipelined 2-D FIR filter using residue
Arithmetic, IEEE JSSC -26[1991], 796-805.
•[9] Tuukka Toivonen., and Janne Heikkilä., Video Filtering With Fermat Number
Theoretic Transforms Using Residue Number System, IEEE CSVT-16[2006], 128-135.
•[10] Schwemmlein, J., and Posch, K.C., Reinhard Posch. RNS-modulo reduction upon
a restricted base value set and its applicability to RSA cryptography, Computer &
Security [1998], 17, 637-650.
•[11]Hanae Nozaki., Masahiko Motoyama., Atsushi Shimbo., and Shinichi Kawamura.,
Implementation of RSA algorithm based on RNS Montgomery multiplication, In C. Paar
(ed). Cryptographic Hardware and Embedded Systems – CHES, Springer-Verlag,
Berlin, Germany [2001], 364-376.

44. •[12] Jean-Claude Bajard., Laurent Stephane Didier., Peter Kornerup.,
An RNS Montgomery modular multiplication Algorithm, IEEE C-47
[1998], 766-776.
•[13] Jean-Claude Bajard., and Laurent Imbert., A Full RNS
Implementation of RSA, IEEE C-53[2004],769-774.
•[14] Schinianakis, D.M., Kakarountas. A.P., and Stouraitis. T., A New
Approach to Elliptic Curve Cryptography: an RNS Architecture, IEEE
MELECON, May 16-19, Benalmádena (Málaga), Spain [2006], 1241-
1245.
•[15] Lie-Liang Yang., and Lajos Hanzo., A Residue Number System
Based Parallel Communication Scheme Using Orthogonal Signaling:
Part I—System Outline, IEEE VT-51[2002],1534-1546.
•[16] Chaves, R., and Sousa, L., “RDSP: A RISC DSP based on
residue number system,” in Proc. Euro. Symp. Digital System
Design: Architectures, Methods, and Tools, Antalya, Turkey [2003],
128-135.
•[17] Wei, W. et al., "RNS application for digital image processing," in
4th IEEE Int. Workshop Syst.-on-Chip for Real Time Applications,
Banff, Alta., Canada [2004],77-80.

45. Conclusion
•Very mature today
•Can be used in place of Custom DSP
blocks
•Research on newer moduli sets with high
cardinality and Faster Reverse
Conversion is of interest