Logic Gates and Arithmetic - How Switches Learn to Add

5.0 What this chapter gives you#

1. You will be able to explain how a rule about true and false became a rule about electricity, and who made that jump and when.
2. You will be able to draw a CMOS inverter, a NAND gate and a NOR gate from real transistors, and count how many transistors each one needs.
3. You will know all seven basic gates by truth table and by plain meaning, and be able to say what each one is for.
4. You will be able to build every gate out of NAND gates only, and say why chip factories care about that.
5. You will be able to take a written specification, turn it into a truth table, and shrink it with a Karnaugh map.
6. You will be able to build a half adder, a full adder and an 8-bit adder, and trace a carry moving through it bit by bit.
7. You will be able to explain how the same adder does subtraction, and how the hardware notices that a result went wrong.
8. You will be able to describe a multiplexer, decoder, comparator, barrel shifter and priority encoder, and say where each sits in a CPU.
9. You will be able to compute the maximum clock speed of a circuit from the delays of its gates.
10. You will be able to explain, from the hardware upward, why 0.1 plus 0.2 does not equal 0.3 on almost every computer you will ever touch.

5.1 Boolean algebra: true and false as 1 and 0#

PLAIN5.1.1 in simple words#

1. Ordinary algebra works with numbers. You add them, multiply them, and follow rules.
2. Boolean algebra works with only two values: true and false.
3. We write true as 1 and false as 0. That is all the values there are.
4. It has three basic operations: AND, OR and NOT.
5. AND is true when both of its two inputs are true.
6. OR is true when at least one of its two inputs is true.
7. NOT flips a value. It turns true into false and false into true.
8. That tiny system is enough to describe every calculation a computer does.
9. A man named George Boole invented it in the 1840s and 1850s.
10. He was doing philosophy and mathematics. He was not thinking about machines, because there were no electronic machines yet.
11. Almost a hundred years later, a student noticed that electrical switches obey exactly those same rules.
12. That student was Claude Shannon, and his observation is why computers work the way they do.

PLAIN5.1.2 a picture in your head#

1. Think of a torch (a flashlight) with two switches wired one after the other along the same wire.
2. Current can only reach the bulb if switch one is closed AND switch two is closed.
3. One switch open anywhere in the line, and the bulb stays dark.
4. That wiring is an AND gate. Two switches in a line.
5. Now rewire the two switches side by side, each with its own path to the bulb.
6. Now the bulb lights if switch one is closed OR switch two is closed, or both.
7. That wiring is an OR gate. Two switches side by side.
8. So “in a line” means AND, and “side by side” means OR. Nothing more complicated than that is needed to start.
9. Where this comparison breaks: real gates do not pass the input current through to the output.
10. A real gate reads its inputs and then uses its own power supply to drive a fresh output. It is a decision, not a pipe.
11. That difference matters, because it is why you can chain a million gates together without the signal fading away.

PLAIN5.1.3 a worked example#

1. Take a door that should unlock only when a valid card is presented and the time is inside working hours.
2. Call the card signal C. C is 1 when a valid card is seen.
3. Call the time signal T. T is 1 when the clock is between 09:00 and 18:00.
4. The unlock rule is U = C AND T.
5. Here is every case.

6. Now add a fire alarm. If the alarm F is 1, the door must open no matter what.
7. The new rule is U = (C AND T) OR F.
8. If F is 1, the OR makes U 1 whatever the left side says.
9. If F is 0, the OR passes the left side through unchanged.
10. You have just written a real access-control specification in Boolean algebra, and it can be built directly out of two gates.

PLAIN5.1.4 what is really happening inside#

1. Inside a chip there is no “true” and no “false”. There is only voltage.
2. A wire is held at one of two voltages. In a typical modern core, about 0.75 volts or about 0 volts.
3. The high voltage is agreed to mean 1. The low voltage is agreed to mean 0.
4. That agreement is a choice made by the designers, not a law of nature.
5. There is a band of voltages in the middle that means nothing. Circuits are designed to pass through it as fast as possible and never rest there.
6. A gate is a small circuit that senses the voltages on its input wires.
7. It then connects its output wire either up to the power rail or down to ground, depending on what it senses.
8. Because the gate drives the output from its own power supply, the output is a clean full-strength 1 or 0.
9. That is called restoring the signal, and it is what lets you build circuits thousands of gates deep.
10. The honest version: the two voltages are not exact. A real 1 might be 0.71 volts on one wire and 0.78 volts on another.
11. The circuit only has to keep every 1 above a guaranteed minimum and every 0 below a guaranteed maximum. Those two numbers are in the datasheet.

TECHNICAL5.1.5 the engineer’s version#

1. George Boole published “The Mathematical Analysis of Logic” in 1847 and “An Investigation of the Laws of Thought” in 1854.
2. Boole’s system was a two-valued algebra over the set {0, 1} with the operations we now call conjunction, disjunction and complement.
3. Augustus De Morgan, a contemporary and correspondent of Boole, published “Formal Logic” in 1847, containing the two duality laws that carry his name.
4. Claude Elwood Shannon submitted his master’s thesis at the Massachusetts Institute of Technology on 10 August 1937, titled “A Symbolic Analysis of Relay and Switching Circuits”.
5. A revised, abridged version appeared in the Transactions of the American Institute of Electrical Engineers, volume 57, in 1938, pages 713 to 723.
6. The paper won the Alfred Noble Prize in 1939. That prize is named after an American engineer, not after Alfred Nobel of the Nobel Prizes.
7. In 1985 the psychologist Howard Gardner described it as “possibly the most important, and also the most famous, master’s thesis of the century”.
8. Shannon’s contribution was the mapping: a relay contact in series is a Boolean product, a relay contact in parallel is a Boolean sum, and a normally-closed contact is a complement.
9. That mapping turned circuit design from trial and error into algebra. You can now simplify a circuit by simplifying an expression.
10. Modern logic levels are defined per family. Some real figures:

11. These are standards written in vendor datasheets and in JEDEC documents, not conventions. A part that violates them is defective.
12. Positive logic means high voltage equals 1, and it is a near-universal convention. Negative logic, where low means 1, still appears on reset and chip-select pins, marked with an overbar or a leading letter n.

WORDS5.1.6 remember these#

1. Boolean algebra — maths with only true and false — a two-element algebraic structure over {0, 1} with AND, OR and NOT.
2. Bit — one true-or-false value — one binary digit, the smallest unit of information.
3. Logic level — which voltage counts as 1 — a specified voltage band with guaranteed input and output thresholds.
4. Gate — a small circuit that makes one decision — a combinational element implementing one Boolean function.
5. Truth table — a list of every input case and its answer — the complete functional specification of a combinational circuit.
6. Positive logic — high voltage means 1 — the near-universal signalling convention in current CMOS families.

5.2 Building gates from real MOSFETs#

PLAIN5.2.1 in simple words#

1. A transistor is a switch with no moving parts, controlled by a voltage on a third wire called the gate.
2. Modern chips use two kinds of transistor together. The style is called CMOS.
3. An NMOS transistor conducts when its gate is high. High turns it on.
4. A PMOS transistor conducts when its gate is low. Low turns it on. It is the opposite.
5. Every CMOS gate has two halves. A group of PMOS transistors on top, joined to the power supply.
6. And a group of NMOS transistors underneath, joined to ground.
7. The output wire sits between the two halves.
8. The design rule is simple. Exactly one half must be conducting at any time.
9. If the top half conducts, the output is pulled up to the power supply and reads as 1.
10. If the bottom half conducts, the output is pulled down to ground and reads as 0.
11. If both halves ever conducted at once, current would pour straight from power to ground and the chip would waste energy and heat up.

PLAIN5.2.2 a picture in your head#

1. Imagine a bucket with a tap above it and a plug hole below it.
2. The tap is the PMOS half. The plug hole is the NMOS half.
3. Open the tap and close the plug: the bucket fills. That is output 1.
4. Close the tap and open the plug: the bucket empties. That is output 0.
5. The whole trick of CMOS is that the two are wired to be opposites. Whenever one opens, the other closes.
6. So the bucket is always either full or empty, and never both filling and draining at once.
7. Where this comparison breaks: water takes real time to fill a bucket, and so does charge, but the amount of charge involved is tiny.
8. The other break is that a real gate does pass a very small current while it is switching over, in the moment when both halves are briefly part-open.
9. That brief overlap is called short-circuit current, and it is a genuine part of a chip’s power budget, though usually a small part.

PLAIN5.2.3 a worked example#

1. Here is the simplest CMOS gate. It has one input and one output, and it flips the value. It is the NOT gate, also called an inverter.

              VDD  (the power rail, logic 1)
               |
             __|__
        A --o|     |   PMOS: conducts when A = 0
             |_____|
               |
               +------------ OUT
               |
             __|__
        A ---|     |   NMOS: conducts when A = 1
             |_____|
               |
              GND  (ground, logic 0)

2. The small circle on the PMOS gate is the standard way to mark “this one is on when the input is low”.
3. Case A = 0. The PMOS is on, because its gate is low. The NMOS is off, because its gate is low. The output is connected up to VDD. OUT = 1.
4. Case A = 1. The PMOS is off, because its gate is high. The NMOS is on. The output is connected down to GND. OUT = 0.
5. Two transistors. That is the entire NOT gate.
6. Note what the table shows: the output is always the opposite of the input, which is exactly the definition of NOT.

PLAIN5.2.4 what is really happening inside#

1. Now the NAND gate. NAND means NOT-AND. Its output is 0 only when both inputs are 1.
2. The rule for building any CMOS gate is a rule of shapes. For AND-like behaviour, put transistors in series. For OR-like behaviour, put them in parallel.
3. The NMOS half of a NAND has the two transistors in series, so the output can only be pulled down when both inputs are high.
4. The PMOS half has the two transistors in parallel, so the output is pulled up if either input is low.

                    VDD
                     |
           +---------+---------+
         __|__               __|__
    A --o|     |         B --o|     |    P1 and P2 in PARALLEL
         |_____|              |_____|
           |                    |
           +---------+----------+
                     |
                     +--------------- OUT
                     |
                   __|__
              A ---|     |   N1
                   |_____|
                     |
                   __|__
              B ---|     |   N2   N1 and N2 in SERIES
                   |_____|
                     |
                    GND

5. Case A=0, B=0. Both PMOS are on. Both NMOS are off. Output pulled up. OUT = 1.
6. Case A=0, B=1. P1 is on, P2 is off, so the parallel pull-up still conducts. N1 is off, so the series pull-down is broken. OUT = 1.
7. Case A=1, B=0. P1 is off, P2 is on, so the pull-up still conducts. N2 is off, so the pull-down is broken. OUT = 1.
8. Case A=1, B=1. Both PMOS are off. Both NMOS are on, so the series chain is complete. Output pulled down. OUT = 0.
9. Four transistors. That is the entire NAND gate.
10. The NOR gate is the same idea with the two halves swapped over. PMOS in series on top, NMOS in parallel underneath.

                    VDD
                     |
                   __|__
              A --o|     |   P1
                   |_____|
                     |
                   __|__
              B --o|     |   P2   P1 and P2 in SERIES
                   |_____|
                     |
                     +--------------- OUT
                     |
           +---------+---------+
         __|__               __|__
    A ---|     |         B ---|     |    N1 and N2 in PARALLEL
         |_____|              |_____|
           |                    |
           +---------+----------+
                     |
                    GND

