Xem mẫu
Chapter 14: Redundant Arithmetic
Keshab K. Parhi
• A non-redundant radix-r number has digits from the set{0, 1, … , r - 1} and all numbers can be represented in a unique way.
• A radix-r redundant signed-digit number system is based on digit set S º {-b, -(b - 1), … , -1, 0, 1, … ,a}, where, 1 £ b, a £ r - 1.
• The digit set S contains more than r values Þ multiple representations for any number in signed digit format. Hence, the name redundant.
• A symmetric signed digit has a = b.
• Carry-free addition is an attractive property of redundant signed-digit numbers. This allows most significant digit (msd) first redundant arithmetic, also called on-line arithmetic.
Chap. 14 2
Redundant Number Representations
• A symmetric signed-digit representation uses the digit set D = {-a, …, -1, 0, 1, …, a}, where r is the radix and a the largest digit in the set. A number in this representation is written as :
X = xW-1.xW-2.xW-3…x0 = å xW-1-iri
The sign of the number is given by the sign of the most significant non-zero digit.
Digit Set D Incomplete
Complete but non-redundant
Redundant Minimally redundant
Maximally redundant
Over-redundant
a
< (r – 1)/2 = (r – 1)/2 ³ ér/2ù = ér/2ù = r – 1
> r - 1
Redundancy Factor r < ½ = ½ > ½
> ½ and < 1 = 1
> 1
Chap. 14 3
Hybrid Radix-2 Addition S<2.1> = X<2.1> + Y
where, X = x .x x …x , Y= y .y y …y . The addition is carried out in two steps :
1. The 1st step is carried out in parallel for all the bit positions. An intermediate sum p = x + y is computed, which lies in the range {1, 0, 1, 2}. The addition is expressed as:
xi + yi = 2ti + ui,
where t is the transfer digit and has value 0 or 1, and is denoted as t+; u is the interim sum and has value either 1 or 0 and is denoted as -ui-. t-1 is assigned the value of 0.
2. The sum digits si are formed as follows: si = ti-1+ - ui-
Chap. 14 4
Digit xi yi
pi = xi + yi ui ti
si = u + ti-1
Radix 2 Digit Set {1, 0, 1} {0, 1}
{1, 0, 1, 2} {1, 0} {0, 1} {1, 0, 1}
Binary Code xi+ - xi-yi+
2ti + u -ui-
ti+ si+ - si-
Eight-digit hybrid radix-2 adder
Chap. 14 5
...
- tailieumienphi.vn
nguon tai.lieu . vn