Descodificación de códigos de reacción en cadena por inactivación.

Un procedimiento (300) de descodificación de una secuencia de símbolos (220,

710, 910) de entrada a partir desímbolos (230, 720, 920) de salida recibidos, transportados en forma codificada por un canal de comunicación, siendo laforma codificada de acuerdo a un código de reacción en cadena, comprendiendo el procedimiento:

almacenar una pluralidad de símbolos de salida recibidos, que han sido transportados por el canal de comunicación,teniendo cada símbolo de salida recibido un grado de uno o más, en donde el grado de un símbolo de salida representa elnúmero de símbolos de entrada a los cuales está asociado un símbolo de salida, y siendo el símbolo de salida un símbolode salida de código de reacción en cadena, y siendo tal que un símbolo desconocido, entre los símbolos de entradaasociados al símbolo de salida, puede ser recuperado si son conocidos valores de los otros símbolos de entradaasociados al símbolo de salida;

proporcionar almacenamiento para un estado, para símbolos de entrada, en donde el estado para un símbolo de entradaes un valor que puede tener un valor activo o un valor inactivo;

procesar símbolos de salida en un proceso de reacción en cadena, en en el que los símbolos de entrada son recuperados(316) a partir de símbolos de salida de grado uno, y a los símbolos de salida de grado mayor que uno, que estánasociados a los símbolos de entrada recuperados, se les reduce su grado en consecuencia, generando por ello símbolosde salida adicionales de grado uno, que pueden ser usados para recuperar símbolos de entrada;determinar (317, 311) si el proceso de reacción en cadena se atasca por falta de símbolos de salida de grado uno pararecuperar símbolos de entrada;

modificar (321, 322) un estado para al menos un símbolo de entrada, desde el valor activo al valor inactivo, cuando eldescodificador determina, en la etapa de determinación, que no quedan símbolos de salida de grado uno para larecuperación de símbolos de entrada;

resolver (332) los valores de los símbolos de entrada que tienen un estado igual al valor inactivo, resolviendo un sistemade ecuaciones que representan el código de reacción en cadena; y

usar (334) los valores resueltos para resolver símbolos de entrada adicionales.

Descodificación de códigos de reacción en cadena por inactivación Referencia cruzada a solicitud relacionada La presente solicitud reivindica el beneficio de la Solicitud Provisional Estadounidense Nº 60 / 388.129, titulada “Descodificación de códigos de reacción en cadena mediante la inactivación”, presentada el 11 de junio de 2002, cuyo contenido se incorpora a la presente memoria por referencia, en su totalidad, para todo fin.

Antecedentes de la invención La presente invención se refiere a sistemas y procedimientos para descodificar datos y, más específicamente, a sistemas y procedimientos para descodificar códigos aditivos de información y códigos aditivos de información de múltiples etapas, mencionados en la presente memoria colectivamente como “códigos de reacción en cadena”.

Los códigos de reacción en cadena han sido descritos previamente en las patentes del cesionario, tales como la Patente Estadounidense Nº 6.307.487, titulada “Generador y descodificador de códigos aditivos de información para sistemas de comunicación” (en adelante en la presente memoria, “Luby I”) y la Solicitud de Patente Estadounidense Nº 10 / 032.156 (número de publicación US 2003 / 058958 A1, publicada el 27 de marzo de 2003 y patentada como US 7.068.729 B1) , titulada “Generador y descodificador de código de múltiples etapas para sistemas de comunicación” (en adelante en la presente memoria, “Raptor”) . Según lo descrito en la presente memoria, la descodificación por reacción en cadena es una forma única de corrección anticipada de errores que permite la reconstrucción de datos a partir de un conjunto de datos recibidos de un tamaño dado, sin considerar los paquetes de datos específicos recibidos. Los sistemas de comunicación que emplean códigos de reacción en cadena son capaces de comunicar información mucho más eficazmente, en comparación con los códigos tradicionales de FEC transmitidos mediante un carrusel de datos o protocolos basados en acuses de recibo, tales como los descritos en Luby I o Raptor.

La Fig. 1 ilustra un proceso ejemplar de codificación de datos usando códigos de reacción en cadena, en el cual un símbolo 170 de salida es generado a partir de varios símbolos de entrada. Los símbolos de entrada son indicados como 110 (a) a 110 (f) . En algunas realizaciones la primera etapa del proceso de codificación es la codificación estática, según lo descrito en Raptor. Esta etapa puede producir los símbolos de origen, indicados como 120 (a) a 120 (f) , y 160 (a) a 160 (c) . En algunas realizaciones, la codificación estática puede ser sistemática, de modo que los valores de los símbolos 120 (a) a 120 (f) de origen sean iguales a los de 110 (a) a 110 (f) . En algunas realizaciones, puede no haber ninguna codificación estática, en cuyo caso los símbolos de entrada coinciden con los símbolos de origen.

Una vez que los símbolos de origen han sido creados, los símbolos de salida son generados a partir de los símbolos de origen. En adelante en la presente memoria, un símbolo de salida y un símbolo de entrada son descritos como “asociados” si el valor del símbolo de entrada es usado para obtener el valor del símbolo de salida. La operación matemática que define esta asociación puede ser cualquier operación específica y, en una realización, el valor del símbolo de salida es el resultado de la operación lógica XOR de los valores de algunos de los símbolos de origen. Para cada símbolo de salida, el generador 140 de claves produce una clave, a partir de la cual el peso del símbolo de salida es determinado desde una tabla 150 de pesos. Una vez que el peso W está determinado, se escogen W símbolos de origen aleatorios, o seudo-aleatorios, y el valor del símbolo de salida es calculado como XOR de los valores de estos símbolos de origen. Por ejemplo, en la Figura 1, el peso del símbolo 170 de salida es igual a 3 y su valor está determinado como el XOR de los símbolos 120 (a) , 120 (d) y 160 (b) de origen. De manera correspondiente, el símbolo 170 de salida está asociado a los símbolos 120 (a) , 120 (d) y 160 (b) de origen. En adelante en la presente memoria, el término “grado” es usado como sinónimo de “peso”.

La Fig. 2A ilustra un gráfico de descodificación usado en la descodificación de un código de reacción en cadena. Este gráfico de descodificación consiste en dos conjuntos de símbolos, los símbolos 220 (a) a (i) de origen y los símbolos 230

(a) a (l) de salida. Un símbolo de salida está conectado con un símbolo de origen si los símbolos de origen y de salida están “asociados”, según lo descrito anteriormente.

La Fig. 2B ilustra una matriz de descodificación correspondiente al gráfico de descodificación de la Fig. 2A, que es útil en el proceso de descodificación. La matriz 200 de descodificación tiene tantas filas como símbolos de salida haya, tantas columnas como símbolos de origen haya, y está poblada con entradas “0” y “1”. Un “1” se coloca en la posición (k, j) de la matriz de descodificación si el j-ésimo símbolo de origen está asociado al k-ésimo símbolo de salida.

En un típico proceso de descodificación por reacción en cadena, la descodificación comienza identificando un símbolo O1 de salida asociado a un único símbolo de origen. El término “símbolo de salida de grado uno” se refiere al precitado símbolo de salida asociado a solamente un símbolo de origen. De manera similar, un símbolo de salida asociado a dos símbolos de origen sería denominado un símbolo de salida de “grado dos”. Los símbolos de origen son denominados de manera similar, correspondiente al número de símbolos de salida a los cuales está asociado cada símbolo de origen.

Una vez que está identificado el símbolo O1 de salida de grado uno, el símbolo de origen asociado de O1 es recuperado y es eliminado del gráfico de descodificación. El proceso continúa identificando otro símbolo O2 de salida de grado uno. Por ejemplo, en la situación ilustrada en la Fig. 2, O1 podría ser el símbolo de salida indicado como 230 (a) . Una vez que su símbolo 220 (b) de origen asociado es eliminado del Gráfico de Descodificación, hay tres símbolos de salida de grado uno, a saber, 230 (c) , 230 (d) y 230 (k) .

El proceso continúa hasta que todos los símbolos de origen estén recuperados, o hasta que no haya ningún símbolo de salida de grado uno. Por ejemplo, en la situación de la Fig. 2, la siguiente secuencia de símbolos de salida es escogida para recuperar los correspondientes símbolos de origen:

