Transcript online_tut

Redundant Number
Systems and
Online Arithmetic
Sridhar Rajagopal
June 16, 2000
Outline
• Introduction to RNS
• Introduction to Online
• An example comparison
• Why are we doing this ?
Redundant Number Systems
• Conventional Systems ( 0.34578 r=10)
– radix r has r possible digits
• Redundant (0.34578,0.35578,…. r=10)
– >r possible digits.
• Limit carry propagation
• Totally Parallel Addition/Subtraction
Contd..
• Radix r can have q values
– r+2 <= q <= 2r-1 (Say why)
• Addition of bit I depends on I and I+1
only
• Transfer Digit ti = -1,0,1
• Interim Sum |wi| <= r-2 (Hence, r >2)
• wmax - wmin >= r-1 (Tell why)
Contd..
• For r >4, more than 1 set of digit values
– ceil{(r-1)/2} <= a <= r-1 (Say why)
– min/max redundancy
– {-wmin-1,…0,…,wmax+1}
Conversion To a RNS
• Z = +/- xi r-i ; x  {0,..r-1}
• 1. Choose ‘a’ - the amt. Of redundancy
• 2. If Z <0,interpret each digit as ‘-’
• 3. Wi = xi - r*ti-1 ; ti-1  f(xi)
• 4. Form zi = wi + ti
Conversion from a RNS
• Sum of 2 numbers,positive and negative
– fed to an adder
• Serial manner, from the LSB.
Multi-operand Addition
• Can be done totally parallel
• |ti| > 1 allowed , r large
• n <= floor(r/2) (Tell why)
• r =10, 5 digits can be added in parallel
Binary Radix Addition
• Two-transfer addition; I,I+1,I+2
• can use for r = 2
• decreased redundancy (r+1)
• More complicated addition
• Greater transfer digit propagation
Example
• R = 10, a = 6,(w=5), t = -1,0,1
• 0.76486 + (-0.39471) = 0.37015 (usual)
• 1.36514 + 0.40531 = 0.43025 (redund)
• Show conversion, addition, backconversion
Online Arithmetic
• Pipelined Bit-Serial Arithmetic
• MSDF computations
• Successive computations as soon as 
inputs available ( = 1-4, typically)
• Advantages of MSDF online (Tell)