K-map: Difference between revisions

From Turing Complete
mNo edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{guide|narrow=1}}
=== What are Karnaugh-Veitch maps? ===
=== What are Karnaugh-Veitch maps? ===
<p style="width:640px;line-height:1.3em">
A Karnaugh-Veitch map is a modified truth table for 4 bits, which allows to derive simplified circuits for this table just by looking at it. So every time you come across a logic, that has 3 or 4 bits of input, you can plug its truth table into a KV map and build the circuit.
A Karnaugh-Veitch map is a modified truth table for 4 bits, which allows to derive simplified circuits for this table just by looking at it. So everytime you come across a logic, that has 3 or 4 bits of input, you can plug its truth table into a KV map and build the circuit.
</p>


=== Okay, so how does it look like? ===
=== Okay, so how does it look like? ===
<p style="width:640px;line-height:1.3em">
Usually you start with a truth table with 4 inputs and an output column with values that are either {{Off}} or {{On}}. In this example the output values doesn't matter (yet), but notice that I gave them numbers from 0 to 15 that matches their corresponding input bit pattern.
Usually you start with a truth table with 4 inputs and an output column with values that are either {{Off}} or {{On}}. In this example the output values doesn't matter (yet), but notice that i gave them numbers from 0 to 15 that matches their corresponding input bit pattern.
</p>


[[File:4bit_TruthTable_decimal_output.png]]
[[File:4bit_TruthTable_decimal_output.png]]


<p style="width:640px;line-height:1.3em">
A Karnaugh map is a truth table, where each bit combination is represented in 2D form.  
A Karnaugh map is a truth table, where each bit combination is represented in 2D form.  
So the outputs are not a straight line like above, but like a square:
So the outputs are not a straight line like above, but like a square:
</p>


[[File:KMap_undefined_output.png]]
[[File:KMap_undefined_output.png]]


<p style="width:640px;line-height:1.3em">
As a careful observer, you may have noticed something strange: The input combinations are not numbered 0-1-2-3 (in binary), but '''0-1-3-2'''!  
As a careful observer, you may have noticed something strange: The input combinations are not numbered 0-1-2-3 (in binary), but '''0-1-3-2'''!  
</p>


<blockquote>Why though?!</blockquote>
<blockquote>Why though?!</blockquote>


<p style="width:640px;line-height:1.3em">
The answer: We make sure, that '''only 1 bit changes in each step'''. So if we would go 0-1-2-3, then the step from 1 to 2 in binary would be 01 to 10. '''Both''' bits would change, but we only want 1 bit to change at max. This is why we swap the order of the inputs, but make sure, that we still have all possible combinations available.
The answer: We make sure, that '''only 1 bit changes in each step'''. So if we would go 0-1-2-3, then the step from 1 to 2 in binary would be 01 to 10. '''Both''' bits would change, but we only want 1 bit to change at max. This is why we swap the order of the inputs, but make sure, that we still have all possible combinations available.
</p>


<blockquote>BUT WHYYY?!</blockquote>
<blockquote>BUT WHYYY?!</blockquote>
Yes, yes... later...
Yes, yes... later...


<p style="width:640px;line-height:1.3em">
Changing the order of the input also changes the order in which we fill in the outputs. Going from left to right, skipping the third column and going from top to bottom, skipping the third row. The white numbers are the order in which you plug in the output values.
Changing the order of the input also changes the order in which we fill in the outputs. Going from left to right, skipping the third column and going from top to bottom, skipping the third row. The white numbers are the order in which you plug in the output values.
</p>


[[File:KMap_undefined_output_graycode.png]]
[[File:KMap_undefined_output_graycode.png]]
Line 39: Line 28:


=== How does this help me in any way? ===
=== How does this help me in any way? ===
<p style="width:640px;line-height:1.3em">
'''BLOCKS!'''
'''BLOCKS!'''
</p>


<p style="width:640px;line-height:1.3em">
The answer is blocks.
The anwser is blocks.
</p>


<p style="width:640px;line-height:1.3em">
Let me explain...
Let me explain...
</p>


