Conde de Tanner

El gráfico de Tanner es un gráfico bipartito que se utiliza para restringir estados o igualdades que definen códigos de corrección de errores . En la teoría de la codificación, los gráficos de Tanner se han utilizado para construir códigos más largos a partir de códigos más pequeños. Tanto los codificadores como los decodificadores hacen un uso intensivo de estos gráficos.

El nombre de Michael Tanner.

Orígenes

Los gráficos de Tanner fueron propuestos por Michael Tanner [1] para generar códigos de corrección de errores más largos a partir de códigos más pequeños utilizando técnicas recursivas. Resumió las técnicas de Peter Elias para derivar códigos.

Tanner discutió los límites inferiores de los códigos derivados de estos gráficos, independientemente de las características específicas de los códigos que se usaron para construir códigos más grandes.

Gráficos de Tanner para códigos de bloque de líneas

Los gráficos de Tanner se dividen en nodos de subcódigo y nodos de signo. Para los códigos de bloque lineal, los nodos de subcódigo definen las filas de la matriz de verificación de paridad H. Los nodos de signo representan las columnas de la matriz H. Un borde conecta el nodo de subcódigo con el nodo de signo si hay un elemento distinto de cero en el matriz en la intersección de la fila y la columna.

Límites probados por Tanner

Tanner demostró los siguientes límites.

Sea la velocidad código lineal resultante, sea el grado de los nodos de signo y sea el grado de los nodos de subcódigo . Si cada nodo de subcódigo está asociado con un código de línea (n,k) con tasa r = k/n, entonces la tasa de código está limitada por

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

La ventaja de estas técnicas recursivas es que son computacionalmente amigables. El algoritmo de codificación para los gráficos de Tanner es extremadamente eficiente en la práctica, aunque no garantiza la convergencia, excepto para los gráficos sin ciclos, que se sabe que no dan buenos códigos asintóticamente [2] .

Aplicaciones del Conde Tanner

El algoritmo de decodificación de Zemor , que es un enfoque recursivo de baja complejidad para construir códigos, se basa en gráficos de Tanner.

Una matriz dispersa para código con una baja densidad de comprobaciones de paridad se puede representar como un gráfico de Tanner, lo que permite que dichos gráficos se utilicen como una estructura de datos de soporte en el algoritmo de matriz de comprobación de paridad conocido como Progressive Edge Growth [3] .

Notas

  1. ↑ R. Michael Tanner Profesor de Ciencias de la Computación, Escuela de Ingeniería Universidad de California, Santa Cruz Testimonio ante Representantes de la Oficina de Derechos de Autor de los Estados Unidos 10 de febrero de 1999 . Consultado el 8 de marzo de 2019. Archivado desde el original el 8 de mayo de 2017.
  2. ↑ Etzion, Trachtenberg, Vardy, 1998 .
  3. ↑ Xiao-Yu Hu, E. Eleftheriou, DM Arnold. Gráficos de tanner de crecimiento de borde progresivo regular e irregular  // IEEE Transactions on Information Theory. — 2005-1. - T. 51 , n. 1 . — S. 386–398 . — ISSN 0018-9448 . -doi : 10.1109/ TIT.2004.839541 . Archivado desde el original el 27 de febrero de 2021.

Literatura