Algoritmo de decodificación de Zemor

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

Zemor consideró una clase típica de códigos expansores construidos por Sipser-Spielman , donde el grafo subyacente es un grafo 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 se basa en las notas del curso del Dr. Venkatesan Guruswami ^{[ 2 ].}

Construcción de códigos

El algoritmo de Zemor se basa en un tipo de grafos expansores llamado grafo de Tanner . La construcción del código fue propuesta por primera vez por Tanner. ^{[ 3 ]} Los códigos se basan en la doble cobertura. $d$ , expansor regular $G$ , que es un grafo bipartito. $G$ = $\left(V,E\right)$ , dónde $V$ es el conjunto de vértices y $E$ es el conjunto de aristas y $V$ = $A$ $\cup$ $B$ y $A$ $\cap$ $B$ = $\emptyset$ , dónde $A$ y $B$ denota conjuntos de vértices. Sea $n$ sea el número de vértices en cada grupo, es decir , $|A|=|B|=n$ . El conjunto de bordes $E$ ser de tamaño $N$ = $nd$ y cada borde en $E$ tiene un punto final en ambos $A$ y $B$ . $E(v)$ denota el conjunto de aristas que contienen $v$ .

Supongamos un orden en $V$ , por lo tanto, el ordenamiento se realizará en cada borde de $E(v)$ por cada $v\in V$ . Sea un campo finito $\mathbb {F} =GF(2)$ y por una palabra $x=(x_{e}),e\en E$ en $\mathbb {F} ^{N}$ , sea la subpalabra de la palabra que será indexada por $E(v)$ . Sea esa palabra denotada por $(x)_{v}$ . El subconjunto de vértices $A$ y $B$ induce cada palabra $x\in \mathbb {F} ^{N}$ una partición en $n$ subpalabras que no se superponen $\left(x\right)_{v}\in \mathbb {F} ^{d}$ , dónde $v$ abarca los elementos de $A$ Para construir un código $C$ , considere un subcódigo lineal $C_{o}$ , que es un $[d,r_{o}d,\delta ]$ código, donde $q$ , el tamaño del alfabeto es $2$ . Para cualquier vértice $v\in V$ , dejar $v(1),v(2),\ldots,v(d)$ ser algún orden de la $d$ vértices de $E$ adyacente a $v$ . En este código, cada bit $x_{e}$ está vinculado con un borde $e$ de $E$ .

Podemos definir el código $C$ ser el conjunto de vectores binarios $x=\left(x_{1},x_{2},\ldots ,x_{N}\right)$ de $\{0,1\}^{N}$ de tal manera que, para cada vértice $v$ de $V$ , $\left(x_{v(1)},x_{v(2)},\ldots ,x_{v(d)}\right)$ es una palabra clave de $C_{o}$ . En este caso, podemos considerar un caso especial cuando cada arista de $E$ está adyacente a exactamente $2$ vértices de $V$ . Significa que $V$ y $E$ conforman, respectivamente, el conjunto de vértices y el conjunto de aristas de $d$ gráfico regular $G$ .

Llamemos al código $C$ construido de esta manera como $\left(G,C_{o}\right)$ código. Para un gráfico dado $G$ y un código dado $C_{o}$ , hay varios $\left(G,C_{o}\right)$ códigos ya que hay diferentes maneras de ordenar las aristas incidentes a un vértice dado $v$ , es decir, $v(1),v(2),\ldots,v(d)$ De hecho, nuestro código $C$ constan de todas las palabras clave tales que $x_{v}\in C_{o}$ a pesar de $v\in A,B$ El código $C$ es lineal $[N,K,D]$ en $\mathbb {F}$ ya que se genera a partir de un subcódigo $C_{o}$ , que es lineal. El código $C$ se define como $C=\{c\in \mathbb {F} ^{N}:(c)_{v}\in C_{o}\}$ por cada $v\in V$ .

En esta figura, $(x)_{v}=\left(x_{e1},x_{e2},x_{e3},x_{e4}\right)\in C_{o}$ Muestra el gráfico $G$ y código $C$ .

En matriz $G$ , dejar $\lambda$ es igual al segundo mayor valor propio de la matriz de adyacencia de $G$ Aquí el mayor valor propio es $d$ Se hacen dos afirmaciones importantes:

Reivindicación 1