11. Case A=0, B=0. Both PMOS on, series chain complete, pull-up wins. OUT = 1.
12. Case A=0, B=1. P2 is off, so the series pull-up is broken. N2 is on, so the parallel pull-down conducts. OUT = 0.
13. Case A=1, B=0. P1 is off, pull-up broken. N1 is on, pull-down conducts. OUT = 0.
14. Case A=1, B=1. Both PMOS off. Both NMOS on. OUT = 0.
15. Four transistors again.
16. Notice something important. Both of these natural, cheap, four-transistor gates produce an inverted output. CMOS is naturally inverting.
17. To get a plain AND you must build a NAND and then add an inverter, which costs two more transistors. AND is six transistors, not four.

TECHNICAL5.2.5 the engineer’s version#

1. MOSFET stands for metal-oxide-semiconductor field-effect transistor. The gate terminal is insulated from the channel by a thin oxide layer.
2. An NMOS device conducts when the gate-to-source voltage exceeds its threshold voltage, typically around 0.2 to 0.4 volts in modern low-voltage processes.
3. CMOS as a circuit style was invented in 1963 by Frank Wanlass and Chih-Tang Sah at the Fairchild Semiconductor research laboratory.
4. They presented “Nanowatt Logic Using Field-Effect Metal-Oxide Semiconductor Triodes” at the International Solid-State Circuits Conference on 20 February 1963.
5. Wanlass received United States patent 3,356,858, filed 18 June 1963 and issued 5 December 1967.
6. The headline property of CMOS is that static power is near zero. Current flows mainly during switching, to charge and discharge load capacitance.
7. The dynamic power of a CMOS node is approximately P = a x C x V x V x f, where a is the activity factor, C the switched capacitance, V the supply voltage and f the frequency.
8. Because power scales with the square of the voltage, supply voltages fell from 5 volts in the 1980s to roughly 0.7 to 0.9 volts in current logic.
9. The honest version: static power is no longer negligible. At small geometries, sub-threshold leakage and gate-oxide tunnelling leakage can be a large share of total power, which is why unused blocks are power-gated.
10. Transistor counts for static complementary CMOS gates:

11. A 2-input OR is likewise 6 transistors: a NOR plus an inverter.
12. A static CMOS 2-input XOR is commonly drawn with 12 transistors. A transmission-gate XOR needs 6, and various pass-transistor designs need 4. The exact count is an implementation detail of the standard-cell library, not a property of XOR.
13. In a real chip you do not draw transistors. You instantiate cells from a standard-cell library such as NAND2_X1 or INVX4, where the trailing number is the drive strength.
14. Tools that let you observe this: Yosys and OpenLane for open synthesis flows, ngspice for transistor-level simulation, and Magic or KLayout for viewing layout.

WORDS5.2.6 remember these#

1. MOSFET — a voltage-controlled switch — a field-effect transistor with an insulated gate over a channel.
2. NMOS — the type that turns on with a high gate — an n-channel enhancement MOSFET conducting when Vgs is above threshold.
3. PMOS — the type that turns on with a low gate — a p-channel enhancement MOSFET conducting when Vgs is below its negative threshold.
4. CMOS — using both types together — complementary metal-oxide-semiconductor logic with a pull-up network and a complementary pull-down network.
5. Pull-up network — the half that connects the output to power — the PMOS network conducting for input patterns that produce a 1.
6. Pull-down network — the half that connects the output to ground — the NMOS network conducting for input patterns that produce a 0.
7. Standard cell — a ready-made gate layout — a characterized, pre-laid-out logic cell in a foundry library with published timing and power data.

5.3 The seven gates#

PLAIN5.3.1 in simple words#

1. There are seven gates you must know. Three basic ones and four built from them.
2. AND: output 1 only when both inputs are 1. Plain meaning: “both of them”.
3. OR: output 1 when at least one input is 1. Plain meaning: “either one, or both”.
4. NOT: one input, output is the opposite. Plain meaning: “the reverse”.
5. NAND: AND with the answer flipped. Plain meaning: “not both of them”.
6. NOR: OR with the answer flipped. Plain meaning: “neither of them”.
7. XOR: output 1 when the two inputs differ. Plain meaning: “exactly one of them”.
8. XNOR: XOR with the answer flipped. Plain meaning: “the two are the same”.
9. That is the whole vocabulary. Every digital circuit ever built is these seven, repeated.

PLAIN5.3.2 a picture in your head#

1. Picture two people voting on whether to go out.
2. AND is a strict rule: we go only if both say yes.
3. OR is a relaxed rule: we go if anybody says yes.
4. NAND is a veto rule reversed: we go unless both say yes.
5. NOR is a very strict rule: we go only if nobody says yes.
6. XOR is a disagreement detector: it lights up exactly when the two people disagree.
7. XNOR is an agreement detector: it lights up exactly when they agree.
8. Where this comparison breaks: people can abstain, hesitate, or change their mind halfway. A gate input is always exactly 0 or exactly 1 at the moment the answer is read.
9. Real wires do spend a few picoseconds in between while changing. Circuits are designed so nobody reads the answer during that window. Chapter 6 covers how that is arranged with a clock.

PLAIN5.3.3 a worked example#

1. Here are all seven truth tables. Each has at most two inputs.

AND — “both of them”:

OR — “either one, or both”:

NOT — “the reverse”:

NAND — “not both of them”:

NOR — “neither of them”:

XOR — “exactly one of them”:

XNOR — “the two are the same”:

2. Read down the last column of NAND and compare with AND. Every row is flipped. That is all “N” in front of a name means.
3. Read down XOR. It is 1 in exactly the two rows where A and B are different.
4. XOR is the single most useful gate in arithmetic, because adding 1 and 1 in binary gives 0 with a carry, and XOR gives exactly that 0.

PLAIN5.3.4 what is really happening inside#

1. Nothing about a gate knows the word “AND”. The gate is a shape of transistors, and the truth table is what that shape does.
2. A gate does not compute in steps. It settles. You change the inputs, and after a short delay the output arrives at the right value.
3. That delay is called propagation delay, and it is the single most important number about a gate.
4. Gates with more inputs are slower, because more transistors sit in series in one of the two halves.
5. That is why a 4-input NAND is slower than a 2-input NAND, and why libraries usually stop at three or four inputs and build wider functions as trees.
6. XOR is not a natural CMOS shape. There is no simple series and parallel arrangement that produces “the inputs differ”.
7. So XOR is built from other gates or from special transistor tricks, and it is always more expensive and slower than NAND or NOR.
8. This has a real consequence you will meet in section 5.6: an adder is mostly XOR gates, and that is a large part of why addition is not free.

TECHNICAL5.3.5 the engineer’s version#

1. Standard symbols come from two competing sets: the distinctive shapes of ANSI/IEEE 91-1984, and the rectangular symbols of IEC 60617-12.
2. In practice, distinctive shapes dominate American and textbook usage, and rectangles dominate European formal drawings. This is a convention split, not a correctness issue.
3. In hardware description languages the operators are written as symbols. Verilog uses & for AND, | for OR, ~ for NOT and ^ for XOR.

wire y_and  =  a & b;
wire y_or   =  a | b;
wire y_not  = ~a;
wire y_nand = ~(a & b);
wire y_nor  = ~(a | b);
wire y_xor  =  a ^ b;
wire y_xnor = ~(a ^ b);

4. Discrete parts in the 7400 family, first shipped by Texas Instruments as the military 5400 series in October 1964 and the commercial plastic 7400 series in the third quarter of 1966:

5. The 7408 is quad 2-input AND and the 7432 is quad 2-input OR. It is not an accident that the very first part in the family, the 7400, was a NAND.
6. Typical transistor counts in a static CMOS standard-cell library:

7. The relative delay figures are indicative for a typical library at equal drive strength, not a specification. Exact values come from the foundry characterization data, usually in Liberty format files with a .lib extension.
8. NOR2 is slower than NAND2 at equal area, because a NOR’s series transistors are PMOS. Hole mobility is two to three times lower than electron mobility, so those PMOS must be made wider.
9. Fan-in is the number of inputs to a gate. Fan-out is the number of gate inputs a single output drives. Both increase delay, fan-out roughly linearly.
10. The standard unit for comparing logic speed across process nodes is the fan-out-of-four inverter delay, written FO4. It is the delay of an inverter driving four copies of itself.

WORDS5.3.6 remember these#

1. XOR — exactly one of them is 1 — the two-input parity function, also called modulo-2 addition.
2. XNOR — the two are the same — the equivalence function, the complement of XOR.
3. NAND — not both of them — the complement of conjunction, and a functionally complete operator.
4. NOR — neither of them — the complement of disjunction, also functionally complete.
5. Propagation delay — how long a gate takes to answer — the time from an input crossing 50 percent of the supply to the output crossing 50 percent.
6. Fan-in — how many inputs a gate has — the count of gate inputs, which raises delay through series transistor stacking.
7. Fan-out — how many inputs one output feeds — the capacitive load on a driver, which raises delay roughly in proportion.
8. FO4 — a fair speed yardstick — the delay of an inverter loaded by four identical inverters, used to compare process technologies.

5.4 Universality: why NAND alone is enough#

PLAIN5.4.1 in simple words#

1. Here is a surprising fact. You do not need seven kinds of gate. You need one.
2. If you have an unlimited supply of NAND gates and wire, you can build every other gate.
3. And if you can build every other gate, you can build every digital circuit that has ever existed.
4. A gate that can do this on its own is called universal, or functionally complete.
5. NAND is universal. NOR is universal too, on its own, in exactly the same way.
6. AND is not universal. Neither is OR. Neither is XOR. None of them can produce a NOT.
7. The reason is simple: AND, OR and XOR of two 0s all give 0. They can never turn a 0 into a 1 on their own.
8. NAND can. NAND of two 0s gives 1. That ability to invert is the key.

PLAIN5.4.2 a picture in your head#

1. Think of a language with only one word, where the word changes meaning depending on how you repeat and arrange it.
2. That sounds useless, but it is exactly what NAND is. One operation, rearranged, becomes all the others.
3. A closer everyday comparison is Lego bricks. There are many shapes, but you could build almost any model from one single brick shape, given enough of them.
4. It would be less elegant and use more bricks, but it would work, and you would only need one bin of parts.
5. Where this comparison breaks: with Lego, using one brick shape is a handicap. With NAND, it is often an advantage.
6. NAND is the cheapest and fastest gate CMOS can make, so building things out of NAND is not a sacrifice. It is frequently the best option.

PLAIN5.4.3 a worked example#

1. NOT from one NAND. Tie both inputs together.

   A ---+
        |---[ NAND ]--- OUT = NOT A
   A ---+

