DIGITAL LOGIC

Digital Logic

Article by:
Date Published:
Last Modified:

1. Overview

Digital logic is the study and application of the fundamentals in digital (binary) electronics, e.g. gates, flip-flops, state machines.

2. Logic Gates

Logic gate inputs are normally labelled as a single letter, starting with A (e.g. a three input AND gate would have inputs A, B and C). The output is normally labelled Y (in other material you may see this labelled X), unless you are using a flip-flop or latch, and the output is labelled Q.

There are a few different standards used to draw logic gates on schematics:

  • MIL-STD-806B (Graphic Symbols For Logic Diagrams): This most commonly used symbols for basic and/or/xor e.t.c gates is captured in this standard. Each gate has a unique shape and are easily distinguished on a large schematic with many gates. NOT logic is shown with a bubble.

  • IEC 60617 (ANSI/IEEE Std 91-1984): All the gates are IC-like rectangles with symbols inside to denote the function. NOT logic is shown with a flag on the pin rather than a bubble. Not as easy too quickly identify the gate as MIL-STD-806B, and not as widely used.

  • DIN 40700-24 (Graphical Symbols; Components For Precision Engineering Devices, Especially Clocks): Ever rarer than the MIL-STD-806B or IEC 60617 symbols, these are rarely seen. The 1976 Edition was released in June 1976. DIN symbols on this page are referenced to https://de.wikipedia.org/wiki/Logikgatter#Typen_von_Logikgattern_und_Symbolik.

This page uses the convention of TRUE or 1 to represent the logic state true, and FALSE or 0 to represent the logic state false.

2.1. NOT

Arguably the simplest logical gate (ignoring a buffer), a NOT gate (a.k.a. inverter) always outputs the opposite (complement) of the input. If the input is TRUE, the output is FALSE. If the input is FALSE, the output is TRUE.

not gate symbol
Figure 1. The symbols for a NOT gate (inverter).
Table 1. Truth table for an NOT gate.
Inputs Output

A

Y

0

1

1

0

And this gives rise to the simple equation for NOT logic:

\[\begin{align} Y = \overline{A} \end{align}\]

2.2. AND/NAND

An AND gate outputs TRUE only if all it’s inputs are TRUE. AND is also called logical conjunction[5].

and gate symbol
Figure 2. The symbols for an AND gate.
Table 2. Truth table for an AND gate.
Inputs Output

A

B

Y

0

0

0

0

1

0

1

0

0

1

1

1

The equation for the AND logic may be written in one of the following ways:

\[\begin{align} Y &= A \cdot B \ \text{(preferred)} \\ Y &= AB \\ Y &= A \& B \\ Y &= A \wedge B \\ \end{align}\]

An AND gate can be made using basic diode logic as shown in Figure 3.

and gate from diodes and resistors
Figure 3. An AND gate made from basic diode logic.

A NAND gate is just an AND gate but with the output inverted. This is shown in Figure 4 with the bubble at the output of the AND symbol.

nand gate symbol
Figure 4. The symbol for an NAND gate.
Table 3. Truth table for an NAND gate.
Inputs Output

A

B

Y

0

0

1

0

1

1

1

0

1

1

1

0

2.3. OR/NOR

A OR gate is TRUE if at least one input is TRUE. This means it is also outputs TRUE if all it’s inputs are TRUE. OR is also called logical disjunction[5].

or gate symbol
Figure 5. The symbol for an OR gate.
Table 4. Truth table for an OR gate.
Inputs Output

A

B

Y

0

0

0

0

1

1

1

0

1

1

1

1

The OR operation can be expressed in an equation in the following ways:

\[\begin{align} Y &= A + B \ \text{(preferred)} \\ Y &= A \vee B \\ Y &= A || B \\ \end{align}\]

A NOR gate is just a OR gate but with the output inverted (i.e. what you would get if you connected the output of an OR gate to an inverter). Just like the NAND gate, the NOR is gate is shown in Figure 6 and is just an OR gate symbol with a bubble on the output.

nor gate symbol
Figure 6. The symbols for a NOR gate.
Table 5. Truth table for an NOR gate.
Inputs Output

A

B

Y

0

0

1

0

1

0

1

0

0

1

1

0

The equation for an NOR gate:

