Lookup table

Lookup tables (LUT ) and conversion tables are used in computer science and in digital technology to define static information and this at runtime of the program - to use - to avoid consuming calculations and high memory consumption.

Basic structure

• In a table pre-calculated results and other information are defined for specific constellations.
• The individual entries in the LUT are either a column short code (which is used as a search term ) or through their position ( entry 01 -nn applies to the facts 1 -nn ) identified.
• Each entry contains the predefined information, if necessary, any other applicable attributes for the entry.
• In the execution of programs, that is, to use the LUT contents to be accessed, the individual entries of the LUT by reference (via the program formed or available keys).

Benefits and Purpose

• Complex calculations for duration of the program can be replaced by a generally faster value search.
• Space can be saved because in the actual data sets ( with a high number of entries ) performed only a short code and the associated long- term is used in the table.
• Also can be minimized ( with pre-assignment of possible inputs ) of the acquisition cost and the probability of error by entering short code ( instead of long names ) or by using selection boxes.
• The ' outsourced ' information can be changed as required ( eg long names) without having to make the change in the actual data itself.

Storage, production, processing

For the storage and processing of lookup tables, the following variants are common:

To generate the LUT data several procedures being:

• The LUT contents are defined statically in the program; only variant ( 1 ) is possible. Changes require a new version of the program.
• The LUT content is automatically (eg when starting the program or in a pre-program ) is determined and stored temporarily. If the generating and the program used the same, so can be stored internally as in ( 1). If the LUT data from other programs, possibly several, used, is stored externally as in ( 2).
• The LUT contents are created and modified with a custom application or by using standard tools for data maintenance. Here, only the external storage is acc. ( 2) common.

External lookup tables are defined only on the type of use ( look-up = " look up "); regard to the storage technology, they differ in any way from other data.

Application for pre-computed results

Principle

The values ​​of a function are determined in advance and stored in memory as a table. Thus, the LUT method is similar to the use of a table from the pre- calculator era, as with interest tables, in board work and some slide rules.

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

Since the requests may be performed on the index of the lookup table with a geringerwertigeren data type than the values ​​shown in the table, the method also for saving space can be used.

A classic example is a trigonometric table. The calculation of the sine for example, can take a long time and is repeated as necessary at each call of the function. To avoid this, some of the values ​​calculated at the start of the sine wave and stored in a table, for example for any integer number of degrees. Later, when a specific sine is to be calculated, the function completes the desired number of degrees, and reads the value from the sine table.

Pre- interval mapping and post- interpolation

You should also remember that, for example, a real argument (or a real number with some decimals) must be mapped only to a natural ( integer ) index to be used as a key to a storage location. To do this, if only values ​​from the first period are provided in the LUT, for example, a periodic function around 0, the argument is initially displayed in the period interval ( " real modulus " ) and then hashed ( mapped to a memory location ) can be.

To improve the accuracy of the calculation, and an interpolation algorithm can be used. An attempt is made by several adjacent entries from the table ( in the example above it and below it whole number of degrees ) and some additional calculations to assess the value accurately. Although this requires a little more time, but the accuracy can improve tremendously. The method can also be used to shrink the look-up table with the same accuracy.

Disadvantages

When using lookup tables is important to note that they may be slower than the direct calculation if the calculation is relatively simple. This is not only to slow memory accesses but also to an increased memory requirement and a deterioration of the cache. This is increasingly important as microprocessors become increasingly faster than memory chips. Optimizations as exemplified sine tables are equipped with modern processor generations often unnecessary or even counterproductive.

Application in integrated circuits

In the digital circuit technique also very simple functions such as logic equations (AND, OR, XOR ) will be replaced by a LUT, in contrast to programming. A table is easier to adapt as a transistor circuit, therefore, the LUT in the programmable logic, in particular FPGAs, and in the manufacture of ICs, according to the customer (ASIC) that implements.

• FPGAs with the table is stored in a small SRAM array. It can be realized with 4 inputs and changed by programming a memory of 16 x 1 bit each logical function. The number of LUT inputs depends on the FPGA architecture.
• In ASICs, the LUT et al realized as (mask ) ROM. Instead of a complete IC maßzufertigen for the principal, variable basic circuits are prefabricated as LUTs especially in gate arrays; only a few production steps ( metallization ) are performed specifically for the customer.

Another LUT circuit based on a 2n -to- 1 multiplexer having n inputs and 2n control memory locations. And PROM memory are used to implement an 8 -bit ALU.

Application forms for value

These entries for any application-related content is done ( information per state, per sector, per vehicle location identifier, for each currency, the error code etc. for example ) in lookup tables. The entries consist typically of a short - identification and other attributes, such as a detailed description. The tables can be used as follows:

• In the detection of attribute values ​​for the operational databases (not for the LUT! ) Existing entries are accepted as valid or offered for input selection only in the LUT.
• In the operational data, such as per customer is stored only a short code (instead of the detailed designation); the detailed description can be shown when needed.
• Possibly. necessary changes in the spelling of names need only be made in the LUT.

Example:

• A bank must report monthly to the amount of credits per sector.
• In the message one line is required with the detailed industry designation for each industry, such as agriculture and forestry; public budgets; Industry and crafts ...
• The order of the rows is predefined by the registration authority.
• In a LUT all scheduled to report industries are out - with content ' industry classification, industry name, line number '.
• For each loan (or customers ) is set to which industry it belongs; the respective industry key (3 digits) is stored.
• To create the message in the IT application, the credit totals per sector keys are formed by line number ( from the LUT ) sorted and the industry designation is assigned from the LUT.

The individual lines in the industry message could then look something like this:

ZL- NR industry term loan amount   01 Public sector 1) 1,234,567 2)   02 Agriculture and forestry 567 890          1) = from the lookup table associated with 2) Industry key aggregates see also

• Color palette
• Truth table

• Data structure
• Programmable Logic