UNIT - I

BOOLEAN ALGEBRA AND LOGIC GATES

 Number System
S.no Type Base Symbols Example 27
1 Binary 2 0,1 11011
2 Decimal 10 0 to 9 27
3 Octal 8 0 to 7 33
4 Hexadecimal 16 0 to 9, A to F 1B

Hexadecimal is used to represent long strings of bits

Like address, instruction, data in a digital system

When human need to do direct communication with computer then they
use octal or hexadecimal numbers as they use less number of digits than
binary

Eg : (111111111111)2 = (7777)8 =( FFF)16
 Number System

• Binary digits are called as bits

• 4 bits Nibble,
• 8 bits bytes (used to represent one keyboard character)
• 16/32/64 bits word
– Hexadecimal = (B65F)16
– Decimal = (46,687)10
– Binary = (1011011001011111)2
– Octal = (133137)8
 Number System

• Let the number be as shown below

• aj : coefficient
• j : position
• r : Base
• aj range from 0 to (r-1)
• a5 a4 a3 a2 a1 a0. a-1 a-2 a-3
• Then the decimal equivalent is
• a5 * r5 + a4 * r4 + a3 * r3 + a2 * r2 + a1 * r1 + a0 * r0 + a-1*r-1 + a-2* r-2 + a-3* r-3

• Eg: 1011 = 1* 23 + 0 * 22 + 1* 21 + 1 *2
= 8 + 0 + 2 +1
= 11
 Number System

Decimal numbers
◦ Decimal digits: (0,1,2,3,4,5,6,7,8,9)
 7392 =7000+300+90+2
 =7*1000+3*100+9*10+2
 =7*103 + 3*102 +9 *101 +2 *100
◦ 97654.35 = 9x104 + 7x103 + 6x102 + 5x101 + 4x100 + 3x10-1 + 5x10-2
◦ Formal notation -> (97654.35)10
◦ Here 10 is the base or radix
 Number System

Octal numbers

Octal digits: (0,1,2,3,4,5,6,7)
◦ (4536)8 = 4x83 + 5x82 + 3x81 + 6x80 = (1362)10
◦ (465.27)8 = 4x82 + 6x81 + 5x80 + 2x8-1 + 7x8-2

Octal numbers don’t use digits 8 or 9

Hexadecimal numbers

Hexadecimal digits: (0 to 9, A to F)

(D63FA)16 =13*164 + 6*163 + 3*162 +15*161 +10*160
= (877562)10
 Number System

Binary numbers

Binary digits (bits): 0 and 1
◦ (1011)2 = 1x23 + 0x22 + 1x21 + 1x20 = (11)10
◦ (110.10)2 = 1x22 + 1x21 + 0x20 + 1x2-1 + 0x2-2 = (6.5)10

Groups of eight bits are called a byte
◦ (11001001) 2

Groups of four bits are called a nibble.
◦ (1101) 2
Number System
Why Use Binary Numbers?
° Easy to represent 0 and 1 using
electrical values.
° Possible to tolerate noise.
° Easy to transmit data
° Easy to build binary circuits.

1 AND Gate
0
0
 Number System
Conversion Between Number Bases

Group 3 bits
Octal(base 8)

Decimal(base 10) Binary(base 2)

Group 4 bits
Hexadecimal
(base16)
 Number System
Conversion
Decimal :
Binary - divide by 2
Octal - divide by 8
Hexadecimal - divide by 16
Binary
Decimal - Multiply by 2
Octal - combine 3 bits
Hexadecimal - combine 4bits
Octal
Binary – represent each element in 3 bit
Decimal - Multiply by 8
Hexadecimal – convert to binary then group by 4 bit
Hexadecimal
Binary – represent each element in 4 bits
Decimal – Multiply by 16
Octal - convert to binary then group by 3 bit
 Number System

Decimal : Binary - Decimal :Octal - Decimal : Hexadecimal -

divide by 2 divide by 8 divide by 16
(20)10= (?)2 (48)10= (?)8 (1256)10= (?)16

2 20
8 48 16 1256
2 10 0
8 6 0 16 78 8
2 5 0
16 4 1
2 2 1 (48)10= (60)8 4
2 1 0
(1256)10= (4E8)16

(20)10= (10100)2
 Number System

Decimal : Binary Decimal : Hexadecimal -

(20.6875)10= (?)2 Decimal :Octal - (1256.513)10= (?)16
(48.513)10= (?)8
16 1256
2 20
8 48 16 78 8
2 10 0
8 6 0 16 4 1
2 5 0 4
2 2 1 0.513 *8=4.104=4
2 1 0 0.104*8 =0.832 =0 0.513*16=8.208 =8
0.832*8=6.656 =6 0.208*16=3.328 =3
0.6875*2 =1 .3750 =1 0.656*8=5.248 =5 0.328*16=5.248 =5
0.3750 *2=0.7500 =0 0.248*16=3.968 =3
0.7500 * 2=1.5000 =1 (48.513)10=(60.4065)8 0.968*16=15.488= F
0.5000*2 = 1.0000 =1
(1256.513)10= (4E8.8353F)16
(20.6875)10= (10100.1011)2
 Number System
