Tablas de Búsqueda (LUT): Acceso Rápido a Datos mediante Precomputación

Tablas de Búsqueda (LUT): Acceso Rápido a Datos mediante Precomputación

Una **Tabla de Búsqueda (LUT)** es una estructura de datos que reemplaza el **cálculo en tiempo de ejecución** con **acceso a memoria**. Mapea claves de entrada a valores de salida precomputados, intercambiando almacenamiento por velocidad y determinismo.

Concepto Central

 Entrada (Clave) ──► [ Memoria LUT ] ──► Salida (Valor) Índice Arreglo Datos 
  • Complejidad de Tiempo: O(1) — Una sola lectura de memoria (índice de arreglo) o búsqueda con hash.
  • Complejidad de Espacio: O(N) — N entradas almacenadas.
  • Determinismo: Latencia fija (crítico para tiempo real / RTOS duro).

Formas de Implementación

FormaEstructuraCaso de Uso
Arreglo 1D / Vectorsalida = tabla[entrada]Mapeo directo: Sen(x), Corrección Gamma, Linearización de Termopar, CRC8.
Arreglo 2D / Multi-Dsalida = tabla[x][y]Interpolación bilineal, Máquinas de estado, Tablas de verdad (puertas lógicas).
Mapa Hash / Diccionariosalida = dict[clave]Claves dispersas, Claves no enteras (cadenas, enums), Tablas dinámicas.
Memoria de Bloque FPGA/ASICBloques de memoria de hardwareDSP: Seno/Coseno, CORDIC, Coeficientes FIR, Conversión de espacio de color (RGB→YUV). Latencia cero.
Memoria de Textura (GPU)Texturas en caché 1D/2D/3DGráficos: Filtrado, Mipmaps. Cómputo: LUTs interpolados.

Aplicaciones Clásicas

  • Trascendentes: sen, cos, log, exp, sqrt — donde falta instrucción de HW o es lenta (MCU de 8 bits, núcleo suave FPGA).
  • Linearización: Termopar (Tipo K, J, T), RTD (Callendar-Van Dusen), Sensor de presión polinomial.
  • Color / Gamma: sRGB ↔ Lineal, CMYK ↔ RGB, LUTs 3D (Calificación de Color, cubos 17×17×17).
  • Comunicaciones Digitales: Mapeo de modulación (Constelación QAM), Métricas de rama del decodizador Viterbi, CRC (tabla impulsada).
  • Sistemas de Control: Programación de ganancia (válvula no lineal → linealizada), Perfiles de leva.
  • Criptografía: S-Boxes (AES SubBytes), Constantes de Montgomery precomputadas.
  • Desarrollo de Videojuegos: Lightmaps, Shadow maps, GI pre-horneado, Curvas de animación.

Consideraciones de Diseño

  • Resolución vs Tamaño: Entrada de 8 bits = 256 entradas. Entrada de 16 bits = 65,536 entradas. Interpolación (lineal/cúbica) reduce las entradas necesarias.
  • Costo de Inicialización: Calcular una vez al inicio / tiempo de compilación (constexpr). Incrustar en binario.
  • Localidad de Caché: Las LUT pequeñas caben en L1. Las LUT grandes → fallos de caché → más lentas que el cálculo.
  • Precisión: Error de cuantización (redondeo del índice de entrada) + Precisión de salida. La interpolación reduce el error.
  • Volatilidad: Estática (ROM/Flash) vs Dinámica (RAM, actualizada en tiempo real — p. ej., ecualizador adaptativo).

Ejemplo de Interpolación (1D Lineal)

 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; } 

Cuándo NO Usar una LUT

  • La función es simple y rápida (p. ej., y = 2*x + 1). El cálculo gana.
  • El rango de entrada es enorme / precisión continua alta (p. ej., float de 32 bits → 4B entradas imposible).
  • Memoria severamente restringida (MCU diminuto, 2 KB RAM) y la función es computable en < 10 ciclos.
  • Los datos cambian cada ciclo (sin reutilización).

Conclusión: Las LUT son una **técnica de optimización fundamental** — "Espacio por Tiempo". Ubicuas en embebido, DSP, gráficos, criptografía y computación científica. Perfile primero: mida ciclos de cálculo vs ancho de banda/latencia de memoria.