\[\begin{align} Y = \overline{A + B} \end{align}\]

The OR gate be drawn using three equal diameter circles placed on a grid as shown in Figure 7. Segments of the circles perimeters are taken along with the addition of two horizontal line sections to form the classic OR gate shape[4].

how to draw the or gate
Figure 7. Diagram showing how to draw an OR gate from the segments of three equal diameter circles placed on a grid[4].

2.4. XOR

A 2-input XOR gate (exclusive OR) only outputs TRUE if one and only one of it’s inputs is also TRUE.

xor gate symbol
Figure 8. The symbols for a 2-input XOR (exclusive-or) gate.
Table 6. Truth table for a 2-input XOR gate.
Inputs Output

A

B

Y

0

0

0

0

1

1

1

0

1

1

1

0

Note The only difference in behaviour between an OR and XOR is when both inputs are TRUE. An OR gate outputs a TRUE in this case, whilst and XOR outputs a FALSE.

The symbol \(\bigoplus\) is used to represent XOR, as hence XOR can be written in the following ways:

\[\begin{align} Y &= (A \cdot \bar{B}) + (\bar{A} \cdot B) \\ Y &= (A + B) \cdot (\bar{A} + \bar{B}) \\ Y &= A \bigoplus B \\ \end{align}\]
xor gate made from and nand or
Figure 9. A XOR gate made from 1 AND, NAND and OR gate.

Figure 10 shows a XOR gate made exclusively from NAND gates.

xor gate made from nands
Figure 10. A XOR gate made exclusively from NAND gates.

You can also make a XOR gate exclusively from NOR gates, as shown in Figure 11. Note that the structure is similar to the all-NAND gate version of the XOR, but with the additional inverting gate on the output.

xor gate made from nors
Figure 11. A XOR gate made exclusively from NOR gates.

Whilst it is intuitive how a AND or OR gate should work with more than 2 inputs, that same cannot be said for a XOR gate. Should the output be TRUE only if exactly one input is TRUE? Should the output be TRUE if at least 1 but not all of the inputs are TRUE? Or should the output be TRUE if one input is TRUE, FALSE for 2 inputs TRUE, TRUE again for 3 inputs TRUE, e.t.c?

  1. Output TRUE only if 1 and only 1 input is TRUE. This is called a one-hot detector. However, this is rarely seen in practise.

  2. Output TRUE only if an odd number of inputs are TRUE. This is called a parity generator or modulo-2 adder. This is more commonly implemented behaviour for a XOR gate with more than 2 inputs.

XOR gates are used for:

  • Parity generators: A sequence of XOR gates can calculate the parity of block of data, which is used for simple single-bit error detection in some communication protocols (e.g. optional setting you can enable with UART)[3].

  • Correlation/sequence detection: XOR gates output FALSE if both inputs are the same. This behaviour can be utilized to perform correlation between two bit streams.

  • Cryptographic circuits.

XNOR is an XOR gate but with the output inverted.

xnor gate symbol
Figure 12. The symbols for a XNOR gate.
Table 7. Truth table for an XNOR gate.
Inputs Output

A

B

Y

0

0

1

0

1

0

1

0

0

1

1

1

3. What Are Logic Gates Built From?

3.1. Diode Logic (DL)

Diode logic (DL) is digital logic circuitry made from just diodes and resistors. It is a very simple (if not the simplest) way of constructing logic gates in a circuit. Diode logic is great for getting a basic theoretical understanding of how logic gates are realized, but is rarely used in practise due to fan-out, switching speed issues, and limited gate constructibility (more on this below)!. Also known as diode-resistor logic (DRL).

and gate from diodes and resistors
Figure 13. An AND gate made from basic diode logic.

Before long you’ll be struck with the solemn realization you can’t create a NOT gate (inverter) from pure diode logic (or any gates that require inverting capabilities, such as NAND or NOR gates). This limits you to being only able to make AND or OR gates, and hence it’s usefulness is severely limited. NOT gates are constructable as soon as you add switching elements, such as transistors. Resistor-transistor logic is the extension of diode logic but the addition of transistors.

3.2. Resistor-Transistor Logic (RTL)

