Combinational Logic Circuits

Source: Combinational Logic Circuits

Learning Goals

• Be able to analyze higher-level, purely behavioral digital system descriptions, and design circuits to implement the behavior;

• Know how to find a minimum expression for any given logic requirement.

Background

Following problems will have a binary output. For that truth tables come handy.

Exercise 49

From which perspective does a truth table describe a circuit?

A) behavioral B) structural C) algorithmic D) data flow E) I don’t know

Solution to Exercise 49

Behavioral.

A truth table describes how a circuit’s output should behave according to an input. After synthesis of our truth table we get a structural circuit description that has the same behavior as the truth table.

Exercise 50

You are asked to build the most efficient circuit for a given functional specification.

What do you have to pay attention to? In other words, what does efficient in this context mean?

Solution to Exercise 50

Does not mean much.

You have to ask back: What kind of efficiency is wanted? 😕.

For example, the circuit should

• consume least amount of space

• achieve the highest frequency

• consume least amount of energy per computation

Exercise 51

What is the advantage of minimizing the logic for a truth table?

Solution to Exercise 51

Our circuit requires less amount of gates, which leads to less transistors and typically less power consumption.

Simulation

Exercise 52

What do we do when we simulate a circuit?

Solution to Exercise 52

We

• take our circuit description

• apply possible inputs according to its specification

• verify if the output corresponds to our specification (or lead to erroneous conditions)

Exercise 53

Why should we work with the simulator if we can directly verify our design on the FPGA?

Solution to Exercise 53

Low-level programming brings its freedom in systems design but also the peril of complexity. You will very likely stumble to functional errors which are not convenient to debug while running the design on the FPGA:

• you have to wait for the synthesis and implementation (mapping, place and route) to complete. Compared to these, compiling a functional simulation from the behavioral description takes much less time

• you have access to most of the data like signals and wires in the simulation. It is also possible to synthesize an internal logic analyzer (similar to a lab oscilloscope) inside your circuit, but the same disadvantage from the previous point also applies here.

Creating a testbench, especially creating test input (i.e., stimulus) can be also time-consuming, so the complexity of the testbench (or if you use a testbench at all) depends on your circuit.

Introduction to Logic Minimization

Same Logic Function, Different Circuit Implementations

Exercise 54

___ truth table exists to describe the relationship between Boolean inputs and outputs. The same relationship can be implemented by ___ logic equations or circuits.

Why?

Solution to Exercise 54

One … many

There can be many logic equations for the same behavior (truth table) because we can always add some redundant inputs to a truth table.

Exercise 55

Why do the minimized SOP and POS versions require less transistors in the figure below?

Solution to Exercise 55

They use NAND, NOR where possible. These gates use the least amount of transistors in CMOS — four transistors.

Exercise 56

What is the difference between a canonical form and a minimized form?

Solution to Exercise 56

According to Wiktionary the word canonical means:

Stated or used in the most basic and straightforwardly applicable manner.

In our context the canonical (POS or SOP) form contains all the input variables. In this regard it is straightforward to read the canonical form from a truth table. The minimized form does not necessarily contain all the input variables.

Find the Most Efficient Circuit

Exercise 57

Which parameters can we optimize for in a circuit?

Solution to Exercise 57

For example:

• size (space). In an FPGA the percentage of used logic resources.

• power

• frequency

• arithmetic operations per energy

Note

The numbers on Figure 2 In the following figure the numbers show the number of logic gates and the total input count of the gates. On the first sight the numbers seem like the number of inputs and total number of transistors, but it is not.

For example the first figure has three gates, a NAND, an AND, an OR. The inverter is not counted as an individual gate. What about the input count? We have three gates and every of them has two inputs, so six in total.

Exercise 58

In the following figure the circuits are augmented with

1. total number of gates

2. the total number of gate inputs.

Why are these measures important in context of logic minimization?

Solution to Exercise 58

Not only total number of gates but also the number of inputs in each gate influence the total transistor count and thus the circuit size. We can try to minimize these parameters to achieve the minimal circuit.

Boolean Algebra

Boolean Algebra: Basic Operations

Exercise 59

What does an

• unary

• binary

• ternary

operation mean? Give examples.

Solution to Exercise 59

• unary operation uses only a single argument, e.g., (1) negation, (2) increment x++ in various languages

• binary operation uses only two arguments, e.g., (1) AND, (2) addition of two numbers

• ternary operation …, e.g., (1) a*x + b, (2) x if y else z in Python

Note

Author’s definition with three set elements 0, 1, A The author writes

Boolean algebra is a proper algebraic system, with three set elements {‘0’, ‘1’, and ‘A’} (where ‘A’ is any variable that can assume the values ‘0’ or ‘1’), two binary operations (AND or intersection, OR or union), and one unary operation (inversion or complementation).

