Gráfico de Tanner
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 [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 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 bloques 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 del 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
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. [2]
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
- ^ R. Michael Tanner Profesor de Ciencias de la Computación, Escuela de Ingeniería de la Universidad de California, Santa Cruz Testimonio ante representantes de la Oficina de Copyright de Estados Unidos 10 de febrero de 1999
- ^ T. Etzion, A. Trachtenberg y A. Vardy , ¿Qué códigos tienen gráficos de Tanner sin ciclo ?, IEEE Trans. Inf. Teoría, 45: 6.
