Digital Logic
This section is about digital logic. Here is an example of an integrated circuit  a chip:
This is a 7404. It is in a package which has 14 pins used to connect it into a circuit, with 7 on each side.
Which pin is connected to what inside the package? The pinout diagram shows us.
Two pins are used to supply power. Pin 7 is the ground connection, and pin 14, labelled Vcc, is used to connect to a power supply at around +5 volts.
The package contains 6 NOT gates, also called inverters. For example one gate is connected between pins 1 and 2. Pin 1 is the input to a gate, and pin 2 is the output.
The inside of the package does not actually look like that. This shows the chip (actually a 7400) under a microscopic:
But that image does not help if we are designing a logic circuit. We need the pinout, not an actual image.
This is an example of abstraction. We are interested in what logic gates do, not how they work.
The 7400 series of chips started around 1970, containing around 100 transistors. They currently retail at about 30 pence each.
Current processor chips are far more complex. Intel's IA64 chips contain around 1 billion transistors. However these are still combinations of the basic logic gates described here.
A circuit diagram, sometimes called a schematic, shows how electrical components are connected. These components include power supplies, resistors, capacitors and transistors.
A logic circuit is different. It shows only basic gates and sometimes, large units such as shift registers. We ignore power supply connections, for clarity. We do not show what is inside a logic gate.
We also think of these gates as idealised models. For example, real gates take a few nanoseconds to switch state. This limits the maximum clock speed to a few GHz. But is this work we ignore such issues.
A truth table is used to show what the output of a logic circuit will be.
The output depends only on the combination of inputs (not on previous inputs). This is why it is called combinational logic.
A truth table has
A column for each input bit
A column for each output bit
Possibly columns showing truth values at internal connection points
There is a row for every combination of input bits. For 1 input, that is just 2 rows  for 0 and 1.
For 2 inputs, there are 4 combiations  00, 01, 10 and 11
3 inputs have 8 combinations  000, 001, 010, 011 and so on.
If there are n inputs, there are 2n rows.
Many examples follow.
The basic gates are little use by themselves, but they are the building blocks to construct useful devices.
This is shown in a logic diagram like this:
There is one input, and one output. In an actual device, the input would be a wire carrying some voltage. This might be around 0 volts or 5 volts. We think of 0 volts as a 0 bit, or logic false, and 5 volts as a 1 bit, or logic true. Or with different types of chips, the actual volages might be different, but we will still have a 0 state and a 1 state.
The output is a similar voltage signal. It would be connected as an input into other gates.
The truth table is simply:
Input 
Output 
0 
1 
1 
0 
An AND gate is shown as
and has a truth table:
Inputs 
Output 

0 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
1 
so this is the same as logical conjunction. Output is 0 unless both inputs are 1.
This is a 2input AND. We can have more inputs, but it is still conjunction. For example if we have 3 inputs, the output is 0 unless all inputs are 1.
An OR gate has curved input and pointed output like this:
and truth table:
Inputs 
Output 

0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
1 
so this is logical disjunction. Output is 1 if either or both inputs are 1.
Multiinput OR gates are the same  output is 1 if any input is 1.
This is exclusiveor. It is either but not both:
Inputs 
Output 

0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
0 
This is sometimes seen as 'not equal', since the output is 1 so long as the inputs are not equal  so 0 and 1 or 1 and 0.
This is notand  the opposite of a NAND gate:
Inputs 
Output 

0 
0 
1 
0 
1 
1 
1 
0 
1 
1 
1 
0 
NAND gates are easy to make, so many circuits are composed entirely of NAND gates
This is notor.
Inputs 
Output 

0 
0 
1 
0 
1 
0 
1 
0 
0 
1 
1 
0 
Draw truth tables of AND, OR, NAND, NOR and XOR twoinput gates
This is how to draw a truth table from a logic circuit. For example:
We have 3 input bits, A B and C, so we have 23 = 8 possible input combinations. We can make sure we have all combinations because they are the same as counting 0,1,2,3..7 in binary:
Inputs 

