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

Un procedimiento de descodificación de símbolos (220, 710, 910) de origen a partir de símbolos (230,

720, 920) desalida codificados por reacción en cadena, en el cual los símbolos de salida son generados en un codificador por reacciónen cadena obtenido a partir de los símbolos de origen, en el cual un grado de un símbolo de salida es el número desímbolos de origen no descodificados asociados a dicho símbolo de salida, comprendiendo el procedimiento:

(i) recibir un primer conjunto de símbolos de salida;

(ii) recuperar símbolos de origen a partir de los símbolos de salida de grado uno contenidos en el primer conjunto desímbolos de salida;

(iia) determinar que ningún símbolo de salida dentro del código de reacción en cadena está asociado a solamente unsímbolo de origen;

(iii) desactivar un símbolo de origen asociado a un símbolo de salida de grado dos o mayor, reduciendo por ello en uno elgrado de cualquier símbolo de salida asociado a un símbolo de origen desactivado, en el que (iii) la desactivación delsímbolo de origen seleccionado produce un símbolo de origen desactivado y uno o más símbolos de origen recuperables,en donde cada símbolo de origen recuperable está asociado a un símbolo de salida de grado uno, donde el grado estádeterminado según lo especificado anteriormente, pero considerando el símbolo de origen desactivado comodescodificado;

(iv) si un símbolo de origen está asociado a un símbolo de salida de grado uno, declarar que el símbolo de origen esrecuperable;

(v) repetir las etapas (iii) y (iv) si queda cualquier símbolo de origen asociado a un símbolo de salida de grado dos o más;y

(vi) descodificar los símbolos de origen que hayan sido desactivados y descodificar símbolos de origen adicionales nodescodificados, declarados como recuperables a partir de símbolos de salida de grado reducido, reducido por lossímbolos de origen desactivados descodificados; y

(vii) solicitar un segundo conjunto de símbolos de salida si se determina que no todos los símbolos de origen han sidorecuperados.

Descodificación de códigos de reacción en cadena por inactivación 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 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 el 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 con 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 con 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 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.

SumarioLa presente invención... [Seguir leyendo]

1. Un procedimiento de descodificación de símbolos (220, 710, 910) de origen a partir de símbolos (230, 720, 920) de salida codificados por reacción en cadena, en el cual los símbolos de salida son generados en un codificador por reacción en cadena obtenido a partir de los símbolos de origen, en el cual un grado de un símbolo de salida es el número de símbolos de origen no descodificados asociados a dicho símbolo de salida, comprendiendo el procedimiento:

(i) recibir un primer conjunto de símbolos de salida;

(ii) recuperar símbolos de origen a partir de los símbolos de salida de grado uno contenidos en el primer conjunto de símbolos de salida;

(iia) determinar que ningún símbolo de salida dentro del código de reacción en cadena está asociado a solamente un símbolo de origen;

(iii) desactivar un símbolo de origen asociado a un símbolo de salida de grado dos o mayor, reduciendo por ello en uno el grado de cualquier símbolo de salida asociado a un símbolo de origen desactivado, en el que (iii) la desactivación del símbolo de origen seleccionado produce un símbolo de origen desactivado y uno o más símbolos de origen recuperables, en donde cada símbolo de origen recuperable está asociado a un símbolo de salida de grado uno, donde el grado está determinado según lo especificado anteriormente, pero considerando el símbolo de origen desactivado como descodificado;

(iv) si un símbolo de origen está asociado a un símbolo de salida de grado uno, declarar que el símbolo de origen es recuperable;

(v) repetir las etapas (iii) y (iv) si queda cualquier símbolo de origen asociado a un símbolo de salida de grado dos o más; y

(vi) descodificar los símbolos de origen que hayan sido desactivados y descodificar símbolos de origen adicionales no descodificados, declarados como recuperables a partir de símbolos de salida de grado reducido, reducido por los símbolos de origen desactivados descodificados; y

(vii) solicitar un segundo conjunto de símbolos de salida si se determina que no todos los símbolos de origen han sido recuperados.

2. El procedimiento de la reivindicación 1, en el cual el procedimiento es para descodificar símbolos de salida de múltiples etapas, 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 en el que un símbolo de comprobación es obtenido por codificación estática de símbolos de entrada, en en el que 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 superior, 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 superior; y

la etapa (ii) recupera símbolos de origen a partir de los símbolos de salida contenidos en el primer conjunto de símbolos de salida de múltiples etapas.

3. El procedimiento de la reivindicación 2, que comprende adicionalmente:

recuperar símbolos de origen usando los símbolos de comprobación en el primer conjunto de símbolos de salida de múltiples etapas.

4. 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 3.

5. Un descodificador para descodificar símbolos (220, 710, 910, 1010) de origen a partir de símbolos (230, 720, 920) de salida codificados por reacción en cadena, en el cual un grado de un símbolo de salida es el número de símbolos de origen no descodificados asociados a ese símbolo de salida, comprendiendo el descodificador medios para:

(i) recibir un primer conjunto de símbolos de salida;

(ii) recuperar símbolos de origen a partir de los símbolos de salida de grado uno contenidos en el primer conjunto de

símbolos de salida;

(iia) determinar que ningún símbolo de salida dentro del código de reacción en cadena está asociado a solamente un símbolo de origen;

(iii) desactivar un símbolo de origen asociado a un símbolo de salida de grado dos o mayor, reduciendo por ello en uno el grado de cualquier símbolo de salida asociado a un símbolo de origen desactivado, en donde (iii) la desactivación del símbolo de origen seleccionado produce un símbolo de origen desactivado y uno o más símbolos de origen recuperables, en donde cada símbolo de origen recuperable está asociado a un símbolo de salida de grado uno, donde el grado está determinado según lo especificado anteriormente, pero considerando el símbolo de origen desactivado como descodificado;

(iv) si un símbolo de origen está asociado a un símbolo de salida de grado uno, declarar que el símbolo de origen es recuperable;

(v) repetir las etapas (iii) y (iv) si queda cualquier símbolo de origen asociado a un símbolo de salida de grado dos o más; y

(vi) descodificar los símbolos de origen que hayan sido desactivados y descodificar símbolos de origen adicionales no descodificados, declarados como recuperables a partir de símbolos de salida de grado reducido, reducido por los símbolos de origen desactivados descodificados; y

(vii) solicitar un segundo conjunto de símbolos de salida si se determina que no todos los símbolos de origen han sido recuperados.

6. El descodificador de la reivindicación 5, en el cual los medios están adicionalmente adaptados para descodificar símbolos de salida de múltiples etapas, 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, estando 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 entrada, 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 superior, 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 superior; y

la etapa (ii) recupera símbolos de origen a partir de los símbolos de salida contenidos en el primer conjunto de símbolos de salida de múltiples etapas.

7. El descodificador de la reivindicación 6, en el cual los medios están adicionalmente adaptados para:

recuperar símbolos de origen usando los símbolos de comprobación en el primer conjunto de símbolos de salida de múltiples etapas.