Código fuente

En teoría de la codificación , los códigos fuente (también conocidos como códigos de borrado sin tasa ) son una clase de códigos de borrado que poseen la propiedad de que se puede generar una secuencia potencialmente ilimitada de símbolos de codificación a partir de un conjunto dado de símbolos fuente, de manera que los símbolos fuente originales se pueden recuperar idealmente a partir de cualquier subconjunto de los símbolos de codificación cuyo tamaño sea igual o ligeramente mayor que el número de símbolos fuente. El término " fuente" o "sin tasa" se refiere al hecho de que estos códigos no presentan una tasa de codificación fija .

Un código fuente es óptimo si los k símbolos fuente originales pueden recuperarse a partir de cualquier conjunto de k símbolos de codificación recibidos correctamente (es decir, excluyendo aquellos que fueron borrados). Se conocen códigos fuente que poseen algoritmos de codificación y decodificación eficientes y que permiten la recuperación de los k símbolos fuente originales a partir de cualquier conjunto de k' símbolos de codificación con alta probabilidad, donde k' es ligeramente mayor que k .

Los códigos LT fueron la primera implementación práctica de los códigos fuente. Posteriormente se introdujeron los códigos Raptor y los códigos en línea , que logran una complejidad de codificación y decodificación lineal mediante una etapa de precodificación de los símbolos de entrada. La codificación de red triangular logra la codificación y decodificación lineal mediante codificación no lineal y decodificación mediante el método de sustitución inversa.

Los códigos Fountain son aplicables de forma flexible a una tasa de codificación fija , o cuando no se puede determinar una tasa de codificación fija a priori, y cuando se requiere una codificación y decodificación eficiente de grandes cantidades de datos.

Un ejemplo es el de un carrusel de datos , donde un archivo grande se transmite continuamente a un conjunto de receptores. ^{[ 1 ]} Al usar un código de borrado de tasa fija, un receptor que no recibe un símbolo fuente (debido a un error de transmisión) se enfrenta al problema del recolector de cupones : debe recibir correctamente un símbolo de codificación que no posee. Este problema se hace mucho más evidente al usar un código de borrado tradicional de longitud corta, ya que el archivo debe dividirse en varios bloques, cada uno de los cuales se codifica por separado: el receptor debe ahora recopilar la cantidad necesaria de símbolos de codificación faltantes para cada bloque. Al usar un código fuente, basta con que un receptor recupere cualquier subconjunto de símbolos de codificación de un tamaño ligeramente mayor que el conjunto de símbolos fuente. (En la práctica, la transmisión suele ser programada por un operador para un período de tiempo fijo en función de las características de la red y los receptores, así como de la fiabilidad de entrega deseada; por lo tanto, el código fuente se utiliza a una tasa de codificación que se determina dinámicamente en el momento en que se programa la transmisión del archivo).

Otra aplicación es la del ARQ híbrido en escenarios de multidifusión fiables : la información de paridad solicitada por un receptor puede resultar útil para todos los receptores del grupo de multidifusión.

Los códigos Raptor son los códigos fuente más eficientes en este momento, ^{[ 2 ]} con algoritmos de codificación y decodificación de tiempo lineal muy eficientes, y requieren solo un pequeño número constante de operaciones XOR por símbolo generado tanto para la codificación como para la decodificación. ^{[ 3 ]} IETF RFC 5053 especifica en detalle un código Raptor sistemático , que ha sido adoptado en múltiples estándares más allá del IETF, como dentro del estándar 3GPP MBMS para entrega de archivos de difusión y servicios de transmisión, el estándar DVB-H IPDC para entrega de servicios IP sobre redes DVB , y DVB-IPTV para entrega de servicios de televisión comercial sobre una red IP. Este código puede usarse con hasta 8192 símbolos fuente en un bloque fuente, y un total de hasta 65 536 símbolos codificados generados para un bloque fuente. Este código tiene una sobrecarga de recepción relativa promedio del 0,2 % cuando se aplica a bloques fuente con 1000 símbolos fuente, y tiene una sobrecarga de recepción relativa de menos del 2 % con una probabilidad del 99,9999 %. ^{[ 4 ]} La sobrecarga de recepción relativa se define como los datos de codificación adicionales necesarios, más allá de la longitud de los datos de origen, para recuperar los datos de origen originales, y se mide como un porcentaje del tamaño de los datos de origen. Por ejemplo, si la sobrecarga de recepción relativa es del 0,2 %, esto significa que se pueden recuperar datos de origen de 1 megabyte a partir de 1,002 megabytes de datos de codificación.  

