Digital Logic

Table of Contents

 

Chips and gates

 

Image2This 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.

Image1

Which pin is connected to what inside the package? The pin-out 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.

Image3The 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 pin-out, not an actual image.

This is an example of abstraction. We are interested in what logic gates do, not how they work.

Current digital logic

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.

Logic circuits and circuit diagrams

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 nano-seconds to switch state. This limits the maximum clock speed to a few GHz. But is this work we ignore such issues.

 

Combinational logic

Truth tables

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

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

The basic gates are little use by themselves, but they are the building blocks to construct useful devices.

NOT gate

This is shown in a logic diagram like this:

Image4

 

 

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

 

AND

Image5An 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 2-input 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.

OR

Image6An 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.

Multi-input OR gates are the same - output is 1 if any input is 1.

XOR

Image7

This is exclusive-or. 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.

 

NAND

Image8

This is not-and - 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

NOR

Image9

This is not-or.

 

Inputs

Output

0

0

1

0

1

0

1

0

0

1

1

0

 

Draw truth tables of AND, OR, NAND, NOR and XOR two-input gates

Drawing truth tables

This is how to draw a truth table from a logic circuit. For example:

Image10

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.

 

Boolean algebra notation

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

Logic circuit from Boolean algebra

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:

Image18

Draw the logic circuit of Q = A.B + C.D

Boolean expression from circuit

For example

Q = A.B + C

is

Image19 

 

 

 

 

Half adder

Image11

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:

  1. The 2 bits, and

  2. 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.

Full adder

Image12This 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.

Decoder

Image13

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 op-codes. An op-code 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

 

Boolean algebra identities

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:

Image20How 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

de Morgan's Laws

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

 

Karnaugh Maps

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:

  1. Start with a truth table, for all input combinations and required output.

  2. Draw a table with rows some input bits and columns the other bits.

  3. Have both in Gray code order - which means changing only 1 bit at a time

  4. Fill in the required output from the truth table.

  5. Identify blocks of 1 bits Blocks should be as large as possible, with sizes power sof 2 IOW 1, 2, 4..

  6. Identify each block as an AND of input bits

  7. 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:

Image17

Sequential logic

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.

S R and J K flip-flop

A flip-flop, 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 flip-flop. The SR is for 'set' 'reset'. One design is here:

Image14

 

 

 

 

 

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.

Clocks

Image15

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 ).    

D type latch

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:

Image16

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.