En teoría de codificación , los códigos fuente (también conocidos como códigos de borrado sin tasa ) son una clase de códigos de borrado con 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 modo que los símbolos fuente originales se pueden recuperar idealmente de cualquier subconjunto de los símbolos de codificación de tamaño igual o apenas 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 código fija .
Un código fuente es óptimo si los k símbolos fuente originales se pueden recuperar de cualesquiera k símbolos de codificación recibidos con éxito (es decir, excluyendo aquellos que se borraron). Se conocen códigos fuente que tienen algoritmos de codificación y decodificación eficientes y que permiten la recuperación de los k símbolos fuente originales de cualesquiera k' de los símbolos de codificación con alta probabilidad, donde k' es apenas un poco mayor que k .
Los códigos LT fueron la primera realizació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 en tiempo lineal mediante una etapa de precodificación de los símbolos de entrada.
Los códigos fuente se pueden aplicar de manera flexible a una tasa de código fija , o cuando no se puede determinar una tasa de código fija a priori y 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 utilizar un código de borrado de tasa fija, un receptor al que le falta un símbolo de origen (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 tiene ya. Este problema se hace mucho más evidente cuando se utiliza un código de borrado de longitud corta tradicional, ya que el archivo debe dividirse en varios bloques, cada uno de los cuales se codifica por separado: el receptor ahora debe recopilar la cantidad requerida de símbolos de codificación faltantes para cada bloque. Al utilizar un código fuente, es suficiente que un receptor recupere cualquier subconjunto de símbolos de codificación de tamaño ligeramente mayor que el conjunto de símbolos de origen. (En la práctica, la transmisión suele programarse para un período de tiempo fijo por un operador en función de las características de la red y los receptores y la fiabilidad de entrega deseada, y por lo tanto el código fuente se utiliza a una tasa de código 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 confiable : la información de paridad solicitada por un receptor puede ser potencialmente ú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] teniendo algoritmos de codificación y decodificación de tiempo lineal muy eficientes, y requiriendo solamente un pequeño número constante de operaciones XOR por símbolo generado tanto para codificación como para 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 streaming, el estándar DVB-H IPDC para entregar servicios IP sobre redes DVB , y DVB-IPTV para entregar servicios de TV comercial sobre una red IP. Este código puede ser usado con hasta 8,192 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 de 0.2% cuando se aplica a bloques fuente con 1,000 símbolos fuente, y tiene una sobrecarga de recepción relativa de menos de 2% con probabilidad 99.9999%. [4] La sobrecarga relativa de recepción 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, medidos como un porcentaje del tamaño de los datos de origen. Por ejemplo, si la sobrecarga relativa de recepción es del 0,2 %, esto significa que se pueden recuperar datos de origen de un tamaño de 1 megabyte a partir de 1,002 megabytes de datos de codificación.
En la RFC 6330 de IETF se ha especificado un código Raptor más avanzado con mayor flexibilidad y una mejor recepción, denominado RaptorQ. El código RaptorQ especificado se puede utilizar con hasta 56.403 símbolos de origen en un bloque de origen y un total de hasta 16.777.216 símbolos codificados generados para un bloque de origen. Este código puede recuperar un bloque de origen a partir de cualquier conjunto de símbolos codificados igual al número de símbolos de origen en el bloque de origen con alta probabilidad y, en casos excepcionales, a partir de un número ligeramente superior al de símbolos de origen en el bloque de origen. El código RaptorQ es una 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 ahorro masivo en el número de unidades de almacenamiento para un nivel dado de redundancia y confiabilidad. Los requisitos del diseño de códigos de borrado para el almacenamiento de datos, en particular para aplicaciones de almacenamiento distribuido, pueden ser bastante diferentes en relación con los escenarios de comunicación o transmisión de datos. Uno de los requisitos de codificación para sistemas de almacenamiento de datos es la forma sistemática, es decir, los símbolos del mensaje original son parte de los símbolos codificados. [ cita requerida ] La forma sistemática permite leer los símbolos del mensaje sin decodificarlos de una unidad de almacenamiento. Además, dado que el ancho de banda y la carga de comunicación entre nodos de almacenamiento pueden ser un cuello de botella, los códigos que permiten una comunicación mínima son muy beneficiosos, en particular cuando un nodo falla y se necesita una reconstrucción del sistema para lograr el nivel inicial de redundancia. En ese sentido, se espera que los códigos fuente permitan un proceso de reparación eficiente en caso de falla: cuando se pierde un solo símbolo codificado, no debería requerir demasiada comunicación y computación entre otros símbolos codificados para resucitar el símbolo perdido. De hecho, la latencia de reparación a veces puede ser más importante que el ahorro de espacio de almacenamiento. Se prevé que los códigos de fuentes reparables [5] aborden los objetivos de diseño de códigos de fuentes para sistemas de almacenamiento. Se puede encontrar un estudio detallado sobre los códigos de fuentes y sus aplicaciones en [6] .
En Liquid Cloud Storage se ha propuesto un enfoque diferente para el almacenamiento distribuido utilizando 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).
{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{citation}}: CS1 maint: varios nombres: lista de autores ( enlace ).{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace ).