Procedimiento y sistema para transmitir y recibir información usando códigos de reacción en cadena.

Un procedimiento de recepción de datos transmitidos desde un origen a un destino por un canal de comunicaciónpor paquetes,

estando los datos inicialmente representados como un conjunto ordenado de símbolos de entrada querepresentan un fichero de entrada, en donde cada uno de los símbolos de entrada es un símbolo de un alfabeto deentrada y cada uno de los símbolos de entrada representa una secuencia de bits en una posición 5 específica en elfichero de entrada, en donde el fichero de entrada es de tamaño conocido, o de tamaño desconocido, tal como unfichero tomado desde una salida de un origen de flujo, comprendiendo el procedimiento:

a) recibir una pluralidad de paquetes desde el canal de comunicación por paquetes;

b) extraer símbolos de salida desde la pluralidad de paquetes;

c) determinar, para al menos algunos de los símbolos de salida recibidos a descodificar, una clave, I, asociada a cadasímbolo de salida, siendo la clave un miembro de un alfabeto de claves, en donde el número de posibles miembros delalfabeto de claves es mucho mayor que el número de símbolos de entrada en el conjunto ordenado de símbolos deentrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida que seangeneralmente independientes entre sí;

d) para cada símbolo de salida recibido para ser descodificado, determinar un peso, W(I), para ese símbolo de salida,usando la clave I de ese símbolo de salida, en donde los pesos son enteros positivos que varían sobre la pluralidad declaves y son mayores que uno para al menos algunas claves en el alfabeto de claves;

e) determinar W(I) símbolos de entrada asociados para cada símbolo de salida a descodificar, usando la clave I de esesímbolo de salida;

f) determinar si han sido recibidos suficientes símbolos de salida para descodificar símbolos de entrada cualesquiera; y

g) descodificar símbolos de entrada que puedan ser descodificados a partir de los símbolos de salida que han sidorecibidos, teniendo en cuenta los W(I) símbolos de entrada asociados para cada símbolo de salida, y una funciónpredeterminada usada para generar el símbolo de salida a partir de sus W(I) símbolos de entrada asociados, de modoque el fichero de entrada pueda ser descodificado a partir de un número de símbolos de salida igual a, o levementemayor que, el número de símbolos de entrada que representan el fichero de entrada, suponiendo que los símbolos deentrada y los símbolos de salida representan el mismo número de bits de datos.

Procedimiento y sistema para transmitir y recibir información usando códigos de reacción en cadena Antecedentes de la invención La presente invención se refiere a la codificación y descodificación de datos en sistemas de comunicación y, más específicamente, a sistemas de comunicación que codifican y descodifican datos para tener en cuenta errores y brechas en los datos comunicados, y para utilizar eficazmente los datos comunicados que emanan desde más de un origen.

La transmisión de ficheros entre un remitente y un destinatario por un canal de comunicaciones ha sido tema de mucha bibliografía. Preferiblemente, un destinatario desea recibir una copia exacta de los datos transmitidos por un canal por un remitente, con cierto nivel de certeza. Allí donde el canal no tiene fidelidad perfecta (lo que abarca la mayoría de todos los sistemas físicamente realizables) , una preocupación es cómo tratar los datos perdidos o desfigurados en la transmisión. Los datos perdidos (borrados) son a menudo más fáciles de tratar que los datos desfigurados (errores) , porque el destinatario no siempre puede decir cuándo los datos desfigurados son datos recibidos con errores. Muchos códigos de corrección de errores han sido desarrollados para corregir borrados (los llamados “códigos de borrado”) y /

o errores (“códigos correctores de errores” o “ECC”) . Habitualmente, el código específico usado se escoge en base a alguna información acerca de las infidelidades del canal a través del cual se están transmitiendo los datos y la naturaleza de los datos que se están transmitiendo. Por ejemplo, allí donde se conoce que el canal tiene largos periodos de infidelidad, un código de errores de ráfaga podría ser el más adecuado para esa aplicación. Allí donde solamente se esperan errores breves e infrecuentes, un código de paridad sencilla podría ser lo mejor.