2. Check it. If A = 0, then NAND(0,0) = 1. If A = 1, then NAND(1,1) = 0. That is NOT.
3. AND from two NANDs. NAND then invert.

   A ---+
        +--> NAND1 --- X ---+
   B ---+                   +--> NAND2 ---> OUT = A AND B
                            +
   Both inputs of NAND2 are tied to X, so NAND2 is an inverter.

4. Written plainly: X = A NAND B, then OUT = X NAND X. Two gates.
5. OR from three NANDs. Invert both inputs first, then NAND them.

   A ---+--> NAND1 --- P ---+
   A ---+                   |
                            +--> NAND3 ---> OUT = A OR B
   B ---+--> NAND2 --- Q ---+
   B ---+

   NAND1 and NAND2 are inverters, so P = NOT A and Q = NOT B.

6. Written plainly: P = NOT A, Q = NOT B, OUT = P NAND Q. Three gates.
7. Why does that give OR? Because NAND(NOT A, NOT B) is NOT(NOT A AND NOT B), and “not (neither)” means “at least one”. That is OR.
8. XOR from four NANDs. This is the classic arrangement.

   X = A NAND B
   Y = A NAND X
   Z = B NAND X
   OUT = Y NAND Z          and this equals A XOR B

   A ---+--> NAND1 ---+--> NAND2 --- Y ---+
        |      ^      |       ^           |
   B ---+------+      |       A           +--> NAND4 --> OUT
        |             |                   |
        +-------------+--> NAND3 --- Z ---+
                              ^
                              B

9. Step by step with A = 1, B = 0.
10. NAND1 = NAND(1, 0) = 1.
11. NAND2 = NAND(A, NAND1) = NAND(1, 1) = 0.
12. NAND3 = NAND(B, NAND1) = NAND(0, 1) = 1.
13. NAND4 = NAND(0, 1) = 1. And XOR(1, 0) = 1. Correct.
14. Now A = 1, B = 1. NAND1 = 0. NAND2 = NAND(1, 0) = 1. NAND3 = NAND(1, 0) = 1. NAND4 = NAND(1, 1) = 0. And XOR(1, 1) = 0. Correct.

15. NOR from NAND takes 4 as well: build OR with 3, then invert with 1.

PLAIN5.4.4 what is really happening inside#

1. The deep reason NAND works is that it combines two abilities in one gate.
2. It can combine two signals, and it can invert. Any gate that can do both can build everything.
3. A formal way to see it: every Boolean function can be written as a sum of products, meaning ORs of ANDs of inputs and inverted inputs.
4. If you can make AND, OR and NOT, you can write any sum of products. And NAND makes all three.
5. So NAND builds every possible function of any number of inputs. There are no exceptions and no special cases.
6. NOR is universal for the mirror-image reason: it can combine and it can invert, so it builds product of sums instead.
7. The honest version: universality is a statement about what is possible, not about what is sensible.
8. Building a 64-bit multiplier out of nothing but 2-input NAND gates is possible and would be enormous and slow. Real designs use whatever cell in the library is cheapest for the job.

TECHNICAL5.4.5 the engineer’s version#

1. Functional completeness of the Sheffer stroke was shown by Henry M. Sheffer in his 1913 paper in the Transactions of the American Mathematical Society. The Sheffer stroke is NAND.
2. Charles Sanders Peirce had found the same result earlier, in unpublished work dated around 1880. The NOR operator is still called Peirce’s arrow.
3. NAND is preferred over NOR in CMOS for a physical reason. In a NAND, the series stack is NMOS and the parallel network is PMOS.
4. Electron mobility in silicon is roughly 1400 square centimetres per volt-second, while hole mobility is roughly 450. The ratio is about 3 in bulk, and about 2 to 2.5 for carriers in a MOSFET inversion layer.
5. Because PMOS devices carry less current per unit width, a series PMOS stack in a NOR must be made two to three times wider than the equivalent NMOS stack in a NAND to reach the same speed.
6. Wider transistors mean more area, more input capacitance and more power. So NOR2 costs more than NAND2 for the same performance.
7. Consequence: standard-cell libraries are NAND-heavy, synthesis tools map preferentially onto NAND and inverter, and NAND2_X1 is typically the most instantiated cell on a die.
8. NAND flash memory is named for the same series-stack idea, with memory cells in series along a bit line. It is a separate use of the word from NAND logic and the two should not be confused.
9. In FPGA design the picture changes completely. An FPGA has no gates. It has lookup tables, typically 6-input LUTs in current Xilinx and AMD parts and in Intel and Altera adaptive logic modules.
10. A 6-input LUT is a 64-bit memory addressed by the six inputs. It implements any function of six variables at identical cost, so gate-count reasoning does not apply. This is an implementation detail of FPGAs, not of logic.

WORDS5.4.6 remember these#

1. Universal gate — one gate that can build all the rest — a functionally complete operator whose closure is all Boolean functions.
2. Functional completeness — nothing else is needed — the property that every Boolean function is expressible using only the given operator set.
3. Sheffer stroke — another name for NAND — the binary connective written as a vertical bar, proved complete by Sheffer in 1913.
4. Peirce arrow — another name for NOR — the dual complete connective, attributed to Charles Sanders Peirce.
5. LUT — a small table that fakes any gate — a lookup table in an FPGA, a configuration memory addressed by the input signals.
6. Technology mapping — turning a design into real cells — the synthesis step that covers a Boolean network with cells from a target library.

5.5 Writing and simplifying logic#

PLAIN5.5.1 in simple words#

1. A truth table says what a circuit must do. An expression says how to build it. You need to move between the two.
2. Going from a table to an expression is mechanical. Look at every row where the output is 1.
3. For each such row, write an AND of all the inputs, with a NOT on any input that is 0 in that row.
4. Then OR all those AND terms together. You now have a working circuit.
5. That form is called sum of products, because OR behaves like a sum and AND behaves like a product.
6. The expression you get this way is correct but usually wasteful. It has one AND term for every 1 in the table.
7. Simplifying means finding a smaller expression that gives exactly the same table. Fewer gates, less area, less power, less delay.
8. There are two ways to simplify. By algebra, using rules. Or by drawing a picture called a Karnaugh map and spotting groups by eye.

PLAIN5.5.2 a picture in your head#

1. Think of writing driving directions. The literal version lists every single junction: “at junction 1 go straight, at junction 2 go straight, at junction 3 turn left”.
2. The simplified version says: “go straight until the church, then turn left”.
3. Both get you to the same place. The second is shorter because it noticed a run of identical steps and merged them.
4. Simplifying logic is exactly that. You look for groups of rows that agree on most inputs, and merge them into one shorter rule.
5. Where this comparison breaks: with directions there is one obvious way to merge. With logic there can be several different smallest answers, all equally good.
6. Also, the smallest expression is not always the fastest circuit. A shallower circuit with more gates can beat a deeper circuit with fewer.

PLAIN5.5.3 a worked example#

1. Here are the core identities. A prime mark means NOT.

2. In these lines a dot means AND and a plus means OR. That is the standard written shorthand.
3. Now De Morgan’s two laws, proved by writing out every case.
4. First law: NOT (A AND B) equals (NOT A) OR (NOT B).

5. The last two columns match on every row. The law holds. That is a complete proof, because there are only four cases and we checked all four.
6. Second law: NOT (A OR B) equals (NOT A) AND (NOT B).

7. Again both columns match on every row. The law holds.
8. In plain words: “not both” is the same as “either one is missing”, and “neither” is the same as “this one is missing and that one is missing”.

PLAIN5.5.4 what is really happening inside#

1. Now a complete Karnaugh map for four variables, from the table to the answer.
2. The specification: four sensor bits A, B, C and D arrive, with A as the most significant bit. Output F must be 1 for these input values, and 0 otherwise.
3. This function is invented for teaching. The method is the real thing.

4. Step 1. Write the raw sum of products straight from the ten rows with a 1. That is ten AND terms of four inputs each. It works and it is horrible.
5. Step 2. Draw the map. The rows are AB, the columns are CD, and both are listed in the order 00, 01, 11, 10.
6. That strange order is Gray code. Only one bit changes between neighbours, so squares that touch differ in exactly one variable.

             CD=00   CD=01   CD=11   CD=10
   AB=00   |   1   |   1   |   1   |   1   |   (m0  m1  m3  m2)
   AB=01   |   1   |   1   |   0   |   0   |   (m4  m5  m7  m6)
   AB=11   |   0   |   0   |   1   |   1   |   (m12 m13 m15 m14)
   AB=10   |   0   |   0   |   1   |   1   |   (m8  m9  m11 m10)

7. Step 3. Find the biggest rectangles of 1s. Sizes must be 1, 2, 4, 8 or 16, and rectangles may wrap around the edges.
8. Group one: the whole top row, four squares, m0 m1 m3 m2. Across that row A is always 0 and B is always 0, while C and D take every value. So the term is A’B’.
9. Group two: the left two columns of the top two rows, m0 m1 m4 m5. Here A is always 0 and C is always 0. The term is A’C’.
10. Group three: the right two columns of the bottom two rows, which is m15, m14, m11 and m10. Across those four squares A is always 1 and C is always 1. The term is AC.
11. Step 4. Check the cover. A’B’ covers 0, 1, 2, 3. A’C’ covers 0, 1, 4, 5. AC covers 10, 11, 14, 15. Together that is all ten 1s and nothing else.
12. Step 5. Write the answer.

   F = A'B' + A'C' + AC

13. Ten four-input AND terms became three two-input AND terms. That is three AND gates, one OR gate and two inverters, instead of dozens of gates.
14. Sanity check value 6, which is A=0 B=1 C=1 D=0. A’B’ is 0 because B is 1. A’C’ is 0 because C is 1. AC is 0 because A is 0. So F = 0, matching the table.
15. Sanity check value 11, which is A=1 B=0 C=1 D=1. A’B’ is 0 and A’C’ is 0, both because A is 1. AC is 1. So F = 1, matching the table.

TECHNICAL5.5.5 the engineer’s version#

1. The canonical sum of products form is also called the minterm expansion or disjunctive normal form. The dual is the maxterm expansion, or conjunctive normal form.
2. A minterm is a product term containing every variable exactly once. Minterm m5 of four variables is A’BC’D, because 5 is binary 0101.
3. The standard notation for the function above is F(A,B,C,D) = sum of m(0, 1, 2, 3, 4, 5, 10, 11, 14, 15).
4. Maurice Karnaugh published “The Map Method for Synthesis of Combinational Logic Circuits” in the Transactions of the American Institute of Electrical Engineers in November 1953.
5. It refined Edward W. Veitch’s 1952 Veitch chart, which was itself a rediscovery of Allan Marquand’s logical diagram of 1881.
6. Karnaugh maps are practical up to four variables, awkward at five and six, and useless beyond that. Beyond four variables, use an algorithm.
7. The Quine-McCluskey algorithm, published by Willard Quine in 1952 and extended by Edward McCluskey in 1956, gives a guaranteed minimal cover but has exponential worst-case cost.
8. Production tools use Espresso, developed at the University of California, Berkeley in the early 1980s. Espresso is a heuristic minimizer: it is fast and very good, but it does not promise the absolute minimum.
9. A prime implicant is a product term that cannot be enlarged further without covering a 0. An essential prime implicant is one that uniquely covers at least one minterm.
10. In the worked map, all three terms are essential prime implicants, so the minimal cover is unique. That is not always the case.
11. Don’t-care conditions, written X or d, are input combinations that cannot occur. They may be read as 1 or 0, whichever makes groups larger. Binary-coded decimal decoders are the classic case: 10 to 15 never occur.
12. De Morgan’s laws generalize to any number of variables and are the formal basis of bubble pushing, the visual technique of moving inversion circles across a gate symbol while swapping AND for OR.
13. Modern practice: nobody minimizes by hand for production. You write the behaviour in Verilog, SystemVerilog or VHDL and a synthesis tool such as Synopsys Design Compiler, Cadence Genus or the open-source Yosys performs minimization and technology mapping.
14. You still do it by hand to read a datasheet, to debug a synthesis result, and to pass an interview.