$\left({\dfrac {K}{N}}\right)\geq 2r_{o}-1$ . Dejar $R$ sea la tasa de un código lineal construido a partir de un grafo bipartito cuyos nodos de dígitos tienen grado $m$ y cuyos nodos de subcódigo tienen grado $n$ . Si un único código lineal con parámetros $\left(n,k\right)$ y tasa $r=\left({\dfrac {k}{n}}\right)$ está asociado con cada uno de los nodos de subcódigo, entonces $k\geq 1-\left(1-r\right)m$ .

Prueba

Dejar $R$ sea la tasa del código lineal , que es igual a $K/N$ Que haya $S$ nodos de subcódigo en el grafo. Si el grado del subcódigo es $n$ , entonces el código debe tener $\left({\dfrac {n}{m}}\right)S$ dígitos, ya que cada nodo de dígito está conectado a $m$ del $\left(n\right)S$ aristas en el grafo. Cada nodo de subcódigo contribuye $(nk)$ ecuaciones para la matriz de verificación de paridad para un total de $\left(nk\right)S$ Estas ecuaciones pueden no ser linealmente independientes. Por lo tanto, $\left({\dfrac {K}{N}}\right)\geq \left({\dfrac {({\dfrac {n}{m}})S-(nk)S}{({\dfrac {n}{m}})S}}\right)$ $\geq 1-m\left({\dfrac {nk}{n}}\right)$ $\geq 1-m\left(1-r\right)$ , Dado que el valor de $m$ , es decir, el nodo de dígitos de este grafo bipartito es $2$ y aquí $r=r_{o}$ , podemos escribirlo como: $\left({\dfrac {K}{N}}\right)\geq 2r_{o}-1$

Reivindicación 2

D\geq N\left({\dfrac {(\delta -({\dfrac {\lambda }{d}}))}{(1-({\dfrac {\lambda }{d}})}})\right)^{2}

=N\left(\delta ^{2}-O\left({\dfrac {\lambda }{d}}\right)\right)

\rightarrow (1)

Si $S$ es un código lineal de tasa $r$ longitud del código del bloque $d$ y distancia relativa mínima $\delta$ y si $B$ es el grafo de incidencia de vértices de aristas de un $d$ – gráfico regular con el segundo valor propio más grande $\lambda$ , luego el código $C(B,S)$ tiene tasa al menos $2r_{o}-1$ y distancia relativa mínima al menos $\left(\left({\dfrac {\delta -\left({\dfrac {\lambda }{d}}\right)}{1-\left({\dfrac {\lambda }{d}}\right)}}\right)\right)^{2}$ .

Prueba

Dejar $B$ ser derivado de la $d$ gráfico regular $G$ . Entonces, el número de variables de $C(B,S)$ es $\left({\dfrac {dn}{2}}\right)$ y el número de restricciones es $n$ . Según Alon-Chung, ^{[ 4 ]} si $X$ es un subconjunto de vértices de $G$ de tamaño $\gamma n$ , entonces el número de aristas contenidas en el subgrafo es inducido por $X$ en $G$ es como máximo $\left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)$ .

Como resultado, cualquier conjunto de $\left({\dfrac {dn}{2}}\right)\left(\gamma ^{2}+\left({\dfrac {\lambda }{d}}\right)\gamma \left(1-\gamma \right)\right)$ Las variables tendrán al menos $\gamma n$ restricciones como vecinas. Por lo tanto, el número promedio de variables por restricción es : $\left({\dfrac {({\dfrac {2nd}{2}})\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)}{\gamma n}}\right)$ $=d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)$ $\rightarrow (2)$

Entonces si $d\left(\gamma +({\dfrac {\lambda }{d}})\left(1-\gamma \right)\right)<\gamma d$ , luego una palabra de peso relativo $\left(\gamma ^{2}+({\dfrac {\lambda }{d}})\gamma \left(1-\gamma \right)\right)$ , no puede ser una palabra clave de $C(B,S)$ La desigualdad $(2)$ está satisfecho por $\gamma <\left({\dfrac {1-({\dfrac {\lambda }{d}})}{\delta -({\dfrac {\lambda }{d}})}}\right)$ . Por lo tanto, $C(B,S)$ no puede tener una palabra clave distinta de cero de peso relativo $\left({\dfrac {\delta -({\dfrac {\lambda }{d}})}{1-({\dfrac {\lambda }{d}})}}\right)^{2}$ o menos.

