CS221: Digital Design

Waleed A. Yousef, Ph.D.,

Human Computer Interaction Lab.,

Computer Science Department,
Faculty of Computers and Information,
Helwan University,
Egypt.

March 24, 2019

Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Lectures follow (and some figures are adapted from):

Mano, M. M., Ciletti, M. D., 2007. Digital design, 4th Edition. Prentice-Hall, Upper
Saddle River, NJ

We will proceed as follows:

• Fast introduction (few sections from Chapter 1).

• Detailed study of Chapters 2-7; very few sections will be skipped. At the end of each chapter Verilog
code for some circuits will be explained.

• If time permits, Chapter 8 will be covered in full or in parts

i Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Course Objectives

This course combines three approaches to teach students Digital Design, which is the fundamental prereq-
uisite to understand computer design and architecture:

1. Theoretical aspects of the subject will be covered in lectures, along with exercises in sections. Stu-
dents, by the end of the course, should be able to design, analyze, and implement combinational and
synchronous digital circuits.

2. A second objective is to teach students the digital design using a Hardware Descriptive Language
(HDL). Students by the end of the semester will be able to analyze logic circuits with Verilog (one of
the available HDLs).

3. A third objective is to develop the practical sense of the students through lab. experiments. Students
will be able to implement logic circuits using breadboards and ICs.

ii Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Contents

Contents iii

1 Introduction to Digital Systems 1

1.9 From Binary Logic (Mathematics) to Logic Gates (Circuits) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Boolean Algebra and Logic Gates 9

2.3 Axiomatic Definition of Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Basic Theorems and Properties of Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 Operator Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Boolean Functions and Gate Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6 Canonical and Standard Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6.1 Minterms and Maxterms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6.2 Standard Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7 Other Logic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.8 Other Digital Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.8.1 Extention to Multiple Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.9 Integrated Circuits (ICs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.9.1 Levels of Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Gate-Level Minimization 36
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 The Map Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.1 Two-Variable Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
iii Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 3.2.2 Three-Variable Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Four-Variable Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4 Five-Variable Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Product-of-Sums Simplifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.6 Don’t-Care Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.6.1 More Examples on K-Map Simplifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.7 Two-Level Implementation in NAND and NOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.7.1 NOR Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.9 Exclusive-OR (XOR) Function: revisit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.9.1 Parity Generation and Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.10 Hardware Descriptive Language (HDL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4 Combinational Logic 66
4.1 Introduction: types of logic circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Combinational Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Analysis Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 Design Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.4.1 Code Conversion Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.5 Binary Adder-Subtractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.1 Half Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.2 Full Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5.3 Implementing FA using ONLY HA => modular design => very interesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.5.4 Binary Adder: => more modular design => wonderful! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.5.5 Carry Propagation: complexity-speed trade off! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.5.6 Binary Subtractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.5.7 Binary Adder-Subtractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.6 Decimal Adder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.7 Binary Multiplier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.7.1 2-bit x 2-bit Multiplier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.7.2 3-bit x 4-bit Multiplier: How many bits? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.8 4-bit x 4-bit Magnitude Comparator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.9 n
n × 2 Decoder: D i = m i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.10 2n to n Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.10.1 Priority Encoder: 4 x 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.11 Multiplexers: 2n × 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.11.1 Two-to-one-line Mux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.11.2 Four-to-one-line Mux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.11.3 Quadrable two-to-one-line Mux (block-reuse design) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.11.4 Boolean Function Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.12 Demultiplexers (DEMUX) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.13 HDL Models of Combinational Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

iv Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5 Synchronous Sequential Logic 101
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2 Sequential Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3 Storage Elements: Latches (for asynchronous circuits) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.3.1 SR Latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.3.2 D Latch (Transparent Latch) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Storage Elements: Flip Flops (for synchronous circuits) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.4.1 Edge-Triggered D Flip-Flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.4.2 Other Flip-Flops: JK and T Flip-Flops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.4.3 Direct Inputs (asynchronous reset) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5 Analysis of Clocked Sequential Circuits (Synchronous Circuits) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.5.1 Mealy and Moore Models of FSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6 HDL Modles of Sequential Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.7 State Reduction and Assignments (needed for design) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.8 FSM: a generic preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.8.1 Rigorous Mathematical Definition (Rosen, 2007, Ch. 12) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.8.2 FSM and Languages: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.9 Design Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

6 Registers and Counters 128

6.1 Registers (n -bits, with parallel load) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.2 Synchronous Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.1 Binary Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.2 Up-Down Binary Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2.3 BCD Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2.4 Binary Counter with Parallel Load . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Shift Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Serial Transfer (compare to parallel registers 6.1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.3.2 Serial Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.3 Universal Shift Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.4 Ripple Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.4.1 Binary Ripple Counters (all counts exist) recall synchronous 6.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.4.2 BCD Ripple Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.5 Other Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.5.1 Ring Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.5.2 Johnson Counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.6 HDL for Registers and Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

7 Memory and Programmable Logic 146

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.2 Random-Access Memory (RAM): block-design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
v Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 7.3 Memory Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.3.1 Internal Construction of 1-bit RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.3.2 Coincident Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.3.3 Address Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.4 Error Dectection and Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.5 Read-Only Memory (ROM): non-volatile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.6 Programmable Array Logic (PAL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.7 Programmable Logic Array (PLA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.8 Sequential Programmable Devices: (more advanced topics) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

8 Design at the Register Transfer Level:

(a gate to "Computer Organization") 159
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.2 Register Transfer Language (RTL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.3 Register Transfer Language (RTL) in HDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4 Algorithmic State Machines (ASMs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.5 Design Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

A Numbering System and Binary Numbers A-1

B Boolean Algebra B-2

C Digital Integrated Circuits (ICs) C-3

Bibliography

vi Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 1

Introduction to Digital Systems

1 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

1.9 From Binary Logic (Mathematics) to Logic Gates (Circuits)
From what we have studied in Discrete Mathematics, we have the following basic three logic functions:

2 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
5 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
6 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Revisiting Course Objectives
Theory (hands on paper)

Simulation using Verilog

 
// Verilog model : Simple_Circuit
module Simple_Circuit (A , B , C, D, E) ;
output D, E ;
input A , B , C ;
wire w1 ;

and G1 (w1, A , B) ; // Optional gate instance

not G2 ( E , C) ;
or G3 (D, w1, E) ;
endmodule
 

Hardware Implementation
7 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
8 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Chapter 2

Boolean Algebra and Logic Gates

9 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.3 Axiomatic Definition of Boolean Algebra
Definition 1 :

• Denote True and False by 1 and 0 that represent Vcc and 0 voltages.

• A bit (binary digit) is a symbol of these two values.

• A Boolean Variable is a variable that is either True or False (or simply 1 or 0); hence a bit.

• Given a set B = 0, 1, the three operators

′
·(AN D), +(OR), (NOT ) are defined by:

• A truth table is the table that represents all the possi- ble combinations of the input to a logical (Boolean)
function.

10 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Claim 2 (Boolean Postulates Come “Dual”) :

1. Closure: the structure is closed w.r.t. + , ·

2. Identity element:

a) 0 + x = x.
b) 1 · x = x.

3. Commutative:

a) x + y = y + x.
b) x · y = y · x.

4. Distributive:

a) x · (y + z) = x · y + x · z.
b) x + (y · z) = (x + y)(x + z).

5. Complement:

a) x + x ′ = 1.
b) x · x ′ = 0
11 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Proof. :

1. is clear from truth table above.

2. by simple truth table:

3. is from definition.

4. by constructing the truth table below:

5. from very simple truth table

12 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.4 Basic Theorems and Properties of Boolean Algebra
Theorem 3 (dual postulates and theorems) :

Proof. (algebraically and by truth table. Some algebraic proofs are tedious and truth table is sufficient):

Theorem 1(a) algebraically :

13 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Theorem 1(a) by truth table :

Theorem 1(b) algebraically :

Theorem 1(b) by truth table :

Theorem 2(a-b) : proof is very similar to above.

Theorem 6(a) : algebraically

x +xy = x ·1+xy
= x · (1 + y)
= x ·1
=x
14 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Theorem 5(a) DeMorgan : truth table

Theorem 4 (Generalization) . It can be easily shown that Theorems 4, 5 in the above table are generalize to
more than 2 variables.

Proof. is straightforward by mathematical induction.

Example 5

(A 1 + A 2 + · · · + A n )′ = A ′1 A ′2 · · · A ′n
(A 1 A 2 · · · A n )′ = A ′1 + A ′2 + · · · + A ′n .

2.4.1 Operator Precedence

(), NOT, AND, OR:

Example 6
x + y · (x + z)′
15 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
2.5 Boolean Functions and Gate Implementation
Example 7 Evaluate and implement the functions:

F1 = x + y ′ z
F2 = x ′ y ′ z + x ′ y z + x y ′

Hint: be smart in filling the truth table:

Hint: draw the circuits elegantly:

16 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Simplify the function to simplify the circuit; why?

F2 = x ′ y ′ z + x ′ y z + x y ′
= x ′ z(y ′ + y) + x y ′
= x ′ z + x y ′,
which has only 4 literals, where a literal is a single variable (complemented or un-complemented).

Less gates (HW) means:

• low cost.

• low power consumption.

• simpler implementation.

Simplifying functions is by:

• algebraic manipulation (this chapter)

• K -map (next chapter)

• computer programs for many-input functions

17 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 8 Simplify the following function to a minimum number
of literals:

F 1 = x(x ′ + x y)
= xx ′ + xx y
= 0 + x y = x y.

F2 = x y + x ′ z + y z
= x y + x′z + x y z + x′ y z
= x y(1 + z) + x ′ z(1 + y)
= x y + x ′ z.

F 3 = (x(y ′ z ′ + y z))′
= x ′ + (y ′ z ′ + y z)′
= x ′ + (y + z)(y ′ + z ′ )
= x ′ + y z ′ + y ′ z.

Hint: for simplicity apply DeMorgan by duality followed by inverting each literal:

18 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 9

F 3 = x(y ′ z ′ + y z)
dual of F 3 = x + (y ′ + z ′ )(y + z)
F 3′ = x ′ + (y + z)(y ′ + z ′ ).

19 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.6 Canonical and Standard Forms
2.6.1 Minterms and Maxterms

• a minterm (or maxterm) equals one (or zero) only at one combination.

• the minterm (or maxterm) subscript is the order and value of this combination.

• order of variables is very important!

• m i = M i′ .

• E.g, what is the truth table of m 0 and M 0 ?

• Each function, then, can be expressed as either: sum of minterms or product of maxterms!
20 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
From Truth Table:

ORing (sum of ) minterms

∑ ∑
f1 = = (1, 4, 7) = m 1 + m 4 + m 7
1 o f f1
= x ′ y ′ z + x y ′ z ′ + x y z,
∑ ∑ ∑
f 1′ = = = (0, 2, 3, 5, 6) = m 0 + m 2 + m 3 + m 5 + m 6 .
1 o f f 1′ 0 o f f1

ANDing maxterms
∏ ∏
f1 = = (0, 2, 3, 5, 6) = M 0 · M 2 · M 3 · M 5 · M 6
0 o f f1
= (x + y + z)(x + y ′ + z)(x + y ′ + z ′ )(x ′ + y + z ′ )(x ′ + y ′ + z),
∏ ∏ ∏
f 1′ = = = (1, 4, 7) = M 1 M 4 M 7 .
0 o f f 1′ 1 o f f1

21 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Conclusion: For any function f equals 1 on the set 1 and 0 on the set 0 :
∑ ∏
= =⇒ f ,
1 of f 0 of f
∑ ∏
= =⇒ f ′ .
0 of f 1 of f

This is obtainable, as well, from DeMorgan:

∑
f =
1
= (m i + m j + · · · )
f = (m i + m j + · · · )′
′

= m i′ · m ′j · · ·
= Mi · M j · · ·
∏
=
1

Gate Implementation ∑
f1 = (1, 4, 7) = m 1 + m 4 + m 7 = x ′ y ′ z + x y ′ z ′ + x y z

22 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Converting algebraic expression to: sum of minterms or product of maxterms

Example 10 (two variables)

A = A(B ′ + B ) = AB ′ + AB
= m2 + m3 .

Example 11

A = A(B ′C ′ + B ′C + BC ′ + BC )
= AB ′C ′ + AB ′C + ABC ′ + ABC
= m4 + m5 + m6 + m7 .

23 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.6.2 Standard Forms
• Sum of minterms and product of maxterms are almost not minimized (because each term contains by
construction all variables).

• We should minimize and keep it as sum of products (SOP) or product of sums (POS), because it is only
two-level implementation; e.g.,

F1 = y ′ + x y + x ′ y z ′ ,
F 2 = x(y ′ + z)(x ′ + y + z ′ ).

• Observe that, we do not consider inversion a level.

• This provides minimal signal delay and simpler implementation.

• So, implement any function as SOM (POM), then simplify to SOP (POS).
24 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 12 (2- vs. 3-level implementation)

F 3 = AB +C (D + E )
F 3 = AB +C D +C E .

25 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.7 Other Logic Operations

For n binary variables:

number of functions = 2(number of rows in truth table)

n
= 22 .

F 0 = 0,
F1 = m3 = x y,
F2 = m2 = x y ′,
F3 = m2 + m3 = x y′ + x y = x,
′
F4 = m1 = x y,
F5 = m1 + m3 = x′ y + x y = y,
′ ′
F6 = m1 + m2 = x y +xy = x ⊕ y,
F7 = M0 = x + y.

The other functions can be obtained, of course, by complementing the previous functions (Why?)
26 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
27 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Special offer for Mathematics lovers: from our study in Discrete Mathematics we have already learned that
(Ch1. Rosen, 2007, P. 6):

Consider the sets X , Y , and any element e, and the indicators

x = IX = e ∈ X ,
y = IY = e ∈ Y ,

then all the following are equivalent:

• X ⊂Y (typo in book),

• If x then y, y if x, y when x,

• x implies y, y follows from x,

• x is sufficient for y, y is necessary for x,

• F = M 2 = x ′ + y.

HW: what is the logic function F that represent the case that X ∩ Y = ϕ and X ∪ Y ̸= Ω.

28 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.8 Other Digital Logic Gates
• From purely mathematical point of view: do we need more gates to implement other functions?

Problem 13 (Sec. 1.2 Rosen, 2007, Prob.: 43–45): Show that NOT, OR, AND form a functionally complete
collection of logical operators.

• Motivation: why, then, introducing new logic gates: NAND, NOR (next figure)? As we will see in Sec. 3.7:

– NAND can represent the main three logic functions!

– Similarly NOR (HW).
∑
– can be implemented only with NAND.
∏
– can be implemented only with NOR.
– Therefore, only NAND or NOR suffice.
– Great to have uniform gate delay.

• We already know AND, OR, NOT gates, with direct hardware implementation. NAND, NOR have their hard-
ware implementation as well.

29 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

30 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
2.8.1 Extention to Multiple Inputs
AND, OR are directly extensible to multiple input from their commutative and associative laws:

(x + y) + z = x + (y + z),
(x y)z = x(y z).

Therefore, we DEFINE:

x + y + z = (x + y) + z = x + (y + z),
x y z = (x y)z = x(y z).

Unfortunately: ↓ (NOR), ↑ (NAND) are not associative:

(x ↓ y) ↓ z = ((x + y)′ + z)′ = (x + y)z ′ = xz ′ + y z ′ ,

x ↓ (y ↓ z) = (x + (y + z)′ )′ = x ′ (y + z) = x ′ y + x ′ z.

HW: prove the same for NAND ↑.

31 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Hence, we have to DEFINE:

x ↓ y ↓ z = (x + y + z)′ ,
x ↑ y ↑ z = (x y z)′ .

32 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

XOR Function
• Prove (by truth table) that it is commutative and associative; i.e.,
x ⊕ y = y ⊕ x,
x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z.

• Hence, we DEFINE:
x ⊕ y ⊕ z = (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)

• From its truth table, all the following are correct

– x ⊕ y = 1 when only x or only y is 1.

– x ⊕ y = 1 when x and y are different.
– x ⊕ y = 1 when x and y have odd # of 1s.

• Get the truth table of x ⊕ y ⊕ z as:

Therefore, the third meaning is emphasized:

x ⊕ y ⊕ z = 1 when they have odd number of ones; (more coming on parity check)
33 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
2.9 Integrated Circuits (ICs)
• We design a digital circuit using theory, HDL, and HW implementation in lab. (breadboards, ...) using
data-sheets on page ( 8)

• After settling on particular design, this circuit can be fabricated on an IC using sophisticated engineer-
ing tools and industry

34 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2.9.1 Levels of Integration
Small-Scale Integration (SSI) ∼ 10 gates;
(Ch. 3)

Medium-Scale Integration (MSI) ∼ 10 ∼ 1000 gates;

(Ch. 4 and 6)

Lare-Scale Integration (LSI) ∼ 10, 000 gates;

(Ch. 7 and Computer Organization course.)

Very-Larage-Scale Integration ∼ 100, 000 gates;

(complex processors,...)

35 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 3

