DIGITAL CIRCUITS

Week-5, Lecture-1
Boolean Algebra

Sneh Saurabh
29th August, 2018
Digital Circuits: Announcements/Revision

Digital Circuits: S. Saurabh Introduction 2

 Digital Circuits

Number System

Digital Circuits: S. Saurabh Number System 3

Decimal Number System: Base/Radix 10

 In decimal system {0, 1, 2, … , 9} digits are used

 A number is represented in general by a series of coefficients

 The position of the coefficients determines the power of 10 that the coefficient must be
multiplied
 𝑎4 𝑎3 𝑎2 𝑎1 𝑎0 . 𝑎−1 𝑎−2
= 𝑎4 × 104 + 𝑎3 × 103 + 𝑎2 × 102 + 𝑎1 × 101 + 𝑎0 × 100 + 𝑎−1 × 10−1 + 𝑎−2 × 10−2
 Example: 72451.29
= 7 × 104 + 2 × 103 + 4 × 102 + 5 × 101 + 1 × 100 + 2 × 10−1 + 9 × 10−2

 The decimal number system is said to be of base or radix 10

 Because it uses 10 digits {0, 1, 2, … , 9} and coefficients are multiplied by power of 10

Digital Circuits: S. Saurabh Number System 4

Binary system or Base-2 system or Radix-2 system

 In binary system {0, 1} digits are used

 The position of the coefficients determines the power of 2 that the coefficient must be multiplied
 𝑎3 𝑎2 𝑎1 𝑎0 . 𝑎−1 𝑎−2
= 𝑎3 × 23 + 𝑎2 × 22 + 𝑎1 × 21 + 𝑎0 × 20 + 𝑎−1 × 2−1 + 𝑎−2 × 2−2
 Example: (1101.11)2
= (1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 + 1 × 2−1 + 1 × 2−2 )10
= (8 + 4 + 1 + 0.5 + 0.25)10 = (13.75)10

Digital Circuits: S. Saurabh Number System 5

Base-𝑟 or Radix-𝑟 system
 In base-r system {0, 1, 2, … , (𝑟 − 1)} digits are used. Beyond 9, {𝐴, 𝐵, 𝐶, … } symbols are used

 Example, digits for various base system:

 𝐵𝑎𝑠𝑒 − 4: {0, 1, 2, 3}
 𝐵𝑎𝑠𝑒 − 5: {0, 1, 2, 3, 4}
 𝐵𝑎𝑠𝑒 − 8 (𝑂𝑐𝑡𝑎𝑙): {0, 1, 2, 3, 4, 5, 6, 7}
 𝐵𝑎𝑠𝑒 − 16 (𝐻𝑒𝑥𝑎𝑑𝑒𝑐𝑖𝑚𝑎𝑙): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹}

 The position of the coefficients determines the power of 𝑟 that the coefficient must be multiplied
 (𝑎4 𝑎3 𝑎2 𝑎1 𝑎0 . 𝑎−1 𝑎−2 )𝑟
= 𝑎4 × 𝑟 4 + 𝑎3 × 𝑟 3 + 𝑎2 × 𝑟 2 + 𝑎1 × 𝑟1 + 𝑎0 × 𝑟 0 + 𝑎−1 × 𝑟 −1 + 𝑎−2 × 𝑟 −2
 Example: (213.2)8
= (2 × 82 + 1 × 81 + 3 × 80 + 2 × 8−1 )10 = (128 + 8 + 3 + 2 × 0.125)10 = (139.25)10

Digital Circuits: S. Saurabh Number System 6

Hexadecimal to decimal

Problem:

Convert the number (𝐹𝐴)16 to decimal.

Solution:
(𝐹𝐴)16 = (15 × 161 + 10 × 160 )10 = (250)10

Digital Circuits: S. Saurabh Number System 7

Conversion of a decimal number to base-r
 If a decimal number contains both the integer portion and the fraction part, then both these
parts are treated differently

 Conversion of integer is done and conversion of fraction is done, and both results are
combined

Integer part

Divide the number and all successive quotients by 𝑟 and accumulate the remainders.

Digital Circuits: S. Saurabh Number System 8

Conversion of a decimal number to binary

Problem: Integer Remainder

Convert the decimal number 153 into 153

binary (𝑟 = 2) 76 1
38 0
19 0
Answer:
(153)10 = (10011001)2 9 1
4 1
2 0
1 0
0 1

Digital Circuits: S. Saurabh Number System 9

