Código de transformación de Luby

En informática , los códigos de transformación de Luby ( códigos LT ) son la primera clase de códigos fuente prácticos que son códigos de corrección de borrado casi óptimos . Fueron inventados por Michael Luby en 1998 y publicados en 2002. ^[1] Al igual que otros códigos fuente , los códigos LT dependen de gráficos bipartitos dispersos para intercambiar la sobrecarga de recepción por la velocidad de codificación y decodificación. La característica distintiva de los códigos LT es emplear un algoritmo particularmente simple basado en la operación exclusiva u ( ) para codificar y decodificar el mensaje. ^[2] ${\displaystyle \oplus }$

Los códigos LT no tienen tasas porque el algoritmo de codificación puede, en principio, producir un número infinito de paquetes de mensajes (es decir, el porcentaje de paquetes que deben recibirse para decodificar el mensaje puede ser arbitrariamente pequeño). Son códigos de corrección de borrado porque pueden usarse para transmitir datos digitales de manera confiable en un canal de borrado .

La próxima generación más allá de los códigos LT son los códigos Raptor (ver, por ejemplo, IETF RFC 5053 o IETF RFC 6330), que tienen codificación y decodificación de tiempo lineal. Los códigos Raptor se basan fundamentalmente en códigos LT, es decir, la codificación de códigos Raptor utiliza dos etapas de codificación, donde la segunda etapa es la codificación LT. De manera similar, la decodificación con códigos Raptor se basa principalmente en la decodificación LT, pero la decodificación LT se mezcla con técnicas de decodificación más avanzadas. El código RaptorQ especificado en IETF RFC 6330, que es el código fuente más avanzado, tiene probabilidades de decodificación y rendimiento muy superiores en comparación con el uso solo de un código LT.

¿Por qué utilizar un código LT?

El esquema tradicional para transferir datos a través de un canal de borrado depende de una comunicación bidireccional continua.

• El remitente codifica y envía un paquete de información.
• El receptor intenta decodificar el paquete recibido. Si se puede decodificar, el receptor envía un acuse de recibo al transmisor. De lo contrario, el receptor le pide al transmisor que envíe el paquete nuevamente.
• Este proceso bidireccional continúa hasta que todos los paquetes del mensaje se hayan transferido correctamente.

Ciertas redes, como las que se utilizan para la transmisión inalámbrica celular, no tienen un canal de retroalimentación. Las aplicaciones en estas redes aún requieren confiabilidad. Los códigos fuente en general, y los códigos LT en particular, solucionan este problema adoptando un protocolo de comunicación esencialmente unidireccional.

• El remitente codifica y envía paquete tras paquete de información.
• El receptor evalúa cada paquete a medida que lo recibe. Si hay un error, el paquete erróneo se descarta. De lo contrario, el paquete se guarda como parte del mensaje.
• Finalmente, el receptor tiene suficientes paquetes válidos para reconstruir el mensaje completo. Cuando todo el mensaje se ha recibido con éxito, el receptor indica que la transmisión se ha completado.

Como se mencionó anteriormente, el código RaptorQ especificado en IETF RFC 6330 supera a un código LT en la práctica.

codificación LT

El proceso de codificación comienza dividiendo el mensaje no codificado en n bloques de aproximadamente la misma longitud. Luego se producen paquetes codificados con la ayuda de un generador de números pseudoaleatorios .

• El grado d , 1 ≤  d  ≤  n , del siguiente paquete se elige al azar.
• Se eligen aleatoriamente exactamente d bloques del mensaje.
• Si Mi es el iésimo bloque del mensaje, la porción _de datos del siguiente paquete se calcula como

${\displaystyle M_{i_{1}}\oplus M_{i_{2}}\oplus \cdots \oplus M_{i_{d}}\,}$

donde { i ₁ ,  i ₂ , ...,  i _d } son los índices elegidos aleatoriamente para los d bloques incluidos en este paquete.

• Se agrega un prefijo al paquete codificado, que define cuántos bloques n hay en el mensaje, cuántos bloques d han sido exclusivos en la porción de datos de este paquete y la lista de índices { i ₁ ,  i ₂ , .. .,  identificación _} .
• Finalmente, se aplica al paquete algún tipo de código de detección de errores (quizás tan simple como una verificación de redundancia cíclica ) y se transmite el paquete.

Este proceso continúa hasta que el receptor indica que el mensaje ha sido recibido y decodificado exitosamente.

decodificación LT

El proceso de decodificación utiliza la operación " exclusiva o " para recuperar el mensaje codificado.

