Algoritmo de decodificación de Zemor

En la teoría de la codificación , el algoritmo de Zemor , diseñado y desarrollado por Gilles Zemor, ^[1] es un enfoque recursivo de baja complejidad para la construcción de código. Es una mejora sobre el algoritmo de Sipser y Spielman .

Zemor consideró una clase típica de construcción Sipser-Spielman de códigos de expansión , donde el gráfico subyacente es un gráfico bipartito . Sipser y Spielman introdujeron una familia constructiva de códigos de error lineal asintóticamente buenos junto con un algoritmo paralelo simple que siempre eliminará una fracción constante de errores. El artículo está basado en las notas del curso del Dr. Venkatesan Guruswami ^[2]

El algoritmo de Zemor se basa en un tipo de gráficos de expansión llamado gráfico de Tanner . La construcción del código fue propuesta por primera vez por Tanner. ^[3] Los códigos se basan en doble cubierta , expansor regular , que es un gráfico bipartito. = , donde es el conjunto de vértices y es el conjunto de aristas y = y = , donde y denota conjuntos de vértices. Sea el número de vértices en cada grupo, es decir , . El conjunto de aristas debe ser de tamaño = y cada arista en tiene un punto final en ambos y .${\ estilo de visualización d}$${\ estilo de visualización G}$${\ estilo de visualización G}$${\ estilo de visualización \ izquierda (V, E \ derecha)}$${\ estilo de visualización V}$${\ estilo de visualización E}$${\ estilo de visualización V}$${\ estilo de visualización A}$ ${\ estilo de visualización \ taza}$ ${\ estilo de visualización B}$${\ estilo de visualización A}$ ${\ estilo de visualización \ gorra}$ ${\ estilo de visualización B}$${\ estilo de visualización \ conjunto vacío}$${\ estilo de visualización A}$${\ estilo de visualización B}$${\ estilo de visualización n}$${\ estilo de visualización | A | = | B | = n}$${\ estilo de visualización E}$${\ estilo de visualización N}$${\ Displaystyle fin}$${\ estilo de visualización E}$${\ estilo de visualización A}$${\ estilo de visualización B}$${\ estilo de visualización E (v)}$denota el conjunto de aristas que contiene .${\ estilo de visualización v}$

Grafica G y codifica C