Código de expansión

En teoría de codificación , los códigos expansores forman una clase de códigos de corrección de errores que se construyen a partir de grafos expansores bipartitos . Junto con los códigos de Justesen , los códigos expansores son de particular interés ya que tienen una tasa positiva constante, una distancia relativa positiva constante y un tamaño de alfabeto constante . De hecho, el alfabeto contiene solo dos elementos, por lo que los códigos expansores pertenecen a la clase de códigos binarios . Además, los códigos expansores pueden codificarse y decodificarse en un tiempo proporcional a la longitud del bloque del código.

Códigos de expansión

En teoría de codificación , un código expansor es un código de bloque lineal cuya matriz de comprobación de paridad es la matriz de adyacencia de un gráfico expansor bipartito . Estos códigos tienen una buena distancia relativa , donde y son propiedades del gráfico expansor como se define más adelante, velocidad y decodificabilidad ( existen algoritmos de tiempo de ejecución). ${\displaystyle [n,n-m]_{2}\,}$ ${\displaystyle 2(1-\varepsilon )\gamma \,}$ ${\displaystyle \varepsilon \,}$ ${\displaystyle \gamma \,}$ ${\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}$ ${\displaystyle O(n)\,}$

Definición

Sea un grafo birregular entre un conjunto de nodos , llamados variables , y un conjunto de nodos , llamados restricciones . ${\displaystyle B}$ ${\displaystyle (c,d)}$ ${\displaystyle n}$ ${\displaystyle \{v_{1},\cdots ,v_{n}\}}$ ${\displaystyle cn/d}$ ${\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}$

Sea una función diseñada de modo que, para cada restricción , las variables vecinas sean . ${\displaystyle b(i,j)}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}$

Sea un código corrector de errores de longitud de bloque . El código expansor es el código de longitud de bloque cuyas palabras de código son las palabras tales que, para , es una palabra de código de . ^[1] ${\displaystyle {\mathcal {S}}}$ ${\displaystyle d}$ ${\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}$ ${\displaystyle n}$ ${\displaystyle (x_{1},\cdots ,x_{n})}$ ${\displaystyle 1\leq i\leq cn/d}$ ${\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}$ ${\displaystyle {\mathcal {S}}}$

Se ha demostrado que existen grafos expansores sin pérdidas no triviales. Además, podemos construirlos explícitamente. ^[2]

Tasa

La tasa de es su dimensión dividida por la longitud de su bloque. En este caso, la matriz de comprobación de paridad tiene un tamaño de , y por lo tanto tiene una tasa de al menos . ${\displaystyle C\,}$ ${\displaystyle m\times n\,}$ ${\displaystyle C\,}$ ${\displaystyle (n-m)/n=1-m/n\,}$

Distancia

Supongamos que . Entonces la distancia de un código expansor es al menos . ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$ ${\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}$ ${\displaystyle C\,}$ ${\displaystyle 2(1-\varepsilon )\gamma n\,}$

Prueba

Nótese que podemos considerar cada palabra de código en como un subconjunto de vértices , diciendo que vértice si y solo si el índice n de la palabra de código es 1. Entonces es una palabra de código si y solo si cada vértice es adyacente a un número par de vértices en . (Para ser una palabra de código, , donde es la matriz de verificación de paridad. Entonces, cada vértice en corresponde a cada columna de . La multiplicación de matrices sobre entonces da el resultado deseado). Entonces, si un vértice es adyacente a un solo vértice en , sabemos inmediatamente que no es una palabra de código. Sea n los vecinos en de , y n aquellos vecinos de que son únicos, es decir, adyacentes a un solo vértice de . ${\displaystyle c\,}$ ${\displaystyle C\,}$ ${\displaystyle S\subset L\,}$ ${\displaystyle v_{i}\in S\,}$ ${\displaystyle i\,}$ ${\displaystyle c\,}$ ${\displaystyle v\in R\,}$ ${\displaystyle S\,}$ ${\displaystyle cP=0\,}$ ${\displaystyle P\,}$ ${\displaystyle R\,}$ ${\displaystyle P\,}$ ${\displaystyle {\text{GF}}(2)=\{0,1\}\,}$ ${\displaystyle v\in R\,}$ ${\displaystyle S\,}$ ${\displaystyle c\,}$ ${\displaystyle N(S)\,}$ ${\displaystyle R\,}$ ${\displaystyle S\,}$ ${\displaystyle U(S)\,}$ ${\displaystyle S\,}$ ${\displaystyle S\,}$