<p style="width:640px;line-height:1.3em">
Humans are very good at visual pattern recognition (if the layout favors it). By using the ''only-1-bit-change'' trick, we can now combine bits in blocks of size 1,2,4 and 8. When forming blocks, we only focus on the {{On}} bits! Leaving the {{Off}} bits alone.
Humans are very good at visual pattern recognition (if the layout favors it). By using the ''only-1-bit-change'' trick, we can now combine bits in blocks of size 1,2,4 and 8. When forming blocks, we only focus on the {{On}} bits! Leaving the {{Off}} bits alone.
</p>


<p style="width:640px;line-height:1.3em">
Lets say there are the following 2 green output bits that we are interested in:
Lets say there are the following 2 green output bits that we are interested in:
</p>


[[File:KMap_Example1.png]]
[[File:KMap_Example1.png]]
Line 69: Line 48:
The bits that we are interested in, are in the row where:
The bits that we are interested in, are in the row where:


{| class="wikitable"
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]]
| [[File:D_boxed.png]] || [[File:C_boxed.png]]
|-
|-
Line 78: Line 57:
The bits that we are interested in, are in the columns where:
The bits that we are interested in, are in the columns where:


{| class="wikitable"
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:A_boxed.png]]
| [[File:A_boxed.png]]
|-
|-
Line 84: Line 63:
|}
|}


<p style="width:640px;line-height:1.3em">
We don't need [[File:B_boxed.png]] to describe the two columns, because [[File:A_boxed.png]] = {{On}} already covers both columns.
We don't need [[File:B_boxed.png]] to describe the two columns, because [[File:A_boxed.png]] = {{On}} already covers both columns.
</p>


<p style="width:640px;line-height:1.3em">
By putting those together, we can describe the {{On}} bits as '''2-bit block'''. The bigger the block, the less inputs we need to describe it! So we want to make the blocks as big as possible. To describe a 2-bit block, we need 3 inputs - the 4th does not matter (also a feature of our ''1-bit-change-only trick'').
By putting those together, we can describe the {{On}} bits as '''2-bit block'''. The bigger the block, the less inputs we need to describe it! So we want to make the blocks as big as possible. To describe a 2-bit block, we need 3 inputs - the 4th does not matter (also a feature of our ''1-bit-change-only trick'').
</p>


[[File:KMap_Example4.png]]
[[File:KMap_Example4.png]]


<p style="width:640px;line-height:1.3em">
The block is described by this combined input conditions:
The block is described by this combined input conditions:
</p>


{| class="wikitable"
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
|-
Line 104: Line 77:
|}
|}


<p style="width:640px;line-height:1.3em">
So now we can '''AND''' everything together and the block is done.
So now we can '''AND''' everything together and the block is done.
</p>


[[File:KMap_circuit_block.png]]
[[File:KMap_circuit_block.png]]
Line 112: Line 83:
=== Any more block limitations? ===
=== Any more block limitations? ===


<p style="width:640px;line-height:1.3em">
Only the 1,2,4,8 block size rule.
Only the 1,2,4,8 block size rule.
</p>


<p style="width:640px;line-height:1.3em">
Additional note: The blocks can also '''''go around''''' from left to right, and from top to bottom. So for example, you can do an 8-bit block from left to right (using only one input variable to describe it).
Additional note: The blocks can also '''''go around''''' from left to right, and from top to bottom. So for example, you can do an 8-bit block from left to right (using only one input variable to describe it).
</p>


[[File:KMap_around.png]]
[[File:KMap_around.png]]


<p style="width:640px;line-height:1.3em">
This block is described only by one input variable
This block is described only by one input variable
</p>


