Common logic circuits

Half adder

Adds two bits. Two gates.

Adding two single bits has four cases, and the two output columns turn out to be gates you already know. The sum is 1 when exactly one input is 1, which is XOR. The carry is 1 only when both are, which is AND. It is called a half adder because it has nowhere to accept a carry coming in from the column to its right.

• The least significant column of an adder, where there is no carry in.
• Incrementing a value by one, which is an adder with the second input tied to a constant.
• A first custom node to build, because everything larger is made of these.

Half adder: live diagram, reference card and questions →

Full adder

Adds two bits and a carry in.

A third input lets the carry from the previous column join in, which is what makes the adder chainable. The sum is the XOR of all three inputs, and the carry out is high whenever at least two of the three are, so it is really a majority function wearing a different hat.

• Every column but the first of a ripple carry adder.
• Subtraction, by inverting one operand and setting the first carry in to 1.
• Counters and accumulators, which are adders with a register on the output.

Full adder: live diagram, reference card and questions →

2-to-1 multiplexer

Picks one of two inputs.

A multiplexer is a switch made of gates. The select line enables one of two AND gates, and an OR merges them, so exactly one input reaches the output at a time. Widen the select to n bits and you can choose between 2^n inputs.

• Choosing between two data sources, which is how a processor picks an operand.
• Implementing any boolean function directly, by wiring the truth table into the data inputs.
• Sharing one bus between several senders, one at a time.

2-to-1 multiplexer: live diagram, reference card and questions →

1-to-2 demultiplexer

Sends one input to one of two outputs.

The mirror image of a multiplexer. One data line goes in, the select decides which output it comes out of, and the other output stays low. Chain them and one signal can be routed to any of many destinations.

• Routing a signal to one of several destinations, such as picking a memory bank.
• Turning a binary address into an enable line for the addressed device.
• Serial to parallel conversion, together with some storage.

1-to-2 demultiplexer: live diagram, reference card and questions →

2-to-4 decoder

Turns a 2-bit number into one hot line.

A decoder raises exactly one output, the one whose number matches the input. Each output is a single AND of the inputs in the right polarities, which means a decoder is really all the minterms of its inputs made available at once.

• Address decoding: picking which chip or register a bus address refers to.
• Driving a display, where each output lights one element.
• Building any function at all, by ORing together the minterms you want.

2-to-4 decoder: live diagram, reference card and questions →

4-to-2 encoder

Turns one hot line back into a number.

The reverse of a decoder: four lines in, a two bit number out saying which one is high. It assumes exactly one input is active. If two are, the output is the OR of their codes rather than either of them, which is why real designs use a priority encoder that picks the highest instead. Note also that all zeros and I0 alone both give 00, so a real encoder adds a valid output to tell them apart.

• Reading a keypad, where one key is down at a time.
• Interrupt handling, usually as a priority encoder so simultaneous requests resolve.
• Compressing a one hot state register back into a binary state number.

4-to-2 encoder: live diagram, reference card and questions →

1-bit comparator

Says whether two bits are equal, or which is bigger.

Comparing one bit needs three answers, and exactly one of them is true at any time. Equality is just XOR inverted, since XOR asks whether the inputs differ. Widening it to several bits means comparing from the most significant end and only looking further down when the bits so far are equal.

• Testing two values for equality, which a processor does on every branch.
• Sorting networks and min or max circuits.
• Detecting that a counter has reached a target value.

1-bit comparator: live diagram, reference card and questions →

3-bit parity generator

Says whether the number of 1s is odd.

XOR gates chained together answer one question: is the number of high inputs odd? Send that bit along with the data and the receiver can recompute it. If the two disagree, something flipped on the way, which catches any single bit error.

• Error detection on serial links and older memory buses.
• The starting point for a CRC, which is the same idea run over many bits at once.
• The sum output of an adder, which is the parity of its three inputs.

3-bit parity generator: live diagram, reference card and questions →

Majority voter

High when at least two of three inputs are.

Three inputs vote and the majority wins. It is the same function as the carry out of a full adder, which is worth noticing: adding three bits produces a carry exactly when at least two of them are 1.

• Redundant systems, where three copies of a circuit vote so one failure is outvoted.
• The carry path of an adder.
• Smoothing a noisy signal by voting over three samples.