Output 

A 
B 
C 
S 
Q 
0 
0 
0 
0 
0 
0 
0 
1 
0 
1 
0 
1 
0 
0 
0 
0 
1 
1 
0 
1 
1 
0 
0 
0 
0 
1 
0 
1 
0 
1 
1 
1 
0 
1 
1 
1 
1 
1 
1 
1 
We work out the intermediate signal at S as an AND of A and B. So it is 0 unless A and B are both 1.
Then we work out Q as C OR S. So it is 1 if C or S or both are 1.
Different notations are used in mathematics, digital logic and programming. Usually these are:
Logical operator 
Mathematic logic 
Logic gates 
Programming ( in C and similar ) 
Conjunction : A AND B 
A ∧ B 
A.B 
A && B 
Disjunction : A OR B 
A ∨ B 
A + B 
A  B 
Negation : NOT A 
¬A 
A 
!A 
So for example the Boolean algebra expression
A.B + C.D
means A AND B OR C AND D.
This would be true (logic 1) if both A and B are 1, or C and D are 1, or both are 1.
Draw the truth table of A + C.D
For example if the Boolean algebra expression is
Q = A.B + C.D
This is A and B, or C and not D. So the circuit is:
Draw the logic circuit of Q = A.B + C.D
For example
Q = A.B + C
is
This is a logic circuit with 2 inputs and 2 outputs:
The truth table would be:
Input A 
Input B 
sum 
carry 
0 
0 
0 
0 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
0 
1 
The idea is that this matches what is required when we add 2 bits (the A and B). 0+0=0. 0+1=1. 1+0=1. 1+1=0, and 1 carry.
Why a half adder? Suppose we add two numbers in binary : 12 +7:






Decimal 

0 
1 
1 
0 
0 
12 

0 
0 
1 
1 
1 
7 
Sum 
1 
0 
0 
1 
1 
19 
Carry 
1 
1 
0 
0 


In a column, we need to add 2 bits, and also the carry in from the column on the right. The result is the sum, and also a carry out.
This means in a column we need to add:
The 2 bits, and
The carry in
so in fact there are 2 additions. We have a half adder, but we need 2 of these to make a full adder.
This uses two half adders as building blocks, both with 2 bit inputs, and sum and carry outputs. We combine them as shown to add 2 bits and a carry in, producing a sum and carry out.
This means we have a logic circuit which can add bits. A current processor uses 64 bit data, so would contain 64 full adders so it can execute a software ADD instruction.
Inputs A and C are inverted. If the input ABCD is 0101, then inputs into the first 2 ANDs will all be 1s, and the output will be 1. For any other input (say 0011 ) the output will be 0.
So this circuit decodes 0101. It 'recognises' 0101.
Circuits like this are used in a processor to recognise instruction opcodes. An opcode is a bit pattern, and each one can be decoded by a circuit like this. The output would then mean that instruction was executed.
Draw the logic circuit to decode A.B.C
As an example
A.B + A.C = A.(B+C) (distributive law)
The left hand side is two ANDs and one OR, but the right is just one AND and one OR:
How do we know these two circuits are the same? By drawing the truth table of both and seeing they have the same output for the same input.
Suppose we need
Q = A+A.B+C
we can take out the common factor of A:
Q = A.(1+B)+C
1+B means 1 OR B. This is always true, so
Q = A.1 + C
A.1 means A AND 1. If A is true, this is true. If A is false it is false. So A.1 is just the same as A, so
Q = A + C
so Q = A+A.B+C does not depend on B. We do not need it as an input.
Draw the truth table of Q = A+A.B+C to show it does not depend on B
These are two important identities:
A+B = A.B
A.B = A + B
Draw the truth tables of A+B and A.B
Draw the logic diagrams of A.B and A + B
This is a technique to produce a logic circuit, with minimum gates, from a requirement in the form of a truth table.
The process is:
Start with a truth table, for all input combinations and required output.
Draw a table with rows some input bits and columns the other bits.
Have both in Gray code order  which means changing only 1 bit at a time
Fill in the required output from the truth table.
Identify blocks of 1 bits Blocks should be as large as possible, with sizes power sof 2 IOW 1, 2, 4..
Identify each block as an AND of input bits
OR these together
For example, if with 4 input bits the requirement is:
Inputs 
Output 

