Digital Circuits

Number System

Decimal Number System:
0             ->   9
10           ->         99
100         ->         999
1000       ->         9999

Binary Number System:
1 bit :  0         -> 1       (1)
2 bits:  10   -> 11      (3)
3 bits:  100 -> 111    (7)
4 bits:  1000 -> 1111  (15)

[Q.] Convert 010101101 from Binary to Decimal Number
-> 128 + 32 + 8 + 4 + 1
 = 173

Octal Number System

•  Base 8 number system
• Allowed symbols are 0, 1, 2, 3, 4, 5, 6, 7

e.g.,
(133) = 1*64 + 3*8 + 3

Hexadecimal Number System

• Base 16
• Symbols are: 0-9, A(10), B(11), C(12), D(13), E(14), F(15)

e.g.,
(B013) -> 4096*11 + 256*0 + 16*1 + 1*3


Representing Negative Integers in Binary:

Modulo Arithmetic:
mod 2^N arithmetic
 - N btis

N = 4 : mod-16 arithmetic

Multiply 51 and 97 in modulo-16 arithmetic
51 --> 3
97 --> 1
          3

On 32-bit machines we are indirectly doing mod 2^32 arithmetic. But, since 2^32 is very large, in practical cases we generally don't observe this. But, its observed in cases where there is some overflow.

Ways of Expressing Negative Numbers:
(1.) Sign magnitude
(2.) One's complement
(3.) Two's complement
(4.) Offset binary

They are suited for different purposes.For example,
Sign magnitude     : for multiplication
One's complement : quick conversion between negative and positive numbers.
Two's complement : Addition/subtraction
Offset binary          : converting analog to digital numbers

(1.) Sign magnitude:

• Least Significant Bit reserved for sign.
• 1: Negative,  0: Positive

e.g., In 8-bit sign magnitude representation
20 : 00010100
-20 : 10010100
So in N-bit, we can represent (-(2^(N-1)-1) to (2^(N-1)-1))
8-bit: -127 to 127

(2.) One's complement:

• Positive numbers : same as sign magnitude representation
• Negative numbers : 1111 1111 - abs(+ve representation)  (Equivalent to flipping all bits of +ve representation)
• Range: -127 to +127 for 8-bits(+0 = -0). 0 counted twice. So only 255 numbers can be represented

e.g.,
+9 : 0000 1001
-9  : 1111 1111 - 0000 1001 = 1111 0110

(3.) Two's complement:

• Positive numbers : same as sign magnitude representation
• Negative numbers : find 1's complement and add 1 to it
• Double counting problem of 0 not there => 256 different numbers represented.

e.g.,
+9 : 0000 1001
-9  : 1111 0110 + 0000 0001 = 1111 0111

(4.) Offset Binary:

• (unsigned representation) - (offset), where offset = 2^(N-1)
• Offset binary <----flip MSB----> 2's Complement

e.g., for 3-bit
binary code  : 000 001 010 011 100 101 110 111
unsigned       : 0     1     2     3     4     5     6     7
Offset binary:-4    -3    -2    -1    0    1      2     3

Addition:
0001 0110
0100 1011
0110 0001

0001 1111
0100 1011
0110 1010

Subtraction:
0110 1001
0011 1111
0010 1010

Multiplication:

• If we multiply 2 N-bit numbers, we need 2N-bits(unsigned numbers)
• For signed bit : 2N-1 bits required for multiplication of 2 N-bit numbers.
• for 2's complement : 2N bits required

e.g,
0110
1001 
0110
       0000
      0000
     0110    
    0110110
 
Addition, multiplication --> take 1-clock cycle
Divison -> N clock cycles (n->number of bits)
Divison takes much more time than addition, multiplication.

Signed Addition/Subtraction:

2's complement:
sum = num1 + num2

1001 1001   (-103)
0011 0011     (51)
1100 1100    (-52)

Diff = num1 - num2
Diff = num1 + (-num2)

-num2 = (flip all bits of num2) + 0000...000001(=> Carry 1) for N bits.

For subtraction, we just find the -ve of num2, and then add the two.
0001 0110  (22)
0100 1001  (73)
 1011 0111  (-73)
----------

   0111 1111   (127)
   0111 1111   (127)
   1111 1110    (-2)
 This phenomenon is called Overflow.(Adding 2 positive numbers gives negative and vice-versa)
____________________________________________________________________

Introduction to Gates

NOT : A--|>o--A'
AND : C = AB
OR  : C = A+B
NAND: The most popular gate in Digital circuits.
NOR : C = (A+B)'
XOR :
XNOR:

De Morgan's law:
---------------
(A+B)' = A'B'
(AB)'  = A'+B'