R N S Residue Number System resources |
preliminary / under construction |
---|
Background
A Residue Number System (RNS) is defined by a set of P relatively
prime integers { m1, m2, ... , mP } which identify the
RNS base. Its
dynamic range is given by the product
Any integer X ∈
{ 0, 1, 2, ... , M-1 } has a unique RNS representation given by:
M = m1 ·m2 · ... ·mP . (1)
where < X >mi denotes the operation
X mod mi
[1].
Figure 1
illustrates an example of RNS, with base
{ 5, 7, 8 } and dynamic range M=5 · 7 · 8 = 280,
and how a positive integer is mapped into the RNS.
The conversion from the RNS representation to the integer one can be accomplished by
the Chinese Remainder Theorem (CRT):
|
with | and | . |
| (2) |
As a consequence, operations on large wordlengths (2k ≤ M) can be split into several modular operations executed in parallel and with reduced wordlength (2k ≤ mi) [1].
Therefore, a digital system can be implemented in RNS by decomposing it into P data-paths working in parallel, as sketched in Figure 2.