# Combinational Logic Circuits
Source: [Combinational Logic Circuits](https://www.realdigital.org/doc/d5772f23c25857c94269e7438b74354f)
## 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}
:label: truth_tables_structural_or_behavioral
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} truth_tables_structural_or_behavioral
:class: dropdown
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}
:label: efficiency_in_context_of_a_circuit
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} efficiency_in_context_of_a_circuit
:class: dropdown
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}
:label: what_does_a_minimal_design_lead_to
What is the advantage of minimizing the logic for a truth table?
```
```{solution} what_does_a_minimal_design_lead_to
:class: dropdown
Our circuit requires less amount of gates, which leads to less transistors and typically less power consumption.
```
### Simulation
```{exercise}
:label: what_do_we_simulate
What do we do when we simulate a circuit?
```
```{solution} what_do_we_simulate
:class: dropdown
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}
:label: why_do_we_simulate
Why should we work with the simulator if we can directly verify our design on the FPGA?
```
```{solution} why_do_we_simulate
:class: dropdown
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}
:label: one_truth_table_but_many_logic_equations_and_circuits
___ 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} one_truth_table_but_many_logic_equations_and_circuits
:class: dropdown
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}
:label: why_minimized_sop_or_pos_need_less_transistors
Why do the minimized SOP and POS versions require less transistors in the figure below?
```{image} https://www.realdigital.org/img/e7a8f12aedcd41f0587c355c0337670c.svg
:alt: Different circuit implementations of same logic function (Realdigital.org CC-BY SA 4.0)
```
````
```{solution} why_minimized_sop_or_pos_need_less_transistors
:class: dropdown
They use `NAND`, `NOR` where possible. These gates use the least amount of transistors in CMOS — four transistors.
```
```{exercise}
:label: meaning_of_canonical
What is the difference between a *canonical* form and a *minimized* form?
```
```{solution} meaning_of_canonical
:class: dropdown
[According to Wiktionary](https://en.wiktionary.org/wiki/canonical#Adjective) 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}
:label: optimization_parameters_in_a_circuit
Which parameters can we optimize for in a circuit?
```
```{solution} optimization_parameters_in_a_circuit
:class: dropdown
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.
```{image} https://www.realdigital.org/img/45b431afeb4f845267169615227138ce.svg
:alt: Realdigital.org CC-BY SA 4.0
```
```{exercise}
:label: why_total_number_of_inputs_and_total_gate_number
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} why_total_number_of_inputs_and_total_gate_number
:class: dropdown
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}
:label: unary_binary_ternary_meaning
What does an
- unary
- binary
- ternary
operation mean? Give examples.
```
```{solution} unary_binary_ternary_meaning
:class: dropdown
- [unary operation](https://en.wikipedia.org/wiki/Unary_operation) uses only a single argument, e.g., (1) negation, (2) increment `x++` in various languages
- [binary operation](https://en.wikipedia.org/wiki/Binary_operation) uses only two arguments, e.g., (1) `AND`, (2) addition of two numbers
- [ternary operation](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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}
:label: x_and_x_not
According to the Boolean algebra $\overline{x} \cdot x = 0$
Why?
```
```{solution} x_and_x_not
:class: dropdown
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}
:label: associative_commutative_distributive_meaning
What do
- associative
- commutative
- distributive
laws in context of Boolean algebra mean?
```
```{solution} associative_commutative_distributive_meaning
:class: dropdown
The adjective [*associative*](https://en.wiktionary.org/wiki/associative#Adjective) derives from the word [*associate*](https://en.wiktionary.org/wiki/associative) 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](https://math.stackexchange.com/questions/2892352/non-associative-operations) think that non-associative means everything which is not associative, but [Wikipedia](https://en.wikipedia.org/wiki/Operator_associativity) 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](https://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floating_point_calculation).
The adjective [*commutative* according to Wiktionary](https://en.wiktionary.org/wiki/commutative#Etymology) 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*](https://en.wiktionary.org/wiki/distributive) is related to the verb [*distribute*](https://en.wiktionary.org/wiki/distribute) which means:
> To divide into portions and dispense.
[The mathematical meaning of distributive](https://en.wiktionary.org/wiki/distributive#Adjective) 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
```{exercise}
:label: demorgans_law
What does DeMorgan's law state?
```
```{solution} demorgans_law
:class: dropdown
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}
:label: demorgan_on_xor_xnor
How can we apply DeMorgan's law on `XOR` and `XNOR`?
```
````{solution} demorgan_on_xor_xnor
:class: dropdown
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](https://en.wikipedia.org/wiki/De_Morgan%27s_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:
$$
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}
$$
The last line describes the `XNOR` operator as we would expect. It is more interesting if we negate a longer `XOR` chain:
$$
x \oplus y \oplus z = TODO \\
= \overline{\overline{x} \oplus y \oplus z} \\
= \overline{ \overline{x} \oplus \overline{y} \oplus \overline{z} }
$$
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*](https://en.wikipedia.org/wiki/Logical_graph) and [*logic diagram*](https://commons.wikimedia.org/wiki/Logic_diagram) have the same meaning, so the author probably means the same with *logic graph*.
There are [many kinds of logical graphs though](https://commons.wikimedia.org/wiki/Logic_diagram) and *Karnaugh map* – in short K-map is one of them.
K-map is *not the logical graph* but a logical graph.
```
````{exercise}
:label: each_cell_in_a_kmap_describes_a_minterm
```{image} https://upload.wikimedia.org/wikipedia/commons/0/02/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg
:alt: en:User:Cburnett, CC BY-SA 3.0, via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:K-map_6,8,9,10,11,12,13,14_anti-race.svg
```
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} each_cell_in_a_kmap_describes_a_minterm
:class: dropdown
A minterm.
```
```{exercise}
:label: how_do_we_fill_out_the_kmap
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} how_do_we_fill_out_the_kmap
:class: dropdown
1. By incrementally folding out the table as follows:
```{image} https://upload.wikimedia.org/wikipedia/commons/f/f6/Karnaugh_map_KV_Herleitung_Symmetrie.svg
:alt: Martin David Johannes Rosenau, CC BY-SA 3.0 DE , via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:Karnaugh_map_KV_Herleitung_Symmetrie.svg
```
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}
:label: advantage_of_kmap
What is the advantage of a K-map over a truth table?
```
```{solution} advantage_of_kmap
:class: dropdown
The human can minimize the circuit much easier using K-maps, [because K-maps use humans' visual pattern recognition capability](https://en.wikipedia.org/wiki/Karnaugh_map#cite_ref-Karnaugh_1953_1-1). Minimization using truth tables involve rewriting the logic formulas, which takes more time.
```
#### Find Minimum Logic Expressions Using K-maps
```{exercise}
:label: kmap_adjacent_cells
What does it mean if two adjacent (neighboring) cells have the same output, e.g., `1` in a K-map?
```
````{solution} kmap_adjacent_cells
:class: dropdown
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`.
```{image} https://upload.wikimedia.org/wikipedia/commons/0/02/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg
:alt: en:User:Cburnett, CC BY-SA 3.0, via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:K-map_6,8,9,10,11,12,13,14_anti-race.svg
```
````
````{exercise}
:label: another_view_on_kmap_loop_around
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!
```{image} https://upload.wikimedia.org/wikipedia/commons/0/02/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg
:alt: en:User:Cburnett, CC BY-SA 3.0, via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:K-map_6,8,9,10,11,12,13,14_anti-race.svg
```
````
````{solution} another_view_on_kmap_loop_around
:class: dropdown
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:
```{image} https://upload.wikimedia.org/wikipedia/commons/3/33/Karnaugh_map_torus.svg
:alt: Cmglee, CC BY-SA 4.0 , via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:Karnaugh_map_torus.svg
```
The conversion process:
```{image} https://upload.wikimedia.org/wikipedia/commons/6/60/Torus_from_rectangle.gif
:alt: Lucas Vieira, Public domain, via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:Torus_from_rectangle.gif
```
The same principle applies to the corners of the k-map, these are adjacent too.
````
#### Super K-maps
(note_super_kmap_does_not_exist)=
```{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](https://instrumentationtools.com/topic/larger-5-6-variable-karnaugh-maps/)
- [Five & six variable K-map](https://people.eecs.berkeley.edu/~newton/Classes/CS150sp98/lectures/week4_2/sld007.htm)
```
````{exercise}
:label: kmap_with_six_variables_which_grouping_makes_no_sense
Below is a K-map with six variables. Which grouping makes no sense?
A) red
B) blue
C) I don't know
```{image} https://upload.wikimedia.org/wikipedia/commons/7/7e/Karnaugh_map_KV_6_Inputs_Valid_and_Invalid.svg
:alt: Martin David Johannes Rosenau, CC BY-SA 3.0 DE , via Wikimedia Commons
:target: https://commons.wikimedia.org/wiki/File:Karnaugh_map_KV_6_Inputs_Valid_and_Invalid.svg
```
````
```{solution} kmap_with_six_variables_which_grouping_makes_no_sense
:class: dropdown
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}
:label: six_input_karnaugh_map
In the previous exercise we have seen an inconvenient way of minimizing a six input K-map. How can we improve this?
```
```{exercise}
- By embedding four input K-maps into another K-map with two inputs. [Example](https://www.realdigital.org/doc/2e2349ab3c0a218f6fe0081e2188a38d#super-k-maps)
- [Other examples](note_super_kmap_does_not_exist)
```
### K-Maps with Don't Cares
#### Incompletely Specified Logic Functions (Don’t Cares)
```{exercise}
:label: what_is_dont_care_term
What does *don't care* in digital logic mean?
```
```{solution} what_is_dont_care_term
:class: dropdown
:label: super_kmap_does_not_exist
If an input is inconsequential for an output, then we can use a [don't-care term](https://en.wikipedia.org/wiki/Don%27t-care_term) to denote this.
```
```{exercise}
:label: how_can_we_use_dont_care_in_minimization
How can we leverage *don't care* in minimization?
```
```{solution} how_can_we_use_dont_care_in_minimization
:class: dropdown
`Don't care` terms act like as a wild card like [the joker in some card games](https://en.wikipedia.org/wiki/Joker_(playing_card)#Use_of_the_Joker_in_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](https://en.wikipedia.org/wiki/Don%27t-care_term#X_value)
```
### 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](https://en.wikipedia.org/wiki/Logic_optimization#Graphical_methods).
```
```{exercise}
:label: how_can_we_compress_kmaps
1. How can we get compacter K-maps?
2. How does it work?
```
````{solution} how_can_we_compress_kmaps
:class: dropdown
1. By entering variable names directly in the output cells additional to `1` and `0`s.
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 care`s.
For an example, look at the first small green rectangle that describes `D` in the truth table in the following figure.
```{image} https://www.realdigital.org/img/749749104867d829ea03a2e9b8fa48e6.svg
:target: https://www.realdigital.org/doc/45fb5de1eb6d83e51779a4e8d71a918f
:alt: CC-BY SA 4.0, Clint Cole
```
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}
:label: how_can_we_minimize_a_kmap_with_entered_variables
How can we minimize a K-map with entered variables?
```
````{solution} how_can_we_minimize_a_kmap_with_entered_variables
:class: dropdown
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`
```{image} https://www.realdigital.org/img/b448fff1b67407c710957698840af297.svg
:target: https://www.realdigital.org/doc/45fb5de1eb6d83e51779a4e8d71a918f
:alt: CC-BY SA 4.0, Clint Cole
```
````
```{note}
[Chapter 3.5.4 from Fundamentals of Digital Electronics by Dhanasekharan Natarajan](https://link.springer.com/content/pdf/10.1007%2F978-3-030-36196-9.pdf#ch3subsection.3.5.4) additional examples.
```
### K-Maps with Multiple Outputs
```{exercise}
:label: how_can_we_minimize_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} how_can_we_minimize_with_multiple_outputs
:class: dropdown
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:
```{image} https://www.realdigital.org/img/087fe951167fcbfc6db014166cbfb1fa.svg
:target: https://www.realdigital.org/doc/bc9e2e5a44f2b47a2056e8eddc3d0636
:alt: CC-BY SA 4.0, Clint Cole
```
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}
:label: which_computer_based_logic_minimization_techniques_exist
We have seen the visual minimization technique K-map.
- Which computer-based techniques exist?
- How do they basically work?
```
```{solution} which_computer_based_logic_minimization_techniques_exist
:class: dropdown
1. [Quine–McCluskey algorithm](https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm) (QM), [Espresso heuristic logic minimizer](https://en.wikipedia.org/wiki/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](https://de.wikipedia.org/wiki/Karnaugh-Veitch-Diagramm#Mengendiagramm) or [hypercubes](https://de.wikipedia.org/wiki/Karnaugh-Veitch-Diagramm#Veranschaulichung_durch_Hyper-Einheitsw%C3%BCrfel).
```
```{note} Minimization methods
We focused on K-maps, but there are [many more approaches to graphical minimization](https://en.wikipedia.org/wiki/Logic_optimization#Graphical_methods). Some are:
- [Minterm-ring map](https://web.archive.org/web/20210217022231/https://www.researchgate.net/profile/Eduardo_Romero11/publication/4162402_A_Survey_of_the_Graphic_Alternate_Method_for_Boolean_Functions_Simplification/links/553916020cf2239f4e7c5149/A-Survey-of-the-Graphic-Alternate-Method-for-Boolean-Functions-Simplification.pdf)
- [Pandit-Plot](https://doi.org/10.1155/2017/9696342)
```
### An introduction to the Vivado logic simulator
```{exercise}
:label: what_is_a_testbench
1. What is a testbench?
2. How does the testbench work?
```
```{solution} what_is_a_testbench
:class: dropdown
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}
:label: majority_of_five_minimization_using_entered_variable_kmap
Minimize the majority of five circuit using an entered variable K-map.
```
````{solution} majority_of_five_minimization_using_entered_variable_kmap
:class: dropdown
```{image} projects/p3/1/project3-1_majority_of_five_minimization.svg
:width: 1000
:height: 2000
:alt: handwritten solution
```
````