Código de transformación de Luby

En ciencias de la computación , 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 grafos 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 el empleo de un algoritmo particularmente simple basado en la operación OR exclusiva (${\displaystyle \oplus }$) para codificar y decodificar el mensaje. ^{[ 2 ]}

Los códigos LT no tienen tasa de transmisión 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 utilizarse para transmitir datos digitales de forma fiable en un canal con borrado .

La siguiente generación de códigos, más allá de los códigos LT, son los códigos Raptor (véase, por ejemplo, IETF RFC 5053 o IETF RFC 6330), que cuentan con codificación y decodificación en tiempo lineal. Los códigos Raptor se basan fundamentalmente en los códigos LT; es decir, su codificación utiliza dos etapas, siendo la segunda la codificación LT. De forma similar, la decodificación con códigos Raptor se basa principalmente en la decodificación LT, aunque esta se combina con técnicas de decodificación más avanzadas. El código RaptorQ, especificado en IETF RFC 6330, el código fuente más avanzado, ofrece probabilidades de decodificación y un rendimiento muy superiores en comparación con el uso exclusivo de un código LT.

El método 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 logra decodificarlo, envía una confirmación al transmisor. De lo contrario, solicita al transmisor que vuelva a enviar el paquete.
• Este proceso bidireccional continúa hasta que todos los paquetes del mensaje se hayan transferido correctamente.

Ciertas redes, como las utilizadas para la transmisión inalámbrica celular, no disponen de un canal de retroalimentación. Las aplicaciones en estas redes aún requieren fiabilidad. Los códigos Fountain 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 dispone de suficientes paquetes válidos para reconstruir el mensaje completo. Cuando el mensaje se ha recibido correctamente, el receptor indica que la transmisión ha finalizado.

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

El proceso de codificación comienza dividiendo el mensaje sin codificar en n bloques de longitud aproximadamente igual. A continuación, se generan 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 M _i 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 añade un prefijo al paquete codificado, que define cuántos bloques n hay en el mensaje, cuántos bloques d se han combinado mediante la operación OR exclusiva en la parte de datos de este paquete y la lista de índices { i ₁ , i ₂ , ..., i _d }.   
• Finalmente, se aplica al paquete algún tipo de código de detección de errores (quizás tan simple como una comprobación de redundancia cíclica ) y el paquete se transmite.

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

El proceso de decodificación utiliza la operación " o exclusivo " 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 recibido correctamente tiene un grado d  >  1, primero se procesa comparándolo con todos los bloques completamente decodificados en el área de cola de mensajes (como se describe con más detalle en el siguiente paso) y luego se almacena en un área de búfer si su grado reducido es mayor que 1.
• Cuando se recibe un nuevo paquete limpio de grado d  =  1 (bloque M _i ) (o el grado del paquete actual se reduce a 1 por el paso anterior), se mueve al área de cola de mensajes y luego se compara con todos los paquetes de grado d  >  1 que residen en el búfer. Se realiza una operación OR exclusiva en la porción de datos de cualquier paquete almacenado en búfer que haya sido codificado usando M _i , el grado de ese paquete coincidente se decrementa y la lista de índices para ese paquete se ajusta para reflejar la aplicación de M _i .
• Cuando este proceso desbloquea un bloque de grado d  =  2 en el búfer, ese bloque se reduce a grado 1 y a su vez se mueve al área de cola de mensajes, y luego se procesa contra 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 correctamente.

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

${\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}}}$

Existen varias variantes 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 reales de los bloques de mensajes { _{i1, i2, ..., id} } _, el _codificador podría simplemente enviar una "clave" corta que sirviera como semilla para el generador de números pseudoaleatorios (GNA) o la tabla de índices utilizada para construir la lista de índices. Dado que el receptor, equipado con el mismo GNA o tabla de índices, puede recrear de forma fiable la lista "aleatoria" de índices a partir de esta semilla, el proceso de decodificación puede completarse con éxito. Alternativamente, combinando un código LT simple de grado medio bajo con un código robusto de corrección de errores, se puede construir un código Raptor que, en la práctica, superará el rendimiento de un código LT optimizado. ^{[ 3 ]}   

Solo hay un parámetro que se puede usar para optimizar un código LT directo: la función de distribución de grado (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 los 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 complete el proceso de decodificación. Sin embargo, la distribución ideal de solitones no funciona bien en la práctica, ya que cualquier fluctuación alrededor del 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 combinarán mediante XOR en ninguno de los paquetes de transmisión. Por lo tanto, en la práctica, se sustituye la distribución ideal por una distribución modificada, la " distribución robusta de solitones ". 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 asegurar que todos los bloques originales se incluyan en algún paquete. ^{[ 4 ]}

• Códigos en línea
• Códigos Raptor
• códigos de tornados

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