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.

NOT

$$f=\bar{A}$$

AND

$$f=A\cdot B$$

OR

$$f=A+B$$

XOR

$$f=A\oplus B$$

NAND

$$f=\overline{A\cdot B}$$

NOR

$$f=\overline{A+B}$$

X-NOR

$$f=\overline{A\oplus B}$$

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.

$$f=\bar{A}\cdot B+A\cdot \bar{B}$$

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.

$$\begin{gathered} P=A\cdot B \\ Q=A\cdot B \\ R=A\cdot C \end{gathered}$$

$$f=P+Q+R=A\cdot B+A\cdot B+A\cdot C$$

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.

Taking only the rows that have an output of 1:

• The first row of the table: $\bar{A}\cdot \bar{B}\cdot \bar{C}$
• The second row: $\bar{A}\cdot \bar{B}\cdot C$
• Fifth: $A\cdot \bar{B}\cdot \bar{C}$
• Seventh: $A\cdot B\cdot \bar{C}$
• Eight: $A\cdot B\cdot C$

Summing the products yields:

$$f=(\bar{A}\cdot \bar{B}\cdot \bar{C})+(\bar{A}\cdot \bar{B}\cdot C)+(A\cdot \bar{B}\cdot \bar{C})+(A\cdot B\cdot \bar{C})+(A\cdot B\cdot C)$$

Boolean Algebra Laws

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

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

• $A+BC=(A+B)(A+C)$
• $A(B+C)=AB+AC$
• $A(A+B)=A$
• $A+AB=A$

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.

$$f=(\overline{X+Y})\cdot (\overline{\bar{X}+Y})$$ $$f=(\bar{X}\cdot \bar{Y})\cdot (\overline{\bar{X}+Y})\text{De Morgan OR form}$$ $$f=(\bar{X}\cdot \bar{Y})\cdot (X\cdot \bar{Y})\text{De Morgan AND form}$$ $$f=\bar{X}\cdot \bar{Y}\cdot X\cdot \bar{Y}\text{Remove brackets (associative law)}$$ $$f=\bar{X}\cdot X\cdot \bar{Y}\cdot \bar{Y}\text{Re-order (commutative law)}$$ $$f=0\cdot \bar{Y}\text{Inverse and idempotent laws}$$ $$f=0\text{Null law}$$

Example 2

$$f=X+\bar{Y}+\bar{X}\cdot Y+(X+\bar{Y})\cdot \bar{X}\cdot Y$$ $$f=X+\bar{Y}+\bar{X}\cdot Y+X\cdot \cdot \bar{X}\cdot Y+\bar{Y}\cdot \bar{X}\cdot Y\text{Distributive law}$$ $$f=X+\bar{Y}+\bar{X}\cdot Y+0+0\text{Inverse AND law}$$ $$f=X+(\bar{Y}+\bar{X})(\bar{Y}+Y)\text{Distributive law}$$ $$f=X+(\bar{Y}+\bar{X})\cdot 1\text{Inverse law}$$ $$f=X+\bar{Y}+\bar{X}\text{Removing 1 and brackets (identity and associative laws)}$$ $$f=\bar{Y}+1\text{Inverse OR law}$$ $$f=1\text{Null law}$$

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

• 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
• Adjacency also wraps around

The function $f=AB\bar{C}D+A\bar{B}\bar{C}D+\bar{A}\bar{B}CD+\bar{A}BCD$ 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 $f=\bar{A}\bar{B}\bar{C}+\bar{A}BD+BCD$ or $f=\bar{A}\bar{B}\bar{C}+\bar{A}\bar{C}D+BCD$ (both are equivalent)

Sometimes it is not possible to minimise an expression. the map below shows an XOR function $f=(A\oplus B)\oplus (C\oplus D)$

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

1-Bit Half Adder

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

1-Bit Full Adder

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

N-Bit Full Adder

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

N-Bit Adder/Subtractor

• To convert an adder to an adder/subtractor, we need a control input $Z$ such that:
  • $Z=0\Rightarrow S=A+B$
  • $Z=1\Rightarrow S=A-B$
• $-B$ is calculated using two's complement
  • Invert the N bit binary number B by doing $Z\oplus B$
  • 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 $\overline{\text{enable}}$
• It is important to be aware of this, as ins and outs must comform to the same standard

• 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

Multiplexers & De-Multiplexers

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

$$Y=X_0{\bar{S}}_0{\bar{S}}_1+X_1{\bar{S}}_0{S}_1+X_2{S}_0{\bar{S}}_1+X_3{S}_0{S}_1$$

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

$$Y_0=A+{\bar{S}}_0{S}_1+S_0{\bar{S}}_1+S_0{S}_1=A+S_1+S_0$$

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.

• $\bar{S}$ and $\bar{R}$ are active low set and reset inputs
• $Q$ is set high when $\bar{S}=0$ and $\bar{R}=1$
• $Q$ is reset (to zero) when $\bar{R}=0$ and $\bar{S}=1$
• If $\bar{S}=\bar{R}=1$ then $Q$ does not change
• If both $\bar{S}$ and $\bar{R}$ are zero, this is a hazard condition and the output is invalid

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
• $D=Q$ when enabled, otherwise $Q$ does not change ($Q=Q$)
• When enabled, data on $D$ goes to $Q$

Clocked Flip-Flop

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

• $\uparrow$ means rising edge responding

N-bit Register

• A multi-bit memory circuit built up from d-type latches
• The number on $A_{N-1}{A}_{N-2}...A_1{A}_0$ is stored in the registers when the clock rises
• The stored number appears on the outputs $Q$
• $Q$ 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 $\overline{E1}=0$, A will be placed on the bus
• When $\overline{E2}=0$, 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.