Binary: Decimal - Multiply by 2

Binary: Octal - combine 3 bits

1 0 1 0 0 (110000)2 = 110 000
24 23 22 21 20 = 6 0

1*16 0*8 1*4 0*2 0*1 (110000)2 = (60)8

16 0 4 0 0
20

(10100)2 = (20)10

Binary: Hexadecimal - combine 4bits

(010011101000)2 = 0100 1110 1000
= 4 E 8
(010011101000)2 =(4E8)16
 Number System
Binary: Decimal -

1 0 1 0 0 1 0 1 1
24 23 22 21 20 2-1 2-2 2-3 2-4

1*16 0*8 1*4 0*2 0*1 1/2 1/4 1/8 1/16

16 0 4 0 0 0.5 0 0.125 0.0625

20 0.6875

(10100.1011)2 = (20.6875)10
 Number System
Binary: Octal
(110000.1011)2 = 110 000. 101 100
= 6 0 . 5 4

(110000.1011)2 = (60.54)8

Binary: Hexadecimal

(010011101000.1011)2 = 0100 1110 1000. 1011

= 4 E 8 . B

(010011101000)2 =(4E8.B)16
 Number System
Octal: Decimal - Octal : Hexadecimal -
Octal : Binary -
Multiply by 8 convert to binary then
each element in 3 bit
group by 4 bit
6 110 6 0
81 80 (60)8= (110000)2
0 000 = 11 0000
6*8 0*8 = 3 0
48 0
(60)8= (30)16
(60)8= (110000)2 48

(60)8= (48)10
 Number System
Octal: Decimal
Octal : Binary -
6 0 4 0 6 5
6 110 81 80 8-1 8-2 8-3 8-4
0 000
5 101 6*8 0*8 4/8 0/64 6/512 5/4096
4 100 48 0 0.5 0 0.011718 0.00122
48 0.5129
(60.54)8= (110000.101100)2
(60.4065)8= (48.5129)10

Octal : Hexadecimal

(60.4065)8= (110000.100000110101)2
= 11 0000.1000 0110 1010
= 3 0 . 8 6 A

(60.4065)8= (30.86A)16
 Number System
Hexadecimal : Binary
Hexadecimal : Decimal Hexadecimal : Octal - -
- – represent each
- Multiply by 16 convert to binary then
element in 4 bits
group by 3 bit
4 0100
(4E8)16 =
E 1110 4 E 8
(010 011 101 000)2
8 1000 162 161 160 = 2 3 5 0

(4E8)16 = 4*256 14* 8*1

16 (4E8)16 = (2350)8
(010011101000)2
1024 224 8
1256

(4E8)16 =(1256)10
 Number System
Hexadecimal : Decimal
Hexadecimal : Binary
4 0100 4 E 8 B
E 1110 162 161 160 16-1
8 1000 4*256 14*16 8*1 11/16
B 1011 1024 224 8 0.687
5

(4E8.B)16 = 1256 0.687

(010011101000.1011)2 5

(4E8.B)16 =(1256.6875)10

Hexadecimal : Octal - - (4E8.B)16 = (010 011 101 000. 101 100)2

= 2 3 5 0. 5 4

(4E8.B)16 = (2350.54)8
 Number System
n 2n n 2n
0 20=1 8 28=256
1 21=2
9 29=512

2 22=4
10 210=1024

3 23=8
11 211=2048

4 24=16
12 212=4096

5 25=32
20 220=1M Mega

6 26=64
30 230=1G Giga

7 27=128 Tera
40 240=1T
Number System
 Binary Addition

Binary addition is very simple.

This is best shown in an example of adding two binary numbers…

1 1 1 1 1
1 carries
1
1 1 1 0 1 Augend
+ 1 0 1 1 1 Addend
---------------------
1 0 1 0 1 0 0 Sum
 Binary Subtraction
° We can also perform subtraction (with borrows in p lace of carries).
° Let’s subtract (10111) 2 from (1001101)2…

1 10 borrows
0 10 10 0 0 10
Minuend
1 0
0 1 1 0 1
- 1 0 1 1 1 Subtrahend
------------------------
Difference
1 1 0 1 1 0
 Binary Multiplication

Binary multiplication is much the same as decimal multiplication, except
that the multiplication operations are much simpler…

1
0 1 1 1 Multiplicand
X 1 0 1 0 Multiplier
-----------------------
0 0 0 0 0
1 0 1 1 1
0 0 0 0 0
1 0 1 1 1
-----------------------
1 1 1 0 0 1 1 0 Product
 Complements