According to Wikipedia: Boolean algebra/Values Boolean algebra does not introduce an A which stands for any value. Boolean algebra includes only True, False, or 1 and 0.

Exercise 60

According to the Boolean algebra \(\overline{x} \cdot x = 0\)

Why?

Solution to Exercise 60

The equation means either

• True and False, if x = False

• False and True, if x = True

So True and False equals to False or 0. In words, something cannot be false and true at the same time. So it is False.

Associative, Commutative, and Distributive Laws

Exercise 61

What do

• associative

• commutative

• distributive

laws in context of Boolean algebra mean?

Solution to Exercise 61

The adjective associative derives from the word associate which (among other things) means to connect together and joined with another or others and having lower status. In mathematics, if a binary operator with more than two operands is associative if we can perform the binary operations in any order without changing the result. So when using associative operator the operands are like teammates joined together and the where (in other words on which pair) we perform the binary operation first does not make any difference. Practically, if \(\cdot\) is an associative operator then \((x \cdot y) \cdot z = x \cdot (y \cdot z)\). It does not matter how we associate (in other words, join) the expression.

Also other kinds of associativity exist. For example, subtraction and division are *left-*associative: 1 - 2 - 3 = (1 - 2) -3 = -4 and not 1 - (2 - 3) = 1 - (-1) = 2. Assignment operators in Python are right-associative: a = b = 1 means a = (b = 1) which leads to b = 1; a = b instead of (a = b) = 1 where either b or a would have an undefined value. Finally there is *non-*associativity, but the definition seems to vary. Stackoverflow think that non-associative means everything which is not associative, but Wikipedia speaks of when the outputs of left and right cannot be chained at all because they may have incompatible data types like boolean and integer.

• left-associativity

A binary operator can give different results if we change the order of the operations. For example floating-point addition can give different results based on which operands are first added together.

The adjective commutative according to Wiktionary comes from:

From French commuter (“to substitute or switch”) + -ative (“tending to”)

and means:

(mathematics, of a binary operation) Such that the order in which the operands are taken does not affect their image under the operation.

So we can switch or substitute the two operands in a binary operation and the result won’t change.

The adjective distributive is related to the verb distribute which means:

To divide into portions and dispense.

The mathematical meaning of distributive is:

A property of functions that have a rule describing how the function can be performed to the individual components of another operation. … If the operation ⋆ is distributive with respect to the operation ∘, then a ⋆ ( b ∘ c ) = ( a ⋆ b ) ∘ ( a ⋆ c )

This means that we can divide the operation into portions and dispense it over the operands of the second operation.

In Boolean algebra the \land and \lor operators have the following properties:

• \land and \lor are associative, so in an expression with only \lands or \lors it does not matter where we begin with our operation

• \land and \lor are commutative, so in an expression with only \lands or \lors and two operands it does not matter if we switch the operands or not, the result will be the same.

• \land is distributive with respect to \lor and vice versa, so we can scatter the first operand and the operator to the second and third operand and apply the second operator on the results.

DeMorgan’s Law

Exercise 62

What does DeMorgan’s law state?

Solution to Exercise 62

If we negate a Boolean expression, all the components of the expression are negated and an or operation turns to and and vice versa.

Example: If Mel is hungry if and only if it is 1pm and they is home, then Mel is not hungry if it is not 1pm or they is not home.

Laws for XOR and XNOR

Exercise 63

How can we apply DeMorgan’s law on XOR and XNOR?

Solution to Exercise 63

The author writes:

The laws of Boolean algebra generally hold for XOR functions as well, except that DeMorgan’s law takes a different form …

According to Wikipedia – De Morgan’s laws, the laws only apply to OR and AND operators but not directly on XOR and XNOR. To apply De Morgan on these, we have to rewrite them in POS or SOP:

\[\begin{split} x \oplus y = x \cdot \overline{y} + \overline{x} \cdot y \\ \Rightarrow \\ \overline{x \oplus y} = (\overline{x} + y) \cdot (x + \overline{y}) \\ = ( (\overline{x} + y) \cdot x ) + ( (\overline{x} + y) \cdot \overline{y} ) \\ = (\overline{x} \cdot x + y \cdot x) + (\overline{x} \cdot \overline{y} + y \cdot \overline{y}) \\ = y \cdot x + \overline{x} \cdot \overline{y} \end{split}\]

The last line describes the XNOR operator as we would expect. It is more interesting if we negate a longer XOR chain:

\[\begin{split} x \oplus y \oplus z = TODO \\ = \overline{\overline{x} \oplus y \oplus z} \\ = \overline{ \overline{x} \oplus \overline{y} \oplus \overline{z} } \end{split}\]

This means: We can negate the XOR operation if we negate an uneven number of operands, because the XOR outputs 1 if the number of 1s in the inputs is uneven, 0 otherwise.

