Computer Architecture Lecture Notes

Lecture 2

Ioana Karnstedt-Hulpus,
Utrecht University

September 5, 2025
Contents

3 Boolean Algebra 3
3.1 Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Boolean Functions and Truth Tables . . . . . . . . . . . . . . . . 4

4 Basic Digital Gates 7

4.1 Very Basics of Electrical Circuits . . . . . . . . . . . . . . . . . . 7
4.2 Elementary Logic Gates . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Combinational Circuits . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.1 Arithmetic Circuits . . . . . . . . . . . . . . . . . . . . . . 13
4.4 Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4.1 Delay circuits . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4.2 Asymmetrical clocks . . . . . . . . . . . . . . . . . . . . . 20
4.4.3 Pulse generators . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 Memory Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5.1 Latches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5.2 Flip flops . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5.3 Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6 Moore’s law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2
Chapter 3

Boolean Algebra

Boolean algebra manipulates two-state binary values that are typically la-
beled True/False, 1/0, yes/no, on/off, and so forth. In this lecture, we mostly
use 1/0 except when discussing logical operations, in which case we sometimes
also use True/False for their more intuitive nature in logic. Boolean functions
operate on binary inputs and return binary outputs. Since computer hardware
is based on representing and manipulating binary values, Boolean functions
and hence Boolean algebra provides the mathematical abstraction to study and
design digital circuits. Therefore, Boolean algebra plays a central role in the
specification, analysis, optimization and hardware architecture.

3.1 Boolean Operators

Some of the most commonly used Boolean operators are And, Or and Not. They
are shown in Figure 3.1. The names of the operators are conventional names
(used as such by convention) that seek to describe the underlying semantics.
Other common notations of these operators are:

Conjunction : x AND y, x · y, x ∧ y

Disjunction : x OR y, x + y, x ∨ y

Negation : NOT x, ¬x, x

Other operators that we will frequently encounter are shown in Table 3.1

x y x AND y x y x OR y x NOT x
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1 (c) The NOT op-
1 1 1 1 1 1 erator (negation)
(a) The AND operator (b) The OR operator
(conjunction) (disjunction)

Figure 3.1: Three common Boolean operators

3
 x y x NAND y x NOR y x XOR y
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 0 0 0

Table 3.1: Other Boolean Operators. NAND stands for Not AND, NOR stands
for Not OR, XOR stands for Exclusive OR

x y z F
0 0 0 0
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 0

Table 3.2: Defining a function through its truth table

3.2 Boolean Functions and Truth Tables

Boolean Functions take as inputs binary variables and the results they output
are also binary. A function over n binary variables can be applied to 2n combi-
nations of variable values. Consequently, any Boolean function can be defined
by the exhaustive enumeration of its 2n possible input combinations with the
corresponding output. Such an exhaustive function definition is called the truth
table.
Actually, the tables in Figure 3.1 and Table 3.1 are the truth tables corre-
sponding to the Boolean functions defined by the operators. Table 3.2 defines
a function F over three variables through its truth table.
The other way of defining Boolean functions is through Boolean expressions.
For example, the function defined in the truth table in Table 3.2 can also be
defined by the Boolean expression F (x, y, z) = (x ∨ y) ∧ ¬z. Then, the first
entry in the truth table is equivalent to evaluating the expression F (0, 0, 0) =
(0 ∨ 0) ∧ ¬0. This expression evaluates to 0. The same can be achieved for the
remaining entries.
It is therefore quite straightforward to write the truth table of a Boolean
function given its Boolean expression, by simply evaluating the expression for
each variable combination. However, given a truth table, the process of synthe-
sizing the Boolean expression of its function requires a more complex algorithm.
One such algorithm is based on two observations: First, the expression should
evaluate to 1 for the input combinations that have a 1 as output. In our exam-
ple, if any one of the following variable combinations is given as input: (0, 1,
0), or (1, 0 , 0) or (1, 1 ,0), the expression should evaluate to 1.
The second observation is that the AND operator evaluates to 1 in exactly
one case: when all the input variables are 1. Therefore, for any input combina-
tion, we can write a Boolean expression that evaluates to 1 by applying the AND

4
 Name Conjunctive form Disjunctive form
Identity law 1∧x=x 0∨x=x
Null law 0∧x=0 1∨x=1
Idempotent law x∧x=x x∨x=x
Inverse law x ∧ ¬x = 0 x ∨ ¬x = 1
Commutative law x∧y =y∧x x∨y =y∨x
Associative law (x ∧ y) ∧ z = x ∧ (y ∧ z) (x ∨ y) ∨ z = x ∨ (y ∨ z)
Distributive law x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
Absorption law x ∧ (x ∨ y) = x x ∨ (x ∧ y) = x
De Morgan’s law ¬(x ∧ y) = ¬x ∨ ¬y ¬(x ∨ y) = ¬x ∧ ¬y

Table 3.3: Boolean operator laws

operator over the variables whose value is 1 and the negations of the variables
whose value is 0. For example, we can create a function g(x, y, z) whose value
is 1 only for the input combination (0, 1, 0) by applying the AND operation
(conjunction) over (NOT(x), y, NOT(z)): g(x, y, z) = ¬x ∧ y ∧ ¬z.
With these two observations, the algorithm to synthesize Boolean expres-
sions from truth tables is as follows:

1. For each row in which the function value is 1, negate each variable whose
value is 0 and keep each variable whose value is 1, then apply the con-
junction over all these variables

2. Write the expression that is the disjunction (OR) of the Boolean expres-
sions obtained in the previous step

For the example in Table 3.2, this algorithm would synthesize the Boolean
expression:
F (x, y, z) = (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z)
This expression is different from the expression we showed before (F (x, y, z) =
(x ∨ y) ∧ ¬z), but they both correspond to the same function. This means that
the two Boolean expressions are equivalent. As we shall see, Boolean expression
equivalence is very important for digital circuit optimization.
Using the above algorithm for synthesizing Boolean expressions from truth
tables, we always obtain expressions that use only the three main operators:
AND, OR and NOT. More specifically, such expressions are always disjunctions
over multiple conjunctions, and each variable or its negation is present in ev-
ery conjunction. Such expressions are called the Disjunctive Normal Form - a
normalization of Boolean functions.
Interestingly, this means that any Boolean function can be represented by
using only the AND, OR and NOT operators. However although the DNF is
straightforward to construct from any truth table, it is frequently not a very
compact formula. Algebraic manipulations are used to reach simpler forms of
functions. Such manipulations make use of the properties of Boolean operators,
which are called laws. Table 3.3 summarizes some such laws.
Using these laws, it is straightforward to obtain multiple equivalent expres-
sions for the same function. Nevertheless, obtaining simplified expressions for
a function is a challenging problem. Reducing a Boolean expression into its
simplest form is an NP-hard problem.

5
Example:

F (x, y, z) = (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z)

= ¬z ∧ ((¬x ∧ y) ∨ (x ∧ ¬y) ∨ (x ∧ y))
= ¬z ∧ ((y ∧ (x ∨ ¬x)) ∨ (x ∧ ¬y))
= ¬z ∧ (y ∨ (x ∧ ¬y))
= ¬z ∧ (y ∨ x) ∧ (y ∨ ¬y)
= ¬z ∧ (x ∨ y)

In this example, we started with a function DNF. We then used the dis-
tributive law in the second and third lines. We obtain line 4 through the inverse
law, line 5 through distributive law and finally line 6 through the inverse and
commutative laws.
While using only the three operators (AND, OR and NOT) is useful partic-
ularly for their semantic interpretation, it is sometimes advantageous to write
Boolean equations using as few operator types as possible. As we will soon see,
to each logical operator corresponds a digital circuit. Since a digital circuit is
a piece of hardware, when putting together circuits for very complex functions,
it can be useful to minimize the types of hardware you need to source - one
would often rather source many items of the same type then different amounts
of different items.
Interestingly, any Boolean function can be written as an expression that
contains only NAND or only NOR operators. This is because as we have
seen, any function can be written by using only AND, OR and NOT opera-
tors. But ¬x = x NAND x. Also, x ∧ y = ¬(x NAND y). It follows that
x ∧ y = (x NAND y) NAND(x NAND y). We therefore wrote both negation
and logical conjunction as forms using only the NAND operator. Furthermore,
by De Morgan’s law, the logical disjunction can be written using only negation
and conjunction, therefore it can also be written using only the NAND operator.
A similar proof can be made with respect to the NOR operator.

6
Chapter 4

Basic Digital Gates

Every digital device - be it a personal computer, smartphone or network router

- is based on a set of chips designed to store and process binary information.
Although these chips come in a variety of shapes and forms they are all made
of the same building blocks: elementary logic gates. While the gates can be
physically realized using multiple hardware technologies, their logical behavior
is consistent across all implementations.
In a digital circuit, only voltages typically in the range from 0 volts to 1.5
volts are permitted. The voltages between 0 and 0.5 volts are considered by
convention a logical (or Boolean) zero (0). Signals between 1 and 1.5 volts are
considered a logical (or Boolean) one (1).
Tiny electronic devices, called gates can compute various functions of these
signals. Today, gates are typically implemented as circuits containing transis-
tors, and packaged into chips. All modern digital logic ultimately rests on the
fact that a transistor can be made to operate as a very fast binary switch.

4.1 Very Basics of Electrical Circuits

Conductive materials such as copper, exhibit the ability to easily conduct elec-
tric current. Insulating or non-conductive materials such as glass, rubber, wood
inhibit the flow of electricity through them and are used as insulators to protect
electric conductors from short circuit. Materials that permit some electrical cur-
rent to flow while predictably restricting the amount allowed to flow are used in
the construction of resistors. Semi-conductor materials such as silicone are ma-
terials that can be either conductive or resistive depending on some conditions
for example, temperature.
The relationship between electrical current, voltage and resistance in a cir-
cuit is analogous to the relationship between flow rate, pressure and flow re-
striction in a hydraulic system: the source ”pushes” electric charge. The charge
flows through the conductive material (the wire) at a rate that depends on how
conductive (or resistive) this material is. Ground is a reference point in the cir-
cuit considered by convention to be 0V, with respect to which all other voltages
are measured.

7
 Figure 4.1: The schematic symbol of a transistor

The transistor A transistor is an electronic device that uses semi-conductor