WORDS5.5.6 remember these#

1. Sum of products — ORs of ANDs — disjunctive normal form, a two-level AND-OR realization.
2. Minterm — one row of the table as a term — a product containing every variable in true or complemented form.
3. Karnaugh map — a grid that makes groups visible — a Gray-coded truth table arrangement placing logically adjacent minterms physically adjacent.
4. Gray code — an order where one bit changes at a time — a reflected binary code with unit Hamming distance between neighbours.
5. Prime implicant — a group that cannot grow — a product term implying the function that is not contained in any larger such term.
6. Don’t care — a case that cannot happen — an unspecified output used to enlarge groups during minimization.
7. De Morgan’s laws — not both means either is missing — the dual identities (A.B)’ = A’ + B’ and (A+B)’ = A’.B’.

5.6 Adding#

PLAIN5.6.1 in simple words#

1. Binary addition has only four cases for a single column: 0+0, 0+1, 1+0 and 1+1.
2. The first three give 0, 1 and 1. The fourth gives 0 with a 1 carried into the next column.
3. So each column produces two outputs: a sum bit and a carry bit.
4. The sum bit is 1 when exactly one input is 1. That is XOR.
5. The carry bit is 1 when both inputs are 1. That is AND.
6. A circuit with two inputs producing those two outputs is called a half adder.
7. It is called half because it cannot accept a carry coming in from the column to its right.
8. Add that third input and you have a full adder. A full adder takes three bits in and produces a sum bit and a carry bit out.
9. Chain eight full adders together, feeding each carry-out into the next carry-in, and you can add two 8-bit numbers.

PLAIN5.6.2 a picture in your head#

1. Think of a line of eight people, each holding two coins and passing notes to the left.
2. Each person adds their two coins plus any note passed to them from the right.
3. If the total is 2 or 3, they pass a note left saying “carry one”, and keep the remainder.
4. The person on the far right starts with no incoming note.
5. Nobody can finish until the person on their right has finished, because they are waiting for the note.
6. So the total time is not the time for one person. It is the time for the note to travel all the way from the right end to the left end.
7. That waiting chain is the single reason addition is not instant, and it is what carry-lookahead exists to fix.
8. Where this comparison breaks: the people do not really take turns. All eight full adders are working continuously and all the time, on whatever values currently sit on their wires.
9. The values just happen to be wrong until the carry has finished travelling. The circuit does not know it is wrong. It simply settles.

PLAIN5.6.3 a worked example#

1. The half adder.

          +-----------+
   A ---->|           |---> SUM   = A XOR B
          |   HALF    |
   B ---->|   ADDER   |---> CARRY = A AND B
          +-----------+

2. The full adder, built from two half adders and one OR gate.

   A --->+-----+
         | HA1 |-- S1 -->+-----+
   B --->+-----+         | HA2 |---> SUM
            |            |     |
            C1    Cin -->+-----+
            |               |
            |               C2
            |               |
            +---> [ OR ] <--+
                     |
                     v
                    Cout

3. The first half adder adds A and B. The second adds that partial sum to the incoming carry.
4. A carry can be produced by either half adder, but never by both, so a plain OR is enough to combine them.
5. Here is the full adder truth table, split so no table is wider than four columns.

6. In equations: SUM = A XOR B XOR Cin, and Cout = (A AND B) OR (Cin AND (A XOR B)).
7. Read the Cout column again: it is 1 whenever two or three of the inputs are
   1. Cout is a majority vote of three bits.
8. Now the 8-bit ripple-carry adder. Eight full adders in a line.

 Cin=0 -> [FA0] -c1-> [FA1] -c2-> [FA2] -c3-> [FA3] -c4->
       -> [FA4] -c5-> [FA5] -c6-> [FA6] -c7-> [FA7] -> Cout

 Each FAn also takes bit n of A and bit n of B, and
 produces bit n of the sum.

9. Worked sum. Add 109 and 46, which are 0110 1101 and 0010 1110 in binary.
10. Bit 0 is the rightmost. Here is the full carry trace.

 bit  A  B  Cin   SUM  Cout
  0   1  0   0     1     0
  1   0  1   0     1     0
  2   1  1   0     0     1
  3   1  1   1     1     1
  4   0  0   1     1     0
  5   1  1   0     0     1
  6   1  0   1     0     1
  7   0  0   1     1     0

11. Reading the SUM column from bit 7 down to bit 0 gives 1001 1011, which is
    155. And 109 plus 46 is 155. Correct.
12. Watch bit 2 and bit 3. Bit 2 generates a carry, which bit 3 receives, and bit 3 passes another one on. That is a carry rippling.
13. The worst case for rippling is 0111 1111 plus 0000 0001, which is 127 plus
    1. The carry born at bit 0 must travel through every one of the eight stages before the answer is right.

PLAIN5.6.4 what is really happening inside#

1. Every full adder in the chain starts computing the moment its inputs change. None of them waits for permission.
2. But seven of the eight are computing with a carry-in that has not settled yet, so seven of them are producing a wrong answer at first.
3. As the correct carry arrives at each stage in turn, that stage recomputes and its output may flip. The flipping travels left like a wave.
4. Those intermediate wrong values are called glitches. They are real voltage changes, they burn real power, and they are harmless as long as nothing reads the output too early.
5. The time to settle is roughly the delay of one stage’s carry path multiplied by the number of stages.
6. Double the width from 8 bits to 16 bits and you roughly double the delay. That is a terrible scaling law for a 64-bit machine.
7. The fix is to stop waiting. Notice that a stage does not need the actual carry to know how it will behave.
8. A stage generates a carry if both its bits are 1, no matter what comes in. Call that G.
9. A stage propagates a carry if exactly one of its bits is 1, meaning it will pass on whatever comes in. Call that P.
10. G and P can be computed for all 64 bits simultaneously, because they depend only on A and B and not on any carry.
11. Then the carry into any position is a single wide formula built from the G and P values below it, computed in a fixed small number of gate levels.
12. That is carry-lookahead. It trades a lot of extra gates for a delay that grows like the logarithm of the width instead of linearly.

TECHNICAL5.6.5 the engineer’s version#

1. The generate and propagate signals are G(i) = A(i) . B(i) and P(i) = A(i) XOR B(i). Some texts use P(i) = A(i) + B(i), which is equivalent for carry purposes but not for the sum.
2. The recurrence is C(i+1) = G(i) + P(i) . C(i).
3. Expanding for four bits gives the classic flat lookahead equation:

 C1 = G0 + P0.C0
 C2 = G1 + P1.G0 + P1.P0.C0
 C3 = G2 + P2.G1 + P2.P1.G0 + P2.P1.P0.C0
 C4 = G3 + P3.G2 + P3.P2.G1 + P3.P2.P1.G0 + P3.P2.P1.P0.C0

4. Every one of those is two gate levels after P and G are available, so a 4-bit block produces its carry-out in about three levels rather than eight.
5. Flat lookahead does not scale past about four bits, because the AND terms grow in both count and fan-in. Real designs build a tree of 4-bit blocks with block-level group generate and group propagate signals.
6. Gerald B. Rosenberger of IBM filed for a binary carry-lookahead adder in 1957 and received United States patent 2,966,305 in 1960. Konrad Zuse is believed to have used carry anticipation in the Z1 in the 1930s.
7. Weinberger and Smith published “A One-Microsecond Adder Using One-Megacycle Circuitry” in the IRE Transactions on Electronic Computers in 1956, which is the standard reference for the lookahead equations above.
8. Delay comparison for a 16-bit adder, counting gate levels:

9. Prefix adders treat carry generation as a parallel prefix problem. Kogge-Stone, from Peter Kogge and Harold Stone in 1973, has minimum depth and maximum wiring. Brent-Kung, from 1982, trades depth for far less wiring.
10. Sklansky and Han-Carlson sit between those two. Experts disagree on the best default: some favour Kogge-Stone for depth, others argue its wiring load makes Han-Carlson faster in practice at modern process nodes.
11. The 7483 and 74283 are 4-bit full adders with internal fast carry. The 74182 is a lookahead carry generator designed to sit above four 74181 ALU slices.
12. In Verilog you simply write the plus sign and let the synthesis tool choose the architecture, guided by your timing constraint:

module add8 (input  [7:0] a, b,
             input        cin,
             output [7:0] sum,
             output       cout);
  assign {cout, sum} = a + b + cin;
endmodule

WORDS5.6.6 remember these#

1. Half adder — adds two bits, no carry in — a circuit producing S = A XOR B and C = A AND B.
2. Full adder — adds three bits — a circuit producing sum and carry from A, B and a carry-in.
3. Ripple carry — each stage waits for the last — a linear-delay adder where carry-out chains into the next carry-in.
4. Carry generate — this column makes a carry regardless — G = A AND B.
5. Carry propagate — this column passes a carry through — P = A XOR B.
6. Carry-lookahead — work out all carries at once — a logarithmic-depth carry network computed from G and P without waiting.
7. Glitch — a wrong value on the way to the right one — a transient logic hazard caused by unequal path delays.

5.7 Subtracting without a subtractor#

PLAIN5.7.1 in simple words#

1. A computer does not contain a subtractor. It contains an adder, and it cheats.
2. To compute A minus B, it computes A plus the negative of B.
3. So the only question is how to represent a negative number in bits.
4. The scheme every modern machine uses is called two’s complement.
5. The rule to negate a number is: flip every bit, then add 1.
6. Take 5 in 8 bits: 0000 0101. Flip every bit: 1111 1010. Add 1: 1111 1011. That is minus 5.
7. To check it, add 5 and minus 5. 0000 0101 plus 1111 1011 is 1 0000 0000. The ninth bit falls off the end and you are left with zero. Correct.
8. The top bit acts as a sign flag. If it is 1, the number is negative.
9. In 8 bits the range is minus 128 to plus 127. There is one more negative value than positive, because zero uses up one of the non-negative slots.

PLAIN5.7.2 a picture in your head#