Circuit Illustration for Boolean Algebra

Use Boolean Algebra to Find Simpler Logic Equations

Introduction to K-Maps

K-Maps

Note

Logic graph The author writes:

… Logic graphs offer the easiest and most useful pen-and-paper method of minimizing a logic system. A logic graph and a truth table contain identical information, but patterns that indicate redundant inputs can be readily identified in a logic graph

According to my research logical graph and logic diagram have the same meaning, so the author probably means the same with logic graph.

There are many kinds of logical graphs though and Karnaugh map – in short K-map is one of them.

K-map is not the logical graph but a logical graph.

Exercise 64

You see a K-Map above. What does each cell in a K-Map describe?

A) K-term B) minterm C) maxterm D) K-reduce E) I don’t know

Solution to Exercise 64

A minterm.

Exercise 65

You want to minimize the logic equation of a truth table with four inputs.

1. How you you draw it?

2. How do you fill it out?

Solution to Exercise 65

1. By incrementally folding out the table as follows:

   

2. Each cell corresponds to a minterm. In each row named with a input variable is the input variable 1. We fill the value of the minterm output in the corresponding cell.

Exercise 66

What is the advantage of a K-map over a truth table?

Solution to Exercise 66

The human can minimize the circuit much easier using K-maps, because K-maps use humans’ visual pattern recognition capability. Minimization using truth tables involve rewriting the logic formulas, which takes more time.

Find Minimum Logic Expressions Using K-maps

Exercise 67

What does it mean if two adjacent (neighboring) cells have the same output, e.g., 1 in a K-map?

Solution to Exercise 67

This means that the output is true (or false) for these two minterms and for the output to become true (or false) one of the input variables does not play a role (at least for these two conditions). In other words, we can write a shorter minterm.

As an example look at the blue horizontal rectangle in the following K-map. You see that in this blue rectangle the output is oblivious to the value of A.

Exercise 68

In the following K-map there are two yellow rectangles which can be compiled together as a square with two variables (\(A\overline{D}\)). Why are we allowed to draw a loop by wrapping around the rectangle? These cells are not adjacent at all!

Solution to Exercise 68

1. When we look at the labels for these cells, we see that they are not dependent on \(B\) and \(C\).

2. In 3D, this K-map can be drawn as a torus, where these cells are indeed neighboring cells:

The conversion process:

The same principle applies to the corners of the k-map, these are adjacent too.

Super K-maps

Note

The naming super K-map does not exist

I could not find any reference to super K-maps in literature. The author most likely means K-maps with more than four variables. There are various ways to draw K-maps with five or six variables, e.g.:

• Larger 5 & 6-variable Karnaugh Maps

• Five & six variable K-map

Exercise 69

Below is a K-map with six variables. Which grouping makes no sense?

A) red B) blue C) I don’t know

Solution to Exercise 69

Blue.

Red cells are described by \(\overline{A}B\overline{D}\). You can see it by folding back the variables \(E\) and \(F\). Even blue cells look adjacent, they cannot be described by a minterm.

This is a reason why it is not easy to use K-maps with more than four variables.

Exercise 70

In the previous exercise we have seen an inconvenient way of minimizing a six input K-map. How can we improve this?

Exercise 71

• By embedding four input K-maps into another K-map with two inputs. Example

• Other examples

K-Maps with Don’t Cares

Incompletely Specified Logic Functions (Don’t Cares)

Exercise 72

What does don’t care in digital logic mean?

Solution to Exercise 72

If an input is inconsequential for an output, then we can use a don’t-care term to denote this.

Exercise 73

How can we leverage don’t care in minimization?

Solution to Exercise 73

Don't care terms act like as a wild card like the joker in some card games – it does not matter if we replace the don't care term with a 0 or 1. If a minterm cell in a K-map has a don't care term and this cell is missing from a shorter minterm, then we can replace the cell with a 1 to get the shorter minterm. For maxterms the approach is similar, we fill then the cell with 0.

Note

Don’t care or the value X in various HDL languages like Verilog and VHDL denote a signal which value is not known

K-Maps with Entered Variables

Note

This approach is also called reduced Karnaugh map, infrequent variables, map-entered variables, variable-entered map, variable-entered Karnaugh map according to WP: logic minimization – graphical methods.

Exercise 74

1. How can we get compacter K-maps?

2. How does it work?

Solution to Exercise 74

1. By entering variable names directly in the output cells additional to 1 and 0s.

2. If we see that an output follows an input variable if other variables are left unused, e.g., D or an equation, e.g., C+D, then we can write these in the minterm cell instead of a larger K-map with only 0, 1 and don't cares.

   For an example, look at the first small green rectangle that describes D in the truth table in the following figure.

   

   You see that the output Y follows D if the rest of the inputs A, B, C do not change. We can integrate other inputs if the truth table allows.