material in order to switch between having a very high and very low resistance.
Figure 4.1 shows the symbol of a transistor. A transistor has three connections:
the collector (labeled ”c” in the figure), the base (labeled ”b” in the figure) and
the emitter (labeled ”e” in the figure). When the voltage at the base is above a
certain value, the transistor turns ”ON” and behaves like a conducting wire. In
this case, current flows from the collector wire to the emitter wire. When the
voltage at the base is below a certain critical value, the transistor turns ”OFF”
and behaves like an infinite resistance. In this case, the transistor blocks the
flow of current from collector to emitter. Therefore the base wire acts as the
control of the transistor. Transistors were invented at Bell Labs in 1948, and
for this its inventors John Bardeen, Walter Brattain, William Shockley were
awarded the Nobel prize in physics.

4.2 Elementary Logic Gates

A logic gate is a physical device that implements a simple Boolean function.
The operands as well as the result are electric voltage levels. Using a transistor,
one of the most straightforward logic gates to implement is one that corresponds
to the Boolean Not operator. Its circuit is shown in Figure 4.2.
The device has 4 connections, which on a chip correspond to ”pins”:
• +VCC that is its connection to power supply. Generally, the voltage VCC is
externally regulated at about 1.5 volts. Since a logical gate is an electronic
device it always requires connection to power supply to operate.
• Vin which is the input signal.
• Vout which is the output signal.
• ”ground” which is the reference 0V signal. Just like power supply, all
electronic devices need a connection to ground.
Its operation is as follows: when the input signal Vin is high (voltage 1V-
1.5V), the transistor turns ON hence the current flows from the source (+VCC )
through the resistor to ground. Vout is then directly connected to ground and its
voltage is 0V. When the input signal Vin is low (voltage 0V-0.5V), the transistor
if OFF, virtually disconnecting the source from the ground. Without a ground,
the current does not flow through the wire, hence there is no drop in voltage
over the resistor and Vout is then similar to +VCC . So the circuit’s function
with respect to Vin and Vout can be summarized as: when Vin is low, Vout is

8
 Figure 4.2: The circuit of a logical NOT gate

high, and when Vin is high, Vout is low. Now replace ”high” and ”low” with ”1”
and ”0” or with ”True” and ”False” respectively, and you have just seen how
voltage levels can be used for implementing the logical negation.
The same type of logic can then be used to implement the other logical
operators that we have studied. Figure 4.3 shows the circuits implementing the
NAND and NOR gates. By connecting the Vout signal of a NAND gate to the
Vin signal of a NOT gate, we obtain the AND gate. Similarly by connecting the
Vout signal of a NOR gate to the Vin signal of a NOT gate, we obtain the OR
gate.
As we have seen in Chapter 3, any Boolean function can be expressed by
using only NAND or only NOR operators, meaning that we can create any digi-
tal circuit using only NAND gates or only NOR gates. Also Boolean expression
equivalence translates to digital circuit equivalence: there are many ways to wire
a circuit in order to obtain a targeted operation. To a gate designer, it is impor-
tant to minimize or at least reduce the number of gates in their products. Fewer
gates often means smaller costs, a smaller chip area needed for implementation,
lower power consumption and higher speeds. To find alternative circuits that
compute the same functions, Boolean algebra is used. Since the circuit imple-
mentation of these gates is not of relevance to designers who use these gates for
more complex circuits (but their function is) these basic logical gates have their
own symbols. Figure 4.4 shows the symbols of the most common elementary
logic gates. In these symbols, since it is taken for granted that any gate needs
connection to the source and ground to operate, these two signals are omitted
to avoid cluttering the diagrams.
The NOT gate is also often called an inverter. The small circles used as part
of the symbols for the inverter, NAND gate and NOR gate are called inversion
bubbles and we will encounter them in various contexts, used to indicate an
inverted (negated) signal.
In general, any gate can be built from the most basic elements, such as
transistors, or can be built by combining other gates. The former are called
primitive gates while the latter are called composite gates. Figure 4.5 shows the
AND gate as a primitive and also as a composite. However, notice that the
input and output - the interface - of the resulting gate is the same.
From here on, we will abstract out the implementation of the basic gates’
circuitry, as we move on to designing more complex gates that make use of
them. Note that when we draw circuit diagrams, the diagrams are such that

9
 (a) NAND gate circuit (b) NOR gate circuit

x y x NAND y x y x NOR y
0 0 1 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 0
(c) NAND truth table (d) NOR truth table

Figure 4.3: Transistor based circuits of NAND and NOR logic gates, as well
as their functions’ truth tables. By x and y we denote the Boolean operands
corresponding to voltages V1 and V2 respectively.

10
(a) The NOT gate (b) The AND gate (c) The NAND gate

A B X A B X
A X 0 0 0 0 0 1
0 1 0 1 0 0 1 1
1 0 1 0 0 1 0 1
(d) The 1 1 1 1 1 0
NOT truth (e) The AND (f) The NAND
table truth table truth table

(g) The OR gate (h) The NOR gate (i) The XOR gate

A B X A B X A B X
0 0 0 0 0 1 0 0 0
0 1 1 0 1 0 0 1 1
1 0 1 1 0 0 1 0 1
1 1 1 1 1 0 1 1 0
(j) The OR truth (k) The NOR (l) The XOR
table truth table truth table

Figure 4.4: Symbols of the elementary logic gates and their respective truth
tables

(b) The AND gate as a composite gate con-

structed using only NAND gates

(c) The AND gate as a composite

(a) The AND gate as a gate constructed of a NOT gate and a
primitive gate NAND gate

