Gráfico de Tanner

En teoría de codificación , un gráfico de Tanner , llamado así por 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 estos gráficos ampliamente.

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 otros más pequeños utilizando técnicas recursivas. Generalizó las técnicas de Elias para los códigos de productos.

Tanner analizó los límites inferiores de los códigos obtenidos a partir 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. En el caso de los códigos de bloque lineales, los nodos de subcódigo denotan filas de la matriz de comprobación de paridad H. Los nodos de dígitos representan las columnas de la matriz H. Una arista conecta un nodo de subcódigo con un nodo de dígitos si existe una entrada distinta de cero en la intersección de la fila y la columna correspondientes.

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 ${\estilo de visualización R}$${\estilo de visualización m}$${\estilo de visualización n}$

${\displaystyle R\geq 1-(1-r)m\,}$

La ventaja de estas técnicas recursivas es que son computacionalmente manejables. El algoritmo de codificación para los grafos de Tanner es extremadamente eficiente en la práctica, aunque no se garantiza su convergencia, excepto en el caso de grafos 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.

• Artículo original de Michael Tanner
• La página de Michael Tanner