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 solo dos elementos, por lo que los códigos de expansión pertenecen a la clase de códigos binarios . Además, los códigos de expansión se pueden codificar y decodificar en un tiempo proporcional a la longitud del bloque del código.
Códigos de expansión | |
---|---|
gráfico expansor bipartito | |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | |
Longitud del mensaje | |
Velocidad | |
Distancia | |
Tamaño del alfabeto | |
Notación | -código |
Códigos de expansión
En la teoría de la codificación , un código de expansión 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 una buena distancia relativa , dónde y son propiedades del gráfico de expansión como se define más adelante), tasa y decodificabilidad (algoritmos de tiempo de ejecución existe).
Definición
Considere un gráfico bipartito , dónde y son los conjuntos de vértices y es el conjunto de aristas que conectan vértices en a los vértices de . Suponga que cada vértice entiene grado (la gráfica es -izquierda- regular ),, y , . Luego es un gráfico de expansión si cada subconjunto lo suficientemente pequeño , tiene la propiedad que tiene al menos vecinos distintos en . Tenga en cuenta que esto es trivial para. Cuándo y por una constante , Nosotros decimos eso es un expansor sin pérdidas.
Desde es un gráfico bipartito, podemos considerar su matriz de adyacencia. Entonces el código lineal generado al ver la transposición de esta matriz como una matriz de verificación de paridad es un código de expansión.
Se ha demostrado que existen gráficos expansores sin pérdidas no triviales. Además, podemos construirlos explícitamente. [1]
Velocidad
La tasa de es su dimensión dividida por la longitud de su bloque. En este caso, la matriz de verificación de paridad tiene un tamaño, y por lo tanto tiene dimensión al menos .
Distancia
Suponer . Entonces la distancia de un código de expansión Por lo menos .
Prueba
Tenga en cuenta que podemos considerar cada palabra en clave en como un subconjunto de vértices , diciendo ese vértice si y solo si el El índice de la palabra de código es un 1. Entonces es una palabra en clave si cada vértice es adyacente a un número par de vértices en . (Para ser una palabra clave,, dónde es la matriz de control de paridad. Entonces, cada vértice en corresponde a cada columna de . Multiplicación de matrices sobre luego da el resultado deseado.) Entonces, si un vértice es adyacente a un solo vértice en , sabemos de inmediato que no es una palabra clave. Dejar denotar a los vecinos en de , y denotar a los vecinos de que son únicos, es decir, adyacentes a un solo vértice de .
Lema 1
Para cada de tamaño , .
Prueba
Trivialmente , desde implica . sigue ya que el grado de cada vértice en es . Por la propiedad de expansión de la gráfica, debe haber un conjunto dearistas que van a vértices distintos. El restante los bordes hacen como máximo vecinos no únicos, así que .
Corolario
Cada suficientemente pequeño Tiene un vecino unico. Esto sigue desde.
Lema 2
Cada subconjunto con Tiene un vecino unico.
Prueba
El lema 1 prueba el caso , así que suponga . Dejar tal que . Por el Lema 1, sabemos que. Entonces un vértice es en si , y sabemos que , entonces por la primera parte del Lema 1, sabemos . Desde, , y por lo tanto no está vacío.
Corolario
Tenga en cuenta que si un tiene al menos 1 vecino único, es decir , luego la palabra correspondiente correspondiente a no puede ser una palabra de código, ya que no se multiplicará al vector de todos ceros por la matriz de verificación de paridad. Por el argumento anterior,. Desde es lineal, llegamos a la conclusión de que tiene distancia al menos .
Codificación
El tiempo de codificación de un código de expansión está delimitado por el de un código lineal general: por multiplicación de matrices. Un resultado de Spielman muestra que la codificación es posible enhora. [2]
Descodificación
La decodificación de códigos de expansión es posible en tiempo cuando utilizando el siguiente algoritmo.
Dejar ser el vértice de que corresponde a la th índice en las palabras de código de . Dejar ser una palabra recibida, y . Dejar ser , y ser . Entonces considere el algoritmo codicioso:
Entrada: palabra recibida.
inicializar y 'a ymientras que hay av en R adyacente a un número impar de vértices en V (y ') si hay una i tal que o (i)> e (i) voltear la entrada i en y ' demás fallar
Resultado: falla o palabra de código modificada.
Prueba
Primero mostramos la exactitud del algoritmo y luego examinamos su tiempo de ejecución.
Exactitud
Debemos demostrar que el algoritmo termina con la palabra de código correcta cuando la palabra de código recibida está dentro de la mitad de la distancia del código de la palabra de código original. Sea el conjunto de variables corruptas, , y el conjunto de vértices insatisfechos (adyacentes a un número impar de vértices) en ser . El siguiente lema resultará útil.
Lema 3
Si , entonces hay un con .
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 ), desde , y así hay un vértice con .
Entonces, si aún no hemos llegado a una palabra de código, siempre habrá algún vértice para voltear. A continuación, mostramos que el número de errores nunca puede aumentar más allá de.
Lema 4
Si empezamos con , entonces nunca llegamos en cualquier punto del algoritmo.
Prueba
Cuando volteamos un vértice , y se intercambian, y dado que teníamos , esto significa que el número de vértices insatisfechos de la derecha disminuye al menos uno después de cada cambio. Desde, el número inicial de vértices insatisfechos es como máximo , por el gráfico -regularidad. 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.
Los lemas 3 y 4 nos muestran que si comenzamos con (la mitad de la distancia de ), entonces siempre encontraremos un vértice voltear. Cada giro reduce el número de vértices insatisfechos en por 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 una palabra de código, habría algún vértice para voltear). El lema 4 nos muestra que nunca podremos estar más allá delejos de la palabra clave correcta. Dado que el código tiene distancia (desde ), 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 menos de la mitad de la distancia (por lo que no podríamos haber viajado lo suficiente para alcanzar cualquier otra palabra de código).
Complejidad
Ahora mostramos que el algoritmo puede lograr una decodificación de tiempo lineal. Dejar ser constante, y ser el grado máximo de cualquier vértice en . Tenga en cuenta que también es constante para construcciones conocidas.
- Preprocesamiento: se necesita tiempo para calcular si cada vértice en tiene un número par o impar de vecinos.
- Preprocesamiento 2: Tomamos tiempo para calcular una lista de vértices en cual tiene .
- Cada iteración: simplemente eliminamos el primer elemento de la lista. Para actualizar la lista de vértices pares / impares en, solo necesitamos actualizar entradas, insertando / quitando según sea necesario. Luego actualizamos entradas en la lista de vértices en con vecinos más impares que pares, insertando / quitando según sea necesario. Por lo tanto, cada iteración toma hora.
- Como se argumentó anteriormente, el número total de iteraciones es como máximo .
Esto da un tiempo de ejecución total de tiempo, donde y son constantes.
Ver también
- Gráfico expansor
- 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. [3]
Referencias
- ↑ 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 computación . ACM. págs. 659–668. doi : 10.1145 / 509907.510003 . ISBN 978-1-58113-495-7.
- ^ 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 .
- ^ Guruswami, V. (15 de noviembre de 2006). "Lección 13: Códigos de expansión" (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 invitado: 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 .