Logic Circuits

Logic circuits use two different values of a physical quantity, usually voltage, to represent the boolean values true (or 1) and false (or 0). Logic circuits can have inputs and they have one or more outputs that are, at least partially, dependent on their inputs. In logic circuit diagrams, connections from one circuit's output to another circuit's input are often shown with an arrowhead at the input end.

In terms of their behavior, logic circuits are much like programming language functions or methods. Their inputs are analogous to function parameters and their outputs are analogous to function returned values. However, a logic circuit can have multiple outputs.

There are two basic types of logic circuitry: combinational circuitry and state circuitry.

These two types of circuitry work together to make up a processor datapath.

Processor Datapath

A processor's datapath is conceptually organized into two parts:

  • State elements hold information about the state of the processor during the current clock cycle
  • Combinational logic determines the state of the processor for the next clock cycle

This diagram, like most diagrams on this web site, adheres to the following conventions:

  • Control signals are colored blue.
  • Clock signals are colored orange.

Combinational Circuitry

The output of combinational circuitry depends only on the current values of its input. Combinational circuitry is conceptually constructed from basic logic gates: AND gates, OR gates, XOR gates, and inverters. The outputs of gates in combinational circuitry is never fed back directly to earlier inputs.

Basic logic gates can be combined to form a variety of higher-level units:

  • Routing
    • multiplexers — have several data input signals and a control input. The output is identical to one of the inputs. The value of the control signal determines which one.
    • demultiplexers — have one data input signal, a control input and several output signals. All of the output signals are 0 (false) except for the one selected by the control input. The selected output is identical to the data input.
  • Computational
    • full adders — perform a single column of a binary addition. They are the primary building block for multi-bit adders and subtracters.
    • adders and subtracters — add or subtract two binary or two's complement numbers. A subtracter is just an adder with extra circuitry to do a two's complement operation on one of the inputs. Usually they are designed to do either addition or subtraction as directed by a control signal.
    • comparators — compare two binary or two's complement numbers.

Adders, subtracters, and comparators are not described here. They are described in Integer Addition and Subtraction.

Basic Gates

Combinational circuitry is conceptually constructed from basic logic gates: AND gates, OR gates, XOR gates, and inverters. Inverters are most often displayed as small circles on inputs or outputs of logic elements.

AND Gates

An AND gate can conceptually have any number of inputs. Its output is true when all of its inputs are true. A 2-input AND gate is shown to the left.

AND Control

An AND gate is frequently used to control a signal — turn it on or off depending on the value of control signals. The AND gate to the left is set up to control the X signal using two control signals S1 and S0.

The small circle on the S1 input means the S1 signal is inverted before it goes into the AND gate.

OR Gates

An OR gate can conceptually have any number of inputs. Its output is true when any one of its inputs is true. A 2-input OR gate is shown to the left.

XOR Gates

An XOR (eXclusive OR) gate has two inputs. Its output is true when one of its inputs, but not both, are true. An XOR gate is shown to the left.

XOR Control

An XOR gate is sometimes used to control a signal — invert it or not depending on the value of a control signal. The XOR gate to the left is set up to control the X signal using the control signal Inv.

The most important use of an XOR gate as a control occurs in the implementation of an adder/subtracter, where XOR gates are used to control complementing one of the numbers. Complementing a binary number is part of a 2's complement operation, which has the effect of negating the number.

Routing Elements

There are two basic types of routing elements: multiplexers and demultiplexers. Multiplexers are much more common in high-level views of processor circuitry.

Multiplexers

A multiplexer is a combinational (stateless) logic circuit for selecting among several possible input signals. Patterson and Hennessey use the symbol to the left for a multiplexer.

This multiplexer has four signal inputs: W, X, Y, and Z. A multiplexer can in principle have any number of signal inputs. The control or select input Sel determines which of the signal inputs appears as the output Out. It has as many bits as needed for the selection. One bit suffices for just 2 signal inputs, 2 bits suffices for 3 or 4 signal inputs, and 3 bits suffices for 5 to 8 signal inputs.

The multiplexer output Out can be a multi-bit signal. Each of the signal inputs has the same number of bits as the output.

Multiplexer Implementation

