# Digital Logic

Digital logic is about reasoning with systems with two states: on and off (0 and 1 (binary)).

## Basic Logic Functions

Some basic logic functions, along with their truth tables.

Af
01
10

ABf
000
010
100
111

ABf
000
011
101
111

ABf
000
011
101
110

ABf
001
011
101
110

ABf
001
010
100
110

ABf
001
010
100
111

### Logic Gates

Logic gates represent logic functions in a circuit. Each logic gate below represents one of the functions shown above.

### Logic Circuits

Logic circuits can be built from logic gates, where outputs are logical functions of their inputs. Simple functions can be used to build up more complex ones. For example, the circuit below implements the XOR function.

Another example, using only NAND gates to build XOR. NAND (or NOR) gates can be used to construct any logic function.

Truth tables can be constructed for logic circuits by considering intermediate signals. The circuit below has 3 inputs and considers 3 intermediate signals to construct a truth table.

ABCPQRf
0000000
0010000
0100000
0110101
1000000
1010011
1101001
1111111

Truth tables of circuits are important as they enumerate all possible outputs, and help to reason about logic circuits and functions.

## Boolean Algebra

• Logic expressions, like normal algebraic ones, can be simplified to reduce complexity
• This reduces the number of gates required for their implementation
• The less gates, the more efficient the circuit is
• More gates is also more expensive
• Sometimes, only specific gates are available too and equivalent expressions must be found that use only the available gates
• Two main ways to simplify expressions
• Boolean algebra
• Karnaugh maps
• The truth table for the expression before and after simplifying must be identical, or you've made a mistake

### Expressions from Truth Tables

A sum of products form of a function can be obtained from it's truth table directly.

ABCf
0001
0011
0100
0110
1001
1010
1101
1111

Taking only the rows that have an output of 1:

• The first row of the table:
• The second row:
• Fifth:
• Seventh:
• Eight:

Summing the products yields:

### Boolean Algebra Laws

There are several laws of boolean algebra which can be used to simplify logic expressions:

NameAND formOR form
Identity Law
Null Law
Idempotent Law
Inverse Law
Commutative Law
Associative Law
Distributive Law
Absorption Law
De Morgan's Law
• Can go from AND to OR form (and vice versa) by swapping AND for OR, and 0 for 1

Most are fairly intuitive, but some less so. The important ones to remember are:

### De Morgan's Laws

De Morgan's Laws are very important and useful ones, as they allow to easily go from AND to OR. In simple terms:

• Break the negation bar
• Swap the operator

### Example 1

When doing questions, all working steps should be annotated.

## Karnaugh Maps

• Karnaugh Maps (k-maps) are sort of like a 2D- truth table
• Expressions can be seen from the location of 1s in the map
ABf
00a
01b
10d
11c

• Functions of 3 variables can used a 4x2 or 2x4 map (4 variables use a 4x4 map)

• Adjacent squares in a k-map differ by exactly 1 variable
• This makes the map gray coded

The function is shown in the map below.

### Grouping

• Karnaugh maps contain groups, which are rectangular clusters of 1s -
• To simplify a logic expression from a k-map, identify groups from it, making them as large and as few as possible
• The number of elements in the group must be a power of 2
• Each group can be described by a singular expression
• The variables in the group are the ones that are constant within the group (ie, define that group)

Sometimes, groups overlap which allow for more than one expression

The function for the map is therefore either or (both are equivalent)

Sometimes it is not possible to minimise an expression. the map below shows an XOR function

### Don't Care Conditions

Sometimes, a certain combination of inputs can't happen, or we dont care about the output if it does. An X is used to denote these conditions, which can be assumed as either 1 or 0, whichever is more convenient.

## Combinatorial Logic Circuits

Some useful circuits can be constructed using logic gates, examples of which are shown below. Combinatorial logic circuits operate as fast as the gates operate, which is theoretically zero time (realistically, there is a nanosecond-level tiny propagation delay).

• Performs the addition of 2 bits, outputting the result and a carry bit.

ABSumCarry
0000
0110
1010
1101

• Adds 2 bits plus carry bit, outputting the result and a carry bit.

Carry inABSumCarry out
00000
00101
01001
01110
10001
10110
11010
11111

• Combination of a number of full adders
• The carry out from the previous adder feeds into the carry in of the next

• To convert an adder to an adder/subtractor, we need a control input such that:
• is calculated using two's complement
• Invert the N bit binary number B by doing
• Add 1 (make the starting carry in a 1)

### Encoders & Decoders

