Combinepdf
Combinepdf
Digital Design
MODULE INTRODUCTION
Chua Dingjuan elechuad@nus.edu.sg
https://app.sli.do/event/vD2MFRBXFNYkBEtmu
dX7gV
Lab Instructors :
Mr. Christopher Moy, Dr. Goh Shu Ting
Tutors :
Mr. Christopher Moy, Dr. Goh Shu Ting, Mr. Shao YuRui,
Ms. Tuteja Sugandha
Lab Officers:
Mr. Ho Fook Mun, Ms. Chia Meow Hwa and Mdm. Goh Kah
Seok
4
Digital Design
Course Lecture Structure
Contents Some portion of every
Part 1 (Combinational Logic) week’s lecture will be
◦ Number systems + Verilog devoted to Verilog
◦ Boolean Algebra and logic gates + Verilog
◦ Gate-level design and minimization + Verilog
◦ Combinational logic blocks and design + Verilog
5
Digital Design
Course Organization (Refer Canvas)
Lab
Lecture
Week (E4-03-06 Digital Tutorial
(LT6)
Electronics Lab)
WK 1 ✓
WK 2 ✓ Tutorial – 1
WK 4 Lab 1 ✓ Tutorial – 3
WK 5 Lab 2 ✓ Tutorial – 4
Mid-Semester Quiz
WK 6 Lab 3 20 Feb 25 - 915AM to
1045AM
Recess Week
6
Digital Design
Course Organization (Refer Canvas)
Week Lab Lecture Tutorial
WK 7 Project 1 ✓ Tutorial – 5
WK 8 Project 2 ✓ Tutorial – 6
✓
WK 9 Project 3 Tutorial – 7
Guest Lecture
WK 10 Verilog Evaluation Tutorial – 8
WK 11 Final Quiz
WK 12
No final exam
7
Course Assessment
Component Assessment Weight
Quizzes Total 40%
o Mid-Term Quiz 17%
o Weekly Canvas Quizzes 6%
o Final Quiz 17%
Labs Total 30%
o Lab Assignment 1 3%
o Lab Assignment 2 5%
o Lab Assignment 3 10%
o Verilog Evaluation 12%
Design Project – Team Work Total 30%
o Project basic features (specified) 30%
o Enhanced features (open-ended)
No final exam
9
Digital Design
Quizzes
o Mid-Semester Quiz 1 – 17%
o Week 6 Thursday 20 Feb 25 - 915AM to 1045AM @ Venue TBA
o Closed book test, single A4 (two sided) help/crib/cheat sheet allowed.
o Calculators are not allowed.
o Includes Part 1 lecture topics covered from Week 1 to Week 4.
oEnd-Semester Quiz 2 – 17%
o Week 11 Thursday 03 Apr 25 - 915AM to 1045AM @ Venue TBA
o Closed book test, single A4 sized (two sided) help/crib/cheat sheet is allowed.
o Calculators are allowed.
o Includes Part 2 lecture topics covered from Week 5 to Week 8.
oWeekly Canvas Quizzes – 6%
o Questions to identify misconceptions and reinforce of concepts
o MCQ, MRQ, FIB, etc
o 3 Attempts, Best Score Taken
10
Digital Design
LAB / PROJECT REMINDER
o EE2026 is a hands-on module
significant lab and project time / components
o Software : Xilinx Vivado 2018.2
o Referring to installation instructions provided on Canvas,
please install the software by end of Week 3
o Unfortunately, this software is not supported on Mac
operating systems (only windows / linux)
o If you have difficulties accessing a windows-based system,
PC Cluster access is available. Details on Canvas Pages >>
EE2026 - PC Cluster Access for Mac Users
o Project will be done in groups of 4, students are to be from
same lab group.
11
Digital Design
Course Information
Course materials
◦ Canvas (Everything about the course)
Need Help?
◦ Tutors (tutorial questions)
◦ TAs and GAs (labs and projects)
◦ During lab sessions
◦ Face-to-face consultation with lecturer:
◦ By appointment, email elechuad@nus.edu.sg
12
Digital Design
Expected Learning Outcomes
Expected learning outcome (Part 1)
◦ Be able to perform conversion between binary, octal, hexadecimal
and decimal number systems, and solve simple problems;
◦ Understand Boolean Algebra, and manipulate and simplify Boolean
functions using theorems and postulates;
◦ Be able to design simple combinational logic circuits based on Truth
table and Karnaugh Map
◦ Be able to design complex combinational logic circuits using Hardware
Description Languages (Verilog) and/or combinational building blocks
◦ Be able to simulate complex combinational blocks and verify their
proper functionality through behavioural simulation
◦ Be able to design combinational logic circuits for practical problems /
applications
13
Digital Design
Expected Learning Outcomes
Expected learning outcome (Part-2)
◦ Be able to describe simple sequential logic circuits based on functional
descriptions
◦ Be able to describe simple sequential logic circuits based on state
transition diagrams
◦ Be able to design complex logic circuits using Hardware Description
Languages (Verilog) and/or sequential/combinational building
blocks/IPs
◦ Be able to simulate complex blocks and verify their proper
functionality through behavioural simulation
◦ Be able to design complex logic circuits for practical problems /
applications
14
Digital Design
Why Study this
Module?
19
Digital Design
INTRODUCTION
Analog vs. Digital Circuit
•Analog circuit deals with continuous signals
•Digital circuit deals with signals having discrete levels
t t
26
Digital Design
Why Digital?
o Robustness (reliability)
o Programmability
o Scalability (in integrated circuit technology)
o Cost
27
Digital Design
Technology Scaling
Transistors got smaller over time (at a relentless pace)
µm
10
1 0.8 µm 0.5 µm
0.35 µm 0.25 µm
0.18 µm
0.1 0.13 µm 90 nm
65 nm
45 nm
32 nm 22 nm
0.01 10 nm
7 nm
5 nm
3 nm
0.001
1970 1980 1990 2000 2010 2020 2030
year
28
Digital Design
Technology Scaling (cont.)
1971:
• Intel 4-bit processor in 10 µm PMOS process
with 2300 transistors
• Initial clock speed of 108 kHz
• 10µm pMOS technology
2020:
• AMD Epyc Rome 7 nm processor (64 cores, 256MB
L3, Zen 2 arch.) 40B transistors
• IBM z15 5.2 GHz clock freq., 12 cores in 14 nm
FinFET, 9.2B transistors
• Intel Xeon Platinum 8180 in 14nm CMOS (28
cores), 3.6 GHz, 205 W, 8B transistors
• nVIDIA Ampere, 7nm FinFET, 5 PFLOPS, 54B
transistors
29
Digital Design
Technology Scaling (cont.)
10000
millions of transistors/die
1000
100
10 Moore’s
1 law
0.1
0.01
0.001
1970 1980 1990 2000 2010 2020
year
As more and more transistors can be integrated on a single chip,
- functionality is increased
- for the same functionality: lower chip area, lower cost per transistor
30
Digital Design
Digital Revolution & Information Age
1947 – Invention of transistor
1971 – First microprocessor
*Rapid development of digital computing and communication technology
brought about the digital revolution and information age
1980s – Personal computers
1990s – World Wide Web, digital cameras
2000s – Mobile phones, digital TVs, ipod
2010 – Smart phones, xPad, cloud computing (accessible
everywhere), social networking (constantly connected)
2020 – Cloud computing, Internet of things, ultra-low
power high-performance mobile computing, ubiquitous
computing, immersive computing/augmented reality,
gesture recognition...
31
Digital Design
Example in Your Pocket (Today)
Application Processor (AP) Image sensor + pre-processing
(microprocessor cores, GPU, LTE modem
memory, video processing…)
Touchscreen
controller
Image sensor +
pre-processing
smart battery
(charge, wearing, GPS, WiFi, DRAM, Flash, RF transceiver, Power
genuineness) Management, NFC, audio, display power management,
Digital Design FPGA, battery charger, compass, other sensors 32
Example Available Everywhere
(Tomorrow) from GREEN IC Group
energy
1.2 V
http://www.green-ic.org
0.3 V
Ultra-low Energy-
CORE
IMEM
bank 0
bank 1
bank 2
bank 3
bank 4
bank 5
bank 6
bank 7
testing harness
clk. gen.
MCU core
3.08mm
bank 0
bank 1
bank 2
bank 3
bank 4
bank 5
bank 6
bank 7
DMEM
ripple self-startup & headers
solar cell
extractor recognition
Voice Activity Detector (VAD)
33
Digital Design voice controlled device
Heaters array Thermopiles array
EE2026
Digital Design
NUMBER SYSTEMS & VERILOG INTRO
Chua Dingjuan elechuad@nus.edu.sg
NUMBER SYSTEMS
Positional Number Systems : Decimal, Binary, Hex
Binary Arithmetic
Introduction to Verilog
Positional Number System (Decimal)
Decimal number: Digits (0 to 9) Radix (r=10)
Terminologies
◦ Radix (or base)
◦ Digits and a numeral (0
radix-1) Number 1260.25
◦ Radix point
◦ Place value (or weight) is in
the power of the base 103 100 10-1
(positive on the left and
negative on the right side of 102
Radix point
the radix point integer part fractional part
6
Digital Design
Radix r and its Decimal Equivalent
General form of Number of radix r:
Radix point
Ar = ( an an −1... ao .a−1... a− m )r
where an , an −1,..., a0 ,..a− m ∈ {0,...( r − 1)} (Integer only)
Decimal equivalent:
Ar = (an an −1... ao .a−1... a−m )r Radix point is here
7
Digital Design
Binary Number
Digits (0 to 1) Radix (r=2)
Number 10110.01
20 2-1
Radix point
24
Decimal Equivalent: 23
N10 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 + 0 × 2 −1 + 1 × 2 −2
1
= 16 + 0 + 4 + 2 + 0 + 0 +
4
= 22.25
(10110.01)2 = (22.25)10
8
Digital Design
MSB and LSB of a Binary Number
MSB
◦Most significant bit
LSB
◦Least significant bit
1011001
(Left-most bit) MSB LSB (Right-most bit)
Range
◦ 0 to 2n – 1, where n is the number of bits ( 2n values )
9
Digital Design
( 1 1 0 1 . 0 1 1 0 )2
Hexadecimal number ( D . 6 )16
Digits (0 to 15) Hex Dec Bin
Radix (r=16) 0 0 0000
1 1 0001
3 3 0011
4 4 0100
16-2
163 2 160 16-1 5 5 0101
16
6 6 0110
Radix point
Decimal Equivalent: 7 7 0111
3 2 1 0 −1 −2 8 8 1000
N10 = 1 × 16 + 8 × 16 + F × 16 + 4 × 16 + 2 × 16 + 10 × 16
9 9 1001
2 10
= 4096 + 2048 + 240 + 4 + + A 10 1010
16 256 B 11 1011
21 C 12 1100
= 6388 +
128 (18F4.2A)16 ≅ (6388.16)10 D 13 1101
≈ 6388.16 E 14 1110
F 15 1111
10
Digital Design
( 1 0 1 . 0 1 1 )2
Octal number ( 5 . 3 )8
Radix (r=8) Digits (0 to 7) Oct Dec
0 0
1 1
3
2
4 4
80 8-1 5 5
82 6 6
Decimal Equivalent: Radix point
7 7
N10 = 7 × 82 + 5 × 81 + 4 × 80 + 2 × 8−1 ? 8
? 9
2
= 448 + 40 + 4 + ? 10
8
= 492.25
11
Digital Design
Numbers with Different Radixes:
Summary
Numbers with Different Radixes
Decimal Binary Octal Hexadecimal
(radix 10) (radix 2) (radix 8) (radix 16)
12
Digital Design
Radix Conversion
Three types of conversions:
o Radix r (r≠10) Decimal
13
Digital Design
Radix r (r ≠ 10) Decimal (r = 10)
Binary Decimal (10110.01)2 = (??)10
(10110.01)2 → 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 + 0 × 2 −1 + 1 × 2 −2 = (22.25)10
14
Digital Design
Decimal (r = 10) Radix r (r ≠ 10)
Decimal Binary (102)10 = (??)2
(102)10 = A2 = ( an an −1... ao .a−1... a− m )r
= an × 2 n + an −1 × 2 n −1 + ... + a1 × 21 + ao (Assume integer)
= ( an × 2 n + an −1 × 2 n −1 + ... + a1 × 21 ) + ao
Integer multiple of 2
25/2 12 1 a2 N10 = a6 × 26 + a5 × 25 + a4 × 2 4 + a3 × 23
12/2 6 0 a3 + a2 × 2 2 + a1 × 21 + a0 × 20
6/2 3 0 a4 = 1 × 2 6 + 1 × 25 + 0 × 2 4 + 0 × 23
3/2 1 1 a5 + 1 × 2 2 + 1 × 21 + 0 × 20
1/2 0 1 a6 = 64 + 32 + 0 + 0 + 4 + 2 + 0
= 102
Stop when the quotient = 0
16
Digital Design
How about Fractional Numbers?
Decimal Binary (0.58)10 = (??)2
Multiply by 2:
17
Digital Design
How about Fractional Numbers? – cont.
Decimal Binary (0.58)10 = (??)2
Page 19
Addition
Addition table:
0+0=0
0+1=1
1 + 1 = 10
Example:
10111 + 110 = 11101
1 1
Carry
10111
+ 110
---------------
11101
20
Digital Design
Multiplication
Multiplication table:
0x0=0
0x1=0
1x1=1 Example:
10111 x 110 = 10001010
10111 Multiplicand
x 110 Multiplier
---------------
Multiplication: 00000
Shift then Add 10111 Partial products
Only need “add” operation + 10111
----------------------
10001010 Product
21
Digital Design
Subtraction
Subtraction table:
0-0=0
1-0=1
1-1=0
0–1=1 with a borrow from the next (higher) bit
Example:
11011 - 110 = 10101
11011
- 110
---------------
10101
22
Digital Design
Division (shift and subtract)
Shift then subtraction
Division Only need “subtract” operation
• Set quotient to 0
100101/101 = ?
• Align leftmost digits in dividend and divisor
• Repeat
111 quotient • If that portion of the dividend above
the divisor is greater than or equal to
101 100101 the divisor
101 • Then subtract divisor from that
portion of the dividend and
1000 • Concatenate 1 to the right hand
101 end of the quotient
• Else concatenate 0 to the right
111 hand end of the quotient
101 • Shift the divisor one place right
• Until dividend is less than the divisor
10 remainder
• quotient is correct, dividend is remainder
• STOP
Check in decimal
23
Digital Design
Arithmetic
•Only addition, subtraction and shifting are needed
for 4 binary arithmetic operations
•Subtraction can be performed by adding a negative
number
•Thus, a computer may only use adders and shifters
to perform all binary arithmetic operations
•This requires an appropriate representation of the
negative binary numbers
24
Digital Design
Signed Binary numbers
Three ways to represent the signed binary
numbers
25
Unsigned Binary number
26
Signed Binary – Signed Magnitude (S-M)
Example:
Signed binary number (n bits)
Decimal S-M
3 011
1 0 1 … … 1 0
2 010
1 001
Note:
Magnitude +0 000 Two zeros
-0 100
Sign bit 0 – represents a positive number
-1 101
1 – represents a negative number
-2 110 Negative
MSB is a sign bit numbers
-3 111
27
Signed Magnitude – cont.
More examples: 00111010 = +0111010 = (58)10
28
Arithmetic
using Binary Numbers (S-M) ?
Computer performs binary arithmetic operations using only
◦ Adders
◦ Multipliers
Subtraction is performed by adding a negative number
30
Diminished Radix Complement
A* = rn – A – 1 or A*= (rn – 1) - A
Examples:
Decimal Operation: 1 1 1
888 888 888
A = 237 A* = (100010 – 1) - 23710 - 237 ⟺ + (-237) ⟺ + 762
= 99910 – 23710 651 ______ 650
+1
= 76210 651
Binary number:
A = 0011 A* = (100002 – 1) – 00112 = 11112 – 00112 = 11002
32
1’s Complement representation of
signed binary number
No change for positive numbers and use 1’s complement for negative numbers
Two Zeroes?
33
2’s Complement of a Binary Number
“2’s Complement” is the radix complement of binary
numbers
2’s complement of a n-bit number can be obtained by
adding “1” to its 1’s complement (reversing all the bits), i.e.,
A* = 2n – A
= (2n – A -1) + 1
Binary number (n=8): 01011100
34
2’s Complement Arithmetic
No change for positive numbers and use 2’s complement for negative numbers
1950s – 1960s
Rapid
1947 Development of
Technology Intel 4-bit
The First Processor
Transistor 2300 Transistors
~ 400 gates
Robert, G. (2013) IBM Standard Modular System [Photograph] Retrieved 1 Dec, 2014, from IEEE Global History Network, Early Popular Computers, 1950 - 1970 http://www.ieeeghn.org/wiki/index.php/File:EPC_-_fig_4.jpg
o Verilog is CasE-SeNSitiVe….
o Module Name : No spaces, No starting with numbers (1box), use meaningful names (box)
o Port Direction : input, output, inout (bidirectional)
o Port Bitwidth : input a,b ; input [1:0] c ; output [3:0] y
By default, signals Input c is a 2-bit vector Output y is a 4-bit vector
are one bit! (little endian) y : y[3] y[2] y[1] y[0]
o Don’t forget the __;____!
We have covered:
•Introduction to Verilog
•Module, input and output ports (Single Bit and Multi-Bit signals)
•Data Types (wire/net vs reg)
•Numerical values (Hexa/Decimal/Binary/Octal/Integer)
•Addition / Subtraction / Conditional Operators
https://app.sli.do/event/vD2MFRBXFNYkBEtmu
dX7gV
5
Digital Design
Radix r and its Decimal Equivalent
General form of Number of radix r:
Radix point
Ar = ( an an −1... ao .a−1... a− m )r
where an , an −1,..., a0 ,..a− m ∈ {0,...( r − 1)} (Integer only)
Decimal equivalent:
Ar = (an an −1... ao .a−1... a−m )r Radix point is here
6
Digital Design
Binary Number
Digits (0 to 1) Radix (r=2)
Number 10110.01
20 2-1
Radix point
24
Decimal Equivalent: 23
N10 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 + 0 × 2 −1 + 1 × 2 −2
1
= 16 + 0 + 4 + 2 + 0 + 0 +
4
= 22.25
(10110.01)2 = (22.25)10
7
Digital Design
MSB and LSB of a Binary Number
MSB
◦Most significant bit
LSB
◦Least significant bit
1011001
(Left-most bit) MSB LSB (Right-most bit)
Range
◦ 0 to 2n – 1, where n is the number of bits ( 2n values )
8
Digital Design
( 1 1 0 1 . 0 1 1 0 )2
Hexadecimal number ( D . 6 )16
Digits (0 to 15) Hex Dec Bin
Radix (r=16) 0 0 0000
1 1 0001
3 3 0011
4 4 0100
16-2
163 2 160 16-1 5 5 0101
16
6 6 0110
Radix point
Decimal Equivalent: 7 7 0111
3 2 1 0 −1 −2 8 8 1000
N10 = 1 × 16 + 8 × 16 + F × 16 + 4 × 16 + 2 × 16 + 10 × 16
9 9 1001
2 10
= 4096 + 2048 + 240 + 4 + + A 10 1010
16 256 B 11 1011
21 C 12 1100
= 6388 +
128 (18F4.2A)16 ≅ (6388.16)10 D 13 1101
≈ 6388.16 E 14 1110
F 15 1111
12
Digital Design
( 1 0 1 . 0 1 1 )2
Octal number ( 5 . 3 )8
Radix (r=8) Digits (0 to 7) Oct Dec
0 0
1 1
3
2
4 4
80 8-1 5 5
82 6 6
Decimal Equivalent: Radix point
7 7
N10 = 7 × 82 + 5 × 81 + 4 × 80 + 2 × 8−1 ? 8
? 9
2
= 448 + 40 + 4 + ? 10
8
= 492.25
13
Digital Design
Numbers with Different Radixes:
Summary
Numbers with Different Radixes
Decimal Binary Octal Hexadecimal
(radix 10) (radix 2) (radix 8) (radix 16)
14
Digital Design
Radix Conversion
Three types of conversions:
o Radix r (r≠10) Decimal
16
Digital Design
Radix r (r ≠ 10) Decimal (r = 10)
Binary Decimal (10110.01)2 = (??)10
(10110.01)2 → 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 + 0 × 2 −1 + 1 × 2 −2 = (22.25)10
17
Digital Design
Decimal (r = 10) Radix r (r ≠ 10)
Decimal Binary (102)10 = (??)2
(102)10 = A2 = ( an an −1... ao .a−1... a− m )r
= an × 2 n + an −1 × 2 n −1 + ... + a1 × 21 + ao (Assume integer)
= ( an × 2 n + an −1 × 2 n −1 + ... + a1 × 21 ) + ao
Integer multiple of 2
25/2 12 a2 N10 = a6 × 26 + a5 × 25 + a4 × 2 4 + a3 × 23
12/2 6 a3 + a2 × 2 2 + a1 × 21 + a0 × 20
6/2 3 a4 = 1 × 2 6 + 1 × 25 + 0 × 2 4 + 0 × 23
3/2 1 a5 + 1 × 2 2 + 1 × 21 + 0 × 20
1/2 0 a6 = 64 + 32 + 0 + 0 + 4 + 2 + 0
= 102
Stop when the quotient = 0
19
Digital Design
How about Fractional Numbers?
Decimal Binary (0.58)10 = (??)2
Multiply by 2:
21
Digital Design
How about Fractional Numbers? – cont.
Decimal Binary (0.58)10 = (??)2
Page 24
Addition
Addition table:
0+0=0
0+1=1
1 + 1 = 10
Example: Carry
10111 + 110 = 11101
10111
+ 110
---------------
25
Digital Design
Multiplication
Multiplication table:
0x0=0
0x1=0
1x1=1 Example:
10111 x 110 = 10001010
10111 Multiplicand
x 110 Multiplier
---------------
Multiplication: 00000
Shift then Add Partial products
10111
Only need “add” operation
+ 10111
----------------------
10001010 Product
27
Digital Design
Subtraction
Subtraction table:
0-0=0
1-0=1
1-1=0
0–1=1 with a borrow from the next (higher) bit
Example:
11011 - 110 = 10101 11011
- 110
---------------
28
Digital Design
Division (shift and subtract)
Shift then subtraction
Division Only need “subtract” operation
• Set quotient to 0
100101/101 = ?
• Align leftmost digits in dividend and divisor
• Repeat
111 quotient • If that portion of the dividend above
the divisor is greater than or equal to
101 100101 the divisor
101 • Then subtract divisor from that
portion of the dividend and
1000 • Concatenate 1 to the right hand
101 end of the quotient
• Else concatenate 0 to the right
111 hand end of the quotient
101 • Shift the divisor one place right
• Until dividend is less than the divisor
10 remainder
• quotient is correct, dividend is remainder
• STOP
Check in decimal
30
Digital Design
Arithmetic
•Only addition, subtraction and shifting are needed
for 4 binary arithmetic operations
•Subtraction can be performed by adding a negative
number
•Thus, a computer may only use adders and shifters
to perform all binary arithmetic operations
•This requires an appropriate representation of the
negative binary numbers
31
Digital Design
Signed Binary numbers
Three ways to represent the signed binary
numbers
32
Unsigned Binary number
33
Signed Binary – Signed Magnitude (S-M)
Example:
Signed binary number (n bits)
Decimal S-M
3 011
1 0 1 … … 1 0
2 010
1 001
Note:
Magnitude +0 000 Two zeros
-0 100
Sign bit 0 – represents a positive number
-1 101
1 – represents a negative number
-2 110 Negative
MSB is a sign bit numbers
-3 111
34
Signed Magnitude – cont.
More examples: 00111010 = +0111010 = (58)10
35
Arithmetic
using Binary Numbers (S-M) ?
Computer performs binary arithmetic operations using only
◦ Adders
◦ Multipliers
Subtraction is performed by adding a negative number
37
Diminished Radix Complement
A* = rn – A – 1 or A*= (rn – 1) - A
Examples:
Decimal Operation: 1 1 1
888 888 888
A = 237 A* = (100010 – 1) - 23710 - 237 ⟺ + (-237) ⟺ + 762
= 99910 – 23710 651 ______ 650
+1
= 76210 651
Binary number:
A = 0011 A* = (100002 – 1) – 00112 = 11112 – 00112 = 11002
39
1’s Complement representation of
signed binary number
No change for positive numbers and use 1’s complement for negative numbers
Two Zeroes?
40
2’s Complement of a Binary Number
“2’s Complement” is the radix complement of binary
numbers
2’s complement of a n-bit number can be obtained by
adding “1” to its 1’s complement (reversing all the bits), i.e.,
A* = 2n – A
= (2n – A -1) + 1
Binary number (n=8): 01011100
42
2’s Complement Arithmetic
No change for positive numbers and use 2’s complement for negative numbers
1950s – 1960s
Rapid
1947 Development of
Technology Intel 4-bit
The First Processor
Transistor 2300 Transistors
~ 400 gates
Robert, G. (2013) IBM Standard Modular System [Photograph] Retrieved 1 Dec, 2014, from IEEE Global History Network, Early Popular Computers, 1950 - 1970 http://www.ieeeghn.org/wiki/index.php/File:EPC_-_fig_4.jpg
o Verilog is CasE-SeNSitiVe….
o Module Name : No spaces, No starting with numbers (1box), use meaningful names (box)
o Port Direction : input, output, inout (bidirectional)
o Port Bitwidth : input a,b ; input [1:0] c ; output [3:0] y
By default, signals Input c is a 2-bit vector Output y is a 4-bit vector
are one bit! (little endian) y : y[3] y[2] y[1] y[0]
o
3
Digital Design
What is Boolean Algebra?
Brief History:
o Boolean was developed in 1854 by George Boole
(An English mathematician, philosopher, and
logician)
o Huntington formulated the postulates in 1904 as
the formal definition
o Boolean Algebra is the mathematical foundation
for digital system design, including computers
o It was first applied to the practical problem
(Analysis of networks of relays) in late 1930s by C.E
Shannon (MIT) who later introduced “Switching
algebra” in 1938
o Switching algebra is a Boolean algebra in which the
number of elements is precisely two
4
Digital Design
Boolean Algebra
o Boolean algebra is a two-valued type of switching algebra
o Switching algebra represents bistable electrical switching
circuits (On or Off)
o Boolean algebra is defined by a set of elements, B, and there
are two main operators (AND, OR)
o Binary operators (two arguments involved)
o AND “.”
o OR “+”
o Plus, one unary operator (only one argument involved)
o NOT “ � ” (Complement operator represented by an overbar)
3. Commutative Law
i. x+𝑦𝑦 = 𝑦𝑦 + 𝑥𝑥
ii. x� 𝑦𝑦 = 𝑦𝑦 � 𝑥𝑥
4. Distributive Law
i. 𝑥𝑥 � 𝑦𝑦 + 𝑧𝑧 = 𝑥𝑥 � 𝑦𝑦 + 𝑥𝑥 � 𝑧𝑧 (� 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 +)
ii. 𝑥𝑥 + 𝑦𝑦 � 𝑧𝑧 = (𝑥𝑥 + 𝑦𝑦) � (𝑥𝑥 + 𝑧𝑧) (+ 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 �)
5. For every element 𝑥𝑥 in the set B, there exists an element 𝑥𝑥̅ in the set B, such that
i. 𝑥𝑥 + 𝑥𝑥̅ = 1
ii. 𝑥𝑥 � 𝑥𝑥̅ = 0
(𝑥𝑥 is called the complement of 𝑥𝑥)
7
Digital Design
The Three Operators in Two-
Valued Boolean Algebra (B={0,1})
OR: 𝑨𝑨 + 𝑩𝑩 AND: 𝑨𝑨 � 𝑩𝑩 NOT: 𝑨𝑨
𝑨𝑨 𝑩𝑩 𝑨𝑨 + 𝑩𝑩 𝑨𝑨 𝑩𝑩 𝑨𝑨 � 𝑩𝑩 𝑨𝑨 𝑨𝑨
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1 A = 0 → 𝐴𝐴 = 1
A = 1 → 𝐴𝐴 = 0
0 + 0 = 0 0 � 0 = 0
0 + 1 = 1 0 � 1 = 0
1 + 0 = 1 1 � 0 = 0
1 + 1 = 1 1 � 1 = 1
1 𝐴𝐴 + 𝐴𝐴 = 𝐴𝐴 𝐴𝐴 � 𝐴𝐴 = 𝐴𝐴 Tautology Law
2 𝐴𝐴 + 1 = 1 𝐴𝐴 � 0 = 0 Union Law
4 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 𝐴𝐴 � 𝐵𝐵 � 𝐶𝐶 = 𝐴𝐴 � 𝐵𝐵 � 𝐶𝐶 Associative Law
= 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶
5 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴̅ � 𝐵𝐵� 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴̅ + 𝐵𝐵� De Morgan’s Law
6 𝐴𝐴 + 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴 𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴 Absorption Law
7 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵 𝐴𝐴 � 𝐴𝐴̅ + 𝐵𝐵 = 𝐴𝐴 � 𝐵𝐵
8 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� = 𝐴𝐴 � = 𝐴𝐴
(𝐴𝐴 + 𝐵𝐵)(𝐴𝐴 + 𝐵𝐵) Logical adjacency
9 ̅ + 𝐵𝐵𝐵𝐵
𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶 𝐴𝐴 + 𝐵𝐵 𝐴𝐴̅ + 𝐶𝐶 𝐵𝐵 + 𝐶𝐶 Consensus Law
̅
= 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶 = (𝐴𝐴 + 𝐵𝐵)(𝐴𝐴̅ + 𝐶𝐶)
1 1 1 1
10
Digital Design
Examples - Truth Table
# Theorem
11
Digital Design
Examples - Truth Table vs Algebra
# Theorem
6 𝐴𝐴 + 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴 𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴 Absorption Law
𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴
𝐴𝐴. 𝐴𝐴 + 𝐴𝐴. 𝐵𝐵 = 𝐴𝐴 + 𝐴𝐴. 𝐵𝐵 = 𝐴𝐴 𝐵𝐵 + 1 = 𝐴𝐴
𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴
A B 𝑨𝑨 � 𝑨𝑨 + 𝑩𝑩 𝑨𝑨
0 0 0 0
0 1 0 0
1 0 1 1
1 1 1 1
12
Digital Design
Examples - Truth Table
Prove the De Morgan’s Law:
𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴̅ � 𝐵𝐵� 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴̅ + 𝐵𝐵�
A B 𝑨𝑨 + 𝑩𝑩 � � 𝑩𝑩
𝑨𝑨 � A B 𝑨𝑨 � 𝑩𝑩 � + 𝑩𝑩
𝑨𝑨 �
0 0 1 1 0 0 1 1
0 1 0 0 0 1 1 1
1 0 0 0 1 0 1 1
1 1 0 0 1 1 0 0
Prove : 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵 𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴
A B � � 𝑩𝑩
𝑨𝑨 + 𝑨𝑨 𝑨𝑨 + 𝑩𝑩 A B 𝑨𝑨 � 𝑨𝑨 + 𝑩𝑩 𝑨𝑨
0 0 0 0 0 0 0 0
0 1 1 1 0 1 0 0
1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1
13
Digital Design
Truth Table – examples (cont.)
Prove : 𝐴𝐴 + 𝐵𝐵 � 𝐶𝐶 = (𝐴𝐴 + 𝐵𝐵) � (𝐴𝐴 + 𝐶𝐶)
14
Digital Design
But how do we
use these ideas?
Page 15
Design Example
Ben Bitdiddle is having a picnic. He won’t enjoy it if it
rains or if there are ants. Design a circuit that will output
TRUE only if Ben enjoys the picnic.
Solution
Inputs : A (Ants), B (Rain)
Output : E (Ben’s Enjoyment)
Minterm Maxterm
◦ Minterm is a product term that contains all – Maxterm is a sum term that contains all
variables in the function variables in the function
◦ AND all the variables – OR all the variables
◦ If the variable in truth table is “0”, take its
complement in the minterm – If the variable in truth table is “1”, take its
◦ Minterm is equal to 1 for that set of given complement in the maxterm
input – Maxterm is equal to 0 for that set of given
input
17
Digital Design
Truth Table CSOP or CPOS
A Boolean function is in canonical form if it is expressed as
◦ a sum of minterms (Canonical Sum Of Products - CSOP) or
◦ a product of maxterms (Canonical Product Of Sums - CPOS)
18
Digital Design
SOP and POS Truth Table
Are the following two Boolean functions same?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵�
𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
Let’s use truth tables to check:
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
A B E1 A B E2
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 0 1 1 0
SOP: If any PRODUCT in SOP is “1”, the function is “1”. Otherwise, the function is “0”
POS: If any SUM in POS is “0”, the function is “0”. Otherwise, the function is “1”
SOP and POS are different ways to present the same Boolean function
19
Digital Design
SOP and POS Truth Table
Are the following two Boolean functions same?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵�
𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
Can we also prove this via Boolean algebra?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
20
Digital Design
Example-2: Non-Canonical Canonical
Form via Truth Table
Example: For the given Boolean function below, find a canonical minterm and
maxterm expression.
1) obtain the truth table from the given function
2) find minterm or maxterm expression from truth table (CSOP or CPOS)
𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ + 𝑦𝑦𝑧𝑧̅ Non Canonical form
Truth table:
x y z F Canonical minterm expression:
0 0 0 1
𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ 𝑦𝑦� 𝑧𝑧̅ + 𝑥𝑥̅ 𝑦𝑦𝑧𝑧
� + 𝑥𝑥𝑦𝑦
̅ 𝑧𝑧̅ + 𝑥𝑥𝑦𝑦𝑧𝑧
̅ + 𝑥𝑥𝑥𝑥𝑧𝑧̅
0 0 1 1
0 1 0 1 (only contains the minterms that make the function = 1)
0 1 1 1
Canonical maxterm expression:
1 0 0 0
1 0 1 0 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧̅ (𝑥𝑥̅ + 𝑦𝑦� + 𝑧𝑧)̅
1 1 0 1 (only contains the maxterms that make the function = 0)
1 1 1 0
21
Digital Design
Example-3: Non-Canonical Canonical
Form via Postulates and Theorems
Example: For the given Boolean functions below, convert it to canonical minterm or
maxterm expression.
(*Using postulates/theorem to expand the given function to canonical form)
SOP CSOP: 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥𝑦𝑦 ̅ + 𝑥𝑥𝑥𝑥 For missing literals, complete
(CSOP – Canonical SOP) minterms through postulates:
= 𝑥𝑥𝑦𝑦
̅ � 1 + 𝑥𝑥 � 1 � 𝑧𝑧
= 𝑥𝑥𝑦𝑦̅ z + 𝑧𝑧̅ + 𝑥𝑥 𝑦𝑦 + 𝑦𝑦� 𝑧𝑧 A � 1 = 𝐴𝐴 𝑎𝑎𝑎𝑎𝑎𝑎 𝐴𝐴 + 𝐴𝐴̅ =
= 𝑥𝑥𝑦𝑦𝑧𝑧
̅ + 𝑥𝑥𝑦𝑦 ̅ 𝑧𝑧̅ + 𝑥𝑥𝑥𝑥𝑥𝑥 + 𝑥𝑥 𝑦𝑦𝑧𝑧
� 1
1) express SOP as POS
1) a) complement twice
SOP CPOS: 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥𝑦𝑦
̅ + 𝑥𝑥𝑥𝑥 b) apply De Morgan’s law
(CSOP – Canonical POS)
̅ + 𝑥𝑥𝑥𝑥 a
= 𝑥𝑥𝑦𝑦 c) expand
d) re-apply De Morgan’s law
Use distribution postulate: = 𝑥𝑥 + 𝑦𝑦� 𝑥𝑥̅ + 𝑧𝑧̅ b 2) for missing literals, complete
𝐴𝐴 + 𝑩𝑩𝑪𝑪 = 𝐴𝐴 + 𝑩𝑩 𝐴𝐴 + 𝑪𝑪 maxterms through distribution
(A = incomplete sum,
= 𝑥𝑥 𝑥𝑥̅ + 𝑥𝑥 𝑧𝑧̅ + 𝑥𝑥̅ 𝑦𝑦� + 𝑦𝑦� 𝑧𝑧̅ c
postulate
C=NOT(B)=missing literal) = 𝑥𝑥 + 𝑦𝑦 𝑥𝑥̅ + 𝑧𝑧 𝑦𝑦 + 𝑧𝑧 d
x+𝑦𝑦 = (𝑥𝑥 + 𝑦𝑦) + 𝒛𝒛�𝒛𝒛 2) = 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧̅ ⋅ 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥̅ + 𝑦𝑦� + 𝑧𝑧
= (𝑥𝑥 + 𝑦𝑦 + 𝒛𝒛)(𝑥𝑥 + 𝑦𝑦 + 𝒛𝒛� ) ⋅ 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧
22
Digital Design
Example-3 : SOP ⇔ POS (De Morgan’s)
Truth table: Applying De Morgan’s Law to CSOP of 𝑭𝑭𝟏𝟏 :
𝐴𝐴 𝐵𝐵 𝐶𝐶 𝐹𝐹1 𝐹𝐹𝟏𝟏
𝑭𝑭𝟏𝟏 = 𝑭𝑭𝟏𝟏 = 𝑭𝑭𝟏𝟏,𝑪𝑪𝑪𝑪𝑪𝑪𝑪𝑪
0 0 0 0 1
= 𝑨𝑨� 𝑩𝑩 � + 𝑨𝑨
� 𝑪𝑪 � 𝑩𝑩
� 𝑪𝑪 + 𝑨𝑨� 𝑩𝑩𝑩𝑩 + 𝑨𝑨𝑨𝑨𝑨𝑨
0 0 1 0 1 � 𝑩𝑩 � � 𝑨𝑨
� 𝑪𝑪 � 𝑩𝑩
� 𝑪𝑪 � 𝑨𝑨
� 𝑩𝑩𝑩𝑩 � 𝑨𝑨𝑨𝑨𝑨𝑨
= 𝑨𝑨
0 1 0 1 0 = 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 � 𝑨𝑨 + 𝑩𝑩 � (𝑨𝑨
� + 𝑪𝑪 � + 𝑩𝑩 �
� + 𝑪𝑪)
0 1 1 0 1
1 0 0 1 0
Now, find CPOS of F1 directly from truth table:
1 0 1 1 0 clearly the
1 1 0 1 0 𝑭𝑭𝟏𝟏 𝑨𝑨, 𝑩𝑩, 𝑪𝑪 CPOS of F1 same
� 𝑨𝑨 + 𝑩𝑩
= 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 � (𝑨𝑨
� + 𝑪𝑪 � + 𝑩𝑩 �
� + 𝑪𝑪)
1 1 1 0 1
CPOS can be obtained from CSOP (and vice versa) by
applying De Morgan’s Law!
31
Digital Design
Pre-Lab Exercise
The following task is required to be implemented :
oWhen switch A turns on, only LED1 lights up.
oWhen switch B turns on, only LED2 lights up.
oWhen both switches A and B turn on, LED1, LED2, and LED3 light up.
0 0 0
0 1 0
1 0 0
1 1 1
̅ + 𝐴𝐴𝐴𝐴)
LED2 = (𝐴𝐴𝐵𝐵
LED3 = (𝐴𝐴𝐴𝐴)
26
Digital Design
Guidelines for Simplification of
Boolean Function (in SOP)
Three most used theorems:
(1) 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� = 𝐴𝐴 (Logical adjacency)
(2) 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵
(3) 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶̅ + 𝐵𝐵𝐵𝐵 = 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶
̅ (Consensus)
27
Digital Design
LOGIC GATES
AND, OR, NOT, XOR gates
29
Digital Design
Logic Gate Introduction
Logic gates are digital circuits that implement the Boolean
operations.
Basic Logic Gates:
Gate Symbol Function Verilog Gate Symbol Function Verilog
(F) Operator (F) Operator
A
AND A F 𝐴𝐴 � 𝐵𝐵 F=A&B NAND F 𝐴𝐴 � 𝐵𝐵 F = ~(A & B)
B B
30
Digital Design
AND and NAND Gates
A Truth Table (AND, NAND):
F 𝑭𝑭 = 𝑨𝑨 � 𝑩𝑩
B AND NAND
A B 𝑨𝑨 � 𝑩𝑩 𝑨𝑨 � 𝑩𝑩
A
F 𝑭𝑭 = 𝑨𝑨 � 𝑩𝑩 0 0 0 1
B
1 0 0 1
A
F 0 1 0 1
B
1 1 1 0
bubble = complement
AND NAND
F is TRUE only when both A and B are • F is FALSE only if both A and
TRUE B are TRUE
OR NOR
• F is FALSE only when both A and B • F is TRUE only if both A and
are FALSE B are FALSE
XOR XNOR
• F is TRUE if A ≠ B • F is TRUE if A = B
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
# of Gates needed = 3 # of Gates needed = 6
𝐴𝐴
𝐴𝐴 𝐵𝐵
𝐸𝐸1
𝐵𝐵
𝐸𝐸2
34
Digital Design
Implementation using Logic Gates –
Sketch Method
- Implement the following Boolean functions to logic gates, assume that
the maximum number of inputs of a gate is 4.
𝐹𝐹 𝑤𝑤, 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑤𝑤
� 𝑥𝑥𝑧𝑧
̅ + 𝑤𝑤𝑥𝑥𝑥𝑥
� + 𝑤𝑤𝑤𝑤𝑤𝑤 + 𝑥𝑥𝑥𝑥𝑥𝑥
𝑤𝑤 𝑥𝑥 𝑦𝑦 𝑧𝑧
𝑤𝑤
� 𝑥𝑥̅
Input signals needed?
𝑤𝑤, 𝑤𝑤,
� 𝑥𝑥, 𝑥𝑥,̅ 𝑦𝑦, 𝑧𝑧
Types / # of Gates
needed?
AND – 3 inputs
OR – 4 inputs
Schematic drawn in
PLA configuration
# of gates = 7
10
gate count = ____
module func(a,b,c,d,F);
input a, b, c, d;
output F;
assign F = a & b & ~c | a & b & c | b & c & d | ~a & c & d | a & ~b & ~c & d;
endmodule
51
Digital Design
Boolean Function Simplification using
Algebra Manipulation
37
Digital Design
Ex - Boolean Function Simplification
(Relook at the second example):
gate count = 6
gate count = 11 (45.5% reduction!)
38
Digital Design
Ex - Boolean Function Simplification
gate count = 3
gate count = 8
(62.5% reduction!)
39
Digital Design
Timing
VDD
B VDD/2
Gnd
We often think of digital signals If we zoom in, things are quite different!
changing instantaneously…
Critical Path
o Assuming the below tpds, which path below is the slowest?
Critical path delay = 2.7ns
Gate tpd
NOT 0.3ns
2-input OR 0.6ns
3-input OR 0.8ns
3-input AND 0.7ns
4-input AND 0.9ns
o The Critical Path limits the speed at which the entire circuit operates
eg. the slowest path in circuit!
o Total tpd of a combinational circuit is sum of tpd through each element
on the critical path.
Which is the critical path here?
Positive &
Negative Logic
44
Digital Design
Example – Implementation in Positive
Logic
Implement the following Boolean function in positive logic.
A.H
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶 B.H
F.H
A.H
C.H
45
Digital Design
Example – Implementation in Positive
Logic
Implement the following Boolean function in positive logic.
A.H
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶 B.H
F.H
A.H
C.H
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶
46
Digital Design
If you could only
choose one gate…
SELF-READING
𝐴𝐴 ⋅ 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵
De Morgan’s law
- bubbles at the input of an OR gate can be “pushed” at its output, and the
gate is transformed into a NAND gate (similarly, NOR becomes AND)
A.L
𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴 ⋅ 𝐵𝐵 F.L
B.L
De Morgan’s law
- and vice versa, of course:
alternate gate
A.L representations
F.L
B.L
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶
AND
Step 1: 𝐴𝐴 � 𝐵𝐵 NOR
Step 2: A
A (add the negation B F
B where needed for
the correct function) A
A C
C 𝐴𝐴 � 𝐶𝐶
redundant... NOR
A
Step 3:
(i) Replace AND gate with NOR gate B F
(ii) balance the bubbles using inverters
to maintain the correct functionality A
C gate count = 7
NOR
49
Digital Design
Summary
Logic gate is a circuit that implement Boolean operations
AND, NAND, OR, NOR, XOR, XNOR gates
Boolean function implementation using logic gates
Boolean function simplification using algebra postulates and theorems
Timing
Positive and negative logic
◦ Definition
◦ Conversion between positive and negative logic
◦ Gates with mixed logic
Universal Gates
50
Digital Design
EE2026
Digital Design
BOOLEAN ALGEBRA, LOGIC GATES
Chua Dingjuan elechuad@nus.edu.sg
BOOLEAN ALGEBRA
Postulates, Theorems, Laws, AND, OR, NOT, XOR, Minterm,
Maxterm, SOP/POS, CSOP/CPOS
Outline
o What is Boolean Algebra?
o Theorems and Postulates
o Boolean functions and truth table
o Boolean function simplification using algebra manipulation
3
Digital Design
Ask Week 2 Questions here…
You can ask questions during the week using
slido here :
https://app.sli.do/event/aNGM7YZg9Q4J8pw
sh5pQne
5
Digital Design
Boolean Algebra
o Boolean algebra is a two-valued type of switching algebra
o Switching algebra represents bistable electrical switching
circuits (On or Off)
o Boolean algebra is defined by a set of elements, B, and there
are two main operators (AND, OR)
o Binary operators (two arguments involved)
o AND “.”
o OR “+”
o Plus, one unary operator (only one argument involved)
o NOT “ � ” (Complement operator represented by an overbar)
3. Commutative Law
i. x+𝑦𝑦 = 𝑦𝑦 + 𝑥𝑥
ii. x� 𝑦𝑦 = 𝑦𝑦 � 𝑥𝑥
4. Distributive Law
i. 𝑥𝑥 � 𝑦𝑦 + 𝑧𝑧 = 𝑥𝑥 � 𝑦𝑦 + 𝑥𝑥 � 𝑧𝑧 (� 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 +)
ii. 𝑥𝑥 + 𝑦𝑦 � 𝑧𝑧 = (𝑥𝑥 + 𝑦𝑦) � (𝑥𝑥 + 𝑧𝑧) (+ 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 �)
5. For every element 𝑥𝑥 in the set B, there exists an element 𝑥𝑥̅ in the set B, such that
i. 𝑥𝑥 + 𝑥𝑥̅ = 1
ii. 𝑥𝑥 � 𝑥𝑥̅ = 0
(𝑥𝑥 is called the complement of 𝑥𝑥)
8
Digital Design
The Three Operators in Two-
Valued Boolean Algebra (B={0,1})
OR: 𝑨𝑨 + 𝑩𝑩 AND: 𝑨𝑨 � 𝑩𝑩 NOT: 𝑨𝑨
𝑨𝑨 𝑩𝑩 𝑨𝑨 + 𝑩𝑩 𝑨𝑨 𝑩𝑩 𝑨𝑨 � 𝑩𝑩 𝑨𝑨 𝑨𝑨
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1 A = 0 → 𝐴𝐴 = 1
A = 1 → 𝐴𝐴 = 0
0 + 0 = 0 0 � 0 = 0
0 + 1 = 1 0 � 1 = 0
1 + 0 = 1 1 � 0 = 0
1 + 1 = 1 1 � 1 = 1
1 𝐴𝐴 + 𝐴𝐴 = 𝐴𝐴 𝐴𝐴 � 𝐴𝐴 = 𝐴𝐴 Tautology Law
2 𝐴𝐴 + 1 = 1 𝐴𝐴 � 0 = 0 Union Law
4 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 𝐴𝐴 � 𝐵𝐵 � 𝐶𝐶 = 𝐴𝐴 � 𝐵𝐵 � 𝐶𝐶 Associative Law
= 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶
5 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴̅ � 𝐵𝐵� 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴̅ + 𝐵𝐵� De Morgan’s Law
6 𝐴𝐴 + 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴 𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴 Absorption Law
7 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵 𝐴𝐴 � 𝐴𝐴̅ + 𝐵𝐵 = 𝐴𝐴 � 𝐵𝐵
8 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� = 𝐴𝐴 � = 𝐴𝐴
(𝐴𝐴 + 𝐵𝐵)(𝐴𝐴 + 𝐵𝐵) Logical adjacency
9 ̅ + 𝐵𝐵𝐵𝐵
𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶 𝐴𝐴 + 𝐵𝐵 𝐴𝐴̅ + 𝐶𝐶 𝐵𝐵 + 𝐶𝐶 Consensus Law
̅
= 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶 = (𝐴𝐴 + 𝐵𝐵)(𝐴𝐴̅ + 𝐶𝐶)
1 1 1 1
11
Digital Design
Examples - Truth Table
Prove the De Morgan’s Law:
𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴̅ � 𝐵𝐵� 𝐴𝐴 � 𝐵𝐵 = 𝐴𝐴̅ + 𝐵𝐵�
A B 𝑨𝑨 + 𝑩𝑩 � � 𝑩𝑩
𝑨𝑨 � A B 𝑨𝑨 � 𝑩𝑩 � + 𝑩𝑩
𝑨𝑨 �
0 0 1 1 0 0 1 1
0 1 0 0 0 1 1 1
1 0 0 0 1 0 1 1
1 1 0 0 1 1 0 0
Prove : 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵 𝐴𝐴 � 𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴
A B � � 𝑩𝑩
𝑨𝑨 + 𝑨𝑨 𝑨𝑨 + 𝑩𝑩 A B 𝑨𝑨 � 𝑨𝑨 + 𝑩𝑩 𝑨𝑨
0 0 0 0 0 0 0 0
0 1 1 1 0 1 0 0
1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1
14
Digital Design
Truth Table – examples (cont.)
Prove : 𝐴𝐴 + 𝐵𝐵 � 𝐶𝐶 = (𝐴𝐴 + 𝐵𝐵) � (𝐴𝐴 + 𝐶𝐶)
15
Digital Design
But how do we
use these ideas?
Page 16
Design Example
Ben Bitdiddle is having a picnic. He won’t enjoy it if it
rains or if there are ants. Design a circuit that will output
TRUE only if Ben enjoys the picnic.
Solution
Inputs : A (Ants), B (Rain)
Output : E (Ben’s Enjoyment)
Minterm Maxterm
◦ Minterm is a product term that contains all – Maxterm is a sum term that contains all
variables in the function variables in the function
◦ AND all the variables – OR all the variables
◦ If the variable in truth table is “0”, take its
complement in the minterm – If the variable in truth table is “1”, take its
◦ Minterm is equal to 1 for that set of given complement in the maxterm
input – Maxterm is equal to 0 for that set of given
input
22
Digital Design
Truth Table CSOP or CPOS
A Boolean function is in canonical form if it is expressed as
◦ a sum of minterms (Canonical Sum Of Products - CSOP) or
◦ a product of maxterms (Canonical Product Of Sums - CPOS)
23
Digital Design
SOP and POS Truth Table
Are the following two Boolean functions same?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵�
𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
Let’s use truth tables to check:
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
A B E1 A B E2
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1
SOP: If any PRODUCT in SOP is “1”, the function is “1”. Otherwise, the function is “0”
POS: If any SUM in POS is “0”, the function is “0”. Otherwise, the function is “1”
SOP and POS are different ways to present the same Boolean function
25
Digital Design
SOP and POS Truth Table
Are the following two Boolean functions same?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵�
𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
Can we also prove this via Boolean algebra?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
27
Digital Design
Example-2: Non-Canonical Canonical
Form via Truth Table
Example: For the given Boolean function below, find a canonical minterm and
maxterm expression.
1) obtain the truth table from the given function
2) find minterm or maxterm expression from truth table (CSOP or CPOS)
𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ + 𝑦𝑦𝑧𝑧̅ Non Canonical form
Truth table:
x y z F Canonical minterm expression:
0 0 0 1
𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ 𝑦𝑦�𝑧𝑧̅ + 𝑥𝑥̅ 𝑦𝑦𝑧𝑧
� + 𝑥𝑥𝑦𝑦
̅ 𝑧𝑧̅ + 𝑥𝑥𝑦𝑦𝑧𝑧
̅ + 𝑥𝑥𝑥𝑥𝑧𝑧̅
0 0 1 1
0 1 0 1 (only contains the minterms that make the function = 1)
0 1 1 1
Canonical maxterm expression:
1 0 0 0
1 0 1 0 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧̅ (𝑥𝑥̅ + 𝑦𝑦� + 𝑧𝑧)̅
1 1 0 1 (only contains the maxterms that make the function = 0)
1 1 1 0
29
Digital Design
Example-3: Non-Canonical Canonical
Form via Postulates and Theorems
Example: For the given Boolean functions below, convert it to canonical minterm or
maxterm expression.
(*Using postulates/theorem to expand the given function to canonical form)
SOP CSOP: 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥𝑦𝑦 ̅ + 𝑥𝑥𝑥𝑥 For missing literals, complete
(CSOP – Canonical SOP) minterms through postulates:
= 𝑥𝑥𝑦𝑦
̅ � 1 + 𝑥𝑥 � 1 � 𝑧𝑧
= 𝑥𝑥𝑦𝑦̅ z + 𝑧𝑧̅ + 𝑥𝑥 𝑦𝑦 + 𝑦𝑦� 𝑧𝑧 A � 1 = 𝐴𝐴 𝑎𝑎𝑎𝑎𝑎𝑎 𝐴𝐴 + 𝐴𝐴̅ =
= 𝑥𝑥𝑦𝑦𝑧𝑧
̅ + 𝑥𝑥𝑦𝑦 ̅ 𝑧𝑧̅ + 𝑥𝑥𝑥𝑥𝑥𝑥 + 𝑥𝑥𝑦𝑦𝑧𝑧
� 1
1) express SOP as POS
1) a) complement twice
SOP CPOS: 𝐹𝐹 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑥𝑥𝑦𝑦
̅ + 𝑥𝑥𝑥𝑥 b) apply De Morgan’s law
(CSOP – Canonical POS)
̅ + 𝑥𝑥𝑥𝑥 a
= 𝑥𝑥𝑦𝑦 c) expand
d) re-apply De Morgan’s law
Use distribution postulate: = 𝑥𝑥 + 𝑦𝑦� 𝑥𝑥̅ + 𝑧𝑧̅ b 2) for missing literals, complete
𝐴𝐴 + 𝑩𝑩𝑪𝑪 = 𝐴𝐴 + 𝑩𝑩 𝐴𝐴 + 𝑪𝑪 maxterms through distribution
(A = incomplete sum,
= 𝑥𝑥 𝑥𝑥̅ + 𝑥𝑥 𝑧𝑧̅ + 𝑥𝑥̅ 𝑦𝑦� + 𝑦𝑦� 𝑧𝑧̅ c
postulate
C=NOT(B)=missing literal) = 𝑥𝑥 + 𝑦𝑦 𝑥𝑥̅ + 𝑧𝑧 𝑦𝑦 + 𝑧𝑧 d
x+𝑦𝑦 = (𝑥𝑥 + 𝑦𝑦) + 𝒛𝒛�𝒛𝒛 2) = 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧̅ ⋅ 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥̅ + 𝑦𝑦� + 𝑧𝑧
= (𝑥𝑥 + 𝑦𝑦 + 𝒛𝒛)(𝑥𝑥 + 𝑦𝑦 + 𝒛𝒛� ) ⋅ 𝑥𝑥 + 𝑦𝑦 + 𝑧𝑧 ⋅ 𝑥𝑥̅ + 𝑦𝑦 + 𝑧𝑧
30
Digital Design
Example-3 : SOP ⇔ POS (De Morgan’s)
Truth table: Applying De Morgan’s Law to CSOP of 𝑭𝑭𝟏𝟏 :
𝐴𝐴 𝐵𝐵 𝐶𝐶 𝐹𝐹1 𝐹𝐹𝟏𝟏
𝑭𝑭𝟏𝟏 = 𝑭𝑭𝟏𝟏 = 𝑭𝑭𝟏𝟏,𝑪𝑪𝑪𝑪𝑪𝑪𝑪𝑪
0 0 0 0 1
= 𝑨𝑨� 𝑩𝑩 � + 𝑨𝑨
� 𝑪𝑪 � 𝑩𝑩
� 𝑪𝑪 + 𝑨𝑨� 𝑩𝑩𝑩𝑩 + 𝑨𝑨𝑨𝑨𝑨𝑨
0 0 1 0 1 � 𝑩𝑩 � � 𝑨𝑨
� 𝑪𝑪 � 𝑩𝑩
� 𝑪𝑪 � 𝑨𝑨
� 𝑩𝑩𝑩𝑩 � 𝑨𝑨𝑨𝑨𝑨𝑨
= 𝑨𝑨
0 1 0 1 0 = 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 � 𝑨𝑨 + 𝑩𝑩 � (𝑨𝑨
� + 𝑪𝑪 � + 𝑩𝑩 �
� + 𝑪𝑪)
0 1 1 0 1
1 0 0 1 0
Now, find CPOS of F1 directly from truth table:
1 0 1 1 0 clearly the
1 1 0 1 0 𝑭𝑭𝟏𝟏 𝑨𝑨, 𝑩𝑩, 𝑪𝑪 CPOS of F1 same
� 𝑨𝑨 + 𝑩𝑩
= 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 � (𝑨𝑨
� + 𝑪𝑪 � + 𝑩𝑩 �
� + 𝑪𝑪)
1 1 1 0 1
CPOS can be obtained from CSOP (and vice versa) by
applying De Morgan’s Law!
31
Digital Design
Pre-Lab Exercise
The following task is required to be implemented :
oWhen switch A turns on, only LED1 lights up.
oWhen switch B turns on, only LED2 lights up.
oWhen both switches A and B turn on, LED1, LED2, and LED3 light up.
LED1 =
LED2 =
LED3 =
LED1 =
LED2 =
LED3 =
37
Digital Design
Guidelines for Simplification of
Boolean Function (in SOP)
Three most used theorems:
(1) 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� = 𝐴𝐴 (Logical adjacency)
(2) 𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵
(3) 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶̅ + 𝐵𝐵𝐵𝐵 = 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶
̅ (Consensus)
38
Digital Design
LOGIC GATES
AND, OR, NOT, XOR gates
40
Digital Design
Logic Gate Introduction
Logic gates are digital circuits that implement the Boolean
operations.
Basic Logic Gates:
Gate Symbol Function Verilog Gate Symbol Function Verilog
(F) Operator (F) Operator
A
AND A F 𝐴𝐴 � 𝐵𝐵 F=A&B NAND F 𝐴𝐴 � 𝐵𝐵 F = ~(A & B)
B B
41
Digital Design
AND and NAND Gates
A Truth Table (AND, NAND):
F 𝑭𝑭 = 𝑨𝑨 � 𝑩𝑩
B AND NAND
A B 𝑨𝑨 � 𝑩𝑩 𝑨𝑨 � 𝑩𝑩
A
F 𝑭𝑭 = 𝑨𝑨 � 𝑩𝑩 0 0 0 1
B
1 0 0 1
A
F 0 1 0 1
B
1 1 1 0
bubble = complement
AND NAND
F is TRUE only when both A and B are • F is FALSE only if both A and
TRUE B are TRUE
OR NOR
• F is FALSE only when both A and B • F is TRUE only if both A and
are FALSE B are FALSE
XOR XNOR
• F is TRUE if A ≠ B • F is TRUE if A = B
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
# of Gates needed = # of Gates needed =
46
Digital Design
Cont’d Ben Bitdiddle’s Example
We developed the following two Boolean expressions for Ben :
𝑬𝑬 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵�
𝑬𝑬 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
How do we implement them?
𝑬𝑬𝟏𝟏 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴̅ � 𝐵𝐵� 𝑬𝑬𝟐𝟐 𝑨𝑨, 𝑩𝑩 = 𝐴𝐴 + 𝐵𝐵� . 𝐴𝐴̅ + 𝐵𝐵 . 𝐴𝐴̅ + 𝐵𝐵�
# of Gates needed = # of Gates needed =
𝐴𝐴
𝐴𝐴 𝐵𝐵
𝐸𝐸1
𝐵𝐵
𝐸𝐸2
47
Digital Design
Implementation using Logic Gates –
Sketch Method
- Implement the following Boolean functions to logic gates, assume that
the maximum number of inputs of a gate is 4.
𝐹𝐹 𝑤𝑤, 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑤𝑤
� 𝑥𝑥𝑧𝑧
̅ + 𝑤𝑤𝑥𝑥𝑥𝑥
� + 𝑤𝑤𝑤𝑤𝑤𝑤 + 𝑥𝑥𝑥𝑥𝑥𝑥
𝑤𝑤 𝑥𝑥 𝑦𝑦 𝑧𝑧
𝑤𝑤
� �
𝒙𝒙
Input signals needed?
𝑤𝑤, 𝑤𝑤,
� 𝑥𝑥, 𝑥𝑥,̅ 𝑦𝑦, 𝑧𝑧
Types / # of Gates
needed?
AND – 3 inputs
OR – 4 inputs
Schematic drawn in
PLA configuration
# of gates = 7
module func(a,b,c,d,F);
input a, b, c, d;
output F;
assign F = a & b & ~c | a & b & c | b & c & d | ~a & c & d | a & ~b & ~c & d;
endmodule
51
Digital Design
Boolean Function Simplification using
Algebra Manipulation
52
Digital Design
Ex - Boolean Function Simplification
(Relook at the second example):
gate count = 6
gate count = 11 (45.5% reduction!)
53
Digital Design
Ex - Boolean Function Simplification
gate count = 3
gate count = 8
(62.5% reduction!)
54
Digital Design
Timing
VDD
B VDD/2
Gnd
We often think of digital signals If we zoom in, things are quite different!
changing instantaneously…
Critical Path
o Assuming the below tpds, which path below is the slowest?
Gate tpd
NOT 0.3ns
2-input OR 0.6ns
3-input OR 0.8ns
3-input AND 0.7ns
4-input AND 0.9ns
o The Critical Path limits the speed at which the entire circuit operates
eg. the slowest path in circuit!
o Total tpd of a combinational circuit is sum of tpd through each element
on the critical path.
Which is the critical path here?
Positive &
Negative Logic
59
Digital Design
Example – Implementation in Positive
Logic
Implement the following Boolean function in positive logic.
A.H
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶 B.H
F.H
A.H
C.H
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶
61
Digital Design
If you could only
choose one gate…
SELF-READING
𝐴𝐴 ⋅ 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵
De Morgan’s law
- bubbles at the input of an OR gate can be “pushed” at its output, and the
gate is transformed into a NAND gate (similarly, NOR becomes AND)
A.L
𝐴𝐴 + 𝐵𝐵 = 𝐴𝐴 ⋅ 𝐵𝐵 F.L
B.L
De Morgan’s law
- and vice versa, of course:
alternate gate
A.L representations
F.L
B.L
𝐹𝐹 = 𝐴𝐴 � 𝐵𝐵 + 𝐴𝐴 � 𝐶𝐶
AND
Step 1: 𝐴𝐴 � 𝐵𝐵 NOR
Step 2: A
A (add the negation B F
B where needed for
the correct function) A
A C
C 𝐴𝐴 � 𝐶𝐶
redundant... NOR
A
Step 3:
(i) Replace AND gate with NOR gate B F
(ii) balance the bubbles using inverters
to maintain the correct functionality A
C gate count = 7
NOR
64
Digital Design
Summary
Logic gate is a circuit that implement Boolean operations
AND, NAND, OR, NOR, XOR, XNOR gates
Boolean function implementation using logic gates
Boolean function simplification using algebra postulates and theorems
Timing
Positive and negative logic
◦ Definition
◦ Conversion between positive and negative logic
◦ Gates with mixed logic
Universal Gates
65
Digital Design
EE2026
Digital Design
MODELING STYLES IN VERILOG
Chua Dingjuan elechuad@nus.edu.sg
Pictorial Summary of Module Structure
2
Recall where we last left off….
module box( input a, b,
input [1:0] c, Net / Variable Number Value in
output [3:0] y ); Name of bits? dec / bin
wire tmp; a 1 1 / 1’b1
reg [1:0] one = 3; b 1 0 / 1’b0
reg two;
c 2 2 / 2’b10
integer three = 1;
tmp 1 Z / 1’bZ
assign y[3] = one[0]; one 2 3 / 2’b11
assign y[2:1] = a + c; two 1 X / 1’bX
assign y[0] = ( a > b ); three 32 1 / 32’h00000001
y 4 15 / 4’b1111
endmodule
Page 4
Continuous Assignment (Dataflow)
assign statements are often used to model combinational logic
A P module bigbox (input a, b, c, d,
B output z);
Q wire p, q, r; internal connections
C Z
assign z = p ^ q ^ r; 1 ∆ ∆
Order? assign q = ~c; 2
D not
not B 1 0
R important assign p = a & b; 3
important
assign r = ~(c | d); 4 P 1 0
endmodule Z 1 0
endmodule
Page 6
Useful Operators
o Boolean (bit-wise), logical, arithmetic, concatenation.
o Use brackets for readability, take note if *synthesizable.
Operator Description Examples: a = 4’b1010, b=4’b0000
Page 8
2
always @ (s, d)
begin
if (s == 1’b0)
y = d[0];
else
y = d[1];
end
endmodule
Page 10
Some notes on: always
o always@(*) includes all input signals that are read in current block.
Registers
o Anything assigned in an always block must be declared as type reg
o In Verilog, the term register (reg) simply means a variable that can
hold a value. (cf. wire)
Page 11
Bad Example 3 – Multi-Driven Net
module notgood(….); There are two conflicting instructions
always @ (*) presented.
Page 12
Ref – Conditional Statements
If - else if - else case
if ( expr ) case ( expr )
statement;
value1 : statement;
value2 : statement;
if ( expr ) value3 : statement;
statement; ...
else default : statement;
statement;
endcase
if ( expr )
statement;
else if ( expr )
statement;
else if ( expr )
statement;
else
statement;
Page 13
Equivalence
module mux21( input s, input [1:0] d, output reg y);
always @ (s, d)
begin
if (s == 1’b0) d[0]
y= d[0]; MUX y
else d[1]
y= d[1];
end s
endmodule
endmodule
Page 14
Equivalence…
A
B
C Z
D
module bigbox module bigbox
(input a,b,c,d, output z); (input a,b,c,d, output ___
reg z);
reg p,q,r;
wire p, q, r; always @ ( a,b,c,d )
begin
assign q = ~c; q = ~c;
assign z = p ^ q ^ r; p = a & b;
assign p = a & b; r = ~(c | d);
assign r = ~(c | d); z = p ^ q ^ r;
end
endmodule endmodule
Page 15
Structural Modeling – Primitives
Structural modeling can be used to connect multiple modules and gates.
Verilog provides a standard set of primitive such as basic logic gates.
Dataflow
module bigbox (input a,b,c,d, output z);
endmodule
Page 16
Structural Modeling
Structural modeling can be used to connect multiple modules via port
connection by name and position.
module mux21( input s, module mux41( input [1:0] s,
input [1:0] d, input [3:0] d,
output y); output y);
… … … ?
assign y = s ? d[1] : d[0];
endmodule
endmodule
mux41
d[3]
mux21
d[1] d[2] y
d[0] y d[1]
d[0]
s
s[1] s[0]
Page 17
Structural Modeling
For example, a 4-to-1 multiplexer can also be implemented by combining
several 2-to-1 multiplexers. How can we write this in Verilog?
mux21
mux41
d[3] d[1] y
d[3] d[2] d[0] mux21
s
d[2] y d[1]
y y
d[1] s[0]
d[0]
d[0] mux21 s
d[1] d[1] y
d[0] d[0]
s[1] s[0] s
s[0] s[1]
Page 18
Structural Modeling
For example, a 4-to-1 multiplexer can also be implemented by combining
several 2-to-1 multiplexers.
module mux21( input s, input [1:0] d,
output y);
assign y = s ? d[1] : d[0];
mux21 endmodule
d[3] d[1] out1
y
Port Connection by Position
d[2] d[0] mux21 module mux41( input [1:0] s,
s
d[1] input [3:0] d,
y y output y);
d[0]
s wire out1, out2;
mux21
d[1] d[1] y
//check for port order!
out2 mux21 u1 (s[0], d[3:2], out1);
d[0] d[0]
s mux21 u2 (s[0], d[1:0], out2);
Page 19
Structural Modeling
For example, a 4-to-1 multiplexer can also be implemented by combining
several 2-to-1 multiplexers. Port Connection by Name
module mux41( input [1:0] s,
input [3:0] d,
output y);
endmodule
Page 20
Example - Structural Modeling
o For modular designs, the top design is often specified as interconnected
blocks.
o Two examples below demonstrate port connection by position / name.
module mymodule (input a, b, output x); module yourmodule (input c, d, output z);
... …
endmodule endmodule
endmodule
Page 21
Recall Simulation?
module savetheworld (input a1, … z1,
a1 a2
output a2, …,z2); save
the
………. ………. ………. ………. ……….
z1 world z2
………. ………. ………. ………. ………. .v
………. ………. ………. ………. ……….
endmodule
module mux_test(); s
reg [1:0] ip = 0;
mux_test
reg sel = 0;
wire op; mux21
ip
d[1]
mux21 dut (sel, ip, op); y op
2’b10 d[0]
initial begin
ip = 2’b10;
sel = 1’b0; s
#10; //wait 10 time units sel
end 1’b0
endmodule
Page 23
EE2026
Digital Design
MODELING STYLES IN VERILOG
Chua Dingjuan elechuad@nus.edu.sg
Ask Week 3 Questions here…
You can ask questions during the week using
slido here :
https://app.sli.do/event/7Y43tp4vqnHWjDqX
S7FXiA
3
Digital Design
Recall where we last left off….
module box( input a, b,
input [1:0] c, Net / Variable Number Value in
output [3:0] y ); Name of bits? dec / bin
wire tmp; a 1 1 / 1’b1
reg [1:0] one = 3; b 1 0 / 1’b0
reg two;
c 2 2 / 2’b10
integer three = 1;
tmp 1 Z / 1’bZ
endmodule Z 1 0
endmodule
Registers
o Anything assigned in an always block must be declared as type reg
o In Verilog, the term register (reg) simply means a variable that can
hold a value. (cf. wire)
if ( expr )
statement;
else if ( expr )
statement;
else if ( expr )
statement;
else
statement;
always @ (s, d)
begin
if (s == 1’b0) d[0]
y= d[0]; MUX y
else d[1]
y= d[1];
end s
endmodule
endmodule
D R
module bigbox module bigbox
(input a,b,c,d, output z); (input a,b,c,d, output ___ z);
wire p, q, r; always @ ( )
begin
assign q = ~c;
assign z = p ^ q ^ r;
assign p = a & b;
assign r = ~(c | d);
end
endmodule endmodule
Digital Design Page 22
Structural Modeling – Primitives
Structural modeling can be used to connect multiple modules and gates.
Verilog provides a standard set of primitive such as basic logic gates.
Dataflow
module bigbox (input a,b,c,d, output z);
endmodule
mux41
d[3]
mux21
d[1] d[2] y
d[0] y d[1]
d[0]
s
s[1] s[0]
Digital Design Page 26
Structural Modeling
For example, a 4-to-1 multiplexer can also be implemented by combining
several 2-to-1 multiplexers. How can we write this in Verilog?
mux21
mux41
d[3] d[1] y
d[3] d[2] d[0] mux21
s
d[2] y d[1]
y y
d[1] s[0]
d[0]
d[0] mux21 s
d[1] d[1] y
d[0] d[0]
s[1] s[0] s
s[0] s[1]
d[1] d[1] y
//check for port order!
out2 mux21 u1 (s[0], d[3:2], out1);
d[0] d[0]
s mux21 u2 ( );
mux21 u3 ( );
s[0] s[1]
endmodule
endmodule
endmodule
module mux_test(); s
reg [1:0] ip = 0;
mux_test
reg sel = 0;
wire op; mux21
ip
d[1]
mux21 dut (sel, ip, op); y op
2’b10 d[0]
initial begin
ip = 2’b10;
sel = 1’b0; s
#10; //wait 10 time units sel
end 1’b0
endmodule
https://app.sli.do/event/ePPnicViz9oMHb8N
AWu4WX
Synthesized Schematic
RTL Schematic
Step 2
◦ Implement the simplified Boolean function using logic gates
◦ Minimize the gate counts
Why minimization?
◦ Cost, power, performance, size, reliability, …
5
Digital Design
Karnaugh Map (K-Map)
K-map is a diagram that consists of a number of squares
Each square represent one minterm (or maxterm) of a Boolean function
The Boolean function (SOP) can be expressed as a sum of minterms in the map
n-variables Boolean function has maximum 2n minterms
Two-variable K-map: m0 → 00 → 𝐴 𝐵
(maximum 4 minterms) m1 → 01 → 𝐴 𝐵
m2 → 10 → 𝐴 𝐵
B squares B B m3 → 11 → 𝐴𝐵
A 𝐵ത B A 0 1 0 1
A
𝐴ҧ 𝐴ҧ𝐵ത ҧ
𝐴𝐵 0 00 01 0 m0 m1
A 𝐴𝐵ത 𝐴𝐵 1 10 11 1 m2 m3
6
Digital Design
Truth table → K-map
A B F B
0 0 0 A 0 1
0 1 0 0 0 0
1 0 1
1 1 1
1 1 1
7
Digital Design
Three- and four-Variable K-Maps
*Note that any two adjacent squares differ by only one literal
𝐹 = 𝐴𝐵 + 𝐴𝐵 + 𝐴𝐵ത
𝑭 =?
in SOP: write F as sum of the minterms
(squares with “1”)
9
Digital Design
Ex - Boolean function in K-map (cont.)
Represent the following function on K-map: Write the Boolean expression
𝐹 = 𝐴𝐵𝐶 + 𝐴𝐵 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത + 𝐴ҧ𝐵ത 𝐶ҧ for the function in K-map:
BC
BC A 00 01 11 10
A 00 01 11 10
0 1 0 0 0
0 1 1 1 0
1 0 1 0 0
1 0 0 0 1
ҧ 𝐶𝐷
ҧ + 𝐴ҧ𝐵𝐶𝐷
𝑭 =? 𝑭 = 𝐴 ⋅ 𝐵 ⋅ 𝐶 + 𝐴 ⋅ 𝐵ത ⋅ 𝐶
𝐹 = 𝐴𝐵 ത + 𝐴𝐵 𝐶ҧ 𝐷
ഥ + 𝐴ҧ𝐵𝐶
ത 𝐷ഥ
ത 𝐷
+𝐴𝐵𝐶 ഥ + 𝐴𝐵𝐶𝐷
ത + 𝐴𝐵ത 𝐶𝐷ҧ + 𝐴ҧ𝐵ത 𝐶ҧ 𝐷
ഥ
CD 00 01 11 10
CD 00 01 11 10 AB
AB 00 0 1 0 0
00 1 0 1 1 01 0 0 0 1
01 0 1 0 0 11 0 1 0 0
11 1 0 0 0 10 0 0 0 0
10 0 1 1 1
𝑭 =? 𝑭 = 𝐴. 𝐵. 𝐶. 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷
10
Digital Design
Boolean function in K-map (cont.)
What about Boolean function in non-canonical form?
Example-1: Example-2:
𝐹 = 𝐴𝐵 + 𝐴𝐵 𝐶ҧ + 𝐴ҧ𝐵𝐶
ത 𝐹 = A + 𝐴ҧ𝐵𝐶𝐷
ത + 𝐵 𝐶ҧ 𝐷
ഥ
CD 00 01 11 10
𝐴𝐵 = 𝐴𝐵 𝐶 + 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵𝐶 AB
00
BC 01
A 00 01 11 10
0 11
1 10
Or 𝐴𝐵 → 1 for 𝐶 = 0 𝑜𝑟 1
or just fill the truth table and derive the K-map
11
Digital Design
Boolean function simplification
using K-map
Boolean function (SOP) simplification using K-map
Simplify: 𝐹 = 𝐴ҧ𝐵ത + 𝐴𝐵 + 𝐴𝐵
Minimum Sum of
𝐴𝐵 + 𝐴ҧ𝐵ത = 𝐴 𝐵 + 𝐵ത = 𝐴 Products
B
A 0 1 eliminated MSOP:
𝐹 =𝐴+𝐵
0 1 1
1 0 1
𝐴𝐵 + 𝐴𝐵 = 𝐵 𝐴ҧ + 𝐴 = 𝐵
2-cell group
eliminated
Alternatively,
𝐹 = 𝐴𝐵 + 𝐴𝐵 + 𝐴ҧ𝐵ത *The variable that changes value in the
= 𝐴ҧ + 𝐴𝐵 group is eliminated, or the variable that
= 𝐴ҧ + 𝐵 doesn’t change value in the group remains
12
Digital Design
How do we find
MSOP using
Kmaps?
14
Digital Design
Three-variables: Application Time!
𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ + 𝐴ҧ𝐵𝐶 ҧ 𝐶ҧ + 𝐴𝐵 𝐶ҧ
ത + 𝐴𝐵𝐶 + 𝐴𝐵 𝐹 = 𝐴ҧ𝐵𝐶
ത + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵𝐶
ത + 𝐴ҧ𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ
BC BC
A
00 01 11 10 00 01 11 10
A
0 1 1 1 1 0 1 1 0 1
1 0 0 0 1 1 1 1 0 0
𝐹𝑀𝑆𝑂𝑃 = 𝐹𝑀𝑆𝑂𝑃 =
Four-variables:
𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴ҧ𝐵𝐶𝐷
ത ҧ 𝐶𝐷
+ 𝐴𝐵 ҧ + 𝐴𝐵𝐶𝐷
ҧ 𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴ҧ𝐵𝐶
ത 𝐷 ҧ 𝐶𝐷
ഥ + 𝐴𝐵 ҧ + 𝐴𝐵𝐶𝐷
ҧ
+𝐴𝐵 𝐶𝐷 ҧ + 𝐴𝐵𝐶𝐷 + 𝐴𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴𝐵𝐶𝐷
ത +𝐴𝐵 𝐶𝐷 ҧ + 𝐴𝐵𝐶𝐷 + 𝐴𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴𝐵𝐶
ത 𝐷
ഥ
CD 00 CD 00 01 11 10
01 11 10 AB
AB 00 1 0 0 1
00 1 0 1 0
01 0 1 1 0 01 0 1 1 0
11 0 1 1 0 11 0 1 1 0
10 1 0 1 0 10 1 0 0 1
𝐹𝑀𝑆𝑂𝑃 = 𝐹𝑀𝑆𝑂𝑃 =
Digital Design 15
Boolean function (SOP) simplification
using K-Map (cont.)
Three-variables: 𝐴ҧ (B and C eliminated)
BC
A
00 01 11 10
𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ + 𝐴ҧ𝐵𝐶 ҧ 𝐶ҧ + 𝐴𝐵 𝐶ҧ
ത + 𝐴𝐵𝐶 + 𝐴𝐵
0 1 1 1 1
𝐹 = 𝐴ҧ + 𝐵 𝐶ҧ 1 0 0 0 1
𝐹 = 𝐵ത + 𝐴ҧ𝐶ҧ 0 1 1 0 1
𝐴ҧ𝐵𝐶
ത + 𝐴𝐵ത 𝐶ҧ + 𝐴𝐵𝐶
ത + 𝐴ҧ𝐵ത 𝐶ҧ → 𝐴ҧ𝐵ത 𝐶 + 𝐶ҧ + 𝐴𝐵ത 𝐶ҧ + 𝐶
𝐴ҧ + 𝐴 𝐵ത → 𝐵ത 1 1 1 0 0
𝐴ҧ𝐵ത 𝐶ҧ + 𝐴𝐵
ҧ 𝐶ҧ → 𝐴ҧ 𝐵ത + 𝐵 𝐶ҧ → 𝐴ҧ𝐶ҧ
𝐴ҧ𝐶ҧ (B is eliminated)
Group the adjacent cells where only one variable changes 16
Digital Design
value so that it can be eliminated
Minimization (MSOP) using K-Map
(cont.)
Four-variables: 𝐵ത 𝐶ҧ 𝐷
ഥ 𝐵𝐷 𝐶𝐷
CD 00 01 11 10
𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴ҧ𝐵𝐶𝐷
ത ҧ 𝐶𝐷
+ 𝐴𝐵 ҧ + 𝐴𝐵𝐶𝐷
ҧ AB
ҧ + 𝐴𝐵𝐶𝐷 + 𝐴𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴𝐵𝐶𝐷
ത 00 1 0 1 0
+𝐴𝐵 𝐶𝐷
01 0 1 1 0
11 0 1 1 0
𝐹𝑀𝑆𝑂𝑃 = 𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐵𝐷 + 𝐶𝐷
1 0 1 0
10
𝐵ത 𝐷
ഥ 𝐵𝐷
CD 00 01 11 10
𝐹 = 𝐴ҧ𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴ҧ𝐵𝐶
ത 𝐷 ҧ 𝐶𝐷
ഥ + 𝐴𝐵 ҧ + 𝐴𝐵𝐶𝐷
ҧ AB
+𝐴𝐵 𝐶𝐷 ҧ + 𝐴𝐵𝐶𝐷 + 𝐴𝐵ത 𝐶ҧ 𝐷
ഥ + 𝐴𝐵𝐶
ത 𝐷
ഥ 00 1 0 0 1
01 0 1 1 0
11 0 1 1 0
𝐹𝑀𝑆𝑂𝑃 = 𝐵ത 𝐷
ഥ + 𝐵𝐷
10 1 0 0 1
17
Digital Design
Minimization (MPOS) using K-Map
maxterm-input correspondence: complement literals if 1
Boolean function in POS:
CD 00 01 11 10 𝐶ҧ + 𝐷
ഥ
𝐹 = 𝐴+𝐵+𝐶+𝐷 𝐴+𝐵+𝐶+𝐷 ҧ AB
𝐴 + 𝐵ത + 𝐶 + 𝐷 𝐴 + 𝐵ത + 𝐶ҧ + 𝐷 00 1 0 1 0
𝐴ҧ + 𝐵ത + 𝐶 + 𝐷 𝐴ҧ + 𝐵ത + 𝐶ҧ + 𝐷 01 0 1 1 0
(𝐴ҧ + 𝐵 + 𝐶 + 𝐷)(
ഥ 𝐴ҧ + 𝐵 + 𝐶ҧ + 𝐷)
11 0 1 1 0
10 1 0 1 0
ഥ ⋅ 𝐶ҧ + 𝐷 ⋅ (𝐵ത + 𝐷)
𝐹𝑀𝑃𝑂𝑆 = 𝐵 + 𝐶 + 𝐷
𝐴+𝐵+𝐶+𝐷 ഥ ⋅ 𝐴ҧ + 𝐵 + 𝐶 + 𝐷
ഥ
POS simplification using K-map: = 𝐴𝐴ҧ + 𝐴 ⋅ 𝐵 + 𝐶 + 𝐷ഥ
+ 𝐵+𝐶+𝐷 ഥ ⋅ 𝐴ҧ + 𝐵 + 𝐶 + 𝐷
ഥ
Group the squares that only contains “0”
⋅ 𝐵+𝐶+𝐷 ഥ = 𝐵+𝐶+𝐷 ഥ
Form an OR term (sum) for each group, instead of a product
Value “1”, instead of “0”, represent complement of the variable
Follow similar grouping rules for SOP
Either SOP or POS can be used to implement the Boolean function, depending on which gives
more efficient implementation.
summarizing: proceed as SOP, but group 0’s instead of 1’s (square = maxterm)
+ complement the values in row-col. to find maxterm associated with square
Digital Design
18
Invalid groupings
CD 00 01 11 10 CD 00 01 11 10
AB AB
00 1 0 1 0 00 0 1 0 1
01 0 1 1 0 01 1 0 0 1
11 0 1 1 0 11 0 1 1 1
10 1 0 1 0 10 0 1 1 1
Squares in the group are not in power of two not horizontal or vertical
19
Digital Design
Application Example - Boolean
Function Simplification
𝐹 𝑎, 𝑏, 𝑐, 𝑑 = 𝑎𝑏𝑐ҧ + 𝑎𝑏𝑐 + 𝑏𝑐𝑑 + 𝑎𝑐𝑑 ത
ത + 𝑎𝑏𝑐𝑑
= 𝑎𝑏 𝑐ҧ + 𝑐 + 𝑏𝑐𝑑 + 𝑎𝑐𝑑ത + 𝑎𝑏𝑐𝑑ത (𝐴 + 𝐴ҧ = 1)
= 𝑎 𝑏 + 𝑏ത 𝑐𝑑 ҧ + 𝑏𝑐𝑑 + 𝑎𝑐𝑑
ത (𝐴 + 𝐴ҧ ∙ 𝐵 = 𝐴 + 𝐵)
= 𝑎 𝑏 + 𝑐𝑑 ҧ + 𝑏𝑐𝑑 + 𝑎𝑐𝑑
ത
= 𝑎𝑏 + 𝑎ത 𝑐𝑑 + 𝑏 𝑐𝑑 + 𝑎𝑐𝑑 ҧ (𝐴𝐵 + 𝐴𝐶 ҧ + 𝐵𝐶 = 𝐴𝐵 + 𝐴𝐶)
ҧ - consensus
= 𝑎𝑏 + 𝑎𝑐𝑑
ത + 𝑎𝑐𝑑 ҧ
20
Digital Design
Design Example - 7-Seg Decoder
A 7-segment display decoder takes a 4-bit input, D3:0, and produces seven outputs to
control LEDs, to display a digit from 0 to 9. The LEDs are named a through g, or Sa – Sg.
Write a truth table for the output Sa and derive
D3 D2 D1 D0 Sa
the MSOP.
0 0 0 0 1
You may assume illegal input values (10–15) will
0 0 0 1 0
never appear and use don’t cares.
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
Digital Design
1 1 1 1 Page 21 X
Design Example - 7-Seg Decoder
00 01 11 10
00
01 𝑆𝑎 =
11
10
oWe often assume that all combinations of input are valid (e.g. 3 inputs = 8
different input combinations that makes the function equal to 0 or 1)
oThere are applications in which some variable combinations never appear.
oThese conditions are called don’t-care conditions.
oDon’t-care condition is marked with “X” in K-map
oFor minimization, X can take either “1” or “0”.
Digital Design Page 22
Design Example - 7-Seg Decoder
D3D2
D1D0 00 01 11 10 𝑫𝟐 . 𝑫𝟎
00 1 0 X 1
01 0 1 X 1 𝑆𝑎 = 𝐷2 𝐷0 + 𝐷2 𝐷0 + 𝐷1 + 𝐷3
𝑫𝟑
11 1 1 X X
10 1 1 X X
𝑫𝟏
𝑫 𝟐 . 𝑫𝟎
oWe often assume that all combinations of input are valid (e.g. 3 inputs = 8
different input combinations that makes the function equal to 0 or 1)
oThere are applications in which some variable combinations never appear.
oThese conditions are called don’t-care conditions.
oDon’t-care condition is marked with “X” in K-map
oFor minimization, every X can take either “1” or “0”.
Digital Design Page 23
EE2026
Digital Design
LOGIC MINIMIZATION, KARNAUGH MAPS
Chua Dingjuan elechuad@nus.edu.sg
In Lab 1… Design Workflow!
idea! .v (verilog)
assign LED1 = (A & ~B) | (A & B);
Synthesized Schematic
RTL Schematic
Page 2
LOGIC MINIMIZATION
Karnaugh Maps
Gate-Level Logic Design
Step 1 (simplify the Boolean function)
◦ Simplify the Boolean function to be implemented
◦ Methods of simplification
◦ Postulates and theorem
◦ Karnaugh Map
Step 2
◦ Implement the simplified Boolean function using logic gates
◦ Minimize the gate counts
Why minimization?
◦ Cost, power, performance, size, reliability, …
4
Karnaugh Map (K-Map)
K-map is a diagram that consists of a number of squares
Each square represent one minterm (or maxterm) of a Boolean function
The Boolean function (SOP) can be expressed as a sum of minterms in the map
n-variables Boolean function has maximum 2n minterms
Two-variable K-map: m0 00 𝐴𝐴 𝐵𝐵
(maximum 4 minterms) m1 01 𝐴𝐴 𝐵𝐵
m2 10 𝐴𝐴 𝐵𝐵
B squares B B m3 11 𝐴𝐴𝐴𝐴
A 𝐵𝐵� B A 0 1 0 1
A
𝐴𝐴̅ 𝐴𝐴̅𝐵𝐵� ̅
𝐴𝐴𝐵𝐵 0 00 01 0 m0 m1
A 𝐴𝐴𝐵𝐵� 𝐴𝐴𝐵𝐵 1 10 11 1 m2 m3
5
Truth table K-map
A B F B
0 0 0 A 0 1
0 1 0 0 0 0
1 0 1
1 1 1
1 1 1
6
Three- and four-Variable K-Maps
*Note that any two adjacent squares differ by only one literal
𝑭𝑭 =?
in SOP: write F as sum of the minterms
(squares with “1”)
𝑭𝑭 = 𝐴𝐴𝐵𝐵 + 𝐴𝐴𝐵𝐵�
8
Ex - Boolean function in K-map (cont.)
Represent the following function on K-map: Write the Boolean expression
𝐹𝐹 = 𝐴𝐴𝐵𝐵𝐵𝐵 + 𝐴𝐴𝐴𝐴𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ for the function in K-map:
BC
BC A 00 01 11 10
A 00 01 11 10
0 1 0 0 0
0 1 1 1 0
1 0 1 0 0
1 0 0 0 1
̅ 𝐶𝐶𝐷𝐷
̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶𝐶𝐶
𝑭𝑭 =? 𝑭𝑭 = 𝐴𝐴 ⋅ 𝐵𝐵 ⋅ 𝐶𝐶 + 𝐴𝐴 ⋅ 𝐵𝐵� ⋅ 𝐶𝐶
𝐹𝐹 = 𝐴𝐴𝐵𝐵 � + 𝐴𝐴𝐴𝐴 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝐷𝐷�
� 𝐷𝐷
+𝐴𝐴𝐵𝐵𝐶𝐶 � + 𝐴𝐴𝐵𝐵𝐶𝐶𝐶𝐶
� ̅ + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
+ 𝐴𝐴𝐵𝐵� 𝐶𝐶𝐷𝐷 �
CD 00 01 11 10
CD 00 01 11 10 AB
00 0 1 0 0
AB
00 1 0 1 1 01 0 0 0 1
01 0 1 0 0 11 0 1 0 0
11 1 0 0 0 10 0 0 0 0
10 0 1 1 1
𝑭𝑭 =? 𝑭𝑭 = 𝐴𝐴. 𝐵𝐵. 𝐶𝐶. 𝐷𝐷 + 𝐴𝐴𝐵𝐵𝐵𝐵𝐷𝐷 + 𝐴𝐴𝐴𝐴𝐶𝐶𝐷𝐷
9
Boolean function in K-map (cont.)
What about Boolean function in non-canonical form?
Example-1: Example-2:
10
Boolean function simplification
using K-map
Boolean function (SOP) simplification using K-map
0 1
𝐴𝐴𝐵𝐵 + 𝐴𝐴𝐴𝐴 = 𝐵𝐵 𝐴𝐴̅ + 𝐴𝐴 = 𝐵𝐵
2-cell group 1
eliminated
Alternatively,
𝐹𝐹 = 𝐴𝐴𝐵𝐵 + 𝐴𝐴𝐴𝐴 + 𝐴𝐴̅𝐵𝐵� *The variable that changes value in the
= 𝐴𝐴̅ + 𝐴𝐴𝐴𝐴 group is eliminated, or the variable that
= 𝐴𝐴̅ + 𝐵𝐵 doesn’t change value in the group remains
11
Minimization (MSOP) using K-Map
(cont.)
*** K-Map Grouping Rules *** :
• Group all squares that contains “1”.
• Groups must be either horizontal or vertical (diagonal is invalid), but can wrap
around edges of the map.
• Group size is always 2n , that is, 2, 4, 8, …
• Group should be as large as possible (contains as many as squares with “1” as
possible)
• Simplified term retains variables that don’t change value.
• A 1 in may be circled multiple times if doing so allows fewer circles to be used.
• Minimum essential number of groupings to cover all the “1”s.
Four-variables: �
𝐷𝐷 𝐵𝐵
CD 00 01 11 10
𝐹𝐹 = 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝐷𝐷 ̅ 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴𝐵𝐵 � + 𝐴𝐴𝐵𝐵̅ 𝐶𝐶𝐷𝐷
̅ AB
̅ ̅ 𝐷𝐷� + 𝐴𝐴𝐴𝐴 𝐶𝐶̅ 𝐷𝐷 ̅
� + 𝐴𝐴𝐴𝐴 𝐶𝐶𝐷𝐷 00 1 0 0 1
+𝐴𝐴𝐵𝐵𝐵𝐵𝐵𝐵 + 𝐴𝐴𝐵𝐵𝐵𝐵
+𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐴𝐴𝐴𝐴 𝐷𝐷 � + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴𝐵𝐵𝐶𝐶
� 𝐷𝐷 � 01 1 1 1 1
11 1 1 1 1
𝐹𝐹𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝐵𝐵 + 𝐷𝐷 10 1 0 0 1
12
Three-variables: Application Time!
𝐹𝐹 = 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶 ̅ 𝐶𝐶̅ + 𝐴𝐴𝐴𝐴𝐶𝐶̅
� + 𝐴𝐴𝐵𝐵𝐵𝐵 + 𝐴𝐴𝐵𝐵 𝐹𝐹 = 𝐴𝐴̅𝐵𝐵𝐶𝐶
� + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ + 𝐴𝐴𝐵𝐵𝐶𝐶
� + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ + 𝐴𝐴𝐵𝐵
̅ 𝐶𝐶̅
BC BC
A
00 01 11 10 00 01 11 10
A
0 1 1 1 1 0 1 1 0 1
1 0 0 0 1 1 1 1 0 0
CD 00 CD 00 01 11 10
01 11 10 AB
AB 00 1 0 0 1
00 1 0 1 0
01 0 1 1 0 01 0 1 1 0
11 0 1 1 0 11 0 1 1 0
10 1 0 1 0 10 1 0 0 1
𝐹𝐹 = 𝐴𝐴̅ + 𝐵𝐵 𝐶𝐶̅ 1 0 0 0 1
𝐹𝐹 = 𝐵𝐵� + 𝐴𝐴̅𝐶𝐶̅ 0 1 1 0 1
𝐴𝐴̅𝐵𝐵𝐶𝐶
� + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ + 𝐴𝐴𝐵𝐵𝐶𝐶
� + 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ → 𝐴𝐴̅𝐵𝐵� 𝐶𝐶 + 𝐶𝐶̅ + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ + 𝐶𝐶
𝐴𝐴̅ + 𝐴𝐴 𝐵𝐵� → 𝐵𝐵� 1 1 1 0 0
̅ 𝐶𝐶̅ → 𝐴𝐴̅ 𝐵𝐵� + 𝐵𝐵 𝐶𝐶̅ → 𝐴𝐴̅𝐶𝐶̅
𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ + 𝐴𝐴𝐵𝐵
𝐴𝐴̅𝐶𝐶̅ (B is eliminated)
Group the adjacent cells where only one variable changes 14
value so that it can be eliminated
Minimization (MSOP) using K-Map
(cont.)
Four-variables: 𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� 𝐵𝐵𝐷𝐷 𝐶𝐶𝐷𝐷
CD 00 01 11 10
𝐹𝐹 = 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵𝐶𝐶𝐶𝐶
� ̅ 𝐶𝐶𝐷𝐷
+ 𝐴𝐴𝐵𝐵 ̅ + 𝐴𝐴𝐵𝐵𝐶𝐶𝐷𝐷
̅ AB
̅ + 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴𝐵𝐵𝐶𝐶𝐷𝐷
� 00 1 0 1 0
+𝐴𝐴𝐴𝐴 𝐶𝐶𝐷𝐷
01 0 1 1 0
11 0 1 1 0
𝐹𝐹𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐵𝐵𝐵𝐵 + 𝐶𝐶𝐷𝐷
1 0 1 0
10
𝐵𝐵� 𝐷𝐷
� 𝐵𝐵𝐷𝐷
CD 00 01 11 10
𝐹𝐹 = 𝐴𝐴̅𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝐷𝐷 ̅ 𝐶𝐶𝐷𝐷
� + 𝐴𝐴𝐵𝐵 ̅ + 𝐴𝐴𝐵𝐵𝐵𝐵𝐵𝐵
̅ AB
+𝐴𝐴𝐴𝐴𝐶𝐶𝐷𝐷 ̅ + 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐵𝐵� 𝐶𝐶̅ 𝐷𝐷
� + 𝐴𝐴𝐵𝐵𝐶𝐶
� 𝐷𝐷� 00 1 0 0 1
01 0 1 1 0
11 0 1 1 0
𝐹𝐹𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝐵𝐵� 𝐷𝐷
� + 𝐵𝐵𝐵𝐵
10 1 0 0 1
15
Minimization (MPOS) using K-Map
maxterm-input correspondence: complement literals if 1
Boolean function in POS:
CD 00 01 11 10 𝐶𝐶̅ + 𝐷𝐷
� ̅
𝐹𝐹 = 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷 AB
𝐴𝐴 + 𝐵𝐵� + 𝐶𝐶 + 𝐷𝐷 𝐴𝐴 + 𝐵𝐵� + 𝐶𝐶̅ + 𝐷𝐷 00 1 0 1 0
𝐴𝐴̅ + 𝐵𝐵� + 𝐶𝐶 + 𝐷𝐷 𝐴𝐴̅ + 𝐵𝐵� + 𝐶𝐶̅ + 𝐷𝐷 01 0 1 1 0
(𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷
� )(𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶̅ + 𝐷𝐷)
0 1 1 0
11
10 1 0 1 0
� ⋅ 𝐶𝐶̅ + 𝐷𝐷 ⋅ (𝐵𝐵� + 𝐷𝐷)
𝐹𝐹𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 = 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷
� ⋅ 𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷
𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷 �
POS simplification using K-map: = 𝐴𝐴𝐴𝐴̅ + 𝐴𝐴 ⋅ 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷
�
+ 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷 � ⋅ 𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷
�
Group the squares that only contains “0”
⋅ 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷� = 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷 �
Form an OR term (sum) for each group, instead of a product
Value “1”, instead of “0”, represent complement of the variable
Follow similar grouping rules for SOP
Either SOP or POS can be used to implement the Boolean function, depending on which gives
more efficient implementation.
summarizing: proceed as SOP, but group 0’s instead of 1’s (square = maxterm)
+ complement the values in row-col. to find maxterm associated with square 16
Invalid groupings
CD 00 01 11 10 CD 00 01 11 10
AB AB
00 1 0 1 0 00 0 1 0 1
01 0 1 1 0 01 1 0 0 1
11 0 1 1 0 11 0 1 1 1
10 1 0 1 0 10 0 1 1 1
Squares in the group are not in power of two not horizontal or vertical
17
Application Example - Boolean
Function Simplification
𝐹𝐹 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑 = 𝑎𝑎𝑎𝑎𝑐𝑐̅ + 𝑎𝑎𝑎𝑎𝑎𝑎 + 𝑏𝑏𝑏𝑏𝑏𝑏 + 𝑎𝑎𝑐𝑐𝑐𝑐 �
� + 𝑎𝑎𝑏𝑏𝑐𝑐𝑑𝑑
= 𝑎𝑎𝑎𝑎 𝑐𝑐̅ + 𝑐𝑐 + 𝑏𝑏𝑏𝑏𝑏𝑏 + 𝑎𝑎𝑐𝑐𝑐𝑐
� + 𝑎𝑎𝑏𝑏𝑐𝑐𝑑𝑑 � (𝐴𝐴 + 𝐴𝐴̅ = 1)
= 𝑎𝑎 𝑏𝑏 + 𝑏𝑏� 𝑐𝑐𝑑𝑑 ̅ + 𝑏𝑏𝑏𝑏𝑏𝑏 + 𝑎𝑎𝑐𝑐𝑐𝑐
� (𝐴𝐴 + 𝐴𝐴̅ � 𝐵𝐵 = 𝐴𝐴 + 𝐵𝐵)
= 𝑎𝑎 𝑏𝑏 + 𝑐𝑐𝑑𝑑 ̅ + 𝑏𝑏𝑏𝑏𝑏𝑏 + 𝑎𝑎𝑐𝑐𝑐𝑐
�
= 𝑎𝑎𝑏𝑏 + 𝑎𝑎� 𝑐𝑐𝑐𝑐 + 𝑏𝑏 𝑐𝑐𝑐𝑐 + 𝑎𝑎𝑐𝑐𝑑𝑑 ̅ (𝐴𝐴𝐵𝐵 + 𝐴𝐴𝐶𝐶̅ + 𝐵𝐵𝐶𝐶 = 𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐶𝐶)
̅ - consensus
= 𝑎𝑎𝑎𝑎 + 𝑎𝑎𝑐𝑐𝑐𝑐
� + 𝑎𝑎𝑐𝑐𝑑𝑑 ̅
K-Map Simplification :
𝐹𝐹 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑 = 𝑎𝑎𝑎𝑎𝑐𝑐̅ + 𝑎𝑎𝑎𝑎𝑎𝑎 + 𝑏𝑏𝑏𝑏𝑏𝑏 + 𝑎𝑎𝑐𝑐𝑐𝑐 �
� + 𝑎𝑎𝑏𝑏𝑐𝑐𝑑𝑑
CD 00 01 11 10
AB
00 1
01 1
𝐹𝐹𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑 = 𝑎𝑎𝑎𝑎 + 𝑎𝑎𝑐𝑐𝑐𝑐
� + 𝑎𝑎𝑐𝑐𝑑𝑑
11 1 1 1 1
10 1
18
Digital Design
Design Example - 7-Seg Decoder
A 7-segment display decoder takes a 4-bit input, D3:0, and produces seven outputs to
control LEDs, to display a digit from 0 to 9. The LEDs are named a through g, or Sa – Sg.
Write a truth table for the output Sa and derive D3 D2 D1 D0 Sa
the MSOP.
0 0 0 0 1
You may assume illegal input values (10–15) will
0 0 0 1 0
never appear and use don’t cares.
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 Page 19 X
Design Example - 7-Seg Decoder
D3D2
D1D0 00 01 11 10 𝑫𝑫𝟐𝟐 . 𝑫𝑫𝟎𝟎
00 1 0 X 1
01 0 1 X 1 𝑆𝑆𝑎𝑎 = 𝐷𝐷2 𝐷𝐷0 + 𝐷𝐷2 𝐷𝐷0 + 𝐷𝐷1 + 𝐷𝐷3
𝑫𝑫𝟑𝟑
11 1 1 X X
10 1 1 X X
𝑫𝑫𝟏𝟏
𝑫𝑫𝟐𝟐 . 𝑫𝑫𝟎𝟎
oWe often assume that all combinations of input are valid (e.g. 3 inputs = 8
different input combinations that makes the function equal to 0 or 1)
oThere are applications in which some variable combinations never appear.
oThese conditions are called don’t-care conditions.
oDon’t-care condition is marked with “X” in K-map
oFor minimization, X can take either “1” or “0”.
Page 20
EE2026
Digital Design
COMBINATIONAL BLOCKS (SELF READING)
Chua Dingjuan elechuad@nus.edu.sg
Combinational Building Blocks
o Combinational logic is often grouped into larger functional
‘blocks’
o This layer of abstraction hides gate levels details and helps us
to visualize using ‘functions’!
o Common building blocks :
o Multiplexers / Demultiplexers
o Decoders – Example BCD to 7-segment
o Encoders
o Adders – Half Adders, Full Adders, Ripple Adders
o Magnitude Comparators
o Tri-State Logic Elements (Not Examinable)
I3
In-1 S1 S0
1 1 I3
Actual truth table would
have 26 rows !
Selection (I0, I1, I2, I3, S0 and S1)
Selection inputs allow one
Control
of the inputs to pass
through to the output
Multiplexer Example Application
A multiplexer (MUX) is a combinational circuit element that
selects data from one of 2N inputs and directs it to a single
output, according to an N-bit selection signal
I0
I1
I2
Z
…
In-1
Selection
Control
Verilog Example: 4:1 MUX
Multiplexers sometimes E S1 S0 I0 I1 I2 I3 Z
0 X X X X X X 0
include enable input signal 1 0 0 0 X X X 0
𝑍 = 𝐸 ⋅ 𝑆0 𝑆ഥ1 𝐼0 + 𝑆0 𝑆ഥ1 𝐼1 + 𝑆0 𝑆1 𝐼2 + 𝑆0 𝑆1 𝐼3 1 0 0 1 X X X 1
1 0 1 X 0 X X 0
1 0 1 X 1 X X 1
1 1 0 X X 0 X 0
1 1 0 X X 1 X 1
1 1 1 X X X 0 0
1 1 1 X X X 1 1
module mux41(Z,S,I0,I1,I2,I3,E);
input I0, I1, I2, I3; // inputs
input [1:0] S; // 2-bit selection signal
input E; // enable
output Z;
assign Z = E ? ( S[1] ? (S[0] ? I3 : I2) : (S[0] ? I1 : I0) ) : 0;
endmodule
MUX Application Example
Multiplexers can be used as lookup tables (LUT) to perform
logic functions!
Alyssa needs to implement the function 𝑌 = 𝐴𝐵ത + 𝐵ത 𝐶ҧ +
ҧ
𝐴𝐵𝐶 for her project. However, the only part in her lab kit is
an 8:1 multiplexer. How does she implement the function?
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1 Z
1 0 0
1 0 1
1 1 0
1 1 1
Page 7
Demultiplexer
A Demultiplexer (DEMUX) connects an input signal to
any of 2N output lines, based on an N-bit selection
control
module demux41(Z0,Z1,Z2,Z3,S,D);
input D; // input
input [1:0] S; // 2-bit selection signal
output Z0, Z1, Z2, Z3;
assign Z0 = (S == 2'b00) ? D : 1'b0;
assign Z1 = (S == 2'b01) ? D : 1'b0;
assign Z2 = (S == 2'b10) ? D : 1'b0;
assign Z3 = (S == 2'b11) ? D : 1'b0;
endmodule
Decoder
Input: N-bit input code, Output : 2N outputs
A decoder asserts ONE output as a function of the input
(these outputs are also called one-hot!)
Truth Table
Functional block diagram
A2 A1 A0 Z0 Z1 Z2 Z3 Z4 Z5 Z6 Z7
3-to-8 decoder
0 0 0 1 0 0 0 0 0 0 0
Z0
0 0 1 0 1 0 0 0 0 0 0
A2 Z1
0 1 0 0 0 1 0 0 0 0 0
Z2
Z3 0 1 1 0 0 0 1 0 0 0 0
N A1
Z4
2N 1 0 0 0 0 0 0 1 0 0 0
Z5 1 0 1 0 0 0 0 0 1 0 0
A0 Z6 1 1 0 0 0 0 0 0 0 1 0
Z7 1 1 1 0 0 0 0 0 0 0 1
a
f b
g
e
d
c
+ -
ANODE CATHODE
A 7-segment display. Each segment is an LED LED
input [ M-1 : 0 ] A;
input E;
output [ 0 : N-1 ] Z;
endmodule
endmodule
Encoder
• For different input bits (usually 2N), encoder generates a code
with fewer bits (usually N bits) uniquely identifying the input
– performs the inverse of the decoding function
I0 I1 I2 I3 I4 I5 I6 I7 C2 C1 C0
1 0 0 0 0 0 0 0 0 0 0
X 1 0 0 0 0 0 0 0 0 1
X X 1 0 0 0 0 0 0 1 0
X X X 1 0 0 0 0 0 1 1
X X X X 1 0 0 0 1 0 0
X X X X X 1 0 0 1 0 1
X X X X X X 1 0 1 1 0
X X X X X X X 1 1 1 1
Example: Priority Encoder
Dataflow Verilog description of 4-2 priority encoder I0 I1 I2 I3 C1 C0
1 0 0 0 0 0
X 1 0 0 0 1
X X 1 0 1 0
X X X 1 1 1
Use nested conditional operators, starting from MSB and progressively
moving to the LSB
module priorityencoder(C,I);
input [3:0] I;
output [1:0] C;
assign C = (I[3]) ? (2'b11) : (I[2] ? (2'b10) : (I[1] ? (2'b01) : (2'b00)) );
// if I[3]=1, C=11
// else, if I[2]=1, C=10, etc.
endmodule
Ai Ai Bi Sumi Carryi+1
SUMi
Bi 0 0 0 0
0+0=0
0+1=1 0 1 1 0
1+0=1 1 0 1 0
CARRYi+1
1 + 1 = 10 1 1 0 1
𝑆 = 𝐴ҧ ⋅ 𝐵 + 𝐴 ⋅ 𝐵ത = 𝐴⨁𝐵
𝐶 =𝐴⋅𝐵
Carry in from previous bit cannot be added
module ha(S,Cout,A,B);
input A, B;
output S, Cout; // Cout is the carry output
assign S = A ^ B;
assign Cout = A & B;
endmodule
Full Adders
Full adders can add carry bit from previous stage of addition
Carry → 𝐶𝑖+1
A : An Ai +1 Ai A0 Ai Bi Ci Si Ci+1
B : Bn Bi +1 Bi B0 0 0 0 0 0
Sum → 𝑆𝑖 0 0 1 1 0
0 1 0 1 0
Full adder
0 1 1 0 1
1 0 0 1 0
Current
Ai Si sum 1 0 1 0 1
Current
bits
1 1 0 0 1
Bi
1 1 1 1 1
carry-in from carry-out to
previous stg Ci Ci+1 next stg
Full Adders (cont.)
K-map for SUM K-map for CARRY
Ai Ai
0 1 0 1
BiCi BiCi
00 0 1 00 0 0
Note: Ci+1 is not a MSOP, but
01 1 0 01 0 1
less overall hardware is reqd.
11 0 1 if we use this expression. It 11 1 1
allows sharing of Ai XOR Bi 10 0 1
10 1 0
between SUMi and Ci+1.
module fa(S,Cout,A,B,Cin);
input A, B, Cin; // Cin is the carry input
output S, Cout; // Cout is the carry output
assign S = A ^ B ^ Cin;
assign Cout = A & B | Cin & (A ^ B);
endmodule
Parallel Adders
Ai Bi
C4 C3 C2 C1
Ci+1 Full Ci A3 A2 A1 A0
Adder B3 B2 B1 B0
Si
MSB LSB
A3 B3 A2 B2 A1 B1 A0 B0
carry-out C4
Stage 3
C3
Stage 2
C2
Stage 1
C1
Stage 0
C0
FA FA FA FA 0
S3 S2 S1 S0
Note: no carry-in
4 cascaded full adders
Parallel Adders (cont.)
In general, n full adders need to be used to form an n-bit adder
Carry ripple effect
◦ output of each full adder is not available until the carry-in from the previous
stage is delivered
◦ carry bits have to propagate from one stage to the next
◦ as the carries ripple through the carry chain → also known as ripple carry
adders
A0 B 0 A1 B 1 AN-1 B N-1
critical path
S0 S1 SN-1
This slow rippling effect is substantially reduced by using carry look ahead
adders
Parallel Adders (cont.)
Structural Verilog description (parameterized, arbitrary bit width)
Magnitude comparator
(A > B)
N AN-1 ...A0
(A = B)
N
BN-1...B0
(A < B)
A>B A<B
A1 A0 A1 A 0
00 01 11 10 00 01 11 10
B1B0 B1B0
00 0 1 1 1 00 0 0 0 0
01 0 0 1 1 01 1 0 0 0
11 0 0 0 0 11 1 1 0 1
10 0 0 1 0 10 1 1 0 0
A=B
A1 A0 ( A = B) = A1 A0 B1B0 + A1 A0 B1B0
00 01 11 10
B1B0
+ A1 A0 B1B0 + A1 A0 B1B0
00 1 0 0 0
01 0 1 0 0 This can be generated
indirectly
11 0 0 1 0
using (A<B) and (A>B)
10 0 0 0 1
( A = B) = ( A B) ( A B)
Magnitude Comparator: Verilog
Dataflow Verilog description (parameterized, arbitrary bit width)
module magcomp(AgreaterB,AequalB,AlowerB,A,B);
parameter N = 4;
input [N-1:0] A, B;
output AgreaterB, AequalB, AlowerB;
implement MUXes
B0.H
When Control = 00, tri-state device for A0 is X0
Device X
enabled, others are disabled. Hence A0 is C0.H X1
Control signals select which input goes to X 2-to-4 decoder Physically connected,
effectively it behaves like a MUX but only one is
Control enabled
I3
In-1 S1 S0
1 1 I3
Actual truth table would
have 26 rows !
Selection (I0, I1, I2, I3, S0 and S1)
Selection inputs allow one
Control
of the inputs to pass
through to the output
Multiplexer Example Application
A multiplexer (MUX) is a combinational circuit element that
selects data from one of 2N inputs and directs it to a single
output, according to an N-bit selection signal
I0
I1
I2
Z
…
In-1
Selection
Control
Verilog Example: 4:1 MUX
Multiplexers sometimes E S1 S0 I0 I1 I2 I3 Z
0 X X X X X X 0
include enable input signal 1 0 0 0 X X X 0
𝑍 = 𝐸 ⋅ 𝑆0 𝑆ഥ1 𝐼0 + 𝑆0 𝑆ഥ1 𝐼1 + 𝑆0 𝑆1 𝐼2 + 𝑆0 𝑆1 𝐼3 1 0 0 1 X X X 1
1 0 1 X 0 X X 0
1 0 1 X 1 X X 1
1 1 0 X X 0 X 0
1 1 0 X X 1 X 1
1 1 1 X X X 0 0
1 1 1 X X X 1 1
module mux41(Z,S,I0,I1,I2,I3,E);
input I0, I1, I2, I3; // inputs
input [1:0] S; // 2-bit selection signal
input E; // enable
output Z;
assign Z = E ? ( S[1] ? (S[0] ? I3 : I2) : (S[0] ? I1 : I0) ) : 0;
endmodule
MUX Application Example
Multiplexers can be used as lookup tables (LUT) to perform
logic functions!
Alyssa needs to implement the function 𝑌 = 𝐴𝐵ത + 𝐵ത 𝐶ҧ +
ҧ
𝐴𝐵𝐶 for her project. However, the only part in her lab kit is
an 8:1 multiplexer. How does she implement the function?
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1 Z
1 0 0
1 0 1
1 1 0
1 1 1
Page 7
MUX Application Example
Multiplexers can be used as lookup tables (LUT) to perform
logic functions!
Alyssa needs to implement the function 𝑌 = 𝐴𝐵ത + 𝐵ത 𝐶ҧ +
ҧ
𝐴𝐵𝐶 for her project. However, the only part in her lab kit is
an 8:1 multiplexer. How does she implement the function?
A B C Y 1
0 0 0 1 0
0 0 1 0
0
0 1 0 0
1
0 1 1 1 Z
1
1 0 0 1
1
1 0 1 1
0
1 1 0 0
1 1 1 0 0
A B C Page 8
Demultiplexer
A Demultiplexer (DEMUX) connects an input signal to
any of 2N output lines, based on an N-bit selection
control
module demux41(Z0,Z1,Z2,Z3,S,D);
input D; // input
input [1:0] S; // 2-bit selection signal
output Z0, Z1, Z2, Z3;
assign Z0 = (S == 2'b00) ? D : 1'b0;
assign Z1 = (S == 2'b01) ? D : 1'b0;
assign Z2 = (S == 2'b10) ? D : 1'b0;
assign Z3 = (S == 2'b11) ? D : 1'b0;
endmodule
Decoder
Input: N-bit input code, Output : 2N outputs
A decoder asserts ONE output as a function of the input
(these outputs are also called one-hot!)
Truth Table
Functional block diagram
A2 A1 A0 Z0 Z1 Z2 Z3 Z4 Z5 Z6 Z7
3-to-8 decoder
0 0 0 1 0 0 0 0 0 0 0
Z0
0 0 1 0 1 0 0 0 0 0 0
A2 Z1
0 1 0 0 0 1 0 0 0 0 0
Z2
Z3 0 1 1 0 0 0 1 0 0 0 0
N A1
Z4
2N 1 0 0 0 0 0 0 1 0 0 0
Z5 1 0 1 0 0 0 0 0 1 0 0
A0 Z6 1 1 0 0 0 0 0 0 0 1 0
Z7 1 1 1 0 0 0 0 0 0 0 1
a
f b
g
e
d
c
+ -
ANODE CATHODE
A 7-segment display. Each segment is an LED LED
input [ M-1 : 0 ] A;
input E;
output [ 0 : N-1 ] Z;
endmodule
endmodule
Encoder
• For different input bits (usually 2N), encoder generates a code
with fewer bits (usually N bits) uniquely identifying the input
– performs the inverse of the decoding function
I0 I1 I2 I3 I4 I5 I6 I7 C2 C1 C0
1 0 0 0 0 0 0 0 0 0 0
X 1 0 0 0 0 0 0 0 0 1
X X 1 0 0 0 0 0 0 1 0
X X X 1 0 0 0 0 0 1 1
X X X X 1 0 0 0 1 0 0
X X X X X 1 0 0 1 0 1
X X X X X X 1 0 1 1 0
X X X X X X X 1 1 1 1
Example: Priority Encoder
Dataflow Verilog description of 4-2 priority encoder I0 I1 I2 I3 C1 C0
1 0 0 0 0 0
X 1 0 0 0 1
X X 1 0 1 0
X X X 1 1 1
Use nested conditional operators, starting from MSB and progressively
moving to the LSB
module priorityencoder(C,I);
input [3:0] I;
output [1:0] C;
assign C = (I[3]) ? (2'b11) : (I[2] ? (2'b10) : (I[1] ? (2'b01) : (2'b00)) );
// if I[3]=1, C=11
// else, if I[2]=1, C=10, etc.
endmodule
Ai Ai Bi Sumi Carryi+1
SUMi
Bi 0 0 0 0
0+0=0
0+1=1 0 1 1 0
1+0=1 1 0 1 0
CARRYi+1
1 + 1 = 10 1 1 0 1
𝑆 = 𝐴ҧ ⋅ 𝐵 + 𝐴 ⋅ 𝐵ത = 𝐴⨁𝐵
𝐶 =𝐴⋅𝐵
Carry in from previous bit cannot be added
module ha(S,Cout,A,B);
input A, B;
output S, Cout; // Cout is the carry output
assign S = A ^ B;
assign Cout = A & B;
endmodule
Full Adders
Full adders can add carry bit from previous stage of addition
Carry → 𝐶𝑖+1
A : An Ai +1 Ai A0 Ai Bi Ci Si Ci+1
B : Bn Bi +1 Bi B0 0 0 0 0 0
Sum → 𝑆𝑖 0 0 1 1 0
0 1 0 1 0
Full adder
0 1 1 0 1
1 0 0 1 0
Current
Ai Si sum 1 0 1 0 1
Current
bits
1 1 0 0 1
Bi
1 1 1 1 1
carry-in from carry-out to
previous stg Ci Ci+1 next stg
Full Adders (cont.)
K-map for SUM K-map for CARRY
Ai Ai
0 1 0 1
BiCi BiCi
00 0 1 00 0 0
Note: Ci+1 is not a MSOP, but
01 1 0 01 0 1
less overall hardware is reqd.
11 0 1 if we use this expression. It 11 1 1
allows sharing of Ai XOR Bi 10 0 1
10 1 0
between SUMi and Ci+1.
module fa(S,Cout,A,B,Cin);
input A, B, Cin; // Cin is the carry input
output S, Cout; // Cout is the carry output
assign S = A ^ B ^ Cin;
assign Cout = A & B | Cin & (A ^ B);
endmodule
Parallel Adders
Ai Bi
C4 C3 C2 C1
Ci+1 Full Ci A3 A2 A1 A0
Adder B3 B2 B1 B0
Si
MSB LSB
A3 B3 A2 B2 A1 B1 A0 B0
carry-out C4
Stage 3
C3
Stage 2
C2
Stage 1
C1
Stage 0
C0
FA FA FA FA 0
S3 S2 S1 S0
Note: no carry-in
4 cascaded full adders
Parallel Adders (cont.)
In general, n full adders need to be used to form an n-bit adder
Carry ripple effect
◦ output of each full adder is not available until the carry-in from the previous
stage is delivered
◦ carry bits have to propagate from one stage to the next
◦ as the carries ripple through the carry chain → also known as ripple carry
adders
A0 B 0 A1 B 1 AN-1 B N-1
critical path
S0 S1 SN-1
This slow rippling effect is substantially reduced by using carry look ahead
adders
Parallel Adders (cont.)
Structural Verilog description (parameterized, arbitrary bit width)
Magnitude comparator
(A > B)
N AN-1 ...A0
(A = B)
N
BN-1...B0
(A < B)
A>B A<B
A1 A0 A1 A 0
00 01 11 10 00 01 11 10
B1B0 B1B0
00 0 1 1 1 00 0 0 0 0
01 0 0 1 1 01 1 0 0 0
11 0 0 0 0 11 1 1 0 1
10 0 0 1 0 10 1 1 0 0
A=B
A1 A0 ( A = B) = A1 A0 B1B0 + A1 A0 B1B0
00 01 11 10
B1B0
+ A1 A0 B1B0 + A1 A0 B1B0
00 1 0 0 0
01 0 1 0 0 This can be generated
indirectly
11 0 0 1 0
using (A<B) and (A>B)
10 0 0 0 1
( A = B) = ( A B) ( A B)
Magnitude Comparator: Verilog
Dataflow Verilog description (parameterized, arbitrary bit width)
module magcomp(AgreaterB,AequalB,AlowerB,A,B);
parameter N = 4;
input [N-1:0] A, B;
output AgreaterB, AequalB, AlowerB;
implement MUXes
B0.H
When Control = 00, tri-state device for A0 is X0
Device X
enabled, others are disabled. Hence A0 is C0.H X1
Control signals select which input goes to X 2-to-4 decoder Physically connected,
effectively it behaves like a MUX but only one is
Control enabled
Exercises 93
Exercises
Exercise 2.1 Write a Boolean equation in sum-of-products canonical form for
each of the truth tables in Figure 2.80.
Exercise 2.3 Minimize each of the Boolean equations from Exercise 2.1.
Exercise 2.5 Repeat Exercise 2.4 using only NOT gates and AND and OR
gates.
Exercise 2.6 Repeat Exercise 2.4 using only NOT gates and NAND and NOR
gates.
Exercise 2.7 Simplify the following Boolean equations using Boolean theorems.
Check for correctness using a truth table or K-map.
(a) Y AC ABC
(b) Y AB A BC (A C)
Exercise 2.9 Simplify each of the following Boolean equations. Sketch a reason-
ably simple combinational circuit implementing the simplified equation.
(a) Y BC ABC BC
(b) Y A AB AB A B
(c) Y ABC ABD ABE ACD ACE (A D E) B C D
B CE B D E C D E
Exercise 2.10 Give an example of a truth table requiring between 3 billion and
5 billion rows that can be constructed using fewer than 40 (but at least 1)
two-input gates.
Exercise 2.11 Give an example of a circuit with a cyclic path that is nevertheless
combinational.
Exercise 2.12 Alyssa P. Hacker says that any Boolean function can be written in
minimal sum-of-products form as the sum of all of the prime implicants of the
function. Ben Bitdiddle says that there are some functions whose minimal equa-
tion does not involve all of the prime implicants. Explain why Alyssa is right or
provide a counterexample demonstrating Ben’s point.
Exercise 2.13 Prove that the following theorems are true using perfect induction.
You need not prove their duals.
Exercise 2.14 Prove De Morgan’s Theorem (T12) for three variables, B2, B1, B0,
using perfect induction.
Exercise 2.15 Write Boolean equations for the circuit in Figure 2.81. You need
not minimize the equations.
Chapter 02.qxd 1/31/07 9:55 PM Page 95
Exercises 95
A B C D
Y Z
Figure 2.81 Circuit schematic
Exercise 2.16 Minimize the Boolean equations from Exercise 2.15 and sketch an
improved circuit with the same function.
Exercise 2.17 Using De Morgan equivalent gates and bubble pushing methods,
redraw the circuit in Figure 2.82 so that you can find the Boolean equation by
inspection. Write the Boolean equation.
A
B
C
D
Y
E
Figure 2.82 Circuit schematic
Exercise 2.18 Repeat Exercise 2.17 for the circuit in Figure 2.83.
Chapter 02.qxd 1/31/07 9:55 PM Page 96
A
B
C
D
Y
E
F
G
Figure 2.83 Circuit schematic
Exercise 2.19 Find a minimal Boolean equation for the function in Figure 2.84.
Remember to take advantage of the don’t care entries.
A B C D Y
0 0 0 0 X
0 0 0 1 X
0 0 1 0 X
0 0 1 1 0
0 1 0 0 0
0 1 0 1 X
0 1 1 0 0
0 1 1 1 X
1 0 0 0 1
1 0 0 1 0
1 0 1 0 X
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 X
1 1 1 1 1
Figure 2.84 Truth table
Exercise 2.20 Sketch a circuit for the function from Exercise 2.19.
Exercise 2.21 Does your circuit from Exercise 2.20 have any potential glitches
when one of the inputs changes? If not, explain why not. If so, show how to
modify the circuit to eliminate the glitches.
Exercise 2.22 Ben Bitdiddle will enjoy his picnic on sunny days that have no
ants. He will also enjoy his picnic any day he sees a hummingbird, as well as on
days where there are ants and ladybugs. Write a Boolean equation for his enjoy-
ment (E) in terms of sun (S), ants (A), hummingbirds (H), and ladybugs (L).
Chapter 02.qxd 1/31/07 9:55 PM Page 97
Exercises 97
(a) Derive Boolean equations for the outputs Sc through Sg assuming that inputs
greater than 9 must produce blank (0) outputs.
(b) Derive Boolean equations for the outputs Sc through Sg assuming that inputs
greater than 9 are don’t cares.
(c) Sketch a reasonably simple gate-level implementation of part (b). Multiple
outputs can share gates where appropriate.
Exercise 2.24 A circuit has four inputs and two outputs. The inputs, A3:0, repre-
sent a number from 0 to 15. Output P should be TRUE if the number is prime
(0 and 1 are not prime, but 2, 3, 5, and so on, are prime). Output D should be
TRUE if the number is divisible by 3. Give simplified Boolean equations for each
output and sketch a circuit.
Exercise 2.25 A priority encoder has 2N inputs. It produces an N-bit binary out-
put indicating the most significant bit of the input that is TRUE, or 0 if none of
the inputs are TRUE. It also produces an output NONE that is TRUE if none of
the input bits are TRUE. Design an eight-input priority encoder with inputs A7:0
and outputs Y2:0 and NONE. For example, if the input is 00100000, the output
Y should be 101 and NONE should be 0. Give a simplified Boolean equation for
each output, and sketch a schematic.
Exercise 2.26 Design a modified priority encoder (see Exercise 2.25) that
receives an 8-bit input, A7:0, and produces two 3-bit outputs, Y2:0 and Z2:0.
Y indicates the most significant bit of the input that is TRUE. Z indicates the
second most significant bit of the input that is TRUE. Y should be 0 if none of
the inputs are TRUE. Z should be 0 if no more than one of the inputs is TRUE.
Give a simplified Boolean equation for each output, and sketch a schematic.
Exercise 2.27 An M-bit thermometer code for the number k consists of k 1’s in
the least significant bit positions and M k 0’s in all the more significant bit
positions. A binary-to-thermometer code converter has N inputs and 2N1
outputs. It produces a 2N1 bit thermometer code for the number specified by
the input. For example, if the input is 110, the output should be 0111111.
Design a 3:7 binary-to-thermometer code converter. Give a simplified Boolean
equation for each output, and sketch a schematic.
Exercise 2.28 Write a minimized Boolean equation for the function performed
by the circuit in Figure 2.85.
Chapter 02.qxd 1/31/07 9:55 PM Page 98
C, D
A
00
01
10 0
11
Y
1
Exercise 2.29 Write a minimized Boolean equation for the function performed
by the circuit in Figure 2.86.
C, D A, B
00 00
01 01
10 10
Y
11 11
Exercise 2.32 Determine the propagation delay and contamination delay of the
circuit in Figure 2.83. Use the gate delays given in Table 2.8.
Chapter 02.qxd 1/31/07 9:55 PM Page 99
Exercises 99
2-input NAND 20 15
3-input NAND 30 25
2-input NOR 30 25
3-input NOR 45 35
2-input AND 30 25
3-input AND 40 30
2-input OR 40 30
3-input OR 55 45
2-input XOR 60 40
Exercise 2.33 Sketch a schematic for a fast 3:8 decoder. Suppose gate delays are
given in Table 2.8 (and only the gates in that table are available). Design your
decoder to have the shortest possible critical path, and indicate what that path is.
What are its propagation delay and contamination delay?
Exercise 2.34 Redesign the circuit from Exercise 2.24 to be as fast as possible.
Use only the gates from Table 2.8. Sketch the new circuit and indicate the critical
path. What are its propagation delay and contamination delay?
Exercise 2.35 Redesign the priority encoder from Exercise 2.25 to be as fast
as possible. You may use any of the gates from Table 2.8. Sketch the new
circuit and indicate the critical path. What are its propagation delay and
contamination delay?
Exercise 2.36 Design an 8:1 multiplexer with the shortest possible delay from
the data inputs to the output. You may use any of the gates from Table 2.7 on
page 88. Sketch a schematic. Using the gate delays from the table, determine
this delay.
Chapter 02.qxd 1/31/07 9:55 PM Page 100
Interview Questions
The following exercises present questions that have been asked at interviews for
digital design jobs.
Question 2.1 Sketch a schematic for the two-input XOR function using only
NAND gates. How few can you use?
Question 2.2 Design a circuit that will tell whether a given month has 31 days
in it. The month is specified by a 4-bit input, A3:0. For example, if the inputs
are 0001, the month is January, and if the inputs are 1100, the month is
December. The circuit output, Y, should be HIGH only when the month speci-
fied by the inputs has 31 days in it. Write the simplified equation, and draw
the circuit diagram using a minimum number of gates. (Hint: Remember to
take advantage of don’t cares.)
Question 2.4 A gate or set of gates is universal if it can be used to construct any
Boolean function. For example, the set {AND, OR, NOT} is universal.
Question 2.5 Explain why a circuit’s contamination delay might be less than
(instead of equal to) its propagation delay.
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 11
CHAPTER 2
2.1
(a) Y = AB + AB + AB
(b) Y = ABC + ABC
(c) Y = ABC + ABC + ABC + ABC + ABC
(d)
Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD
(e)
Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD
2.3
(a) Y = A + B
(b) Y = ABC + ABC
(c) Y = AC + AB + AC
(d) Y = AB + BD + ACD
(e)
Y = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD
This can also be expressed as:
Y = (A ⊕ B)(C ⊕ D) + (A ⊕ B)(C ⊕ D)
2.5
(a) Same as 2.4(a).
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
12 SOLUTIONS chapter 2
2.4 (b)
A
B
C
Y
(c)
A B C
(d)
A B C D
(e)
A B C D
Y
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 13
2.7
(a) Y = AC + BC
(b) Y = A
(c) Y = A + B C + B D + BD
2.9
(a) Y = B + AC
B
A Y
C
(b) Y = AB
A
Y
B
A B CD E
Y
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
14 SOLUTIONS chapter 2
2.11
A
Y
B
Y=A
2.13
(a)
B B B
0 0
1 1
(b)
B C D (B C) + (B D) B (C + D)
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 0 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
(c)
B C (B C) + (B C)
0 0 0
0 1 0
1 0 1
1 1 1
2.15
Y = AD + ABC + ACD + ABCD
Z = ACD + BD
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 15
2.17
A
B
C
D
Y
E
Y = (A + B)(C + D) + E
2.19
Two possible options are shown below:
Y Y
AB AB
CD 00 01 11 10 CD 00 01 11 10
00 X 0 1 1 00 X 0 1 1
01 X X 1 0 01 X X 1 0
11 0 X 1 1 11 0 X 1 1
10 X 0 X X 10 X 0 X X
2.21
Option (a) could have a glitch when A=1, B=1, C=0, and D transitions from
1 to 0. The glitch could be removed by instead using the circuit in option (b).
Option (b) does not have a glitch. Only one path exists from any given input
to the output.
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
16 SOLUTIONS chapter 2
2.23 (a)
Sc Sd
D3:2 D3:2
D1:0 00 01 11 10 D1:0 00 01 11 10
00 1 1 0 1 00 1 0 0 1
01 1 1 0 1 01 0 1 0 0
11 1 1 0 0 11 1 0 0 0
10 0 1 0 0 10 1 1 0 0
00 1 0 0 1 00 1 1 0 1
01 0 0 0 0 01 0 1 0 1
11 0 0 0 0 11 0 0 0 0
10 1 1 0 0 10 0 1 0 0
SOLUTIONS 17
Sg
D3:2
D1:0 00 01 11 10
00 0 1 0 1
01 0 1 0 1
11 1 0 0 0
10 1 1 0 0
18 SOLUTIONS chapter 2
(b)
Sa Sb
D3:2 D3:2
D1:0 00 01 11 10 D1:0 00 01 11 10
00 1 0 X 1 00 1 1 X 1
01 0 1 X 1 01 1 0 X 1
11 1 1 X X 11 1 1 X X
10 0 1 X X 10 1 0 X X
00 1 1 X 1 00 1 0 X 1
01 1 1 X 1 01 0 1 X 0
11 1 1 X X 11 1 0 X X
10 0 1 X X 10 1 1 X X
SOLUTIONS 19
Se Sf
D3:2 D3:2
D1:0 00 01 11 10 D1:0 00 01 11 10
00 1 0 X 1 00 1 1 X 1
01 0 0 X 0 01 0 1 X 1
11 0 0 X X 11 0 0 X X
10 1 1 X X 10 0 1 X X
00 0 1 X 1
01 0 1 X 1
11 1 0 X X
10 1 1 X X
20 SOLUTIONS chapter 2
(c)
D3 D2 D1 D0
Sa Sb Sc Sd Se Sf Sg
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 21
2.25
A7 A6 A5 A4 A3 A2 A1 A0 Y2 Y1 Y0 NONE
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 X 0 0 1 0
0 0 0 0 0 1 X X 0 1 0 0
0 0 0 0 1 X X X 0 1 1 0
0 0 0 1 X X X X 1 0 0 0
0 0 1 X X X X X 1 0 1 0
0 1 X X X X X X 1 1 0 0
1 X X X X X X X 1 1 1 0
Y2 = A7 + A6 + A5 + A4
Y1 = A7 + A6 + A5 A4 A3 + A5 A4 A2
Y0 = A7 + A6 A5 + A6 A5 A4 A3 + A6 A5 A4 A2 A1
NONE = A 7 A 6 A 5 A 4 A 3 A 2 A 1 A 0
A7 A6 A5 A4 A3 A2 A1 A0
Y2
Y1
Y0
NONE
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
22 SOLUTIONS chapter 2
2.27
Y6 = A2 A1 A0
Y5 = A2 A1
Y4 = A2 A1 + A2 A0
Y3 = A2
Y2 = A2 + A1 A0
Y1 = A2 + A1
Y0 = A2 + A1 + A0
A2 A1 A0
Y6
Y5
Y4
Y3
Y2
Y1
Y0
HARRIS SOLUTION CHAPTER 2 (CORRECTION)
QUESTION 2.29
⊕ ⊕
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 23
2.31
A B C A C Y A Y
A B C Y 0 0 1 0 B+C
0 0 0 1 000 0 1 B 1 B
0 0 1 0 001 1 0 B
0 1 0 1 010 1 1 B
0 1 1 1 011 A
Y AC
1 0 0 0 100
C
1 0 1 0 101 00 0
B
1 1 0 1 110 B 01 Y
Y
1 1 1 1 111 10 1
11
2.33
tpd = tpd_NOT + tpd_AND3
= 15 ps + 40 ps
= 55 ps
tcd = tcd_AND3
= 30 ps
A2 A1 A0
Y7
Y6
Y5
Y4
Y3
Y2
Y1
Y0
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
24 SOLUTIONS chapter 2
2.35
A7 A6 A5 A4 A3 A2 A1 A0
Y2
Y1
Y0
NONE
Question 2.1
A
Y
B
David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, © 2007 by Elsevier Inc.
Exercise Solutions
SOLUTIONS 25
Question 2.3
A tristate buffer has two inputs and three possible outputs: 0, 1, and Z. One
of the inputs is the data input and the other input is a control input, often called
the enable input. When the enable input is 1, the tristate buffer transfers the data
input to the output; otherwise, the output is high impedance, Z. Tristate buffers
are used when multiple sources drive a single output at different times. One and
only one tristate buffer is enabled at any given time.
Question 2.5
A circuit’s contamination delay might be less than its propagation delay be-
cause the circuit may operate over a range of temperatures and supply voltages,
for example, 3-3.6 V for LVCMOS (low voltage CMOS) chips. As temperature
increases and voltage decreases, circuit delay increases. Also, the circuit may
have different paths (critical and short paths) from the input to the output. A gate
itself may have varying delays between different inputs and the output, affect-
ing the gate’s critical and short paths. For example, for a two-input NAND gate,
a HIGH to LOW transition requires two nMOS transistor delays, whereas a
LOW to HIGH transition requires a single pMOS transistor delay.