Residue Number Systems: Theory and Implementation

by Z H Bar-NIV, BBC Audiobooks Ltd

Overview

Residue number systems (RNSs) and arithmetic are useful for several reasons. First, a great deal of computing now takes place in embedded processors, such as those found in mobile devices, for which high speed and low-power consumption are critical; the absence of carry propagation facilitates the realization of high-speed, low-power arithmetic. Second, computer chips are now getting to be so dense that full testing will no longer be possible; so fault tolerance and the general area of computational integrity have become more important. RNSs are extremely good for applications such as digital signal processing, communications engineering, computer security (cryptography), image processing, speech processing, and transforms, all of which are extremely important in computing today.This book provides an up-to-date account of RNSs and arithmetic. It covers the underlying mathematical concepts of RNSs; the conversion between conventional number systems and RNSs; the implementation of arithmetic operations; various related applications are also introduced. In addition, numerous detailed examples and analysis of different implementations are provided.

Product Details

ISBN-13:	9781860948664
Publisher:	Imperial College Press
Publication date:	09/10/2007
Series:	Advances in Computer Science and Engineering Reports
Pages:	312
Product dimensions:	6.32(w) x 8.95(h) x 0.84(d)

Table of Contents

Preface     vii
Introduction     1
Conventional number systems     2
Redundant signed-digit number systems     5
Residue number systems and arithmetic     6
Choice of moduli     9
Negative numbers     10
Basic arithmetic     11
Conversion     13
Base extension     14
Alternative encodings     14
Using residue number systems     15
Summary     17
References     18
Mathematical fundamentals     21
Properties of congruences     22
Basic number representation     24
Algebra of residues     27
Chinese Remainder Theorem     39
Complex residue-number systems     40
Redundant residue number systems     42
The Core Function     44
Summary     47
References     47
Forward conversion     49
Special moduli-sets     50
{lcub}2[superscript n-1], 2[superscript n], 2[superscript n+1]{rcub} moduli-sets     52
Extended special moduli-sets     56
Arbitrary moduli-sets: look-up tables     58
Serial/sequentialconversion     59
Sequential/parallel conversion: arbitrary partitioning     62
Sequential/parallel conversion: periodic partitioning     65
Arbitrary moduli-sets: combinational logic     68
Modular exponentiation     68
Modular exponentiation with periodicity     78
Summary     80
References     80
Addition     83
Conventional adders     84
Ripple adder     85
Carry-skip adder     88
Carry-lookahead adders     91
Conditional-sum adder     97
Parallel-prefix adders     101
Carry-select adder     108
Residue addition: arbitrary modulus     111
Addition modulo 2[superscript n] - 1     119
Ripple adder     122
Carry-lookahead adder     123
Parallel-prefix adder     127
Addition modulo 2[superscript n] + 1     130
Diminished-one addition     130
Direct addition     131
Summary     134
References     134
Multiplication     137
Conventional multiplication     138
Basic binary multiplication      139
High-radix multiplication     142
Conventional division     151
Subtractive division     151
Multiplicative division     160
Modular multiplication: arbitrary modulus     162
Table lookup     162
Modular reduction of partial products     165
Product partitioning     169
Multiplication by reciprocal of modulus     173
Subtractive division     176
Modular multiplication: modulus 2[superscript n] - 1     177
Modular multiplication: modulus 2[superscript n] + 1     185
Summary     191
References     191
Comparison, overflow-detection, sign-determination, scaling, and division     193
Comparison     194
Sum-of-quotients technique     195
Core Function and parity     197
Scaling     198
Division     201
Subtractive division     201
Multiplicative division     207
Summary     210
References     210
Reverse conversion     213
Chinese Remainder Theorem     213
Pseudo-SRT implementation     220
Base-extension implementation      223
Mixed-radix number systems and conversion     227
The Core Function     234
Reverse converters for [characters not reproducible]2n - 1, 2n,2n + 1[characters not reproducible] moduli-sets     237
High-radix conversion     248
Summary     251
References     251
Applications     255
Digital signal processing     256
Digital filters     257
Sum-of-products evaluation     264
Discrete Fourier Transform     272
RNS implementation of the DFT     275
Fault-tolerance     278
Communications     286
Summary     288
References     289
Index     293