Símbolo de salida Símbolo de origen recuperado

230 (a) 220 (b)

230 (c) 220 (e)

230 (h) 220 (h)

230 (d) 220 (i)

230 (i) 220 (d)

230 (b) 220 (a)

230 (j) 220 (f)

230 (g) 220 (g)

230 (e) 220 (c)

En este caso, la descodificación es exitosa.

El precedente proceso de descodificación por reacción en cadena encuentra dificultades cuando no se halla ningún símbolo de salida de grado uno. En algunos casos, el proceso de descodificación puede detenerse prematuramente y el descodificador puede indicar un error. Alternativamente, el descodificador puede usar otros algoritmos más complejos, como la eliminación Gaussiana, para completar la descodificación, si es posible. Sin embargo, el tiempo de ejecución de la eliminación Gaussiana puede ser prohibitivamente largo para aplicaciones donde se desea una descodificación rápida, especialmente cuando el número de símbolos de entrada no recuperados, en el momento en que no se hallan más símbolos de salida de grado uno, es grande. Esto llevaría a un algoritmo de descodificación cuyo sobregasto de cálculo es significativamente mayor que el de un descodificador por reacción en cadena, y puede por tanto ser indeseable en ciertas aplicaciones.

Por esta razón, el diseño de sistemas de codificación por reacción en cadena se hace usualmente de manera que garantice que el descodificador no se detenga prematuramente. Este requisito puede imponer condiciones más restrictivas en el diseño del código que las que pueden ser posibles usando un descodificador más complejo. Por ejemplo, puede imponer que el grado medio de un símbolo de salida sea mayor que en otros casos y de ese modo puede llevar a una reducción en las prestaciones del codificador y del descodificador. Más generalmente, este procedimiento de descodificación fuerza que el diseño de la tabla de pesos sea de tal forma como para garantizar el éxito del precitado algoritmo de descodificación con alta probabilidad, y por ello puede imponer restricciones sobre el conjunto de posibles... [Seguir leyendo]

1. Un procedimiento (300) de descodificación de una secuencia de símbolos (220, 710, 910) de entrada a partir de símbolos (230, 720, 920) de salida recibidos, transportados en forma codificada por un canal de comunicación, siendo la forma codificada de acuerdo a un código de reacción en cadena, comprendiendo el procedimiento:

almacenar una pluralidad de símbolos de salida recibidos, que han sido transportados por el canal de comunicación, teniendo cada símbolo de salida recibido un grado de uno o más, en donde el grado de un símbolo de salida representa el número de símbolos de entrada a los cuales está asociado un símbolo de salida, y siendo el símbolo de salida un símbolo de salida de código de reacción en cadena, y siendo tal que un símbolo desconocido, entre los símbolos de entrada asociados al símbolo de salida, puede ser recuperado si son conocidos valores de los otros símbolos de entrada asociados al símbolo de salida;

proporcionar almacenamiento para un estado, para símbolos de entrada, en donde el estado para un símbolo de entrada es un valor que puede tener un valor activo o un valor inactivo;

procesar símbolos de salida en un proceso de reacción en cadena, en en el que los símbolos de entrada son recuperados (316) a partir de símbolos de salida de grado uno, y a los símbolos de salida de grado mayor que uno, que están asociados a los símbolos de entrada recuperados, se les reduce su grado en consecuencia, generando por ello símbolos de salida adicionales de grado uno, que pueden ser usados para recuperar símbolos de entrada;

determinar (317, 311) si el proceso de reacción en cadena se atasca por falta de símbolos de salida de grado uno para recuperar símbolos de entrada;

modificar (321, 322) un estado para al menos un símbolo de entrada, desde el valor activo al valor inactivo, cuando el descodificador determina, en la etapa de determinación, que no quedan símbolos de salida de grado uno para la recuperación de símbolos de entrada;

resolver (332) los valores de los símbolos de entrada que tienen un estado igual al valor inactivo, resolviendo un sistema de ecuaciones que representan el código de reacción en cadena; y

usar (334) los valores resueltos para resolver símbolos de entrada adicionales.

2. El procedimiento de la reivindicación 1, en el cual la resolución de valores de símbolos de entrada inactivados, a partir de símbolos de salida asociados, es realizada usando la eliminación Gaussiana.

