Lookup Table

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

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.

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.

Complexity

When following the arrangement described above, we can compute the approximate required component count as $chainCount\cdot (1+inputCount)$. If we assume that half of the possible input assignments lead to a true output, the number of chains would be equivalent to $50\mathrm{\%}\cdot 2^{inputCount}=2^{inputCount-1}$. If we factor in, that each chain requires $1+inputCount$ components, the total can be written as $2^{inputCount-1}\cdot (1+inputCount)$. Approximately, this could be written as ${𝒪}(2^{inputCount-1}\cdot (1+inputCount))={𝒪}(2^{inputCount}\cdot (inputCount))={𝒪}(2^{inputCount})$. 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).

TODO: add infobox giving an overview of time and component count maybe?