Majority voter: live diagram, reference card and questions →

Half subtractor

Subtracts one bit from another. Two gates and an inverter.

Subtracting B from A one bit at a time has the same four cases as adding, and the difference column is the same XOR. What changes is the carry: subtraction borrows, and only one case needs it, 0 minus 1. So the borrow is 1 exactly when A is 0 and B is 1, which is ¬A ∧ B rather than the adder's A ∧ B.

• The least significant column of a subtractor, where nothing has been borrowed yet.
• The rightmost column of a decrementer, which is a chain of these with a constant 1 fed into that column.
• Showing why adders and subtractors are the same circuit apart from one inverted input.

Half subtractor: live diagram, reference card and questions →

Full subtractor

Subtracts two bits and a borrow in.

A third input takes the borrow from the column to the right, which is what makes the subtractor chainable. The difference is the XOR of all three inputs, exactly as in the full adder. The borrow out is 1 when B alone exceeds A, or when A and B are equal and the incoming borrow has to be passed on: ¬A ∧ B ∨ ¬(A ⊕ B) ∧ Bin.

• Every column but the first of a ripple borrow subtractor.
• Comparing two numbers, since a subtraction that ends with a borrow out means the second number was bigger.
• The subtract half of an arithmetic unit, though most real designs add the two's complement instead and reuse the adder.

Full subtractor: live diagram, reference card and questions →

3-to-8 decoder

Turns a 3-bit number into one hot line out of eight.

The same idea as the 2-to-4 decoder with one more input bit: each output is a single three-input AND of the inputs in the right polarity, so the eight outputs are the eight minterms of A, B and C. Three inverters and eight AND gates make the whole circuit, and this is the size that turns up most often as a real part, the 74138, which adds enable inputs so that two of them can be wired into a 4-to-16.

• Selecting one of eight registers, memory chips or peripherals from three address bits.
• Generating all the minterms of three variables at once, so any three-input function is an OR of some outputs.
• Converting a three bit state number into one hot signals for a state machine.

3-to-8 decoder: live diagram, reference card and questions →

2-bit comparator

Compares two 2-bit numbers: equal, greater or less.

Comparing two bits at a time is the 1-bit comparator twice, with a rule for combining them: the high bits decide unless they are equal, in which case the low bits decide. Equality is the AND of the two per-bit XNORs. Greater is "A1 beats B1" or "the high bits tie and A0 beats B0", and less is the mirror image. Widening to more bits adds one more term per bit, each guarded by every tie above it.

• Branch decisions on small fields such as priority levels or opcodes.
• Detecting that a 2-bit counter has passed a threshold.
• The building block of wider comparators, which chain these so that a lower stage only decides when every stage above it reports equal.

2-bit comparator: live diagram, reference card and questions →

Putting them together

None of these is interesting alone. What makes them worth knowing is that they compose, and the simulator lets you package each one into a node you can reuse.

• Two half adders and an OR make a full adder.
• Four full adders in a row make a four bit ripple carry adder, each carry feeding the next.
• An adder with one input inverted and the first carry set to 1 becomes a subtractor, because that is two's complement.
• A decoder plus a set of ORs builds any function at all, straight from its truth table.
• Four input bits and seven output functions make a seven-segment decoder, the classic exercise in using don't cares.
• Add a flip-flop and an adder becomes a counter, which is where combinational logic stops and sequential logic starts.

Open the four bit calculator

Or draw any of the expressions above with the circuit diagram generator. The adders are also where two's complement earns its keep: feed one input its complement and the same circuit subtracts.

Reference cards

Every circuit above as a gate diagram, black on white, for notes or a slide.

Click to download: Half adder circuit diagram

Click to download: Full adder circuit diagram

Click to download: 2-to-1 multiplexer circuit diagram

Click to download: 1-to-2 demultiplexer circuit diagram

Click to download: 2-to-4 decoder circuit diagram

Click to download: 4-to-2 encoder circuit diagram

Click to download: 1-bit comparator circuit diagram

Click to download: 3-bit parity generator circuit diagram

Click to download: Majority voter circuit diagram

Click to download: Half subtractor circuit diagram

Click to download: Full subtractor circuit diagram

Click to download: 3-to-8 decoder circuit diagram

Click to download: 2-bit comparator circuit diagram