{| class="wikitable"
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
|-
Line 135: Line 100:


=== So this is it? ===
=== So this is it? ===
<p style="width:640px;line-height:1.3em">
Not quite.
Not quite.
</p>


<p style="width:640px;line-height:1.3em">
Since we can only do 1,2,4 and 8 bit blocks, we have to combine multiple blocks together, to cover all {{On}} outputs. Each one of them has to be part of a block. Overlapping blocks are no problem, they are actually quite helpful to create big blocks for missing bits.
Since we can only do 1,2,4 and 8 bit blocks, we have to combine multiple blocks together, to cover all {{On}} outputs. Each one of them has to be part of a block. Overlapping blocks are no problem, they are actually quite helpful to create big blocks for missing bits.
</p>


==== Example ====
==== Example ====
<p style="width:640px;line-height:1.3em">
This is our truth table, that we already plugged into our Karnaugh map:
This is our truth table, that we already plugged into our Karnaugh map:
</p>


[[File:KMap_Example5.png]]
[[File:KMap_Example4.png]]


<p style="width:640px;line-height:1.3em">
Now we have to do blocks of 1,2,4 or 8 (as big as possible) to cover all {{On}} output bits.
Now we have to do blocks of 1,2,4 or 8 (as big as possible) to cover all {{On}} output bits.
</p>


<p style="width:640px;line-height:1.3em">
We can do it like this:
We can do it like this:
</p>


[[File:KMap_Example9.png]]
[[File:KMap_Example9.png]]


<p style="width:640px;line-height:1.3em">
We need 3 blocks to cover all bits:
We need 3 blocks to cover all bits:
</p>


#[[File:YellowBox.png|14px]] A yellow 2-bit block
#[[File:YellowBox.png|14px]] A yellow 2-bit block
Line 169: Line 121:
#[[File:WhiteBox.png|14px]] A white 4-bit block
#[[File:WhiteBox.png|14px]] A white 4-bit block


<p style="width:640px;line-height:1.3em">
Combined they look like this:
Combined they look like this:
</p>


{| class="wikitable"
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
|  || [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|  || [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
|-
Line 183: Line 133:
|}
|}


<p style="width:640px;line-height:1.3em">
To build the blocks, we '''AND''' the inputs and after that we '''OR''' the blocks together
To build the blocks, we '''AND''' the inputs and after that we '''OR''' the blocks together
</p>


[[File:KMap_circuit_combining_blocks.png]]
[[File:KMap_circuit_combining_blocks.png|640px]]
 
And that's it! We created a circuit that describes the truth table completely!


<p style="width:640px;line-height:1.3em">
And thats it! We created a circuit that describes the truth table completely!
</p>


=== Final notes ===
=== Final notes ===
<p style="width:640px;line-height:1.3em">
The whole idea is based on the fact that a circuit like this:
The whole idea is based on the fact that a circuit like this:
</p>


<code>
<code>
Line 202: Line 147:
</code>
</code>


<p style="width:640px;line-height:1.3em">
is the same as just
is the same as just
</p>


<code>
<code>
Line 210: Line 153:
</code>
</code>


<p style="width:640px;line-height:1.3em">
Because it doesn't matter if A is {{On}} or {{Off}} - either the first part of the bracket is passed through, or the second part. So if only one bit changes, then we can remove that bit from the equation. (I was asked about that fact in my exam, so maybe it is good to know).
Because it doesn't matter if A is {{On}} or {{Off}} - either the first part of the bracket is passed through, or the second part. So if only one bit changes, then we can remove that bit from the equation. (I was asked about that fact in my exam, so maybe it is good to know).
</p>


----
----


<p style="width:640px;line-height:1.3em">
You can do a Karnaugh map for 3 bits, by throwing away the two rows on the bottom and the D input.
You can do a Karnaugh map for 3 bits, by throwing away the two rows on the bottom and the D input.
</p>


----
----


<p style="width:640px;line-height:1.3em">
You can also do a Karnaugh map for 5 bits, by creating two 4-bit maps. One where the 5th bit is {{Off}} and one where the 5th bit is {{On}}. Then imagine you lay both maps on top of each other, so you can do additional blocks by piercing through both maps.
You can also do a Karnaugh map for 5 bits, by creating two 4-bit maps. One where the 5th bit is {{Off}} and one where the 5th bit is {{On}}. Then imagine you lay both maps on top of each other, so you can do additional blocks by piercing through both maps.
</p>


----
----


<p style="width:640px;line-height:1.3em">
The way we collected the bits and put together the blocks is called ''Disjunctive Normal Form (DNF)'' which focuses on the {{On}} output bits, which are then '''OR'''d together. There is also a ''Conjunctive Normal Form (CNF)'' where you focus on the {{Off}} bits and then '''AND''' the blocks together (a bit more complicated - you have to look it up).
The way we collected the bits and put together the blocks is called ''Disjunctive Normal Form (DNF)'' which focuses on the {{On}} output bits, which are then '''OR'''d together. There is also a ''Conjunctive Normal Form (CNF)'' where you focus on the {{Off}} bits and then '''AND''' the blocks together (a bit more complicated - you have to look it up).
</p>


----
----


<p style="width:640px;line-height:1.3em">
If you have two potential blocks of {{On}} bits, but the intersection of those two blocks are {{Off}}, then you can '''XOR''' them together instead of '''OR'''.
If you have two potential blocks of {{On}} bits, but the intersection of those two blocks are {{Off}}, then you can '''XOR''' them together instead of '''OR'''.
</p>


[[File:KMap_Example10.png]]
[[File:KMap_Example10.png]]
Line 242: Line 175:
----
----


<p style="width:640px;line-height:1.3em">
If you have a ''chess board pattern'' in your KV map, you can just XOR all inputs together.
If you have a ''chess board pattern'' in your KV map, you can just XOR all inputs together.
</p>


=== Now its your turn! ===
=== Now its your turn! ===
<p style="width:640px;line-height:1.3em">
Here is a task for you:
Here is a task for you:
</p>


<p style="width:640px;line-height:1.3em">
You get a 4 bit number as input, and you have to display the number in decimal. For this purpose there is the 7-Segment display in the sandbox, which has 7 segments that you can turn on and off.
You get a 4 bit number as input, and you have to display the number in decimal. For this purpose there is the 7-Segment display in the sandbox, which has 7 segments that you can turn on and off.
</p>


<p style="width:640px;line-height:1.3em">
Fill a Karnaugh map for each segment (Seg1 to Seg7) and build a circuit, so that the correct decimal number is displayed for each binary input number. If you want, you can also display 10 as A, 11 as b etc. up to 15 (hex converter). Otherwise the numbers 10-15 do not matter and can be used to build bigger blocks.
Fill a Karnaugh map for each segment (Seg1 to Seg7) and build a circuit, so that the correct decimal number is displayed for each binary input number. If you want, you can also display 10 as A, 11 as b etc. up to 15 (hex converter). Otherwise the numbers 10-15 do not matter and can be used to build bigger blocks.
</p>


<p style="width:640px;line-height:1.3em">
In this picture the input number is a binary 6. Build the circuit in the purple box (the box is way to small, I know), so that for the binary 6 the segments 1,6,7,5,4, and 3 are ''"glowing"''. (And for the rest of the binary numbers as well from 0 to 9). You need a KV map for each segment. Create the "normal" truth table first, and then fill the map, create blocks and OR them together.
In this picture the input number is a binary 6. Build the circuit in the purple box (the box is way to small, i know), so that for the binary 6 the segments 1,6,7,5,4, and 3 are ''"glowing"''. (And for the rest of the binary numbers as well from 0 to 9). You need a KV map for each segment. Create the "normal" truth table first, and then fill the map, create blocks and OR them together.
</p>


[[File:KMap_Exercise.png|640px]]
[[File:KMap_Exercise.png|640px]]
Line 267: Line 190:
----
----


<p style="width:640px;line-height:1.3em">
Happy wiring! Hope you learned something :)
Happy wiring! Hope you learned something :)
</p>

