celosía

En la teoría de la comunicación y el procesamiento de señales, un "trellis" es una estructura gráfica que mapea la evolución de un sistema de estados finitos a lo largo de pasos de tiempo discretos. Cada "rebanada" vertical representa un momento en el tiempo, con nodos que representan los posibles estados del sistema. Los bordes conectan estados en pasos de tiempo consecutivos, mostrando qué transiciones de estado están permitidas por el esquema de codificación o modulación. Esta estructura se vuelve esencial cuando se necesita encontrar la secuencia de estados más probable que produjo una señal recibida corrompida por ruido.

El "trellis" debe su poder al algoritmo de Viterbi, que explota la estructura del gráfico para decodificar los datos recibidos de manera eficiente. En lugar de verificar cada posible ruta a través de todos los pasos de tiempo, el algoritmo de Viterbi mantiene solo la ruta más probable que conduce a cada estado en cada momento, y luego poda las ramas imposibles. Para un código convolucional con una longitud de restricción de 7 y símbolos binarios, el "trellis" típicamente tiene 26 = 64 estados por "rebanada" de tiempo, lo que hace que la búsqueda sea manejable incluso para mensajes largos.

Los diagramas de "trellis" aparecen dondequiera que se utilice la codificación basada en restricciones: códigos convolucionales en comunicaciones satelitales y móviles, turbo códigos, códigos LDPC e incluso en la ecualización de canales dispersivos. La estructura del "trellis" codifica directamente los polinomios generadores o las relaciones de verificación de paridad del código. Un codificador convolucional de tasa 1/2 con dos tomas de retroalimentación producirá una topología de "trellis" diferente a la de un código de tasa 1/3, y esa diferencia es visible en el número de bordes por nodo y el patrón de conexiones.

El nombre "trellis" proviene de su parecido con un enrejado de jardín o una estructura de soporte para vides: columnas verticales (pasos de tiempo) con conexiones diagonales (transiciones de estado). Esta metáfora visual se mantuvo porque el diagrama realmente ayuda a los ingenieros a ver cómo los estados proliferan y reconvergen con el tiempo. En las variantes de "trellis" de "tail-biting" y circulares, el paso de tiempo final se conecta de nuevo a los estados iniciales, lo que permite códigos sin bits de relleno desperdiciados.

Un "trellis" no es exclusivo de ninguna modulación o código; es una herramienta de representación que se adapta a las restricciones del sistema. La misma estructura de "trellis" puede ser recorrida por diferentes algoritmos: Viterbi para la decodificación de máxima verosimilitud, el algoritmo "forward-backward" para la decodificación de salida suave, o los métodos de propagación de creencias para gráficos de factores. Comprender la estructura del "trellis" es esencial para los diseñadores de hardware que implementan decodificadores, porque la ruta crítica y los requisitos de memoria dependen directamente de la topología de las ramas y los estados.