DLD - DIGITAL LOGIC DESIGN

Digital Systems and Binary Numbers

1
• Digital
• Concerned with the interconnection among digital components and
modules
» Best Digital System example is General Purpose
Computer
• Logic Design
• Deals with the basic concepts and tools used to design digital
hardware consisting of logic circuits
» Circuits to perform arithmetic operations (+, -, x, ÷)

2
• Digital Signal : Decimal values are difficult to represent in
electrical systems. It is easier to use two voltage values than
ten.

• Digital Signals have two basic states:

1 (logic “high”, or H, or “on”)
0 (logic “low”, or L, or “off”)
• Digital values are in a binary format. Binary means 2 states.

• A good example of binary is a light (only on or off)

on off

Power switches have labels “1” for on and “0” for off.

3
• Bits and Pieces of DLD History
• George Boole
• Mathematical Analysis of Logic (1847)
• An Investigation of Laws of Thoughts; Mathematical Theories of Logic
and Probabilities (1854)

• Claude Shannon
• Rediscovered the Boole
• “ A Symbolic Analysis of Relay and Switching Circuits “
• Boolean Logic and Boolean Algebra were Applied to Digital Circuitry

---------- Beginning of the Digital Age and/or Computer Age

World War II
Computers as Calculating Machines

Arlington (State Machines) “ Control “

4
Digital Systems and Binary
Numbers
 Digital age and information age
 Digital computers
– General purposes
– Many scientific, industrial and commercial applications
• Digital systems
– Telephone switching exchanges
– Digital camera
– Electronic calculators, PDA's
– Digital TV
• Discrete information-processing systems
– Manipulate discrete elements of information
– For example, {1, 2, 3, …} and {A, B, C, …}…

5
Analog and Digital Signal
• Analog system
– The physical quantities or signals may vary
continuously over a specified range.
• Digital system
– The physical quantities or signals can assume only
discrete values.
X(t)
– Greater accuracy
X(t)

t t
Analog signal Digital signal 6
Analog Digital
Converts analog waveforms into set of
Analog technology records waveforms as numbers and records them. The numbers are
Technology:
they are. converted into voltage stream for
representation.
Can be used in various computing
Uses: platforms and under operating systems Computing and electronics
like Linux, Unix, Mac OS and Windows.
Analog signal is a continuous signal
which transmits information as a Digital signals are discrete time signals
Signal:
response to changes in physical generated by digital modulation.
phenomenon.
Uses continuous range of values to Uses discrete or discontinuous values to
Representation:
represent information. represent information.
Memory unit: not required required
applications: Thermometer PCs, PDAs
Data
not of high quality high quality
transmissions:
Result: not very accurate accurate
Storage capacity: limited high
processed using OPAMP which uses
Process: using microprocessor which uses logic circuits
electronic circuits
Respose to More likely to get affected reducing Less affected since noise response are analog in
Noise: accuracy nature
Waves: Denoted by sine waves Denoted by square waves
Example: human voice in air electronic devices

7
Binary Digital Signal
• An information variable represented by physical quantity.
• For digital systems, the variable takes on discrete values.
– Two level, or binary values are the most prevalent values.
• Binary values are represented abstractly by:
– Digits 0 and 1
V(t)
– Words (symbols) False (F) and True (T)
– Words (symbols) Low (L) and High (H)
– And words On and Off Logic 1
• Binary values are represented by values
or ranges of values of physical quantities.
undefine

Logic 0
t
Binary digital signal
8
Decimal Number System
• Base (also called radix) = 10
– 10 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
• Digit Position 2 1 0 -1 -2

– Integer & fraction 5 1 2 7 4

• Digit Weight 100 10 1 0.1 0.01

– Weight = (Base) Position

• Magnitude
500 10 2 0.7 0.04
– Sum of “Digit x Weight”
d2*B2+d1*B1+d0*B0+d-1*B-1+d-2*B-2
• Formal Notation
(512.74)10
9
Octal Number System
• Base = 8
– 8 digits { 0, 1, 2, 3, 4, 5, 6, 7 }
• Weights 64 8 1 1/8 1/64

