Digital Logic Design

Chapter 1
Binary Numbers and Logic Gates
Number system

 Decimal (base 10)

 Weights in powers of 10
 Decimal digits: 0, 1,….9
 Octal (base 8)
 Weights in powers of 8
 Octal digits: 0, 1, 2, 3, 4, 5, 6, 7.
 Hexadecimal (base 16)
 Weights in powers of 16
 Hexadecimal digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
 Binary (base 2)
 Weights in powers of 2
 Binary digits (bits): 0, 1
Decimal Number System
 Base (also called radix) = 10
 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 Digit Position
 Integer & fraction 2 1 0 -1 -2

 Digit Weight 5 1 2 7 4
Position
 Weight = (Base)
 Magnitude 100 10 1 0.1 0.01
 Sum of “Digit x Weight”
5 1 2 7 4
 Formal Notation
500 10 2 0.7 0.04
2 1 0 -1 -2
d2*B +d1*B +d0*B +d-1*B +d-2*B

(512.74)10
Octal Number System
 Base = 8 2 1 0 -1 -2
 8 digits { 0, 1, 2, 3, 4, 5, 6, 7 }
5 1 2 7 4
 Weights
Position
 Weight = (Base) 64 8 1 1/8 1/64

 Magnitude 5 1 2 7 4
 Sum of “Digit x Weight”
2 1 0 -1 -2
 Formal Notation 2 1
5*8 +1 *8 +2 *8 +7 *8 +4 *8
0 -1 -2

=(330.9375)10

(512.74)8
Hexadecimal Number System
 Base = 16
 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
 Weights
Position 1/16 1/256
 Weight = (Base) 256 16 1

 Magnitude 1 E 5 7 A
 Sum of “Digit x Weight”
2 1 0 -1 -2
 Formal Notation 2 1 0 -1 -2
1 *16 +14 *16 +5 *16 +7 *16 +10 *16
=(485.4765625)10

(1E5.7A)16
Binary Number System
 Base = 2
 2 digits { 0, 1 }, called binary digits or “bits”
 Weights
 Weight = (Base)
Position 4 2 1 1/2 1/4

 Magnitude 1 0 1 0 1
 Sum of “Bit x Weight” 2 1 0 -1 -2
 Formal Notation 2 1 0
1*2 +0 *2 +1 *2 +0 *2 +1 *2
-1 -2

 Groups of bits
=(5.25)10

(101.01)2

4 bits = Nibble 1011

8 bits = Byte
11000101
The Power of 2

n 2n n 2n
0 20=1 8 28=256
1 21=2 9 29=512
2 22=4 10 210=1024 Kilo

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 40 240=1T Tera

Binary Addition

 Column Addition

1 1 1 1 1 1
1 1 1 1 0 1 = 61
+ 1 0 1 1 1 = 23

1 0 1 0 1 0 0 = 84

≥ (2)10
Binary Subtraction

 Borrow a “Base” when needed

1 2 = (10)2
0 2 2 0 0 2
1 0 0 1 1 0 1 = 77
− 1 0 1 1 1 = 23

0 1 1 0 1 1 0 = 54
 Try this
1 1 0 0 1 1 0 1 0
− 1 1 1 1 0 0
Binary Multiplication

 Bit by bit

1 0 1 1 1
x 1 0 1 0
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
Number Base Conversions
Evaluate
Magnitude
Octal
(Base 8)

Evaluate
Magnitude
Decimal Binary
(Base 10) (Base 2)

Hexadecimal
(Base 16)
Evaluate
Magnitude
Decimal (Integer) to Binary Conversion

 Divide the number by the ‘Base’ (=2)

 Take the remainder (either 0 or 1) as a coefficient
 Take the quotient and repeat the division

Example: (13)10
Quotient Remainder Coefficient
13 / 2 = 6 1 a0 = 1
6 /2= 3 0 a1 = 0
3 /2= 1 1 a2 = 1
1 /2= 0 1 a3 = 1
Answer: (13)10 = (a3 a2 a1 a0)2 = (1101)2

MSB LSB
Decimal (Fraction) to Binary Conversion

 Multiply the number by the ‘Base’ (=2)

 Take the integer (either 0 or 1) as a coefficient
 Take the resultant fraction and repeat the multiplication

Example: (0.625)10
Integer Fraction Coefficient
0.625 * 2 = 1 . 25 a-1 = 1
0.25 * 2 = 0 . 5 a-2 = 0
0.5 *2= 1 . 0 a-3 = 1
Answer: (0.625)10 = (0.a-1 a-2 a-3)2 = (0.101)2

MSB LSB
Decimal to Octal Conversion
Example: (175)10
Quotient Remainder Coefficient
175 / 8 = 21 7 a0 = 7
21 / 8 = 2 5 a1 = 5
2 /8= 0 2 a2 = 2
Answer: (175)10 = (a2 a1 a0)8 = (257)8