Figure 4.5: Three ways of implementing the AND gate

11
they illustrate the operation of the circuit, and they are by no means the only
way possible, or the best way by any criteria - except hopefully by pedagogical
criteria.

4.3 Combinational Circuits

Circuits whose outputs depend only on their inputs are called combinational
circuits. Not all circuits are combinational for instance, memory circuits take
as input an address and output the value stored at that address. Hence, the
output depends on what is stored at the address as much as on the address.
We will study memory circuits later. In the following, we take a look at some
frequently used combinational circuits.

m-way versions of the basic gates When a basic logic function (except for
NOT) takes m > 2 operands, it is called an m-way gate:

• An m-way AND gate returns 1 only when all m inputs are equal to 1

• An m-way OR gate returns a 1 when at least one of its inputs are equal
to 1

• An m-way XOR gate returns 1 if the number of 1’s in the input is odd
and 0 if it is even. It is built as follows: the first 2 bits are passed through
a XOR gate, and the result is passed through another XOR together with
the third bit, the result is XOR’ed with fourth bit and so on

• m-way NAND and NOR gates return the inverse of m-way AND and OR
respectively.

The symbols of m-way gates is the same as that of the simple gates just with
multiple inputs.

n-bit versions of the basic gates It is frequently required to apply a logic

function to one or more multi-bit words. Such an instance is a 4-bit NOT gate.
It takes 4-bits as input and outputs also 4-bits, each one being the inverse of
its corresponding input bit. An 8-bit AND gate takes 2 sets of 8 bits each and
applies the AND function between the corresponding pairs of bits. It therefore
outputs one 8-bit word.

Multiplexers Multiplexers are also called selectors. They are used to select
and output one input signal out of 2n input signals. Besides the 2n input signals
a multiplexer also has n control signals. The control signals are used to specify
the input signal that needs to be output. Since n control signals can specify one
out of 2n combinations, the number of inputs in a multiplexer with n control
signals is 2n . Table 4.1 shows the truth table of a multiplexer with two inputs
(I1 and I0 ) and one control C. The output X takes the value of I0 when the
control C is equal to 0 and takes the value of I1 when C = 1.
Figure 4.6 shows the a schematic diagram of the circuit of a 4-bit multiplexer,
as well as a 4-bit multiplexer symbol used in higher level diagrams. This circuit
uses four 3-way AND gates and one 4-way OR gate. The filled circle symbol

12
 I1 I0 C X
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Table 4.1: Truth table of a 2-bit multiplexer

at the intersection of lines signifies that the wire is split, hence all ”lines” that
are connected to the same dot (filled circle) correspond to the same signal.
When lines intersect without a dot, the wires (signals) are distinct and they
just happen to cross eachother in the diagram. The two control lines C1 and
C0 encode a 2-bit number that specifies which of the four input lines is sent to
the OR gate and then output. Notice that whichever the C1 C0 combination,
there are always at least 3 AND gates that output a zero. If the input that
corresponds to the control combination is 1, the corresponding AND gate will
output a 1 triggering the OR gate to also output a 1. In any other cases, the
output is 0.
One of the applications of a multiplexer, besides that of a selector, is as a
parallel-to-serial data converter. In our example, in Figure 4.6, by putting 4
bits of data on the input lines, and by having the control lines step sequentially
from 00 to 11, the 4 bits of data will be sent in order from I0 to I3 , one by one.

Demultiplexers Demultiplexers are the inverse of multiplexers. They have

one input, n control signals and 2n output signals. Their function is to route
the value of the input to the output selected by the control signal. Figure 4.7
illustrates the circuit of a demultiplexer together with its symbol.

Decoders As opposed to the previous two types of combinational circuits,

the decoders do not have control signals in addition to the input signals. They
generally have n input signals and 2n output signals. Their function is to set to
1 exactly one output signal: the one that corresponds to the code (or number)
represented by the n input signal. For example, on a 3-to-8 decoder, if the
three input signals are 011(=4), then out of the 8 output signals, the fourth
one (number 3 counting from 0) will be set to 1 and all others to 0. Figure 4.8
shows the circuit of a 2-to-4 decoder.

4.3.1 Arithmetic Circuits

A particular type of combinational circuits are the arithmetic circuits. As their
name implies they are used for arithmetic operations. Addition is the most
basic arithmetic operation. Subtraction - when using two’s complement repre-
sentation - is a type of addition, where the second term is a negative number.
Multiplication and division can also be implemented based on a series of ad-
ditions and/or subtractions. Which arithmetic operations are implemented in

13
 (a) The circuit schematic diagram

(b) The multiplexer symbol

Figure 4.6: A 4-to-1 multiplexer

hardware is a design decision. Commonly, addition is implemented in hardware.

Therefore multiplication and division can also be implemented in hardware, but
if the hardware already implements addition, that is not necessary: software
algorithms that use the addition hardware can be devised to implement them.

Adders We have already touched on binary addition in Lecture 1. There

we defined the bit-wise addition rules. Written as a truth table, the addition
between two bits is shown in Table 4.2. Interestingly, the Sum function is equiv-
alent to applying the XOR operator between the two bits. The Carry function is
equivalent to the AND operator between the two bits. It is then straightforward
to draw the circuit diagram for 1-bit addition, as seen in Figure 4.9
Now that this circuit is able to add a pair of bits, it should be useful for

