K-map - Revision history

173.48.100.6: /* AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA */

2024-05-06T20:32:29Z

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

← Older revision		Revision as of 20:32, 6 May 2024
Line 107:		Line 107:
	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:

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

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

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


	=== Final notes ===		=== Final notes ===

BlockOG: A couple typos fixed, and Is capitalized

2023-11-21T19:21:27Z

A couple typos fixed, and Is capitalized

← Older revision		Revision as of 19:21, 21 November 2023
Line 1:		Line 1:
	{{guide\|narrow=1}}		{{guide\|narrow=1}}
	=== What are Karnaugh-Veitch maps? ===		=== What are Karnaugh-Veitch maps? ===
	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.		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? ===		=== Okay, so how does it look like? ===
	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.

	[[File:4bit_TruthTable_decimal_output.png]]		[[File:4bit_TruthTable_decimal_output.png]]
Line 30:		Line 30:
	'''BLOCKS!'''		'''BLOCKS!'''

	The ~~anwser~~ is blocks.		The answer is blocks.

	Let me explain...		Let me explain...
Line 137:		Line 137:
	[[File:KMap_circuit_combining_blocks.png\|640px]]		[[File:KMap_circuit_combining_blocks.png\|640px]]

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

	=== Final notes ===		=== Final notes ===
Line 183:		Line 183:
	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.

	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.

	[[File:KMap_Exercise.png\|640px]]		[[File:KMap_Exercise.png\|640px]]

UnsignedRobin: /* Example */

2023-11-19T00:05:52Z

Example

← Older revision		Revision as of 00:05, 19 November 2023
Line 123:		Line 123:
	Combined they look like this:		Combined they look like this:

	{\| 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]]
	\|-		\|-

UnsignedRobin: /* Any more block limitations? */

2023-11-19T00:05:35Z

Any more block limitations?

← Older revision		Revision as of 00:05, 19 November 2023
Line 91:		Line 91:
	This block is described only by one input variable		This block is described only by one input variable

	{\| 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]]
	\|-		\|-

UnsignedRobin: /* How does this help me in any way? */

2023-11-19T00:05:19Z

How does this help me in any way?

← Older revision		Revision as of 00:05, 19 November 2023
Line 48:		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 57:		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 71:		Line 71:
	The block is described by this combined input conditions:		The block is described by this combined input conditions:

	{\| 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]]
	\|-		\|-

Gelthor: Use template {{guide|narrow=1}}

2023-11-11T16:47:09Z

Use template {{guide|narrow=1}}

Show changes

UnsignedRobin at 18:11, 30 October 2023

2023-10-30T18:11:36Z

← Older revision		Revision as of 18:11, 30 October 2023
Line 187:		Line 187:
	</p>		</p>

	[[File:KMap_circuit_combining_blocks.png]]		[[File:KMap_circuit_combining_blocks.png\|640px]]

	<p style="width:640px;line-height:1.3em">		<p style="width:640px;line-height:1.3em">

UnsignedRobin at 18:01, 30 October 2023

2023-10-30T18:01:22Z

← Older revision		Revision as of 18:01, 30 October 2023
Line 72:		Line 72:
	\| [[File:D_boxed.png]] \|\| [[File:C_boxed.png]]		\| [[File:D_boxed.png]] \|\| [[File:C_boxed.png]]
	\|-		\|-
	\| [[File:Off.png~~\|frameless~~\|24px]] \|\| [[File:On.png\|frameless\|24px]]		\| [[File:Off.png\|24px]] \|\| [[File:On.png\|frameless\|24px]]
	\|}		\|}

Line 81:		Line 81:
	\| [[File:A_boxed.png]]		\| [[File:A_boxed.png]]
	\|-		\|-
	\| [[File:On.png~~\|frameless~~\|24px]]		\| [[File:On.png\|24px]]
	\|}		\|}

Line 101:		Line 101:
	\| [[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]]
	\|-		\|-
	\| [[File:Off.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]]		\| [[File:Off.png\|24px]] \|\| [[File:On.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:On.png\|24px]]
	\|}		\|}

Line 129:		Line 129:
	\| [[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]]
	\|-		\|-
	\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:Off.png~~\|frameless~~\|24px]]		\| [[File:Cross_gray.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:Off.png\|24px]]
	\|}		\|}

Line 165:		Line 165:
	</p>		</p>

	#[[File:YellowBox.png~~\|frameless~~\|14px]] A yellow 2-bit block		#[[File:YellowBox.png\|14px]] A yellow 2-bit block
	#[[File:BlueBox.png~~\|frameless~~\|14px]] A blue 4-bit block		#[[File:BlueBox.png\|14px]] A blue 4-bit block
	#[[File:WhiteBox.png~~\|frameless~~\|14px]] A white 4-bit block		#[[File:WhiteBox.png\|14px]] A white 4-bit block

	<p style="width:640px;line-height:1.3em">		<p style="width:640px;line-height:1.3em">