Exercise 75

How can we minimize a K-map with entered variables?

Solution to Exercise 75

The rules are the same to uncompressed K-maps if we draw the sub-maps for the entered variables for every cell in which these variables are used. (Alternatively we can expand the truth table with the entered variable, but this would be against the advantage of the entered variables. The entered variables here to reduce the size of our K-map).

For example, in the top left minimization example below, we see that we can not only group same variables, e.g., \(D\) with \(D\) but also

• \(D\) with 1

• \(\overline{D}\) with 1

Note

Chapter 3.5.4 from Fundamentals of Digital Electronics by Dhanasekharan Natarajan additional examples.

K-Maps with Multiple Outputs

Exercise 76

We discussed some approaches how to minimize circuits with a single output. How do we minimize when we have multiple outputs?

Solution to Exercise 76

1. We minimize for the individual outputs separately and find the locally minimum circuit. Then we put the circuits together. If we see some gates with same inputs shared by these locally minimum circuits, then we can eliminate some gates.

2. We may not find any similarities in the above approach. Instead we can use a global minimization approach to find the global minimum circuit. Here

   • we locally minimize for each output as before

   • we write all the terms for the individual outputs

   • look which of them are shared by at least two outputs

   • we try to integrate these terms into the locally minimized circuits, e.g., by looping out the terms differently

If we are successful, we can use the circuit described by the shared term for multiple outputs and can save some space.

Let us show the global minimum using the following example:

Assume that we found the locally minimal circuits for all the outputs:

• \(X_\mathrm{LM} = AD + AB\overline{D} + \overline{C}D + \overline{A}\overline{B}C\overline{D}\)

• \(Y_\mathrm{LM} = ... \)

• \(Z_\mathrm{LM} = \overline{A}\overline{B}C + AB\overline{C} + A\overline{B}D \)

We find the shared terms:

• shared by \(X\), \(Y\), \(Z\): \(m_{9}, m_{11}\)

• shared only by \(X\), \(Y\) but not all: \(m_{14}, m_{15}\)

• shared only by \(Y\), \(Z\) but not all: \(m_{3}\)

• shared only by \(X\), \(Z\) but not all: \(m_{2}, m_{12}, m_{13}\)

For example \(m_{2} = \overline{A}\overline{B}C\overline{D}\) is shared by \(X\) and \(Z\). \(m_{2}\) and thus the circuit is already integrated in \(X\). To integrate \(m_{2}\) in \(Z\) we can break \(\overline{A}\overline{B}C\) into the terms \(\overline{A}\overline{B}CD\) and \(\overline{A}\overline{B}C\overline{D}\) to allow \(X\) and \(Z\) share \(m_{2}\). By breaking the shorter minterm into two longer ones we:

• introduce two inputs and a gate in \(Z\)

• eliminate four inputs and a gate in \(X\).

If we calculate the transistor count:

• introduce for \(\overline{A}\overline{B}CD\) +2 transistors (1 transistor for each N- and NFET network) in \(Z\)

• introduce for \(\overline{A}\overline{B}C\overline{D}\) +4 transistors (similar to above and two transistors for the inverter) in \(Z\)

• save for \(\overline{A}\overline{B}C\overline{D}\) in \(X\) +16 transistors (2 transistors for 4 inputs, 2 transistors for 3 inverters and 2 transistors for the end inverter)

Note that the transistor count varies on the optimizations, so it makes more sense to use the input number with gate count for comparison.

Computer-Based Logic Minimum

Exercise 77

We have seen the visual minimization technique K-map.

• Which computer-based techniques exist?

• How do they basically work?

Solution to Exercise 77

1. Quine–McCluskey algorithm (QM), Espresso heuristic logic minimizer

2. QM is functionally similar to K-maps, but the minimization is done using tables. QM tries every combination to generate minimum terms.

   Espresso uses a heuristic (a rule-based approach) which is not guaranteed to find the exact solution but in less time than QM.

Final notes on K-Maps

Note

K-maps can also be drawn as Venn diagrams or hypercubes.

Note

Minimization methods We focused on K-maps, but there are many more approaches to graphical minimization. Some are:

• Minterm-ring map

• Pandit-Plot

An introduction to the Vivado logic simulator

Exercise 78

1. What is a testbench?

2. How does the testbench work?

Solution to Exercise 78

A testbench tests if a circuit works correctly.

A testbench

• instantiates the circuit

• stimulates the circuit

• checks if the circuit behaves correctly. Sometimes this check is done by the engineer by visually inspecting the waveform output.

Creating a test bench for a Majority-of-Five circuit

Requirements

1. Design a “majority of five” circuit

Exercise 79

Minimize the majority of five circuit using an entered variable K-map.

Solution to Exercise 79