Table de correspondance

Une table de correspondance, aussi appelée tableau de correspondances ou Lookup Table (LUT) en anglais, est une liste d'association de valeurs utilisée en informatique et électronique. Elle se comporte sur le même modèle qu'une table de vérité désignant sa sortie de manière unique en fonction de ses entrées et du contenu de la table.

Description

Il s'agit d'une structure de données stockée en mémoire, employée pour remplacer un calcul par une opération plus simple de consultation. Le gain de vitesse peut être significatif, car rechercher une valeur en mémoire est souvent plus rapide qu'effectuer un calcul important.

Exemples

L'exemple classique est celui de la table trigonométrique. Dans certaines applications, le calcul d'un sinus peut s'avérer récurrent et par conséquent ralentir l'exécution. Pour éviter cela, l'application va précalculer au démarrage les valeurs dont elle aura souvent besoin, par exemple le sinus de tous les angles entiers. Ces données seront alors enregistrées dans une LUT. Chaque fois que l'application aura besoin d'une valeur, elle pourra consulter la LUT pour trouver la valeur la plus proche. La mémoire stockant la table de correspondance peut également être statique, enregistrée directement au sein du circuit électronique dans certains circuits dédiés.

Avant l'arrivée des ordinateurs, des tables semblables ont été employées pour accélérer les calculs à la main. Les plus particulièrement répandues furent les tables de trigonométrie, les tables logarithmiques et les fonctions de densité en statistique. De telles tables sont souvent employées de nos jours dans l'électronique embarquée et notamment en électronique de puissance pour la commande d'onduleurs. Une LUT est également un élément central des circuits programmables, notamment des FPGA, permettant de réaliser des circuits logiques génériques.

Autres exemples : ces tables sont employées pour corriger la linéarité du rendu des couleurs (correction du gamma) sur les écrans vidéo ou pour les cartes graphiques des systèmes informatiques.

Infographie

L'infographie et les applications web utilisent depuis l'origine des tables de correspondances pour permettre un codage de pixel ou de zone en couleurs sur un seul octet, les palettes font correspondre un octet à un triplet {rouge, vert, bleu}. L'utilisateur peut calculer la palette la mieux adaptée à une image et l'annexer au fichier. Les conversions de couleur basées sur le profil ICC fonctionnent avec les trois composantes en entrée et en sortie, le logiciel devant interpoler entre un nombre restreint de points. Les cartes graphiques et les logiciels d'édition photo et vidéo modernes supportent désormais presque tous nativement l'utilisation de tables de correspondance.

Les tables de correspondance en vue de modifier des couleurs doivent faire correspondre des triplets RGB. Une table complète avec des composantes de couleur définies sur 8 bits aurait un index de trois octets, soit 2²⁴ valeurs, et 4 GiB de données. Pour éviter cela, les tables codent un nombre limité de valeurs entre lesquelles les logiciels effectuent des interpolations linéaires ou cubiques entre les valeurs qui encadrent celle à traiter sur chacun des axes. Les tables ont d'ordinaire 17 valeurs sur chaque axe, un total de 4 913 triplets (<16 kiB).

Voir aussi

• Rainbow table