Códigos en línea

Se puede utilizar cualquier código de borrado como codificación externa, pero el autor de los códigos en línea sugiere lo siguiente.

Para cada bloque de mensaje, se eligen pseudoaleatoriamente q bloques auxiliares (de un total de 0,55 q ε n bloques auxiliares) para adjuntarlo. Cada bloque auxiliar es entonces el resultado de la operación XOR de todos los bloques de mensaje que se le han adjuntado.

La codificación interna toma el mensaje compuesto y genera una secuencia de bloques de verificación. Un bloque de verificación es el resultado de la operación XOR de todos los bloques del mensaje compuesto al que está adjunto.

El grado de un bloque de control es el número de bloques a los que está conectado. El grado se determina mediante el muestreo de una distribución aleatoria, p , que se define como:

${\displaystyle F=\left\lceil {\frac {\ln(\epsilon ^{2}/4)}{\ln(1-\epsilon /2)}}\right\rceil }$

${\displaystyle p_{1}=1-{\frac {1+1/F}{1+\epsilon }}}$

${\displaystyle p_{i}={\frac {(1-p_{1})F}{(F-1)i(i-1)}}}$para${\displaystyle 2\leq i\leq F}$

Una vez que se conoce el grado del bloque de verificación, los bloques del mensaje compuesto al que está adjunto se eligen de forma uniforme.

Obviamente, el decodificador de la etapa interna debe contener bloques de verificación que no puede decodificar actualmente . Un bloque de verificación solo se puede decodificar cuando se conocen todos los bloques a los que está conectado, excepto uno. El gráfico de la izquierda muestra el progreso de un decodificador interno. El eje x representa el número de bloques de verificación recibidos y la línea discontinua muestra el número de bloques de verificación que no se pueden utilizar. Este número aumenta casi linealmente al principio, ya que se reciben muchos bloques de verificación con grado > 1 que no se pueden utilizar. En cierto punto, algunos de los bloques de verificación se vuelven repentinamente utilizables, lo que permite resolver más bloques y, a su vez, habilitar 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 tarda un poco en decodificar todo tras recibir n bloques de verificación. La codificación externa garantiza que algunos bloques que el decodificador interno no representen un problema, ya que el archivo se puede recuperar sin ellos.