1. Think of a car odometer with only three digits, so it can show 000 to 999.
2. Wind it back one from 000 and it shows 999. So on that dial, 999 behaves exactly like minus one.
3. Add 5 to 999 and you get 1004, but the leading 1 cannot be shown, so the dial reads 004. And 5 minus 1 is 4. It worked.
4. Two’s complement is that same wrap-around idea with two digits per position instead of ten.
5. The bits that fall off the left end are simply discarded, and the arithmetic still comes out right.
6. Where this comparison breaks: on an odometer, everything above 500 is not automatically treated as negative. It is just a big number.
7. In two’s complement, the machine decides which half is negative by the top bit, and it is the instruction you choose that decides whether the same bits mean 200 or minus 56.

PLAIN5.7.3 a worked example#

1. Compute 45 minus 67 in 8 bits.
2. 45 is 0010 1101. 67 is 0100 0011.
3. Flip every bit of 67: 1011 1100.
4. Feed that to the adder together with 45, and set the carry-in to 1. The carry-in supplies the “add one” for free, with no extra gate.
5. 0010 1101 plus 1011 1100 plus 1 gives 1110 1010, with a carry-out of 0.
6. Read 1110 1010 as a signed value. The top bit is 1, so it is negative.
7. To read it, flip and add one: 0001 0101 plus 1 is 0001 0110, which is 22. So the answer is minus 22.
8. And 45 minus 67 is minus 22. Correct.
9. Here is the whole trick in one diagram. One control wire, called SUB, does everything.

   B7..B0 ---> [ 8 XOR gates, other input = SUB ] ---> B' bits
                                                        |
   A7..A0 ---------------------------------------+      |
                                                 v      v
                                          [ 8-BIT ADDER ]
                                                 ^
                              carry-in = SUB ----+

10. When SUB is 0, XOR with 0 leaves every B bit unchanged and the carry-in is
    0. The circuit computes A plus B.
11. When SUB is 1, XOR with 1 flips every B bit and the carry-in is 1. The circuit computes A minus B.
12. Cost of adding subtraction to an adder: eight XOR gates and one wire. That is the whole subtractor.

PLAIN5.7.4 what is really happening inside#

1. Two’s complement works because of arithmetic modulo 256 for 8 bits, or modulo 2 to the power 64 for 64 bits.
2. Flipping every bit of B gives 255 minus B, because the all-ones pattern is 255 and flipping is the same as subtracting from all ones.
3. Adding 1 gives 256 minus B.
4. So A plus the flipped B plus 1 equals A plus 256 minus B.
5. The 256 is exactly one more than the largest 8-bit value, so it appears only in the ninth bit position, which the hardware drops.
6. What is left on the wires is A minus B. The mathematics is exact, not an approximation.
7. Now, the hardware must also spot when the answer does not fit. There are two separate failure signals, and they are not the same thing.
8. Carry-out means the result was too big for the width, treating the numbers as unsigned. It is the ninth bit that fell off.
9. Overflow means the result was too big for the width, treating the numbers as signed. It is detected differently.
10. The signed overflow rule is short: overflow happens when the carry into the top bit differs from the carry out of the top bit.
11. In one XOR gate: V = C(n) XOR C(n-1).
12. A second way to say the same thing: overflow happens if two numbers of the same sign are added and the answer has the opposite sign.
13. Adding a positive and a negative number can never overflow, because the answer is always between the two inputs.

TECHNICAL5.7.5 the engineer’s version#

1. Two’s complement is the representation mandated by essentially every current general-purpose instruction set: x86-64, ARM AArch64, RISC-V and POWER.
2. Since the C23 standard, published in 2024, signed integers in C are required to use two’s complement. Before that, C permitted sign-magnitude and one’s complement too, though no mainstream compiler used them.
3. The asymmetry is real and it bites. In 8 bits, negating minus 128 gives back minus 128, because plus 128 does not exist. The same holds at every width.
4. In C, computing 0 minus INT_MIN, or INT_MIN divided by minus 1, is undefined behaviour. On x86-64 the IDIV instruction raises a divide-error exception, the same one as division by zero.
5. Worked signed overflow example: 100 plus 50 in 8 bits. 0110 0100 plus 0011 0010 gives 1001 0110.
6. As unsigned that is 150 and there was no carry-out, so the unsigned carry flag is 0.
7. As signed it is minus 106, which is wrong. The carry into bit 7 was 1 and the carry out of bit 7 was 0, so V = 1 XOR 0 = 1. Overflow is flagged.
8. Flag conventions differ, and this is a genuine trap when porting code.

9. This is a convention, not a standard. On ARM the C flag is the literal carry out of A plus NOT B plus 1. On x86 it is inverted before being stored.
10. RISC-V has no condition-code register by design. Comparison is done with instructions such as SLT and SLTU that write a 0 or 1 into a normal register, and branches compare two registers directly.
11. Tools to observe this: in GDB, “info registers eflags” on x86-64 shows CF, ZF, SF and OF. In LLDB, “register read cpsr” shows N, Z, C and V on ARM.
12. Compilers exploit signed overflow being undefined behaviour in C and C++ to optimize loops. Build with -fwrapv to force wrapping, or use -fsanitize=signed-integer-overflow to trap it at runtime.

WORDS5.7.6 remember these#

1. Two’s complement — flip the bits and add one — the radix complement representation where the top bit has weight minus 2 to the power n-1.
2. Sign bit — the top bit says positive or negative — bit n-1 of a two’s complement value.
3. Carry flag — a bit fell off the end, unsigned — the carry-out of the most significant adder stage, inverted after subtraction on x86.
4. Overflow flag — the signed answer is wrong — set when the carry into the sign bit differs from the carry out of it.
5. Modular arithmetic — numbers wrapping round a dial — arithmetic modulo 2 to the power n, which is what fixed-width binary hardware performs.
6. Undefined behaviour — the language makes no promise — a construct for which the C and C++ standards impose no requirements, permitting any result.

5.8 More building blocks#

PLAIN5.8.1 in simple words#

1. Beyond gates and adders there is a small set of standard parts. Every CPU is made mostly of copies of these.
2. A multiplexer is a chooser. It has many data inputs, a few select inputs, and one output. The select value picks which input reaches the output.
3. A demultiplexer is the reverse. One data input, many outputs, and the select value picks which output receives it.
4. A decoder turns a small binary number into one hot wire. Three input bits become eight output wires, exactly one of which is 1.
5. An encoder is the reverse of a decoder. One hot wire in, a binary number out.
6. A priority encoder is an encoder that copes when several inputs are 1 at once. It reports the highest-numbered one and ignores the rest.
7. A comparator takes two numbers and says whether they are equal, or which one is bigger.
8. A barrel shifter moves all the bits of a word left or right by any amount, in one step, with no looping.
9. A parity generator counts whether the number of 1 bits is odd or even. It is one XOR tree.

PLAIN5.8.2 a picture in your head#

1. Think of a railway station. A multiplexer is the points where many tracks merge into one platform, and a lever chooses which train comes through.
2. A demultiplexer is the points at the far end, where one track fans out to many platforms.
3. A decoder is the departure board lighting up exactly one platform number.
4. A priority encoder is the station controller when three trains all signal at once: the express goes first and the others wait.
5. A barrel shifter is the whole train being moved sideways onto a parallel track, all carriages at once, rather than shunted one carriage at a time.
6. Where this comparison breaks: trains physically travel and take time proportional to distance. In a multiplexer no data moves through the unused paths at all. The unselected inputs are simply blocked.
7. Also, a real multiplexer does not queue. If two inputs change, both are read continuously. Only one is passed on.

PLAIN5.8.3 a worked example#

1. A worked 3-to-8 decoder. Three inputs A2, A1, A0 and eight outputs Y0 to Y7.
2. The rule is: Y(n) is 1 when the input bits spell the number n in binary, and 0 otherwise. Exactly one output is ever 1. That is called one-hot.

3. Each output is a single 3-input AND gate over the inputs, with inverters where a 0 is required.

   Y0 = A2' . A1' . A0'
   Y1 = A2' . A1' . A0
   Y2 = A2' . A1  . A0'
   Y3 = A2' . A1  . A0
   Y4 = A2  . A1' . A0'
   Y5 = A2  . A1' . A0
   Y6 = A2  . A1  . A0'
   Y7 = A2  . A1  . A0

4. Cost: eight 3-input AND gates plus three inverters. Delay: two gate levels.
5. Check A2=1, A1=0, A0=1. Y5 needs A2 true, A1 false, A0 true. All hold, so Y5 = 1. Every other line has at least one term false, so all others are 0.
6. Now a 4-to-1 multiplexer with select bits S1 and S0.

   OUT = S1'.S0'.D0 + S1'.S0.D1 + S1.S0'.D2 + S1.S0.D3

7. Notice the four product terms are exactly the four decoder outputs. A multiplexer is a decoder whose one-hot lines gate the data through.
8. A 2-to-1 multiplexer is the smallest useful case: OUT = S’.A + S.B. It is the atom of all control logic in a CPU.

PLAIN5.8.4 what is really happening inside#

1. Where each part sits in a real CPU.
2. Multiplexers sit everywhere. In front of every register write port, choosing which value gets written.
3. In the forwarding paths of a pipeline, choosing whether an operand comes from the register file or straight from a later stage.
4. And at the program counter, choosing between the next sequential address and a branch target.
5. Decoders sit in the instruction decoder, turning an opcode field into control lines, and in the memory system, turning an address into one row select line inside a RAM array.
6. Demultiplexers sit on write paths, steering one result to one of many destination registers.
7. Priority encoders sit in the interrupt controller, choosing which of many simultaneous interrupt requests to serve first.
8. They also sit in a floating-point unit, finding the position of the highest set bit so a result can be normalized.
9. Comparators sit in branch units, in cache tag matching, and in address range checks in a memory protection unit.
10. A barrel shifter sits inside the ALU, so that shift and rotate instructions take one cycle instead of one cycle per bit position.
11. Parity generators sit on memory buses and on cache arrays, producing one extra check bit per byte or per word.
12. The honest version: a modern core has no part labelled “priority encoder”. It has a synthesized cloud of gates produced from a description of that behaviour. The names are how engineers think, not how silicon is drawn.

TECHNICAL5.8.5 the engineer’s version#

1. Sizes and costs of the standard blocks:

2. A barrel shifter is built as a chain of 2-to-1 multiplexer stages, one per bit of the shift amount. A 32-bit shifter needs five stages, shifting by 16, 8, 4, 2 and 1.
3. That gives logarithmic depth: shifting a 64-bit word by any amount takes six multiplexer stages, not 63 steps.
4. A funnel shifter is a barrel shifter fed by two concatenated words. It implements rotate, and on x86 the SHLD and SHRD double-precision shift instructions.
5. Classic discrete parts, all from the 7400 family:

6. The 74280 is a 9-bit odd and even parity generator and checker. Parity over n bits is an XOR tree of depth log base 2 of n, so 64-bit parity is six levels deep.
7. x86-64 has a POPCNT instruction that counts set bits, and a parity flag in EFLAGS covering only the low 8 bits of a result. That 8-bit limit is a hangover from the 8086 of 1978.
8. An equality comparator is an XNOR per bit followed by a wide AND. A magnitude comparator is usually a subtraction whose sign and zero flags are read, which is why CMP on x86 is SUB with the result discarded.
9. One-hot encoding is standard for finite state machines on FPGAs, because flip-flops are plentiful and the next-state logic becomes shallow. On ASICs, binary encoding is usually preferred to save flip-flops. This is a technology-dependent trade-off, not a rule.

