1.1 What digital design is

Why this matters

A processor is a very large number of small circuits wired together, and digital design is the craft of building circuits like them. This section shows what a wire carries, what a logic gate does with it, and how a drawing of gates becomes a working device. It also introduces the idea that surprises programmers most: a hardware description looks like code, but it describes something that exists.

Learning goals

Explain how a wire carries one bit and what a logic gate does with the bits it receives.
Describe the idealized gate, whose output depends only on its inputs at this moment.
Put the steps of the design flow in order, from a drawing to a working device.
Read a small SystemVerilog module as a description of gates and wires, not as a list of instructions.
Name the differences between a hardware description and a program.

Intuition first

Wire two switches in series with a lamp. The lamp is lit exactly when the first switch and the second switch are both closed. Nobody runs anything: the lamp does not remember earlier positions of the switches, and it reacts the moment either one moves, because the wires connect them. Now wire the switches in parallel instead, and the lamp is lit when either switch is closed. Two arrangements, two different behaviors, and the behavior is fixed by how the parts are connected.

A digital circuit is the same idea with electronic parts in place of switches. Each part looks at some wires, and drives another wire according to a fixed rule. The rules are simple, and the work of design is choosing which parts to connect and how.

If you write software, the nearest idea you know is a spreadsheet. A cell that holds a formula such as "the sum of these two cells" is not run once. It is a relationship that stays true, and the cell follows its inputs. The analogy breaks in two places. A spreadsheet recalculates cells one after another in some order, while in a circuit every part is a separate physical device and all of them work at the same time. And a spreadsheet holds numbers of any size, while a circuit has a fixed number of wires, each carrying one bit.

Bits, signals and gates

Definition 1.1.1(bit and signal).

A bit is a quantity that is either 0 or 1. A signal is the value carried by one wire in a circuit, or by a group of wires taken together (a bus, Section 2.6): a one-wire signal is 1 while the wire is at a high voltage, and 0 while it is at a low voltage.

Any voltage inside a wide high range counts as a 1 and any voltage inside a wide low range counts as a 0. That is why a little electrical noise does not change a value, and it is the reason digital circuits are dependable enough to build computers from. One wire carries one bit. A group of wires that carry several bits together is called a bus, and later sections use buses to carry numbers.

Definition 1.1.2(logic gate).

A logic gate is a small circuit with one or more input wires and one output wire. Its output is a fixed function of the values on its inputs at that moment: the same inputs always give the same output, whatever happened before.

In this book a gate is idealized: its output changes at the instant its inputs change. A real gate needs a short time to respond, and Chapter 3 shows when that matters. Until then, the idealized gate is the whole story, and it is what makes the next section possible, because a circuit whose outputs depend only on its current inputs can be described completely by a table of its outputs for every setting of its inputs. The logic of the computer that guided the Apollo spacecraft was built from thousands of copies of a single kind of chip, each holding NOR gates.^{F (fact ch01/apollo-nor)} Gates are small, but a great many of them go a long way.

The layers of a computer

Hardware is the bottom of a stack of layers, each built on the one below. A programmer works near the top and rarely sees the rest.

Layer	What it is made of	An example
Application	programs	a web browser
Operating system	programs that manage the machine	a file system
Instruction set	the operations a processor can carry out	adding two numbers
Blocks	adders, multiplexers, registers	a circuit that adds two 8-bit numbers
Gates	AND, OR, NOT and their relatives	one gate in an adder
Transistors	electronic switches in silicon	the parts a gate is made of

This book works at the gate and block layers. Two questions organize it. The first is how a machine holds information at all, and the answer is bits, each carried on a wire. The second is how to build parts that do something useful with those bits, and the answer is gates, wired into blocks, and blocks into larger blocks. It does not design at the transistor level.

The first circuit: a half adder

Example 1.1.1(adding two one-bit numbers).

Add two numbers that are each 0 or 1. The result can be 0, 1 or 2, which takes two bits to write: 00, 01 or 10. The right bit is the sum bit S, and the left bit is the carry bit C. The table lists S and C for every setting of A and B.

Truth table with 2 inputs (A, B) and outputs S, C; 4 rows in ascending binary order, A most significant
A	B	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Look at the S column. It is 1 when exactly one of the inputs is 1. The C column is 1 only when both inputs are 1. A circuit with one gate for each column does the job: an XOR gate gives S, and an AND gate gives C. Section 1.2 describes these gates in full. For now, read the picture as "A and B each go to both gates".

Figure 1.1.1. A half adder. One gate produces the sum bit and the other produces the carry bit.

The name "half adder" is the one you will meet in other books. It is half of a complete adder because it has no input for a carry arriving from a lower bit, and later chapters add that input.

From drawing to device

A design starts as a picture and ends as something physical. Several steps lie between.

Definition 1.1.3(hardware description language).

A hardware description language (HDL) is a text language for describing the parts of a circuit and how they connect. This book uses SystemVerilog, the modern form of Verilog.

Draw. Sketch the circuit as a block diagram, and then as gates.
Describe. Write the drawing as text in an HDL.
Simulate. A simulator is a program that computes what the described circuit would do. You feed it input values and look at the outputs. Mistakes found here cost almost nothing to fix.
Synthesize. A synthesis tool turns the description into a circuit that can actually be built. For an FPGA, that is a setting for the chip's logic elements and for the connections between them.
Build. Put the result on a device.

Step 3 repeats with step 2: you simulate, find a mistake, fix the text, and simulate again, until the behavior is right.

Illustration a block diagram that explains an idea; its behavior is not checked

Figure 1.1.2. The design flow, read along the top row and then along the bottom row. In practice you repeat the HDL and simulate steps until the behavior is right, and only then go on to synthesis. The sketch does not draw that loop.