En matriz $G$ , podemos suponer que $\lambda /d$ está delimitado lejos de $1$ . Para esos valores de $d$ en el cual $d-1$ es primo impar, existen construcciones explícitas de secuencias de $d$ - grafos bipartitos regulares con un número arbitrariamente grande de vértices tales que cada grafo $G$ En la secuencia hay un grafo de Ramanujan . Se llama grafo de Ramanujan porque satisface la desigualdad. $\lambda (G)\leq 2{\sqrt {d-1}}$ En el gráfico se aprecian ciertas propiedades de expansión. $G$ como la separación entre los valores propios $d$ y $\lambda$ . Si el gráfico $G$ es el gráfico de Ramanujan, entonces esa expresión $(1)$ se convertirá $0$ eventualmente como $d$ se vuelve grande.

El algoritmo de Zemor

El algoritmo de decodificación iterativo que se muestra a continuación alterna entre los vértices. $A$ y $B$ en $G$ y corrige la palabra clave de $C_{o}$ en $A$ y luego cambia para corregir la palabra clave $C_{o}$ en $B$ . Aquí, las aristas asociadas con un vértice en un lado de un grafo no son incidentes a otros vértices en ese lado. De hecho, no importa en qué orden, el conjunto de nodos $A$ y $B$ se procesan. El procesamiento de vértices también se puede realizar en paralelo.