x y Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Table 4.2: Bit wise binary addition truth table

14
 (a) The circuit schematic diagram

(b) The demultiplexer symbol

Figure 4.7: A 1-to-4 demultiplexer

Figure 4.8: 2-to-4 decoder circuit

15
 Figure 4.9: The circuit of a 1-bit adder (half adder)

Figure 4.10: The circuit of a 1-bit full-adder)

adding n-bit words. Recapping the process of n-bit addition, we start from the
LSBs, adding them and if they generate a carry, this carry is added to the next
pair of bits to the left. In that case, the addition of the pair of bits that receives
a carry from the previous pair of bits needs to also add this carry bit, meaning
it needs to have three input bits. Therefore, in the context of multi-bit words,
the 1-bit adder in Figure 4.9 is not adequate for adding bits that are not the
LSB. To account for this limitation, it is known as a half adder.
The one-bit adder that is able to also add the carry bit coming from the pair
at the right is called a full adder. Its circuit is shown in Figure 4.10. Basically,
in this adder, X and Y are added with a half-adder, then their sum is added to
the carry-in also with a half adder. The sum output by the second half-adder
is the final sum. The full-adder outputs a 1 as a carry-out if one of the two
half-adders generate a carry. Note that it is not possible for both AND gates to
output a 1. For the first one to output a 1 it means X and Y are both 1, but
then their sum is 0, so the second AND gate’s output will be 0. Hence, the last
OR gate could have just as well been another XOR.
To build an adder for n-bit words, n full adders need to be connected such
that the carry-out of a full adder is connected to the carry-in of the next adder
to the left. Such an n-bit word adder is shown in Figure 4.11. An adder
implemented this way is known as a ripple carry adder because the carry
signal ”ripples” through all the full adder components before the result can be
output. Given that each full-adder computation requires some time (as little
as it is), and that a full adder’s result is only ready after the results of all the
previous full adders are ready, this implementation is sometimes deemed too
slow.
An alternative implementation of a n-bit word adder that is faster than the
ripple-carry adder is in Figure 4.12. This type of adder is called a carry-select
adder. Its operation is as follows. It splits the two words in two halves each:

16
 Figure 4.11: n-bit word ripple carry adder

the lower half and upper half. As the addition of the two lower halves have
no carry-in, their carry-in is connected to the ground. As for the addition of
the upper halves, this adder proceeds with two additions: an addition with the
carry-in connected to the ground (0), and an addition with a carry-in connected
to the source (1). The results of these two additions are then passed through
a multiplexer which uses as selection control the carry-out of the adder of the
lower halves. In other words, three sums are computed in parallel: one for the
least significant halves, and two for the most significant halves - one with the
carry in equal to 1 and one with 0. The decision which of the most significant
halves’ sums to output is taken once the addition of the least significant halves is
finished. Therefore, the addition itself of the most significant bits does not need
to wait for the addition of the least significant bits. This is an example of an
eager computation in which the computation of the most significant half of the
sum is computed before all its parameters are known, for all possible parameter
values. Once the parameter (in this case the carry out of the least significant
half) has been computed, it is only used for selecting the correct result.
These splits and computations on half-words can proceed similarly for longer
word sizes: for example for a 32-bit word adder, a carry select adder can be used,
splitting it into the two 16-bit halves, but the addition of each of the 16-bit halves
can also be implemented with a carry-select adder that splits them in two 8-bit
halves, then each in two 4-bits halves and so on. Every such split reduces the
required computation time by a factor of two.

Shifters Shifting a binary number one position to the right is equivalent to

dividing it by 2. Shifting a binary number one position to the left is equivalent
to multiplying it by 2. Therefore the shifting operation on n-bit sized words is
useful for multiplication with powers of two, and as we have seen, in operations
on floating-point numbers. When shifting to the right, the LSB is lost and a 0 is
inserted into the MSB position. Hence the result is the quotient of the division
by 2. When shifting to the left, the MSB is lost and a 0 is inserted into the LSB
position. Hence the result is the multiplication by 2, modulo 2n .
n-bit shifters take as input an n-bit word and output also an n-bit word.
They usually have a control signal that determines if the shift operation is to
the left or to the right. A 4-bit shifter diagram is shown in Figure 4.13. The
control signal, called R from right, determines a shift to the right when set to 1
and a shift to the left when set to 0.

17
Figure 4.12: 4-bit carry select adder

Figure 4.13: A 4-bit shifter

18
 Figure 4.14: A clock signal

4.4 Clocks
In computer systems, synchronization between various stages of the compu-
tation is extremely important. To illustrate, consider the ripple carry adder
again. If two 32-bit words are input to be added up, until all the 32 full adders
have finished their part one by one, the binary code that is output is gibberish.
The output signal only becomes meaningful at the end of the computation, so
any downstream device that needs to use the result of the sum needs to know
when to read the output signal. But we can imagine the situation even more
complicated, for example if the input signals change before the sum finished
computing. Then without hardwired synchronization, the circuit might never
output anything useful. Remember that the wires are electric wires with contin-
uous voltage values within a designated range. The changes of voltage as signal
travels through the circuit take time, they are not instant although they might
appear so to the human eye.
To allow designers to achieve the required synchronization between compu-
tations, special circuits, called clocks are used. The clock signal can be seen as
the heartbeat of the system. Rather than working with the continuous notion of
time, clock circuits implement time as a discrete concept. A unit of time in this
context is a cycle. A clock is then a digital circuit that generates clock cycles of
a precise length. Each clock cycle has two phases: a 0 (low) phase also called a
tick, and a 1 (high) phase also called a tock, with the tock always following the
tick, and each phase being on for a precise amount of time. A cycle provides 2
time references that are commonly used:

• the rising edge occurring at the switch between tick and tock
• the falling edge occurring at the switch between the tock of a cycle and
the tick of the next cycle

Figure 4.14 illustrates a clock signal over time.

Typically, a clock cycle lasts about 10 nsec (nanoseconds) to 250 psec (pi-
coseconds). The very high frequency and accuracy are achieved with a crystal
(usually quartz) oscillator.

4.4.1 Delay circuits

Sometimes, multiple events occurring during the same clock cycle need to be
synchronized. In this case, other clocks can be defined starting from the main
clock, to capture the recurrence of different moments inside the main clock
cycles. One way of defining new clock signals is by plugging the main clock

19
 Figure 4.15: A clock signal that is delayed through a delay circuit

signal into a circuit whose main purpose is to delay it - a delay circuit. After
this, a new clock is achieved, with a slight delay with respect to the original clock.
More over, using the original clock signal and the (new) delayed clock signal,
other new clock signals (both symmetric and asymmetric) can be generated as
functions of these two clocks.
Let us look at an example: a straightforward delay circuit is built with two
inverters such that the output of the first is fed into the input of the second.
Then the output signal of this circuit is the same as the input signal, just a tiny
bit delayed - the time it takes for the signal to pass through the two NOT gates.
Figure 4.15 shows such an example circuit together with a signal representation
for the two clocks. Generally, any circuit that implements the identity function
f (x) = x can be used as a delay. What gates are used to implement it depends
on the time specifications of the gates and the delay requirement.

4.4.2 Asymmetrical clocks

Starting from two or more clock signals that are not perfectly in synch, multiple
other clocks can be created. For instance, by passing the C1 and C2 clocks
from Figure 4.15 into an AND gate, we obtain an asymmetric clock C3 that
has a longer tick and shorter tock. Figure 4.16 shows the circuit and the signal
in time. The figure also shows that C3 is slightly delayed, and this is due to
the time it takes the signal to go through the AND gate. Also note that the
illustrations show the switch from 0 to 1 and 1 to 0 as instant in time. This is
just for convenience, but in reality, the switch between 0 and 1 and vice versa
also takes some time so the switch would be represented more accurately as
increasing and decreasing curves rather than vertical lines.

4.4.3 Pulse generators

A very specific type of asymmetric clocks are pulses. Frequently, the value
of a signal needs to be read at a specific point in time. Using again an adder
as an example, imagine the situation where the adder has its input set at the
very start of each clock cycle, and it takes a bit less than one tick for the adder
device to compute the sum between the inputs, so we can be sure that at the
end of the tick and beginning of the tock the output signals are stable and
correct. This brief moment at the end of the tick and beginning of the tock
corresponds to what we call the rising edge of the cycle. In our example this

20
 Figure 4.16: Example of generation of asymmetrical clocks

Figure 4.17: A circuit generating a pulse on the rising edge of the master clock

means that the output of the adder can be read on the rising edge of the cycle.
Now also consider another device that needs to read the output of the adder
and store it. It would be highly undesirable for this device to store all the
gibberish values that are output by the adder until the correct result comes. So
this device must be ready to read the output of the adder precisely on the rising
edge of the clock. Reading that output signal any sooner or later, will result in
intermediate gibberish. To perfectly time the rising edge (or falling edge) of a
clock, a pulse signal is typically used.

Figure 4.17 shows a clock that generates a pulse on the rising edge of clock
C1. Interestingly, this circuit takes advantage exactly of the delay in the inverter
to exploit the short time in which both C1 and C2 are 1 - before the switch from
0 to 1 in C1 has propagated through the inverter to generate the switch from 1
to 0 in C2. For this short instant, as long as the duration of the delay through
the inverter, the AND gate receives two 1 signals, hence it outputs a 1. It is
also slightly delayed by the propagation through the AND gate. This ”blink” in
the signal P occurs right after the rising edge of C1, and due to its very short
duration is called a pulse. Now, how does a device know to read meaningful
input only on the pulse of the clock? By first passing the input signal and the
pulse signal through an AND gate. We will use this mechanism shortly, as we
study memory circuits.

21
 (a) SR-latch with two NOR gates (b) SR-latch with an inverter, an OR and an
AND gate

Figure 4.18: SR-latch circuits

4.5 Memory Circuits

Memory circuits, as opposed to the combinational circuits, ”remember” previous
input values and use them to generate the output. They are also called sequential
circuits as their output is decided by a sequence of input values - such that the
output depends both on the current and past inputs. Sequential circuits are built
using combinational circuits. Concretely, basic logic gates (combinational) can
be used to create data storage elements (sequential) by sending a gate’s output
to another gate’s input that precedes the first gate in the signal chain. Such
a setting creates a feedback loop. We study some sequential circuits in the
following.

