Lookup Table - Revision history

DjSapsan: Big addition - using LUT to store characters

2025-09-10T17:52:50Z

Big addition - using LUT to store characters

@@ Line 1: / Line 1: @@
-Any arbitrary logic formula can always be represented in [https://en.wikipedia.org/wiki/Disjunctive_normal_form disjunctive normal form]. Put in simple terms, the output of the formula is computed using a single OR operation on its inputs coming from a number of AND gates. Each AND gate represents a distinct case where the output is supposed to be ''true''.
+{{LUT}}
 [[File:5BitEqualityLut.png|alt=5 bit equality LUT|thumb|5 bit equality LUT]]
-{{LUT}}.
+=== Construction ===
-== Construction ==
+A LUT for formulas is implemented by first creating a list of all input combinations that should lead to a ''true'' output. From this list, the LUT can then be built quite easily.
-A LUT is implemented by first creating a list of all input combinations that should lead to a ''true'' output. From this list, the LUT can then be built quite easily.
+It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a result.
-We can avoid delays by not using [[Buffer|Buffers]], it will make circuit perform the operation in a single tick!
+We can avoid delays by not using [[Buffer|Buffers]], which makes the circuit perform the operation in a single tick.
 In that case, back-propagation must be prevented by using [[Fast Buffer|Fast Buffers]].
-In this case each chain needs one component per input (relays plus Fast Buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.
+Each chain therefore needs one component per input (Relays plus Fast Buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.
 === Complexity to build ===
 When building a LUT as described above, we can count the total number of components as:
 :<math>C = c \cdot (1 + n)</math>
 Where:
 <math>c</math> is the number of distinct '''chains''' (true outputs),<br>
 <math>n</math> is the number of inputs.
-Let's assume half of all possible input combinations lead to a true output:
+Assuming half of all possible input combinations lead to a true output:
 So in total:
 :<math>C = 2^{n-1} \cdot (1 + n)</math>
-In theory it's asymptotically approaching : <math>\mathcal{O}(2^n)</math>
 In other words, the required component count grows exponentially with the number of inputs, assuming the number of true-output cases also scales exponentially.
-While LUT circuits become very expensive in terms of components, they are the '''extremely fast''', producing an output in a single tick regardless of input size. This makes them essential for designs that must run within strict time limits. For non-trivial functions, this speed is usually only achievable by using a LUT.
+== Storing characters for a screen ==
-{{todo|add infobox giving an overview of time and component count maybe?}}
+{{todo|add infobox maybe?}}

Jimmy: /* Construction */

2025-09-09T04:58:28Z

Construction

← Older revision		Revision as of 04:58, 9 September 2025
Line 7:		Line 7:
	It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.		It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.

	We can avoid delays by not using [[Buffer\|~~buffers~~]], it will make circuit perform the operation in a single tick!		We can avoid delays by not using [[Buffer\|Buffers]], it will make circuit perform the operation in a single tick!
	In that case, back-propagation must be prevented by using [[Fast Buffer\|Fast Buffers]].		In that case, back-propagation must be prevented by using [[Fast Buffer\|Fast Buffers]].
	In this case each chain needs one component per input (relays plus Fast Buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.		In this case each chain needs one component per input (relays plus Fast Buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.

Jimmy: fix link

2025-09-09T04:58:13Z

fix link

← Older revision		Revision as of 04:58, 9 September 2025
Line 8:		Line 8:

	We can avoid delays by not using [[Buffer\|buffers]], it will make circuit perform the operation in a single tick!		We can avoid delays by not using [[Buffer\|buffers]], it will make circuit perform the operation in a single tick!
	In that case, back-propagation must be prevented by using [[Fast-Buffers~~\|fast-buffers~~]].		In that case, back-propagation must be prevented by using [[Fast Buffer\|Fast Buffers]].
	In this case each chain needs one component per input (relays plus ~~fast-buffers~~), along with one NOT-gate if there are any inputs that are supposed to be ''off''.		In this case each chain needs one component per input (relays plus Fast Buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.
	=== Complexity to build ===		=== Complexity to build ===
	When building a LUT as described above, we can count the total number of components as:		When building a LUT as described above, we can count the total number of components as:

Jimmy: Make external link external

2025-09-07T20:47:03Z

Make external link external

← Older revision		Revision as of 20:47, 7 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form~~\|Disjunctive~~ normal form]]. Put in simple terms, the output of the formula is computed using a single OR operation on its inputs coming from a number of AND gates. Each AND gate represents a distinct case where the output is supposed to be ''true''.		Any arbitrary logic formula can always be represented in [https://en.wikipedia.org/wiki/Disjunctive_normal_form disjunctive normal form]. Put in simple terms, the output of the formula is computed using a single OR operation on its inputs coming from a number of AND gates. Each AND gate represents a distinct case where the output is supposed to be ''true''.
	[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]		[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

DjSapsan: Made it much simpler by removing some wording. Added a LUT definition using a template. Made formulas clearer.

2025-09-07T17:27:43Z

Made it much simpler by removing some wording. Added a LUT definition using a template. Made formulas clearer.

← Older revision		Revision as of 17:27, 7 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form\|Disjunctive normal form]]. Put in simple terms, ~~this means~~ the output is computed using a single OR-operation~~, whose~~ inputs ~~are formed by~~ AND gates~~, which directly use (possibly negated) inputs~~. Each AND-gate represents a ~~single~~ case where the output is supposed to be ''true''.		Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form\|Disjunctive normal form]]. Put in simple terms, the output of the formula is computed using a single OR operation on its inputs coming from a number of AND gates. Each AND gate represents a distinct case where the output is supposed to be ''true''.
	[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]		[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

	~~In Logic World, this is referred to as a ''lookup table'' (~~LUT~~), which~~ is ~~generally~~ implemented by first creating a list of all input ~~states~~ that should lead to a ''true'' output. From this list, the LUT can then be ~~constructed~~ quite easily. It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.		{{LUT}}.
			== Construction ==
			A LUT is implemented by first creating a list of all input combinations that should lead to a ''true'' output. From this list, the LUT can then be built quite easily.
			It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.

	~~Normally~~, ~~however~~, ~~it is also necessary to prevent~~ back-propagation ~~of signals~~ by using fast-buffers~~, meaning~~ each chain ~~requires as many components as there are inputs to account for~~ relays ~~and~~ fast-buffers, along with one NOT-gate if there are any inputs that are supposed to be off.		We can avoid delays by not using [[Buffer\|buffers]], it will make circuit perform the operation in a single tick!
	== Complexity ==		In that case, back-propagation must be prevented by using [[Fast-Buffers\|fast-buffers]].
	When ~~following the arrangement~~ described above, we can ~~compute the approximate required component~~ count ~~as <math>chainCount \cdot (1 + inputCount)</math>. If we assume that half of the possible input assignments lead to a true output,~~ the number of ~~chains would be equivalent to <math>50% \cdot 2^{inputCount} = 2^{inputCount-1}</math>. If we factor in, that each chain requires <math>1+inputCount</math>~~ components~~, the total can be written~~ as <math>~~2^{inputCount-1}~~ \cdot (1+~~inputCount~~)</math>. Approximately, this could be written as <math>\mathcal{O}(2^{inputCount-1} \cdot (1+inputCount))=\mathcal{O}(2^{inputCount} \cdot (inputCount)) = \mathcal{O}(2^{inputCount})</math>. In order words, the component count scales exponentially with input size, under the assumption that the amount of true assignment also scales exponentially.		In this case each chain needs one component per input (relays plus fast-buffers), along with one NOT-gate if there are any inputs that are supposed to be ''off''.
			=== Complexity to build ===
			When building a LUT as described above, we can count the total number of components as:
			:<math>C = c \cdot (1 + n)</math>
			Where:

	~~While LUTs tend to become incredibly expensive quite quickly, they are~~ '''~~very fast~~''', ~~computing~~ the ~~output in a single tick, regardless~~ of ~~input size~~.		<math>c</math> is the number of distinct '''chains''' (true outputs),<br>
			<math>n</math> is the number of inputs.

	~~Sometimes, LUTs are essential building blocks for designing~~ a ~~more complex circuit within a predefined, small time constraint~~ (~~generally~~ in ~~the range of~~ 2-~~3 ticks~~), ~~as this often means that part~~ of the ~~function needs to be executed~~ in a single tick~~, which,~~ for non-trivial functions, is usually only achievable ~~via~~ a ~~lookup table~~.		Let's assume half of all possible input combinations lead to a true output:

			:<math>c = 50%( 2^n) = 2^{n-1}</math>
			So in total:
			:<math>C = 2^{n-1} \cdot (1 + n)</math>
			In theory it's asymptotically approaching : <math>\mathcal{O}(2^n)</math>

			In other words, the required component count grows exponentially with the number of inputs, assuming the number of true-output cases also scales exponentially.

			While LUT circuits become very expensive in terms of components, they are the '''extremely fast''', producing an output in a single tick regardless of input size. This makes them essential for designs that must run within strict time limits. For non-trivial functions, this speed is usually only achievable by using a LUT.

	{{todo\|add infobox giving an overview of time and component count maybe?}}		{{todo\|add infobox giving an overview of time and component count maybe?}}

GHXX: clarify wording

2025-09-06T13:06:39Z

clarify wording

← Older revision		Revision as of 13:06, 6 September 2025
Line 8:		Line 8:
	When following the arrangement described above, we can compute the approximate required component count as <math>chainCount \cdot (1 + inputCount)</math>. If we assume that half of the possible input assignments lead to a true output, the number of chains would be equivalent to <math>50% \cdot 2^{inputCount} = 2^{inputCount-1}</math>. If we factor in, that each chain requires <math>1+inputCount</math> components, the total can be written as <math>2^{inputCount-1} \cdot (1+inputCount)</math>. Approximately, this could be written as <math>\mathcal{O}(2^{inputCount-1} \cdot (1+inputCount))=\mathcal{O}(2^{inputCount} \cdot (inputCount)) = \mathcal{O}(2^{inputCount})</math>. In order words, the component count scales exponentially with input size, under the assumption that the amount of true assignment also scales exponentially.		When following the arrangement described above, we can compute the approximate required component count as <math>chainCount \cdot (1 + inputCount)</math>. If we assume that half of the possible input assignments lead to a true output, the number of chains would be equivalent to <math>50% \cdot 2^{inputCount} = 2^{inputCount-1}</math>. If we factor in, that each chain requires <math>1+inputCount</math> components, the total can be written as <math>2^{inputCount-1} \cdot (1+inputCount)</math>. Approximately, this could be written as <math>\mathcal{O}(2^{inputCount-1} \cdot (1+inputCount))=\mathcal{O}(2^{inputCount} \cdot (inputCount)) = \mathcal{O}(2^{inputCount})</math>. In order words, the component count scales exponentially with input size, under the assumption that the amount of true assignment also scales exponentially.

	While LUTs tend to become incredibly expensive quite quickly, they are '''very fast''', computing the output in a single tick, regardless of input size. Sometimes, LUTs are ~~the only way of~~ designing a circuit within a predefined, small time constraint (generally in the range of 2-3 ticks).		While LUTs tend to become incredibly expensive quite quickly, they are '''very fast''', computing the output in a single tick, regardless of input size.

			Sometimes, LUTs are essential building blocks for designing a more complex circuit within a predefined, small time constraint (generally in the range of 2-3 ticks), as this often means that part of the function needs to be executed in a single tick, which, for non-trivial functions, is usually only achievable via a lookup table.

	{{todo\|add infobox giving an overview of time and component count maybe?}}		{{todo\|add infobox giving an overview of time and component count maybe?}}

GHXX: fix link text

2025-09-06T13:01:30Z

fix link text

← Older revision		Revision as of 13:01, 6 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form\|~~https://en.wikipedia.org/wiki/~~Disjunctive normal form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.		Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form\|Disjunctive normal form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.
	[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]		[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

GHXX: fix linking cnf instead of dnf

2025-09-06T13:00:03Z

fix linking cnf instead of dnf

← Older revision		Revision as of 13:00, 6 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can always be represented in [[wikipedia:~~Conjunctive_normal_form~~\|~~Conjunctive Normal Form~~]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.		Any arbitrary logic formula can always be represented in [[wikipedia:Disjunctive_normal_form\|https://en.wikipedia.org/wiki/Disjunctive normal form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.
	[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]		[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

GHXX: clarify wording

2025-09-06T12:42:43Z

clarify wording

← Older revision		Revision as of 12:42, 6 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can~~, theoretically,~~ always be represented in [[wikipedia:Conjunctive_normal_form\|Conjunctive Normal Form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.		Any arbitrary logic formula can always be represented in [[wikipedia:Conjunctive_normal_form\|Conjunctive Normal Form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.
	[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]		[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

GHXX: add lut image

2025-09-06T12:41:30Z

add lut image

← Older revision		Revision as of 12:41, 6 September 2025
Line 1:		Line 1:
	Any arbitrary logic formula can, theoretically, always be represented in [[wikipedia:Conjunctive_normal_form\|Conjunctive Normal Form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.		Any arbitrary logic formula can, theoretically, always be represented in [[wikipedia:Conjunctive_normal_form\|Conjunctive Normal Form]]. Put in simple terms, this means the output is computed using a single OR-operation, whose inputs are formed by AND gates, which directly use (possibly negated) inputs. Each AND-gate represents a single case where the output is supposed to be ''true''.
			[[File:5BitEqualityLut.png\|alt=5 bit equality LUT\|thumb\|5 bit equality LUT]]

	In Logic World, this is referred to as a ~~Lookup Table~~ (LUT), which is generally implemented by first creating a list of all input states that should lead to a ''true'' output. From this list, the LUT can then be constructed quite easily. It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.		In Logic World, this is referred to as a ''lookup table'' (LUT), which is generally implemented by first creating a list of all input states that should lead to a ''true'' output. From this list, the LUT can then be constructed quite easily. It consists of multiple relay chains that are simply OR-ed together at the end, where one chain corresponds to one input-assignment that should lead to a truthy output value. The aforementioned relay chains are started by a single NOT-gate whose inputs are all signals that are ''false'' in the case where a ''true'' output is expected, followed by a set of relays where the top input is expected to be ''true'' for such a ''true'' result.

	Normally, however, it is also necessary to prevent back-propagation of signals by using fast-buffers, meaning each chain requires as many components as there are inputs to account for relays and fast-buffers, along with one NOT-gate if there are any inputs that are supposed to be off.		Normally, however, it is also necessary to prevent back-propagation of signals by using fast-buffers, meaning each chain requires as many components as there are inputs to account for relays and fast-buffers, along with one NOT-gate if there are any inputs that are supposed to be off.
Line 7:		Line 8:
	When following the arrangement described above, we can compute the approximate required component count as <math>chainCount \cdot (1 + inputCount)</math>. If we assume that half of the possible input assignments lead to a true output, the number of chains would be equivalent to <math>50% \cdot 2^{inputCount} = 2^{inputCount-1}</math>. If we factor in, that each chain requires <math>1+inputCount</math> components, the total can be written as <math>2^{inputCount-1} \cdot (1+inputCount)</math>. Approximately, this could be written as <math>\mathcal{O}(2^{inputCount-1} \cdot (1+inputCount))=\mathcal{O}(2^{inputCount} \cdot (inputCount)) = \mathcal{O}(2^{inputCount})</math>. In order words, the component count scales exponentially with input size, under the assumption that the amount of true assignment also scales exponentially.		When following the arrangement described above, we can compute the approximate required component count as <math>chainCount \cdot (1 + inputCount)</math>. If we assume that half of the possible input assignments lead to a true output, the number of chains would be equivalent to <math>50% \cdot 2^{inputCount} = 2^{inputCount-1}</math>. If we factor in, that each chain requires <math>1+inputCount</math> components, the total can be written as <math>2^{inputCount-1} \cdot (1+inputCount)</math>. Approximately, this could be written as <math>\mathcal{O}(2^{inputCount-1} \cdot (1+inputCount))=\mathcal{O}(2^{inputCount} \cdot (inputCount)) = \mathcal{O}(2^{inputCount})</math>. In order words, the component count scales exponentially with input size, under the assumption that the amount of true assignment also scales exponentially.

	While LUTs tend to become ~~very~~ expensive quite quickly, they are '''very fast''', computing the output in a single tick, regardless of input size.		While LUTs tend to become incredibly expensive quite quickly, they are '''very fast''', computing the output in a single tick, regardless of input size. Sometimes, LUTs are the only way of designing a circuit within a predefined, small time constraint (generally in the range of 2-3 ticks).

	{{todo\|add infobox giving an overview of time and component count maybe?}}		{{todo\|add infobox giving an overview of time and component count maybe?}}
	~~{{todo\|add screenshot of 5 bit equality LUT}}~~