Lookup table

The logarithm table as the forerunner of the LUT

Lookup tables (LUT) or conversion tables are used in computer science and digital technology to statically define information and to use it during the runtime of the program - in order to avoid complex calculations or high memory consumption.

Basic structure

In a table , precalculated results or other information are defined for certain constellations.
The individual entries of the LUT are identified either by a short code column (which is used as a search term) or by their position (entry 01-nn applies to facts 1-nn).
Each entry contains the predefined information and , if necessary, other attributes that apply to the entry .
In the execution of programs , i. H. To use the LUT contents, the individual entries of the LUT are accessed by referencing (using keys created or available in the program ).

Use and purpose

Complex calculations for the program runtime can be replaced by a usually faster value search.
Storage space can be saved because only a short code is kept in the actual data sets (with a large number of entries) and the associated long description from the table is used.
The recording effort and the probability of errors can also be minimized by entering short codes (instead of long names) or by using selection boxes (with pre-allocation of possible entries).
The 'outsourced' information can be changed if necessary (e.g. long names) without having to change the actual data yourself.

Storage, generation, processing

The following variants are common for storing and processing lookup tables:

The table contents are saved in the program itself (in memory-internal data structures) and used for processing.
The table contents are saved in external databases (e.g. in a database table or a file ). For processing, these data are either accessed directly or they are loaded into the internal memory of the program when the program is started and processed as under 1.

There are several ways of generating the LUT data:

The LUT contents are statically defined in the program ; only possible for variant (1). Changes require a new program version.

The LUT contents are determined automatically (e.g. at the beginning of the program or in a preliminary program) and temporarily saved. If the generating and the using program are identical, you can save internally as in (1). If the LUT data are used by other programs, possibly more than one, it is saved externally as in (2).

The LUT contents are generated and changed with a dedicated application or with the help of standard tools for data maintenance . Only the external storage according to (2) common.

External lookup tables are only defined by the way they are used (look-up = "look up"); in terms of storage technology, they do not differ in any way from other data.

Application for pre-calculated results

principle

The values of a function are determined in advance and stored in the memory as a table. The LUT method is like using a table from the pre-pocket calculator era, such as with interest tables, in tables and some slide rules .

The LUT is implemented as a data structure , usually an ( associative ) array , which replaces complicated runtime calculations with simple indexed access to the data structure. This leads to a significant gain in speed, provided that the required memory accesses are faster than the normal calculation.

Since the accesses to the index of the lookup table can be carried out with a data type of less value than the values contained in the table, the method can also be used to save storage space.

A classic example is a trigonometric table. The calculation of the sine, for example, can take a long time and is necessary repeatedly each time the function is called. To avoid this, some values of the sine are calculated at the beginning and stored in a table, for example for each whole number of degrees. Later, when a specific sine is to be calculated, the function rounds the desired number of degrees and reads the sine value from the table.

Pre-interval mapping and post-interpolation

It should also be noted that z. B. a real argument (or a real number with a few decimal places) must first be mapped to a natural (integer) index in order to be used as a key for a storage location. For this purpose, if, for example, only values from the first period around 0 are available in the LUT for a periodic function, the argument must first be mapped into the period interval ("real modulo") and then hashed (mapped to a memory location).

An interpolation algorithm can also be used to improve the accuracy of the calculation . An attempt is made to estimate the value more precisely using several neighboring entries from the table (in the above example the whole number of degrees above and below) and some other calculations. This takes a little more time, but can improve the accuracy enormously. The method can also be used to reduce the size of the lookup table with the same accuracy.

disadvantage

When using lookup tables, it should be noted that they can be slower than the direct calculation if the calculation is relatively simple. This is not only due to slow memory access, but also an increased memory requirement and an impairment of the cache . This is becoming increasingly important as microprocessors become increasingly faster than memory chips. Optimizations such as the example sine tables are often unnecessary or even counterproductive with modern processor generations.

Use in integrated circuits

Exemplary logic block of an FPGA, with LUT and flip-flop

In digital circuit technology , in contrast to programming, very simple functions such as logical equations ( AND , OR , XOR ) are replaced by a LUT. A table is easier to adapt than a transistor circuit, so the LUT is implemented in the programmable logic, especially FPGAs and in the manufacture of ICs according to customer requirements ( ASIC ).

With FPGAs the table is saved in a small SRAM field. With a memory of 16 × 1 bit, every logical function with 4 inputs can be implemented and changed by programming . The number of LUT inputs depends on the FPGA architecture.
In ASICs the LUT u. a. realized as (mask) ROM . Instead of custom-making an IC completely for the client, variable basic circuits are prefabricated as LUTs , especially with gate arrays ; only a few production steps ( metallization ) are carried out specifically for the customer.

Another LUT circuit is based on a 2 ⁿ -to-1 multiplexer with n control inputs and 2 ⁿ storage locations. Also were PROM -Speicher for realizing an 8-bit ALU used.

Application for values

Entries for any application-related content (e.g. information per federal state, per branch, per vehicle registration number, per currency, per error code, etc.) are kept in look-up tables. The entries consist i. d. Usually from a short identification and other attributes, e.g. B. a detailed description. The tables can be used as follows:

When capturing attribute values for the operational databases (not for the LUT!), Only entries in the LUT are accepted as valid or offered for input selection.
In the operational data, e.g. B. per customer, only a short code is saved (instead of the detailed description) ; the detailed description can be shown if necessary.
Possibly. required changes in the spelling of designations only need to be made in the LUT.

Example:

A bank must report the amount of the loans per industry on a monthly basis.
In the report, a line with the detailed description of the industry is required for each industry, e.g. B. Agriculture and Forestry; public budgets; Industry and trade ...
The order of the lines is fixed by the registration authority.
All industries intended for reporting are listed in a LUT - with the content 'Industry code, industry description, line number'.
For each loan (or customer) it is determined which branch it belongs to; the relevant branch code (3 digits) is saved.
To create the report, the credit sums for each branch key are formed in the IT application, sorted by line number (from the LUT) and the branch name is assigned from the LUT.

The individual lines of the industry message could then z. B. look like this:

ZL-NR   Branchenbezeichnung                 Kreditsumme
 01     Öffentliche Haushalte ¹⁾              1.234.567 ²⁾
 02     Land- und Forstwirtschaft               567.890
        ^{1) = aus der Lookup-Tabelle zugeordnet           2) über Branchenschlüssel aggregiert}

Individual evidence

↑ LUT (lookup table) :: Value table :: ITWissen.info. Retrieved April 15, 2019 .

[1] LUT (lookup table) :: Value table :: ITWissen.info. Retrieved April 15, 2019 .