La transmisión de ficheros entre múltiples remitentes y / o múltiples receptores por un canal de comunicaciones también ha sido tema de mucha bibliografía. Habitualmente, la transmisión de ficheros desde múltiples remitentes requiere la coordinación entre los múltiples remitentes para permitir que los remitentes minimicen la duplicación de esfuerzos. En un típico sistema de múltiples remitentes que envían un fichero a un receptor, si los remitentes no coordinan qué datos transmitirán y cuándo, sino que, en cambio, simplemente envían segmentos del fichero, es probable que un receptor reciba muchos segmentos duplicados inservibles. De manera similar, allí donde distintos receptores se incorporan a una transmisión desde un remitente en distintos momentos en el tiempo, una preocupación es cómo asegurar que todos los datos que reciben los receptores desde el remitente sean útiles. Por ejemplo, supongamos que el remitente está transmitiendo continuamente datos acerca del mismo fichero. Si el remitente solamente envía segmentos del fichero original y se pierden algunos segmentos, es probable que un receptor reciba muchos segmentos duplicados inservibles antes de recibir una copia de cada segmento en el fichero.

Otra consideración al seleccionar un código es el protocolo usado para la transmisión. En el caso de la intrared global de redes conocida como “Internet” (con “I” mayúscula) , se usa un protocolo de paquetes para el transporte de datos. Ese protocolo se llama el Protocolo de Internet o “IP”, para abreviar. Cuando un fichero, u otro bloque de datos, ha de ser transmitido por una red del IP, se divide en símbolos de entrada de igual tamaño y los símbolos de entrada se colocan en paquetes consecutivos. Al estar basado en paquetes, un esquema de codificación orientado a paquetes podría ser adecuado. El “tamaño” de un símbolo de entrada puede ser medido en bits, ya sea que el símbolo de entrada esté o no efectivamente dividido en un flujo de bits, donde un símbolo de entrada tiene un tamaño de M bits cuando el símbolo de entrada se selecciona entre un alfabeto de 2M símbolos.

El Protocolo de Control de Transporte (“TCP”) es un esquema de control de paquetes punto a punto de uso común, que tiene un mecanismo de acuse de recibo. El TCP es bueno para las comunicaciones de uno a uno, donde tanto el remitente como el destinatario acuerdan cuándo tendrá lugar y se recibirá la transmisión, y ambos acuerdan cuáles transmisores y receptores se usarán. Sin embargo, el TCP a menudo no es adecuado para comunicaciones de uno a muchos o de muchos a muchos, o allí donde el remitente y el destinatario determinan independientemente cuándo y dónde transmitirán o recibirán datos.

Al usar el TCP, un remitente transmite paquetes ordenados y el destinatario acusa recibo de cada paquete. Si se pierde un paquete, no se enviará ningún acuse de recibo al remitente y el remitente reenviará el paquete. La pérdida de paquetes tiene un cierto número de causas. En Internet, la pérdida de paquetes a menudo ocurre porque la congestión esporádica causa que el mecanismo de almacenamiento temporal en un encaminador colme su capacidad, forzándolo a descartar paquetes entrantes. Con protocolos tales como TCP / IP, el paradigma de acuse de recibo permite que los paquetes se pierdan sin fallo total, dado que los paquetes perdidos pueden ser simplemente retransmitidos, bien en respuesta a una falta de acuse de recibo o bien en respuesta a una solicitud explícita del destinatario. En cualquier caso, un protocolo de acuse de recibo requiere un canal de retorno desde el destinatario al remitente.

Aunque los protocolos basados en acuse de recibo son generalmente adecuados para muchas aplicaciones y, de hecho, se usan extensamente por la Internet actual, son ineficaces y, a veces, completamente inviables para ciertas aplicaciones. En particular, los protocolos basados en acuse de recibo responden mediocremente en redes con altas

latencias, altas tasas de pérdida de paquetes, altas y bajas no coordinadas de destinatarios y / o ancho de banda sumamente asimétrico. La alta latencia se da allí donde los acuses de recibo se toman un largo tiempo para viajar desde el destinatario de regreso al remitente. La alta latencia puede dar como resultado que el tiempo global antes de una retransmisión sea prohibitivamente largo. Las altas tasas de pérdida de paquetes también causan problemas allí donde varias retransmisiones del mismo paquete pueden dejar de llegar, lo que conduce a un largo retardo para obtener el último, o los pocos últimos, paquetes sin suerte.

Las “altas y bajas no coordinadas de destinatarios” se refieren a la situación donde cada destinatario puede incorporarse a, y abandonar, una sesión de transmisión en marcha, según su propio criterio. Esta situación es típica en Internet, los servicios de próxima generación tales como el “vídeo a petición” y otros servicios a ser ofrecidos por los proveedores de red en el futuro. En el típico sistema, si un destinatario se incorpora a, y abandona, una transmisión en marcha sin la coordinación de los remitentes, el destinatario probablemente percibirá una pérdida de un gran número de paquetes, con patrones de pérdidas ampliamente dispares percibidos por los distintos destinatarios.