Resistor-transistor logic (RTL) is one of the most basic families of digital logic (only diode logic beats it in terms of simplicity). It uses resistors and BJTs to build the basic gates required for digital logic. Now days it is completely superseded by logic families such transistor-transistor logic (TTL) and CMOS. However, it serves as a great place to introduces readers on how logic gates are built from discrete components.

rtl logic inverter
Figure 14. A very basic logic "inverter" made from RTL.

Advantages:

  • Very basic to create.

  • Used a minimal amount of transistors (this was important in the early days of IC fabrication as transistors were expensive!)

Disadvantages:

  • Very limited fan-out.

  • Significant power consumption: When the transistors are switched on.

  • Weak drive in one direction: Single transistor strongly drives output only in one direction, pull-up/down resistor is used in opposite direction.

  • Poor noise margins.

rtl logic nor gate
Figure 15. Schematic of a RTL NOR gate. When both inputs are LOW, neither transistor is on and the output is pulled HIGH by \(R_C\). Any HIGH input will turn on a transistor, which will drive the output LOW.

3.3. Diode-Transistor Logic (DTL)

TODO: Add info here.

3.4. Transistor-Transistor Logic (TTL)

The inputs of TTL logic are the emitters of BJTs.

3.5. CMOS

Represented by AC/ACT in part numbers, or HC/HCT for high-speed equivalents. The T in the logic subfamily name signifies the parts have TTL-compatible inputs.

3.6. Comparison

Logic Subfamily Description Comment

AC

CMOS.

CVSL

Cascode voltage switch logic.

HC

HCT

High-speed CMOS with TTL-compatible inputs.

Only works with a +5V power supply. Interestingly, still slower than original TTL.

IIL

Integrated injection logic.

LS

Low-power Schottky.

PTL

4. Logic Gate Part Numbers

Texas Instruments introduced the SN74xx series of logic ICs in the 1960s, using TTL logic. These parts became very popular and many other manufactures began making pin-compatible parts. They kept the 74xx section of the part number to aid identification, and hence the 74xx is somewhat standardized across the industry.

The 5400 series is the military rated version of the 7400 series. The 4000 series is the newer CMOS alternative to the 7400 TTL logic. However (and which is somewhat confusing), newer 7400 parts can also be made using CMOS logic, for example, the 74HC4051 analogue multiplexer[2]. These parts commonly using the logic subfamily names HC or HCT.

Table 8. Part number descriptions for the popular TTL 74xx family of ICs.
Part Number Description Num. Units Input Output

74x00

Quad 2-input NAND gate

4

Normal

Push-pull

74x01

Quad 2-input NAND gate

4

Normal

Open-collector

74x02

Quad 2-input NOR gate

4

Normal

Push-pull

74x03

Quad 2-input NAND gate

4

Normal

Open-collector

74x04

Hex inverter gate

6

Normal

Push-pull

74x05

Hex inverter gate

6

Normal

Open-collector

74x06

Hex inverter gate

6

Normal

Open-collector, 30V/40mA

74x07

Hex buffer gate

6

Normal

Open-collector, 30V/40mA

74x08

Quad 2-input AND gate

4

Normal

Push-pull

74x09

Quad 2-input AND gate

4

Normal

Open-collector

74x10

Triple 3-input NAND gate

3

Normal

Push-pull

74x11

Triple 3-input AND gate

3

Normal

Push-pull

74x12

Triple 3-input NAND gate

3

Normal

Open-collector

74x13

Dual 4-input NAND gate

2

Schmitt trigger

Push-pull

74x4051

High-speed 8-channel analog multiplexer/demultiplexer

1

Analog

Analog

74x4052

Dual 4-channel analog multiplexer/demultiplexer

2

Analog

Analog

74x4053

Triple 2-channel analog multiplexer/demultiplexer

3

Analog

Analog

The x is a placeholder for the logic subfamily. For example, in 74LSxx the LS represent the low-power Schottky subfamily.

A company specific prefix may be added to the above part numbers depending on the manufacturer.

Prefix Company

<none>

Nexperia, Phillips

CD

Texas Instruments

DM

National Semiconductor

ID

IDT

M

STMicroelectronics

MC

OnSemi

MM

National Semiconductor

NLV

OnSemi

SN

Texas Instruments

TC

Toshiba

5. Flip-Flops

