Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 67 ยท Digital Logic

Combinational Circuits

Build multiplexers, decoders, encoders, half and full adders and a ripple-carry adder from simple gate functions, and test them in Python.

A combinational circuit is a network of logic gates whose outputs depend only on the current inputs. It has no memory: set the inputs, wait a few picoseconds for the signals to ripple through, and the outputs show the answer. Change an input and the outputs follow. Circuits that remember past values are sequential and come in the next lesson.

Combinational blocks are the working parts of every processor. A multiplexer picks which register to read, a decoder turns an instruction's opcode into a single "do this" wire, and adders do arithmetic. In this lesson you will design the most important blocks, then wire full adders into a ripple-carry adder that adds multi-bit numbers. Every block is written as a Python function built only from gate functions, so you can test it against all inputs.

Building blocks as functions

First, our gates. Everything below uses only these:

Python
def NOT(a): return 1 - a
def AND(a, b): return a & b
def OR(a, b): return a | b
def XOR(a, b): return a ^ b

A combinational circuit is then simply a function that calls other functions, with no stored state. That matches the hardware: an output is a pure function of the inputs.

Multiplexer (mux)

A multiplexer selects one of several data inputs and passes it to the output. A 2-to-1 mux has data inputs D0 and D1, a select line S, and one output:

TEXT
Y = D0 ยท S' + D1 ยท S

When S = 0 the output copies D0; when S = 1 it copies D1. A 4-to-1 mux needs two select bits, an 8-to-1 mux needs three, and in general n select lines choose among 2^n inputs. Larger muxes are built as trees of 2-to-1 muxes.

flowchart LR
  D0["D0"] --> M["2-to-1 mux"]
  D1["D1"] --> M
  S["S (select)"] --> M
  M --> Y["Y"]

A multiplexer chooses one of its data inputs using the select line.

Muxes are everywhere in a CPU: choosing which register feeds the ALU, whether the next address is PC + 4 or a branch target, or whether an ALU input is a register or a constant. You will see them in The CPU Datapath.

Decoder

A decoder does the opposite job: it takes an n-bit binary number and activates exactly one of 2^n output lines. A 2-to-4 decoder with inputs A1 A0 has outputs Y0 to Y3, and Y_k = 1 only when the input number equals k:

TEXT
Y0 = A1' A0'    Y1 = A1' A0    Y2 = A1 A0'    Y3 = A1 A0

Each output is an AND of the inputs or their inverses (a minterm). Decoders select a memory chip or a register from an address, and they turn an opcode into a one-hot control signal. Add an enable input and the whole decoder can be switched off, which is how you combine small decoders into big ones.

Encoder and priority encoder

An encoder is the inverse of a decoder: it takes 2^n lines, of which exactly one is active, and outputs the n-bit number of that line. Plain encoders fail when two inputs are active at once. A priority encoder fixes this by always reporting the highest-numbered active input, plus a valid output saying whether any input was active at all. Interrupt controllers use priority encoders to pick the most urgent request.

Python Mux, decoder and priority encoder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the last block, requests [0, 1, 1, 0] give index 2 even though request 1 is also active: the higher line wins.

Half adder

Adding two single bits gives a two-bit answer: a sum and a carry. From the addition table you saw in binary arithmetic:

A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Sum is XOR and carry is AND. That is the whole half adder: one XOR gate and one AND gate.

TEXT
Sum   = A โŠ• B
Carry = A ยท B

It is called "half" because it cannot accept a carry coming in from a lower column.

Full adder

A full adder adds three bits: A, B and a carry-in Cin. The result is a sum bit and a carry-out, and the sum ranges from 0 to 3.

TEXT
Sum  = A โŠ• B โŠ• Cin
Cout = AยทB + Cinยท(A โŠ• B)

The structure reuses half adders: the first adds A and B; the second adds that result to Cin; the two carries are OR-ed together. At most one of those two carries can be 1, which is why OR is enough.

flowchart LR
  A["A"] --> HA1["Half adder 1"]
  B["B"] --> HA1
  HA1 -->|"sum"| HA2["Half adder 2"]
  Cin["Cin"] --> HA2
  HA2 --> S["Sum"]
  HA1 -->|"carry"| OR1["OR"]
  HA2 -->|"carry"| OR1
  OR1 --> Cout["Cout"]

A full adder is two half adders plus an OR gate.

Python Half adder and full adder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ripple-carry adder

To add two n-bit numbers, chain n full adders. The carry-out of each stage feeds the carry-in of the next one, from the least significant bit upward. This is the ripple-carry adder: the carry "ripples" from right to left, exactly like pencil-and-paper addition.

flowchart LR
  C0["Cin = 0"] --> FA0["FA bit 0"]
  FA0 -->|"c1"| FA1["FA bit 1"]
  FA1 -->|"c2"| FA2["FA bit 2"]
  FA2 -->|"c3"| FA3["FA bit 3"]
  FA3 --> CO["Cout"]

Four full adders chained into a 4-bit ripple-carry adder.

It is simple and small, but slow: bit 3 cannot finish until the carry has travelled through bits 0, 1 and 2. The delay grows linearly with the width. A 64-bit ripple adder would have a 64-stage carry chain, so real ALUs use faster designs such as carry-lookahead; you will see the idea in Building an ALU.

The same adder also subtracts: invert B and set Cin = 1, as explained in the binary-arithmetic lesson. The carry-out of the top stage is the carry flag, and XOR-ing the carries into and out of the top stage gives the overflow flag.

Python A 4-bit ripple-carry adder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test loop is the real prize: with only 256 input pairs we can check the circuit exhaustively and prove it correct, something impossible for most software. Hardware designers do the same, using simulators and formal tools.

Delay and glitches

A combinational output is not instantaneous. Each gate adds a small delay, and the longest path from any input to any output, the critical path, limits how fast the clock may tick. Different paths have different lengths, so for a moment an output can show a wrong value before settling (a glitch). That is harmless in a circuit read only at clock edges, which is exactly why synchronous design samples signals with registers. The next lesson introduces them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What defines a combinational circuit?

    A combinational circuit has no memory; the outputs are a function of the current inputs alone.
  2. 2. How many select lines does a 16-to-1 multiplexer need?

    n select lines choose among 2^n inputs, and 2^4 = 16.
  3. 3. Which gates form a half adder?

    Sum = A XOR B and Carry = A AND B.
  4. 4. Why is the ripple-carry adder slow for wide numbers?

    The carry has to propagate through all stages in turn, so the delay grows with the number of bits.
  5. 5. What does a priority encoder do when several inputs are active?

    A priority encoder resolves conflicts by reporting the highest-priority (usually highest-numbered) active line, with a valid flag.

Summary

  • A combinational circuit's outputs depend only on its current inputs; it has no memory.
  • A multiplexer selects one of 2^n inputs with n select lines; a decoder activates one of 2^n outputs; a priority encoder reports the highest active input.
  • A half adder is XOR plus AND; a full adder adds a carry-in using two half adders and an OR.
  • Chaining full adders gives a ripple-carry adder, which is simple but has a delay proportional to its width.
  • Subtraction reuses the adder with inverted B and a carry-in of 1.
  • Small circuits can be verified exhaustively by testing every input combination.

Next, add memory to circuits with Latches, Flip-Flops and Registers.