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

Un procedimiento de descodificación de símbolos (220, 710, 910) de origen que fueron codificados usando uncódigo por reacción en cadena,

en el cual la descodificación de un símbolo de origen comprende determinar un valorde símbolo de origen para ese símbolo de origen, entre un conjunto de símbolos (230, 720, 920) de salida, estandocada símbolo de salida asociado a uno o más de la pluralidad de símbolos de origen, en cuanto a que un valor delsímbolo de salida es una función de los valores de uno o más de la pluralidad de símbolos de origen, en el que ungrado de un símbolo de salida es el número de símbolos de origen no descodificados de los cuales depende esesímbolo de salida, y a los cuales está por tanto asociado, comprendiendo el procedimiento:

en un proceso de descodificación por reacción en cadena, identificar un símbolo de salida que tenga un grado de uno ydescodificar (316) dicho símbolo de origen asociado al símbolo de salida identificado, determinando así un valor de esedicho símbolo de origen;

si no queda ningún símbolo de salida de grado uno,

seleccionar (321) uno entre la pluralidad de símbolos de origen que esté asociado a un símbolo de salida asociado degrado dos o superior, en donde la selección de uno entre la pluralidad de símbolos de origen comprende seleccionar unsímbolo de origen para obtener el mayor número de símbolos de salida grado restante uno, en donde un gradorestante de un símbolo de salida es igual al número de símbolos de origen a los que está asociado, excluyendo lossímbolos de origen seleccionados;

desactivar (322) el símbolo de origen seleccionado y, si la desactivación del símbolo de origen seleccionado da comoresultado al menos un símbolo de salida de grado restante uno, declarar (324) como recuperable el símbolo de origenasociado a dicho al menos un símbolo de salida de grado restante uno;

repetir (325) las etapas de selección (321) y desactivación (322);

determinar (332) valores para los símbolos de origen desactivados; y

recuperar (334) los símbolos de origen declarados como recuperables usando los valores determinados para lossímbolos de origen desactivados.

Descodificación de códigos de reacción en cadena mediante inactivación Antecedentes de la invención La presente invención se refiere a sistemas y procedimientos de descodificación de datos y, más específicamente, a sistemas y procedimientos de descodificación de 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, 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 las mismas, 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 se 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 de reacción en cadena, 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 tablas de pesos.

Lo que se necesita, por lo tanto, es un nuevo algoritmo de descodificación que ofrezca ventajas de cálculo similares a las del descodificador por reacción en cadena, y que sea capaz de continuar descodificando incluso si no se halla ningún símbolo de salida de grado uno en alguna etapa de la descodificación.

Sumario La presente invención proporciona un procedimiento, un sistema y un producto de programa de ordenador para descodificar un código... [Seguir leyendo]

1. Un procedimiento de descodificación de símbolos (220, 710, 910) de origen que fueron codificados usando un código por reacción en cadena, en el cual la descodificación de un símbolo de origen comprende determinar un valor de símbolo de origen para ese símbolo de origen, entre un conjunto de símbolos (230, 720, 920) de salida, estando cada símbolo de salida asociado a uno o más de la pluralidad de símbolos de origen, en cuanto a que un valor del símbolo de salida es una función de los valores de uno o más de la pluralidad de símbolos de origen, en el que un grado de un símbolo de salida es el número de símbolos de origen no descodificados de los cuales depende ese símbolo de salida, y a los cuales está por tanto asociado, comprendiendo el procedimiento:

en un proceso de descodificación por reacción en cadena, identificar un símbolo de salida que tenga un grado de uno y descodificar (316) dicho símbolo de origen asociado al símbolo de salida identificado, determinando así un valor de ese dicho símbolo de origen;

si no queda ningún símbolo de salida de grado uno,

seleccionar (321) uno entre la pluralidad de símbolos de origen que esté asociado a un símbolo de salida asociado de grado dos o superior, en donde la selección de uno entre la pluralidad de símbolos de origen comprende seleccionar un símbolo de origen para obtener el mayor número de símbolos de salida grado restante uno, en donde un grado restante de un símbolo de salida es igual al número de símbolos de origen a los que está asociado, excluyendo los símbolos de origen seleccionados;

desactivar (322) el símbolo de origen seleccionado y, si la desactivación del símbolo de origen seleccionado da como resultado al menos un símbolo de salida de grado restante uno, declarar (324) como recuperable el símbolo de origen asociado a dicho al menos un símbolo de salida de grado restante uno;

repetir (325) las etapas de selección (321) y desactivación (322) ;

determinar (332) valores para los símbolos de origen desactivados; y

recuperar (334) los símbolos de origen declarados como recuperables usando los valores determinados para los símbolos de origen desactivados.

2. 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 la reivindicación 1.

3. Un sistema de descodificación de símbolos de origen que fueron codificados usando un código de reacción en cadena, en el cual la descodificación de un símbolo de origen comprende determinar un valor de símbolo de origen para ese símbolo de origen, entre un conjunto de símbolos (230, 720, 920) de salida, estando cada símbolo de salida asociado a uno o más de la pluralidad de símbolos de origen, en cuanto a que un valor del símbolo de salida es una función de valores de uno o más de la pluralidad de símbolos de origen, en el que un grado de un símbolo de salida es el número de símbolos de origen no descodificados de los cuales depende el símbolo de salida y a los cuales está por tanto asociado, comprendiendo el sistema:

medios para llevar a cabo las etapas de la reivindicación 1.