• Si el paquete actual no está limpio o si replica un paquete que ya ha sido procesado, el paquete actual se descarta.
• Si el paquete actual recibido limpiamente es de grado d  > 1, primero se procesa contra todos los bloques completamente decodificados en el área de cola de mensajes (como se describe con más detalle en el siguiente paso), luego se almacena en un área de buffer si su grado reducido es mayor que 1.
• Cuando se recibe un paquete nuevo y limpio de grado d  = 1 (bloque Mi ₎ (o el grado del paquete actual se reduce a 1 mediante el paso anterior), se mueve al área de cola de mensajes y luego se compara con todos los demás. los paquetes de grado d  > 1 que residen en el buffer. Se integra de forma exclusiva en la porción de datos de cualquier paquete almacenado en el buffer que se codificó utilizando _Mi , _el grado de ese paquete coincidente se reduce y la lista de índices para ese paquete se ajusta para reflejar la aplicación de Mi.
• Cuando este proceso desbloquea un bloque de grado d  = 2 en el búfer, ese bloque se reduce al grado 1 y, a su vez, se mueve al área de cola de mensajes y luego se procesa con los paquetes que quedan en el búfer.
• Cuando los n bloques del mensaje se han movido al área de cola de mensajes, el receptor le indica al transmisor que el mensaje se ha decodificado exitosamente.

Este procedimiento de decodificación funciona porque A  A  = 0 para cualquier cadena de bits A. Después de que d  − 1 bloques distintos se hayan exclusivo en un paquete de grado d , todo lo que queda es el contenido original no codificado del bloque no coincidente. En símbolos tenemos ${\displaystyle \oplus }$ 

${\displaystyle {\begin{aligned}&{}\qquad (M_{i_{1}}\oplus \dots \oplus M_{i_{d}})\oplus (M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}})\\&=M_{i_{1}}\oplus M_{i_{1}}\oplus \dots \oplus M_{i_{k-1}}\oplus M_{i_{k-1}}\oplus M_{i_{k}}\oplus M_{i_{k+1}}\oplus M_{i_{k+1}}\oplus \dots \oplus M_{i_{d}}\oplus M_{i_{d}}\\&=0\oplus \dots \oplus 0\oplus M_{i_{k}}\oplus 0\oplus \dots \oplus 0\\&=M_{i_{k}}\,\end{aligned}}}$

Variaciones

Son posibles varias variaciones de los procesos de codificación y decodificación descritos anteriormente. Por ejemplo, en lugar de anteponer a cada paquete una lista de los índices de bloques de mensajes reales { i ₁ ,  i ₂ , ...,  i _d }, el codificador podría simplemente enviar una "clave" corta que sirviera como semilla para el paquete pseudoaleatorio. generador de números (PRNG) o tabla de índices utilizada para construir la lista de índices. Dado que el receptor equipado con el mismo RNG o tabla de índices puede recrear de manera confiable la lista "aleatoria" de índices a partir de esta semilla, el proceso de decodificación se puede completar con éxito. Alternativamente, combinando un código LT simple de grado promedio bajo con un código de corrección de errores robusto, se puede construir un código raptor que superará en la práctica a un código LT optimizado. ^[3]

Optimización de códigos LT

Sólo hay un parámetro que se puede utilizar para optimizar un código LT directo: la función de distribución de grados (descrita como un generador de números pseudoaleatorios para el grado d en la sección de codificación LT anterior). En la práctica, los otros números "aleatorios" (la lista de índices {  i ₁ ,  i ₂ , ...,  i _d  }) se toman invariablemente de una distribución uniforme en [0, n ), donde n es el número de bloques en en que se ha dividido el mensaje. ^[4]

El propio Luby ^[1] discutió la " distribución ideal de solitones " definida por

${\displaystyle {\begin{aligned}\mathrm {P} \{d=1\}&={\frac {1}{n}}\\[2pt]\mathrm {P} \{d=k\}&={\frac {1}{k(k-1)}}\qquad (k=2,3,\dots ,n).\,\end{aligned}}}$

Esta distribución de grados minimiza teóricamente el número esperado de palabras de código redundantes que se enviarán antes de que se pueda completar el proceso de decodificación. Sin embargo, la distribución ideal de solitones no funciona bien en la práctica porque cualquier fluctuación en torno al comportamiento esperado hace probable que en algún paso del proceso de decodificación no haya ningún paquete disponible de grado 1 (reducido), por lo que la decodificación fallará. Además, algunos de los bloques originales no se incluirán en ninguno de los paquetes de transmisión. Por lo tanto, en la práctica, una distribución modificada, la " distribución robusta de solitones ", sustituye a la distribución ideal. El efecto de la modificación es, generalmente, producir más paquetes de grado muy pequeño (alrededor de 1) y menos paquetes de grado mayor que 1, excepto por un pico de paquetes en una cantidad bastante grande elegida para garantizar que todos los bloques originales sean incluido en algún paquete. ^[4]

Ver también

• Códigos en línea
• Códigos de rapaces
• Códigos de tornado

notas y referencias

1. M.Luby, "LT Codes", 43º Simposio anual del IEEE sobre los fundamentos de la informática, 2002.
2. La operación exclusiva o (XOR), simbolizada por ⊕, tiene la propiedad muy útil de que A  ⊕  A  = 0, donde A es una cadena arbitraria de bits .
3. Códigos fuente, de DJC MacKay, publicado por primera vez en IEEE Proc.-Commun., vol. 152, núm. 6, diciembre de 2005.
4. Optimización de la distribución de grados de códigos LT con un enfoque de muestreo de importancia, por Esa Hyytiä, Tuomas Tirronen y Jorma Virtamo (2006).

enlaces externos

• "Implementación del código de transformación Luby en C#"
• "Implementación de Códigos Fuente para almacenamiento en C/C++"
• "Introducción a los códigos fuente: Códigos LT con Python"