Conversion of a decimal number to Octal/Hexadecimal
Problem: Integer Remainder
153
Convert the decimal number 153 into octal (𝑟 = 8)
19 1
Answer: 2 3
(153)10 = (231)8
0 2

Problem: Integer Remainder

Convert the decimal number 153 into hexadecimal 153

(𝑟 = 16) 9 9
0 9
Answer:
(153)10 = (99)16

Digital Circuits: S. Saurabh Number System 10

Unsigned number representation

Digital Circuits: S. Saurabh Number System 11

Conversion of binary to Octal/Hexadecimal
Problem: Problem:

Convert the binary number (10011001)2 Convert the binary number (10011001)2 into
into octal (𝑟 = 8) hexadecimal (𝑟 = 16)

 Form a group of three bits starting from

right.  Form a group of four bits starting from right.

 Replace each group with corresponding  Replace each group with corresponding
octal digit hexadecimal digit

 Add extra zeroes on the left of MSB to  Add extra zeroes on the left of MSB to make
make the number of digits as multiple of the number of digits as multiple of four
three
(1001 1001)2
(010 011 001)2
= (9 9)16
= (2 3 1)8

Digital Circuits: S. Saurabh Number System 12

Conversion of fraction in decimal to base-r
Fraction part.

Multiply the fractional part by 𝑟 and accumulate the integer portion

Problem:
Integer Fraction
Convert the decimal number 0.6875 × 2 1 0.375
(0.6875)10 into binary (𝑟 = 2)
0.375 × 2 0 0.75
0.75 × 2 1 0.5
Answer:
(0.6875)10 = (0.1011)2 0.5 × 2 1 0

Problem:
Answer:
Convert the decimal number (153.6875)10 = (10011001.1011)2
(153.6875)10 into binary (𝑟 = 2)

Digital Circuits: S. Saurabh Number System 13

 Digital Circuits

Arithmetic Operations

Digital Circuits: S. Saurabh Number System 14

Addition of unsigned numbers: 2 bits
 Addition of binary numbers is similar to decimal numbers, except that individual digits can take
only 0 and 1

A circuit which implements

the addition of only two
bits is known as Half
Adder (HA)

Digital Circuits: S. Saurabh Number System 15

Addition of unsigned numbers: Multiple bits
 Each pair is added, similar to two-bits

 At bit position 𝑖, carry-in from bit position (𝑖 − 1) can come

 For each bit position 𝑖, the addition

involves bits 𝑥𝑖 and 𝑦𝑖 and carry-in 𝑐𝑖
{except for the first bit}

 For each bit position sum 𝑠𝑖 and

carry for the next stage 𝑐𝑖+1 are
computed

Digital Circuits: S. Saurabh Number System 16

Addition of unsigned numbers: Full Adder
𝑠𝑖 = 𝑐𝑖 ′𝑥𝑖′ 𝑦𝑖 + 𝑐𝑖 ′𝑥𝑖 𝑦𝑖′ + 𝑐𝑖 𝑥𝑖 ′𝑦𝑖 ′ + 𝑐𝑖 𝑥𝑖 𝑦𝑖

= 𝑐𝑖 ′(𝑥𝑖′ 𝑦𝑖 + 𝑥𝑖 𝑦𝑖′ ) + 𝑐𝑖 (𝑥𝑖 ′𝑦𝑖 ′ + 𝑥𝑖 𝑦𝑖 )

= 𝑐𝑖 ′(𝑥𝑖 ⊕ 𝑦𝑖 ) + 𝑐𝑖 (𝑥𝑖 ⊕ 𝑦𝑖 )′

= 𝑥𝑖 ⊕ 𝑦𝑖 ⊕ 𝑐𝑖

𝑐𝑖+1 = 𝑥𝑖 𝑦𝑖 + 𝑥𝑖 𝑐𝑖 + 𝑦𝑖 𝑐𝑖
Full Adder Circuit

Digital Circuits: S. Saurabh Number System 17

N-bit adder

 To add two unsigned numbers, circuit is designed similar to what is done in hand-calculation

 Least Significant Bit (LSB) is on the right and Most Significant Bit (MSB) is on the left

 Bits are added starting from right using Full Adders

 Carry bits propagate from right to left

Digital Circuits: S. Saurabh Number System 18
 Digital Circuits

Signed Numbers

Digital Circuits: S. Saurabh Number System 19

Signed Number Representation in Binary
 Positive numbers are represented by positional number system (as explained)

 Negative numbers can be represented in three ways:

1. Sign-and-magnitude
2. 1’s complement
3. 2’s complement

 Sign is represented by the leftmost bit

Digital Circuits: S. Saurabh Number System 20