Complex logic gates

Logic gates can be built up into chains of logical decisions. Some logic gates may have more than two inputs. The diagram below shows a complex logic gate combining three simple gates.

NOT gate has input A, output D. AND gate has inputs B&C, output E. OR gate has inputs D&E, output Z

Altogether there are three inputs and eight possible outcomes. To solve the truth table below, first find D, then E and finally Z. Complete a whole columnn before moving on to the next column. D depends only on A, E depends on B and C, and Z depends on E or D.

This logic gate truth table is written as:

ABCD = NOT AE = B AND CZ = D OR E
000101
001101
010101
011111
100000
101000
110000
111011

This circuit would be written as Z = D OR E or Z = NOT A OR (B AND C).

Logic gates in the CPU

The following example demonstrates how the ALU uses logic gates to perform binary addition. It combines two gates, in parallel. There are two inputs and each gate has a single output - so in total there are two outputs, with four possible outcomes.

Diagram of a boolean half adder gate

The Boolean expressions for this circuit are:

S = A XOR B

C = A AND B

The truth table for this circuit is:

ABS = A XOR BC = A AND B
0000
0110
1010
1101

Half adder - binary addition

This gate models a 1-bit binary sum. The possible calculations of a 1-bit binary sum are:

  1. 0+0=0
  2. 0+1=1
  3. 1+0=1
  4. 1+1=10

S and C together represent the output of the sum of 'A + B'. Each gate can only output a single bit - a number with one place value. 1+1 creates 10 which needs 2 place values, so this is an overflow number. In overflow sums, the result is recorded as 0 and the 1 has to be carried. S represents the recorded 0 and C represents the carried 1.

This configuration is called a binary half adder. It is a good way to begin to understand how an ALU is able to perform arithmetic. To perform complete arithmetic that can take account of carry bits and add more than two bits together, two half adders must be combined together to make a full adder.

An ALU uses millions or billions of circuits like this cascaded together to perform calculations.

Binary addition and overflow errors is explained further in Numbers and binary addition.