3. El procedimiento de la reivindicación 1, en el cual un valor de un símbolo de salida es el resultado de la operación lógica XOR sobre un cierto número de símbolos de entrada, y el número de símbolos de entrada es el grado del símbolo de salida.

4. El procedimiento de la reivindicación 1, en el cual la modificación del estado comprende:

seleccionar (321) un símbolo de entrada activo asociado al mayor número de símbolos de salida; y

modificar (322) un estado del símbolo de entrada activo seleccionado.

5. El procedimiento de la reivindicación 1, en el cual la modificación comprende:

seleccionar (321) un símbolo de entrada activo, de acuerdo a una selección al azar, entre los símbolos de entrada asociados a símbolos de salida de grado dos; y

modificar (322) un estado para el símbolo de entrada seleccionado.

6. El procedimiento de la reivindicación 5, que comprende adicionalmente repetir la modificación (312, 322) del estado, y luego continuar el procesamiento para resolver (332) los valores de los símbolos de entrada que tengan un estado igual al valor inactivo.

7. El procedimiento de la reivindicación 1, que comprende adicionalmente cambiar un estado, para al menos un símbolo de entrada inactivo cualquiera, al valor activo si el número de símbolos de entrada potencialmente recuperables no supera un número predefinido, y cambiar un estado, para otro símbolo de entrada activo, a un valor inactivo.

8. El procedimiento de la reivindicación 1, en el cual la recuperación de los símbolos de entrada inactivados a partir de símbolos de salida asociados comprende recuperar los valores de todos los símbolos de entrada inactivados antes de recuperar símbolos de entrada no inactivados.

9. El procedimiento de cualquiera de las reivindicaciones 1 a 8, teniendo el código de reacción en cadena una pluralidad

de símbolos de salida de múltiples etapas y dicha pluralidad de símbolos de entrada, siendo dichos símbolos de entrada descodificados a partir de dichos símbolos de salida de múltiples etapas, transportados por dicho canal de comunicación, comprendiendo cada uno de los símbolos de salida de múltiples etapas dicho símbolo de salida, o bien un símbolo de comprobación, en donde un símbolo de comprobación se obtiene por codificación estática de símbolos de entada, en donde cada uno de los símbolos de salida de múltiples etapas está asociado a uno o más símbolos de entrada, siendo denominados los símbolos de salida de múltiples etapas, asociados a uno o más símbolos de entrada, símbolos de salida de múltiples etapas de grado uno o más, en el que al menos un símbolo de salida de múltiples etapas está asociado a al menos dos símbolos de entrada, siendo denominados los símbolos de salida de múltiples etapas, asociados a dos o más símbolos de entrada, símbolos de salida de múltiples etapas de grado dos o más.

10. Un producto de programa de ordenador que comprende un medio de almacenamiento legible por ordenador, que comprende instrucciones para hacer que un ordenador lleve a cabo el procedimiento de cualquiera de las reivindicaciones 1 a 9.

11. Un descodificador (1110) configurado para descodificar símbolos (220, 710, 910) de entrada, según un proceso de descodificación por reacción en cadena, usando los símbolos (230, 720, 920) de salida recibidos, asociados a los símbolos de entrada, en donde el descodificador comprende un procesador que, al ejecutar códigos de instrucción para descodificar los símbolos de entrada, usando los símbolos de salida, realiza operaciones que comprenden:

determinar (317, 311) si el proceso de reacción en cadena se atasca por falta de símbolos de salida de grado uno para recuperar símbolos de entrada;

modificar (321, 322) un estado para al menos un símbolo de entrada, desde el valor activo al valor inactivo, cuando el

descodificador determina, en la etapa de determinación, que no quedan símbolos de salida de grado uno para la recuperación de símbolos de entrada;

resolver (332) los valores de los símbolos de entrada que tienen un estado igual al valor inactivo, resolviendo un sistema de ecuaciones que representan el código de reacción en cadena; y

usar (334) los valores resueltos para resolver símbolos de entrada adicionales.

12. El descodificador de la reivindicación 11, en el cual la resolución (332) es realizada por un descodificador por inactivación, configurado para reducir un grado medio asociado a la pluralidad de símbolos de salida.