El ancho de banda asimétrico se refiere a la situación donde un trayecto inverso de datos desde el destinatario al remitente (el canal de retorno) está menos disponible, o es más costoso, que el trayecto directo. El ancho de banda asimétrico puede hacer que sea prohibitivamente lento y / o caro para el destinatario acusar recibo de paquetes frecuentemente y los acuses infrecuentes de recibo pueden nuevamente introducir retardos.

Además, los protocolos basados en acuses de recibo no se adaptan bien para la difusión, donde un remitente está enviando simultáneamente un fichero a múltiples usuarios. Por ejemplo, supongamos que un remitente está difundiendo un fichero a múltiples destinatarios por un canal por satélite. Cada destinatario puede experimentar un patrón distinto de pérdida de paquetes. Los protocolos que dependen de datos de acuse de recibo (ya sea positivo o negativo) para el suministro fiable del fichero requieren un canal de retorno desde cada destinatario al remitente, y esto puede ser prohibitivamente caro de proporcionar. Además, esto requiere un remitente complejo y potente, para ser capaz de gestionar debidamente todos los datos de acuse de recibo enviados desde los destinatarios. Otro inconveniente es que si distintos destinatarios pierden distintos conjuntos de paquetes, la redifusión de paquetes perdidos solamente por unos pocos de los destinatarios causa la recepción de paquetes duplicados inservibles por parte de otros destinatarios. Otra situación... [Seguir leyendo]

1. Un procedimiento de recepción de datos transmitidos desde un origen a un destino por un canal de comunicación por paquetes, estando los datos inicialmente representados como un conjunto ordenado de símbolos de entrada que representan un fichero de entrada, en donde cada uno de los símbolos de entrada es un símbolo de un alfabeto de entrada y cada uno de los símbolos de entrada representa una secuencia de bits en una posición específica en el fichero de entrada, en donde el fichero de entrada es de tamaño conocido, o de tamaño desconocido, tal como un fichero tomado desde una salida de un origen de flujo, comprendiendo el procedimiento:

a) recibir una pluralidad de paquetes desde el canal de comunicación por paquetes;

b) extraer símbolos de salida desde la pluralidad de paquetes;

c) determinar, para al menos algunos de los símbolos de salida recibidos a descodificar, una clave, I, asociada a cada símbolo de salida, siendo la clave un miembro de un alfabeto de claves, en donde el número de posibles miembros del alfabeto de claves es mucho mayor que el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida que sean generalmente independientes entre sí;

d) para cada símbolo de salida recibido para ser descodificado, determinar un peso, W (I) , para ese símbolo de salida, usando la clave I de ese símbolo de salida, en donde los pesos son enteros positivos que varían sobre la pluralidad de claves y son mayores que uno para al menos algunas claves en el alfabeto de claves;

e) determinar W (I) símbolos de entrada asociados para cada símbolo de salida a descodificar, usando la clave I de ese símbolo de salida;

f) determinar si han sido recibidos suficientes símbolos de salida para descodificar símbolos de entrada cualesquiera; y

g) descodificar símbolos de entrada que puedan ser descodificados a partir de los símbolos de salida que han sido recibidos, teniendo en cuenta los W (I) símbolos de entrada asociados para cada símbolo de salida, y una función predeterminada usada para generar el símbolo de salida a partir de sus W (I) símbolos de entrada asociados, de modo que el fichero de entrada pueda ser descodificado a partir de un número de símbolos de salida igual a, o levemente mayor que, el número de símbolos de entrada que representan el fichero de entrada, suponiendo que los símbolos de entrada y los símbolos de salida representan el mismo número de bits de datos.

2. El procedimiento de la reivindicación 1, en el cual el procesamiento de cada símbolo de salida recibido incluye determinar una función F (I) de valor para ese símbolo de salida, en el cual el símbolo de salida es la función F (I) de valor de los símbolos de entrada asociados y la función de valor es usada en la descodificación de los símbolos de entrada.

3. El procedimiento de la reivindicación 1, en el cual cada símbolo de salida es un O exclusivo (XOR) de sus correspondientes símbolos de entrada asociados.

4. El procedimiento de la reivindicación 1, en el cual algunos de los símbolos de salida son recibidos desde un primer origen y en el cual algunos de los símbolos de salida son recibidos desde un segundo origen.

