Logical Operations

Every arithmetic operation a processor performs ultimately bottoms out in logical operations — and, or, not — carried out by logic gates. This page starts with the rules of those gates and their truth tables, then shows how gates are wired into adders and other combinational circuits, and finally how flip-flops turn a purely combinational circuit into one that can remember. That last step is the whole answer to the question of how a machine can compute: it is not that the gates are clever, it is that a feedback loop lets a bit keep its value long enough to be used again.

Basic Logical Operations

A logical operation takes one or two binary inputs and produces one binary output. There are only three that matter, and every other operation can be expressed in terms of them.

AND Operation

The AND operation outputs 1 only when every input is 1. In symbolic form it is written A ∧ B, and in algebraic form A · B. The dot notation comes from the way the operation behaves like multiplication: any 0 among the inputs forces the result to 0.

• Symbol: A ∧ B or A · B

• Truth table:

  A	B	A ∧ B
  0	0	0
  0	1	0
  1	0	0
  1	1	1

This is the operation behind “enable” signals and “all conditions met” checks: a component is enabled only when every control bit is asserted.

OR Operation

The OR operation outputs 1 when at least one input is 1. It is written A ∨ B, and in algebraic form A + B. The plus sign reflects the behaviour of addition on binary values, where a 1 in either place is enough to produce a 1.

• Symbol: A ∨ B or A + B

• Truth table:

  A	B	A ∨ B
  0	0	0
  0	1	1
  1	0	1
  1	1	1

An OR gate is what “interrupt” lines and “any one of these requests” lines are built from.

NOT Operation

The NOT operation inverts its single input: 0 becomes 1 and 1 becomes 0. It is written ¬A, or A' in algebraic notation.

• Symbol: ¬A or A’

• Truth table:

  A	¬A
  0	1
  1	0

XOR Operation

The exclusive OR, written A ⊕ B, outputs 1 when exactly one of the two inputs is 1, and 0 when the two inputs are equal. It is the gate that detects difference, which is why it plays a central role in every adder and in the parity checks of error-detecting codes.

• Symbol: A ⊕ B

• Truth table:

  A	B	A ⊕ B
  0	0	0
  0	1	1
  1	0	1
  1	1	0

Two facts make XOR especially useful: A ⊕ B equals 1 exactly when A and B differ, and it can be built from the three basic gates — A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B).

Boolean Algebra

Boolean algebra is the set of rules that lets you rewrite a gate network in a different but equivalent form. It exists for one practical reason: a circuit that is correct on paper may need more gates, more delay, or more power than the one you can actually afford to build. Simplifying the expression before building it is often cheaper than optimising the silicon afterwards.

Basic Laws

• Commutative law: A ∧ B = B ∧ A, A ∨ B = B ∨ A
• Associative law: (A ∧ B) ∧ C = A ∧ (B ∧ C)
• Distributive law: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
• De Morgan’s laws: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B

The last pair is the one that shows up most often in practice, because it lets you move an inversion past a gate. Whenever you see a NOT feeding an AND, De Morgan’s law says you can push the inversion inside and swap AND for OR — which is exactly what a NAND gate does, and why NAND (rather than AND) is the gate that most standard cell libraries are built from.

Simplification Methods

• Algebraic simplification: applying the laws of Boolean algebra
• Karnaugh map: a graphical method of simplification
• Quine-McCluskey algorithm: a systematic method of simplification

A Karnaugh map arranges the truth table as a grid so that variables which differ in one row or column become neighbours; grouping neighbours into powers of two makes the minimal expression visible at a glance. It is the practical tool for circuits with up to about four inputs, and the Quine-McCluskey algorithm covers the cases where the expression is too large to draw.

Combinational Logic Circuits

A combinational circuit is one whose output depends only on the current inputs. There is no history and no feedback: give the gates the same inputs and they always produce the same outputs. This is the “pure logic” half of a computer.

Basic Gate Circuits

• AND gate: implements the AND operation
• OR gate: implements the OR operation
• NOT gate: implements the NOT operation
• NAND gate: an AND gate followed by a NOT gate
• NOR gate: an OR gate followed by a NOT gate

NAND and NOR are called universal gates because either one alone can implement any function — AND, OR, NOT and everything else can be reconstructed from them. Chip foundries therefore tend to optimise the NAND cell and build everything else out of it, because a chip with only one well-optimised cell type is smaller and cheaper than one with many.

Encoders and Decoders

• Encoder: encodes several inputs into a binary output
• Decoder: decodes a binary input into several outputs
• Priority encoder: handles the case where several inputs are asserted at once

A 3-to-8 decoder, for example, takes a 3-bit number and drives exactly one of its eight outputs low. Decoders are how a processor turns an instruction byte into the individual control signals that drive the rest of the chip.

Multiplexers and Demultiplexers

• Multiplexer: selects one of several inputs as its output
• Demultiplexer: routes one input to one of several outputs

A multiplexer is the reason a processor does not need a separate wire for every possible source: a bus is shared, and the multiplexer decides which source is currently allowed to drive it. That sharing is what makes wide buses affordable.

Arithmetic Logic Unit (ALU)

• Function: performs arithmetic and logical operations
• Control signals: determine which operation is performed
• Flag bits: report the characteristics of the result

The ALU is where the instruction decoder and the register file meet. The control unit tells the ALU which operation to perform and on which operands, and the ALU returns the result together with flags such as zero, carry, sign, and overflow — which the program then branches on.

Sequential Logic Circuits

A sequential circuit adds memory to the combinational logic. Its output depends not only on the current inputs but also on what happened before, because a feedback path carries a value from one clock cycle to the next.