A 
B 
C 
D 
Q 
0 
0 
0 
0 
0 
0 
0 
0 
1 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
1 
0 
1 
0 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
0 
0 
0 
1 
1 
1 
0 
1 
0 
0 
0 
0 
1 
0 
0 
1 
1 
1 
0 
1 
0 
0 
1 
0 
1 
1 
1 
1 
1 
0 
0 
0 
1 
1 
0 
1 
1 
1 
1 
1 
0 
0 
1 
1 
1 
1 
1 
The transformed table is:


AB 





00 
01 
11 
10 


CD 
00 
0 
0 
0 
0 
not C 
not D 
01 
0 
0 
1 
1 
D 

11 
1 
0 
1 
1 
C 

10 
1 
0 
0 
0 
not D 



not A 
A 





not B 
B 
not B 


Inputs are in blue, and outputs in yellow. Check the order of the input bits.
The red block corresponds to A.D = A and D
The blue block is A.B.C = not A and not B and C
We can OR these. So the logic circuit is:
Sequential logic circuits have output which depends on previous inputs, as well as the current set. In other words these circuits have memory. They also have state.
In terms of finite state machines, combinational logic has only one state. Sequential logic circuits have more than one.
A flipflop, or latch, stores a bit. In other words it has two states, outputing a 0 or a 1. It stays in that state, unless it gets an input to change state.
One type is a SR flipflop. The SR is for 'set' 'reset'. One design is here:
Suppose S and R are 0. Then a is 1. Suppose Q is 1. Then the OR outputs a 1, so a and b are 1, so Q is 1. So this is a stable state  it will stay like this.
Or maybe Q is 0. S is 0, so b is 0. So the AND gate outputs 0. So Q is 0. This is the other stable state.
Now suppose the S inputs goes to 1, and R stays at 0. b will be 1, and so is a, so the AND gate outputs a 1. So this flips to the 1 state, and it will remain there if S goes back to 0.
Or suppose R goes to 1 (and S is 0). a is 0, so Q is 0. The OR gate has 2 0 inputs, so b is 0. This has reset the state to Q = 0.
If S and R both go to 1 then a is 0, so Q is 0. So R has priority.
Real chips are usually made using only NOR and NAND gates. SR latches can be made from these, but then the S=1 and R=1 condition is unstable and not allowed.
This is fixed in a JK latch.
So this circuit holds 1 bit in storage, and can be flipped to a 1 or a 0. If we have 64 of these, we have a register  as in a processor.
This circuit has a capacitor on the inverter input. This device stores electrical charge. It takes time to charge up and discharge.
Suppose the capacitor is discharged  so 0 voltage. The input to the invertor is 0, so the output is 1. So the capacitor will charge up (given time), the input becomes 1, the output 0, and the capacitor will discharge. How quickly depends on how large the capacitor is.
So this circuit is unstable. The output will be a train of 1 and 0 pulses. Such a signal is used as a clock.
This is not a practical circuit  for one reason the clock speed would not be stable enough. But it shows the idea of a digital clock outputting a train of 1 and 0 signals. Processors currently use clocks generating around one thousand million pulses per second ( 1 GHz ).
This is a development from an SR flipflop, which when made from NANDs has an illegal S=1 R=1 state. The solution is to have only one input, and the inverted form, as the 2 inputs to an SR latch. Then they cannot both be 1 at the same time.
We can also only let any inputs in on a clock 1 signal. So we get this:
So this stores one bit. The input is D, and on a clock 1, this is stored into the latch. On a clock 0, the input is ignored.