WORDS5.8.6 remember these#

1. Multiplexer — a chooser — a combinational selector routing one of 2 to the power n data inputs to a single output under n select bits.
2. Demultiplexer — a router — the inverse of a multiplexer, steering one input to one of many outputs.
3. Decoder — small number in, one hot wire out — an n-to-2-to-the-n one-hot converter.
4. Priority encoder — reports the most important active input — an encoder that resolves multiple simultaneous requests by fixed rank, usually with a valid output.
5. Barrel shifter — shifts any distance in one step — a logarithmic-depth multiplexer network performing arbitrary shifts and rotates.
6. One-hot — exactly one wire is 1 — an encoding using one signal per state or value.
7. Parity — odd or even count of 1 bits — the XOR reduction of a word, used as a single-bit error detection code.

5.9 The ALU#

PLAIN5.9.1 in simple words#

1. An ALU is the arithmetic and logic unit. It is the part of a CPU that actually computes things.
2. It is simpler than people expect. You build every operation you want, all in parallel, all at once.
3. Then you put a multiplexer at the end and use a control code to pick which answer to keep.
4. So the adder is always adding. The AND unit is always ANDing. The shifter is always shifting. Only one result is chosen.
5. That sounds wasteful, and it is. But it is fast, because no operation waits for any other to finish.
6. The control code that selects the operation comes from the instruction being executed. It is called the ALU control, or the opcode.
7. Besides the result, the ALU also produces a few single-bit facts about that result. Those are called flags or condition codes.
8. The four classic flags are zero, carry, sign and overflow.

PLAIN5.9.2 a picture in your head#

1. Think of a kitchen where four cooks each prepare a different dish from the same two ingredients, all at the same time.
2. When the order ticket arrives it does not say “start cooking”. It says “serve dish number three”.
3. All four dishes were already made. Three are thrown away.
4. Serving is instant because the work was done speculatively, in parallel.
5. Where this comparison breaks: throwing away three meals costs real food, and in an ALU the unused operations cost real energy every cycle.
6. That is why modern designs add clock gating and operand isolation, which hold the inputs of unused units steady so those gates never switch and never burn power.
7. So the picture is right about the timing and slightly wrong about the cost.

PLAIN5.9.3 a worked example#

1. Here is the shape of a small ALU.

   A ---+--> [ ADDER / SUBTRACTOR ] ---+
        |                              |
        +--> [ LOGIC: AND OR XOR NOT ]-+--> [ MUX ] --> RESULT
        |                              |        ^
   B ---+--> [ BARREL SHIFTER ] -------+        |
                                            OPCODE (3 bits)

   flags out:  Z (zero)  C (carry)  N (sign)  V (overflow)

2. A control table for an 8-operation ALU with a 3-bit opcode.

3. Note that opcode bit 0 doubles as the SUB control wire from section 5.7, feeding the eight XOR gates and the adder carry-in. One bit, two jobs.
4. Now the four flags, which are computed from the result and from the adder.

5. Z is a wide NOR gate over all result bits. For 8 bits it is one NOR of eight inputs, or a tree of smaller NORs.
6. N is a wire. It is literally bit 7 of the result, with no gate at all.
7. C comes straight from the adder’s carry-out.
8. V is one XOR gate: V = C(8) XOR C(7).
9. Worked case. Opcode 001, A = 45, B = 67, as in section 5.7. Result is 1110 1010.
10. Z is 0, because the result is not all zeros. N is 1, because bit 7 is 1. C is 0, meaning a borrow occurred on x86 convention. V is 0, because minus 22 fits fine in 8 bits.

PLAIN5.9.4 what is really happening inside#

1. Not every instruction updates every flag, and the rules are precise. Getting them wrong is a classic source of bugs.
2. On x86-64, arithmetic instructions write the full set. Logic instructions write some and force others to zero.
3. Move instructions write none at all, which is why you can load a value between a compare and a conditional jump without destroying the comparison.

4. INC and DEC deliberately leave the carry flag alone so that they can be used inside a multi-word addition loop without destroying the running carry.
5. SHL and SHR put the last bit shifted out into the carry flag, and set OF only when the shift count is exactly 1.
6. A shift by zero on x86 leaves all flags completely unchanged, which is a genuine special case in the specification and a well-known trap.
7. The order of events in one ALU operation: operands arrive on the A and B buses, every unit computes, the multiplexer selects, the flags are derived from that result, and the destination register captures it at the next edge.
8. Nothing is sequenced inside that. It is one settling of combinational logic.

TECHNICAL5.9.5 the engineer’s version#

1. The 74181 was introduced by Texas Instruments in February 1970 and was the first complete ALU on a single chip.
2. It is a 4-bit slice performing 16 arithmetic and 16 logic functions, selected by four function lines S0 to S3, a mode line M and a carry-in Cn.
3. Standard versions completed an operation in 22 nanoseconds. The 74S181 did it in 11 nanoseconds and the 74F181 in 7 nanoseconds.
4. It was used in the Data General Nova 1200, the Digital Equipment PDP-11 series, the Xerox Alto and the VAX-11/780.
5. Four 74181 slices plus one 74182 lookahead carry generator gave a 16-bit ALU. Sixteen 74S181 slices plus five 74S182 parts gave 64 bits.
6. Modern cores have several ALUs. Intel Skylake, released in August 2015, has four integer execution ports, p0, p1, p5 and p6, each able to retire a simple ALU operation every cycle.
7. That is why the reciprocal throughput of ADD on Skylake is 0.25 cycles: four independent adds can issue per cycle even though each takes one cycle of latency.
8. Condition-code architectures differ sharply. x86-64 and AArch64 have a flags register. RISC-V has none. MIPS has none for integers.
9. Flags are expensive in an out-of-order core, because the flags register is a single hot dependency that every arithmetic instruction writes. Designs cope by renaming the flags register and by splitting it into independently renamed groups.
10. The x86 partial-flag problem is real. INC writes some flags and leaves CF, so a later instruction reading all flags may need to merge two sources. Intel added a merging micro-operation for it, and compilers prefer ADD 1.
11. To observe flags: in GDB use “info registers eflags”; on AArch64 read the NZCV field of CPSR or PSTATE. In a disassembly, look for SETcc, CMOVcc and Jcc instructions, which are the consumers.

WORDS5.9.6 remember these#

1. ALU — the part that computes — the arithmetic and logic unit, a combinational block selecting among parallel functional results.
2. Opcode — the code that says which operation — the instruction field driving the ALU function select multiplexer.
3. Flag — a one-bit fact about the result — a condition code recording zero, carry, sign, overflow or parity.
4. Zero flag — the answer was all zeros — the NOR reduction of the result bus.
5. Condition code register — where the flags live — EFLAGS or RFLAGS on x86, NZCV in PSTATE on AArch64.
6. Operand isolation — stop unused units switching — holding inputs of unselected functional units constant to save dynamic power.
7. Bit slice — one chip handling four bits — a design style where identical narrow ALU chips are cascaded to build a wider machine.

5.10 Multiply and divide in hardware#

PLAIN5.10.1 in simple words#

1. There is no such thing as a multiply gate. Multiplication has to be built out of adding and shifting.
2. The school method works in binary and is much easier there, because every digit of the multiplier is either 0 or 1.
3. For each 1 bit in the multiplier, you add a shifted copy of the multiplicand. For each 0 bit, you add nothing.
4. So multiplying two 32-bit numbers means adding up to 32 shifted copies.
5. Doing that one step at a time takes 32 clock cycles. That is the slow way, called shift-and-add.
6. The fast way is to build all 32 shifted copies at once, in wires, and then add them all together with a tree of adders.
7. Division is worse. You cannot know a quotient digit until you have tested it.
8. So division is inherently a guess-and-check loop, and that is why it is the slowest common instruction on every processor.

PLAIN5.10.2 a picture in your head#

1. Multiplying by hand on paper is writing several rows and then adding the column totals.
2. A hardware array multiplier is that same sheet of paper, made of wire, with every row present at once.
3. Adding the rows is the slow part. Doing it one row at a time is like adding a long column top to bottom.
4. A Wallace tree instead pairs rows off in a knockout tournament: 32 rows become 22, then 15, then 10, and so on down to 2.
5. Because the tournament halves the field each round, the number of rounds grows like the logarithm of the number of rows.
6. Where this comparison breaks: in a knockout tournament the losers are eliminated. In a Wallace tree nothing is lost. Three rows are merged into two rows with the same total, using carry-save adders.
7. Nothing is thrown away. The value is preserved exactly at every level.

PLAIN5.10.3 a worked example#

1. Multiply 13 by 11 in binary. 13 is 1101 and 11 is 1011.

        1 1 0 1        (13)
   x    1 0 1 1        (11)
   -----------------
        1 1 0 1        bit 0 of 11 is 1, shift 0
      1 1 0 1          bit 1 of 11 is 1, shift 1
    0 0 0 0            bit 2 of 11 is 0, shift 2
  1 1 0 1              bit 3 of 11 is 1, shift 3
  -----------------
  1 0 0 0 1 1 1 1      = 143

2. And 13 times 11 is 143. Correct.
3. Note the product of two 4-bit numbers needs 8 bits. In general n bits times n bits needs 2n bits, which is why x86 MUL writes its result across two registers.
4. Restoring division of 13 by 3, using 4-bit values. The rule each step is: shift the remainder left, bring down the next bit, try subtracting the divisor.
5. If the subtraction goes negative, undo it and write a 0 quotient bit. If it does not, keep it and write a 1.

  step  rem  bring  trial rem-3   keep?  quotient bit
   1     0     1      1-3 = -2      no        0
   2     1     1      3-3 =  0     yes        1
   3     0     0      0-3 = -3      no        0
   4     0     1      1-3 = -2      no        0

6. Quotient 0100 is 4, remainder 1. And 13 divided by 3 is 4 remainder 1. Correct.
7. The word restoring means undoing the subtraction whenever it went negative. That undo is a whole extra add, which is pure waste.
8. Non-restoring division avoids the undo by allowing negative partial remainders and correcting at the end. It costs one add-or-subtract per bit instead of up to two.

PLAIN5.10.4 what is really happening inside#

1. Booth’s algorithm speeds up multiplication by noticing that a long run of 1s can be handled with one subtraction and one addition.
2. Multiplying by 0111 1111, which is 127, is the same as multiplying by 128 and then subtracting 1 copy. Two operations instead of seven.
3. Modified Booth encoding, also called radix-4 Booth, looks at three multiplier bits at a time and emits one partial product per two bits.
4. That halves the number of rows to add before the tree even starts. It is used in essentially every production multiplier.
5. The adder tree uses carry-save adders. A carry-save adder is just a full adder with its carry not connected onward, so it takes three numbers in and produces two numbers out, with no carry rippling at all.
6. Only the very last step, turning the final two numbers into one, needs a real carry-propagating adder. That is where a fast prefix adder is used.
7. Division has no such trick, because the quotient bits are not known in advance. Each digit depends on the remainder produced by the previous digit.
8. SRT division, named after Sweeney, Robertson and Tocher, speeds this up by guessing several quotient bits at a time from a small lookup table and tolerating a slightly wrong guess.
9. That lookup table is where Intel’s famous 1994 bug lived.

