RNS representation and arithmetic Consider the lowcost RNS s

RNS representation and arithmetic Consider the low-cost RNS system RNS(32|31|15|7) derived in Section 4.2. Represent the numbers x = 168 and y = -23 in this RNS. Compute x + y, x - y, x times y, checking the results via decimal arithmetic. Knowing that x is a multiple of 7, divide it by 7 in the RNS. Compare the numbers (4 | 3 | 2 | 1)_RNS and (1 | 2 | 3 | 4)RNs using mixed-radix conversion. Convert the numbers (4 | 3 | 2 | 1)_RNS and (1 | 2 | 3 | 4)_RNS to decimal. What is the representational efficiency of this RNS compared to standard binary?

Solution

a) RNS given is RNS(32|31|15|7)

To find RNS representation of x = 168, divide 168 by each moduli of RNS and store the remainder value

168%32 = 8

168%31 = 13

168%15 = 3

168%7 = 0

x = 168 = (8|13|3|0)_RNS

To find RNS representation of y = - 23, find the RNS representation of 23 first

23%32 = 23

23%31 = 23

23%15 = 8

23%7 = 2

23 = (23|23|8|2)_RNS

To find -23, Subtract the given number from moduli of RNS

-23 = (32-23|31-23|15-8|7-2)_RNS = (9|8|7|5)_RNS

_b) x = 168 = (8|13|3|0)_RNS y = -23 = (9|8|7|5)_RNS

x + y (RNS) = (8+19|13+8|3+7|0+5) = (27|21|10|5)_RNS

Please note: For subtraction, every moduli will be added parallely. In case of overflow, result % rns moduli will be used.

x+y = 168 - 23 = 145 = (27|21|10|5)_RNS

x-y (RNS) = (32+8-9|13-8|15+3-7|7+0-5) = (31|5|11|2)_RNS

Please note: For subtraction, every moduli will be subtracted parallely. If subtrahend is larger than minuend, then the moduli of RNS will get added to minuend.

x-y = 168 - -23 = 191 = (31|5|11|2)_RNS