A flip-flop (a.k.a. latch, or bistable multivibrator) is a digital circuit which is able to store a single "bit" of information. It has two stable states (representing a digital 1 or 0), and they can be made to change state by manipulating digital inputs. Hence they are also called bistable multivibrators (two stable states). Flip-flops form the basic storage element in sequential logic.

Flip-flops can be either level-triggered (asynchronous, transparent, opaque) or edge-triggered (synchronous, clocked). Sometimes the word _latch_is exclusively used to refer to level-triggered flip-flops whilst flip-flop is reserved for edge-triggered ones only[1].

5.1. SR Latches

SR (Set-Reset) latches are the most basic form of flip-flop. It is level triggered.

sr latch from nor gates
Figure 16. An SR latch made from NOR gates.
Table 9. Characteristic table for a SR latch built from NOR gates.
S R \(Q_{next}\) Action

0

0

Q

Hold

0

1

0

Reset

1

0

1

Set

1

1

X

Not allowed

Driving both set and reset high is a forbidden state. A JK latch is just an extension of the SR latch where the circuit is modified to remove the forbidden state \(S = R = 1\) and instead cause the output to toggle.

SN74LS279 is a quad SR latch component by Texas Instruments. Two of the four latches have two set inputs, allowing for either to be active to set the latch (equivalent to an OR gate placed before a normal single set input SR latch).

SR latches can be used to make a switch debounce circuit.

5.1.1. How Does An SR Latch Work?

  1. \(R\) is HIGH and \(S\) is LOW: Since \(R\) is high, the output of the top NOR gate is LOW. This LOW feeds into the bottom NOR gate, along with \(S\) which is also LOW, thus the output of the bottom NOR gate is HIGH. This HIGH feeds into the top NOR gate, which will keep the circuit in this defined state, even if \(R\) is then brought LOW. This gives the SR latch it’s memory.

  2. \(R\) is LOW and \(S\) is HIGH: Because of the symmetry, the same things happens, but in reverse. \(Q\) is HIGH and \(\bar{Q}\) is LOW. Again, if \(S\) goes low, the SR latch "remembers" and keeps it’s outputs in the same state.

sr latch from nor gates states red black
Figure 17. (A): A SR latch in the reset state. (B): A SR latch in the set state. Red represents logical "1", black logical "0".

5.2. D Flip-Flops

A D flip-flop (where the D either stands for Delay or Data) is a flip-flop which does not propagate the input to the output until a specific state or change in the clock signal. Figure 18 shows the basic symbol for a D-type flip-flop with no preset or clear.

d flipflop symbol
Figure 18. The schematic symbol for a D-type flipflop.

Figure 19 shows the internals of a flip-flop.

d flipflop internals
Figure 19. How a D flipflop is made from discrete NAND gates. The inverting gate can be replaced by a NAND with both inputs connected to form an all-NAND implementation.

You can actually eliminate the need the inverting/NAND gate altogether by connecting the output of the top NAND to the input of the bottom NAND as shown in Figure 20, saving one gate (lower cost/size).

d flipflop internals no inv gate
Figure 20. A D-type flip-flop with the inverting/NAND gate removed by connecting the output of the top NAND to the input of the bottom NAND.

You may have noticed that the output stage of the D-type flip-flop looks familiar — that’s because it’s just an SR latch! Figure 21 highlights the SR latch section of a D-type flip-flop.

d flipflop internals highlighting sr latch
Figure 21. A D flip-flop is just a SR latch with some extra circuitry added on the front end to add in the delay functionality.

D-type flip-flops are used for counters, shift-registers and input synchronization.

5.2.1. Triggering

Edge-triggered D flip-flops can be either positive or negative edge triggered. Edge-triggered flip-flops are shown by a triangle at the clock input, and negative edge-triggered ones have an additional bubble. However, positive-edge triggered is much more common, and standard practice is to make a negative edge triggered flip-flop by adding your own inverting gate on the clock signal.

Note Adding a inverting gate to the clock signal increasing the propagation delay for that clock input, and will have a significant impact on the operation in high-speed designs.

5.2.2. Flip-flop MTBF

\[{\rm MTBF}(t_r) = \frac{e^{ \frac{t_r}{\tau} } } {T_O fa}\]