• Used to simplifying the subtraction
• Simplification lead to simpler and less expensive circuits
to implement

Radix / Base r 2 10
Radix complement r 2 10
Diminished radix complement r-1 1 9
 Complements
999999
– 9’s complement -546700
• Subtract each digit from 9
453299
– 10’s complement
• Subtract each digit from 9 and add 1 to the result
• Subtract the first non zero from 10 and all others from 9
• Count the number of digit and subtract from 10n

999999
-546700 9 9 9 10 - -
1000000
453299 -5 4 6 7 0 0
- 546700
+ 1 453 3 00
453300
453300
 Complements
– 1’s complement 1111111
– Find the inverse of the given number 1011000

0100111
– 2’s complement
– Find the inverse of the given number and add 1 to the result
– Keep the first non zero as such and then complement the others
– Count the number of digit and subtract from 2n

1111111
1011000 1112 - - -
10000000
0100111 -1 0 1 1 0 0 0
-1011000
+ 1 0 101000
0101000
0101000
 Subtraction with r’s Complement

• The subtraction of two positive numbers (M - N), both of base r, may

be done follows:
1. Add the minuend M to the r’s complement of the subtrahend N.
2. Insert the result obtained in step 1 for an end carry:
(a). If an end carry occurs, discard it.
(b). If an end carry does not occur, take the r’s complement of the
number obtained in the step 1 and place a negative sign in front.
 Subtraction with Complement
• 52532 – 3250

Radix 52532 3250

R-1 47467 96749
R 47468 96750

+ 52532
9’s comp 96749 + 52532
149281 10’s comp 96750
(carry Positive , 9’s comp so add
149282
carry) 1
(carry Positive , 10’s comp so
49282
discard carry)
49282
 Subtraction with Complement
• 3250 - 52532
Radix 52532 3250
R-1 47467 96749
R 47468 96750

+ 03250 + 03250
9’s comp 47467 10’s comp 47468
50717 50718
(No carry , negative (No carry , negative
Find 9’s complement ) Find 10’s complement )
- 49282 -49282
 Subtraction with Complement
• 1010100 – 1000011
Radix 1010100 1000011
R-1 0101011 0111100
R 0101100 0111101

+ 1010100
1’s comp 0111100

10010000 + 1010100
(carry Positive , 1’s comp so add carry) 2’s comp 0111101
1
10010001
0010001
(carry Positive , 2’s comp so discard
carry)

0010001
Subtraction with Complement
• 1000011 – 1010100
Radix 1010100 1000011
R-1 0101011 0111100
R 0101100 0111101

+1000011 +1000011
1’s comp 0101011 2’s comp 0101100
1101110
1101111
(No carry , negative
Find 1’s complement ) (No carry , negative
-0010001 Find 2’s complement )
-0010001
 Signed Binary Numbers

Sign Magnitude
bit

Sign bit : 0 - Negative number

1 - Positive Number

Number : 10101
Signed: 10101 = -5
Unsigned : 10101 = 21
 Signed Binary Numbers

• Representation:
Signed Binary Numbers

September 5, 2003
 Signed Binary Numbers
■ Arithmetic Addition

signed-magnitude Addition

The addition of two numbers in the signed-magnitude system follows the rules
of ordinary arithmetic.

If the signs are the same, we add the two magnitudes and give the sum the
common sign.

If the signs are different, we subtract the smaller magnitude from the larger
and give the difference the sign of the larger magnitude.

♣ The addition of two signed binary numbers with negative numbers

represented in signed-2's-complement form is obtained from the addition of
the two numbers, including their sign bits.
♣ A carry out of the sign-bit position is discarded.
 Signed Binary Numbers
■ Arithmetic Addition

♣ Signed-2’s Complement Addition

♣ The addition of two signed binary numbers with negative numbers
represented in signed-2's-complement form is obtained from the
addition of the two numbers, including their sign bits.
♣ A carry out of the sign-bit position is discarded.
♣ If the sign bit is 1 then find the 2’s complement of the number
 Signed Binary Arithmetic Addition
■ Arithmetic Subtraction

Negative numbers are changed into positive numbers using r’s complement

(+A) –(+B) = (+A) + (-B)

(+A) –(-B) = (+A) + (+B)
 Signed Binary Arithmetic Addition
+6 00000110 6 13

Signed Mag. 00000110 00001101

00001101
+13 -6 -13
+19 00010011 2’s comp 11111010 11110011

+6 00000110
-13 11110011
-6 11111010
-7 11111001 -6 11111010
+13 00001101
sign bit 1 so find 2’s comp. -13 11110011
+7 100000111
-19 111101101
Discard carry, sign bit 0
Discard Carry
sign bit 1 so find 2’s comp.
Complete Post class Assignment