5. El procedimiento de la reivindicación 1, que comprende:

almacenar los símbolos de salida en un almacén temporal de símbolos de salida que, para cada símbolo de salida recibido, genera una indicación de los símbolos de entrada asociados al símbolo de salida; y

almacenar la indicación en el almacén temporal de símbolos de salida.

6. El procedimiento de la reivindicación 1, que comprende adicionalmente:

almacenar los símbolos de salida en un almacén temporal de símbolos de salida que, para cada símbolo de salida recibido, incluye un valor B (I) del símbolo de salida, el número W (I) de símbolos de entrada asociados para ese símbolo de salida, y las posiciones de los símbolos de entrada asociados en el fichero de entrada;

para cada símbolo de salida, OS, con un peso de uno y que no esté indicado como un símbolo de salida consumido, realizar las etapas de:

1) calcular un valor de símbolo de entrada para una posición de símbolo de entrada correspondiente al OS;

2) identificar los símbolos de salida conectados en la tabla de símbolos de salida, en donde un símbolo de salida conectado es un símbolo de salida que es una función del símbolo de entrada calculado en base al OS;

3) recalcular los símbolos de salida conectados para que sean independientes del símbolo de entrada calculado en base al OS;

4) decrementar en uno los pesos de los símbolos de salida recalculados; y

5) indicar OS como un símbolo de salida consumido.

7. Un sistema para descodificar símbolos de salida recibidos mediante un canal de comunicaciones, representando inicialmente los símbolos de salida, generados a partir de un conjunto ordenado de símbolos de entrada, un fichero de entrada en el cual cada uno de los símbolos de entrada es un símbolo de un alfabeto de entrada, y cada uno de los símbolos de entrada representa una secuencia de bits en una posición específica en el fichero de entrada, en donde el fichero de entrada es de tamaño conocido, o de tamaño desconocido, tal como un fichero tomado desde una salida de un origen de flujo, comprendiendo el sistema:

un regenerador de claves que, para al menos algunos de los símbolos de salida recibidos a descodificar, regenera una clave, I, para ese símbolo de salida, en donde las claves son miembros de un alfabeto de claves, en donde el número de posibles miembros del alfabeto de claves es mucho mayor que el número de símbolos de entrada en el conjunto ordenado de símbolos de entrada, de modo que pueda ser generado un número efectivamente ilimitado de símbolos de salida que sean generalmente independientes entre sí;

un asociador acoplado al regenerador de claves que, para los símbolos de salida a descodificar, determina una lista, AL (I) , de símbolos asociados de entrada, asociados a ese símbolo de salida, según una función de I, siendo designado el número de miembros de AL (I) como el peso, W (I) , del símbolo de salida, y en donde los valores de W (I) son enteros positivos que varían sobre la pluralidad de claves y son mayores que uno para al menos algunas claves en el alfabeto de claves;

un módulo que determina si han sido recibidos suficientes símbolos de salida para descodificar símbolos de entrada cualesquiera; y

un descodificador, acoplado para recibir los símbolos de salida y acoplado al asociador, que descodifica símbolos de entrada que pueden ser descodificados a partir de la información recibida, teniendo en cuenta los W (I) símbolos de entrada asociados para cada símbolo de salida, y una función predeterminada usada para generar el símbolo de salida a partir de sus W (I) símbolos de entrada asociados, de modo que el fichero de entrada pueda ser descodificado a partir de un cierto número de símbolos de salida, igual a, o levemente mayor que, el número de símbolos de entrada que representan el fichero de entrada, suponiendo que los símbolos de entrada y los símbolos de salida representan el mismo número de bits de datos.

8. El sistema de la reivindicación 7, en el cual el descodificador está configurado para determinar una función F (I) de valor para cada símbolo de salida a descodificar, en el cual la función F (I) de valor puede variar.

9. El sistema de la reivindicación 7, en el cual cada símbolo de salida es un O exclusivo (XOR) de sus correspondientes símbolos de entrada asociados.

10. El sistema de la reivindicación 7, en el cual algunos de los símbolos de salida son recibidos desde un primer origen y en el cual algunos de los símbolos de salida son recibidos desde un segundo origen.

11. El sistema de la reivindicación 7, que comprende adicionalmente un almacén temporal de símbolos de salida para almacenar los símbolos de salida y, para cada símbolo de salida recibido, una indicación de los símbolos de entrada asociados al símbolo de salida.