Example: (0.3125)10
Integer Fraction Coefficient
0.3125 * 8 = 2 . 5 a-1 = 2
0.5 *8= 4 . 0 a-2 = 4
Answer: (0.3125)10 = (0.a-1 a-2 a-3)8 = (0.24)8

Try this : convert it to octal (575.6125)10

Binary − Octal Conversion
Octal Binary
 8 = 23
 Each group of 3 bits represents an octal 0 000
digit 1 001

2 010
Assume Zeros
Example: 3 011

( 1 0 1 1 0 . 0 1 )2 4 100

5 101

6 110
( 2 6 . 2 )8 7 111

Works both ways (Binary to Octal & Octal to Binary)

Binary − Hexadecimal Conversion
Hex Binary
 16 = 24 0 0000
1 0001
 Each group of 4 bits represents a 2 0010
hexadecimal digit 3 0011
4 0100
5 0101
Assume Zeros 6 0110
Example: 7 0111
8 1000
( 1 0 1 1 0 . 0 1 )2 9 1001
A 1010
B 1011
C 1100
D 1101
(1 6 . 4 )16 E 1110
F 1111

Works both ways (Binary to Hex & Hex to Binary)

Octal − Hexadecimal Conversion
 Convert to Binary as an intermediate step

Example:
( 2 6 . 2 )8

Assume Zeros Assume Zeros

( 0 1 0 1 1 0 . 0 1 0 )2

(1 6 . 4 )16

Works both ways (Octal to Hex & Hex to Octal)

Decimal, Binary, Octal and Hexadecimal
Decimal Binary Octal Hex
00 0000 00 0
01 0001 01 1
02 0010 02 2
03 0011 03 3
04 0100 04 4
05 0101 05 5
06 0110 06 6
07 0111 07 7
08 1000 10 8
09 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
Signed Binary number
 Unsigned numbers: only non-negative values.
 Signed numbers: include all values (positive and
negative)
 There are 3 common representations for signed
binary numbers:
 1s Complement
 2s Complement

 Sign-and-Magnitude
Sign-and-Magnitude
 Use left-most bit for sign
0 = plus; 1 = minus
 Total range of integers the same
Half of integers positive; half negative
Magnitude of largest integer half as large
 Example using 8 bits:
Unsigned: 1111 1111 = +255
Signed: 0111 1111 = +127
1111 1111 = -127
Note: 2 values for 0:
+0 (0000 0000) and -0 (1000 0000)
Complements(1)
 There are two types of complements for each base-r system: the radix
complement and diminished radix complement.
 1. Diminished Radix Complement - (r-1)’s Complement
 Given a number N in base r having n digits, the (r–1)’s
complement of N is defined as:
(rn –1) – N
 Example for 6-digit decimal numbers:
 9’s complement is (rn – 1)–N = (106–1)–N = 999999–N
 9’s complement of 546700 is 999999–546700 = 453299
 Example for 6-digit binary numbers:
 1’s complement is (rn – 1) – N = (26–1)–N = 111111–N
 1’s complement of 101100 is 111111–101100 = 010011
Complements(2)

 2. Radix Complement

The r's complement of an n-digit number N in base r is defined as

rn – N for N ≠ 0 and as 0 for N = 0. Comparing with the (r  1) 's
complement, we note that the r's complement is obtained by adding 1
to the (r  1) 's complement, since rn – N = [(rn  1) – N] + 1.

 Example: Base-10

The 10's complement of 012398 is 987602

The 10's complement of 246700 is 753300

 Example: Base-2

The 2's complement of 1101100 is 0010100

The 2's complement of 0110111 is 1001001
Complements(3)
 1’s Complement (Diminished Radix Complement)
 All ‘0’s become ‘1’s
 All ‘1’s become ‘0’s

Example (10110000)2
 (01001111)2
 2’s Complement (Radix Complement)
 Take 1’s complement then add 1
Example
Number = (10110000)2
1’s complement  (01001111)2
2’s complement 1 0 1 1 0 0 0 0
01001111
+ 1
01010000
Complements(4)

 Subtraction with Complements

 The subtraction of two n-digit unsigned numbers M – N in base
r can be done as follows:
Complements(5)

 Example
 Using 10's complement, subtract 72532 – 3250.

 Example
 Using 10's complement, subtract 3250 – 72532.

There is no end carry.