Definition 1.1.4(FPGA and ASIC).

An ASIC (application-specific integrated circuit) is a chip made for one design: its gates are fixed in silicon, which costs a lot to produce and cannot be changed afterward. A field-programmable gate array (FPGA) is a chip holding a large number of small logic blocks. A configuration loaded onto the chip sets both what each block computes and how the blocks are wired together, so one chip can hold one design today and a different one tomorrow.

An FPGA is what you use for prototyping, because loading a new design takes the time to run a tool, not the time to manufacture a chip. The lab board of the course is the Terasic DE1-SoC, a development kit built around an Altera Cyclone V FPGA.^{F (fact ch01/de1-soc)} The course uses Intel Quartus Prime to write, synthesize and program designs, and ModelSim to simulate them.^{F (fact ch01/tools)} The examples in this book are checked with open-source tools instead, so any tool message shown here is theirs, and the tools you use may word it differently. The simulator is the tool to trust first: it can show every signal at every moment, while a board shows only the signals wired to something you can see.

In SystemVerilog

Here is the half adder as a module, the unit of design in SystemVerilog.

// A half adder: it adds two one-bit numbers. S is the sum bit and C is the carry bit.
module half_adder(input logic A, B, output logic S, C);
  assign S = A ^ B;  // the sum bit is 1 when exactly one input is 1
  assign C = A & B;  // the carry bit is 1 only when both inputs are 1
endmodule

A module is a box with named connections. The input logic A, B and output logic S, C give the box four connections, and logic is the type of a signal. Each assign line connects an output to a gate: the operator ^ is the XOR gate and & is the AND gate. The line assign S = A ^ B; is the XOR gate of Figure 1.1.1 with its output wired to S, and the next line is the AND gate wired to C. Section 1.4 explains the syntax.

Swap the two assign lines and you have described exactly the same circuit. Neither line runs before the other. Both gates exist at once, and both always compute from the current values of A and B. This is the sense in which a hardware description is not a program:

No one calls it. A function waits to be called, runs, and returns. The module is always there. S and C are wires that carry the right values whenever A and B have values.
No order. The lines of a program run in sequence. The lines of a module describe parts that work side by side.
No stored values. A program variable keeps a value until the program changes it. A signal holds nothing of its own: it carries whatever its gate produces from the inputs now. (SystemVerilog calls most logic signals variables, though an input port is a net; tool messages use both words, and Section 2.5 explains them.)

Everything you write in this book is either a circuit that behaves like this, or a way of testing one. Circuits that do remember earlier values do exist, and they appear in Chapter 4.

Course conventions

How CSE 369 writes this

In CSE 369 we write hardware in SystemVerilog and declare every signal as logic, the same word for a wire and for a variable. This book does the same. Inputs and outputs of a module are declared in its port list, and a signal that lives only inside a module is declared with logic in the module body.

Pitfalls

Common pitfall

Reading each assign as a step that runs once, after the line above it. Each one describes a gate that is always connected, so the order of the lines carries no meaning.
Treating a signal as a variable that holds an older value. A signal is whatever the gate driving it produces from the current inputs.
Loading a design onto a board to find out whether it works. Simulate first, because a simulator can show every signal.
Expecting the synthesized circuit to match your drawing gate for gate. The synthesis tool may choose different gates arranged differently. What must stay the same is the function.

Check your understanding

Take the quiz (5 questions)

Exercises

Exercise 1.1.1

A teammate describes the half adder module like this: "It runs whenever A or B changes, and then it returns S and C." Rewrite the sentence so that it describes what the hardware does.

Hint

Ask what, in the circuit, could correspond to "runs" and to "returns".

Solution

Nothing in the circuit runs, and nothing returns. A better sentence is: "The XOR gate and the AND gate are always connected to A and B, so S and C always carry the sum bit and the carry bit for the current values of A and B." In the idealized model they change the instant an input changes, which is the part of the teammate's sentence that is right.

Tags: Warm-upSystemVerilog

Exercise 1.1.2

These five steps are out of order: synthesize the description; write the description in an HDL; draw the circuit as gates; load the result onto a device; simulate the description. Put them in order, and say which two of them are repeated together.

Hint

Ask which step can find a mistake without building anything.

Solution

The order is: draw the circuit as gates, write the description in an HDL, simulate it, synthesize it, load the result onto a device. Writing and simulating are repeated together: each simulation can show a mistake, you fix the description, and you simulate again until the behavior is right.

Tags: Warm-upSystemVerilog

Exercise 1.1.3

Read this module. Write out its output Y for every setting of A, B and C, listing the rows by counting up in binary from 000 to 111 with A as the leftmost bit. Then sketch it as gates: an AND gate looks like the one in Figure 1.1.1, and the OR gate is drawn in Section 1.2.

// Exercise: what does Y do for each setting of A, B and C?
module and_then_or(input logic A, B, C, output logic Y);
  logic both;

  assign both = A & B;
  assign Y = both | C;
endmodule

Hint

First write what both is in words. Then ask when both | C is 1: it needs only one of its two inputs to be 1.

Solution

The signal both is 1 exactly when A and B are both 1. The output Y is both | C, so it is 1 when both is 1, when C is 1, or when both are. That makes Y equal to 1 in the rows where C is 1, and also in the row where A and B are both 1 and C is 0. The table lists all eight rows, with A as the leftmost, most significant input.

Truth table with 3 inputs (A, B, C) and output Y; 8 rows in ascending binary order, A most significant
A	B	C	Y
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

The circuit has two gates: an AND gate for both and an OR gate that takes both and C.

Figure 1.1.3. The module as gates: the AND gate is the signal both, and the OR gate gives Y.

Tags: StandardSystemVerilogTruth tablesGates and schematics