where:
\(t_r\) = resolution time (time since clock edge), \(s\)
\(f\) = sampling clock frequency, \(Hz\) \(a\) = asynchronous event frequency, \(Hz\) \(\tau\) = flip-flop time constant (this is a function of it’s transconductance), \(s\) \(T_o\) =

Typical values for a flip-flop inside an ASIC could be:

  • \(t_r = 2.3ns\)

  • \(\tau = 0.31ns\)

  • \(T_O = 9.6as\)

  • \(f = 100MHz\)

  • \(a = 1MHz\)

Which gives \(\rm MTBF = 20.1days\).

5.3. JK Flip-flop

6. Karnaugh Maps

Karnaugh maps are a way of simplifying combinational logic, often used before realising a combination equation into a number of gates to reduce the complexity.

7. Logic Simulators

CEDAR Logic Simulator is my personal favourite. Free, easy to use, colours the wires depending on their state, and allows for named nets as well as direct connections.

8. Example Logic Circuits

8.1. 6-State Binary Counter

Category: Counter Expression Style: Sum of Products No. of Gates: 14 No. of Flip-flops: 3 1-Bit Inputs: 2 + reset 1-Bit Outputs: 3

Tested On:

The 6-state binary counter is a counter which counts from 000 to 101 in the normal binary fashion before resetting back to 0. The output increments on every rising-edge of the count pulse, and the direction pin (upNDown) determines the count direction (when upNDown = 1, the counter goes from 000 to 101, when upNDown is 0 the counter goes from 101 to 000).

The flip-flop equations expressed as sums of products are:

\[Q_2 = \bar{Q_2}.\bar{Q_1}.\bar{Q_0}.\bar{y} + \bar{Q_2}.Q_1.Q_0.y + Q_2.\bar{Q_1}.Q_0.\bar{y} + Q_2.\bar{Q_1}.\bar{Q_0}.y \\ \\ Q_1 = \bar{Q_2}.\bar{Q_1}.Q_0.y + \bar{Q_2}.Q_1.\bar{Q_0}.y + \bar{Q_2}.Q_1.Q_0.\bar{y} + Q_2.\bar{Q_1}.\bar{Q_0}.\bar{y} \\ \\ Q_0 = \bar{Q_2}.\bar{Q_0} + Q_2.\bar{Q_1}.\bar{Q_0} \\ \\\]
digital logic counter six state binary
Figure 22. Schematic of a six state binary counter.

8.2. 3-Bit Grey Encoded Counter

Category: Counter Expression Style: Sum of Products No. of Gates: 14 No. of Flip-flops: 3 1-Bit Inputs: 2 + reset 1-Bit Outputs: 3

Tested On:

The 3-Bit Grey Encoded Counter is a counter that counts from 0 to 7 in binary in a grey encoded fashion. The counter increments on every rising edge of the bit 'count' and the direction bit 'upNDown' determines the direction of counting.

digital logic counter three bit grey encoded binary
Figure 23. Schematic of a three-bit Grey encoded binary counter.

8.3. Quadrature Detection Circuit

This quadrature detection circuit is built entirely in hardware, and only uses one flip-flop. It is useful for detecting the direction that an encoder that outputs quadrature signals is spinning in. Potential applications include BLDC motor control. This circuit can be built entirely in reconfigurable PSoC on-chip logic.

When the encoder is spinning in one direction, the output will be logic high (1), when it is spinning in the opposite direction, it will be logic low (0).

quadrature phase detection circuit
Figure 24. A simple quadrature phase detection circuit using a D flip-flop.

8.4. Delay Circuit

A simple delay circuit can be made just by chaining DQ flip-flops together in series (the output of one feeds the input of another). For every flip-flop, the signal will be delayed by one clock-cycle (assuming they all share the same clock source).

four clock cycle delay element from flipflops
Figure 25. A simple four clock-cycle delay element made from four DQ flip-flops. This can be used as a simple timer.

This can be used to make a simple timer. Obviously, a limitation is that a flip-flop is needed for every clock cycle of delay needed (try that with a 1000 clock cycle delay!). More advanced timers use binary encoding with the flip-flops to achieve a greater number of states for a lower number of flip-flops.

References


Authors

Twitter

Tags:

comments powered by Disqus