4.5.1 Latches
SR Latches The most basic circuits that ”remember” one bit are the SR-
latches. Figure 4.18 shows two possible ways of constructing a SR-latch. There
is also another option similar to the one using two NOR gates, but using two
NAND gates. An SR-latch has two inputs: S for setting the latch, and R for
resetting (or clearing) it. Typically, it also has two outputs such as the one in
Figure 4.18a: Q and Q̄ which are complementary. Remember the Q̄ notation
indicates the negation of Q.
In the following, we focus on the SR-latch implementation in Figure 4.18a,
but the implementation in Figure 4.18b can be similarly analyzed. Let us start
with the assumption that S and R are both 0 and let us make no assumption
over the values of Q and Q̄. To understand the behavior of this sequential
circuit, let us work through a sequence of inputs as follows1 :

1. S=0; R=0; Consider first that both S and R are 0. Given the nature of
the NOR gates, both Q=1 & Q̄ =0, and Q=0 & Q̄ = 1 states are possible,
but let us make no assumption. Output: Q=0/1 and Q̄=1/0. Now let
us set S to 1.

2. S=1; R=0 Regardless of the other input in the upper NOR gate, if S is
1, its output is certainly 0. Hence Q̄ = 0 Now this 0 output is fed into
the input of the lower NOR gate, which together with R = 0 produce the
1 Make sure to study this example on the circuit diagram, pen on paper

22
 output 1, hence Q = 1. This output is fed into the input of the upper
NOR gate, whose output then stays 0. Output: Q=1 and Q̄=0. Now
let us set S back to 0:

3. S=0; R=0 As Q=1, the upper NOR gate outputs 0, therefore Q̄ stays 0.
This output is fed into the lower NOR gate, such that its output stays 1,
therefore Q=1. The output of the lower NOR gate is fed into the input of
the upper NOR gate, maintaining its output as 0. Output: Q=1 and
Q̄=0. Now let us set R to 1.

4. S=0; R=1 When R becomes 1, the output of the lower NOR gate becomes
0, hence Q = 0. This 0 signal is fed into the input of the upper NOR gate.
Since S is also 0, the output of the NOR gate becomes 1. So Q̄=1. This
output is sent to the lower NOR, but does not change its output. Output:
Q=0 and Q̄=1 Now let us switch R back to 0.

5. S=0; R=0 As Q̄=1 and R=0, the lower NOR gate outputs 0 so Q stays
0. This output is sent to the input of the upper NOR gate and since S is
also 0 the output becomes 1: Q̄=1. Output: Q=0 and Q̄=1. Let us
now switch R back to 1.
6. S=0; R=1 Note that this is different than step 4 because back then Q was
1. Now Q is 0. This switch determines the output Q of the lower NOR
gate to stay 0 because its other input Q̄ is 1. This output is fed into the
upper NOR gate whose output remains 1, so Q̄ stays 1. Output: Q=0
and Q̄=1 Let us now also switch S to 1. Notice that if we would choose
to rather switch R back to 0 we would be in the same process as step 5.

7. S=1; R=1 So now that S is also 1, the output of the upper NOR gate
becomes 0 so Q̄ is 0. This output is sent to the lower NOR gate , but
since R=1, its output stays 0, therefore Q is also 0. This output is now
sent to the upper NOR gate but since S =1, its output stays 0. So in this
state, when both S and R are 1, both Q and Q̄ are 0. Output: Q=0
and Q̄=0 This is a problem because the logic of the outputs is not reliable
anymore: Q and Q̄ should not be 0 at the same time. Leaving this logics
inconvenience aside, from this state, if S is set to 0 the latch reaches the
same state as in step 4. Otherwise if R is set to 0, the latch reaches the
same state as in step 2. However, a new problem occurs when both S and
R are switched to 0 at the very same time. It is then non-deterministic
whether the latch settles in the Q=0 and Q̄=1 state, or in the Q=1 and
Q̄=0 state. This is called a race condition - the output depends on which
signal manages to travel through the wire and settle first. It is therefore
considered generally ”illegal” to bring the SR-latch in the S=R=1 state
and chip designers must make sure this cannot happen.
Analyzing step 1, we note that regardless of the previous value of Q, when S
becomes 1 then Q becomes 1. Analyzing steps 4 and 6, we note that regardless
of the previous value of Q, when R becomes 1 then Q becomes 0. So far, it
looks as if the inputs only determine the outputs. However, in steps 3 and
5 both inputs are 0, but the outputs are different: in step 3 the output Q is
1, while in step 5 the output Q is 0. These are the values that correspond
to the Q values from their corresponding previous steps. This illustrates the

23
 Figure 4.19: SR latch with enable

”memorizing” capability of this circuit. We conclude that when S=0 & R=0
the latch is in one of two possible stable states: the 0 hold state when Q=0 or
the 1 hold state when Q=1. Which one it is, depends on the S and R inputs in
the previous step: if S was 1, then we are in 1-hold state. If R was 1, then we
are in 0-hold state.
In use, a latch spends most time in one of the stable states. To set it to the
1-hold state, the S signal is quickly set to 1 and back to 0 - a pulse signal usually
achieves this - similarly as pushing and releasing a button. To reset the latch
(put it into the 0-hold state), a pulse signal is applied to the R input (reset).