The multiplexer implementation uses an AND gate for each data input. This AND gate is configured to control its data input — pass it to the output only when the select signal matches its input number. The AND outputs are then combined with an OR gate.

If the multiplexer has multi-bit input and output data signals then this circuitry is repeated once for each bit. The select signal is connected to each replication.

Demultiplexers

A demultiplexer routes a single data input signal to one of several different data outputs. That is, one of its outputs is identical to the data input signal, while the other output signals are 0. The output that matches the input signal is determined by a control input signal.

A demultiplexer can in principle have any number of data outputs. The control input has as many bits as needed for the selection. One bit suffices for just 2 data outputs, 2 bits suffices for 3 or 4 data outputs, and 3 bits suffices for 5 to 8 data inputs.

The demultiplexer data input can be a multi-bit signal. Each of the data outputs has the same number of bits as the input.

Uses

Demultiplexers play an important role in the write ports of register banks — they route the write enable signal to the appropriate register. By doing so, the demultiplexer determines which register gets data written to it.

Demultiplexer Implementation

The demultiplexer implementation uses an AND gate for each data input. This AND gate is configured to control the data input — pass it to the output only when the select signal matches its input number.

If the demultiplexer has multi-bit input and output data signals then this circuitry is repeated once for each bit. The select signal is connected to each replication.

Computational Elements

The only computational element described here is a full adder. It is the basic building block of multi-bit adders and subtracters.

Full Adder

A full adder performs a single column of a binary addition. It has two inputs, X and Y for bits from the summands. It has another input, Ci for the carry from the column to the right.

The S output is the column sum. This output should be 1 whenever an odd number of the inputs are 1.

The Co output is the carry output, which is sent to the column to the left. This output should be 1 when at least two of the inputs are 1.

Full Adder Implementation

State Circuitry

The output of state circuitry does not just depend on its input — it also depends on the past history of its inputs. In other words, the circuitry has memory.

State circuitry includes anything that can "remember" bits of information. This includes memory, registers, and the program counter.

The basic element of state circuitry is a flip-flop. A flip-flop stores one bit of data. Multiple flip-flops can be combined to form a multi-bit state element called a register. Multiple registers can be combined into a register bank.

Flip-Flops

The flip-flop is the basic element of state circuitry. It has three inputs:

  • D - data to be written into the flip-flop
  • En - enables data to be written into the flip-flop
  • Cl - clock that determines when data is written into the flip-flop

A flip-flop has a single output:

  • Q - data out, the most recent data value written into the flip-flop

Flip-Flop Implementation

Registers

A register is just a multi-bit analog of flip-flop. It has three inputs:

  • D - data to be written into the register
  • En - enables data to be written into the register
  • Cl - clock that determines when data is written into the register

A register has a single output:

  • Q - data out, the most recent data value written into the register

These are the same inputs and output that a flip-flop has. The only difference is that the D input and the Q output are multi-bit signals.

As shown to the left, a register is implemented as a group of flip-flops that share their clock and enable signals.

Register Implementation

A register is implemented as a group of flip-flops that share their clock and enable signals.

Register Banks

A register bank is similar to memory in that it provides read and write access to words of data. For a register bank, the word of data is selected by a register number instead of an address.

A register bank consists of some registers together with circuitry for read and wite ports.

Read Ports

A read port provides read access to a selected word. It consists of two or three signals.

  • an input signal to specify the register number or memory address
  • an output signal for the selected word
  • if needed, a read enable control input

Write Ports

A write port provides write access to a selected word. It consists of two or three signals.

  • an input signal to specify the register number or memory address
  • an input signal for the value to be put into the selected word
  • if needed, a write enable control input

Processor Datapath Control

Processor datapath control signals can be classified according to which part of the processor they control:

  • State controls
  • Combinational controls

State Controls

All of the state elements are connected to the processor clock. Their state only changes at the start of a clock period. Control circuitry must generate the enable signals that control whether or not a state element changes state.

For example, many instructions write data to a destination register. The control signals need to enable a write to that register, but not enable a write to any of the other registers.

Combinational Logic Controls

The control signals for the combinational logic are frequently just controlling routing. Often these signals are applied to multiplexers.

For example, many instructions write a result to a register. A multiplexer is needed to select whether that data comes from a calculation (arithmetic and logic instructions) or from memory (load instructions).