Therefore, the answer is – (10's complement of 30718) =  69282.

Complements(6)

 Example
 Given the two binary numbers X = 1010100 and Y = 1000011,
perform the subtraction (a) X – Y ; and (b) Y  X, by using 2's
complement.

There is no end carry.

Therefore, the answer is
Y – X =  (2's complement
of 1101111) =  0010001.
Complements(7)

 Subtraction of unsigned numbers can also be done by means of the (r  1)'s

complement. Remember that the (r  1) 's complement is one less then the r's
complement.
 Example
 Repeat the above Example, but this time using 1's complement.

There is no end carry,

Therefore, the answer is Y –
X =  (1's complement of
1101110) =  0010001.
Binary codes

 If we want to represent a denary/Decimal number in a

binary form, we have more ways than the obvious choice of a

straight conversion.

 There are a dozen or more ways of representing a denary

number, each with their own advantages and disadvantages.

 If the input to a circuit gives rise to a binary code at the

output, we have what we call a 'binary coded decimal' or

BCD.
Binary Coded Decimal
 BCD Code
 A number with k decimal digits will
require 4k bits in BCD.

 Decimal 396 is represented in BCD with

12bits as 0011 1001 0110, with each
group of 4 bits representing one decimal
digit.

 A decimal number in BCD is the same

as its equivalent binary number only
when the number is between 0 and 9.

 The binary combinations 1010 through

1111 are not used and have no meaning
in BCD.
BCD

 Example:
 Consider decimal 185 and its corresponding value in BCD and binary:

 BCD addition
BCD

 Example:
 Consider the addition of 184 + 576 = 760 in BCD:

 Decimal Arithmetic: (+375) + (-240) = +135

ASCII Codes(1)

 American Standard Code for Information Interchange.

 A popular code used to represent information sent as
character-based data.
 It uses 7-bits to represent:
 94 Graphic printing characters.
 34 Non-printing characters.
 Some non-printing characters are used for text format
(e.g. BS = Backspace, CR = carriage return).
 Other non-printing characters are used for record
marking and flow control (e.g. STX and ETX start and
end text areas).
ASCII Codes(2)
 ASCII has some interesting properties:
 Digits 0 to 9 span Hexadecimal values 3016 to 3916
 Upper case A-Z span 4116 to 5A16
 Lower case a-z span 6116 to 7A16
» Lower to upper case translation (and vice versa)
occurs by flipping bit 6.
Alphanumeric Codes
 ASCII Character Code
Error-Detecting Code
 To detect errors in data communication and processing, an
eighth bit is sometimes added to the ASCII character to indicate
its parity.
 A parity bit is an extra bit included with a message to make the
total number of 1's either even or odd.
 Example:
 Consider the following two characters and their even and odd
parity:
Gray Code
 In a Gray code only one bit changes between each pair of
successive code words.
 Unweight (not an arithmetic code).
 Gray code is a reflected code.
 It can be defined recursively using the following rules:
 A 1-bit Gray code has two code words, 0 and 1.

 The first 2n code words of an (n+1)-bit Gray code equal the code words of
an n-bit gray code, written in order with a leading 0 appended.

 The last 2n code words of an (n+1)-bit Gray code equal the code words of
an n-bit gray code, but written in reverse order with a leading 1 appended.
Gray Code
Binary-to-Gray Code Conversion

 Retain most significant bit.

 From left to right, add each adjacent pair of binary code bits to get
the next Gray code bit, discarding carries.
 Example: Convert binary number 10110 to Gray code.

1 0 1 1 0 Binary 1 + 0 1 1 0 Binary 1 0 + 1 1 0 Binary

  
1 Gray 1 1 Gray 1 1 1 Gray

1 0 1 + 1 0 Binary 1 0 1 1 + 0 Binary
 
1 1 1 0 Gray 1 1 1 0 1 Gray

(10110)2 = (11101)Gray
Gray-to-Binary Conversion

 Retain most significant bit.

 From left to right, add each binary code bit generated to the Gray
code bit in the next position, discarding carries.
 Example: Convert Gray code 11011 to binary.

1 1 0 1 1 Gray 1 1 0 1 1 Gray 1 1 0 1 1 Gray

 +  + 
1 Binary 1 0 Binary 1 0 0 Binary

1 1 0 1 1 Gray 1 1 0 1 1 Gray
+  + 
1 0 0 1 Binary 1 0 0 1 0 Binary

(11011)Gray = (10010)2
Logic Gates

 A gate is an electronic device that produces a result based

on two or more input values.
 In reality, gates consist of one to six transistors, but digital
designers think of them as a single unit.
 Integrated circuits contain collections of gates suited to a
particular purpose.
 Basic Logic gates NOT, AND, OR

 Derived logic gates, NAND, NOR, XOR, XNOR

Basic Logic gates
 Truth Tables, Boolean Expressions, and Logic Gates

AND OR NOT
x y z x y z x z
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

z=x•y=xy z=x+y z = x = x’

x x x
y z y z z
NAND Gate

NAND

A C = ~(A & B)
nand(C,A,B)
Z
B
Truth table
A B C
0 0 1
A 0 1 1
C
1 0 1
B
1 1 0
NOR Gate

NOR

A C = ~(A | B)
C nor(C,A,B)
B
A B C
0 0 1
A 0 1 0
C 1 0 0
B 1 1 0
Exclusive-OR Gate

XOR A B C
A
C 0 0 0
B
0 1 1
C = A ^ B 1 0 1
xor(C,A,B)
1 1 0
Exclusive-NOR Gate

XNOR A B C
A
C 0 0 1
B
0 1 0
C = ~(A ^ B)
C = A ~^ B 1 0 0
xnor(C,A,B) 1 1 1
Multiple-input Gates

C1 C2

C3 C4