Designing a combinational circuit

A combinational circuit's outputs depend only on its inputs right now (no memory). Designing one always follows the same steps:

1. Name the inputs and outputs.
2. Write the truth table: what the output must be for every input.
3. Simplify each output (K-map, or the Quine–McCluskey method in software).
4. Draw the gates, and check the circuit against the table.

Example: a 2-bit comparator

Compare two 2-bit numbers A = A1A0 and B = B1B0. Output G is 1 when A > B.

Step 2. 16 rows (4 inputs). For example A = 10 (2) and B = 01 (1) gives G = 1.

Step 3. The 1s, in a K-map with rows A1A0 and columns B1B0, form three groups:

• A1B1': A's high bit is 1 and B's is 0, so A is bigger whatever the low bits are;
• A0B1'B0': A is odd and B is 0;
• A1A0B0': A is 3 and B is even (0 or 2).

G = A1B1' + A0B1'B0' + A1A0B0'

Step 4. Check every row by machine:

wrong = 0
for row in range(16):
    a1, a0, b1, b0 = (row >> 3) & 1, (row >> 2) & 1, (row >> 1) & 1, row & 1
    want = 1 if a1 * 2 + a0 > b1 * 2 + b0 else 0
    g = (a1 & (1 - b1)) | (a0 & (1 - b1) & (1 - b0)) | (a1 & a0 & (1 - b0))
    if g != want:
        wrong += 1
        print("wrong for A =", a1, a0, "B =", b1, b0)
print("rows checked: 16, wrong:", wrong)

How fast is the circuit?

Every gate takes a little time to react: its propagation delay, a few tens of picoseconds in a modern chip. A signal's delay is the sum of the gates on its path, and the circuit is only as fast as its slowest input-to-output path, the critical path. Two levels of logic (AND then OR, as in any sum of products) keep the path short, which is one more reason to simplify.

delay = {"NOT": 10, "AND": 20, "OR": 25}      # picoseconds
paths = {
    "B1 -> NOT -> AND -> OR": ["NOT", "AND", "OR"],
    "A1 -> AND -> OR": ["AND", "OR"],
}
for name, gates in paths.items():
    print(name, ":", sum(delay[g] for g in gates), "ps")
print("critical path:", max(sum(delay[g] for g in gates) for gates in paths.values()), "ps")

Mark lesson complete