Gate-Level Minimization

36 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.1 Introduction
Let’s remember why minimization (page 17).

3.2 The Map Method

• K-map (named after Karnaugh) is a visual method, utilizing visual power.

• Difficult for more than 5 variables.

• Produces always SOP or POS expressions.

37 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.2.1 Two-Variable Map

Simplify the following functions both algebraically and with K-Map and observe the visual power:
F1 = m1 + m2 + m3 = x′ y + x y ′ + x y = x y + x ′ y + x y ′ + x y = y + x.
F2 = m3 = x y.
F3 = m0 + m3 = x ′ y ′ + x y.

• Only one-bit (variable) change for any two adjacent squares!

38 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
3.2.2 Three-Variable Map

• Only one-bit (variable) change for any two adjacent squares! Therefore, e.g.,

F = m 5 + m 7 = x y ′ z + x y z = xz(y ′ + y) = xz

• Make sure of number of variables (e.g., m 2 + m 3 for 2 or 3 variables) and their order

39 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 ∑
Example 14 : Simplify the function F (x, y, z) = (2, 3, 4, 5).

F = x ′ y + x y ′ = x ⊕ y.

40 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 ∑
Example 15 Simplify F (x, y, z) = (3, 4, 6, 7). (Hint: look at the most isolated 1s first.)

F = xz ′ + y z.

41 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 ∑
Example 16 : Consider the function F (x, y, z) = (0, 2, 4, 5, 6).