En el RFC 6330 de la IETF se ha especificado un código Raptor más avanzado, con mayor flexibilidad y una sobrecarga de recepción mejorada, denominado RaptorQ. Este código puede utilizarse con hasta 56 403  símbolos fuente en un bloque fuente y un total de hasta 16 777 216  símbolos codificados generados para dicho bloque. El código es capaz de recuperar un bloque fuente a partir de cualquier conjunto de símbolos codificados igual al número de símbolos fuente del bloque con alta probabilidad, y en raras ocasiones a partir de un número ligeramente superior. El código RaptorQ forma parte integral de la instanciación ROUTE especificada en ATSC A-331 (ATSC 3.0).

Los códigos de borrado se utilizan en aplicaciones de almacenamiento de datos debido al enorme ahorro que suponen en el número de unidades de almacenamiento para un nivel determinado de redundancia y fiabilidad. Los requisitos del diseño de códigos de borrado para el almacenamiento de datos, especialmente para aplicaciones de almacenamiento distribuido, pueden ser bastante diferentes a los de los escenarios de comunicación o transmisión de datos. Uno de los requisitos de la codificación para sistemas de almacenamiento de datos es la forma sistemática, es decir, que los símbolos del mensaje original formen parte de los símbolos codificados. La forma sistemática permite leer los símbolos del mensaje sin decodificarlos desde una unidad de almacenamiento. Además, dado que el ancho de banda y la carga de comunicación entre los nodos de almacenamiento pueden ser un cuello de botella, los códigos que permiten una comunicación mínima son muy beneficiosos, sobre todo cuando falla un nodo y se necesita reconstruir el sistema para alcanzar el nivel inicial de redundancia. En este sentido, se espera que los códigos fuente permitan un proceso de reparación eficiente en caso de fallo: cuando se pierde un único símbolo codificado, no debería requerir demasiada comunicación ni computación entre otros símbolos codificados para recuperar el símbolo perdido. De hecho, a veces la latencia de reparación puede ser más importante que el ahorro de espacio de almacenamiento. Se prevé que los códigos de fuente reparables ^{[ 5 ]} aborden los objetivos de diseño de los códigos de fuente para sistemas de almacenamiento. Un estudio detallado sobre los códigos de fuente y sus aplicaciones se puede encontrar en ^{[ 6 ] .}

En Liquid Cloud Storage se ha propuesto un enfoque diferente para el almacenamiento distribuido que utiliza códigos fuente. ^{[ 7 ] [ 8 ]} Liquid Cloud Storage se basa en el uso de un código de borrado grande como el código RaptorQ especificado en IETF RFC 6330 (que proporciona una protección de datos significativamente mejor que otros sistemas), el uso de un proceso de reparación en segundo plano (que reduce significativamente los requisitos de ancho de banda de reparación en comparación con otros sistemas) y el uso de una organización de datos de flujo (que permite un acceso rápido a los datos incluso cuando no todos los símbolos codificados están disponibles).

• Códigos en línea
• Codificación de red lineal
• Compartir secretos
• Códigos Tornado , precursores de los códigos fuente.

• Amin Shokrollahi y Michael Luby (2011). "Códigos Raptor". Fundamentos y tendencias en la teoría de la comunicación y la información . 6 ( 3– 4). Now Publishers: 213– 322. doi : 10.1561/0100000060 . S2CID 1731099 . 
• Luby, Michael (2002). "Códigos LT". 43.º Simposio Anual del IEEE sobre Fundamentos de la Informática, 2002. Actas . págs. 271–282 . doi : 10.1109/sfcs.2002.1181950 . ISBN  0-7695-1822-2. S2CID 1861068 . 
• A. Shokrollahi (2006), "Códigos Raptor", IEEE Transactions on Information Theory , 52 (6): 2551– 2567, Bibcode : 2006ITIT...52.2551S , doi : 10.1109/tit.2006.874390 , S2CID 61814971 .
• P. Maymounkov (noviembre de 2002). "Códigos en línea" (PDF) . (Informe técnico) .
• David JC MacKay (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge University Press. Bibcode : 2003itil.book.....M . ISBN 0-521-64298-1.
• M. Luby , A. Shokrollahi , M. Watson, T. Stockhammer (octubre de 2007), Esquema de corrección de errores hacia adelante de Raptor para la entrega de objetos , RFC 5053 {{citation}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) .
• M. Luby , A. Shokrollahi , M. Watson, T. Stockhammer, L. Minder (mayo de 2011), Esquema de corrección de errores hacia adelante de RaptorQ para la entrega de objetos , RFC 6330 {{citation}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) .