En la 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 con la propiedad de que se puede generar una secuencia potencialmente ilimitada de símbolos de codificación a partir de un conjunto determinado de símbolos fuente, de modo que los símbolos fuente originales puedan idealmente ser recuperado de cualquier subconjunto de los símbolos de codificación de tamaño igual o sólo 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 exhiben una tasa de código fija .
Un código fuente es óptimo si los k símbolos fuente originales se pueden recuperar a partir de cualquier k símbolos de codificación recibidos exitosamente (es decir, excluyendo aquellos que fueron borrados). 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 cualquier k' de los símbolos de codificación con alta probabilidad, donde k' es apenas ligeramente mayor que k .
Los códigos LT fueron la primera realización práctica de los códigos fuente. Posteriormente se introdujeron códigos Raptor y códigos en línea , que lograron una complejidad de codificación y decodificación de tiempo lineal a través de 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 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] Utilizando un código de borrado de tarifa fija, un receptor al que le falta un símbolo fuente (debido a un error de transmisión) se enfrenta al problema del cobrador de cupones : debe recibir con éxito un símbolo de codificación que aún no tiene. Este problema se vuelve mucho más evidente cuando se utiliza un código de borrado tradicional de corta duración, ya que el archivo debe dividirse en varios bloques, cada uno codificado por separado: el receptor ahora debe recopilar la cantidad requerida de símbolos de codificación faltantes para cada bloque. Usando 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 fuente. (En la práctica, un operador normalmente programa la transmisión durante un período de tiempo fijo en función de las características de la red y los receptores y la confiabilidad de entrega deseada y, por lo tanto, el código fuente se utiliza a una velocidad de código que se determina dinámicamente en el momento en que el archivo está programado para ser transmitido).
Otra aplicación es la del ARQ híbrido en escenarios de multidifusión confiables : 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] tienen 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 codificación como para decodificación. [3] IETF RFC 5053 especifica en detalle un código Raptor sistemático , que se ha adoptado en múltiples estándares más allá del IETF, como dentro del estándar 3GPP MBMS para la entrega de archivos de difusión y servicios de streaming, el estándar DVB-H IPDC para la entrega de servicios IP. a través de redes DVB y DVB-IPTV para brindar servicios de televisión comercial a través de una red IP. Este código se puede utilizar con hasta 8192 símbolos fuente en un bloque fuente y un total de hasta 65536 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 de origen con 1000 símbolos de origen, 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, medidos 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 los datos de origen de tamaño 1 megabyte se pueden recuperar a partir de 1,002 megabytes de datos de codificación.
En IETF RFC 6330 se ha especificado un código Raptor más avanzado con mayor flexibilidad y sobrecarga de recepción mejorada, llamado RaptorQ. El código RaptorQ especificado se puede usar con hasta 56,403 símbolos fuente en un bloque fuente y un total de hasta 16,777,216 símbolos codificados. símbolos generados para un bloque fuente. Este código es capaz de recuperar un bloque fuente de cualquier conjunto de símbolos codificados igual a la cantidad de símbolos fuente en el bloque fuente con alta probabilidad y, en casos excepcionales, de un número ligeramente mayor que la cantidad de símbolos fuente en el bloque fuente. El código RaptorQ es una parte integral de la instanciación de RUTA especificada en ATSC A-331 (ATSC 3.0)
Los códigos de borrado se utilizan en aplicaciones de almacenamiento de datos debido a ahorros masivos en la cantidad de unidades de almacenamiento para un nivel determinado de redundancia y confiabilidad. Los requisitos del diseño del código de borrado para el almacenamiento de datos, particularmente 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 la 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 necesaria ] 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, particularmente cuando falla un nodo y se necesita una reconstrucción del sistema para alcanzar 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 cálculo 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 proyecta que los códigos de fuente reparables [5] aborden los objetivos de diseño de códigos de fuente para sistemas de almacenamiento. Puede encontrar una encuesta detallada sobre los códigos fuente 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 de gran tamaño, como el código RaptorQ especificado en IETF RFC 6330 (que proporciona una protección de datos significativamente mejor que otros sistemas), utilizando un proceso de reparación en segundo plano (que reduce significativamente el tiempo de reparación). requisitos de ancho de banda en comparación con otros sistemas) y el uso de una organización de flujo de datos (que permite un acceso rápido a los datos incluso cuando no todos los símbolos codificados están disponibles).
{{cite web}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ).{{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ).