En teoría de codificación , un gráfico de Tanner , que lleva el nombre de Michael Tanner, es un gráfico bipartito que se utiliza para establecer restricciones o ecuaciones que especifican códigos de corrección de errores . En teoría de codificación , los gráficos de Tanner se utilizan para construir códigos más largos a partir de otros más pequeños. Tanto los codificadores como los decodificadores emplean ampliamente estos gráficos.
Los gráficos de Tanner fueron propuestos por Michael Tanner [1] como un medio para crear códigos de corrección de errores más grandes a partir de códigos más pequeños utilizando técnicas recursivas. Generalizó las técnicas de Elías para códigos de productos.
Tanner analizó los límites inferiores de los códigos obtenidos de estos gráficos, independientemente de las características específicas de los códigos que se utilizaban para construir códigos más grandes.
Los gráficos de Tanner se dividen en nodos de subcódigo y nodos de dígitos. Para códigos de bloque lineales, los nodos de subcódigo denotan filas de la matriz de verificación de paridad H. Los nodos de dígitos representan las columnas de la matriz H. Un borde conecta un nodo de subcódigo a un nodo de dígitos si existe una entrada distinta de cero en la intersección de los correspondientes. fila y columna.
Tanner demostró los siguientes límites
Sea la tasa del código lineal resultante, sea el grado de los nodos de dígitos y el grado de los nodos de subcódigo . Si cada nodo de subcódigo está asociado con un código lineal (n,k) con tasa r = k/n, entonces la tasa del código está limitada por
La ventaja de estas técnicas recursivas es que son manejables computacionalmente. El algoritmo de codificación para gráficos de Tanner es extremadamente eficiente en la práctica, aunque no se garantiza que converja excepto en el caso de gráficos sin ciclos, que se sabe que no admiten códigos asintóticamente buenos. [2]
El algoritmo de decodificación de Zemor , que es un enfoque recursivo de baja complejidad para la construcción de código, se basa en gráficos de Tanner.