SR Latch with Enable Since latches ”remember” the previous input, the
action of setting or resetting a latch is equivalent to writing a 1 or writing a 0
in its 1-bit memory. Frequently, it is useful to be able to control when to write
the value provided at input. To achieve this, an additional enable input is used,
that conditions the values of S and R to reach the output only when this bit is
1. This is straightforwardly implemented with additional AND gates as shown
in Figure 4.19. When the enable signal is 0, both AND gates output 0 therefore
the latch is in the stable state, holding 1 or 0 depending on which one it was
set to when enable was 1.
An SR-latch that provides this control bit is called an SR-latch with en-
able, or gated SR-latch. If this enable input is expected to be a clock signal
(for example a pulse signal), then the latch is called a clocked SR-latch. How-
ever, the nature of this signal - being a clock, or a signal decided through a
different logic - does not change the circuit of the latch. It is mostly a matter
of how the latch is being used. Considering this control as an enabler signal is
the more general way of thinking about latches.

D-Latches As we have seen, the SR latches have the drawback of the illegal
S = 1 & Q = 1 state. D-latches solve this issue by having only one input
called D from data and by sending its inverse to the second NOR gate. This
change makes the enable signal indispensable: Without the enable signal, the D-
latch would be either in set state (when D=1, then Q=1) or reset state (when
D=0, then Q=0) states, and never in the stable state as that would require
D = D̄=0. So it would interestingly be a rather complicated implementation for
the identity function. The enable control with its AND gates provide the device
with a stable state: when Enable is 0. Just like in the SR latch with enable,
as long as the enable signal is 1 the value of D is propagated to the NOR gates

24
 Figure 4.20: D-latch with enable

and into Q. When the enable is 0, changes in D’s value do not reach the NOR
gates and hence do not change the output. The last value of D during a high
enable is stored until the enable signal becomes 1 again. Figure 4.20 shows a
D-latch circuit (with enable).
To conclude, all the latches that use an enable signal react to the data that
they receive on their inputs as long as the enable signal is high, and they store
the last received input for as long as the enable signal is low. Due to this
property they are called level-sensitive (also level-triggered).

4.5.2 Flip flops

In more complex digital circuits (such as computers), it is important to syn-
chronize multiple circuit elements. Reading and writing multi-bit words needs
to be done with the certainty that all the individual bits are written and/or
read simultaneously despite propagation delays across individual devices. This
synchronization is handled by using a shared clock signal as a control signal
for multiple devices. In such setups, components update their outputs based on
clock signal edges (moments of clock transition from low to high or high to low)
rather than responding continuously for as long as the clock signal level is high.
Such devices are called edge-sensitive (also edge-triggered).
Edge triggering is useful because the clock signal edges identify precise mo-
ments at which device inputs must be stable and valid. After the clock edge has
passed, the device’s inputs are free to vary in preparation for the next active
clock edge without the possibility of altering the circuit outputs. A flip-flop
is such a device, providing the desirable characteristics for complex digital cir-
cuits. A straightforward way to construct a flip-flop is to modify a D-latch such
that its enable signal receives a pulse signal (see Section 4.4.3). The clock is an
externally controlled signal, but the mechanism of only reacting on its edge is
built within the flip flop. Figure 4.21 shows the circuit of a D flip-flop (DFF)
that reacts on the rising edge of the clock.
Besides the D input and clock (CK), D flip-flops are frequently provided
with more control signals. Some common ones are:
• CLR or R: which stand for clear or reset respectively. This signal forces
the flip-flop to state Q = 0;
• S: which stands for set. This signal forces the flip-flop to state Q = 1;
• E: which stands for enable. This signal when 1 makes the device behave
like a D-latch. So it outputs what is input on D for as long as E is high;

25
 Figure 4.21: D flip-flop circuit

Figure 4.22: A 4-bit register

It is useful when additional logic is required to decide when to write. It

can be AND’ed or OR’ed with CK.

Also, some D flip flops only output Q others output both Q and Q̄. The latter
option is for the convenience of not needing another inverter if Q̄ is required
downstream.

4.5.3 Registers
As we previously hinted to, flip-flops can be combined to create registers which
can hold binary codes longer than 1 bit. A key characteristic of a register is
that all flip-flops that make it receive the same control signals (CK, CLR, S or
E). They only receive different input data. Registers’ Enable signal is frequently
called Load. Figure 4.22 shows the schematic diagram of a register built out of
D flip flops as the ones we introduced in Figure 4.21.

4.6 Moore’s law

All circuits that we have introduced in this chapter can be built with a handful
of transistors. For example, a D-latch requires as few as 6 transistors - although
the design we have shown requires 11. Since the invention of the transistor, the
computer technology field has gone through a rush of reducing the transistor
size in order to fit more and more on smaller boards. In 1965 Gordon Moore -
co-founder and former chairman of Intel - noticed that each new generation of

26
memory chips was being introduced 3 years after the previous one and had four
times as much memory. Based on this observation he predicted the doubling
of the number of transistors on a memory chip every 18 months, for the next
10 years. This prediction came to be known as Moore’s law. It proved true
for several decades afterwards up until about 2010 when the growth started to
decline. Currently, the industry standard uses chips with 7nm transistors, fitting
70-90 mil transistors per square millimeter. Apple M4 uses 3nm transistors.
These dimensions are approaching physical limits that will eventually put the
brakes on the growth under Moore’s law: the smallest molecule in nature - the
diatomic hydrogen molecule (H2 ) is 0.074nm.

27