Look-Up-Table

Look-Up-Table
Die Logarithmentafel als Vorläufer der LUT

In der Informatik und in der Digitaltechnik ist eine Lookup-Tabelle (LUT) eine Datenstruktur, die vorberechnete Daten einer aufwändigen Berechnung enthält. Mithilfe einer solchen Tabelle ist es möglich, komplexe Berechnungen auf die in der Regel erheblich schnellere Wertsuche innerhalb eines Datenfeldes zu vereinfachen. Durch die Verwendung von Lookup-Tabellen wird Berechnungsaufwand durch Speicheraufwand ersetzt.

Inhaltsverzeichnis

Grundprinzip

Die Werte einer Funktion werden vorab ermittelt und im Speicher als Tabelle abgelegt. Damit gleicht das LUT-Verfahren der Benutzung einer Tabelle aus der Vor-Taschenrechner-Ära, wie bei Zinstabellen, im Tafelwerk und manchen Rechenschiebern.

Anwendung in der Programmierung

Prinzip

Die LUT wird in der Informatik als eine Datenstruktur, meist ein (assoziatives) Array, das komplizierte Laufzeitberechnungen durch einen einfachen indizierten Zugriff auf die Datenstruktur ersetzt, realisiert. Dies führt zu einem signifikanten Geschwindigkeitsgewinn, sofern die benötigten Speicherzugriffe schneller sind als die normale Berechnung.

Da die Zugriffe auf den Index der Lookup-Tabelle mit einem geringerwertigeren Datentyp durchgeführt werden können als die in der Tabelle enthaltenen Werte, kann die Methode auch zur Einsparung von Speicherplatz verwendet werden.

Ein klassisches Beispiel ist eine trigonometrische Tabelle. Die Berechnung des Sinus etwa kann sehr lange dauern und ist bei jedem Aufruf der Funktion wiederholt nötig. Um das zu vermeiden, werden zu Beginn einige Werte des Sinus berechnet und in einer Tabelle gespeichert, zum Beispiel für jede ganze Gradzahl. Später, wenn ein konkreter Sinus berechnet werden soll, rundet die Funktion die gewünschte Gradzahl und liest den Sinuswert aus der Tabelle.

Look-Up-Tabellen können auch beliebige Permutationen oder Abbildungen effizient beschreiben. Die Tabellen ersetzen dabei einen Binärbaum, d.h. auch hier wird der Geschwindigkeitsvorteil des schnellen Zugriffs O(1) statt O(nlogn) mit erhöhtem Speicherbedarf erkauft, da relativ viele Einträge in der Tabelle undefiniert sein können. Diese Technik kann aber auch zur einfachen Realisierung von physikalischen Sorts verwendet werden.

Pre-Intervallabbildung und Post-Interpolation

Zu beachten ist weiterhin, dass z. B. ein reelles Argument (bzw. eine Real-Zahl mit einigen Nachkommastellen) erst auf einen natürlichen (Integer-) Index abgebildet werden muss, um als Schlüssel für eine Speicherstelle Verwendung zu finden. Dazu muss, wenn beispielsweise für eine periodische Funktion nur Werte aus der ersten Periode um 0 herum in der LUT vorhanden sind, das Argument zunächst in das Periodenintervall abgebildet („reelles Modulo“) und danach gehasht (auf eine Speicherstelle abgebildet) werden.

Um die Genauigkeit der Berechnung zu verbessern, kann auch ein Interpolations-Algorithmus verwendet werden. Dabei wird versucht, durch mehrere benachbarte Einträge aus der Tabelle (im obigen Beispiel zum Beispiel die darüber und darunter liegende ganze Gradzahl) und einige weitere Berechnungen den Wert genauer abzuschätzen. Das benötigt zwar etwas mehr Zeit, kann die Genauigkeit aber enorm verbessern. Die Methode kann auch dazu verwendet werden, die Lookup-Tabelle bei gleicher Genauigkeit zu verkleinern.

Nachteile

Bei der Benutzung von Lookup-Tabellen ist zu beachten, dass sie auch langsamer als die direkte Berechnung sein können, wenn die Berechnung relativ simpel ist. Das liegt nicht nur an langsamen Speicherzugriffen, sondern auch an einem erhöhten Speicherbedarf und einer Beeinträchtigung des Caches. Dies wird immer wichtiger, da Mikroprozessoren zunehmend schneller als Speicherchips werden. Optimierungen wie die beispielhaft angeführten Sinus-Tabellen sind mit modernen Prozessorgenerationen oft unnötig oder sogar kontraproduktiv.

Anwendung in Integrierten Schaltungen

Beispielhafter Logikblock eines FPGAs, mit LUT und Flipflop

In der digitalen Schaltungstechnik werden im Gegensatz zur Programmierung auch sehr einfache Funktion wie logische Gleichungen (AND, OR, XOR) durch eine LUT ersetzt. Eine Tabelle ist leichter anzupassen als eine Transistorschaltung, daher wird die LUT in der programmierbaren Logik, insbesondere FPGAs und bei der Herstellung von ICs nach Kundenwunsch (ASIC) implementiert.

  • Bei FPGAs wird die Tabelle in einem kleinen SRAM-Feld gespeichert. So kann mit einem Speicher von 16x1 Bit jede logische Funktion mit 4 Eingängen realisiert und durch Programmierung geändert werden.
  • In ASICs wird die LUT u.a. als (Masken-)ROM realisiert. Anstatt einen IC komplett für den Auftraggeber maßzufertigen, werden insbesondere bei Gate Arrays variable Grundschaltungen als LUTs vorgefertigt; nur wenige Fertigungsschritte (Metallisierung) werden speziell für den Kunden ausgeführt.

Eine weitere LUT-Schaltung basiert auf einem 2n-nach-1-Multiplexer mit n Steuereingängen und 2n Speicherstellen. Auch wurden PROM-Speicher zur Realisierung einer 8-Bit-ALU verwendet.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • look-up table — peržvalgos lentelė statusas T sritis informatika apibrėžtis Lentelė, pagal kurią galima susiaurinti duomenų paieškos vietą. Paspartina duomenų peržvalgą ir paiešką, ypač kai ieškoma dideliuose duomenų rinkiniuose. Paruošiama iš anksto intensyviai …   Enciklopedinis kompiuterijos žodynas

  • Look-Up Table — Die Logarithmentafel als Vorläufer der LUT In der Informatik und in der Digitaltechnik ist eine Lookup Tabelle (LUT) eine Datenstruktur, die vorberechnete Daten einer aufwändigen Berechnung enthält. Mithilfe einer solchen Tabelle ist es möglich,… …   Deutsch Wikipedia

  • Colour look-up table — A colour look up table (CLUT) is a mechanism used to transform a range of input colours into another range of colours. It can be a hardware device built into an imaging system or a software function built into an image processing application. The …   Wikipedia

  • color look-up table — ekrano spalvų lentelė statusas T sritis informatika apibrėžtis Lentelė, kurioje surašytos visos ekrano rodomos spalvos ir jas atitinkančių ↑vaizdo signalų kodai. Laikoma vaizdo adapteryje. Jeigu paveiksle yra spalvų, kurių nėra ekrano spalvų… …   Enciklopedinis kompiuterijos žodynas

  • video look-up table — ekrano spalvų lentelė statusas T sritis informatika apibrėžtis Lentelė, kurioje surašytos visos ekrano rodomos spalvos ir jas atitinkančių ↑vaizdo signalų kodai. Laikoma vaizdo adapteryje. Jeigu paveiksle yra spalvų, kurių nėra ekrano spalvų… …   Enciklopedinis kompiuterijos žodynas

  • Colour Look-Up Table — In der Computergrafik bezeichnet man mit indizierten Farben eine Methode zur Speicherung einer Rastergrafik. Bei indizierten Farben enthält die Datenstruktur jedes Pixels nicht direkt die einzelnen Farbwerte, sondern nur einen Index auf einen… …   Deutsch Wikipedia

  • Color Look-up Table —   [Abk. CLUT, dt. Farbindextabelle], eine Tabelle im Header einer Bilddatei, in der die RGB Werte (RGB Farbmodell) aller verwendeten Farben festgehalten sind. Eine Color Look up Table wird v. a. bei Bildern mit geringer Farbtiefe (256 Farben oder …   Universal-Lexikon

  • Look-up Table (LUT) — Таблица поиска; Таблица преобразования, перекодировки; Справочная таблица; Таблица соответствия; Контрольная шкала …   Краткий толковый словарь по полиграфии

  • Table de correspondance — LUT (Look Up Table) est un terme informatique désignant une table de correspondance (aussi appelé tableau de correspondances), qui permet d associer des valeurs. Elle se comporte un peu comme une table de vérité, et désigne sa sortie en fonction… …   Wikipédia en Français

  • Table tennis styles — Table tennis is unique among racket sports in that it supports a large variety of different styles of players. As players levels increase, the diversity of styles decreases slightly, because technically weak styles are quickly eliminated. But… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”