Lema 1

Para cada tamaño , . ${\displaystyle S\subset L\,}$ ${\displaystyle |S|\leq \gamma n\,}$ ${\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}$

Prueba

Trivialmente, , ya que implica . se deduce que el grado de cada vértice en es . Por la propiedad de expansión del grafo, debe haber un conjunto de aristas que vayan a vértices distintos. Las aristas restantes forman, como máximo, vecinos no únicos, por lo que . ${\displaystyle |N(S)|\geq |U(S)|\,}$ ${\displaystyle v\in U(S)\,}$ ${\displaystyle v\in N(S)\,}$ ${\displaystyle |N(S)|\leq d|S|\,}$ ${\displaystyle S\,}$ ${\displaystyle d\,}$ ${\displaystyle d(1-\varepsilon )|S|\,}$ ${\displaystyle d\varepsilon |S|\,}$ ${\displaystyle d\varepsilon |S|\,}$ ${\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}$

Corolario

Cada número suficientemente pequeño tiene un vecino único. Esto se deduce de que . ${\displaystyle S\,}$ ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

Lema 2

Cada subconjunto tiene un vecino único. ${\displaystyle T\subset L\,}$ ${\displaystyle |T|<2(1-\varepsilon )\gamma n\,}$

Prueba

El Lema 1 demuestra el caso , así que supongamos . Sea tal que . Por el Lema 1, sabemos que . Entonces un vértice está en si y solo si , y sabemos que , así que por la primera parte del Lema 1, sabemos . Dado que , , y por lo tanto no está vacío. ${\displaystyle |T|\leq \gamma n\,}$ ${\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}$ ${\displaystyle S\subset T\,}$ ${\displaystyle |S|=\gamma n\,}$ ${\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}$ ${\displaystyle v\in U(S)\,}$ ${\displaystyle U(T)\,}$ ${\displaystyle v\notin N(T\setminus S)\,}$ ${\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}$ ${\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}$ ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$ ${\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}$ ${\displaystyle U(T)\,}$

Corolario

Nótese que si a tiene al menos 1 vecino único, es decir , entonces la palabra correspondiente a no puede ser una palabra de código, ya que no se multiplicará por el vector de todos ceros mediante la matriz de verificación de paridad. Por el argumento anterior, . Como es lineal, concluimos que tiene una distancia de al menos . ${\displaystyle T\subset L\,}$ ${\displaystyle |U(T)|>0\,}$ ${\displaystyle c\,}$ ${\displaystyle T\,}$ ${\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}$ ${\displaystyle C\,}$ ${\displaystyle C\,}$ ${\displaystyle 2(1-\varepsilon )\gamma n\,}$

Codificación

El tiempo de codificación de un código expansor está limitado en su parte superior por el de un código lineal general ( mediante la multiplicación de matrices). Un resultado de Spielman muestra que la codificación es posible en el tiempo. ^[3] ${\displaystyle O(n^{2})\,}$ ${\displaystyle O(n)\,}$

Descodificación

