En informática , los códigos de transformada 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 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 o exclusiva ( ) para codificar y decodificar el mensaje. [2]
Los códigos LT no tienen tasa de transferencia porque el algoritmo de codificación puede, en principio, producir una cantidad infinita de paquetes de mensajes (es decir, el porcentaje de paquetes que se deben recibir para decodificar el mensaje puede ser arbitrariamente pequeño). Son códigos de corrección de borrado porque se pueden utilizar para transmitir datos digitales de manera confiable en un canal de borrado .
La siguiente generación, 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 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 para 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 de un código LT únicamente.
El esquema tradicional para transferir datos a través de un canal de borrado depende de una comunicación bidireccional continua.
Algunas 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, resuelven este problema adoptando un protocolo de comunicación esencialmente unidireccional.
Como se mencionó anteriormente, el código RaptorQ especificado en IETF RFC 6330 supera a un código LT en la práctica.
El proceso de codificación comienza dividiendo el mensaje no codificado en n bloques de longitud aproximadamente igual. A continuación, se generan los paquetes codificados con la ayuda de un generador de números pseudoaleatorios .
Este proceso continúa hasta que el receptor señala que el mensaje ha sido recibido y decodificado exitosamente.
El proceso de decodificación utiliza la operación " o exclusiva " para recuperar el mensaje codificado.
Este procedimiento de decodificación funciona porque A A = 0 para cualquier cadena de bits A . Después de que d − 1 bloques distintos hayan sido codificados de forma exclusiva en un paquete de grado d , el contenido original no codificado del bloque no coincidente es todo lo que queda. En símbolos tenemos
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 bloque de mensaje reales { i 1 , i 2 , ..., i d }, el codificador podría simplemente enviar una "clave" corta que sirviera como semilla para el generador de números pseudoaleatorios (PRNG) o la tabla de índices utilizada para construir la lista de índices. Dado que el receptor equipado con el mismo RNG o la misma tabla de índices puede recrear de manera confiable la lista "aleatoria" de índices a partir de esta semilla, el proceso de decodificación puede completarse con éxito. Alternativamente, al combinar 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]
Sólo hay un parámetro que puede utilizarse 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 1 , i 2 , ..., 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] analizó la " distribución ideal de solitones " definida por
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 combinarán con ninguno de los paquetes de transmisión. Por lo tanto, en la práctica, una distribución modificada, la " distribución robusta de solitones ", se sustituye por 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 asegurar que todos los bloques originales se incluirán en algún paquete. [4]
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07edd84325bf9894feb871f759adbed68b3fad45)