imported>Serols: Änderungen von 217.70.138.127 (Diskussion) auf die letzte Version von Johannes Maximilian zurückgesetzt

2025-04-07T09:44:14Z

Änderungen von 217.70.138.127 (Diskussion) auf die letzte Version von Johannes Maximilian zurückgesetzt

Neue Seite

{{Quelle||Dieser Artikel}}
[[Datei:Abramowitz&Stegun.page97.agr.jpg|mini|Die [[Logarithmentafel]] als Vorläufer der LUT]]

'''Lookup-Tabellen''' (LUT) bzw. '''Umsetzungstabellen''' werden in der [[Informatik]] und in der [[Digitaltechnik]] verwendet, um Informationen statisch zu definieren und diese zur [[Laufzeit (Informatik)|Laufzeit]] des Programms – zur Vermeidung aufwändiger Berechnungen oder hohen Speicherverbrauchs – zu benutzen.<ref>{{Internetquelle |url=https://www.itwissen.info/LUT-lookup-table-Wertetabelle.html |titel=LUT (lookup table) :: Wertetabelle :: ITWissen.info |abruf=2019-04-15}}</ref>

== Grundstruktur ==
* In einer [[Tabelle]] werden für bestimmte Konstellationen vorberechnete Ergebnisse oder andere Informationen definiert.
* Die einzelnen Einträge der LUT werden entweder über eine Spalte ''Kurzcode'' (der als Suchbegriff verwendet wird) oder über ihre ''Position'' (Eintrag 01-nn gilt für Sachverhalt 1-nn) identifiziert.
* Jeder Eintrag enthält die ''vordefinierte Information'', bei Bedarf auch weitere für den Eintrag geltende Attribute.
* In der Ausführung von [[Computerprogramm|Programmen]], d. h. zur Verwendung der LUT-Inhalte, wird auf die einzelnen Einträge der LUT durch [[Referenz (Programmierung)|Referenzierung]] (über im Programm gebildete oder verfügbare [[Schlüssel (Datenbank)|Schlüssel]]) zugegriffen.

== Nutzen und Zweck ==
* ''Komplexe Berechnungen'' zur Programmlaufzeit lassen sich durch eine in der Regel schnellere Wertsuche ersetzen.
* ''Speicherplatz'' lässt sich einsparen, weil in den eigentlichen Datenbeständen (mit einer hohen Anzahl von Einträgen) nur ein Kurzcode geführt und die zugehörige Langbezeichnung aus der Tabelle verwendet wird.
* Auch lässt sich der ''Erfassungsaufwand'' sowie die ''Fehlerwahrscheinlichkeit'' durch Eingabe von Kurzcodes (anstatt langer Bezeichnungen) bzw. durch Verwendung von [[Combobox|Auswahlboxen]] (mit [[Voreinstellung|Vorbelegung]] möglicher Eingaben) minimieren.
* Die 'ausgelagerten' Informationen können bei Bedarf ''geändert'' werden (z. B. Langbezeichnungen), ohne die Änderung in den eigentlichen Daten selbst vornehmen zu müssen.

== Speicherung, Erzeugung, Verarbeitung ==
Zur Speicherung und Verarbeitung von Lookup-Tabellen sind folgende Varianten üblich:
# Der Tabelleninhalt wird ''im Programm selbst'' (in speicherinternen Datenstrukturen) gespeichert und zur Verarbeitung verwendet.
# Der Tabelleninhalt wird ''in externen Datenbeständen'' (z. B. in einer [[Datenbanktabelle]] oder einer [[Datei]]) gespeichert. Zur Verarbeitung wird auf diese Daten entweder jeweils direkt zugegriffen oder sie werden bei Programmstart in den internen Speicher des Programms geladen und wie unter 1. verarbeitet.

Zur Erzeugung der LUT-Daten kommen mehrere Verfahrensweisen infrage:
* Die LUT-Inhalte werden im Programm ''statisch definiert;'' nur zu Variante (1) möglich. Änderungen bedingen eine neue Programmversion.
* Die LUT-Inhalte werden automatisch (z. B. bei Programmanfang oder in einem Vorprogramm) ermittelt und ''temporär gespeichert.'' Ist das erzeugende und das verwendende Programm identisch, so kann wie bei (1) intern gespeichert werden. Werden die LUT-Daten von anderen Programmen, evtl. mehreren, benutzt, so wird wie bei (2) extern gespeichert.
* Die LUT-Inhalte werden ''mit einer eigenen Anwendung oder mithilfe von [[Editor (Software)|Standardwerkzeugen zur Datenpflege]]'' erzeugt und geändert. Hierbei ist nur die externe Speicherung gem. (2) üblich.

Externe Lookup-Tabellen definieren sich lediglich über die Art ihrer Verwendung (look-up = "nachschlagen"); bezüglich der Speicherungstechnik unterscheiden sie sich in keiner Weise von anderen Daten.

== Anwendung für vorberechnete Ergebnisse ==
=== Prinzip ===
Die Werte einer [[Funktion (Programmierung)|Funktion]] werden vorab ermittelt und im [[Halbleiterspeicher|Speicher]] als Tabelle abgelegt. Damit gleicht das LUT-Verfahren der Benutzung einer Tabelle aus der Vor-Taschenrechner-Ära, wie bei Zinstabellen, im [[Tafelwerk (Buch)|Tafelwerk]] und manchen [[Rechenschieber]]n.

Die LUT wird als eine [[Datenstruktur]], meist ein ([[Assoziatives Array|assoziatives]]) [[Feld (Datentyp)|Array]], das komplizierte Laufzeitberechnungen durch einen einfachen [[Indexstruktur|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 [[Indexstruktur|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 [[Trigonometrie|trigonometrische]] Tabelle. Die Berechnung des [[Sinus und Kosinus|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.

=== 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 [[Hashing|gehasht]] (auf eine Speicherstelle abgebildet) werden.

Um die Genauigkeit der Berechnung zu verbessern, kann auch ein [[Interpolation (Mathematik)|Interpolations]]-Algorithmus verwendet werden. Dabei wird versucht, durch mehrere benachbarte Einträge aus der Tabelle (im obigen 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 [[Cache]]s. Dies wird immer wichtiger, da Mikroprozessoren zunehmend schneller als Speicherchips werden. [[Optimierer|Optimierungen]] wie die beispielhaft angeführten Sinus-Tabellen sind mit modernen Prozessorgenerationen oft unnötig oder sogar kontraproduktiv.

== Anwendung in Integrierten Schaltungen ==
{{Hauptartikel|Field Programmable Gate Array#Aufbau und Struktur|titel1=„Aufbau und Struktur“ im Artikel Field Programmable Gate Array}}
[[Datei:Logic block.gif|mini|Beispielhafter Logikblock eines FPGAs, mit LUT und Flipflop]]
In der digitalen [[Digitaltechnik|Schaltungstechnik]] werden im Gegensatz zur Programmierung auch sehr einfache Funktionen wie logische Gleichungen ([[Konjunktion (Logik)|AND]], [[Disjunktion|OR]], [[Kontravalenz|XOR]]) durch eine LUT ersetzt. Eine Tabelle ist leichter anzupassen als eine Transistorschaltung, daher wird die LUT in der programmierbaren Logik, insbesondere [[Field Programmable Gate Array|FPGAs]] und bei der Herstellung von [[Integrierter Schaltkreis|ICs]] nach Kundenwunsch ([[Anwendungsspezifische integrierte Schaltung|ASIC]]), implementiert.
* Bei FPGAs wird die Tabelle in einem kleinen [[Static random-access memory#Schreibzugriff|SRAM]]-Feld gespeichert. So kann mit einem Speicher von 16×1 Bit jede logische Funktion mit 4 Eingängen realisiert und durch ''Programmierung'' geändert werden. Die Anzahl der LUT-Eingänge hängt von der FPGA-Architektur ab.
* In ASICs wird die LUT u. a. als [[Festwertspeicher|(Masken-)ROM]] realisiert. Anstatt einen IC komplett für den Auftraggeber maßzufertigen, werden insbesondere bei [[Gate-Array]]s variable Grundschaltungen als LUTs vorgefertigt; nur wenige Fertigungsschritte ([[Leiterbahn|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 [[Programmable Read-Only Memory|PROM]]-Speicher zur Realisierung einer 8-Bit-[[Arithmetisch-logische Einheit|ALU]] verwendet.

== Anwendung für Wertausprägungen ==
Hierbei werden in Lookup-Tabellen Einträge für beliebige anwendungsbezogene Inhalte (z. B. Informationen je Bundesland, je Branche, je Kfz-Ortskennzeichen, je Währung, je Fehlercode etc.) geführt. Die Einträge bestehen i. d. R. aus einer Kurz-Identifikation und weiteren Attributen, z. B. einer ausführlichen Bezeichnung. Die Tabellen können wie folgt benutzt werden:
* Bei der Erfassung von Attributwerten für die betrieblichen Datenbestände (nicht für die LUT!) werden nur in der LUT vorhandene Einträge als ''gültig'' akzeptiert bzw. zur Eingabeauswahl angeboten.
* In den betrieblichen Daten, z. B. je Kunde, wird (anstelle der ausführlichen Bezeichnung) nur ein ''Kurzcode'' gespeichert; die ausführliche Bezeichnung kann bei Bedarf dargestellt werden.
* Evtl. erforderliche ''Änderungen in der Schreibweise'' von Bezeichnungen müssen nur in der LUT vorgenommen werden.

''Beispiel:''
* Eine Bank muss die Höhe der Kredite je Branche monatlich melden.
* In der Meldung ist je Branche eine Zeile mit der ausführlichen Branchenbezeichnung gefordert, z. B. Land- und Forstwirtschaft; öffentliche Haushalte; Industrie und Handwerk ...
* Die Reihenfolge der Zeilen ist von der Meldebehörde fest vorgegeben.
* In einer LUT werden alle zur Meldung vorgesehenen Branchen geführt – mit Inhalt 'Branchenschlüssel, Branchenbezeichnung, Zeilennummer'.
* Für jeden Kredit (bzw. Kunden) ist festgelegt, zu welcher Branche er gehört; der jeweilige Branchenschlüssel (3 Stellen) ist gespeichert.
* Zur Erstellung der Meldung werden in der IT-Anwendung die Kreditssummen je Branchenschlüssel gebildet, nach Zeilennummer (aus der LUT) sortiert und die Branchenbezeichnung wird aus der LUT zugeordnet.
Die Einzelzeilen der Branchenmeldung könnten dann z. B. wie folgt aussehen:
ZL-NR Branchenbezeichnung Kreditsumme
01 Öffentliche Haushalte 1) 1.234.567 2)
02 Land- und Forstwirtschaft 567.890
1) = aus der Lookup-Tabelle zugeordnet 2) über Branchenschlüssel aggregiert

== Siehe auch ==
* [[Indizierte Farben|Farbpalette]]
* [[Wahrheitstabelle]]

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Programmierbare Logik]]

Lookup-Tabelle - Versionsgeschichte

imported>Serols: Änderungen von 217.70.138.127 (Diskussion) auf die letzte Version von Johannes Maximilian zurückgesetzt