La decodificación de códigos expansores es posible a tiempo utilizando el siguiente algoritmo. ${\displaystyle O(n)\,}$ ${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$

Sea el vértice de que corresponde al índice n en las palabras de código de . Sea una palabra recibida, y . Sea , y sea . Consideremos entonces el algoritmo voraz: ${\displaystyle v_{i}\,}$ ${\displaystyle L\,}$ ${\displaystyle i\,}$ ${\displaystyle C\,}$ ${\displaystyle y\in \{0,1\}^{n}\,}$ ${\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}$ ${\displaystyle e(i)\,}$ ${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}$ ${\displaystyle o(i)\,}$ ${\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}$

---

Entrada: palabra recibida . ${\displaystyle y\,}$

inicializar y' a ymientras haya un v en R adyacente a un número impar de vértices en V(y') si existe una i tal que o(i) > e(i) voltear la entrada i en y' demás fallar

Salida: error o palabra clave modificada . ${\displaystyle y'\,}$

---

Prueba

Mostramos primero la corrección del algoritmo y luego examinamos su tiempo de ejecución.

Exactitud

Debemos demostrar que el algoritmo termina con la palabra clave correcta cuando la palabra clave recibida está dentro de la mitad de la distancia del código con respecto a la palabra clave original. Sea el conjunto de variables corruptas , , y el conjunto de vértices insatisfechos (adyacentes a un número impar de vértices) en sea . El siguiente lema resultará útil. ${\displaystyle S\,}$ ${\displaystyle s=|S|\,}$ ${\displaystyle R\,}$ ${\displaystyle c\,}$

Lema 3

Si , entonces hay un con . ${\displaystyle 0<s<\gamma n\,}$ ${\displaystyle v_{i}\,}$ ${\displaystyle o(i)>e(i)\,}$

Prueba

Por el Lema 1, sabemos que . Por lo tanto, un vértice promedio tiene al menos vecinos únicos (recuerde que los vecinos únicos no se satisfacen y, por lo tanto, contribuyen a ), ya que , y, por lo tanto, hay un vértice con . ${\displaystyle U(S)\geq d(1-2\varepsilon )s\,}$ ${\displaystyle d(1-2\varepsilon )>d/2\,}$ ${\displaystyle o(i)\,}$ ${\displaystyle \varepsilon <{\tfrac {1}{4}}\,}$ ${\displaystyle v_{i}\,}$ ${\displaystyle o(i)>e(i)\,}$

Por lo tanto, si aún no hemos llegado a una palabra clave, siempre habrá algún vértice que voltear. A continuación, demostramos que la cantidad de errores nunca puede aumentar más allá de . ${\displaystyle \gamma n\,}$

Lema 4

Si empezamos con , entonces nunca llegaremos a ningún punto del algoritmo. ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ ${\displaystyle s=\gamma n\,}$

Prueba

Cuando cambiamos un vértice , y se intercambian, y como teníamos , esto significa que el número de vértices insatisfechos a la derecha disminuye en al menos uno después de cada cambio. Como , el número inicial de vértices insatisfechos es como máximo , por la -regularidad del grafo . Si llegamos a una cadena con errores, entonces por el Lema 1, habría al menos vecinos únicos, lo que significa que habría al menos vértices insatisfechos, una contradicción. ${\displaystyle v_{i}\,}$ ${\displaystyle o(i)\,}$ ${\displaystyle e(i)\,}$ ${\displaystyle o(i)>e(i)\,}$ ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ ${\displaystyle d\,}$ ${\displaystyle \gamma n\,}$ ${\displaystyle d\gamma (1-2\varepsilon )n\,}$ ${\displaystyle d\gamma (1-2\varepsilon )n\,}$

Los lemas 3 y 4 nos muestran que si empezamos con (la mitad de la distancia de ), entonces siempre encontraremos un vértice para voltear. Cada volteo reduce el número de vértices no satisfechos en al menos 1, y por lo tanto el algoritmo termina en como máximo pasos, y termina en alguna palabra de código, por el Lema 3. (Si no fuera en una palabra de código, habría algún vértice para voltear). El Lema 4 nos muestra que nunca podemos estar más lejos que lejos de la palabra de código correcta. Dado que el código tiene distancia (ya que ), la palabra de código en la que termina debe ser la palabra de código correcta, ya que el número de volteos de bits es menor que la mitad de la distancia (por lo que no podríamos haber viajado lo suficientemente lejos para alcanzar cualquier otra palabra de código). ${\displaystyle s<\gamma (1-2\varepsilon )n\,}$ ${\displaystyle C\,}$ ${\displaystyle v_{i}\,}$ ${\displaystyle R\,}$ ${\displaystyle m\,}$ ${\displaystyle \gamma n\,}$ ${\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}$ ${\displaystyle \varepsilon <{\tfrac {1}{2}}\,}$

Complejidad

Ahora demostramos que el algoritmo puede lograr una decodificación de tiempo lineal. Sea constante y sea el grado máximo de cualquier vértice en . Nótese que también es constante para las construcciones conocidas. ${\displaystyle {\tfrac {n}{m}}\,}$ ${\displaystyle r\,}$ ${\displaystyle R\,}$ ${\displaystyle r\,}$

1. Preprocesamiento: lleva tiempo calcular si cada vértice tiene un número par o impar de vecinos. ${\displaystyle O(mr)\,}$ ${\displaystyle R\,}$
2. Preprocesamiento 2: Nos tomamos tiempo para calcular una lista de vértices en los que tienen . ${\displaystyle O(dn)=O(dmr)\,}$ ${\displaystyle v_{i}\,}$ ${\displaystyle L\,}$ ${\displaystyle o(i)>e(i)\,}$
3. Cada iteración: simplemente eliminamos el primer elemento de la lista. Para actualizar la lista de vértices pares/impares en , solo necesitamos actualizar las entradas, insertando/eliminando según sea necesario. Luego, actualizamos las entradas en la lista de vértices en con más vecinos impares que pares, insertando/eliminando según sea necesario. Por lo tanto, cada iteración lleva tiempo. ${\displaystyle R\,}$ ${\displaystyle O(d)\,}$ ${\displaystyle O(dr)\,}$ ${\displaystyle L\,}$ ${\displaystyle O(dr)\,}$
4. Como se argumentó anteriormente, el número total de iteraciones es como máximo . ${\displaystyle m\,}$

Esto da un tiempo de ejecución total de tiempo, donde y son constantes. ${\displaystyle O(mdr)=O(n)\,}$ ${\displaystyle d\,}$ ${\displaystyle r\,}$

Véase también

• Gráfico expansor
• Código de comprobación de paridad de baja densidad
• Codificación y decodificación de códigos correctores de errores en tiempo lineal
• Códigos ABNNR y AEL

Notas

Este artículo se basa en las notas del curso del Dr. Venkatesan Guruswami. ^[4]

Referencias

1. Sipser, M.; Spielman, DA (1996). "Códigos expansores". IEEE Transactions on Information Theory . 42 (6): 1710–1722. doi :10.1109/18.556667.
2. Capalbo, M.; Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Conductores aleatorios y expansores sin pérdidas de grado constante". STOC '02 Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación . ACM. págs. 659–668. doi :10.1145/509907.510003. ISBN . 978-1-58113-495-7.S2CID1918841  .​
3. Spielman, D. (1996). "Códigos correctores de errores codificables y decodificables en tiempo lineal". IEEE Transactions on Information Theory . 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736 . doi :10.1109/18.556668. 
4. Guruswami, V. (15 de noviembre de 2006). "Conferencia 13: Códigos expansores" (PDF) . CSE 533: Corrección de errores . Universidad de Washington.
   Guruswami, V. (marzo de 2010). "Notas 8: Códigos expansores y su decodificación" (PDF) . Introducción a la teoría de la codificación . Universidad Carnegie Mellon.
   Guruswami, V. (septiembre de 2004). "Columna invitada: códigos de corrección de errores y gráficos expansores" . ACM SIGACT News . 35 (3): 25–41. doi :10.1145/1027914.1027924. S2CID  17550280.