Home > Residue Number System > Implementation of Residue Number System Based Digital Filters

Implementation of Residue Number System Based Digital Filters

Modulo Multipliers

We can use conventional multiplier (see Figure 3(a) first to find (A×B) and then find residue mod mi. Multiplication mod 2n is simple since we need to take only n LSBs of the product. As an illustration, consider finding (5×13) mod 16 = 1 since the product 65 = (0100 0001)2 and we ignore the four MSBs. Multiplication mod (2n-1) can be done in several ways. One method finds (A.B) first and then we add MSBs with LSB using an end-around-carry (EAC) adder. For the same example above, we have
5×13 mod 15 = 65 mod 15 = (0100 0001)2 mod 15 = (1+4) mod 15 = 5.
We can use the EAC adder of Figure 2(b) on the product (A.B). The multiplication time is sum of normal multiplication time followed by modulo 15 reduction time.

In the case of modulus (2n+1), we need to subtract MSBs of the product (A.B) from LSBs of the product and if the result is negative we need to add (2n+1). As an illustration, consider (5×13) mod 17 = (0100 0001) mod 17 = (1-4) mod 17 = 14.