El decodificador $\mathbb {D$ representa un decodificador para $C_{o}$ que se recupera correctamente con cualquier palabra clave con menos de $\left({\dfrac {d}{2}}\right)$ errores.

Algoritmo decodificador

Mensaje recibido : $w=(w_{e}),e\in E$ $z\leftarrow w$ For $t\leftarrow 1$ to $m$ do // $m$ is the number of iterations { if ( $t$ is odd) // Here the algorithm will alternate between its two vertex sets. $X\leftarrow A$ else $X\leftarrow B$ Iteration $t$ : For every $v\in X$ , let $(z)_{v}\leftarrow \mathbb {D} ((z)_{v})$ // Decoding $z_{v}$ to its nearest codeword. } Producción: $z$

Explicación del algoritmo

Desde $G$ es bipartito, el conjunto $A$ de vértices induce la partición del conjunto de aristas $E$ = $\cup _{v\in A}E_{v}$ . El conjunto $B$ induce otra partición, $E$ = $\cup _{v\in B}E_{v}$ .

Dejar $w\in \{0,1\}^{N}$ sea el vector recibido, y recordemos que $N=dn$ . La primera iteración del algoritmo consiste en aplicar la decodificación completa para el código inducido por $E_{v}$ por cada $v\in A$ . Esto significa que para reemplazar, por cada $v\in A$ , el vector $\left(w_{v(1)},w_{v(2)},\ldots ,w_{v(d)}\right)$ por una de las palabras clave más cercanas de $C_{o}$ . Dado que los subconjuntos de aristas $E_{v}$ son disjuntos para $v\in A$ , la decodificación de estos $n$ subvectores de $w$ puede hacerse en paralelo.

La iteración producirá un nuevo vector. $z$ . La siguiente iteración consiste en aplicar el procedimiento anterior a $z$ pero con $A$ reemplazado por $B$ . En otras palabras, consiste en decodificar todos los subvectores inducidos por los vértices de $B$ . Las siguientes iteraciones repiten esos dos pasos alternativamente aplicando decodificación paralela a los subvectores inducidos por los vértices de $A$ y a los subvectores inducidos por los vértices de $B$ . Nota: [Si $d=n$ y $G$ es el grafo bipartito completo , entonces $C$ es un código de producto de $C_{o}$ [Con ello, y el algoritmo anterior se reduce a la decodificación iterativa natural y compleja de los códigos de producto].

Aquí, el número de iteraciones, $m$ es $\left({\dfrac {(\log {n})}{\log(2-\alpha )}}\right)$ En general, el algoritmo anterior puede corregir una palabra clave cuyo peso de Hamming no sea mayor que $({\dfrac {1}{2}}).\alpha N\delta \left(({\dfrac {\delta }{2}})-({\dfrac {\lambda }{d}})\right)=\left(({\dfrac {1}{4}}).\alpha N(\delta ^{2}-O({\dfrac {\lambda }{d}})\right)$ para valores de $\alpha <1$ Aquí, el algoritmo de decodificación se implementa como un circuito de tamaño $O(N\log {N})$ y profundidad $O(\log {N})$ que devuelve la palabra clave dado que el vector de error tiene un peso menor que $\alpha N\delta ^{2}(1-\epsilon )/4$ .

Teorema

Si $G$ es un grafo de Ramanujan de grado suficientemente alto, para cualquier $\alpha <1$ El algoritmo de decodificación puede corregir $({\dfrac {\alpha \delta _{o}^{2}}{4}})(1-\varepsilon )N$ errores, donde $\varepsilon$ tiende a 0 cuando $\lambda /d$ tiende a 0, en $O(\log {n})$ rondas (donde el grande- $O$ La notación oculta una dependencia de $\alpha$ ). Esto se puede implementar en tiempo lineal en un solo procesador; en $n$ Los procesadores de cada ronda pueden implementarse en tiempo constante.

Prueba

Dado que el algoritmo de decodificación es insensible al valor de los bordes y por linealidad, podemos asumir que la palabra clave transmitida es un vector de ceros. Sea la palabra clave recibida $w$ . Se considera el conjunto de aristas que tiene un valor incorrecto durante la decodificación. Aquí por valor incorrecto, nos referimos a $1$ en cualquiera de los bits. Deja $w=w^{0}$ sea el valor inicial de la palabra clave, $w^{1},w^{2},\ldots ,w^{t}$ sean los valores después del primero, segundo . . . $t$ etapas de decodificación. Aquí, $X^{i}={e\in E|x_{e}^{i}=1}$ , y $S^{i}={v\in V^{i}|E_{v}\cap X^{i+1}!=\emptyset }$ . Aquí $S^{i}$ corresponde a aquellos conjuntos de vértices que no pudieron decodificar con éxito su palabra clave en el $i^{th}$ ronda. Del algoritmo anterior $S^{1}<S^{0}$ como número de vértices fallidos se corregirán en cada iteración. Podemos demostrar que $S^{0}>S^{1}>S^{2}>\cdots$ es una secuencia decreciente. De hecho, $|S_{i+1}|<=({\dfrac {1}{2-\alpha }})|S_{i}|$ . Como suponemos, $\alpha <1$ , la ecuación anterior está en una secuencia geométrica decreciente . Entonces, cuando $|S_{i}|<n$ , más que $log_{2-\alpha }n$ Son necesarias rondas. Además, $\sum |S_{i}|=n\sum ({\dfrac {1}{(2-\alpha )^{i}}})=O(n)$ y si implementamos el $i^{th}$ ronda en $O(|S_{i}|)$ tiempo, entonces el tiempo total de ejecución secuencial será lineal.

Desventajas del algoritmo de Zemor

Es un proceso largo debido al número de iteraciones. $m$ en el algoritmo del decodificador toma es $[(\log {n})/(\log(2-\alpha ))]$
El algoritmo de decodificación de Zemor tiene dificultades para decodificar borraduras. Una forma detallada de cómo podemos mejorar el algoritmo es:

dado en. ^{[ 5 ]}

Véase también

Referencias

↑ "Gilles Zémor" . www.math.u-bordeaux.fr . Consultado el 9 de abril de 2023 .
↑ Guruswami, Venkatesan; Cary, Matt (27 de enero de 2003). "Clase 5" . CSE590G: Códigos y objetos pseudoaleatorios . Universidad de Washington. Archivado del original el 24 de febrero de 2014.
↑ "Apuntes de clase" (PDF) . washington.edu . Consultado el 9 de abril de 2023 .
↑ N. Alon ; FRK Chung (diciembre de 1988). "Construcción explícita de redes tolerantes de tamaño lineal". Matemáticas Discretas . 72 ( 1–3 ): 15–19 . CiteSeerX 10.1.1.300.7495 . doi : 10.1016/0012-365X(88)90189-6 .
↑ "Copia archivada" . Archivado del original el 14 de septiembre de 2004. Recuperado el 1 de mayo de 2012 .{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )

[vg1-1] "Gilles Zémor" . www.math.u-bordeaux.fr . Consultado el 9 de abril de 2023 .

[vg2-2] Guruswami, Venkatesan; Cary, Matt (27 de enero de 2003). "Clase 5" . CSE590G: Códigos y objetos pseudoaleatorios . Universidad de Washington. Archivado del original el 24 de febrero de 2014.

[vg3-3] "Apuntes de clase" (PDF) . washington.edu . Consultado el 9 de abril de 2023 .

[vg4-4] N. Alon ; FRK Chung (diciembre de 1988). "Construcción explícita de redes tolerantes de tamaño lineal". Matemáticas Discretas . 72 ( 1–3 ): 15–19 . CiteSeerX 10.1.1.300.7495 . doi : 10.1016/0012-365X(88)90189-6 .

[vg5-5] "Copia archivada" . Archivado del original el 14 de septiembre de 2004. Recuperado el 1 de mayo de 2012 .{{cite web}}: CS1 mantenimiento: copia archivada como título ( enlace )

[ 1 ]

[ 2 ].

[ 3 ]

[ 4 ]

[ 5 ]