Lookup Table: Difference between revisions

Revision as of 17:27, 7 September 2025

Any arbitrary logic formula can always be represented in 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.

Lookup table

In Logic World, a Lookup table (LUT) is a circuit that explicitly encodes all possible input cases and assigns a specific output to each case.

The output may be a single bit or a pattern of bits.

Examples:

read-only memory (ROM) (general example)
storing characters for a screen (particular example)
a hard-coded complex formula.

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.

We can avoid delays by not using buffers, it will make circuit perform the operation in a single tick! In that case, back-propagation must be prevented by using 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.

Complexity to build

When building a LUT as described above, we can count the total number of components as:

C = c \cdot (1 + n)

Where:

$c$ is the number of distinct chains (true outputs),
$n$ is the number of inputs.

Let's assume half of all possible input combinations lead to a true output:

c = 50 % (2^{n}) = 2^{n - 1}

So in total:

C = 2^{n - 1} \cdot (1 + n)

In theory it's asymptotically approaching : $𝒪 (2^{n})$

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?

@@ 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]]
-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?}}