– Weight = (Base) Position 5 1 2 7 4

2 1 0 -1 -2
• Magnitude
5 *82+1 *81+2 *80+7 *8-1+4 *8-2
– Sum of “Digit x Weight”
=(330.9375)10
• Formal Notation
(512.74)8

10
Binary Number System
• Base = 2
– 2 digits { 0, 1 }, called binary digits or “bits”
• Weights 4 2 1 1/2 1/4

– Weight = (Base) Position 1 0 1 0 1

2 1 0 -1 -2
• Magnitude
1 *22+0 *21+1 *20+0 *2-1+1 *2-2
– Sum of “Bit x Weight”
=(5.25)10
• Formal Notation
(101.01)2
• Groups of bits 4 bits = Nibble
1011
8 bits = Byte
11000101
11
Hexadecimal Number System
• Base = 16
– 16 digits { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
• Weights 256 16 1 1/16 1/256

– Weight = (Base) Position 1 E 5 7 A

• Magnitude 2 1 0 -1 -2

1 *162+14 *161+5 *160+7 *16-1+10 *16-2

– Sum of “Digit x Weight”
• Formal Notation =(485.4765625)10
(1E5.7A)16

12
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

13
Addition
• Decimal Addition
1 1 Carry
5 5
+ 5 5

1 1 0
= Ten ≥ Base
 Subtract a Base

14
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

15
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

16
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

17
Number Base Conversions
Evaluate
Magnitude
Octal
(Base 8)

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

Hexadecimal
(Base 16)
Evaluate
Magnitude 18
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
19
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
division
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
20
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

21
Binary − Octal Conversion
Octal Binary
• 8=2 3
0 000
• Each group of 3 bits 1 001
represents an octal digit 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)

22
Binary − Hexadecimal Conversion
Hex Binary
• 16 = 24 0
1
0000
0001
• Each group of 4 bits 2
3
0010
0011
represents a hexadecimal 4
5
0100
0101
digit Assume Zeros 6 0110
7 0111
Example: 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)

23
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)

24
Decimal, Binary, Octal and
00
Hexadecimal
Decimal Binary
0000
Octal
00 0
Hex

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

25
1.5 Complements
• There are two types of complements for each base-r system: the radix complement and diminished
radix complement.
• 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 7-digit binary numbers:
– 1’s complement is (rn – 1) – N = (27–1)–N = 1111111–N
– 1’s complement of 1011000 is 1111111–1011000 = 0100111
• Observation:
– Subtraction from (rn – 1) will never require a borrow
– Diminished radix complement can be computed digit-by-digit
– For binary: 1 – 0 = 1 and 1 – 1 = 0
26
Complements
• 1’s Complement (Diminished Radix Complement)
– All ‘0’s become ‘1’s
– All ‘1’s become ‘0’s
Example (10110000)2
 (01001111)2
If you add a number and its 1’s complement …

10110000
+ 01001111
11111111
27
Complements
• 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
28
Complements
• Example 1.5
– Using 10's complement, subtract 72532 – 3250.

• Example 1.6
– Using 10's complement, subtract 3250 – 72532.
There is no end carry.

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

29
• American Standard Code for Information Interchange (ASCII) Character
Code

30
• ASCII Character Code

31
ASCII Character Codes and Properties
• American Standard Code for Information Interchange (Refer to Table 1.7)
• 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 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.

32
• 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:

33
• Error-Detecting Code
– Redundancy (e.g. extra information), in the form of
extra bits, can be incorporated into binary code
words to detect and correct errors.
– A simple form of redundancy is parity, an extra bit
appended onto the code word to make the number
of 1’s odd or even. Parity can detect all single-bit
errors and some multiple-bit errors.
– A code word has even parity if the number of 1’s in
the code word is even.
Message A: 10001001 1 (even parity)
– A code word hasB:odd
Message parity0 if (odd
10001001 theparity)
number of 1’s in
the code word is odd.
– Example:
34
Binary Storage and Registers
• Registers
– A binary cell is a device that possesses two stable states and is capable of storing
one of the two states.
– A register is a group of binary cells. A register with n cells can store any discrete
quantity of information that contains n bits.

