Fundamentals of Digital Design
A story of how mathematics, logic, and physical transistors combine to create computers.
by Michelle Phung
A Note from the Author
The unique format of this ‘book’ aims to close the gap between the practical and theoretical as it applies to introductory level electrical engineering.Each new concept presented is coupled with an interactive example and the reader encouraged to play, twiddle, toggle, and change the variables. Using the interactions as a catalysis to learning the material, abstract concepts come alive on the page. It is my hope that you enjoy reading and playing along with this book as much as I have enjoyed creating it.
1 Binary Number System
The language of computers is written in binary code. In the same way we use the letters ‘C’, ‘A’, and ‘R’ to represent the word ‘car’, and the word ‘car’ to represent the concept of the automobile, computers use ‘0’s and ‘1’s to represent words, instructions, rules, everything.
The two states (state 0 and state 1) describe an entire world of software. For example:
if 1000011 represent the letter ‘C’,
and 1000001 represent ‘A’,
and 1010010 represent ‘R’,
all information can be written in binary.
Since binary is so simple (only two options ‘0’ or ‘1’), and 1000001 represent ‘A’,
and 1010010 represent ‘R’,
all information can be written in binary.
the chance of misinterpreting signals is low, and as a result, there are less likely to be errors.
binary
decimal
hexadecimal
0
1
10
11
0
1
2
3
0
1
2
3
100
101
110
111
4
5
6
7
4
5
6
7
1000
1001
1010
1011
8
9
10
11
8
9
A
B
1100
1101
1110
1111
12
13
14
15
C
D
E
F
10000
10001
10010
10011
16
17
18
19
10
11
12
13
10000
10001
10010
10011
16
17
18
19
10
11
12
13
10100
10101
10110
10111
20
21
22
23
14
15
16
17
11000
11001
11010
11011
24
25
26
27
18
19
1A
1B
11100
11101
11110
11111
28
29
30
31
1C
1D
1E
1F
100000
32
20
Let’s start with how to read binary.
The system that most of us are familiar with is the base 10 system (i.e., 1 2 3 4 5 6 7 8 9 0), also called decimal.
Base 16 system has 16 symbols (0 1 2 3 4 5 6 7 8 9 A B C D E F) and is also called hexadecimal.
There are only two numbers in the binary numbering system: ‘0’ and ‘1’. It is a base 2 system.
A letter or a subscript is used to denote the radix:
The system that most of us are familiar with is the base 10 system (i.e., 1 2 3 4 5 6 7 8 9 0), also called decimal.
Base 16 system has 16 symbols (0 1 2 3 4 5 6 7 8 9 A B C D E F) and is also called hexadecimal.
There are only two numbers in the binary numbering system: ‘0’ and ‘1’. It is a base 2 system.
A letter or a subscript is used to denote the radix:
0x32 and 3216 are in hexadecimal (base 16)
0b110010 and 1100102 are in binary (base 2)
50 and 5010 are in decimal (base 10)
The numbers increase in magnitude according to their positions.
0b110010 and 1100102 are in binary (base 2)
50 and 5010 are in decimal (base 10)
0012
= 110
0102
= 210
0112
= 310
1002
= 410
Convert Binary to Decimal
Since there are only two numbers in binary, we interpret the value of the number by the position of the numbers.
Decimal is the most familar radix, thus we start by converting binary into decimal.
First, realize that for every position left of the number, the value of that number increases by 2n.
We multiply the 0 or 1 by their position, and add the sum to convert the number into decimal.
Since there are only two numbers in binary, we interpret the value of the number by the position of the numbers.
Decimal is the most familar radix, thus we start by converting binary into decimal.
First, realize that for every position left of the number, the value of that number increases by 2n.
We multiply the 0 or 1 by their position, and add the sum to convert the number into decimal.
The first position is multiplied by 20.
The second position is multiplied by 21.
The third position is multiplied by 22.
(A fourth position would be multiplied by 23,
and a fifth position would be multiplied by 24.)
The second position is multiplied by 21.
The third position is multiplied by 22.
(A fourth position would be multiplied by 23,
and a fifth position would be multiplied by 24.)
From each bit's position, we get the powers (0, 0, and 4),
and when adding each together, the sum is the converted
value in decimal.
2 Binary Math
For handling the addition of two 1-bit numbers, the half adder works great. However, the limitation of the half-adder is that it only sums 1-bit numbers.
For addition to be useful, the number of bits must be magnitudes larger.
Column addition is a common method to work out addition, that is shows how carry - overs work.
For addition to be useful, the number of bits must be magnitudes larger.
Column addition is a common method to work out addition, that is shows how carry - overs work.
decimal addition
binary addition
3 Logic Gates
The special nature of the binary numbering system gives way to a subdivision of algebra, called Boolean algebra (also known as Boolean Logic).
Since there are only two numbers in the binary numbering system, it lends itself to other interpretations. The two numbers, ‘0’ and ‘1’ can represents states, like on and off, true and false, or HIGH and LOW signals.
Boolean algebra has its own rules, notations, and operations. There are three basic operations, AND, OR, and NOT. The gates pictured to the right are symbols that represent Boolean algebra operations. Similar to a plus or minus symbol, they represent an operation taking place that produces a single result.
These gates also represent physical electrical components, which can be used to build and control circuits, and which, in turn can be used to build
Since there are only two numbers in the binary numbering system, it lends itself to other interpretations. The two numbers, ‘0’ and ‘1’ can represents states, like on and off, true and false, or HIGH and LOW signals.
Boolean algebra has its own rules, notations, and operations. There are three basic operations, AND, OR, and NOT. The gates pictured to the right are symbols that represent Boolean algebra operations. Similar to a plus or minus symbol, they represent an operation taking place that produces a single result.
These gates also represent physical electrical components, which can be used to build and control circuits, and which, in turn can be used to build
complex computer systems.
Each of the gates have inputs on the left hand side. The AND and OR gates pictured here take 2 inputs each, and result in one output. There are more logic gate symbols and operations, but these are the basics. To gain an idea of how the AND, OR, and NOT operations work, consider ‘0’ is ‘false’ and ‘1’ is ‘true’.
Each of the gates have inputs on the left hand side. The AND and OR gates pictured here take 2 inputs each, and result in one output. There are more logic gate symbols and operations, but these are the basics. To gain an idea of how the AND, OR, and NOT operations work, consider ‘0’ is ‘false’ and ‘1’ is ‘true’.
This is an AND gate symbol.
This is an OR gate symbol.
This is an NOT gate symbol.
Truth Tables can quickly show the result of an operation on the inputs. Each operation has it’s own truth table. Logic gates can have more than two inputs but the most shown here are two. For gates with more than two inputs, a different truth table has to be made, but the rules stay the same in each case.
Addition (pictured below) is not a gate, but an operation. Very similarly, gates act as operators between it's inputs. It is the basis of math, and a computer can be thought of as a very complex adder. On the right, the truth table will highlight the line containing the inputs, and the resulting output.
plus
x
y
z
This type of chart is a called a truth table.
and
x
y
z
if the x input is 0 and the y input is 0, then the result is 0if the x input is 0 and the y input is 1, then the result is 0if the x input is 1 and the y input is 0, then the result is 0if the x input is 1 and the y input is 1, then the result is 1The AND gate outputs a true result only if all of the inputs are true. Otherwise, the result is false.
Each of the gates have inputs on the left hand side.
The NOT gate takes one input (on the left hand side), and results in one output
(on the right hand side).
Play with the inputs of the logic gates by clicking on the orange variables.
The corresponding output will change as a result of the inputs
and the truth table will highlight which outcome is currently being addressed.
or
The OR gate outputs a true signal in cases where eithere one of the inputs are true. It's output is only false when both inputs are false.
x
y
z
not
The NOT gate outputs the opposite of the input.
x
x'
xor
The XOR gate outputs a true signal if the inputs are not the same.
x
y
z
nand
The NAND gate outputs a false result only if both of the inputs are true. Otherwise, the result is true.
x
y
z
nor
The NOR gate outputs a true signal in cases when both inputs are false. Otherwise, the result is false.
x
y
z
xnor
The XNOR gate outputs a true signal if both inputs are the same.
x
y
z
Inside a Chip’s Transistors:
Physical logic gates are arrays of transistors made of silicon.
The nickname ‘Silicon Valley’ comes from the fact that a lot of chip makers began their business in the
SF Bay Area.
Electricity flows from one point in space another, it is drawn to the destination point, like water falls to the ground. Imagine that electricy is flowing down towards the ground in these diagrams, and control the flow using the orange numbers on left side of each transistor.
AND gate - Transistor Level
You can click on the orange elements
to change the diagrams.
The diagram above shows how a series of transistors (three transistors in this diagram) can be arranged so that the inputs and output to the grouping behaves as an AND gate.
Each of the gates presented before (AND, OR, NOT, NOR, NAND, XOR, etc.) can be made using transistors.
Many mathematical concepts and solutions can be created through transistors, this is the basis of computers and machines: to produce a desired output by creating a correct electrical path.
OR gate - Transistor Level
You can click on the orange elements
to change the diagrams.
The diagram above shows how a series of transistors (three transistors in this diagram) can be arranged so that the inputs and output to the grouping behaves as an OR gate.
XOR gate - Transistor Level
You can click on the orange elements
to change the diagrams.
The diagram above shows how a series of transistors (five transistors in this diagram) can be arranged so that the inputs and output to the grouping behaves as an XOR gate.
Examining the XOR gate transistors, you can see that the XOR diagram is made up of a combination of the previous AND gate pattern and the previous OR gate pattern.
5 Half, Full, and Carry Look Ahead Adders
A basic circuit is a half-adder. It adds two (one digit) numbers.
Since there are only 2 numbers in the binary system, there are only so many combinations of addition that can occur.
The output of the half-adder circuit has 2 outputs, with the output of the AND gate acting as the carry, or "over flow", when the sum is bigger than one digit.
This happens when x=1 and y=1, and subsequently the carry=1 and sum=0, which is read as output=10, the correct sum of 1+1=10.
Click on the orange gate labels
to see the truth tables, and on
the inputs to change the diagram.
When...
x=0 and y=0 then 0+0=0 (the sum = 0).
x=0 and y=1 then 0+1=1 (sum is 1).
x=1 and y=1 then 1+0=1 (sum is 1).
x=1 and y=1 then 1+1=10 (sum is 10)*.
x=0 and y=0 then 0+0=0 (the sum = 0).
x=0 and y=1 then 0+1=1 (sum is 1).
x=1 and y=1 then 1+0=1 (sum is 1).
x=1 and y=1 then 1+1=10 (sum is 10)*.
*
In the special case where x=1 and y=1, the result needs 2 bits to accurately describe the sum.
In other cases, (0+0, 0+1, 1+0), only 1 bit is necessary to accurately describe the sum.
In the special case where x=1 and y=1, the result needs 2 bits to accurately describe the sum.
In other cases, (0+0, 0+1, 1+0), only 1 bit is necessary to accurately describe the sum.
The Half Adder
One could imagine that chaining multiple half-adders together could produce our desired output for a multi-bit sum.
However, there is no input for “carrying over” when using just the half-adder.
This is where the full adder comes into play. The full-adder has an extra input called the ‘carry in’ or commonly denoted by ‘Cin’.
However, there is no input for “carrying over” when using just the half-adder.
This is where the full adder comes into play. The full-adder has an extra input called the ‘carry in’ or commonly denoted by ‘Cin’.
The Full Adder
The Full Adder. This diagram is interactive. You can click and change the orange inputs on the left hand side. You can also view the transistor overlay by clicking on the orange circles below the diagram. The two circles show three views: a transistor view (dark orange), a gate view (light orange), and a combination of both (click in the overlapping space of the two circles).
A full adder is made up of two XOR gates, two AND gates, and one OR gate.
The above animation shows that another way to interpret the scheme of the full adder is to imagine that it is composed of two half adders. Click 'start' to begin the animation.
Why the full adder?
The point, and the difference between the half adder and the full adder is the third input. The half adder has only two inputs.
In column addition, there is a need for a 'carry in'.
This ‘phantom row’ is the row in which all the carry in’s get placed.
When a column has a carry over (a figure 1) on top of it, the result of that row is the sum of 3 numbers:
the original two numbers,
plus the additional carry over.
For n-inputs, we know there are 2n unique combinations for inputs.
Let’s make some distinctions between carry in and carry out:
The addition of a third input means that there are more combinations of addition.
A truth table for a full-adder reveals how the carry in can influence the result:
Let’s take a look at binary addition again, this time keeping notice of the carry ins and carry outs.
We begin with the right most column, and this time, we can look at how reading the truth table could help us.
To reiterate:
the 1 that was “carried over”
to the next column, is added
to the sum of the next column.
When we add up the second column, we can use the truth table, however realize that the carry out from the last computation, is now the carry in to the next addition.
From the truth table,
the sum bit is 1 ,(0+0+1=1)
and the carry out bit is 0.
This continues left, carrying over as necessary. When the carry out bit = 0, it is usually omitted, and understood that ‘nothing’ is added.
When we add up the second column, we can use the truth table, however realize that the carry out from the last computation, is now the carry in to the next addition.
From the truth table,
the sum bit is 1 ,(0+0+1=1)
and the carry out bit is 0.
This continues left, carrying over as necessary. When the carry out bit = 0, it is usually omitted, and understood that ‘nothing’ is added.
4 bit Enumeration
A 4-bit adder adds two 4-bit numbers. It has four, and only four, places in each number. This means that the minimum number that one of the addends can be is 0000.
The maximum an addend can be is 11112. (recall: 11112 = 1510)
Since the adder is going to sum the LSB (least significant bit) of A with the LSB (least significant bit) of B, then every corresponding bits after that, it is clarifying to name each bit.
So when we add them together, roughly, it would look something like this:
The maximum an addend can be is 11112. (recall: 11112 = 1510)
Since the adder is going to sum the LSB (least significant bit) of A with the LSB (least significant bit) of B, then every corresponding bits after that, it is clarifying to name each bit.
So when we add them together, roughly, it would look something like this:
An example: A + B = ?, where A=11012 B=10012
Similarly for B:
Notice that the “carry-outs” are the “carry-ins” for the next column.
Similarly for B:
Notice that the “carry-outs” are the “carry-ins” for the next column.
The full adder (again):
Note that each of the inputs (x, y, carryin) and outputs (sum, carryout) are 1 bit signals. Paired with each equation, we would need 4 full adders to create the
5-bit wide sum:
Note that each of the inputs (x, y, carryin) and outputs (sum, carryout) are 1 bit signals. Paired with each equation, we would need 4 full adders to create the
5-bit wide sum:
Cout
Sum3
Sum2
Sum1
Sum0
*the final carryout represents the MSB (most significant bit) of the sum
*the final carryout represents the MSB (most significant bit) of the sum
The Full Adder
It may help to realize:
Carry in1=Carry out0
Carry in2=Carry out1
Carry in3=Carry out2
Carry in4=Carry out3*
Carry in2=Carry out1
Carry in3=Carry out2
Carry in4=Carry out3*
The 4-bit Ripple Carry Adder
Chaining multiple full adders like this will create n-bit adders.
This scheme is called a ripple-carry adder; the carry bit
“ripples” through the circuit.
Electricity traveling through logic gates is very fast, but not simultaneous. In order for the next full adder to start it’s computation, it must receive the carry in signal from the last full adder.
The full adder following also has to wait for the one before it to get last bit of the sum.
This waiting time is called propagation delay.
Electricity traveling through logic gates is very fast, but not simultaneous. In order for the next full adder to start it’s computation, it must receive the carry in signal from the last full adder.
The full adder following also has to wait for the one before it to get last bit of the sum.
This waiting time is called propagation delay.
The 4-bit Ripple Carry Adder
Improving on the Ripple Carry Adder
The propagation delay from the time the adder starts obtaining the first carry to the time it gets the last carry out in a ripple carry adder means that for an n-bit adder, the n-th adder must wait n times the propagation delay of one full adder. For example, if there are 64-bit numbers being added together, the last bit and its carry-out would have had to wait 64 times the propagation delay of each of the full adders.This lag is exacerbated when larger number of bits are being added together.
There are other types of adders. The most efficient currently is called the Carry-Look Ahead Adder. The trade off with the Carry-Look Ahead adder is that it uses many more logic gates than the Ripple-Carry Adder, but is much faster.
The reason that the Ripple-Carry adder is slow is because the carrys must ripple through the circuit, one at a time, as this is how the circuit is set up.
However, if the circuit could recieve all of carrys at the same time, then all the bits of the sum would occur at once, instead of obtaining them one bit at a time.
However, if the circuit could recieve all of carrys at the same time, then all the bits of the sum would occur at once, instead of obtaining them one bit at a time.
The Carry Look Ahead Adder
To get all the carry-outs at the same time, we can rely on the following equations:
c1 = g0+p0c0
c2 = g1+p1c1
c3 = g2+p2c2
c4 = g3+p3c3
ci+1 = gi+pici
where :
i goes from 1 to 4,
c0 is the intial carry in,
gi is called the ‘generate’ term, from Ai AND Bi
pi is called the ‘propagate‘ term, from Ai OR Bi
It looks as though each ci+1 would depend on ci, indicating a delay, but since all the p’s and g’s are received simultaneously, the equations can be expanded:
c1 = g0+p0c0
c2 = g1+p1c1 = g1+p1(g0+p0c0)
c3 = g2+p2c2 = g2+p2(g1+p1(g0+p0c0))
c4 = g3+p3c3 = g3+p3(g2+p2(g1+p1(g0+p0c0)))
When there are more bits being added, say in a 16-bit or 32-bit adder, the number of logic gates increases, but it takes the same amount of time to arrive at the sum.
c1 = g0+p0c0
c2 = g1+p1c1 = g1+p1(g0+p0c0)
c3 = g2+p2c2 = g2+p2(g1+p1(g0+p0c0))
c4 = g3+p3c3 = g3+p3(g2+p2(g1+p1(g0+p0c0)))
When there are more bits being added, say in a 16-bit or 32-bit adder, the number of logic gates increases, but it takes the same amount of time to arrive at the sum.
The Carry Look Ahead Adder
References
Computer Organization and Design:
The Hardware / Software Interface
David Patterson and John L. Hennessy, 4th Edition
ISBN 978-0-12-374493-7
2009, Morgan Kaufmann Publishers
Digital Design: Principles and Practices
John F. Wakerly, 3rd Edition - updated
ISBN 0-13-089891-1
2001, Prentice Hall
Fundamentals of Electrical Circuits
Charles K. Alexander and Matthew N.O. Sadiku,
3rd Edition
ISBN 10-0-07-297718-3
2007, McGraw-Hill
The Hardware / Software Interface
David Patterson and John L. Hennessy, 4th Edition
ISBN 978-0-12-374493-7
2009, Morgan Kaufmann Publishers
Digital Design: Principles and Practices
John F. Wakerly, 3rd Edition - updated
ISBN 0-13-089891-1
2001, Prentice Hall
Fundamentals of Electrical Circuits
Charles K. Alexander and Matthew N.O. Sadiku,
3rd Edition
ISBN 10-0-07-297718-3
2007, McGraw-Hill
Digital Design and Computer Architecture
David M. Harris and Sarah L. Harris, 2nd Edition
ISBN 978-0-12-394424-5
2013, Morgan Kaufmann Publishers
David M. Harris and Sarah L. Harris, 2nd Edition
ISBN 978-0-12-394424-5
2013, Morgan Kaufmann Publishers