TECHNICAL5.10.5 the engineer’s version#

1. Andrew Donald Booth devised his signed multiplication technique in 1950 at Birkbeck College, London, while working on crystallography. It appeared as “A Signed Binary Multiplication Technique” in the Quarterly Journal of Mechanics and Applied Mathematics, volume 4, part 2.
2. Chris Wallace published “A suggestion for a fast multiplier” in the IEEE Transactions on Electronic Computers in February 1964. A Wallace tree has depth of order log n and places multiplication in complexity class NC1.
3. Luigi Dadda proposed the Dadda multiplier in 1965. It reduces later and uses fewer full adders than a Wallace tree for the same delay, at the cost of a slightly wider final adder.
4. An n by n array multiplier has delay of order n and area of order n squared. A Wallace or Dadda tree has delay of order log n and similar area.
5. Measured Intel Skylake figures, from the uops.info instruction database. Latency is in clock cycles; reciprocal throughput is cycles between independent issues, so smaller is better.

6. Floating-point division on the same core: DIVSS, single precision, latency up to 11 with reciprocal throughput 3.00; DIVSD, double precision, latency up to 13 with reciprocal throughput 4.00.
7. The legacy x87 FDIV on Skylake is approximately 14 to 16 cycles, per Agner Fog’s instruction tables. Treat that as approximate; it is not listed in the same form by uops.info. Compilers targeting x86-64 emit DIVSD instead.
8. Integer division latency is data-dependent, which is why DIV r64 is a range and not a number. The hardware exits early when the operands are small. ADD and IMUL are fixed-latency.
9. Division has improved sharply in recent parts:

10. This is why compilers replace division by a constant with a multiply by a magic reciprocal and a shift. Look for that pattern in any optimized build: a division by 10 becomes an IMUL and an SHR.
11. The Pentium FDIV bug: Thomas R. Nicely of Lynchburg College noticed inconsistencies on 13 June 1994, confirmed them on 19 October 1994 and reported them to Intel on 24 October 1994.
12. The cause was five cells missing from an SRT quotient-digit lookup table that should have held 1,066 populated entries. Intel announced full replacement on 20 December 1994, and took a pre-tax charge of 475 million US dollars.
13. The lesson engineers took from it: division hardware is intricate, and verifying it is now done with formal methods rather than test vectors alone.

WORDS5.10.6 remember these#

1. Shift-and-add — the school method in binary — iterative multiplication adding a shifted multiplicand per set multiplier bit.
2. Partial product — one shifted row before adding — the term contributed by one multiplier bit or Booth group.
3. Booth encoding — handle runs of 1s in one step — a signed-digit recoding of the multiplier that halves the partial product count at radix 4.
4. Carry-save adder — three numbers in, two out — a full adder array with carries kept as a separate vector rather than propagated.
5. Wallace tree — a knockout tournament of adders — a logarithmic-depth partial product reduction network.
6. Restoring division — undo the subtraction if it went negative — a one-bit per cycle division algorithm with a correction step.
7. SRT division — guess several quotient bits from a table — the radix-4 or higher division method named after Sweeney, Robertson and Tocher.

5.11 Propagation delay and the critical path#

PLAIN5.11.1 in simple words#

1. A gate does not answer instantly. It takes a small, fixed amount of time to change its output after its inputs change.
2. That time is called propagation delay, or gate delay.
3. If you wire three gates in a line, the delays add up. Three gates in series take three gate delays.
4. A circuit has many paths from its inputs to its outputs. Each path has its own total delay.
5. The longest of all those paths is called the critical path.
6. The whole circuit is not finished until the critical path is finished. The fast paths finished long ago and are just waiting.
7. So the critical path sets the maximum clock speed. Nothing else does.
8. To make a circuit faster you must shorten its longest path. Speeding up anything else changes nothing at all.

PLAIN5.11.2 a picture in your head#

1. Think of a group hike where everyone must reach the hut before dinner is served.
2. Dinner starts when the last walker arrives, not when the first does.
3. Making the fastest walker faster does nothing. Dinner is still at the same time.
4. Only helping the slowest walker moves dinner earlier.
5. That slowest walker is the critical path, and finding them is the whole job of a timing analysis tool.
6. Once you speed that walker up, someone else becomes the slowest, and you repeat.
7. Where this comparison breaks: walkers are independent, but circuit paths share gates. Enlarging a gate to speed up one path slows another, because a bigger gate is a bigger load on whatever feeds it.
8. That coupling is why timing closure is an iterative struggle and not a single calculation.

PLAIN5.11.3 a worked example#

1. We will compute the maximum clock frequency of the 8-bit ripple-carry adder from section 5.6, using assumed but realistic delay figures.
2. Assumptions, which stand in for a slow discrete logic family:

3. The register setup time is 0.5 ns. Clock skew is assumed to be zero.
4. Recall the full adder equations: SUM = A XOR B XOR Cin, and Cout = (A AND B) OR (Cin AND (A XOR B)).
5. Delay from carry-in to carry-out of one stage: AND then OR, so 2.0 plus 2.0 equals 4.0 ns.
6. Delay from A or B to carry-out of the first stage: XOR then AND then OR, so 3.0 plus 2.0 plus 2.0 equals 7.0 ns.
7. Delay from carry-in to that stage’s sum bit: one XOR, so 3.0 ns.
8. Now trace the critical path across all eight bits.

   A0/B0 -> C1                     7.0 ns
   C1 -> C2 -> ... -> C8           7 hops x 4.0 = 28.0 ns
   total A0/B0 -> Cout             35.0 ns

   alternative ending:
   A0/B0 -> C7                     7.0 + 6 x 4.0 = 31.0 ns
   C7 -> S7 (one XOR)              3.0 ns
   total A0/B0 -> S7               34.0 ns

9. The critical path is the longer of the two, 35.0 ns.
10. Now the clock period. It must fit three things: the register’s own delay, the logic, and the setup time of the capturing register.

   T_min = clock-to-output + critical path + setup
   T_min = 1.0 + 35.0 + 0.5 = 36.5 ns

   f_max = 1 / 36.5 ns = 27.4 MHz

11. So this adder cannot be clocked faster than about 27 MHz, no matter how good the rest of the design is.
12. Now replace it with two 4-bit carry-lookahead blocks. Generating P and G takes one XOR, 3.0 ns. Each block’s carry-out is then one AND plus one OR, 4.0 ns.
13. Carry out of the first block arrives at 3.0 plus 4.0 equals 7.0 ns. Carry into bit 7 arrives 4.0 ns later, at 11.0 ns. The final sum XOR adds 3.0 ns, giving 14.0 ns. Allow 15.0 ns with margin.

   T_min = 1.0 + 15.0 + 0.5 = 16.5 ns
   f_max = 1 / 16.5 ns = 60.6 MHz

14. The same arithmetic, more than twice as fast, purely by shortening the longest path.

PLAIN5.11.4 what is really happening inside#

1. Setup time is how long before the clock edge the data must already be stable at the register input.
2. Hold time is how long after the clock edge the data must stay stable.
3. Setup violations are fixed by slowing the clock down. Hold violations are not. A hold violation means a path is too fast, and slowing the clock does not help at all.
4. Hold violations are fixed by inserting delay, usually pairs of buffers, into the offending path.
5. If either is violated, the register can enter a state that is neither 0 nor 1 for an unpredictable time. That is called metastability.
6. Chapter 6 covers clocks, registers, setup, hold and metastability properly. Here you only need the one idea that the longest path sets the speed.
7. One more honesty point. Gate delay is not a single number. It depends on temperature, on supply voltage, and on random manufacturing variation.
8. So every real timing figure comes as a set of corners: slow-slow at high temperature and low voltage, fast-fast at low temperature and high voltage, and typical in between.
9. A design must pass setup checks in the slow corner and hold checks in the fast corner. Both, always.

TECHNICAL5.11.5 the engineer’s version#

1. Propagation delay is measured between 50 percent supply crossings, from input transition to output transition. Rise and fall delays differ and are listed separately as tPLH and tPHL.
2. Real 2-input NAND propagation delays across the 7400 family, showing sixty years of progress:

3. The 74HC00 datasheet limit is 15 ns maximum at 6 volts with a 50 picofarad load. Datasheet maxima are guaranteed numbers; typicals are not.
4. Inside a modern chip, gate delays are in picoseconds, not nanoseconds. A fan-out-of-four inverter delay is roughly 5 to 15 picoseconds at leading process nodes, which is why cores run at several gigahertz.
5. The setup-time equation used by every static timing analysis tool is:

 T_clk >= t_cq + t_logic_max + t_setup + t_skew_uncertainty

6. And the hold-time check, which does not involve the clock period at all:

 t_cq + t_logic_min >= t_hold + t_skew

7. Static timing analysis, or STA, checks every path in a design against these two inequalities without simulating any vectors. Tools: Synopsys PrimeTime, Cadence Tempus, and the open-source OpenSTA.
8. Slack is the margin on a path: required arrival time minus actual arrival time. Negative slack is a violation. Worst negative slack, WNS, is the headline number a designer watches.
9. Logical effort, the design method published by Ivan Sutherland, Bob Sproull and David Harris in their 1999 book “Logical Effort”, gives a systematic way to size gates along a path for minimum delay.
10. Process, voltage and temperature corners are usually enumerated as SS, TT and FF for slow, typical and fast silicon, combined with voltage and temperature extremes. A modern signoff may check dozens of corner and mode combinations.

WORDS5.11.6 remember these#

1. Propagation delay — how long a gate takes to answer — the 50 percent to 50 percent input-to-output transition time.
2. Critical path — the slowest route through the logic — the timing path with the largest delay, which bounds the clock period.
3. Slack — how much margin a path has — required arrival time minus actual arrival time, negative meaning a violation.
4. Setup time — data must be ready before the edge — the minimum stable time at a register input preceding the active clock edge.
5. Hold time — data must stay put after the edge — the minimum stable time following the active clock edge.
6. Static timing analysis — checking speed without simulating — exhaustive path-based timing verification against setup and hold constraints.
7. PVT corner — the worst case combination — a specified process, voltage and temperature condition at which timing must be met.

5.12 Why floating point maths is not exact#

PLAIN5.12.1 in simple words#

1. Type 0.1 plus 0.2 into almost any programming language and you get 0.30000000000000004, not 0.3.
2. This is not a bug in the language. It is not a bug in the processor. It is the direct consequence of building numbers out of a fixed number of bits.
3. In base ten, one third cannot be written exactly. It is 0.3333 forever, and you must stop somewhere.
4. In base two, one tenth cannot be written exactly either. It is 0.0001100110011 with 0011 repeating forever.
5. The hardware has room for 53 significant bits. It stores the closest value it can and throws the rest away.
6. So the value stored for 0.1 is not 0.1. It is very slightly more than 0.1.
7. The same is true for 0.2. Add the two slightly wrong values and the errors do not cancel. They add up.
8. The result is slightly more than 0.3, and it is a different bit pattern from the closest value to 0.3. So the comparison fails.
9. Numbers like 0.5, 0.25 and 0.75 are exact, because they are sums of powers of two. Only fractions whose denominator is a power of two are exact.

