بسم الله الرحمن الرحيم

Signed-Digit Number Systems:

Main features:

Ø      Radix, r³ 2

Ø      Digit set:

Ø      Rule:

Properties of Signed-Digit Number System:

1. Easy to negate numbers
2. No separate sign digit
3. SD has positive and negative digits (no need for a rule to represent negative numbers)
4. No carry propagation for addition, which means addition is fast
5. SD numbers are inherently redundant

Example (1):

Let: radix: r =10, number of digits: n =2, and a =9 (max.)

*        So the digit set is

*        Range (R): 

*        Number of representation: R=99*2+1= 199 numbers

*        Possible number of combination: P= 19*19=361

*        Representation of 0 (or 10) is unique

*        Out of 361 representations, 361-199=162 are redundant (81% redundancy)

*        Each number in range has at most two representations

Reducing the redundancy:

When we decrease a, the redundancy is reduced. See below example.

Example (2):

Let r =10, so the range of a is 6 £ a £ 9

Now, If a =6 and n =2

*        Range (R): 

*        Number of representation: R=66*2+1= 133 numbers

*        Possible number of combination: P= 13*13=169

*        Representation of 0 (or 10) is unique

*        Out of 169 representations, 169-133=36 are redundant (27% redundancy)

Addition of SD numbers:

Addition time is independent of the length of operands since there is no carry propagation chain. The carry bits are shifted to the left to simplify execution of second step.

Addition Rule:

Step 1: Compute interim sum u_i  and carry digit c_i

u_i = x_i + y_i - r c_i      ,where

Step 2: Calculate the final sum s_i = u_i + c_i-1

Example (3):

Let: r=10 &  a=6

x_i= -6,...,0,1,...,6  

Step 1: u_i =( x_i+y_i )-10 c_i

If:

x= 3645

y= 1456

Therefore x+y =

Converting Representations:

Convert decimal to SD:

The addition rule can be used for converting a decimal number to SD form by considering each digit as the sum x_i+y_i above:

Example (4):

Convert decimal 6849 to SD number:

Converting SD to decimal: subtract digits with negative weight from digits with positive weight.

Example (5):

converting  to decimal       

Number Systems

    - Conventional Number System

         >Properties

         >Binary, Decimal, Hexadecimal

         >Number Base Conversion

    - Unconventional Number System

         >Roman Number System

         >Signed Digit Number System

         >Binary SD Number System

Fast Addition

    - Half and Full Adders

    - Ripple Carry Adder

    - Carry Look-Ahead Adders

Fast Multiplication

    - Carry Save Adders

    - Additive & Non-additive Multiplier

    - Counters