Latest revision as of 20:32, 6 May 2024

What are Karnaugh-Veitch maps?[edit | edit source]

A Karnaugh-Veitch map is a modified truth table for 4 bits, which allows to derive simplified circuits for this table just by looking at it. So every time you come across a logic, that has 3 or 4 bits of input, you can plug its truth table into a KV map and build the circuit.

Okay, so how does it look like?[edit | edit source]

Usually you start with a truth table with 4 inputs and an output column with values that are either or . In this example the output values doesn't matter (yet), but notice that I gave them numbers from 0 to 15 that matches their corresponding input bit pattern.

A Karnaugh map is a truth table, where each bit combination is represented in 2D form. So the outputs are not a straight line like above, but like a square:

As a careful observer, you may have noticed something strange: The input combinations are not numbered 0-1-2-3 (in binary), but 0-1-3-2!

Why though?!

The answer: We make sure, that only 1 bit changes in each step. So if we would go 0-1-2-3, then the step from 1 to 2 in binary would be 01 to 10. Both bits would change, but we only want 1 bit to change at max. This is why we swap the order of the inputs, but make sure, that we still have all possible combinations available.

BUT WHYYY?!

Yes, yes... later...

Changing the order of the input also changes the order in which we fill in the outputs. Going from left to right, skipping the third column and going from top to bottom, skipping the third row. The white numbers are the order in which you plug in the output values.

