Código fuente


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 dado de símbolos de origen, de modo que los símbolos de origen originales pueden idealmente ser recuperado de cualquier subconjunto de los símbolos de codificación de tamaño igual o ligeramente mayor que el número de símbolos de origen. 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 cualquier k símbolos de codificación recibidos con éxito (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 un poco más grande que k .

Los códigos LT fueron la primera realización práctica de códigos fuente. Los códigos Raptor y los códigos en línea se introdujeron posteriormente, y logran una complejidad de codificación y descodificació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 una tasa de código fija no se puede determinar 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 tasa fija, un receptor al que le falta un símbolo de fuente (debido a un error de transmisión) se enfrenta al problema del recolector 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 usa un código de borrado tradicional de corta longitud, ya que el archivo debe dividirse en varios bloques, cada uno codificado por separado: el receptor ahora debe recopilar el número requerido de símbolos de codificación faltantes para cada bloque. Usando un código fuente, es suficiente que un receptor recupere cualquiersubconjunto de símbolos de codificación de tamaño ligeramente mayor que el conjunto de símbolos de origen. (En la práctica, un operador suele programar la transmisión para un período fijo de tiempo 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 usa a una tasa de código que se determina dinámicamente en el momento en que el archivo está programado para ser difundido.)

Otra aplicación es la ARQ híbrida en escenarios de multidifusión fiables : la información de paridad que solicita un receptor puede ser potencialmente útil para todos los receptores del grupo de multidifusión.