Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    Chapter 14: Redundant Arithmetic: Keshab K. Parhi

    Uploaded by

    InJune Yeo
    The document discusses redundant arithmetic in signed digit number systems. Some key points: 1. Redundant number systems use a digit set with more values than the radix, allowing multiple representations of a number. This enables carry-free addition. 2. Hybrid radix systems combine redundant and non-redundant representations to perform addition and subtraction using a minimal number of gates. 3. Maximally and minimally redundant hybrid radix-4 systems are described as examples, including the digit sets, addition algorithms, and cell designs used. 4. Methods for converting between non-redundant and redundant number representations are also covered.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Chapter 14: Redundant Arithmetic: Keshab K. Parhi

    Uploaded by

    InJune Yeo
    40 views21 pages
    The document discusses redundant arithmetic in signed digit number systems. Some key points: 1. Redundant number systems use a digit set with more values than the radix, allowing multiple representations of a number. This enables carry-free addition. 2. Hybrid radix systems combine redundant and non-redundant representations to perform addition and subtraction using a minimal number of gates. 3. Maximally and minimally redundant hybrid radix-4 systems are described as examples, including the digit sets, addition algorithms, and cell designs used. 4. Methods for converting between non-redundant and redundant number representations are also covered.

    Original Title

    Chap 14

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses redundant arithmetic in signed digit number systems. Some key points: 1. Redundant number systems use a digit set with more values than the radix, allowing multiple representations of a number. This enables carry-free addition. 2. Hybrid radix systems combine redundant and non-redundant representations to perform addition and subtraction using a minimal number of gates. 3. Maximally and minimally redundant hybrid radix-4 systems are described as examples, including the digit sets, addition algorithms, and cell designs used. 4. Methods for converting between non-redundant and redundant number representations are also covered.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    40 views21 pages

    Chapter 14: Redundant Arithmetic: Keshab K. Parhi

    Uploaded by

    InJune Yeo
    The document discusses redundant arithmetic in signed digit number systems. Some key points: 1. Redundant number systems use a digit set with more values than the radix, allowing multiple representations of a number. This enables carry-free addition. 2. Hybrid radix systems combine redundant and non-redundant representations to perform addition and subtraction using a minimal number of gates. 3. Maximally and minimally redundant hybrid radix-4 systems are described as examples, including the digit sets, addition algorithms, and cell designs used. 4. Methods for converting between non-redundant and redundant number representations are also covered.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 21

    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 {-, -( - 1), , -1, 0, 1, ,}, where, 1 , 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 = . 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<r.> = {-, , -1, 0, 1, , }, where r is the radix and the largest digit in the set. A number in this representation is written as : X<r. > = xW-1.xW-2.xW-3x0 = xW-1- iri The sign of the number is given by the sign of the most significant non-zero digit. Digit Set D<r.> Incomplete
    Complete but non-redundant

    < (r 1)/2 = (r 1)/2 r/2 = r/2 =r1 >r-1

    Redundancy Factor < = > > and < 1 =1 >1


    3

    Redundant Minimally redundant Maximally redundant Over-redundant


    Chap. 14

    Hybrid Radix-2 Addition S<2.1> = X<2.1> + Y


    where, X<r.> = xW-1.xW-2xW-3x0 , Y = yW-1.yW-2yW-3 y0. 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 pi = xi + yi is computed, which lies in the range {1, 0, 1, 2}. The addition is expressed as: xi + yi = 2ti + ui, where ti is the transfer digit and has value 0 or 1, and is denoted as ti+ ; ui 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

    Digit xi yi ui ti pi = xi + yi

    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 + ui -uiti+

    si = ui + ti-1

    si+ - si-

    Eight-digit hybrid radix-2 adder


    Chap. 14 5

    Digit-serial adder formed by folding

    LSD-first adder

    MSD-first adder

    Chap. 14

    Hybrid Radix-2 Subtraction S<2.1> = X<2.1> - Y


    where, X<r.> = xW-1.xW-2xW-3x0 , Y = yW-1.yW-2yW-3 y0. The addition is carried out in two steps : 1. The 1st step is carried out in parallel for all the bit positions. An intermediate difference pi = xi - yi is computed, which lies in the range {2, 1, 0, 1}. The addition is expressed as: xi - yi = 2ti + ui, where ti is the transfer digit and has value 1 or 0, and is denoted as -ti- ; ui is the interim sum and has value either 0 or 1 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

    Digit xi yi ui ti pi = xi yi

    Radix 2 Digit Set {1, 0, 1} {0, 1} {2, 1, 0, 1} {0, 1} {1, 0} {1, 0, 1}

    Binary Code xi + - xi yi2ti + ui ui+ -ti-

    si = ui + ti-1

    si+ - si-

    Eight-digit hybrid radix-2 subtractor


    Chap. 14 8

    Hybrid Radix-2 Addition/Subtraction

    Hybrid radix-2 adder/subtractor (A/S = 1 for addition and A/S = 0 for subtraction) This is possible if one of the operands is in radix-r complement representation. Hybrid subtraction is carried out by hybrid addition where the 2s complement of the subtrahend is added to the minuend and the carry-out from the most significant Chap. 14 9 position is discarded.

    Signed Binary Digit (SBD) Addition/Subtraction Y<r.> = Y + - Y -, is a signed digit number, where Y+ and Y- are from the digit set {0, 1, , }. A signed digit number is thus subtraction of 2 unsigned conventional numbers. Signed addition is given by: S<r.> = X<r.> + Y<r.> = X<r.> + Y + - Y -, S1<r.> = X<r.> + Y+, S<r.> = S1<r.> - YDigit serial SBD adders can be derived by folding the digit parallel adders in both lsd-first and msdfirst modes. LSD-first adders have zero latency and msd-first adders have latency of 2 clock cycles.
    10

    Chap. 14

    Chap. 14

    (a) Signed binary digit adder/subtractor (b) Definition of the switching box

    11

    Digit serial SBD redundant adders. (a) LSD-first adder (b) msd-first adder
    Chap. 14 12

    Maximally redundant numbers are based on digit set D <4.3>. S<4.3> = X<4.3> - Y4 The first step computes: xi + yi = 4ti + ui Replacing the respective binary codes from the table the following is obtained : (2xi+2 - 2xi-2 + 2yi+2) + xi+ - xi- + yi+ = 4ti+ + 2ui+2 - 2ui-2 - uiA MRHY4A cell consisting of two PPM adders is used to compute the above. Step 2 computes computes si = ti-1 + ui. Replacing si, ui, and ti-1 by corresponding binary codes leads to si+2 = ui+2, si-2 = ui-2, si+=ti-1+ and si- = ui-.

    Maximally Redundant Hybrid Radix-4 Addition (MRHY4A)

    Chap. 14

    13

    Digit xi yi ui ti pi = xi + yi

    Radix 4 Digit Set {3, 2, 1, 0, 1, 2, 3} {0, 1, 2, 3} {3, 2, 1, 0, 1, 2, 3, 4, 5, 6} {3, 2, 1, 0, 1, 2} {0, 1} {3, 2, 1, 0, 1, 2, 3}

    Binary Code 2xi+2 2xi-2 + xi+ - xi2yi+2 + yi+ 4ti + ui ti+

    2ui+2 2ui-2 - ui2si+2 - 2si-2 + si+ - si-

    si = ui + ti-1

    Digit sets involved in Maximally Redundant Hybrid Radix-4 Addition

    Chap. 14

    14

    MRHY4A adder cell

    Four-digit MRHY4A
    Chap. 14 15

    Minimally redundant numbers are based on digit set D<4.2>. S<4.2> = X<4.2> - Y4 The first step computes: xi + yi = 4ti + ui Replacing the respective binary codes from the table the following is obtained : (- 2xi-2 + 2yi+2) + (xi+ + xi++ + yi+) = 4ti+ - 2ui-2 + ui+ A mrHY4A cell consisting of one PPM adder and a full adder is used to compute the above. Step 2 computes computes si = ti-1 + ui. Replacing si, ui, and ti-1 by corresponding binary codes leads to si-2 = ui-2, si++ = ti-1+ and si+ = ui+.

    Minimally Redundant Hybrid Radix-4 Addition (mrHY4A)

    Chap. 14

    16

    Digit xi yi ui ti pi = xi + yi

    Radix 4 Digit Set {2, 1, 0, 1, 2} {0, 1, 2, 3} {2, 1, 0, 1, 2, 3, 4, 5} {2, 1, 0, 1} {0, 1} {2, 1, 0, 1, 2}

    Binary Code 2xi-2 + xi+ + xi++ 2yi+2 + yi+ 4ti + ui ti+

    2ui+2 2ui-2 - ui2si-2 + si+ + si++

    si = ui + ti-1

    Digit sets involved in Minimally Redundant Hybrid Radix-4 Addition

    Chap. 14

    17

    mrHY4A adder cell

    Four-digit mrHY4A
    Chap. 14 18

    Non-redundant to Redundant Conversion Radix-2 Representation : A non-redundant number X = x3.x2.x1.x0 can be converted to a redundant number Y = y3.y2.y1.y0, where each digit yi is encoded as yi+ and yi- as shown below:

    Chap. 14

    19

    Radix-4 representation : radix-4 maximally redundant number: X is a

    radix-4 complement number, whose digits xi are encoded using 2 wires as xi = 2xi+2 + xi+. Its corresponding maximally redundant number Y is encoded using yi = 2yi+2 - 2yi-2 + yi+ - yi-. The sign digit x3 can take values -3, -2, -1 or 0, and is encoded using x3 = -2x3-2 - x3-.

    Chap. 14

    20

    radix-4 minimally redundant number: X is a radix4 complement number, whose digits xi are encoded using 2 wires as xi = 2xi+2 + xi+ . Its corresponding minimally redundant number Y is encoded using yi = -2yi-2 + yi+ + yi++. To convert radix-r number x to redundant number y<r.>, the digits in the range [, r - 1] are encoded using a transfer digit 1 and a corresponding digit xi - r where xi is the ith digit of x. Thus, 2xi+2 + xi+ = 4xi+2 - 2xi+2 + xi+ = yi+1++ - 2yi-2 + yi+

    Chap. 14

    21

    You might also like