PLAIN5.12.2 a picture in your head#

1. Imagine a ruler marked only in halves, quarters, eighths, sixteenths and so on, down to a very fine division.
2. Every mark on that ruler is a number the computer can hold exactly.
3. Now try to measure one tenth of the ruler’s length. There is no mark there. There never will be, however fine you make the divisions.
4. So you pick the nearest mark. That is what rounding to 53 bits does.
5. Measure a tenth twice and add the two nearest marks. The two small errors both pointed the same way, so the total is a little further off.
6. Where this comparison breaks: the marks on a real ruler are evenly spaced. Floating-point marks are not.
7. Near zero the marks are extremely close together. Near very large values they are far apart. The spacing doubles every time the exponent increases by one.
8. That is what floating means. The point moves so that you always get about 16 significant decimal digits, whether the number is tiny or huge.

PLAIN5.12.3 a worked example#

1. Here are the exact values a 64-bit double actually holds. These are not approximations of the stored values. They are the stored values, written out in full decimal.

 stored for 0.1:
   0.1000000000000000055511151231257827021181583404541015625

 stored for 0.2:
   0.200000000000000011102230246251565404236316680908203125

 exact sum of those two:
   0.3000000000000000444089209850062616169452667236328125

 nearest double to 0.3:
   0.299999999999999988897769753748434595763683319091796875

2. The sum lands on a different mark from the one 0.3 lands on. That is why the equality test is false.
3. Printed with the shortest string that round-trips, that sum shows as 0.30000000000000004. The extra digits are not noise. They are the true value.

>>> 0.1 + 0.2
0.30000000000000004
>>> 0.1 + 0.2 == 0.3
False
>>> from decimal import Decimal
>>> Decimal(0.1)
Decimal('0.1000000000000000055511151231257827021181583404541015625')

4. Now the same idea in hardware terms. A double has one sign bit, 11 exponent bits and 52 stored fraction bits.
5. The 53rd significant bit is implied. For normal numbers there is always a leading 1 that does not need storing, which buys one free bit of precision.
6. 0.1 in binary is 1.100110011001100… times 2 to the power minus 4, with 1001 repeating.
7. The hardware keeps 53 bits of that and rounds the rest. Rounding up here, which is why the stored value is slightly too big.

PLAIN5.12.4 what is really happening inside#

1. Watch what the adder actually does when it is handed the two stored values.
2. Step 1, align. The two numbers have different exponents, minus 4 and minus 3. The smaller one is shifted right by one bit so the binary points line up.
3. That shift can push bits off the right-hand end straight away. They are not lost yet, because the hardware keeps a few extra bits for exactly this reason.
4. Step 2, add. The two 53-bit fractions go into an ordinary integer adder, the same kind built in section 5.6. There is nothing special about it.
5. Step 3, normalize. Shift the result so the leading bit is a 1 again, and adjust the exponent to match. That shift uses a barrel shifter and a priority encoder to find the leading 1.
6. Step 4, round. The result is now wider than 53 bits, so it must be cut down. The default rule is round to nearest, ties to even.
7. That rounding step is where the error is created. It is a deliberate, specified, deterministic operation, not an accident.
8. The three extra bits the hardware carries through the alignment are called guard, round and sticky. The sticky bit records whether anything non-zero fell off the end.
9. Without those three bits, results would be measurably worse. With them, the result is provably the correctly rounded value of the exact sum.
10. The honest version: the hardware is not sloppy. Every basic floating-point operation is required to give the exact result rounded once. The error you see is the minimum possible error for the format.

TECHNICAL5.12.5 the engineer’s version#

1. The format is IEEE 754 binary64, universally called double. It was first standardized as IEEE 754-1985, revised as IEEE 754-2008 and again as IEEE 754-2019.

2. Precision is 53 bits, which is about 15.95 decimal digits. Machine epsilon for binary64 is 2 to the power minus 52, roughly 2.22 times 10 to the power minus 16.
3. The bit patterns for the worked example, as 64-bit hexadecimal:

 0.1              = 3FB999999999999A
 0.2              = 3FC999999999999A
 0.3              = 3FD3333333333333
 0.1 + 0.2        = 3FD3333333333334

4. The two results differ in the final hexadecimal digit only. That is a difference of one unit in the last place, written 1 ulp.
5. IEEE 754 requires that add, subtract, multiply, divide and square root be correctly rounded: the result must equal the exact mathematical result rounded once to the destination format.
6. Five rounding modes are defined. The default is roundTiesToEven. The others are roundTiesToAway, roundTowardPositive, roundTowardNegative and roundTowardZero.
7. Correct rounding is not required for transcendental functions such as sine and exponential. Those are library code, and different libraries give slightly different answers. That is permitted by the standard.
8. Floating-point addition is commutative but not associative. Changing the grouping changes the result, which is why compilers may not reorder floating-point sums unless you pass -ffast-math and accept the consequences.
9. Practical rules for engineers: never test floating-point values with equality for computed results. Compare against a tolerance, or scale to integers, or use a decimal type.
10. For money, use integers of the smallest unit, or a decimal library. Python’s decimal module, Java’s BigDecimal and the SQL NUMERIC type all exist for this reason.
11. Fused multiply-add, or FMA, computes a times b plus c with a single rounding at the end instead of two. It was added to x86 as FMA3 with Intel Haswell in 2013 and is standard on AArch64.
12. Tools to observe this: printf with “%.20f” in C, Python’s decimal.Decimal constructor applied to a float, and the online notion of shortest round-trip printing implemented by repr in Python 3 and by Double.toString in Java.

WORDS5.12.6 remember these#

1. Floating point — the point moves to keep precision — a sign, exponent and significand representation of the form s times m times 2 to the power e.
2. Significand — the digits of the number — the 53-bit mantissa of binary64, with one bit implied for normal values.
3. Rounding — cutting to the bits you have — mapping an exact result to the nearest representable value under a specified rule.
4. ULP — one step on the ruler — unit in the last place, the gap between adjacent representable numbers at a given magnitude.
5. Machine epsilon — the smallest relative step — 2 to the power minus 52 for binary64, about 2.22 times 10 to the power minus 16.
6. Guard, round and sticky — the three spare bits — extra precision retained during alignment so the final rounding is correct.
7. IEEE 754 — the rule book — the standard defining binary and decimal floating-point formats, operations and rounding, current edition 2019.

5.98 Common wrong ideas#

1. Wrong: a gate passes the input current through to the output. Right: a gate reads its inputs and drives a fresh output from its own power supply, which is why signals do not fade along a chain.
2. Wrong: AND and OR are the basic gates. Right: in CMOS, NAND and NOR are the cheap four-transistor primitives, and AND and OR are each one of those plus an inverter, costing six transistors.
3. Wrong: XOR is just another basic gate like AND. Right: XOR has no simple series and parallel transistor form, so it costs 8 to 12 transistors and is noticeably slower, which matters because adders are mostly XOR.
4. Wrong: a computer contains a subtractor circuit. Right: it contains an adder, plus one XOR gate per bit and one control wire, and subtraction is addition of the two’s complement.
5. Wrong: the carry flag and the overflow flag mean the same thing. Right: carry means the unsigned result did not fit, overflow means the signed result did not fit, and either can be set without the other.
6. Wrong: making any gate faster makes the circuit faster. Right: only the critical path matters, so speeding up a gate that is not on the longest path changes the maximum clock frequency by exactly nothing.
7. Wrong: a Karnaugh map gives the fastest circuit. Right: it gives a small two-level expression, but a shallower circuit with more gates is often faster, and synthesis tools optimize for timing, not gate count.
8. Wrong: 0.1 plus 0.2 not equalling 0.3 is a rounding bug in the language. Right: it is the specified, correct behaviour of IEEE 754 binary64, because one tenth has no exact binary representation at any finite width.
9. Wrong: division is slow because it is complicated to write. Right: it is slow because each quotient digit depends on the remainder from the previous one, so it cannot be fully parallelized the way multiplication can.
10. Wrong: universality means NAND is the best gate for every job. Right: universality says NAND is sufficient, not optimal, and real designs pick whichever library cell is cheapest for each specific function.

5.99 Chapter summary in 20 lines#

1. Boolean algebra has two values, 1 and 0, and three operations, AND, OR and NOT, published by George Boole in 1847 and 1854.
2. Claude Shannon’s MIT master’s thesis, submitted on 10 August 1937, showed that relay switching circuits obey exactly those rules.
3. Inside a chip, 1 and 0 are two voltage bands, and the assignment of high to 1 is a convention called positive logic.
4. A CMOS gate has a PMOS pull-up network and a complementary NMOS pull-down network, and exactly one of them conducts at a time.
5. An inverter costs 2 transistors, a 2-input NAND or NOR costs 4, and an AND or OR costs 6 because it is a NAND or NOR plus an inverter.
6. Series transistors give AND-like behaviour and parallel transistors give OR-like behaviour, and CMOS gates are naturally inverting.
7. The seven gates are AND, OR, NOT, NAND, NOR, XOR and XNOR; XOR means exactly one, XNOR means the same, NAND means not both, NOR means neither.
8. NAND alone is functionally complete, needing 1 gate for NOT, 2 for AND, 3 for OR and 4 for XOR; NOR alone is complete too.
9. Fabs favour NAND because its series stack is NMOS, and electron mobility is two to three times higher than hole mobility.
10. Any truth table becomes a sum of products, and a Karnaugh map shrinks it by grouping adjacent 1s in Gray-code order.
11. De Morgan’s two laws, provable in four rows each, say that not-both equals either-missing and neither equals both-missing.
12. A half adder is one XOR and one AND; a full adder is two half adders and an OR, giving sum and a majority-vote carry.
13. An 8-bit ripple-carry adder is eight full adders in a chain, and its speed is set by the carry travelling from bit 0 to bit 7.
14. Carry-lookahead computes generate and propagate for every bit at once, turning linear carry delay into logarithmic delay.
15. Subtraction is addition of the two’s complement: invert every bit of B and set the adder carry-in to 1, costing eight XOR gates.
16. Carry means the unsigned answer overflowed; signed overflow is the XOR of the carry into and out of the top bit.
17. Multiplexers, decoders, priority encoders, comparators, barrel shifters and parity trees are the standard blocks a CPU is assembled from.
18. An ALU computes every operation in parallel and picks one with a multiplexer driven by the opcode, then derives the Z, C, N and V flags.
19. Multiplication is shift-and-add accelerated by Booth encoding and a Wallace tree; division is a guess-and-check loop and is the slowest common instruction, at 35 to 90 cycles for DIV r64 on Intel Skylake.
20. The critical path sets the clock, and rounding a 53-bit significand is why 0.1 plus 0.2 gives 0.30000000000000004 on every IEEE 754 machine.