Bits, Numbers & Boolean Logic

Every circuit you will put inside an FPGA works with wires that carry a voltage. In principle a wire could carry any voltage between 0 V and the supply, 3.3 V on the PYNQ-Z2's I/O pins, and we could use that continuous value to represent a number. That is analog electronics. The problem is noise: every wire picks up a little interference, every transistor adds a little error, and in a chain of thousands of stages those errors add up until the number is meaningless.

Digital electronics gives up almost all of that resolution in exchange for robustness. A wire only ever means one of two things, 0 (low voltage) or 1 (high voltage). Each such two-valued quantity is a bit (binary digit). A logic gate reading a wire does not care whether it sees 2.9 V or 3.2 V: anything clearly high is a 1. Then the gate drives a fresh, full-strength output. Small errors are thrown away at every stage instead of accumulating. This restoring property is the whole reason computers work.

To make this precise, a logic family specifies four voltages. A receiving input is guaranteed to read 0 below \(V_{IL}\) and 1 above \(V_{IH}\); in between is a forbidden zone where the result is not guaranteed. A driving output is guaranteed to be below \(V_{OL}\) when it sends a 0 and above \(V_{OH}\) when it sends a 1. The gap between what is sent and what is needed is the noise margin, the amount of noise a signal can pick up and still be read correctly:

For the 3.3 V LVCMOS standard used on the PYNQ-Z2's LED, button and switch pins, the Xilinx 7-series data sheet gives approximately \(V_{IL} = 0.8\) V, \(V_{IH} = 2.0\) V, \(V_{OL} = 0.4\) V and \(V_{OH} = 3.3 - 0.4 = 2.9\) V, so \(NM_H \approx 0.9\) V and \(NM_L \approx 0.4\) V.

The program below makes the argument concrete. It sends a value through 30 stages that each add random noise. The analog chain drifts like a random walk, with error growing as \(\sigma\sqrt{N}\). The digital chain sees the same noise on every wire, yet every gate restores a clean level and not one bit is wrong.

One bit gives two values. A group of \(n\) bits, called a word or vector, gives \(2^n\) different patterns. To use them as numbers we give each position a weight, exactly as in decimal, but with powers of 2 instead of powers of 10. The rightmost bit is the least significant bit (LSB, weight 1) and the leftmost the most significant bit (MSB). We number bits from 0 at the LSB, so bit \(i\) weighs \(2^i\):

For example \(1101_2 = 8 + 4 + 0 + 1 = 13\). To convert a decimal number to binary, divide by 2 repeatedly and read the remainders from last to first: \(13 = 2\cdot6+1,\ 6 = 2\cdot3+0,\ 3 = 2\cdot1+1,\ 1 = 2\cdot0+1\), giving 1101.

Long binary strings are hard to read, so engineers write them in hexadecimal (base 16), with digits 0–9 and A–F. Because \(16 = 2^4\), each hex digit stands for exactly four bits and conversion is just grouping from the right: 1110 1011 = 0xEB = 235. The prefix 0x marks hex; in HDL you will meet 8'hEB (Verilog) and x"EB" (VHDL).

A useful habit: \(2^{10} = 1024 \approx 10^3\). So a 10-bit counter counts to about a thousand, 20 bits to about a million, 27 bits to about 134 million, which is roughly one second of the PYNQ-Z2's 125 MHz clock (Chapter 14).

A wire cannot carry a minus sign, so negative numbers must also be bit patterns. Almost all digital hardware uses two's complement, and the definition is a single change to the formula above: the MSB gets a negative weight.

Range. The largest value has the MSB at 0 and every other bit at 1: \(0111\ldots1_2 = 2^{n-1} - 1\). The smallest has only the MSB set: \(1000\ldots0_2 = -2^{n-1}\). So

The range is lopsided by one because zero takes one of the non-negative patterns. The MSB acts as a sign bit (1 means negative), and comparing the two formulas shows that whenever it is 1 the signed value is the unsigned value minus \(2^n\): \(S = U - 2^n\,b_{n-1}\).

Negation rule. Write \(\overline{x}\) for the word with every bit inverted. Adding a word to its inverse puts a 1 in every position, with no carries, and the all-ones pattern is \(-1\) in two's complement (check: \(-128+127 = -1\)). Hence

"Invert every bit and add one." For example \(+21 = 0001\,0101_2\); inverted, \(1110\,1010_2\); plus one, \(1110\,1011_2 = \)0xEB = −21, as in the figure.

The real reason hardware loves two's complement: in \(n\)-bit arithmetic every result is taken modulo \(2^n\) (the carry out of the top bit is simply dropped), and \(S \equiv U \pmod{2^n}\). So the same adder circuit adds unsigned and signed numbers; only our interpretation of the bits differs. Subtraction is addition of the negation: \(a - b = a + \overline{b} + 1\). To widen a signed number, copy its MSB into the new bits (sign extension): 1110 1011 becomes 1111 1111 1110 1011, still −21.

A logic gate is a small circuit (a handful of transistors) that computes one output bit from one or more input bits. Three operations are enough to describe any digital function:

