Lookup table
Een lookup table (afgekort LUT, Nederlands: opzoektabel) is een datastructuur die wordt gebruikt om de uitvoerwaarden van een functie vooraf op te slaan, zodat deze snel kunnen worden opgehaald zonder de functie opnieuw te moeten berekenen. Lookup tables worden veel toegepast in de informatica, digitale elektronica en signaalverwerking.
Werking
Het basisprincipe van een lookup table is eenvoudig: voor elke mogelijke invoerwaarde wordt de bijbehorende uitvoerwaarde vooraf berekend en opgeslagen in een tabel. Tijdens uitvoering wordt de invoer gebruikt als index om direct de juiste uitvoerwaarde op te halen.
Dit vermijdt complexe of tijdrovende berekeningen en kan de prestaties van een systeem aanzienlijk verbeteren, vooral wanneer dezelfde berekeningen vaak moeten worden uitgevoerd.
Voorbeeld
Een eenvoudig voorbeeld is een tabel voor de functie f(x)=x2:
| x | f(x) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
In plaats van de vermenigvuldiging telkens uit te voeren, kan het resultaat rechtstreeks uit de tabel worden gelezen.
Toepassingen
Lookup tables worden in verschillende domeinen gebruikt:
- Digitale elektronica: In programmeerbare logische schakelingen zoals FPGA's worden LUT’s gebruikt om logische functies te implementeren.
- Grafische verwerking: Voor kleurcorrectie, gamma-correctie en belichting.
- Signaalverwerking: Voor snelle berekening van trigonometrische functies zoals sinus en cosinus.
- Computerspellen: Voor optimalisatie van berekeningen in real-time toepassingen.
In field-programmable gate arrays (FPGA's)
In FPGA's vormen LUT’s de basisbouwstenen van logische implementaties. Een LUT kan worden gezien als een kleine geheugenstructuur die elke mogelijke combinatie van invoerbits koppelt aan een uitvoerbit.
Bijvoorbeeld, een LUT met 3 ingangen heeft 23=8 mogelijke invoercombinaties en dus 8 opgeslagen uitvoerwaarden. Hierdoor kan elke willekeurige logische functie van 3 variabelen worden geïmplementeerd.
Voor- en nadelen
Voordelen
- Snelle toegang tot resultaten (constante tijd)
- Vermijdt complexe berekeningen
- Efficiënt voor herhaald gebruik van dezelfde functie
Nadelen
- Vereist extra geheugen
- Niet efficiënt voor functies met een zeer groot aantal invoercombinaties
- Minder flexibel bij dynamische of onbekende invoerwaarden