En informática , los códigos Raptor ( rap id tornado ; [1] ver códigos Tornado ) son la primera clase conocida de códigos fuente con codificación y decodificación de tiempo lineal. Fueron inventados por Amin Shokrollahi en 2000/2001 y se publicaron por primera vez en 2004 como un resumen extendido. Los códigos Raptor son una mejora teórica y práctica significativa sobre los códigos LT , que fueron la primera clase práctica de códigos fuente .
Los códigos Raptor, al igual que los códigos fuente en general, codifican un bloque de datos fuente dado que consiste en un número k de símbolos fuente de igual tamaño en una secuencia potencialmente ilimitada de símbolos de codificación de modo que la recepción de k o más símbolos de codificación permite que el bloque fuente se recupere con alguna probabilidad distinta de cero. La probabilidad de que el bloque fuente pueda recuperarse aumenta con el número de símbolos de codificación recibidos por encima de k, llegando a ser muy cercano a 1, una vez que el número de símbolos de codificación recibidos es solo ligeramente mayor que k . Por ejemplo, con la última generación de códigos Raptor, los códigos RaptorQ, la probabilidad de falla de decodificación cuando se han recibido k símbolos de codificación es menor al 1%, y la probabilidad de falla de decodificación cuando se han recibido k+2 símbolos de codificación es menor a una en un millón. Un símbolo puede tener cualquier tamaño, desde un solo byte hasta cientos o miles de bytes.
Los códigos Raptor pueden ser sistemáticos o no sistemáticos . En el caso sistemático, los símbolos del bloque fuente original, es decir, los símbolos fuente, se incluyen dentro del conjunto de símbolos de codificación. Algunos ejemplos de un código Raptor sistemático son el uso por parte del Proyecto de Asociación de Tercera Generación en la transmisión y multidifusión inalámbrica celular móvil , y también por los estándares DVB-H para la transmisión de datos IP a dispositivos portátiles. [ cita requerida ] Los códigos Raptor utilizados en estos estándares también se definen en IETF RFC 5053.
Los códigos en línea son un ejemplo de un código fuente no sistemático.
La versión más avanzada de Raptor es el código RaptorQ definido en IETF RFC 6330. El código RaptorQ es un código sistemático, se puede implementar de manera que se logre un rendimiento de codificación y decodificación en tiempo lineal, tiene propiedades de recuperación casi óptimas, admite hasta 56.403 símbolos de origen y puede admitir una cantidad esencialmente ilimitada de símbolos de codificación.
El código RaptorQ definido en IETF RFC 6330 se especifica como parte del estándar Next Gen TV ( ATSC 3.0 ) para permitir la transmisión de video de alta calidad (TV móvil robusta) y la entrega eficiente y confiable de archivos de transmisión (transmisión de datos). En particular, el código RaptorQ se especifica en A/331 dentro de ATSC 3.0. [2] Consulte la Lista de estándares ATSC para obtener una lista de las partes del estándar ATSC 3.0. Next Gen TV (ATSC 3.0) va mucho más allá de la TV tradicional para proporcionar una Internet de transmisión que permite servicios de entrega de datos generales.
Los códigos Raptor se forman mediante la concatenación de dos códigos.
Un código de borrado de tasa fija , normalmente con una tasa bastante alta, se aplica como un "precódigo" o "código externo". Este precódigo puede ser en sí mismo una concatenación de múltiples códigos, por ejemplo, en el código estandarizado por 3GPP, un código de verificación de paridad de alta densidad derivado de la secuencia binaria de Gray se concatena con un código de verificación de paridad de baja densidad regular simple . Otra posibilidad sería una concatenación de un código Hamming con un código de verificación de paridad de baja densidad.
El código interno toma el resultado de la operación de precodificación y genera una secuencia de símbolos de codificación. El código interno es una forma de códigos LT . Cada símbolo de codificación es el XOR de un conjunto de símbolos elegidos de forma pseudoaleatoria de la salida del precódigo. La cantidad de símbolos que se combinan mediante XOR para formar un símbolo de salida se elige de forma pseudoaleatoria para cada símbolo de salida de acuerdo con una distribución de probabilidad específica.
Tanto el emisor como el receptor deben conocer esta distribución, así como el mecanismo para generar números pseudoaleatorios para muestrear esta distribución y para elegir los símbolos que se van a combinar mediante la operación XOR. En un enfoque, cada símbolo va acompañado de un identificador que se puede utilizar como semilla para un generador de números pseudoaleatorios para generar esta información, y tanto el emisor como el receptor siguen el mismo proceso.
En el caso de códigos Raptor no sistemáticos, los datos fuente que se van a codificar se utilizan como entrada para la etapa de precodificación.
En el caso de los códigos sistemáticos Raptor, la entrada a la etapa de precodificación se obtiene aplicando primero la operación inversa de codificación que genera los primeros k símbolos de salida a los datos de origen. De este modo, la aplicación de la operación de codificación normal a los símbolos resultantes hace que los símbolos de origen originales se regeneren como los primeros k símbolos de salida del código. Es necesario asegurar que los procesos pseudoaleatorios que generan los primeros k símbolos de salida generen una operación que sea invertible.
Existen dos enfoques posibles para decodificar los códigos Raptor. En un enfoque concatenado, el código interno se decodifica primero, utilizando un algoritmo de propagación de creencias, como el utilizado para los códigos LT. La decodificación tiene éxito si esta operación recupera una cantidad suficiente de símbolos, de modo que el código externo pueda recuperar los símbolos restantes utilizando el algoritmo de decodificación apropiado para ese código.
En un enfoque combinado, las relaciones entre los símbolos definidos por los códigos internos y externos se consideran como un único conjunto combinado de ecuaciones simultáneas que pueden resolverse por los medios habituales, normalmente mediante eliminación gaussiana .
Los códigos Raptor requieren un tiempo O(tamaño del símbolo) para generar un símbolo de codificación a partir de un bloque fuente, y requieren un tiempo O(tamaño del bloque fuente) para recuperar un bloque fuente de al menos k símbolos de codificación.
La sobrecarga es la cantidad de símbolos de codificación adicionales, además del número k de símbolos de origen en el bloque de origen original, que se deben recibir para recuperar completamente el bloque de origen. (Basándose en consideraciones de teoría de la información elemental, no es posible la recuperación completa de un bloque de origen con k símbolos de origen si se reciben menos de k símbolos de codificación). La probabilidad de recuperación es la probabilidad de que el bloque de origen se recupere completamente al recibir una cantidad dada de símbolos de codificación aleatorios generados a partir del bloque de origen.
El código RaptorQ especificado en IETF RFC 6330 tiene el siguiente equilibrio entre probabilidad de recuperación y sobrecarga de recuperación:
Estas afirmaciones son válidas para todo el rango de k admitido en IETF RFC 6330, es decir, k = 1,...,56403. Consulte IETF RFC 6330 para obtener más detalles. [3]
Qualcomm, Inc. ha publicado una declaración de propiedad intelectual para el código Raptor especificado en IETF RFC 5053 y una declaración de propiedad intelectual para el código RaptorQ más avanzado especificado en IETF RFC 6330. Estas declaraciones reflejan el compromiso de licencia que Qualcomm, Inc. ha asumido con respecto al estándar MPEG DASH . El estándar MPEG DASH ha sido implementado por una amplia variedad de empresas, incluidas las empresas miembro del DASH Industry Forum.