En informática , los códigos en línea son un ejemplo de códigos de borrado sin tasa . Estos códigos pueden codificar un mensaje en varios símbolos, de modo que el conocimiento de cualquier fracción de ellos permite 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 externa 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 un cierto número de bloques de verificación, se puede recuperar una fracción del mensaje compuesto. Una vez que se haya recuperado lo suficiente, la decodificación externa se puede utilizar para recuperar el mensaje original.
Discusión detallada
Los códigos online 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. Se puede recuperar un mensaje de n bloques, con alta probabilidad , de (1 + 3ε) n bloques de verificación. La probabilidad de falla es (ε / 2) q + 1 .
Codificación externa
Se puede usar 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, 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.
Codificación interna
La codificación interna toma el mensaje compuesto y genera una secuencia 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 control es el número de bloques al que está unido. El grado se determina muestreando una distribución aleatoria, p , que se define como:
- por
Una vez que se conoce el grado del bloque de verificación, los bloques del mensaje compuesto al que está adjunto se eligen uniformemente.
Descodificación
Obviamente, el decodificador de la etapa interna debe contener bloques de verificación que actualmente no puede decodificar . Un bloque de verificación solo 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 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 actualmente. Esto sube casi linealmente al principio, ya que se reciben muchos bloques de control con grado> 1 pero no se pueden utilizar. En cierto punto, algunos de los bloques de verificación se pueden usar repentinamente, resolviendo más bloques, lo que 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 está un poco tímido para decodificar todo por un tiempo después de haber recibido n bloques de verificación. La codificación externa asegura que unos pocos bloques elusivos del decodificador interno no sean un problema, ya que el archivo se puede recuperar sin ellos.
enlaces externos
- Papel original
- Rateless Codes and Big Downloads (Un artículo más accesible del mismo autor)
- Artículos de Petar Maymounkov
- Un proyecto Ruby alojado en RubyForge que contiene una biblioteca Ruby para codificación en línea