How does this help me in any way?[edit | edit source]

BLOCKS!

The answer is blocks.

Let me explain...

Humans are very good at visual pattern recognition (if the layout favors it). By using the only-1-bit-change trick, we can now combine bits in blocks of size 1,2,4 and 8. When forming blocks, we only focus on the bits! Leaving the bits alone.

Lets say there are the following 2 green output bits that we are interested in:

Question is: How can we describe these two bits using the bits from the columns and rows?

Row:
The bits that we are interested in, are in the row where:

Column:
The bits that we are interested in, are in the columns where:

We don't need to describe the two columns, because = already covers both columns.

By putting those together, we can describe the bits as 2-bit block. The bigger the block, the less inputs we need to describe it! So we want to make the blocks as big as possible. To describe a 2-bit block, we need 3 inputs - the 4th does not matter (also a feature of our 1-bit-change-only trick).

The block is described by this combined input conditions:

So now we can AND everything together and the block is done.

Any more block limitations?[edit | edit source]

Only the 1,2,4,8 block size rule.

Additional note: The blocks can also go around from left to right, and from top to bottom. So for example, you can do an 8-bit block from left to right (using only one input variable to describe it).

This block is described only by one input variable

Question for you: Can you do a block, that covers only the 4 corners?

So this is it?[edit | edit source]

Not quite.

Since we can only do 1,2,4 and 8 bit blocks, we have to combine multiple blocks together, to cover all outputs. Each one of them has to be part of a block. Overlapping blocks are no problem, they are actually quite helpful to create big blocks for missing bits.

Example[edit | edit source]

This is our truth table, that we already plugged into our Karnaugh map:

Now we have to do blocks of 1,2,4 or 8 (as big as possible) to cover all output bits.

We can do it like this:

We need 3 blocks to cover all bits:

  1. A yellow 2-bit block
  2. A blue 4-bit block
  3. A white 4-bit block

Combined they look like this:

To build the blocks, we AND the inputs and after that we OR the blocks together

And that's it! We created a circuit that describes the truth table completely!


Final notes[edit | edit source]

The whole idea is based on the fact that a circuit like this:

(SuperComplexExpression AND a) OR (SuperComplexExpression AND NOT a)

is the same as just

(SuperComplexExpression)

Because it doesn't matter if A is or - either the first part of the bracket is passed through, or the second part. So if only one bit changes, then we can remove that bit from the equation. (I was asked about that fact in my exam, so maybe it is good to know).


You can do a Karnaugh map for 3 bits, by throwing away the two rows on the bottom and the D input.


You can also do a Karnaugh map for 5 bits, by creating two 4-bit maps. One where the 5th bit is and one where the 5th bit is . Then imagine you lay both maps on top of each other, so you can do additional blocks by piercing through both maps.


The way we collected the bits and put together the blocks is called Disjunctive Normal Form (DNF) which focuses on the output bits, which are then ORd together. There is also a Conjunctive Normal Form (CNF) where you focus on the bits and then AND the blocks together (a bit more complicated - you have to look it up).


If you have two potential blocks of bits, but the intersection of those two blocks are , then you can XOR them together instead of OR.


If you have a chess board pattern in your KV map, you can just XOR all inputs together.

Now its your turn![edit | edit source]

Here is a task for you:

You get a 4 bit number as input, and you have to display the number in decimal. For this purpose there is the 7-Segment display in the sandbox, which has 7 segments that you can turn on and off.

Fill a Karnaugh map for each segment (Seg1 to Seg7) and build a circuit, so that the correct decimal number is displayed for each binary input number. If you want, you can also display 10 as A, 11 as b etc. up to 15 (hex converter). Otherwise the numbers 10-15 do not matter and can be used to build bigger blocks.

In this picture the input number is a binary 6. Build the circuit in the purple box (the box is way to small, I know), so that for the binary 6 the segments 1,6,7,5,4, and 3 are "glowing". (And for the rest of the binary numbers as well from 0 to 9). You need a KV map for each segment. Create the "normal" truth table first, and then fill the map, create blocks and OR them together.


Happy wiring! Hope you learned something :)