• A decoder has binary input pins, and one output pin per possible input state
• eg 2 inputs has 4 unique states so has 4 outputs
• 3 inputs has 8 outputs
• Often used for addressing memory
• The decoder shown below is active low
• Active low means that 0 = active, and 1 = inactive
• Converse to what would usually be expected
• Active low pins sometimes labelled with a bar, ie
• It is important to be aware of this, as ins and outs must comform to the same standard

000111
011011
101101
111110
• Encoders are the opposite of decoders, encoding a set of inputs into outputs
• Multiple input pins, only one should be active at a time
• Active low encoder shown below

011100
101101
110110
111011

### Multiplexers & De-Multiplexers

Multiplexers have multiple inputs, and then selector inputs which choose which of the inputs to put on the output.

Y
00
01
10
11

De-Multiplexers are the reverse of multiplexers, taking one input and selector inputs choosing which output it appears on. The one shown below is active low

00A111
011A11
1011A1
11111A

Multiplexers and De-Multiplexers are useful in many applications:

• Source selection control
• Share one communication line between multiple senders/receivers
• Parallel to serial conversion
• Parallel input on X, clock signal on S, serial output on Y

## Sequential Logic Circuits

A logic circuit whose outputs are logical functions of its inputs and it's current state

### Flip-Flops

Flip-flops are the basic elements of sequential logic circuits. They consist of two nand gates whose outputs are fed back to the inputs to create a bi-stable circuit, meaning it's output is only stable in two states.

• and are active low set and reset inputs
• is set high when and
• is reset (to zero) when and
• If then does not change
• If both and are zero, this is a hazard condition and the output is invalid
QP
00XX
0110
1001
11XX

The timing diagram shows the operation of the flip flop

### D-Type Latch

A D-type latch is a modified flip-flop circuit that is essentially a 1-bit memory cell.

• Output can only change when the enable line is high
• when enabled, otherwise does not change ()
• When enabled, data on goes to
Enable
00
01
1001
1110

### Clocked Flip-Flop

There are other types of clocked flip-flop whose output only changes on the rising edge of the clock input.

• means rising edge responding

### N-bit Register

• A multi-bit memory circuit built up from d-type latches
• The number on is stored in the registers when the clock rises
• The stored number appears on the outputs
• cannot change unless the circuit is clocked
• Parallel input, parallel output

### N-bit Shift Register

• A register that stores and shifts bits taking one bit input at a time
• Serial input, parallel output
• When a clock transition occurs, each bit in the register will be shifted one place
• Useful for serial to parallel conversion

### N-bit Counter

• The circles on the clock inputs are inverted on all but the first
• Each flip-flop is triggerd on a high -> low transition of the previous flip-flop
• Creates a counter circuit

Output is 0000, 1000, 0100, 1100, 0010, etc...

• The first bit swaps every clock
• 2nd bit swaps every other clock
• 3rd bit swaps every fourth clock
• etc...

## Three State Logic

• Three state logic introduces a third state to logic - unconnected
• A three-state buffer has an enable pin, which when set high, disconnects the output from the input
• Used to prevent connecting outputs to outputs, as this can cause issues (short circuits)

This can be used to allow different sources of data onto a common bus. Consider a 4-bit bus, where 2 4-bit inputs are connected using 3-state buffers. Only one of the buffers should be enabled at any one time.

• When , A will be placed on the bus
• When , B will be placed on the bus

## Physical Implementations

Logic gates are physical things with physical properties, and these have to be considered when designing with them. Typical voltage values for TTL (Transistor-Transistor Logic):

• 5v - max voltage
• 2.8v - minimum voltage for a logical 1
• 2.8-0.8v - "forbidden region", ie voltages in this region are undefined
• 0.8-0v - voltage range for a logical 0

### Propagation Delay

• Logic gates have a propagation delay, the amount of time it takes for the output to reflect the input
• Typically a few nanoseconds or less
• This limits the speed at which logic circuits can operate
• Delay can be reduced by increasing density of gates on an IC

### Integrated Circuits

• Elementary logic gates can be obtained in small ICs
• Programmable deviced allow large circuits to be created inside a single chip
• PAL - Programmable Array Logic
• One-time programmamble
• PLA - Programmable Logic Array
• Contains an array of AND and OR gates to implement any logic functions
• FPGA - Field Programmable Gate Array
• Contains millions of configurable gates
• More modern

#### PLA example

A PLA allows for the implementation of any sum-of-products function, as it has an array of AND gates, then OR gates, with fuses that can be broken to implement a specific function.