CMSC 250: Digital Circuits, Number Systems,
Adder Circuits
Justin Wyss-Gallifent
September 16, 2021
1 Digital Logic Circuits . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Digital Circuits and Gates . . . . . . . . . . . . . . . . . . 2
1.2 Circuit Diagrams . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Input-Output Tables for Circuit Diagrams . . . . . . . . . 5
1.4 Boolean Expressions for Circuit Diagrams . . . . . . . . . 6
1.5 Circuit Diagrams for Boolean Expressions . . . . . . . . . 7
1.6 Boolean Expression for a Given Input-Output Table . . . 9
1.7 Equivalent Circuits . . . . . . . . . . . . . . . . . . . . . . 10
2 Number Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1 Introduction and Base 10 . . . . . . . . . . . . . . . . . . 10
2.2 Base 8 (Octal) . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Base b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Base 16 (Hexadecimal) . . . . . . . . . . . . . . . . . . . . 11
2.5 Base 2 (Binary) . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Base 10 to Base b the Slow Way . . . . . . . . . . . . . . 12
2.7 Base 10 to Base b the Fast Way . . . . . . . . . . . . . . . 12
2.8 Binary to Octal and Hexadecimal by Grouping . . . . . . 13
2.9 Octal and Hexadecimal to Binary by Grouping . . . . . . 14
2.10 Base n Addition . . . . . . . . . . . . . . . . . . . . . . . 14
3 Designing Circuits for Binary Addition . . . . . . . . . . . . . . . 16
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Half-Adders . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Full-Adders . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 An Adder Circuit for n Bits . . . . . . . . . . . . . . . . . 18
1
1 Digital Logic Circuits
1.1 Digital Circuits and Gates
Consider the following digital circuit which represents a battery (on the left)
connected to a bulb (on the right) with a switch (at the top).
It’s obvious that when the switch is closed, the bulb is lit.
Now consider the following two circuits:
Figure 1: Series
Figure 2: Parallel
In the first figure the bulb will be lit only when both swiches are closed (think
AND) whereas in the second figure the bulb will be lit if either or both of the
switches are closed (think OR).
It’s obvious that we could combine these. For example in the following picture
there are three switches and the bulb will be lit if either both the top switches
is closed or the bottom switch is closed, or both of these are true:
2
Figure 3: Combination
It’s obvious that these diagrams could get really messy very quickly so what we’ll
do is strip away the unnecessary details and focus on the control mechanisms
in a more abstract way.
Instead of saying “open” we’ll use the value 0 and instead of saying “closed”
we’ll use the value 1. For purposes of AND, OR, and NOT, treat 0 as False and
1 as True.
In addition we can think of 0 as “off” (no power) and 1 as “on” (power!).
Definition 1.1.1. An AND gate is a control mechanism in which there are two
inputs (each either 0 or 1) and one output (either 0 or 1). The output will be
1 iff both inputs are 1. We draw this as follows:
In this sense:
output = input1 ∧ input2
�
Definition 1.1.2. An OR gate is a control mechanism in which there are two
inputs (each either 0 or 1) and one output (either 0 or 1). The output will be
1 iff one or both inputs are 1. We draw this as follows:
In this sense:
output = input1 ∨ input2
�
To round things out:
Definition 1.1.3. A NOT gate is a control mechanism in which there is one
input (either 0 or 1) and one output (either 0 or 1). The output will be 1 iff the
input is 0. We draw this as follows:
3
In this sense:
output = ∼ input1
�
Note 1.1.1. Actually constructing not gates in circuits is a little more chal-
lenging than just using switches and we won’t cover it here.
�
1.2 Circuit Diagrams
Now for the fun part. We can start creating new circuit diagrams by putting
these together.
p
q
r
Example 1.1. Observe, for example, that if p = 1, q = 1, and r = 0 then the
AND gate outputs 1 ∧ 1 = 1 which feeds into the OR gate along with r = 0
which then outputs 1 ∨ 0 = 1 which then feeds into the NOT gate which then
outputs ∼ 1 = 0. So if all three input switches are closed then the ouput switch
is open.
�
There are certain rules for these diagrams, they are the following:
1. Never combine two input wires.
2. A single input wire can be split partway and used as input for two separate
gates.
3. An output wire can be used as input.
4. No output of a gate can eventually feed back into that gate.
4
1.3 Input-Output Tables for Circuit Diagrams
In order to see how these circuit diagrams function we can draw output tables.
To draw an output table we trace each possible combination of inputs through
the circuit and create a table which shows the results.
Consider this example. In the following when two wires meet at a solid point
then the wire is meeting/splitting whereas if there is no solid point they are not
meeting.
q
p
Example 1.2. Let’s look at the input p = 1 and q = 0. We can follow them
through the logic gates step by step.
1
0
First we follow the values through their first gates and label the outputs accord-
ingly:
1
0
1
0
1
0
1
0
Then we follow the value from our leftmost AND gate and label the output
accordingly:
5
1
0
1
0
1
0
1
0
1
Then we follow the values from the OR gate and the NOT gate into the rightmost
AND gate and label the output accordingly:
1
0
1
0
1
0
1
0
1
1
1
1
If we try this with the other three possibilities and put them together in a table
we get the following:
p q Output
0 0 0
0 1 1
1 0 1
1 1 0
�
1.4 Boolean Expressions for Circuit Diagrams
Instead of following specific values through we could also trace variables through,
building the result as we go.
Here is the above example. We have filled in as with before but now with
variables:
Example 1.3. Consider:
6
q
p
p ∨ q
p ∧ q ∼ (p ∧ q)
∼ (p ∧ q) ∧ (p ∨ q)
Thus we see the boolean expression is:
∼ (p ∧ q) ∧ (p ∨ q)
Note that this is the same as XOR, which we also see in the table above.
�
1.5 Circuit Diagrams for Boolean Expressions
Let’s now reverse the situation. Suppose we are given a boolean expression and
we wish to design a circuit which represents this.
We start filling in the diagram from the right side by looking at the last opera-
tor which was applied. We proceed recursively with the subsequent operators,
working our way left until we hook up the input variables. If input variables
are repeated we just make sure we merge them on the left.
This is a bit confusing to write down and is much more clear with an example.
Example 1.4. Let’s draw a circuit diagram for the boolean expression:
(∼ p ∨ q)∧ ∼ r
The last operator we applied was ∧ so we put that on the right. The inputs are
(∼ p ∨ q) and ∼ r so we can put those as inputs temporarily:
∼ p ∨ q
∼ r
Then we do the same, recursively, for ∼ p ∨ q and ∼ r:
7
r
∼ p
q
Lastly with the ∼ p:
r
p
q
Since the input variables are all different there is no merging to do.
�
Example 1.5. Suppose the previous question had been:
(∼ p ∨ q)∧ ∼ p
We would have reached:
p
p
q
Now we notice that there are two p on the left. Thus we merge them to become
one input:
8
p
q
�
1.6 Boolean Expression for a Given Input-Output Table
Now for a more challenging and more realistic situation. Suppose we are given
an input-output table and wish to design a circuit which represents the table.
Example 1.6. For example can we design a circuit which produces this:
p q r Output
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
�
The systematic way we can find an appropriate boolean expression (and a circuit
if we need it) is to follow these steps:
1. For each row which contains a 1 in the output column construct a ∧-only
statement form which is true only under the conditions of the row.
2. Then simply ∨ these together.
Example 1.7. In the example above the first row has p = 0, q = 0, and r = 0.
We construct the statement form ∼ p∧ ∼ q∧ ∼ r. Note this statement will then
be true only for this row.
Likewise for the second, fourth and eighth rows we construct ∼ p∧ ∼ q ∧ r,
∼ p ∧ q ∧ r, and p ∧ q ∧ r respectively.
The final boolean expression is then:
(∼ p∧ ∼ q∧ ∼ r) ∨ (∼ p∧ ∼ q ∧ r) ∨ (∼ p ∧ q ∧ r) ∨ (p ∧ q ∧ r)
�
Note that we could go from here directly to a circuit but it would be fairly
complex. In many cases it can be easier to first simplify the boolean expression
first and then build the circuit.
9
1.7 Equivalent Circuits
Definition 1.7.1. Two circuits are said to be equivalent if they have boolean
expressions which are logically equivalent.
2 Number Bases
2.1 Introduction and Base 10
What does it mean to use base 10? It means that when we write a number,
such as 639, the 9 is in the 1s place, the 3 is in the 10s place, and the 6 is in the
100s place.
If we think of 1 = 100, 10 = 101, and 100 = 102 then we are saying:
639 = 6 · 102 + 3 · 101 + 9 · 100
In general a number in base 10 has the expression:
n is written as …d3d2d1d0
Where 0 ≤ di ≤ 9 and:
n = … + d3 · 103 + d2 · 102 + d1 · 101 + d0 · 100
When we want to be completely clear that …d3d2d1d0 is in base 10 we’ll subscript
the number with 10, for example:
63910
2.2 Base 8 (Octal)
In general a number in base 8 has the expression:
n is written as …d3d2d1d0
Where 0 ≤ di ≤ 7 and:
n = … + d3 · 83 + d2 · 82 + d1 · 81 + d0 · 80
Example 2.1. For example the expression 462 in base 8 represents the number:
462 = 4 · 82 + 6 · 81 + 2 · 80 = 30610
�
When we want to be completely clear that …d3d2d1d0 is in base 8 we’ll subscript
the number with 8, for example the above would be:
4628 = 30610
10
2.3 Base b
In general a number in base b has the expression:
n is written as …d3d2d1d0
Where 0 ≤ di ≤ b− 1 and:
n = … + d3 · b3 + d2 · b2 + d1 · b1 + d0 · b0
Example 2.2. For example the expression 235 in base 6 represents the number:
2356 = 2 · 62 + 3 · 61 + 5 · 60 = 8510
�
Observe that when b > 10 the “digits” would need to be 10 and larger. Typically
what is done is that after 9 we continue with A, B, C, etc.
2.4 Base 16 (Hexadecimal)
In general a number in base 16 has the expression:
n is written as …d3d2d1d0
Where di ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F} and we have the following,
where A is interpreted as 10, B as 11, and so on:
n = … + d3 · 163 + d2 · 162 + d1 · 161 + d0 · 160
Example 2.3. For example the expression 4EA in base 16 represents the num-
ber:
4EA16 = 4 · 162 + 14 · 161 + 10 · 160 = 125810
�
2.5 Base 2 (Binary)
In general a number in base 2 has the expression:
n is written as …d3d2d1d0
Where 0 ≤ di ≤ 1 and:
n = … + d3 · 23 + d2 · 22 + d1 · 21 + d0 · 20
Example 2.4. For example the expression 110101 in base 2 represents the
number:
1101012 = 1 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 5310
�
11
2.6 Base 10 to Base b the Slow Way
We’ve seen how to convert from base b to decimal. To convert from decimal to
base b. Given a decimal number n, the most obvious way is to start by finding
the largest power of b, say bi, which is less than n, then count how many of
those you can subtract from n still keeping a nonnegative result. That value is
your leftmost digit.
Next, repeat the process with bi−1, bi−2, and so on, adding the resulting digits
to the right until a result of 0 is obtained.
Example 2.5. Let’s convert 978910 to base 8. First we observe that 8
4 = 4096
and 85 = 32768 so 84 = 4096 is the largest. We can subtract two of these:
9789− 2(4096) = 1597
Thus our leftmost digit is 2.
Then we have 1597 left. From this we can subtract three 83 = 512s:
1597− 3(512) = 61
Thus our next digit is 3.
Then we have 61 left. From this we can subtract zero 82 = 64s. Thus our next
digit is 0.
Then we still have 61 left. From this we can subtract seven 81 = 8s:
61− 7(8) = 5
Thus our next digit is 7.
Now we have 5 left so the final digit is 5.
Thus:
978910 = 230758
�
2.7 Base 10 to Base b the Fast Way
There’s a slicker, more organized way to go about this. Let’s to back to our
example of 9789 which we’d like in base 8.
What we do is start with 9789 and repeatedly divide by 8, each successive time
using the previous quotient as the dividend and continuing until the quotient is
0:
9789÷ 8 = 1223R 5
1223÷ 8 = 152R 7
152÷ 8 = 19R 0
19÷ 8 = 2R 3
2÷ 8 = 0R 2
12
We then put down the remainders in reverse order:
978910 = 230758
This looks a bit like magic so it’s worth taking a second to see what this calcu-
lation has actually told us. If we rewrite the successive divisions above:
9789 = 1223 · 8 + 5
= (152 · 8 + 7) · 8 + 5
= 152 · 82 + 7 · 8 + 5
= (19 · 8 + 0) · 82 + 7 · 8 + 5
= 19 · 83 + 0 · 82 + 7 · 8 + 5
= (2 · 8 + 3) · 83 + 0 · 82 + 7 · 8 + 5
= 2 · 84 + 3 · 83 + 0 · 82 + 7 · 8 + 5
This is exactly the expansion we wanted!
Note that when we convert to hexadecimal we have to keep an eye on our digits
A through F .
Example 2.6. Let’s convert 20075 to hexadecimal.
20075÷ 16 = 1254R 11
1254÷ 16 = 78R 6
78÷ 16 = 4R 14
4÷ 16 = 0R 4
The “digits” 4, 14, 6, and 11 become 4E6B16.
�
2.8 Binary to Octal and Hexadecimal by Grouping
In the special case when we wish to convert between binary and either octal or
hexadecimal we can do so quickly by grouping. This works specifically because
8 and 16 are powers of 2.
To convert to octal simply group the bits into groups of three and convert each
group directly to octal. Make sure to group from right to left and prepend 0s if
necessary.
Example 2.7. Let’s convert 110101000011102 to octal. We group them and
prepend a single 0 and convert:
Binary 011 010 100 001 110
Octal 3 2 4 1 6
13
Thus the answer is 324168.
�
To convert to hexadecimal simply group the bits into groups of four and convert
each group directly to octal. Make sure to group from right to left and prepend
0s if necessary. We may have to think of an intermediate decimal value for each
group but the values are small.
Example 2.8. Let’s convert 111101011011102 to hexadecimal. We group them
and prepend two 0s and convert:
Binary 0011 1101 0110 1110
Decimal 3 13 6 14
Hexadecimal 3 D 6 E
Thus the answer is 3D6E16.
�
2.9 Octal and Hexadecimal to Binary by Grouping
In these cases we can simply reverse the above procedure.
Example 2.9. Let’s convert 56108 to binary. We simply convert 5, 6, 1, and
0 independently and string them together, yielding 101, 110, 001, and 000 so
then 1011100010002.
�
Example 2.10. Let’s convert A5D916 to binary. We simply convert A, 5, D,
and 9 independently and string them together, yielding 1010, 0101, 1110, and
1001 so then 10100101111010012.
�
2.10 Base n Addition
We add in base n just as we do in decimal. When we add digits we have to
make sure that the resulting number is in the correct base and we must carry
when appropriate. This requires that we can convert relatively small numbers
into the necessary base but this is usually pretty easy to do.
Example 2.11. Let’s do 2345 + 4035. We line them up:
2 3 4
4 0 3
We add 4 + 3 = 7 and in base 5 this is 12 so we put down the 2 and carry the 1:
14
1
2 3 4
4 0 3
2
Then we add 1 + 3 + 0 = 4 and in base 5 this is still 4 so we put down the 4:
1
2 3 4
4 0 3
4 2
Then we add 2 + 4 = 6 and in base 5 this is 11 so we put that down:
1
2 3 4
4 0 3
1 1 4 2
Thus:
2345 + 4035 = 11425
�
When we do hexadecimal we have to be careful with our sums because of A
through F .
Example 2.12. Consider 7F2E16 + BD5C16. We line them up:
7 F 2 E
B D 5 C
We add E + C = 1A in hexadecimal so we put down the A and carry the 1:
1
7 F 2 E
B D 5 C
A
Then we add 1 + 2 + 5 = 8 in hexadecimal so we put down the 8:
1
7 F 2 E
B D 5 C
8 A
Then we add F + D = 1C in hexadecimal so we put down the C and carry the
1:
1 1
7 F 2 E
B D 5 C
C 8 A
15
Then we add 1 + 7 + B = 13 in hexadecimal so we put down both:
1 1
7 F 2 E
B D 5 C
1 3 C 8 A
The result is then 13C8A16.
�
Binary is a little easier since there are only a few possible sums. Here’s an
example without all the details:
Example 2.13. Here is 11001010112 + 01101100112.
1 1 1 1
1 1 0 0 1 0 1 0 1 1
0 1 1 0 1 1 0 0 1 1
1 0 0 1 1 0 1 1 1 1 0
�
3 Designing Circuits for Binary Addition
3.1 Introduction
Let’s now pull together everything we know and build a circuit out of our three
gates that adds two binary numbers. When we add two binary numbers bit-by-
bit we could simply be adding two bits or we could be adding three bits when
there is a carry bit.
3.2 Half-Adders
First let’s just see how to add two bits. There are four possibilities. In each
we’ll write the result as two bits for future reference. These results are the sum
bit and carry bit, the latter because we’ll need to carry it, as we’ll see:
p q carry sum
0 + 0 = 0 0
0 + 1 = 0 1
1 + 0 = 0 1
1 + 1 = 1 0
Observe that the result in the 1’s place is the same as XORing the starting bits
and the result in the 2’s place is the same as ANDing the starting bits.
It follows that with an XOR circuit and an AND gate we can add two bits.
Since we only have ∧, ∨, and ∼ we first observe that:
pXOR q = (p ∨ q)∧ ∼ (p ∧ q)
We can therefore build a circuit that will do the job.
16
Definition 3.2.1. A half-adder adds two bits and produces a sum bit and a
carry bit. One way to design this circuit is as follows:
p
q
c
s
Take a second to trace through this to see that s and c will contain the sum
bits (the ⊕) and the carry bit (the ∧).
3.3 Full-Adders
Now let’s see how to add three bits. There are eight possibilities. In each we’ll
write the result as two bits for future reference.
p + q + r carry sum
0 + 0 + 0 = 0 0
0 + 0 + 1 = 0 1
0 + 1 + 0 = 0 1
0 + 1 + 1 = 1 0
1 + 0 + 0 = 0 1
1 + 0 + 1 = 1 0
1 + 1 + 0 = 1 0
1 + 1 + 1 = 1 1
While we could get really technical and figure out how to draw a circuit for this,
interestingly it can be built out of two half-adders and an OR gate.
Definition 3.3.1. A full-adder adds three bits and produces a sum bit and a
carry bit. One way to design this circuit is as follows:
HA
HAr
q
p
s
c
c
s
c
s
17
It’s far less obvious than the half-adder that this does what is intended. Basically
this circuit makes two claims. Here the functions s and c return the sum and
carry bits respectively.
1. s(p, q, r) = s(s(p, q), r) which equals (p⊕ q)⊕ r.
2. c(p, q, r) = c(p, q) ∨ c(s(p, q), r) which equals (p ∧ q) ∨ ((p⊕ q) ∧ r).
This can be verified by simply writing down a truth table which contains the
two logical expressions above.
p q r p⊕ q (p⊕ q)⊕ r (p⊕ q) ∧ r p ∧ q ((p⊕ q) ∧ r) ∨ (p ∧ q)
0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0
0 1 0 1 1 0 0 0
0 1 1 1 0 1 0 1
1 0 0 1 1 0 0 0
1 0 1 1 0 1 0 1
1 1 0 0 0 0 1 1
1 1 1 0 1 1 1 1
We can see that the column (p⊕ q)⊕ r equals the value of the sum bit and the
column ((p⊕ q) ∧ r) ∨ (p ∧ q) equals the value of the carry bit.
3.4 An Adder Circuit for n Bits
The key to building a circuit which adds binary numbers is to observe that we
start by adding the rightmost bits, and there are only two of those, so we can
use a half-adder.
Each successive addition involves three bits, one of which is the carry bit from
the previous sum and which might be 0.
The very last addition takes the carry bit and just dumps it on the left. We can
therefore proceed as follows to add the binary numbers represented by an…a1
and bn…b1 to get dn+1dn…d1.
In total then we require 1 half-adder and n− 1 full adders:
FA FA FA HA
dn+1 dn
sc
…
d3
sc
…
d2
sc
d1
sc
an bn a3 b3 a2 b2 a1 b1
. . .
18
Digital Logic Circuits
Digital Circuits and Gates
Circuit Diagrams
Input-Output Tables for Circuit Diagrams
Boolean Expressions for Circuit Diagrams
Circuit Diagrams for Boolean Expressions
Boolean Expression for a Given Input-Output Table
Equivalent Circuits
Number Bases
Introduction and Base 10
Base 8 (Octal)
Base b
Base 16 (Hexadecimal)
Base 2 (Binary)
Base 10 to Base b the Slow Way
Base 10 to Base b the Fast Way
Binary to Octal and Hexadecimal by Grouping
Octal and Hexadecimal to Binary by Grouping
Base n Addition
Designing Circuits for Binary Addition
Introduction
Half-Adders
Full-Adders
An Adder Circuit for n Bits