En informática , los códigos en línea son un ejemplo de códigos de borrado sin tasas . Estos códigos pueden codificar un mensaje en una serie de símbolos de modo que el conocimiento de cualquier fracción de ellos permita recuperar el mensaje original (con alta probabilidad). Los códigos sin tasa producen una cantidad arbitrariamente grande de símbolos que pueden transmitirse hasta que los receptores tengan suficientes símbolos.
El algoritmo de codificación en línea consta de varias fases. Primero, el mensaje se divide en n bloques de mensajes de tamaño fijo. Entonces la codificación exterior es un código de borrado que produce bloques auxiliares que se añaden a los bloques de mensaje para formar un mensaje compuesto.
A partir de esto, la codificación interna genera bloques de verificación. Al recibir una cierta cantidad de bloques de verificación, se puede recuperar una fracción del mensaje compuesto. Una vez que se haya recuperado lo suficiente, se puede utilizar la decodificación externa para recuperar el mensaje original.
Los códigos en línea están parametrizados por el tamaño del bloque y dos escalares , q y ε . Los autores sugieren q =3 y ε=0,01. Estos parámetros establecen el equilibrio entre la complejidad y el rendimiento de la codificación. Un mensaje de n bloques se puede recuperar, con alta probabilidad , a partir de (1+3ε) n bloques de verificación. La probabilidad de falla es (ε/2) q+1 .
Se puede utilizar cualquier código de borrado como codificación externa, pero el autor de códigos en línea sugiere lo siguiente.
Para cada bloque de mensaje, elija pseudoaleatoriamente q bloques auxiliares (de un total de 0,55 q ε n bloques auxiliares) para adjuntarlo. Cada bloque auxiliar es entonces el XOR de todos los bloques de mensajes que se le han adjuntado.
La codificación interna toma el mensaje compuesto y genera un flujo de bloques de verificación. Un bloque de verificación es el XOR de todos los bloques del mensaje compuesto al que está adjunto.
El grado de un bloque de verificación es el número de bloques a los que está adjunto. El grado se determina muestreando una distribución aleatoria, p , que se define como:
Una vez conocido el grado del bloque de verificación, los bloques del mensaje compuesto al que está adjunto se eligen de manera uniforme.
Obviamente, el decodificador de la etapa interna debe contener bloques de verificación que actualmente no puede decodificar. Un bloque de verificación sólo se puede decodificar cuando se conocen todos menos uno de los bloques a los que está adjunto. El gráfico de la izquierda muestra el progreso de un decodificador interno. El eje x traza la cantidad de bloques de verificación recibidos y la línea discontinua muestra la cantidad de bloques de verificación que no se pueden usar actualmente. Al principio, esto sube casi linealmente, ya que se reciben muchos bloques de verificación con grado > 1, pero no se pueden utilizar. En cierto punto, algunos de los bloques de verificación de repente se pueden usar, lo que resuelve más bloques, lo que luego hace que se puedan usar más bloques de verificación. Muy rápidamente se puede decodificar todo el archivo.
Como también muestra el gráfico, el decodificador interno apenas logra decodificar todo por un tiempo después de haber recibido n bloques de verificación. La codificación externa garantiza que algunos bloques esquivos del decodificador interno no sean un problema, ya que el archivo se puede recuperar sin ellos.
