Tables de Correspondance (LUT) : Accès Rapide aux Données par Précalcul
Tables de Correspondance (LUT) : Accès Rapide aux Données par Précalcul
Une Table de Correspondance (LUT - Lookup Table) est une structure de données qui remplace le calcul à l'exécution par un accès mémoire. Elle associe des clés d'entrée à des valeurs de sortie précalculées, échangeant du stockage contre de la vitesse et du déterminisme.
Concept Fondamental
Entrée (Clé) ──► [ Mémoire LUT ] ──► Sortie (Valeur) Index Tableau Données
- Complexité Temporelle : O(1) — Lecture mémoire unique (index tableau) ou recherche hash.
- Complexité Spatiale : O(N) — N entrées stockées.
- Déterminisme : Latence fixe (critique pour temps réel / RTOS dur).
Formes d'Implémentation
| Forme | Structure | Cas d'Usage |
|---|---|---|
| Tableau 1D / Vecteur | sortie = table[entrée] | Mapping direct : Sin(x), Correction gamma, Linéarisation thermocouple, CRC8. |
| Tableau 2D / Multi-D | sortie = table[x][y] | Interpolation bilinéaire, Machines d'état, Tables de vérité (portes logiques). |
| Hash Map / Dictionnaire | sortie = dict[clé] | Clés éparse, Clés non-entières (chaînes, enums), Tables dynamiques. |
| RAM Blocs FPGA/ASIC | Blocs mémoire matériels | DSP : Sin/Cos, CORDIC, Coeff FIR, Conversion espace couleur (RGB→YUV). Latence nulle. |
| Mémoire Texture (GPU) | Textures 1D/2D/3D en cache | Graphismes : Filtrage, Mipmaps. Calcul : LUT interpolées. |
Applications Classiques
- Fonctions Transcendantes : sin, cos, log, exp, sqrt — là où instruction matérielle absente ou lente (MCU 8-bit, cœur soft FPGA).
- Linéarisation : Thermocouple (Type K, J, T), Sonde PT100 (Callendar-Van Dusen), Capteur pression polynomial.
- Couleur / Gamma : sRGB ↔ Linéaire, CMYK ↔ RGB, LUT 3D (Étalonnage couleur, cubes 17×17×17).
- Communications Numériques : Mapping modulation (Constellation QAM), Métriques branches décodeur Viterbi, CRC (piloté par table).
- Systèmes de Contrôle : Ordonnancement gains (vanne non-linéaire → linéarisée), Profils came.
- Cryptographie : S-Boxes (AES SubBytes), Constantes Montgomery précalculées.
- Jeu Vidéo : Lightmaps, Shadow maps, GI précalculé, Courbes animation.
Considérations de Conception
- Résolution vs Taille : Entrée 8-bit = 256 entrées. 16-bit = 65 536 entrées. Interpolation (linéaire/cubique) réduit entrées nécessaires.
- Coût d'Initialisation : Calcul une fois au démarrage / compilation (constexpr). Embarqué dans binaire.
- Localité Cache : Petites LUTs tiennent dans cache L1. Grandes LUTs → défauts cache → plus lent que calcul.
- Précision : Erreur quantification (arrondi index entrée) + Précision sortie. Interpolation réduit erreur.
- Volatilité : Statique (ROM/Flash) vs Dynamique (RAM, mise à jour exécution — ex. égaliseur adaptatif).
Exemple Interpolation (1D Linéaire)
float lut_interp(const float* table, int n, float x, float x_min, float x_max) { float idx = (x - x_min) * (n - 1) / (x_max - x_min); int i = (int)floorf(idx); float frac = idx - i; i = clamp(i, 0, n - 2); return table[i] * (1 - frac) + table[i + 1] * frac; }
Quand NE PAS Utiliser de LUT
- Fonction simple et rapide (ex.
y = 2*x + 1). Le calcul gagne. - Plage d'entrée énorme / précision continue haute (ex. float 32-bit → 4G entrées impossible).
- Mémoire sévèrement contrainte (minuscule MCU, 2 Ko RAM) et fonction calculable en < 10 cycles.
- Données changent chaque cycle (pas de réutilisation).
En Résumé : Les LUTs sont une technique d'optimisation fondamentale — « Espace contre Temps ». Ubiquitaires dans l'embarqué, DSP, graphismes, crypto, calcul scientifique. Profilez d'abord : mesurez cycles calcul vs bande passante/latence mémoire.