Gráfico de Tanner - Tanner graph

En la teoría de la 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 la teoría de la codificación , los gráficos de Tanner se utilizan para construir códigos más largos a partir de códigos más pequeños. Tanto los codificadores como los decodificadores emplean estos gráficos ampliamente.

Orígenes

Los gráficos de Tanner fueron propuestos por Michael Tanner 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 Elias para códigos de producto.

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 estaban utilizando para construir códigos más grandes.

Gráficos de Tanner para códigos de bloques lineales

Los gráficos de Tanner se dividen en nodos de subcódigo y nodos de dígitos. Para los 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 la correspondiente fila y columna.

Límites probados por Tanner

Tanner demostró los siguientes límites

Sea la tasa del código lineal resultante, sea el grado de los nodos de dígitos y sea 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 ${\ Displaystyle R}$${\ Displaystyle m}$${\ Displaystyle n}$

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

Complejidad computacional de los métodos basados ​​en gráficos de Tanner

La ventaja de estas técnicas recursivas es que son manejables computacionalmente. El algoritmo de codificación para los gráficos de Tanner es extremadamente eficiente en la práctica, aunque no se garantiza que converja, excepto para los gráficos sin ciclo, que se sabe que no admiten códigos asintóticamente buenos.

Aplicaciones del gráfico de Tanner

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.

Notas

• Documento original de Michael Tanner
• Página de Michael Tanner