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

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.

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

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#

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)

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#

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

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.

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#

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.

In the following figure the circuits are augmented with

total number of gates

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#

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 languagesbinary operation uses only two arguments, e.g., (1)

`AND`

, (2) addition of two numbersternary 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`

.

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#

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`\land`

s or`\lor`

s it does not matter where we begin with our operation`\land`

and`\lor`

are commutative, so in an expression with only`\land`

s or`\lor`

s 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#

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#

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:

The last line describes the `XNOR`

operator as we would expect. It is more interesting if we negate a longer `XOR`

chain:

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 `1`

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

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.

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

How you you draw it?

How do you fill it out?

Solution to Exercise 65

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#

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`

.

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

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

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

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.

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

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

### K-Maps with Don’t Cares#

#### Incompletely Specified Logic Functions (Don’t Cares)#

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.

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.

How can we get compacter K-maps?

How does it work?

Solution to Exercise 74

By entering variable names directly in the output cells additional to

`1`

and`0`

s.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 care`

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

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#

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

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

We have seen the visual minimization technique K-map.

Which computer-based techniques exist?

How do they basically work?

Solution to Exercise 77

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

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:

### An introduction to the Vivado logic simulator#

What is a testbench?

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#

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

Solution to Exercise 79