código expansor

En la teoría de la codificación , los códigos expansores forman una clase de códigos de corrección de errores que se construyen a partir de gráficos expansores bipartitos . Junto con los códigos 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 sólo dos elementos, por lo que los códigos expansores pertenecen a la clase de códigos binarios . Además, los códigos de expansión 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 verificación de paridad es la matriz de adyacencia de un gráfico expansor bipartito . Estos códigos tienen 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 gráfico biregular 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 para 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 de corrección de errores de longitud de bloque . El código de expansión es el código de longitud de bloque cuyas palabras de código son 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 gráficos de expansión sin pérdidas no triviales. Además, podemos construirlos explícitamente. ^[2]

Tasa

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

Distancia

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

Prueba

Tenga en cuenta que podemos considerar cada palabra de código en como un subconjunto de vértices , diciendo que el vértice si y solo si el índice de la palabra de código es 1. Entonces es una palabra de código si cada vértice es adyacente a un número par de vértices en . (Para ser una palabra en clave , donde está la matriz de verificación de paridad. Luego, cada vértice en corresponde a cada columna de . La multiplicación de la matriz da el resultado deseado). Entonces, si un vértice es adyacente a un solo vértice en , Sabemos inmediatamente que no es una palabra clave. Denotemos a los vecinos en de y denotemos aquellos vecinos de los cuales son únicos, es decir, adyacentes a un único 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 . sigue ya que el grado de cada vértice es . Por la propiedad de expansión del gráfico, debe haber un conjunto de aristas que vayan a vértices distintos. Los bordes restantes hacen que, como máximo, los vecinos no sean ú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

Todo lo suficientemente pequeño tiene un vecino único. Esto sigue desde . ${\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 prueba el caso , así que supongamos . Deja tal que . Por el Lema 1, sabemos que . Entonces hay un vértice en iff y lo sabemos, por lo que, según la primera parte del Lema 1, lo sabemos . Dado que , y por 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

Tenga en cuenta que si a tiene al menos 1 vecino único, es decir , entonces la palabra correspondiente a no puede ser una palabra en código, ya que no se multiplicará por el vector de todos ceros por la matriz de verificación de paridad. Por el argumento anterior, . Como es lineal, concluimos que tiene una distancia 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 superiormente 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 con el tiempo. ^[3] ${\displaystyle O(n^{2})\,}$ ${\displaystyle O(n)\,}$

Descodificación

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

Sea el vértice de que corresponde al índice enésimo en las palabras clave de . Sea una palabra recibida, y . Dejar ser y ser . Entonces considere el algoritmo codicioso: ${\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 que hay av 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

Primero mostramos 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 de 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 be . 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 . Entonces, un vértice promedio tiene al menos vecinos únicos (recuerde que los vecinos únicos están insatisfechos 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)\,}$

Entonces, si aún no hemos llegado a una palabra clave, siempre habrá algún vértice que voltear. A continuación, mostramos que el número de errores nunca puede aumentar más allá de . ${\displaystyle \gamma n\,}$

Lema 4

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

Prueba

Cuando volteamos un vértice y se intercambian, y como teníamos , esto significa que el número de vértices insatisfechos a la derecha disminuye al menos en uno después de cada volteo. Dado que , el número inicial de vértices insatisfechos es como máximo , por la regularidad del gráfico . Si llegamos a una cadena con errores, entonces, según 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 comenzamos con (la mitad de la distancia de ), siempre encontraremos un vértice para voltear. Cada giro reduce el número de vértices insatisfechos en al menos 1 y, por lo tanto, el algoritmo termina en la mayoría de los pasos y termina en alguna palabra en código, según el Lema 3. (Si no fuera en una palabra en código, habría algún vértice para voltear ). El lema 4 nos muestra que nunca podemos estar más lejos que la palabra clave correcta. Dado que el código tiene distancia (desde ), la palabra clave en la que termina debe ser la palabra clave correcta, ya que el número de cambios de bits es menor que la mitad de la distancia (por lo que no podríamos haber viajado lo suficiente como para alcanzar ninguna otra palabra clave). ${\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 mostramos que el algoritmo puede lograr una decodificación en tiempo lineal. Sea constante y sea el grado máximo de cualquier vértice en . Tenga en cuenta que también es constante para 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 el tiempo para calcular una lista de vértices en los que tenemos . ${\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 con más vecinos pares que impares, insertando/eliminando según sea necesario. Por 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 , donde y son constantes. ${\displaystyle O(mdr)=O(n)\,}$ ${\displaystyle d\,}$ ${\displaystyle r\,}$

Ver también

• Gráfico de expansión
• Código de verificación de paridad de baja densidad
• Codificación y decodificación de tiempo lineal de códigos de corrección de errores.
• Códigos ABNNR y AEL

Notas

Este artículo está basado en las notas del curso del Dr. Venkatesan Guruswami. ^[4]

Referencias

1. Sipser, M.; Spielman, DA (1996). "Códigos de expansión". Transacciones IEEE sobre teoría de la información . 42 (6): 1710-1722. doi : 10.1109/18.556667.
2. Capalbo, M.; Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Conductores de aleatoriedad y expansores sin pérdidas de grado constante". STOC '02 Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la informática . ACM. págs. 659–668. doi :10.1145/509907.510003. ISBN 978-1-58113-495-7. S2CID  1918841.
3. Spielman, D. (1996). "Códigos de corrección de errores codificables y decodificables en tiempo lineal". Transacciones IEEE sobre teoría de la información . 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 de Carnegie mellon.
   Guruswami, V. (septiembre de 2004). "Columna de invitados: códigos de corrección de errores y gráficos de expansión" . Noticias ACM SIGACT . 35 (3): 25–41. doi :10.1145/1027914.1027924. S2CID  17550280.