From a specification to a circuit
A combinational circuit is a network of gates with no loops: its outputs depend only on its present inputs. Adders, comparators, decoders, the arithmetic logic unit (ALU) at the heart of a processor, the logic that turns a key code into a character on a display: all combinational. The previous lesson, Logic gates and Boolean algebra, gave you the gates and the algebra. This one is about design: given what a circuit must do, find a good circuit that does it.
"Good" has three measures that pull against each other. Area: fewer and smaller gates cost less silicon or fewer FPGA resources. Delay: the slowest path from an input to an output limits the clock rate. Power: every gate that switches spends energy, and so does every glitch. In industry a synthesis tool does most of the searching, so why learn to do it by hand? Because a designer who knows what the tool is doing can read its reports, write descriptions it can optimise, spot when it has been asked something impossible, and fix the problems tools do not see, such as the glitches later in this lesson.
Canonical forms and implicants
Number the rows of an -input truth table to by reading the inputs as a binary number, first input most significant.
Definition— Minterm, maxterm, canonical forms
A minterm is an AND of all inputs, each complemented or not, that is 1 on exactly one row: for inputs , row 5 () has minterm . A maxterm is an OR of all inputs that is 0 on exactly one row: . Every function is the OR of the minterms of its 1-rows, its canonical sum of products, written ; and the AND of the maxterms of its 0-rows, its canonical product of sums, .
The three-input majority function of the previous lesson is . Canonical forms are unique, which makes them good for comparing functions, but wasteful as circuits: majority needs four 3-input ANDs in canonical form, against three 2-input ANDs as .
Often some input combinations can never happen, or their output does not matter. These are don't-cares, written : the designer may choose 0 or 1 for each, whichever makes the circuit smaller.
Definition— Implicant, prime implicant, essential prime implicant
A product term is an implicant of if wherever (counting don't-care rows as allowed). It is a prime implicant if removing any literal from it stops it being an implicant: it cannot be made any bigger. A prime implicant is essential if it is the only prime implicant covering some 1-row of .
Theorem— Minimal sums of products use only primes
Some sum of products with the fewest literals for consists only of prime implicants.
Proof
Take any minimal sum of products. If one of its terms is not prime, remove literals from until it is a prime implicant . covers every row covered and is still an implicant, so the sum still equals on every row that matters, and it has fewer or equally many literals. Repeat for every term.
∎
So minimisation is two problems: find all the prime implicants, then choose the fewest (and cheapest) that cover every 1. Karnaugh maps solve both by eye for small functions; the Quine–McCluskey method solves them by computation.
Karnaugh maps
A Karnaugh map (K-map) is a truth table folded into a grid so that rows differing in one input sit next to each other. The trick is the order of the row and column labels: Gray code, 00, 01, 11, 10, in which neighbours differ in exactly one bit. The grid also wraps around: the left column neighbours the right one, and the top row the bottom one. Two adjacent 1-cells differ in one variable , so their minterms combine as , and the variable disappears. A rectangle of cells, whose sides are powers of two, is a product term with fewer literals.
Example— Segment e of a seven-segment display
A BCD (binary-coded decimal) to seven-segment decoder receives a digit 0–9 on four inputs ( most significant) and lights the segments a–g of a display. Inputs 10 to 15 never occur, so they are don't-cares. Segment e, the lower-left bar, is lit for the digits 0, 2, 6 and 8:
Place the 1s and the don't-cares (×) on the map below. Two groups cover all the 1s:
- the whole column : cells 2, 6, 14 and 10. and throughout, while and take every value, so the term is ;
- the four corners: cells 0, 2, 8 and 10, adjacent through the wrap-around. Here and , giving .
So : two 2-input gates and an OR, or three gates in factored form, instead of four 4-input minterms. Both groups used don't-cares (cells 10 and 14) to grow larger; a designer who set the don't-cares to 0 would need bigger terms.
The rules for reading a map: make every group a rectangle of 1, 2, 4, 8 or 16 cells (wrapping allowed); make each group as large as possible (that makes it prime); use as few groups as possible, starting with 1s that only one group can cover (those groups are essential); include don't-cares only when they help. Grouping the 0s instead gives a minimal product of sums.
Quine–McCluskey: minimisation by computation
Willard Quine (1952) and Edward McCluskey (1956) turned the map into an algorithm a computer can run for any number of variables.
- Write each 1 and don't-care as a binary string, such as
0110. - Merge any two strings that differ in exactly one position, writing a dash there:
0110and0010merge into-010. Repeat with the merged strings (dashes must line up). A string that never merges with anything is a prime implicant. - Cover: choose the fewest primes such that every 1 (not every don't-care) is covered by at least one of them.
The program below implements both steps. For the covering step it simply tries all choices of 1 prime, then 2, and so on, which is fine for the handful of primes a four-input function has. It then minimises all seven segments of the decoder.
from itertools import combinations
def combine(t1, t2):
"""Merge two terms that differ in exactly one fixed position: '0110' + '0100' -> '01-0'."""
diff = [i for i in range(len(t1)) if t1[i] != t2[i]]
if len(diff) == 1 and "-" not in (t1[diff[0]], t2[diff[0]]):
i = diff[0]
return t1[:i] + "-" + t1[i + 1:]
return None
def prime_implicants(ones, dont_cares, n):
"""Quine-McCluskey, step 1: merge terms until no more merges are possible."""
terms = {format(m, f"0{n}b") for m in ones + dont_cares}
primes = set()
while terms:
merged, used = set(), set()
for t1, t2 in combinations(sorted(terms), 2):
t = combine(t1, t2)
if t:
merged.add(t)
used |= {t1, t2}
primes |= terms - used # a term that merged with nothing is prime
terms = merged
return sorted(primes)
def covers(term, m):
bits = format(m, f"0{len(term)}b")
return all(t in ("-", b) for t, b in zip(term, bits))
def literals(term):
return len(term) - term.count("-")
def minimum_cover(primes, ones):
"""Step 2: the fewest primes covering every 1 (ties: fewest literals). Exhaustive, fine for small n."""
for k in range(1, len(primes) + 1):
options = [c for c in combinations(primes, k) if all(any(covers(p, m) for p in c) for m in ones)]
if options:
return min(options, key=lambda c: sum(literals(p) for p in c))
return ()
def expression(cover, names="ABCD"):
terms = ["".join(v + ("'" if b == "0" else "") for v, b in zip(names, t) if b != "-") or "1" for t in cover]
return " + ".join(terms) or "0"
# A BCD to seven-segment decoder: inputs ABCD (A most significant) hold a digit 0-9;
# the codes 10-15 never occur, so they are don't-cares.
DIGITS = { # segments lit: a b c d e f g
0: "1111110", 1: "0110000", 2: "1101101", 3: "1111001", 4: "0110011",
5: "1011011", 6: "1011111", 7: "1110000", 8: "1111111", 9: "1111011"}
DONT_CARE = list(range(10, 16))
ones_e = [d for d in range(10) if DIGITS[d][4] == "1"]
primes_e = prime_implicants(ones_e, DONT_CARE, 4)
print("segment e is lit for digits", ones_e)
print("its prime implicants:", primes_e, "=", expression(primes_e).replace(" + ", ", "))
print("minimum cover: e =", expression(minimum_cover(primes_e, ones_e)))
print()
total = 0
for k, seg in enumerate("abcdefg"):
ones = [d for d in range(10) if DIGITS[d][k] == "1"]
best = minimum_cover(prime_implicants(ones, DONT_CARE, 4), ones)
total += sum(literals(t) for t in best)
print(f"{seg} = {expression(best)}")
print("literals in all seven:", total)Segment e has five prime implicants, , , , and , but the last three cover only don't-cares and one already-covered 1, so the minimum cover is the pair we found by hand. The whole decoder needs 42 literals across its seven outputs. A real implementation would also share terms between outputs: appears in d, e and g, and in a, d and e, so one gate can serve several outputs. Multi-output minimisation is part of what synthesis tools do.
Glitches and hazards
Boolean algebra describes what a circuit settles to. It says nothing about the moments in between, when signals travel through gates of different delays. Take the function from the consensus example of the previous lesson, , built directly as two AND gates and an OR, with an inverter making . Hold . Then whatever does. But when falls from 1 to 0, the term turns off one gate delay later, while turns on only after two gate delays (inverter, then AND). For one gate delay neither term is 1, and dips to 0. That is a static-1 hazard: an output that should stay 1 briefly glitches to 0.
The cure is the consensus term , logically redundant but physically useful: while it holds the output at 1 regardless of the race between the other two terms. In K-map language, a static-1 hazard can occur wherever two adjacent 1s are covered by different groups; adding a group that spans the boundary removes it. A Verilog simulation with gate delays shows both versions. Each gate below is given a delay of 1 ns with #1; the testbench counts every change of each output.
`timescale 1ns/1ps
// F = AB + A'C, built from gates that each take 1 ns, with and without the consensus term BC.
module mux_logic (input a, b, c, output f, f_fixed);
wire na, t1, t2, t3;
not #1 g0 (na, a);
and #1 g1 (t1, a, b);
and #1 g2 (t2, na, c);
or #1 g3 (f, t1, t2);
and #1 g4 (t3, b, c); // the consensus term BC, logically redundant
or #1 g5 (f_fixed, t1, t2, t3);
endmodule
module tb;
logic a, b, c;
wire f, f_fixed;
int changes = 0, changes_fixed = 0;
mux_logic dut (.a(a), .b(b), .c(c), .f(f), .f_fixed(f_fixed));
always @(f) if ($time > 5) begin changes++; $display("t = %0d ns: f = %b", $time, f); end
always @(f_fixed) if ($time > 5) begin changes_fixed++; $display("t = %0d ns: f_fixed = %b", $time, f_fixed); end
initial begin
a = 1; b = 1; c = 1;
#10 $display("t = 10 ns: a falls from 1 to 0 (f should stay 1)");
a = 0;
#10;
if (changes != 2 || f !== 1) $fatal(1, "expected a 1-0-1 glitch on f");
if (changes_fixed != 0) $fatal(1, "f_fixed should not move");
$display("t = 20 ns: a rises from 0 to 1");
a = 1;
#10;
if (changes != 2) $fatal(1, "no glitch expected when a rises");
$display("glitches: f %0d, f_fixed %0d", changes / 2, changes_fixed / 2);
$finish(0);
end
endmoduleIt prints:
t = 10 ns: a falls from 1 to 0 (f should stay 1)
t = 12 ns: f = 0
t = 13 ns: f = 1
t = 20 ns: a rises from 0 to 1
glitches: f 1, f_fixed 0The glitch appears only when falls; when rises, turns on before turns off. Hazards are not limited to this case: a static-0 hazard is a brief 1 on an output that should stay 0, and a dynamic hazard is a multiple bounce (0, 1, 0, 1) on an output that should change once, typical of multi-level logic with several paths of different lengths.
How much should you worry? In a synchronous design, the flip-flops of the next lesson sample each combinational output only once per clock cycle, after it has settled, so glitches are harmless to correctness and synthesis tools happily remove consensus terms. They still waste power (every glitch charges and discharges capacitance), and they are dangerous wherever a signal is used without a clock: an asynchronous reset, a clock-enable built from gates, a signal leaving the chip to another system. Rule: never drive a clock or an asynchronous input from combinational logic.
Building blocks: multiplexers, decoders, encoders, comparators
Designers rarely minimise individual functions. They assemble a handful of standard blocks, each of which you could now design from gates.
| Block | Inputs → outputs | What it does |
|---|---|---|
| Multiplexer (mux), :1 | data inputs, select lines → 1 | passes the data input whose number is on the select lines |
| Decoder, -to- | inputs (often with an enable) → | exactly one output is 1, the one numbered by the input: each output is one minterm |
| Encoder, -to- | inputs, at most one active → | outputs the number of the active input |
| Priority encoder | inputs → + a "valid" bit | outputs the number of the highest-priority active input, and whether any is active |
| Equality comparator | two -bit words → 1 | 1 when : an AND of XNORs |
| Magnitude comparator | two -bit words → | usually computed by subtraction: the borrow out of |
Two of these are more powerful than they look. A decoder generates every minterm of its inputs, so a decoder plus OR gates implements any set of functions; memories use decoders to select one word out of many. A multiplexer with select lines can implement any function of inputs: wire the select lines to the inputs and tie each data input to 0 or 1, the function's value on that row. That is Shannon expansion applied times, and it is exactly what an FPGA's look-up table is, as Verilog and FPGAs will show. Large muxes are built as trees of 2:1 muxes, so an :1 mux has depth .
A priority encoder appears wherever several requests compete: interrupt controllers, arbiters for a shared bus, the logic that finds the leading 1 of a floating-point mantissa. With inputs and highest, its outputs are , and ; the term is where the "priority" lives.
Adders and their delay
The ripple-carry adder of Lumenary CS's From logic gates to a processor chains full adders, each waiting for the carry of the one below. Its worst case is the carry that travels the whole way, as in , so its delay grows linearly with the width . For a 64-bit processor that is too slow. The fix starts with two signals per bit position:
Then , and expanding the recurrence gives every carry directly from the inputs. For four bits,
This is a carry-lookahead adder: two levels of logic after and , whatever the width, but the terms grow quickly, so in practice lookahead is applied to groups of four bits, and then again to the groups. Each group computes a group generate and group propagate:
The key observation is that combining two adjacent groups, high and low , is always the same operation, , and that it is associative. Any associative operation over items can be computed as a tree of depth , the parallel prefix problem. Different trees give the classic adders: Kogge–Stone (1973) combines every position with the one places below, giving minimum depth and low fan-out at the price of many gates and long wires; Sklansky (1960) uses a divide-and-conquer tree with fewer gates but high fan-out; Brent–Kung (1982) uses fewer gates still, at nearly twice the depth.
The program models each adder as a netlist of 2-input gates, each taking one unit of delay, checks every design against Python's +, and then measures the latest-arriving sum bit and the number of gates.
import random
class Circuit:
"""Each signal is (value, arrival time). Every 2-input gate adds one unit of delay."""
def __init__(self):
self.gates = 0
def gate(self, op, x, y):
self.gates += 1
return op(x[0], y[0]), max(x[1], y[1]) + 1
AND = lambda u, v: u & v
OR = lambda u, v: u | v
XOR = lambda u, v: u ^ v
def ripple(c, a, b):
carry, s = (0, 0), []
for ai, bi in zip(a, b):
p, g = c.gate(XOR, ai, bi), c.gate(AND, ai, bi)
s.append(c.gate(XOR, p, carry))
carry = c.gate(OR, g, c.gate(AND, p, carry)) # c[i+1] = g[i] + p[i] c[i]
return s
def prefix_adder(c, a, b, style):
"""Parallel-prefix adder: combine (G, P) pairs of ever larger groups in log2(n) levels."""
n = len(a)
p = [c.gate(XOR, a[i], b[i]) for i in range(n)]
G = [c.gate(AND, a[i], b[i]) for i in range(n)]
P = p[:]
d = 1
while d < n:
if style == "Kogge-Stone": # every bit combines with the group d places below it
pairs = [(i, i - d) for i in range(d, n)]
else: # Sklansky: upper half of each 2d-block uses the lower half's top
pairs = [(i, (i & ~(d - 1)) - 1) for i in range(n) if i & d]
newG, newP = G[:], P[:]
for i, j in pairs:
newG[i] = c.gate(OR, G[i], c.gate(AND, P[i], G[j]))
newP[i] = c.gate(AND, P[i], P[j])
G, P = newG, newP
d *= 2
return [p[0]] + [c.gate(XOR, p[i], G[i - 1]) for i in range(1, n)] # carry into bit i is G[0..i-1]
def add(design, x, y, n):
c = Circuit()
a = [((x >> i) & 1, 0) for i in range(n)]
b = [((y >> i) & 1, 0) for i in range(n)]
s = design(c, a, b)
return sum(v << i for i, (v, t) in enumerate(s)), max(t for v, t in s), c.gates
designs = {"ripple-carry": ripple,
"Kogge-Stone": lambda c, a, b: prefix_adder(c, a, b, "Kogge-Stone"),
"Sklansky": lambda c, a, b: prefix_adder(c, a, b, "Sklansky")}
rng = random.Random(1)
for name, design in designs.items(): # check every design against Python's +
for _ in range(300):
n = rng.choice([8, 16, 32])
x, y = rng.getrandbits(n), rng.getrandbits(n)
assert add(design, x, y, n)[0] == (x + y) % 2**n, name
print("all three adders agree with + on 900 random sums\n")
print(" bits | gate delays: ripple Kogge-Stone Sklansky | gates: ripple Kogge-Stone Sklansky")
for n in (8, 16, 32, 64):
d = {k: add(f, 2**n - 1, 1, n)[1:] for k, f in designs.items()} # all ones + 1: the longest carry
print(f"{n:5} | {d['ripple-carry'][0]:19} {d['Kogge-Stone'][0]:12} {d['Sklansky'][0]:9} |"
f" {d['ripple-carry'][1]:13} {d['Kogge-Stone'][1]:12} {d['Sklansky'][1]:9}")The ripple adder's delay is exactly gate delays; the prefix adders' grows by two per doubling of the width. At 64 bits Kogge–Stone is ten times faster than ripple-carry in this model, and needs 3.6 times the gates; Sklansky is one gate delay slower, with a third fewer gates. Real designs pick a point on this curve to meet their clock period with the least area and power, and often mix styles.
An ALU in Verilog
An arithmetic logic unit computes one of several operations on two words, chosen by an operation code. Its central trick is that one adder serves for addition, subtraction and comparison: in two's complement, so subtraction inverts and sets the adder's carry-in to 1. Comparison is then a subtraction whose result is thrown away:
- unsigned exactly when the subtraction borrows, that is, when the carry out of is 0;
- signed exactly when the sign bit of is 1, unless the subtraction overflowed, in which case the sign bit is wrong and must be flipped.
Signed overflow happens when two operands of the same sign (after inverting for subtraction) give a result of the other sign, as in , the largest 32-bit signed number plus one.
The ALU below has the ten operations a RISC-V processor's integer instructions need (the processor in Designing a processor uses one like it). Its testbench follows the professional pattern: a reference model, written separately with Verilog's own operators, predicts every result, and the testbench compares the design against it on hand-picked corner cases and on 2,000 pseudo-random vectors per operation. $random(seed) with a fixed seed makes the run repeatable.
// A 32-bit ALU: one adder does addition, subtraction and both comparisons.
module alu (
input logic [31:0] a, b,
input logic [3:0] op,
output logic [31:0] y,
output logic zero, overflow
);
localparam ADD = 4'd0, SUB = 4'd1, AND = 4'd2, OR = 4'd3, XOR = 4'd4,
SLT = 4'd5, SLTU = 4'd6, SLL = 4'd7, SRL = 4'd8, SRA = 4'd9;
logic subtract, carry, less_signed;
logic [31:0] b_in, sum;
logic [4:0] shamt;
assign subtract = (op == SUB) || (op == SLT) || (op == SLTU);
assign b_in = subtract ? ~b : b; // a - b = a + ~b + 1
assign {carry, sum} = {1'b0, a} + {1'b0, b_in} + {32'd0, subtract};
// Signed overflow: both operands have the same sign and the result's sign differs.
assign overflow = (a[31] == b_in[31]) && (sum[31] != a[31]);
assign less_signed = sum[31] ^ overflow; // sign of a - b, corrected for overflow
assign shamt = b[4:0]; // shifts use the low 5 bits of b
always_comb begin
case (op)
ADD, SUB: y = sum;
AND: y = a & b;
OR: y = a | b;
XOR: y = a ^ b;
SLT: y = {31'd0, less_signed}; // a < b as signed numbers
SLTU: y = {31'd0, ~carry}; // a < b unsigned: the subtraction borrowed
SLL: y = a << shamt;
SRL: y = a >> shamt;
SRA: y = $signed(a) >>> shamt;
default: y = 32'd0;
endcase
end
assign zero = (y == 32'd0);
endmodule
module tb;
logic [31:0] a, b, y, expected;
logic [3:0] op;
logic zero, overflow;
int seed = 2026, tests = 0;
alu dut (.a(a), .b(b), .op(op), .y(y), .zero(zero), .overflow(overflow));
// The reference model uses Verilog's own operators, written independently of the design.
function automatic logic [31:0] model(input logic [31:0] x, z, input logic [3:0] o);
case (o)
0: return x + z; 1: return x - z;
2: return x & z; 3: return x | z;
4: return x ^ z; 5: return {31'd0, $signed(x) < $signed(z)};
6: return {31'd0, x < z}; 7: return x << z[4:0];
8: return x >> z[4:0]; 9: return $signed(x) >>> z[4:0];
default: return 0;
endcase
endfunction
task automatic check(input logic [31:0] x, z, input logic [3:0] o);
a = x; b = z; op = o; #1;
expected = model(x, z, o);
if (y !== expected || zero !== (expected == 0))
$fatal(1, "op %0d: a=%h b=%h gave %h, expected %h", o, x, z, y, expected);
tests++;
endtask
initial begin
check(32'h7FFF_FFFF, 32'd1, 0);
$display("7fffffff + 1 = %h overflow = %b", y, overflow);
if (overflow !== 1) $fatal(1, "missed signed overflow");
check(32'h8000_0000, 32'd1, 1);
$display("80000000 - 1 = %h overflow = %b", y, overflow);
if (overflow !== 1) $fatal(1, "missed signed overflow");
check(32'hFFFF_FFFB, 32'd3, 5);
$display("fffffffb < 3 signed = %0d (-5 < 3)", y);
check(32'hFFFF_FFFB, 32'd3, 6);
$display("fffffffb < 3 unsigned = %0d (4294967291 < 3)", y);
check(32'h8000_0000, 32'd4, 9);
$display("80000000 >>> 4 = %h", y);
check(32'd42, 32'd42, 1);
$display("42 - 42 = %0d zero = %b", y, zero);
for (int o = 0; o <= 9; o++)
repeat (2000) check($random(seed), $random(seed), o[3:0]);
$display("%0d vectors match the reference model", tests);
$finish(0);
end
endmoduleIt prints:
7fffffff + 1 = 80000000 overflow = 1
80000000 - 1 = 7fffffff overflow = 1
fffffffb < 3 signed = 1 (-5 < 3)
fffffffb < 3 unsigned = 0 (4294967291 < 3)
80000000 >>> 4 = f8000000
42 - 42 = 0 zero = 1
20006 vectors match the reference modelalways_comb is SystemVerilog's way of saying "this block is combinational logic": the simulator re-evaluates it whenever an input changes, and synthesis tools warn if it would infer memory by accident. The shift amount uses only the low five bits of b, as RISC-V specifies for 32-bit registers, and the arithmetic right shift >>> copies the sign bit in from the left, so .
How combinational logic is designed in practice
Nobody draws K-maps for a processor. A designer writes behaviour (assign y = a + b;) or a structure of blocks in a hardware description language, and a logic synthesis tool turns it into gates. Modern synthesis represents logic as an and-inverter graph, a network of 2-input AND gates and inverters, rewrites it to reduce size and depth, and then maps it onto the cells available: a standard-cell library of NAND, NOR, AOI, flip-flop and other cells for a chip, or look-up tables and carry chains for an FPGA. Berkeley's open-source ABC does this inside Yosys; the commercial tools of Synopsys, Cadence and Siemens do the same at much larger scale. For arithmetic, tools keep libraries of adder and multiplier architectures and choose among ripple, prefix and hybrid designs according to the timing constraint.
Two consequences matter to anyone writing hardware. First, after optimisation the gates no longer match the source, so teams run formal equivalence checking (SAT-based and BDD-based tools) to prove that the netlist computes the same function as the description. Second, the best structure depends on the target. On an FPGA, an adder is usually fastest as a ripple-carry chain, because FPGAs have dedicated carry logic running vertically through each column, far faster than general routing; a hand-built Kogge–Stone adder in LUTs can be slower. On a custom chip the prefix adder wins.
Common misconceptions
Misconception
"A minimal sum of products is the smallest circuit." It is the smallest two-level AND–OR circuit. Factoring ( instead of ), sharing terms between outputs, and XOR gates often give much smaller multi-level circuits. Parity of 16 bits needs terms as a sum of products and 15 XOR gates as a tree.
Misconception
"Redundant terms are always waste." The consensus term that removes a hazard is logically redundant and physically necessary in circuits that are not sampled by a clock. Synthesis tools remove such terms, which is why asynchronous logic is written and constrained with special care.
Misconception
"Don't-cares mean the output is 0 for those inputs." They mean the designer may choose either value, row by row. Treating them all as 0 throws away the freedom that made segment e two small terms. (Conversely, if those inputs can occur after all, for example at power-up, the chosen values had better be harmless.)
Misconception
"The fastest adder is always the best." A Kogge–Stone adder costs several times the area and power of a ripple adder and has long wires. If the adder is not on the critical path, the smallest design that meets timing is the right one.
Exercises
1. Combinational logic
CoreHumanMinimise as a sum of products ( most significant). How many literals does a minimal sum of products have? (A literal is one occurrence of a variable, complemented or not: has two.)
2. Combinational logic
CoreHumanThe function is built directly as two AND gates and an OR gate, with an inverter making . Which input change can cause a static-1 hazard, and which added term removes it?
3. Combinational logic
Warm-upHumanA 32:1 multiplexer is built as a tree of 2:1 multiplexers. How many 2:1 multiplexers does it need?
4. Combinational logic
Warm-upComputationalWrite the merging step of Quine–McCluskey. Terms are strings of 0, 1 and - of equal length. merge(t1, t2) returns the merged term when the two differ in exactly one position and neither has a dash there (for example merge('0110', '0100') is '01-0'); otherwise it returns None.
5. Combinational logic
CoreComputationalWrite group_gp(a, b, lo, hi), returning the group generate and group propagate of bit positions lo to hi (inclusive) of the integers a and b. With and , must be 1 exactly when the group produces a carry out with carry-in 0, and exactly when every position propagates, so that the carry out of the group is . Do not add the operands with +; build and from the bits.
6. Combinational logic
CoreHumanIn the lesson's model (every 2-input gate one unit of delay), the Kogge–Stone adder's delay was 7, 9, 11 and 13 gate delays for 8, 16, 32 and 64 bits. How many gate delays would a 128-bit Kogge–Stone adder take in the same model, and how many would a 128-bit ripple-carry adder take? Give the Kogge–Stone figure.
7. Combinational logic
CoreHumanAn 8-bit ALU computes as , with and . What is the carry out of the adder, and what does it say about for unsigned numbers?
Further reading and resources
- The map method for synthesis of combinational logic circuits · Maurice Karnaugh · 1953The paper that introduced the Karnaugh map (Transactions of the AIEE, Part I).
- Minimization of Boolean functions · Edward J. McCluskey · 1956McCluskey's tabular method, completing Quine's earlier work (Bell System Technical Journal).
- A parallel algorithm for the efficient solution of a general class of recurrence equations · Peter M. Kogge and Harold S. Stone · 1973The parallel-prefix method behind the Kogge–Stone adder.
- ABC, a system for sequential synthesis and verification · Berkeley Logic Synthesis and Verification GroupThe open-source logic optimiser used inside Yosys and many research flows.
- Yosys Open SYnthesis SuiteOpen-source synthesis from Verilog to gates, LUTs and standard cells.