n cells 2n possible states

• A binary cell
– Two stable state
– Store one bit of information
– Examples: flip-flop circuits, ferrite cores, capacitor
• A register
– A group of binary cells
– AX in x86 CPU
• Register Transfer
– A transfer of the information stored in one register to another.
– One of the major operations in digital system.
– An example in next slides.

35
A Digital Computer Example

Memory

Control
CPU unit Datapath

Inputs: Keyboard, Outputs: CRT,

mouse, modem, LCD, modem,
Input/Output
microphone speakers

Synchronous or
Asynchronous?
36
Transfer of information

37
Figure 1.1 Transfer of information among register
Transfer of information
• The other major
component of a
digital system
– Circuit elements to
manipulate individual
bits of information
– Load-store machine
LD R1;
LD R2;
ADD R3, R2,
R1;
SD R3;
Figure 1.2 Example of binary information processing 38
Binary 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
Universal Gate
• NAND and NOR Gates are called Universal
Gates because AND, OR and NOT gates can be
implemented &created by using these gates.

NAND Gate Implementations NOR Gate

Implementations

Dr. V. Krishnanaik Ph.D

Binary Logic
• Logic gates
– Example of binary signals

3
Logic 1
2
Un-define
1
Logic 0
0

Figure 1.3 Example of binary signals 42

Binary Logic

• Logic gates
– Graphic Symbols and Input-Output Signals for
Logic gates:
Fig. 1.4 Symbols for digital logic circuits

43
Fig. 1.5 Input-Output signals for gates
Binary Logic

• Logic gates
– Graphic Symbols and Input-Output Signals for
Logic gates:

Fig. 1.6 Gates with multiple inputs

44
Boolean Operations and Expressions

• Boolean Addition
– Logical OR operation
Ex 4-1) Determine the values of A, B, C, and D that make the sum term
A+B’+C+D’
Sol) all literals must be ‘0’ for the sum term to be ‘0’
A+B’+C+D’=0+1’+0+1’=0 A=0, B=1, C=0, and D=1

• Boolean Multiplication
– Logical AND operation
Ex 4-2) Determine the values of A, B, C, and D for AB’CD’=1
Sol) all literals must be ‘1’ for the product term to be ‘1’
AB’CD’=10’10’=1 A=1, B=0, C=1, and D=0

45
Laws of Boolean Algebra
• Commutative Law: the order of literals does not
matter
A+B=B+A AB=BA

• Associative Law: the grouping of literals does not

matter
A + (B + C) = (A + B) + C (=A+B+C)
A(BC) = (AB)C (=ABC)

46
 Distributive Law : A(B + C) = AB + AC (A+B)(C+D) = AC + AD + BC + BD
Rules of Boolean Algebra
 A+0=A In math if you add 0 you have changed
nothing in Boolean Algebra ORing with 0 changes
nothing
 A•0=0 In math if 0 is multiplied with anything
you get 0. If you AND anything with 0 you get 0
 A•1 =A ANDing anything with 1 will yield the
anything

 A+A = A ORing with itself will give the same result

 A+A’=1 Either A or A’ must be 1 so A + A’ =1
 A•A = A ANDing with itself will give the same result
 A•A’ =0 In digital Logic 1’ =0 and 0’ =1, so AA’=0
since one of the inputs must be 0.
 A = (A’)’ If you not something twice you are back
47
to the beginning
Karnaugh Map
• Simplification methods
– Boolean algebra(algebraic method)
– Karnaugh map(map method)) XY+XY=X(Y+Y)=X

– Quine-McCluskey(tabular method) Gray code

– Three- and Four-

input Kanaugh maps