• NOT (inverter): the output is the opposite of the input. Written \(\overline{a}\).
• AND: the output is 1 only if all inputs are 1. Written \(a\cdot b\) or just \(ab\).
• OR: the output is 1 if at least one input is 1. Written \(a + b\). (Here \(1 + 1 = 1\): this "+" is not addition.)

Four more are so common they have their own symbols. NAND and NOR are AND and OR followed by NOT; in CMOS they are actually the cheapest gates to build. XOR (exclusive OR) is 1 when the inputs differ, and XNOR when they are equal. XOR is the sum bit of a one-bit addition, which is why it will dominate Chapter 2.

A combinational circuit is one whose outputs depend only on its present inputs (no memory; memory arrives in Chapter 3). Such a circuit is completely described by its truth table: one row for each of the \(2^n\) input combinations, listing the output. Nothing else about the circuit matters to its function.

Take a concrete problem: three judges vote, and a motion passes when at least two vote yes. This is the majority function of three inputs:

With \(n\) inputs there are \(2^n\) rows, and each row can independently be 0 or 1, so there are \(2^{2^n}\) different Boolean functions: 16 of two inputs, 256 of three, about \(1.8\times10^{19}\) of six. Keep that number in mind. In Chapter 5 you will see that the basic FPGA cell, the 6-input look-up table (LUT), is a 64-bit memory that stores a truth table directly, so it can implement any of those functions.

Truth tables grow quickly, so we also manipulate expressions algebraically. Boolean algebra has laws that look like ordinary algebra, plus a few surprising ones. Every law can be proved by checking all rows of a truth table (the Python program in Section 3 does exactly that by brute force).

Notice the duality: swapping AND with OR and 0 with 1 turns every law into its partner. The second distributive law, \(a + bc = (a+b)(a+c)\), has no counterpart in ordinary arithmetic. Prove it by expanding the right side: \(a + ab + ac + bc = a(1 + b + c) + bc = a + bc\).

The two De Morgan laws tell you how to push a NOT through an AND or an OR: invert each input and swap the operation.

In words: "not (both)" is the same as "at least one is not"; "not (either)" is the same as "neither". The proof is a four-row truth table:

The laws extend to any number of inputs, \(\overline{a\,b\,c\cdots} = \overline{a}+\overline{b}+\overline{c}+\cdots\), and they have a graphical form called bubble pushing: a NAND gate is the same as an OR gate with bubbles on its inputs. This is why NAND alone is universal: with NOT and De Morgan you can make AND and OR out of NANDs (Problem 4).

Given any truth table, there is a mechanical recipe to build a circuit for it. For each row where the output is 1, write a product term (an AND) that is 1 for that row only: take each input as is if it is 1 in that row, inverted if it is 0. Such a term is called a minterm. Then OR all the minterms together. The result is the sum-of-products (SOP) form. For the majority function (rows 3, 5, 6, 7):

This is correct but wasteful: four 3-input ANDs and a 4-input OR. Algebra simplifies it. Use idempotence to copy the term \(abc\) three times (\(x = x + x + x\)), pair each copy with one other term, and use \(x + \overline{x} = 1\):

Three 2-input ANDs and one 3-input OR. The result also reads naturally: "some pair of judges agrees on yes." Chapter 2 introduces Karnaugh maps, a visual way to find such simplifications without guessing.

You will not draw gates by hand to program an FPGA. You will describe them in a hardware description language (HDL), and a tool called a synthesiser turns the description into hardware. Below is the majority circuit in the two HDLs this course uses, Verilog and VHDL. Do not worry about the syntax yet; Part III (Chapters 7–9) explains every keyword. Just notice that each line corresponds to one gate of the figure above, and that both languages describe exactly the same circuit.

// Majority of three inputs, written gate by gate.
// y = a.b + a.c + b.c  (sum of products)
module majority3 (
    input  wire a,
    input  wire b,
    input  wire c,
    output wire y
);
    wire ab, ac, bc;

    and g1 (ab, a, b);      // product terms
    and g2 (ac, a, c);
    and g3 (bc, b, c);
    or  g4 (y, ab, ac, bc); // their sum
endmodule

-- Majority of three inputs, written gate by gate.
-- y = a.b + a.c + b.c  (sum of products)
library ieee;
use ieee.std_logic_1164.all;

entity majority3 is
    port (
        a : in  std_logic;
        b : in  std_logic;
        c : in  std_logic;
        y : out std_logic
    );
end entity;

architecture gates of majority3 is
    signal ab, ac, bc : std_logic;
begin
    ab <= a and b;          -- product terms
    ac <= a and c;
    bc <= b and c;
    y  <= ab or ac or bc;   -- their sum
end architecture;

A testbench (Chapter 10) for this module applies all eight input rows and compares the output against "at least two inputs are 1". Run with the free simulators Icarus Verilog and GHDL, both versions print the same truth table as Section 5 and end with PASS: all 8 rows correct. On the FPGA itself, the whole circuit would fit in a single LUT.