Residue number systems: Theory and implementation

Contents......Page 12
Preface......Page 8
Acknowledgements......Page 11
1. Introduction......Page 16
1.1 Conventional number systems......Page 17
1.2 Redundant signed-digit number systems......Page 20
1.3 Residue number systems and arithmetic......Page 21
1.3.1 Choice of moduli......Page 24
1.3.2 Negative numbers......Page 25
1.3.3 Basic arithmetic......Page 26
1.3.4 Conversion......Page 28
1.3.6 Alternative encodings......Page 29
1.4 Using residue number systems......Page 30
1.5 Summary......Page 32
References......Page 33
2. Mathematical fundamentals......Page 36
2.1 Properties of congruences......Page 37
2.2 Basic number representation......Page 39
2.3 Algebra of residues......Page 42
2.4 Chinese Remainder Theorem......Page 54
2.5 Complex residue-number systems......Page 55
2.6 Redundant residue number systems......Page 57
2.7 The Core Function......Page 59
References......Page 62
3. Forward conversion......Page 64
3.1 Special moduli-sets......Page 65
3.1.1 {2n–1, 2n; 2n+1g} moduli-sets......Page 67
3.1.2 Extended special moduli-sets......Page 71
3.2 Arbitrary moduli-sets: look-up tables......Page 73
3.2.1 Serial/sequential conversion......Page 74
3.2.2 Sequential/parallel conversion: arbitrary partitioning......Page 77
3.2.3 Sequential/parallel conversion: periodic partitioning......Page 80
3.3.1 Modular exponentiation......Page 83
3.3.2 Modular exponentiation with periodicity......Page 93
References......Page 95
4. Addition......Page 98
4.1 Conventional adders......Page 99
4.1.1 Ripple adder......Page 100
4.1.2 Carry-skip adder......Page 103
4.1.3 Carry-lookahead adders......Page 106
4.1.4 Conditional-sum adder......Page 112
4.1.5 Parallel-pre¯x adders......Page 116
4.1.6 Carry-select adder......Page 123
4.2 Residue addition: arbitrary modulus......Page 126
4.3 Addition modulo 2n–1......Page 134
4.3.1 Ripple adder......Page 137
4.3.2 Carry-lookahead adder......Page 138
4.3.3 Parallel-prefix adder......Page 142
4.4.1 Diminished-one addition......Page 145
4.4.2 Direct addition......Page 146
References......Page 149
5. Multiplication......Page 152
5.1 Conventional multiplication......Page 153
5.1.1 Basic binary multiplication......Page 154
5.1.2 High-radix multiplication......Page 157
5.2.1 Subtractive division......Page 166
5.2.2 Multiplicative division......Page 175
5.3.1 Table lookup......Page 177
5.3.2 Modular reduction of partial products......Page 180
5.3.3 Product partitioning......Page 184
5.3.4 Multiplication by reciprocal of modulus......Page 188
5.3.5 Subtractive division......Page 191
5.4 Modular multiplication: modulus 2n–1......Page 192
5.5 Modular multiplication: modulus 2n + 1......Page 200
References......Page 206
6. Comparison, overflow-detection, sign-determination, scaling, and division......Page 208
6.1 Comparison......Page 209
6.1.1 Sum-of-quotients technique......Page 210
6.1.2 Core Function and parity......Page 212
6.2 Scaling......Page 213
6.3.1.1 Basic subtractive division......Page 216
6.3.1.2 Pseudo-SRT division......Page 221
6.3.2 Multiplicative division......Page 222
References......Page 225
7.1 Chinese Remainder Theorem......Page 228
7.1.1 Pseudo-SRT implementation......Page 235
7.1.2 Base-extension implementation......Page 238
7.2 Mixed-radix number systems and conversion......Page 242
7.3 The Core Function......Page 249
7.4 Reverse converters for f2n ¡ 1; 2n; 2n + 1g moduli-sets......Page 252
7.5 High-radix conversion......Page 263
References......Page 266
8. Applications......Page 270
8.1 Digital signal processing......Page 271
8.1.1.1 Finite Impulse Response ¯lters......Page 272
8.1.1.2 Infinite Impulse Response Filters......Page 278
8.1.2 Sum-of-products evaluation......Page 279
8.1.3.1 Fourier Series......Page 287
8.1.4 RNS implementation of the DFT......Page 290
8.2 Fault-tolerance......Page 293
8.3 Communications......Page 301
8.4 Summary......Page 303
References......Page 304
Index......Page 308