1. Simplify F . (Hint: a group should have (2m ) ones and its resulting SOP has (n − m) literals.

2. Implement the function using AND, OR, NOT.

3. Observe the number of AND and OR gates (ignore inverters for now).

m0 + m2 + m4 + m6 = x ′ y ′ z ′ + x ′ y z ′ + x y ′ z ′ + x y z ′ (z ′ with the 4 combinations of x, y)

∑
= (x ′ y ′ + x ′ y + x y ′ + x y)z ′ (z ′ · all Minterms of x, y = z ′ )
= (x ′ (y ′ + y) + x(y ′ + y))z ′ = (x ′ + x)z ′ = z ′ .

F = x y ′ + z ′.

42 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 17 Consider the function F = A ′C + A ′ B + AB ′C + BC .

1. Express the function as a sum of Minterms.

2. Find the minimal SOP expression.

Hint: each SOP term missing m literals will be expanded by 2m Minterms.

∑
F (A, B,C ) = (1, 2, 3, 5, 7)
F = C + A ′ B.

43 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Golden Rules to Remember:

• Only one-bit (variable) change for any two adjacent squares!

• The boundaries are adjacent as well.

• A group of ones should be 2m , where m is the number of removed variables in this group (SOP), and
the SOP will have n − m literals.

• Therefore, maximize the number of 1s in each group to minimize the number of literals in the SOP.

• Minimize the number of groups (the SOP terms).

• Therefore, start with the most isolated 1s.

• Make sure of number of variables and their order

• The number of literals in each group (SOP) is the number of inputs to its AND gate.

• The number of groups is the number of SOP terms is the number of AND gates is the number of inputs
to the OR gate.

• All Minterms are covered.

44 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.3 Four-Variable Map

• Adjacency from top-bottom, right-left, and corners.

• Corners: w and y took their 4 combinations at x = 0, z = 0: =⇒

m 0 + m 2 + m 8 + m 10 = w ′ x ′ y ′ z ′ + w ′ x ′ y z ′ + w x ′ y ′ z ′ + w x ′ y z ′
= (w ′ y ′ + w ′ y + w y ′ + w y)x ′ z ′
= x ′ z ′.

45 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 ∑
Example 18 Simplify the function F (w, x, y, z) = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

F = y ′ + w ′ z ′ + xz ′ .

46 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 19 Simplify the function F = A ′ B ′C ′ + B ′C D ′ + A ′ BC D ′ + AB ′C ′ .

F = B ′ D ′ + B ′C ′ + A ′C D ′ .

47 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.4 Five-Variable Map

∑
Example 20 Simplify the function F (A, B,C , D, E ) = (0, 2, 4, 6, 9, 13, 21, 23, 25, 29, 31).

F = A ′ B ′ E ′ + B D ′ E + AC E .

48 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

49 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
3.5 Product-of-Sums Simplifications
∑
Example 21 Simplify the function F (A, B,C , D) = (0, 1, 2, 5, 8, 9, 10). (Hint: Remember page (22)):
∑ ∏ ∑ ∏
= =⇒ f , = =⇒ f ′ .
1 of f 0 of f 0 of f 1 of f

F = B ′ D ′ + B ′C ′ + A ′C ′ D = (A ′ + B ′ )(C ′ + D ′ )(B ′ + D).

50 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Two-Level Implementation
Remember: Section 2.6.2

51 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.6 Don’t-Care Conditions
• A combination of input that will not happen; so don’t care about it. E.g., BCD.

• A combination of input at which we don’t care about the output.

Example 22 Minimize F and find its expression in terms of Minterms:

∑ ∑
F (w, x, y, z) = (1, 3, 7, 11, 15); d (w, x, y, z) = (0, 2, 5).

52 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.6.1 More Examples on K-Map Simplifications
1 1 1 1 1
1 1 1 x 1

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 x 1

1 1 1 1
1 1 1
1 1
1 1 1

53 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.7 Two-Level Implementation in NAND and NOR
• Recall that AND, OR, NOT are complete; they can implement any function.

• NAND, NOR can implement them as well.

Example: F = AB +C D.

54 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 23 Minimize and implement, using only NAND gates the function.
Hint: remember to use a NAND for inverter to keep two-level implementations.
∑
F (x, y, z) = (1, 2, 3, 4, 5, 7)

55 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.7.1 NOR Implementation
F = (A + B )(C + D)E

56 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.9 Exclusive-OR (XOR) Function: revisit

x ⊕ y = x y ′ + x ′ y,
x ⊕ 0 = x,
x ⊕ 1 = x ′,
x ⊕ x = 0,
x ⊕ x ′ = 1.

57 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Three-Input XOR: (revise page 33)

• Of course, could be implemented with two-level ordinary implementation.

58 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Multi-Input XOR: (special offer for Mathematics lovers)
Lemma 24 The XOR function is an odd function for any arbitrary number of bits; i.e.,
F = A 0 ⊕ A 1 · · · A n is 1 when (A 0 · · · A n ) have odd number of ones and 0 otherwise.

Proof. We prove it by induction. For n = 1, it is true Implementation of 4-input XOR using

from the definition of XOR. Next, suppose the state- NANDs or only XORs
ment is true for some n. Then, for n + 1:

F n+1 = A 0 ⊕ A 1 · · · A n+1
F n+1 = F n ⊕ A n+1 .

Fn A n+1 F n+1 (A 0 · · · A n ) (A 0 · · · A n+1 )

0 0 0 even even
0 1 1 even odd
1 0 1 odd odd
1 1 0 odd even

59 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.9.1 Parity Generation and Checking

• With this implementation, checker works as generator if P = 0.

• HW: How many 2-input XORs are needed to implement an even parity generator?

60 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

3.10 Hardware Descriptive Language (HDL)
The objective of the following few pages is to MOTIVATE you to self-start NOT to fully teach you

• When circuits become complicated and hard to analyze either on paper or by HW implementation.

• The basic two languages supported by IEEE are VHDL and Verilog

• Verilog CD comes with the book, or you can download the SW and a free 6-months license from:
http://www.syncad.com/

61 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

A Basic Example

 
 
module Simple_Circuit (A , B , C, D, E) ; module Simple_Circuit_prop_delay (A , B , C, D, E) ;
output D, E ; output D, E ;
input A , B , C; input A, B, C;
wire w1 ; wire w1 ;

and G1 (w1, A , B) ; and #(30) G1 (w1, A , B) ;

not G2 ( E , C) ; not #(10) G2 ( E , C) ;
or G3 (D, w1, E) ; or #(20) G3 (D, w1, E) ;
endmodule endmodule
 
 
62 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 
// Testbench for Simple_Circuit_prop_delay
‘timescale 1 ns / 100 ps
module t_Simple_Circuit_prop_delay ;
wire D, E ;
reg A, B, C;

Simple_Circuit_prop_delay M1 (A , B , C, D, E) ; // Instance name required

initial
begin
A = 1 ’b0 ; B = 1 ’b0 ; C = 1 ’b0 ;
#100 A = 1 ’b1 ; B = 1 ’b1 ; C = 1 ’b1 ;
#100 $finish ;
end

i n i t i a l $monitor ( $time , , "A = 5b B= %b C = %b w1 = %b D = %b E = %b" , A , B , C, D, M1. w1

, E) ;
endmodule
 

63 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Boolean Expressions

E = A + BC + B ′ D,
F = B ′C + BC ′ D ′ .

 
// Verilog model : Circuit_Boolean_CA
module Circuit_Boolean_CA ( E , F , A , B , C, D) ;
output E, F;
input A , B , C, D;

assign E = A | (B & C) | (~B & D) ;

assign F = (~B & C) | (B & ~C & ~D) ;
endmodule
 

64 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

User-Defined Primitives
 
primitive UDP_02467 (D, A , B , C) ;
output D;
input A , B , C ;
// Truth table for D = f (A , B, C) = Sum (0 , 2 , 4 , 6 , 7) ;
table
// A B C : D // Column header
0 0 0 : 1;
0 0 1 : 0;
0 1 0 : 1;
0 1 1 : 0;
1 0 0 : 1;
1 0 1 : 0;
1 1 0 : 1;
1 1 1 : 1;
endtable
endprimitive

// Verilog model : Circuit instantiation of Circuit_UDP_02467

module Circuit_with_UDP_02467 ( e , f , a , b , c , d) ;
output e, f ;
input a , b, c , d;

UDP_02467 M0 ( e , a , b , c ) ;
and ( f , e , d) ; // instance name omitted
endmodule
 
65 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Chapter 4

Combinational Logic

66 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.1 Introduction: types of logic circuits
• combinational: output is function only of input (Ch. 4)

• sequential: output is function of input and previous output => MEMORY (Ch. 5–9)

67 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.2 Combinational Circuits

• Output is a function only of inputs.

• Therefore, outputs can be specified by only truth table or Boolean function.

n
• Of course, m ≤ 22 .

• In Ch. 4 we will employ the previous chapters to analyze, design, and simplify these circuits.

– Analysis: given a circuit find the output as a function of input.

– Design: given a certain functionality, design the circuit.

68 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.3 Analysis
Procedure
• Make sure that the circuit
has no feedback => com-
binational.

• Label outputs with mean-

ingful names; then start
propagating until you
reach the output.

F 1 = T3 + T2
= F 2′ T1 + ABC
= ABC +
(AB + AC + BC )′ (A + B +C )
.
= ..
= A ′ B ′C + A ′ BC ′ + AB ′C ′ + ABC
∑
= (1, 2, 4, 7).

69 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.4 Design Procedure
1. Determine the number of inputs and outputs from the circuit functionality; then draw a block diagram
without the internal details. This is exactly similar to function prototype in programming.

2. Derive a truth table.

3. Simplify the expression.

4. Implement the circuit.

4.4.1 Code Conversion Example

Design a circuit that converts from a BCD code to excess-3 code.
Motivation:

• Some circuits use excess-3 code and we need to feed this circuit with the right input.

• very easy to complement: 9 − x is obtained by inverting the digits!

Let’s draft it on a clean page, then see the complete solution to save time.

70 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

71 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4.5 Binary Adder-Subtractor
4.5.1 Half Adder

72 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.5.2 Full Adder

73 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.5.3 Implementing FA using ONLY HA => modular design => very interesting

C3 = 0
S = S2 = S1 ⊕ z
= x ⊕y ⊕z
C = S 3 = C 1 +C 2
= x y + S1 z
= x y + (x ⊕ y)z
.
= ..
∑
= (3, 5, 6, 7)
74 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4.5.4 Binary Adder: => more modular design => wonderful!

Hint:

• without observing this modularity, it would be extremely difficult to design, e.g., 8-bit binary adder!

• carry subscript here is different from our previous example.

75 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4.5.5 Carry Propagation: complexity-speed trade off!

Pi = Ai ⊕ Bi
Gi = Ai Bi
S i = P i ⊕C i
C i +1 = G i + P i C i
C 1 = G 0 + P 0C 0
C 2 = G 1 + P 1C 1
= G 1 + P 1G 0 + P 1 P 0C 0
C 3 = G 2 + P 2C 2
= G 2 + P 2G 1 + P 2 P 1G 0 + P 2 P 1 P o C o .

76 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

77 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4.5.6 Binary Subtractor
Block Diagram level:

From Appendix A (Binary Num-

ber System) we already know
that for any n-bit numbers:

A − B = A − B + 2n − 2n
( )
= A + (2n − 1 − B ) + 1 − 2n
( )
= A + (1’s comp of B ) + 1 − 2n
= (A + B ′ + 1) − 2n .

6 0110 0110
2 0010 1101
1
10100 FAs level
• For signed numbers, we
use 2’s Comp.

• Over-flow: when last two

carries are different.

78 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.5.7 Binary Adder-Subtractor
Back to truth table and K-Map:

x y f x y f
0 0 0 0 0 0 0 1 0 1 0 0 1 1
0 1 1 0 1 1 A B A x x A x x
1 0 1 1 0 A
1 1 1 1 1 B

M Op xi yi C0
0 A +B Ai Bi 0
1 A + B′ + 1 Ai B i′ 1

xi = A i
y i = M ′ B i + M B i′ = M ⊕ B i
Co = M .

79 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.6 Decimal Adder

cin b3 b2 b1 b0 a3 a2 a1 a0 cout s8 s4 s2 s1
Design 1: very goofy 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 functions, each: 0 0 0 0 0 0 0 0 1 0 0 0 0 1
29 = 512 rows! .. ..
. .
X X

80 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Design 2: smarter but not yet

81 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Design 3: smartest!

C abcd
0 0000
1 0110

82 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

83 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
4.7 Binary Multiplier

4.7.1 2-bit x 2-bit Multiplier

Design 1: truth table

Design 2: Let’s think algorithmic

84 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.7.2 3-bit x 4-bit Multiplier: How many bits?
Design 1: truth table (very goofy)

Design 2: smart
B3 B2 B1 B0
A2 A1 A0
0 0 0 A0B3 A0B2 A0B1 A0B0
0 0 A1B3 A1B2 A1B1 A1B0 0

0 A2B3 A2B2 A2B1 A2B0 0 0

C6 C5 C4 C3 C2 C1 C0

85 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.8 4-bit x 4-bit Magnitude Comparator
Design 1: truth table (very goofy).

Design 2: Let’s go modular. design a 1-bit x 1-bit.

A0 B0 L0 S0 E0
0 0 0 0 1 L 0 = A 0 B 0′ ,
0 1 0 1 0 S 0 = A ′0 B 0 ,
1 0 1 0 0 E 0 = A ′0 B 0′ + A 0 B 0
1 1 0 0 1
= (L 0 + S 0 )′ .

For 4-bit comparator:

 
/* Algorithm for the logic : L = A > B
A3 A2 A1 A0
B3 B2 B1 B0
*/
L =( A3 > B3 ) ||
( A3 == B3 ) &&( A2 > B2 ) ||
( A3 == B3 ) &&( A2 == B2 ) &&( A1 > B1 ) ||
( A3 == B3 ) &&( A2 == B2 ) &&( A1 == B1 ) &&( A0 > B0 )
 

L = L3 + E3L2 + E3E2L1 + E3E2E1L0

S = S3 + E3S2 + E3E2S1 + E3E2E1S0
E = E3E2E1E0
86 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
87 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 25 Design an 8-bit comparator.

Design 1: using the 1-bit comparator very similar to what we have done.

Design 2: using the 4-bit comparator.

A7 A6 A5 A4 A3 A2 A1 A0
B7 B6 B5 B4 B3 B2 B1 B0

L = L1 + E1L0,
S = S1 + E1S0,
E = E1E0.

Is design 2 slower (propagation delay)? HW

88 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.9 n × 2n Decoder: D i = m i

∑
S= (1, 2, 4, 7)
∑
C = (3, 5, 6, 7)
∑
K = (0, 1, 2, 3, 4, 5) (# minterms > 2n /2)
∑
K ′ = (6, 7)

inverted output and enabled decoders:

E Di
0 0 D i = Em i
1 mi
89 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Therefore, we have:

E Inv-E E Inv-E
Out Out Inv-Out Inv-Out

E Op. Di E Op. Di E Op. Di E Op. Di

0 Dsb 0 0 Enb mi 0 Dsb 1 0 Enb Mi
1 Enb mi 1 Dsb 0 1 Enb Mi 1 Dsb 1

90 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 26 Design a 4x16 decoder using only 3x8 decoders. Hint: take care of LSB and MSB.

w x y z
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

we will see after studying multiplexer the connection to decoders!

91 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.10 2n to n Encoders

• the opposite operation of decoders.

z = D1 + D3 + D5 + D7
• we rely on no D i = D j = 1, i ̸= j .
y = D2 + D3 + D6 + D7
• no handling to D i = 0∀i x = D 4 + D 5 + D 6 + D 7.

92 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.10.1 Priority Encoder: 4 x 2
# D3 D2 D1 D0 x y v
X 0 0 0 X 0 1 1
0 0 0 0 0 X X 0
1 1 1 1 0 0 0 0
1 0 0 0 1 0 0 1
v = D3 + D2 + D1 + D0 1 1 1 1 1 1 1 1
2-3 0 0 1 X 0 1 1
1 1 1 1 1 1 1 1
4-7 0 1 X X 1 0 1 ′
x = D3 + D2 y = D 3 + D 1D 2
8-15 1 X X X 1 1 1

• D 3 is more prior than D 0 .

• Xs in inputs are NOT don’t care.

• V is 1 to indicate “Valid”.

Example 27 Encode the comparator out-

puts L, S, E to X, Y such that:

cond. X Y
A>B 1 0
A=B 1 1
A<B 0 1

93 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.11 Multiplexers: 2n × 1
How to use n selectors to select only one among 2n inputs?

4.11.1 Two-to-one-line Mux

Motivation: How to select between two variables (or more generally: two things)?
S Y
0 I0
1 I1

Y = S ′ I 0 + SI 1

• Of course, we can make it Enable or Inv-Enable MUX; how?

94 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.11.2 Four-to-one-line Mux

4×1
S1 S0 Y MUX
0 0 I0
0 1 I1
1 0 I2
1 1 I3

Y = I 0 S 1′ S 0′ + I 1 S 1′ S 0 + I 2 S 1 S 0′ + I 3 S 1 S 0
= I 0 m0 + I 1 m1 + I 2 m2 + I 3 m3
2∑
n
−1
= I i mi .
i =0

• 2n ×1 MUX is an extension to n ×2n DEC (check Sec-

tion 4.9)
• In Dec. :
– All I i where just the enable E .
– No OR Gate.

95 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.11.3 Quadrable two-to-one-line Mux (block-reuse design)
Design 1: S Y3 Y2 Y1 Y0
Yi = S ′ A i +SB i 0 A3 A2 A1 A0
1 B3 B2 B1 B0

Design 2: use four 2 × 1 MUXs

2×1 2×1
MUX MUX

2×1
MUX

2×1
MUX

2×1
MUX

96 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.11.4 Boolean Function Implementation
∑
• Given: F (x, y, z) = (1, 2, 6, 7)
• Implement it using 4×1 MUX.

• Could we use 2 × 1 MUX?

– For x = 0
F = I0 = y ′ z + y z ′,
– For x = 1
F = I 1 = y z ′ + y z = y.

2×1
MUX

97 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 ∑
Example 28 : Implement the function F (A, B,C , D) = (1, 3, 4, 11, 12, 13, 14, 15) using 8 × 1 MUX.

98 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.12 Demultiplexers (DEMUX)
• Analogous to DEC-ENC could we have MUX-DEMUX?
• 2n × 1 MUX => 1 × 2n DEMUX?
• Only the output F i = I when selectors have a minterm value of i

Fi = I mi

1 × 22
DEMUX

• HENCE: 1 × 2n DEMUX is nothing but Enabled n × 2n DEC, where the “Enable” is the input! (see Section
4.9)

99 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

4.13 HDL Models of Combinational Circuits

Homework

100 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 5

Synchronous Sequential Logic

101 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.1 Introduction
• Remember the introduction of Section 4.1.

• In “Sequential” the new output is a function of its current value (“state”) and the input.

102 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.2 Sequential Circuits
Asynchronous : Ch. 9
• Element delay determines speed.
• Basic elements are “Latches”.
• Studied only if time permits.

Synchronous : Ch. (5–8)

• Clock frequency (1GHz, 2GHz, etc.
) determines speed.
• Basic elements are “Flip Flops”
(but they are constructed from
Latches)
• Clock design is an “Electronics”
topic.
• Ch. 5–7 will be studied
• Ch. 8 is the introduction to “Com-
puter Organization” course.

103 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.3 Storage Elements: Latches (for asynchronous circuits)
5.3.1 SR Latch

( )
• Q(t + 1) Q(t ), S, R

• We will prove Q and Q’.

• Value of Q => “state”.

• Q = 1 => “set”.

• Q = 0 => “reset”.

• SR Latch with NAND implemen-

tation
(S ′ R ′ Latch)

• SR Latch with Enable =>

“when”

104 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.3.2 D Latch (Transparent Latch)
• A remedy to the forbidden condition => D Latch.
• D passes directly and stores into Q (transparent).
• What is the difference between D Latch and simply a wire!! => (memory)

Graphic Symbols

105 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.4 Storage Elements: Flip Flops (for synchronous circuits)
• Problem with Enabled D Latch is output change during the whole positive Enable period!
• Response at ONLY edge Enabled is therefore required => CLOCK (positive or negative).

106 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.4.1 Edge-Triggered D Flip-Flop
From Latches:
• Master-Slave Flip-Flip
• This is negative-edge triggered.

From Gates:

General Notes:
• Either way, clock frequency (hence system speed) is
confined to gate delay.
• f = 1/T
• The function table is the same as D-Latch with re-
placing En with Clk

Clk D Next State of Q

0/1 X No change
↑ 0 Q=0 reset
↑ 1 Q=1 set

107 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.4.2 Other Flip-Flops: JK and T Flip-Flops
• Let’s understand them right now.

• How to reach the design of these and other Flip-Flops and convert from any Flip-Flop to others is
detailed in Section 5.9

JK Flip-Flop (from D Flip-Flop)

Input Equation

D = JQ ′ + K ′Q

Characteristic Equation

Q(t + 1) = D
= JQ ′ (t ) + K ′Q(t ).

Characteristic Table
J K Q(t + 1)
0 0 Q(t ) (no change)
0 1 0 (reset)
1 0 1 (set)
1 1 Q ′ (t ) (complement)

108 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

T Flip-Flop (from D or JK Flip-Flops)

Input Equation

D = T ⊕Q

Characteristic Equation

Q(t + 1) = D
= T ⊕Q(t ).

Characteristic Table
T Q(t + 1)
0 Q(t ) (no change)
1 Q ′ (t ) (complement)

109 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.4.3 Direct Inputs (asynchronous reset)
• When power turns on, “state” is unknown.
• We need instant/direct/asynchronous reset.
• Here, active-low reset (similar to the Inv-En).

Function Table

R Clk D Q Q′
0 X X 0 1
1 ↑ 0 0 1
1 ↑ 1 1 0

110 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.5 Analysis of Clocked Sequential Circuits (Synchronous Circuits)
We represent a sequential circuit (as well as combinational) by:
• circuit drawing.
• equation (“algebraic expression”, “state equation”, “transition equation”),
• table (“state table”, “transition table”) same as “truth table”, “characteristic table”, “functional table”
in addition:
• state diagram (“Finite State Machine (FSM)”, “transition diagram”),
• timing diagram.

111 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 4,5- State Table and State Diagram (FSM)
Example 29 (Analysis with D flip-flop) .

6- Timing Diagram: A(0) = 0, B (0) = 0, x = (1, 0, 1).

1- Input Equation (appropriate notation):

D A = Ax + B x, D B = A ′ x.
2- Flip-Flop Characteristic Equation: A
A(t + 1) = D A , B (t + 1) = D B
B
3- Output and State Equations:
A(t + 1) = Ax + B x, B (t + 1) = A ′ x, x
y = (A + B )x ′ . y
112 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 4,5- State Table and State Diagram (FSM)
Example 30 (a simpler example) .

1- Input Equation (appropriate notation):

DA = A ⊕x ⊕ y

2- Flip-Flop Characteristic Equation: 6- Timing Diagram: A(0) = 0, x = (1, 0, 1), y = (0, 1, 1).
A(t + 1) = D A

3- Output and State Equations:

A(t + 1) = A ⊕ x ⊕ y A

113 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 4,5- State Table and State Diagram (FSM)
Example 31 (Analysis with j-k flip-flop) .

1- Input Equation (appropriate notation):

J A = B K A = B x ′, 6- Timing Diagram: A(0) = 0, B (0) = 0, x = (1, 0, 1).
J B = x ′ K B = A ⊕ x.

2- Flip-Flop Characteristic Equation:

A(t + 1) = J A A ′ + K A′ A A
B (t + 1) = J B B ′ + K B′ B
B
3- Output and State Equations: x
A(t + 1) = B A ′ + (B x ′ )′ A = A ′ B + AB ′ + Ax
B (t + 1) = x ′ B ′ + (A ⊕ x)′ B = B ′ x ′ + AB x +
A′B x ′.

114 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 4,5- State Table and State Diagram (FSM)
Example 32 (Analysis with T flip-flop) .

6- Timing Diagram: A(0) = 0, B (0) = 0, x = (1, 0, 1).

1- Input Equation (appropriate notation): B

T A = B x, TB = x.
x
2- Flip-Flop Characteristic Equation: y
A(t + 1) = T A ⊕ A, B (t + 1) = TB ⊕ B

3- Output and State Equations:

A(t + 1) = B x ⊕ A, B (t + 1) = x ⊕ B ,
y = AB .
115 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
5.5.1 Mealy and Moore Models of FSM
Moore:

• Output is fully synchronized with

flip-flops output and, of course,
clock even if the input is not synced.

Mealy:

• Output may change during the cycle

if input changes!
• Input should be synchronized with
clock (either with active or inactive
edge)
• The moment right before the active
edge is guaranteed to be correct.
• Very simple example:
A
D = x, y = Ax, A(0) = 0, x = (1, 0).
x synced with active edge

x synced with inactive edge

y
116 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
5.6 HDL Modles of Sequential Circuits

Homework

117 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.7 State Reduction and Assignments (needed for design)

118 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Flip-Flop Excitation Tables (inverse function)
characteristic table & equation excitation table

T Q(t + 1) T Q Q(t+1) Q Q(t+1) T

0 Q (no change) 0 0 0 0 0 0
1 Q′ (complement) 0 1 1 0 1 1
1 0 1 1 0 1
Q(t + 1) = T ⊕Q
1 1 0 1 1 0

J K Q(t + 1) J K Q Q(t+1) Q Q(t+1) J K

0 0 Q (no change) 0 0 0 0 0 0 0 X
0 1 0 (reset) 0 0 1 1 0 1 1 X
1 0 1 (set) 0 1 0 0 1 0 X 1
1 1 Q′ (complement) 0 1 1 0 1 1 X 0
1 0 0 1
Q(t + 1) = JQ ′ + K ′Q.
1 0 1 1
1 1 0 1
1 1 1 0

D Q(t + 1)
0 0 (reset)
1 1 (set)
Q(t + 1) = D

119 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.8 FSM: a generic preview
5.8.1 Rigorous Mathematical Definition (Rosen, 2007, Ch. 12)
Definition 33 (Finite-State Machines with Outputs and Finite State Automata (without outputs)) :
A Finite-State Machine (FSM) M = (S, I , O, f , g , s o ) consists of:
• S, a finite set of states,
• I , a finite input alphabet,
• O, a finite output alphabet,
• f : S × I → S, a transition function such that assigns to each state and input pair a new state,
• g , an output function that assigns to each state and input pair and output, and
• s o , an initial state.

Example 34 (Vending Machine) :

120 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.8.2 FSM and Languages:

• Language Recognition Theory of Computation (Sipser, 2006)

• Compiler Design

• Natural Language Processing

• Formal Languages
..
• .

121 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

5.9 Design Procedure: (all is about FSM design; others are routine stuff )
Example 35 (Detect 3 ones in row (overlap)) .
AB x AB y D A DB JA KA JB KB
State table, 00 0 00 0 0X 0X
reduction, and assignment 00 1 01 0 0X 1X
P.S. N.S. Y 01 0 00 0 0X X1 excitation table
x =0 x =1 01 1 10 0 1X X1 Q, Q(t+1) JK
S0 S0 S1 0 10 0 00 0 X1 0X 00 0X
S1 S0 S2 0 10 1 11 0 X0 1X 01 1X
S2 S0 S3 0 11 0 00 1 X1 X1 10 X1
S3 S0 S3 1 11 1 11 1 X0 X0 11 X0

122 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 36 (Detect 3 ones in row (with/without overlap) both (Moore and Mealy)) .

overlap Moore overlap Mealy compare to page 112

P.S. N.S./Y
1/0 x =0 x =1
S0 S1
S0 S 0 /0 S 1 /0
0/0 S1 S 0 /0 S 2 /0
0/0 S2 S 0 /0 S 2 /1
1/0
0/0
input sequence: 011011110
1/1 S2

no overlap Moore no overlap Mealy

X
0
0
Y (Moore)
1 1/0
S 0 /0 S 1 /0 S0 S1
0 Y (Mealy)
0/0
1 0/0
0 1 1/0
1/1 0/0 Y (Moore)

S 3 /1 S 2 /0 S2 Y (Mealy)
1
123 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 37 (Using a T FF, design a circuit that counts from 0 to 7. comp. to D and JK P. 109) .

Q Q(t+1) T
0 0 0
0 1 1
1 0 1
1 1 0

T0 = 1
∏−1
J =i
Ti = Aj, i >0
j =0
124 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 38 (Using a T FF, design a circuit that counts from 0 to 4 and check for unused states!) .

Q Q(t+1) T
0 0 0
0 1 1
1 0 1
1 1 0

0 0 1 0 0 1 1 0 1 1 1 1
T A2 = A 2 + A 1 A 0 T A1 = A 0 T A 0 = A ′2
1 X X X 0 X X X 0 X X X

unused states analysis:

P.S. T N.S.
A2 A1 A0 T A2 T A1 T A0 A2 A1 A0
101 110 011
110 100 010
111 110 001

125 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 39 (Detect 0101 with/without overlap) .
1/0 0/0
0/0

0/0 1/0 0/0

start A (ϕ) B (0) C (01) D (010)
1/1
1/0 x
1/1
y

Example 40 (Detect whether each 4 cycles contain 0101) .

0/0 1/1

0/0 1/0 0/0

start A (ϕ) B (0) C (01) D (010)

0/0
1/0 1/0
0,1/0 x

0,1/0 0,1/0
E (#1) F (#2) G (#3) y

126 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 41 (Convert from a JK flip-flop to T flip-flop) .
This is equivalent to: using JK flip-flop design a circuit whose state-table is the characteristic table of T flip-flop
(both are essentially the same of course).

No need for transition diagram: T Q Q(t+1) J K Q, Q(t+1) JK

0 0 0 0 X 00 0X
0 1 1 X 0 01 1X
1 0 1 1 X 10 X1
1 1 0 X 1 11 X0

0 X X 0
J =T K =T
1 X X 1

Same as P. 109

127 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 6

Registers and Counters

Same sections from book but in different order

128 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.1 Registers (n-bits, with parallel load)

2×1
MUX

Info. transfer. L function A i (t + 1) D J K D i = L ′ A i + LI i

Load circuit: MUX. 0 no change Ai Ai 0 0 J i = LI i ,
Modular vs. discrete Logic 1 Load Ii Ii Ii I i′ K i = LI i′
129 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
6.2 Synchronous Counters
6.2.1 Binary Counters

T0 = 1 (Up/Down)
∏−1
J =i
Ti = Aj, i >0 (Up)
j =0

∏−1
J =i
Ti = A ′j , i >0 (Down)
j =0

• As in Example 37 C Function T
• Clock could be +/- 0 no change 0
• Other complementing FF (P. 109) 1 count up EQ
• Count-Down counter is immediate by: T = C · EQ
• Count-enable (C)
130 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
6.2.2 Up-Down Binary Counter

U D Function Ti
0 0 no change 0
∏i −1 ′
0 1 down A , T 0 = 1 (EqD)
∏i0−1 j
1 x up 0 A j , T0 = 1 (EqU)

Ti = U ′ D · E qD +U · E qU ,
T1 = U ′ D +U = U + D
0 EqD
EqU EqU

The controllers could be:

C U Function Ti
0 x no change 0
∏i −1 ′
1 0 down A , T 0 = 1 (EqD)
∏i0−1 j
1 1 up 0 A j , T0 = 1 (EqU)

4×1
MUX

131 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.2.3 BCD Counter

• The output y = 1 during ALL the count 9

• y can enable the next stage, if any.
• The unused states are taken as X. TQ 1 = 1
• HW: do unused-state analysis. TQ 2 = Q 8′ Q 1
TQ 4 = Q 2Q 1
TQ 8 = Q 8Q 1 +Q 4Q 2Q 1
y = Q 8Q 1 .

132 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.2.4 Binary Counter with Parallel Load

Other func are possible, e.g., sync clear.

L C Function Ji Ki
0 0 no change 0 0
0 1 Up EqU EqU
1 X Load Ii I i′
J i = L ′C · E qU + L · I i
K i = L ′C · E qU + L · I i′

4×1 4×1
MUX MUX

133 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 42 (Design a BCD counter using the Binary Counter with Parallel Load) .

0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
X X X X X X X X
0 1 X X 1 1 X 0
L = A3 A0 C = A 3 + A 1 = (A 3 A 1 )′
′ ′

A3 A3
A2 A2
A1 A1
A0 A0
L C

134 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 6.3 Shift Registers
• Operations in computers are parallel (faster).

• We need sometimes serial processing/communica-

tions (slower):
– phone lines (serial communications)
– computer processing (less hardware)

• The output will delay by the number of registers. C LK

• Also, we can convert serial input to parallel. SI

D3
• Stopping transfer is done by controlling clock (as we
D2
will see).
D1
• Controlling should NOT be by controlling clock: D0
– Not changing clock path
– delays clocks in fast circuits (GHz and above)
4-bit
– Circuit/design-dependent. Shift Register

• Alternatively, using 2x1 MUX with L for each D FF,

(Sec. 6.1):
D i = L ′ A i + L A i −1 , D 0 = L ′ A o + LI

• Block diagram: serial input (I), serial output (O),

clock (C), and transfer control (L).
135 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 6.3.1 Serial Transfer (compare to parallel registers 6.1)
• Notice: the control signal width = the register
size (4 here).

• The control signal should be synchronized with

clock

• Designing the control circuit of registers is a

major part of computer organization (the sec-
ond major part is designing the circuits them-
selves, e.g., ALU)

• Example: Initial value of A and B:

136 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 6.3.2 Serial Addition
Design 1 (modular):
• Recall the parallel adder of Sec. 4.5.4 to see
the trade-off between hardware complex-
ity and speed.

• The serial adder adds one-bit at a time.

• A = A + SI (cumulatively).

• Initially: A = 0, B = SI .

• After n cycles: A = A + 0 and B = new SI.

• Controlling the FF should be by “Load” as

explained.

• The next carry-in (z) is the current carry-

out (C) => a delay caused by a D FF.

• Now: Had not we realized this trick, could

we design from scratch? Yes we can but
longer and harder. Lets see (with keeping
in mind from the FA (4.5.2) that:)

C = Qx +Q y + x y
S = x ⊕ y ⊕Q.
137 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
 Design 2 (longer):
• The summation x + y depends
on the carry (0 or 1) so it should
be represented by a state Q of a
single FF; draw the truth table:

• Using D FF:

D = Q(t + 1) = Qx +Q y + x y
S = x ⊕ y ⊕Q.

exactly the same as the outputs

C and S of the FA in design 1.
(A redesign for the FA of Sec.
4.5.2!!)

• Using JK FF:

J = x y,
K = (x + y)′ ,
S = x ⊕ y ⊕Q.

138 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 6.3.3 Universal Shift Register
• For shift right, the MSB (w.r.t.
A 3 A 2 A 1 A 0 ) or the LSB (w.r.t.
SI) should be the input to the
MUX.

• Vise versa for shift left.

139 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.4 Ripple Counters

6.4.1 Binary Ripple Counters (all counts

exist) recall synchronous 6.2.1
Hint: all toggles at -ve edge (even To ) because in
counting, A i toggles when A i −1 goes from 1 to 0

Using T FF: C l k i = A ′i −1 , C l k 0 = C l k ′ , Ti = 1.
Using D FF: C l k i = A ′i −1 , C l k o = C l k ′ , D i = A ′i

Advantages: clock divider, counter, simpler (less C LK

hardware, and hence power consumption). C1 = A0
Disadvantages: clock ripples (propagates) and C 2 = A 1
hence delays; so number of stages (n) is restricted. C = A
3 2
Design is very tricky for non binary counters (see
A3
BCD next:)
140 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Delay comparison between synchronous and ripple counters:
Suppose that the FF delay is ∆1 , the AND delay is ∆2 , the clock period is T , and # of FFs is n r , n s , respectively.

Ripple:
A 0 appears after ∆1
A 1 appears after ∆1 + ∆1 = 2∆1 , and so on...
Then, A nr −1 appears after n r ∆1 .
The last bit should appear before T (the next edge) => n r ∆1 < T .

Synchronous: (Sec. 6.2.1)

All A i appears after ∆1 (since clock is common).
However, the input to n th FF suffers from n s − 1 delays of AND gates. => (n s − 1)∆2 < T
Almost, ∆1 > 2∆2 (because the FF master-slave latch has at least 2-level gates (Sec. 5.3.2));
=> n s > 2n r => # of counts will be more than squared.

141 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.4.2 BCD Ripple Counters
Recal the counting mechanism of BCD synchronous counters 6.2.3:

x 1 1 x x 0 0 x
x 1 1 x x 0 1 x
x x x x x x x x
x 0 x x x x x x
J 2 = Q 8′ J 8 = Q 4Q 2

All FFs should either flip or resets => K i = 1 and J i either 0 or 1

If Q i feeds the clock of a FF => at +ve edges no transition => x.

FF1: flips when C k : 1 → 0 => C 1 = C k ′ AND no exception => J = 1

FF2: flips when Q 1 : 1 → 0 => C 2 = Q 1′ , AND at 9 Q 2 : 0 → 0 => J 2 = 0
FF4: flips when Q 2 : 1 → 0 => C 4 = Q 2′ , AND no exception => J 4 = 1
FF8: flips when Q 1 : 1 → 0 => C 8 = Q 1′ , AND:
at 7 (Q 8 : 0 → 1 => J 8 = 1) OR at 9 (Q 8 : 1 → 0 => J 8 =x)
142 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
6.5 Other Counters
6.5.1 Ring Counters
In control units, we need to keep track of the order
of 2n clock pulse (in which cycle we are now in?) Only
one wire of the 2n will be one at a clock cycle.

Design 1 (ring counter):

2n -bit shift register with initially “1000 · · · ”
=> 2n FFs

Design 2 :
one n-bit binary counter + one n × 2n -decoder
=> (n FFs + 2n n-input AND gates).

143 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.5.2 Johnson Counter

Design 3 : (modified ring counter):

2n−1 -bit shift register with initially “00 · · · ” + 2n 2-input AND gates
=> 2n−1 FFs + 2n 2-input AND gates.

Advantages : It is half the number of FFs than the ring counters with additional AND gates. The AND gates
are 2-input (to be compared with the n-input of Design 2)

Disadvantages : will not get out of any visited unused state!

144 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

6.6 HDL for Registers and Counters

Homework

145 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 7

Memory and Programmable Logic

146 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.1 Introduction
Motivation : memory for storing information to be processed by processor

• All circuits designed so far will be part of the processor ALU.

• The second part of the processor is the CU.
• Processor needs to access information to be processed.

Memory : collection of cells for storing information (bits) to be fetched from/to processor

• Random-Access Memory (RAM):

– Storing data (writing)
– Retrieving data (reading)
– volatile
• Read-Only Memory (ROM) is a PLD device.

Programmable Logic Device (PLD) : programming is a hardware procedure specifying bits inserted into
the device for future use. PLD may has 100s–1000,000s of gates.

• Read-Only Memory (ROM)

• Programmable Logic Array (PLA)
• Programmable Array Logic (PAL)
• Field-Programmable Gate Array (FPGA)

147 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.2 Random-Access Memory (RAM): block-design
• “Random-Access”: access time is constant

• “Byte”: 8 bits

• “Word”: multiple of bytes

• “Address”: points at word, (0) – (2k − 1).

• “capacity” or “size”: total number of bytes in

memory.

• Ex. for 10-bit address and 2-byte word length:

Si ze = 210 Words
= 1024 Words
= 1 K Words
= 1 K × 2 Bytes
= 2 KB

• 1 G = 1024 M = 210 M

• 1 M = 1024 K = 210 K

• 1 K = 1024 = 210

• 1 G = 230
148 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
7.3 Memory Decoding
7.3.1 Internal Construction of 1-bit RAM

• RAM is fabricated directly not implemented as connected components (this is just a logic diagram)

• Registers vs. RAM (inside processor, sync. with clock, faster, not expandable, etc.)

sel read function output memory content (Q) S R

0 X no. change no. output 0 no change 0 0
1 0 write 0 changes I I’ S = sel · r ead ′ · I
1 1 read Q no change 0 0 R = sel · r ead ′ · I ′
out put = sel · r ead · Q

149 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

2k -words-n-bit RAM:
(4 × 4 in this example)

• The OR gates are represented

as array logic.

• Decoder Enable accounts for

Enable to the whole memory
unit.

• Lets save the hardware of the

decoder:

150 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.3.2 Coincident Decoding
• Redesign each BC has 2 selects from Example: 1024 × n memory
2 decoders (for row/column); and • The word number 404 is addressed by 0110010100 in a direct
hence each word has two selects. list ordering.

• So, memory cells are arranged in a • but addressed as X = 01100 and Y = 10100 in coincident de-
matrix (a dot is a word). coding.

• The address now is: k/2 MSBs (X )

and k/2 LSBs (Y ).

• k × 2k -decoder (prev. design:)

2k k-input AND gates.

• 2 (k/2)×2(k/2) -decoder (coinc. dec.):

2 ∗ 2(k/2) (k/2) − i nput AND gates.

• 2k > 21+(k/2) if k > 2.

• For this decreased HW, can we de-

crease the # of pins? Lets see:

151 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.3.3 Address Multiplexing
• The Row/Column Address
Strobe (RAS/CAS) selects the
MSB/LSB part of the address
line (only k/2). A very smart
trick to reduce the number of
pins in the IC is to use only
k/2 but in two cycles using 2
registers to save X and Y .

• This is always needed in

DRAM, which is designed with
only one MOS transistor and
a capacitor that stores infor-
mation (but discharges with
time; so it needs refreshing);
while SRAM BC almost needs
6 transistors;

• DRAM saves: space, cost,

power.

152 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.4 Error Dectection and Correction

153 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.5 Read-Only Memory (ROM): non-volatile

• Motivation: flash memory and mother-

board BIOS.

• ROM: comes programmed from manu-

facturer (clients provide their truth table)

• PROM: Programmable ROM, is pro-

grammed using special burners.

• EPROM: Erasable PROM (erased by ultra-

violet application)

• EEPROM: Electrically Erasable PROM,

e.g., motherboard bios and flash memory.

• In this example, A i is the output of ORing

all decoder outputs. The crosspoints have
fuses all are normally connected to give
One (intact and shown as stars *). When
blown up (by high voltage) the crosspoint
is disconnected to give Zero.
154 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.
Example 43 (7.1) : ROM can be seen as:
Storage device : if we look at the ta-
ble row-wise. The k-bit input will se-
lected the appropriate row.

Combinational functions : if we
look at the table column-wise. The
k-bit input has n corresponding
functions A 1 -A n . For a particular
input, each function provides a
value.

155 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

ROM is one of three types of PLDs:

Same concept as ROM; we will just allude to that:

156 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.6 Programmable Array Logic (PAL) 7.7 Programmable Logic Array (PLA)

157 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

7.8 Sequential Programmable Devices: (more advanced topics)
• To add the sequential circuitry to the IC for extend-
ing PLD.

• This is a topic that is very advanced for a first course

in Digital Design.

• The most important and recent technology is Field-

Programmable Gate Array (FPGA).

• It is: VLSI circuit that can be programmed at the

user’s location.

• An FPGA contains: thousands or more pro-

grammable logic blocks.

• A logic block contains: multiplexers, gates, FFs.

• Programming requires extensive HDL coding to de-

scribe the required hardware.

• The most famous FPGA is by Xilinx nc. (/’zy-lingks)

Xilinx, Spartan 3E: Summer training, 2008, for top 10 stu-
• Breadboards, Printed Circuit Boards (PCB), FPGA, dents in digital design. The power and USB-PC connector
Fabrication. (Sec. 2.9) are shown.

158 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Chapter 8

Design at the Register Transfer Level:

(a gate to "Computer Organization")

159 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

8.1 Introduction
• Remember block design of combinational circuits, e.g., 4.7.2.

• We need the same for sequential circuits; otherwise, we will do state table for hundreds of states.

• When it comes to very large scale integration, it is impossible but block-design.

• Same concept in programming; no one writes high level functions in Assembly.

• We will provide essential tools here in this chapter and leave the rest to the whole course of “Computer
Organization”.

160 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 8.2 Register Transfer Language (RTL)
Simple examples: draw datapath vs. control

1. very simple transfer

R2 ←− R1

2. controlling the transfer (see ring counter 6.5.1 for T3)

If (T 3 = 1) then R2 ←− R1

3. more transfer at same condition

If (T 3 = 1) then R2 ←− R1, R1 ←− R2

4. other transfer and control

If (T 2 = 1) then R1 ←− R1 + R2

5. Here, we need additional MUX and feedback from datap-

ath to control.

If (T 2 = 1) then If (R1 > 0) then R1 ←− R1 + R2

If (T 3 = 1) then R2 ←− R1, R1 ←− R2

161 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

8.3 Register Transfer Language (RTL) in HDL

Homework

162 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

8.4 Algorithmic State Machines (ASMs)
Rectangle box is a state with name and
number. Transitions happens next edge
with a “Moore” control, e.g., incr_A.

Diamond box is a “Meally” condition.

Round rectangle : is a conditional Mealy

output that occurs once the condition
happens. However: the register actions
take place next edge of course.

ASM Block is therefore a rectangle box,

along with all diamonds, and rounded
boxes stemming from it. All takes place
either during the cycle (Mealy condi-
tions and outputs) or at the next edge
(register transfer).

Asynchronous Start Reset_b.

ASM vs. Flow Chart ASM is different in

the timing of actions. A ←− A + 1, R ←−
0, and transition to next state ALL hap-
pens at the end of S _0 at the edge of
next clock; while in flow-chart it is ex-
ecuted right away. E.g., R ←− 0 is in S_0
block; however, it means that the con-
troller is ready during S_0 to cause this
transfer at the exit of S_0 (next edge).

Figures (b), (c) : datapath and controls.

We can convert the ASM chart to a state

diagram for easy design like this one =>

ASMD (Algorithmic State Machine and

Datapath) combines both (a) and (b) for
very clear design and implementation
as will be seen next example:

163 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

8.5 Design Example
• 2 JK FF (E and F), and one 4-bit binary counter ( A[3 : 0]). Datapath:
• Start initiates the system: ( A = 0, F = 0).
• Each clock pulse, A is incremented.
• If A 2 = 0, E is cleared and count continues.
• If A 2 = 1, E is set to 1; then if A 3 = 0, count continues, but
if A 3 = 1, F is set to 1 on the next clock pulse and system
stops counting. Then, if St ar t = 0, system remains in the
initial state, but if St ar t = 0 repeat.

164 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Cont.
• 2 JK FF (E and F), and one 4-bit binary counter ( A[3 : 0]).
• Start initiates the system: ( A = 0, F = 0).
• Each clock pulse, A is incremented.
• If A 2 = 0, E is cleared and count continues.
• If A 2 = 1, E is set to 1; then if A 3 = 0, count continues, but
if A 3 = 1, F is set to 1 on the next clock pulse and system
stops counting. Then, if St ar t = 0, system remains in the
initial state, but if St ar t = 0 repeat.

Tracing the ASMD assuming that we come from S_2:

165 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 D G1 = G 1′ G o A 2 A 3
D G o = St ar t G 1′ G o′ +G 1′ G 0
set _E = G 1′ G o A 2
cl r _E = G 1′ G o A ′2
set _F = G 1 G o
cl r _ A _F = St ar t G 1′ G o′
i ncr _ A = G 1′ G o

166 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

 D G1 = G 1′ G o A 2 A 3
D G o = St ar t G 1′ G o′ +G 1′ G 0
set _E = G 1′ G o A 2
cl r _E = G 1′ G o A ′2
set _F = G 1 G o
cl r _ A _F = St ar t G 1′ G o′
i ncr _ A = G 1′ G o

167 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Example 44 (a whole course!) building the MIPS computer in “Computer Organization” course:

• Patterson, D. A., Hennessy, J. L., 2007. Computer Organization And Design : The Hardware/Software
Interface, 3rd Edition. MORGAN KAUFMANN, Boston
• “The hardware/software interface” wow!. Look at the branching statements and connection to func-
tion call, if conditions, etc.

168 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Appendix A

Numbering System and Binary Numbers

A-1 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Appendix B

Boolean Algebra

B-2 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Appendix C

Digital Integrated Circuits (ICs)

C-3 Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.

Bibliography

Mano, M. M., Ciletti, M. D., 2007. Digital design, 4th Edition. Prentice-Hall, Upper Saddle River, NJ.

Patterson, D. A., Hennessy, J. L., 2007. Computer Organization And Design : The Hardware/Software Inter-
face, 3rd Edition. MORGAN KAUFMANN, Boston.

Rosen, K. H., 2007. Discrete mathematics and its applications, 6th Edition. McGraw-Hill Higher Education,
Boston.

Sipser, M., 2006. Introduction to the theory of computation, 2nd Edition. Thomson Course Technology,
Boston.

Copyright © 2015, 2019 Waleed A. Yousef. All Rights Reserved.