Line 176:		Line 176:
	\| \|\| [[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]]
	\|-		\|-
	\| [[File:YellowBox.png]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]]		\| [[File:YellowBox.png]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:On.png\|24px]] \|\| [[File:On.png\|24px]] \|\| [[File:On.png\|24px]]
	\|-		\|-
	\| [[File:BlueBox.png]] \|\| [[File:On.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:Off.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]]		\| [[File:BlueBox.png]] \|\| [[File:On.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:Off.png\|24px]] \|\| [[File:Cross_gray.png\|24px]]
	\|-		\|-
	\| [[File:WhiteBox.png]] \|\| [[File:On.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:Cross_gray.png~~\|frameless~~\|24px]] \|\| [[File:On.png~~\|frameless~~\|24px]]		\| [[File:WhiteBox.png]] \|\| [[File:On.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:Cross_gray.png\|24px]] \|\| [[File:On.png\|24px]]
	\|}		\|}

UnsignedRobin: Layout

2023-10-30T17:47:27Z

Layout

Show changes

UnsignedRobin at 16:51, 30 October 2023

2023-10-30T16:51:00Z

← Older revision		Revision as of 16:51, 30 October 2023
Line 6:		Line 6:

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


	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.
Line 13:		Line 12:
	[[File:KMap_undefined_output.png]]		[[File:KMap_undefined_output.png]]

	As a careful observer, you may have noticed something strange: The input combinations are not numbered 0-1-2-3 (in binary), but ~~[b]~~0-1-3-2~~[/b]~~!		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'''!

	~~[quote=Whyman]~~Why though?![/~~quote]~~		<blockquote>Why though?!</blockquote>

	The answer: We make sure, that ~~[b]~~only 1 bit changes in each step~~[/b]~~. So if we would go 0-1-2-3, then the step from 1 to 2 in binary would be 01 to 10. ~~[b]~~Both~~[/b]~~ 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.

	~~[quote=Whyman]~~BUT WHYYY?! [/~~quote]~~		<blockquote>BUT WHYYY?!</blockquote>
	Yes, yes... later...		Yes, yes... later...

Line 28:		Line 27:

	=== How does this help me in any way? ===		=== How does this help me in any way? ===
	~~[b]~~BLOCKS!~~[/b]~~		'''BLOCKS!'''

	The anwser is blocks.		The anwser is blocks.
Line 34:		Line 33:
	Let me explain...		Let me explain...

	Humans are very good at visual pattern recognition (if the layout favors it). By using the ~~[i]~~only-1-bit-change~~[/i]~~ 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.

	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:

	[[File:KMap_Example1.png]]		[[File:KMap_Example1.png]]


	Question is: How can we describe these two bits using the bits from the columns and rows?		Question is: How can we describe these two bits using the bits from the columns and rows?
Line 45:		Line 43:
	[[File:KMap_Example2.png]]		[[File:KMap_Example2.png]]
	[[File:KMap_Example3.png]]		[[File:KMap_Example3.png]]
	⠀

	'''Row:'''<br>		'''Row:'''<br>
Line 79:		Line 76:
	\|}		\|}

	So now we can ~~[b]~~AND~~[/b]~~ everything together and the block is done.		So now we can '''AND''' everything together and the block is done.

	[[File:KMap_circuit_block.png]]		[[File:KMap_circuit_block.png]]
Line 86:		Line 83:
	Only the 1,2,4,8 block size rule.		Only the 1,2,4,8 block size rule.

	Additional note: The blocks can also ~~[i][b]~~go around~~[/b][/i]~~ 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).

	[[File:KMap_around.png]]		[[File:KMap_around.png]]
Line 98:		Line 95:
	\|}		\|}

	~~[b]~~Question for you:~~[/b] [i]~~Can you do a block, that covers only the 4 corners?~~[/i]~~		'''Question for you:''' ''Can you do a block, that covers only the 4 corners?''

	=== So this is it? ===		=== So this is it? ===
Line 133:		Line 130:
	\|}		\|}

	To build the blocks, we ~~[b]~~AND~~[/b]~~ the inputs and after that we ~~[b]~~OR~~[/b]~~ the blocks together		To build the blocks, we '''AND''' the inputs and after that we '''OR''' the blocks together

	[[File:KMap_circuit_combining_blocks.png]]		[[File:KMap_circuit_combining_blocks.png]]
Line 142:		Line 139:
	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:

	[code]		<code>
	(SuperComplexExpression AND a) OR (SuperComplexExpression AND NOT a)		(SuperComplexExpression AND a) OR (SuperComplexExpression AND NOT a)
	[/code]		</code>

	is the same as just		is the same as just

	[code]		<code>
	(SuperComplexExpression)		(SuperComplexExpression)
	[/code]		</code>

	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).
Line 164:		Line 161:
	----		----

	The way we collected the bits and put together the blocks is called ~~[i]~~Disjunctive Normal Form (DNF)~~[/i]~~ which focuses on the {{On}} output bits, which are then ~~[b]ORd[/b]~~ together. There is also a ~~[i]~~Conjunctive Normal Form (CNF)~~[/i]~~ where you focus on the {{Off}} bits and then ~~[b]~~AND~~[/b]~~ 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).

	----		----

	If you have two potential blocks of {{On}} bits, but the intersection of those two blocks are {{Off}}, then you can ~~[b]~~XOR~~[/b]~~ them together instead of ~~[b]~~OR~~[/b]~~.		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'''.

	[[File:KMap_Example10.png]]		[[File:KMap_Example10.png]]
Line 174:		Line 171:
	----		----

	If you have a ~~[i]~~chess board pattern~~[/i]~~ 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.

	----		----
Line 185:		Line 182:
	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.

	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 ~~[i]~~"glowing"~~[/i]~~. (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.

	[[File:KMap_Exercise.png]]		[[File:KMap_Exercise.png]]