Flip-Flops

• SR flip-flop: the basic storage element
• D flip-flop: the data flip-flop, the one in most common use
• JK flip-flop: the general-purpose flip-flop
• T flip-flop: the toggle flip-flop

A flip-flop has two stable states and one active edge that moves it between them. The D flip-flop — whose output simply follows its input at the clock edge — is by far the most common, because it removes the ambiguity that the SR and JK types carry with them.

Registers

• Basic register: stores several bits of data
• Shift register: shifts data from one position to the next
• Parallel register: loads all of its bits at once
• Serial register: loads the data bit by bit

Registers are flip-flops grouped together and given a common clock, so they all change state on the same edge. A processor’s register file is built this way, which is why reading and writing a register costs a single clock cycle.

Counters

• Synchronous counter: all bits change at the same time
• Asynchronous counter: the bits change one after another
• Up-down counter: counts either up or down
• Ring counter: counts in a cycle

The synchronous and asynchronous distinction is about clocking: a synchronous counter drives every flip-flop from the same clock and therefore changes all its bits together, while an asynchronous counter chains the clocks so that each stage toggles after the one before it. Synchronous counters are faster and produce no intermediate invalid states; asynchronous ones need fewer gates but glitch on the way to each new value.

Memory Logic

The same gates that compute with bits can also hold them. The trick is that a gate with a feedback loop can be made to have two stable states, and then a group of them can be addressed and read as a unit.

Random Access Memory (RAM)

• Static RAM (SRAM): stores each bit in a flip-flop
• Dynamic RAM (DRAM): stores each bit in a capacitor
• Address decoding: selects a particular storage cell
• Read/write control: governs the read and write operations on the data

The difference between SRAM and DRAM is what holds the charge and what it costs to keep it there. An SRAM cell keeps its bit in a feedback loop as long as power is supplied, so it is fast and needs no refresh — but it needs six transistors per bit. A DRAM cell stores the bit as charge on a capacitor, which leaks and must be refreshed thousands of times per second, but a cell needs only one transistor and one capacitor, so DRAM is far denser and far cheaper per bit, and far slower.

Read-Only Memory (ROM)

• Mask ROM: programmed at the factory
• Programmable ROM (PROM): programmable once by the user
• Erasable PROM (EPROM): erased with ultraviolet light
• Electrically Erasable PROM (EEPROM): erased electrically

ROM keeps its contents when the power is off, which is what makes it the right home for firmware and for the fixed lookup tables that decode instructions.

Digital System Design

Design Methods

• Top-down: start the design at the system level
• Bottom-up: start the design from the basic cells
• Modular design: decompose the system into modules
• Hierarchical design: design at different levels of abstraction

In practice a design moves between all four. You partition the system into modules, specify the behaviour of each, implement each from the cell library upward, and then check the whole against the original specification downward.

Design Tools

• Hardware description languages (HDL): VHDL, Verilog
• Simulation tools: verify that a design is correct
• Synthesis tools: turn an HDL description into a circuit
• Place and route tools: carry out the physical design

The synthesis step is where the tool decides the actual gate-level structure: given a behavioural description, it selects gates and widths that meet the timing constraints at the lowest area and power. The result is then placed and routed onto the silicon.

Performance Optimisation

Speed Optimisation

• Critical path optimisation: shorten the longest delay path
• Pipelining: split a circuit into stages
• Parallel processing: perform several operations at once
• Caching: reduce the access latency

Pipelining is worth a word on its own, because it is the technique that lets a processor raise its clock frequency. The critical path is the longest chain of gates a signal must traverse; if it takes 10 ns, the clock cannot be shorter than 10 ns. Splitting that chain into two stages of 5 ns each does not make the computation finish sooner — the total latency is unchanged — but it does allow the clock to run twice as fast, and because a new item enters the pipeline every cycle, the throughput doubles.

Area Optimisation

• Logic simplification: reduce the number of gates
• Resource sharing: let several functions share a circuit
• Encoding optimisation: reduce the number of signal lines
• Layout optimisation: reduce the area of the chip

Resource sharing is worth understanding because it trades time for area: one multiplier can serve several multipliers in the pipeline if they are never needed at the same time, at the cost of a control mechanism and extra delay.

Power Optimisation

• Clock gating: switch off circuits that are not in use
• Voltage scaling: lower the operating voltage
• Frequency scaling: lower the operating frequency
• Sleep modes: power a part of the circuit down completely

Clock gating is the most effective of these in practice, because in a modern chip the clock net reaches every sequential element and toggles continuously regardless of whether anything useful happens. Halving the supply voltage roughly halves the dynamic power, which is why the power cost of a chip is dominated by the CV²f term and why voltage scaling has been the main lever for a decade.

Practical Applications

Processor Design

• Instruction decoding: turns an instruction into control signals
• Address calculation: computes a memory address
• Condition evaluation: implements branches and jumps
• Datapath: connects the functional units to one another

All four are combinational except for the state that feeds them, which is what makes the processor a mixture of the two kinds of circuit rather than one or the other.

Communication Systems

• Encoding and decoding: data encoding and error detection
• Protocol handling: the implementation of a communication protocol
• Routing: to route data packets
• Flow control: to control the data transfer rate

Control Systems

• State machines: the state transitions of a control system
• Timing control: precise control over time
• Feedback control: control based on the output
• Safety and protection: fault detection and protection

A state machine is the clearest example of sequential logic in the wild: a finite set of states, a table of transitions between them, and flip-flops holding the current state.

---

Glossary