En informática , los códigos Raptor ( rap id tor nado ; [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 ampliado. Los códigos Raptor son una mejora teórica y práctica significativa con respecto a 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 determinado que consta de 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 cualquier k o más símbolos de codificación permite que el bloque fuente recuperarse con alguna probabilidad distinta de cero. La probabilidad de que el bloque fuente pueda recuperarse aumenta cuando el número de símbolos de codificación recibidos por encima de k se acerca mucho a 1, una vez que el número de símbolos de codificación recibidos es sólo 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 inferior al 1%, y la probabilidad de falla de decodificación cuando se han recibido k+2 símbolos de codificación es menor. que uno entre un millón. (Consulte la sección Probabilidad de recuperación y gastos generales a continuación para obtener más información sobre esto). Un símbolo puede tener cualquier tamaño, desde un solo byte hasta cientos o miles de bytes.
Los códigos de aves rapaces 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 transmisión y multidifusión inalámbrica de celulares móviles , y también por los estándares DVB-H para transmisión de datos IP a dispositivos portátiles (ver enlaces externos). 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 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 de tiempo lineal y tiene propiedades de recuperación casi óptimas (consulte Probabilidad de recuperación y sección general a continuación para obtener más detalles), admite hasta 56,403 símbolos de origen y puede admitir un número esencialmente ilimitado 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 en streaming de alta calidad (TV móvil robusta) y la entrega eficiente y confiable de archivos de transmisión (difusión de datos). En particular, el código RaptorQ se especifica en A/331: Señalización, entrega, sincronización y protección contra errores dentro de ATSC 3.0 (consulte la Lista de estándares ATSC para obtener una lista de las partes estándar de ATSC 3.0). Next Gen TV (ATSC 3.0) va mucho más allá de la televisión tradicional para brindar una transmisión de Internet que permite servicios generales de entrega de datos.
Los códigos Raptor están formados por la concatenación de dos códigos.
Un código de borrado de tarifa fija , normalmente con una tarifa bastante alta, se aplica como '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 regular simple de baja densidad . 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 pseudoaleatoriamente de la salida del código previo. El número de símbolos que se combinan mediante XOR para formar un símbolo de salida se elige pseudoaleatoriamente para cada símbolo de salida de acuerdo con una distribución de probabilidad específica.
Tanto el remitente como el receptor deben conocer esta distribución, así como el mecanismo para generar números pseudoaleatorios para muestrear esta distribución y elegir los símbolos a los que se aplicará XOR. En un enfoque, cada símbolo va acompañado de un identificador que puede usarse como semilla para un generador de números pseudoaleatorios para generar esta información, y tanto el remitente como el receptor siguen el mismo proceso.
En el caso de códigos Raptor no sistemáticos, los datos fuente a codificar se utilizan como entrada para la etapa de precodificación.
En el caso de códigos Raptor sistemáticos, la entrada a la etapa de precodificación se obtiene aplicando primero la inversa de la operación de codificación que genera los primeros k símbolos de salida a los datos fuente. Por lo tanto, aplicar la operación de codificación normal a los símbolos resultantes hace que los símbolos fuente originales se regeneren como los primeros k símbolos de salida del código. Es necesario garantizar que los procesos pseudoaleatorios que generan los primeros k símbolos de salida generen una operación que sea invertible.
Son posibles dos enfoques para decodificar códigos Raptor. En un enfoque concatenado, el código interno se decodifica primero, utilizando un algoritmo de propagación de creencias, como se utiliza 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 usando 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 tiempo O (tamaño del símbolo) para generar un símbolo de codificación a partir de un bloque fuente, y requieren tiempo O (tamaño del bloque fuente) para recuperar un bloque fuente de al menos k símbolos de codificación.
La sobrecarga es cuántos símbolos de codificación adicionales más allá del número k de símbolos fuente en el bloque fuente original deben recibirse para recuperar completamente el bloque fuente. (Según consideraciones elementales de la teoría de la información, la recuperación completa de un bloque fuente con k símbolos fuente no es posible si se reciben menos de k símbolos de codificación). La probabilidad de recuperación es la probabilidad de que el bloque fuente se recupere completamente al recibir un número determinado de símbolos de codificación aleatoria generados a partir del bloque fuente.
El código RaptorQ especificado en IETF RFC 6330 tiene el siguiente equilibrio entre probabilidad de recuperación y gastos generales 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.
Qualcomm, Inc. ha publicado una declaración de derechos de propiedad intelectual para el código Raptor especificado en IETF RFC 5053 y una declaración de derechos 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 a el estándar MPEG DASH . El estándar MPEG DASH ha sido implementado por una amplia variedad de empresas, incluidas las empresas miembros del DASH Industry Forum.