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

Un descodificador para descodificar un código de reacción en cadena,

con una pluralidad de símbolos (230, 720, 920) de salida y una pluralidad de símbolos (220, 710, 910, 1010) de origen, en el cual cada símbolo de salida está asociado a uno o más símbolos de origen, y siendo los códigos de reacción en cadena tales que un símbolo de origen puede ser descodificado a partir de un símbolo de salida de grado uno, y la descodificación de un símbolo de origen reduce los grados de los símbolos de salida que están asociados a ese símbolo de origen descodificado, y 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 origen, comprendiendo cada uno de los símbolos de salida de múltiples etapas ya sea dicho símbolo de salida o bien un símbolo de comprobación, 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 origen, denominándose los símbolos de salida de múltiples etapas, asociados a uno o más símbolos de origen, 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 origen, denominándose los símbolos de salida de múltiples etapas, asociados a dos o más símbolos de origen, símbolos de salida de múltiples etapas de grado dos o superior, y en el que al menos un símbolo de origen está marcado como activo, comprendiendo el descodificador:

(0) medios para determinar que ningún símbolo de salida de múltiples etapas dentro del código de reacción en cadena está asociado a solamente un símbolo de origen,

(i) medios para seleccionar uno de los símbolos de origen activos asociados a un símbolo de salida de múltiples etapas de grado dos o superior;

(ii) medios para desactivar el símbolo de origen seleccionado, asociado a un símbolo de salida de múltiples etapas de grado dos o superior, en el que (ii) el medio para desactivar el símbolo de origen seleccionado produce un símbolo de origen desactivado y uno o más símbolos de origen recuperables, en el que cada símbolo de origen recuperable está asociado a un símbolo de salida de múltiples etapas de grado uno, donde el grado está determinado según lo especificado anteriormente, pero considerando el símbolo de origen desactivado como descodificado;

(iii) medios para recuperar los valores de uno o más símbolos de origen desactivados; y

(iv) medios para determinar, en base a los valores recuperados de los símbolos de origen desactivados, los valores de uno o más símbolos de origen recuperables.

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 US2003/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 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 sistemas... [Seguir leyendo]

1. Un descodificador para descodificar un código de reacción en cadena, con una pluralidad de símbolos (230, 720, 920) de salida y una pluralidad de símbolos (220, 710, 910, 1010) de origen, en el cual cada símbolo de salida está asociado a uno o más símbolos de origen, y siendo los códigos de reacción en cadena tales que un símbolo de origen puede ser descodificado a partir de un símbolo de salida de grado uno, y la descodificación de un símbolo de origen reduce los grados de los símbolos de salida que están asociados a ese símbolo de origen descodificado, y 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 origen, comprendiendo cada uno de los símbolos de salida de múltiples etapas ya sea dicho símbolo de salida o bien un símbolo de comprobación, 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 origen, denominándose los símbolos de salida de múltiples etapas, asociados a uno o más símbolos de origen, 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 origen, denominándose los símbolos de salida de múltiples etapas, asociados a dos o más símbolos de origen, símbolos de salida de múltiples etapas de grado dos o superior, y en el que al menos un símbolo de origen está marcado como activo, comprendiendo el descodificador:

(0) medios para determinar que ningún símbolo de salida de múltiples etapas dentro del código de reacción en cadena está asociado a solamente un símbolo de origen,

(i) medios para seleccionar uno de los símbolos de origen activos asociados a un símbolo de salida de múltiples etapas de grado dos o superior;

(ii) medios para desactivar el símbolo de origen seleccionado, asociado a un símbolo de salida de múltiples etapas de grado dos o superior, en el que (ii) el medio para desactivar el símbolo de origen seleccionado produce un símbolo de origen desactivado y uno o más símbolos de origen recuperables, en el que cada símbolo de origen recuperable está asociado a un símbolo de salida de múltiples etapas de grado uno, donde el grado está determinado según lo especificado anteriormente, pero considerando el símbolo de origen desactivado como descodificado;

(iii) medios para recuperar los valores de uno o más símbolos de origen desactivados; y

(iv) medios para determinar, en base a los valores recuperados de los símbolos de origen desactivados, los valores de uno o más símbolos de origen recuperables.

2. El descodificador de la reivindicación 1, que comprende adicionalmente medios para repetir (i) a (ii) si algunos símbolos de origen, asociados a un símbolo de salida de múltiples etapas de grado dos o superior, permanecen en el código de reacción en cadena.

3. El descodificador de la reivindicación 1, que comprende adicionalmente medios para repetir (i) a (ii) una o más veces, para producir uno o más símbolos de origen desactivados y uno o más símbolos de origen recuperables.

4. El descodificador de la reivindicación 1, en el cual (iii) los medios para recuperar los valores de uno o más de los símbolos de origen desactivados están adaptados para recuperar los valores de todos los símbolos de origen desactivados.

5. El descodificador de la reivindicación 1, en el cual (i) los medios para seleccionar uno de los símbolos de origen activos están adaptados para seleccionar uno de los símbolos de origen activos, que esté asociado a un símbolo de salida de múltiples etapas de grado dos o superior, comprendiendo el símbolo de salida de múltiples etapas dos o más símbolos de comprobación.

6. El descodificador de la reivindicación 1, en el cual (i) los medios para seleccionar uno de los símbolos de origen activos están adaptados para seleccionar uno de los símbolos de origen activos, que esté asociado al mayor número de símbolos de salida de múltiples etapas.

7. El descodificador de la reivindicación 1, en el cual (i) los medios para seleccionar uno de los símbolos de origen activos están adaptados para seleccionar aleatoriamente un símbolo de origen activo entre un grupo de símbolos de origen activos, cada uno de los cuales está asociado a un símbolo de salida de múltiples etapas de grado dos o superior.

8. El descodificador de la reivindicación 1, en el cual (i) los medios para seleccionar uno de los símbolos de origen activos están adaptados para:

(a) identificar un símbolo de origen activo;

(b) determinar el número de símbolos de origen activos que son potencialmente recuperables si es desactivado el símbolo

de origen activo identificado; y

(c) si el número de símbolos de origen recuperables no supera un número predefinido, repetir (a) y (b) para otro símbolo de origen activo.

9. El descodificador de la reivindicación 3, que comprende adicionalmente:

medios para reactivar el símbolo de origen desactivado si el número de símbolos de origen potencialmente recuperables no supera un número predefinido; y

medios para seleccionar otro símbolo de origen activo.

10. El descodificador de la reivindicación 1, en el cual los medios para seleccionar uno de los símbolos de origen activos están adaptados para:

identificar un símbolo de origen que esté asociado a un símbolo de salida de múltiples etapas, que esté a su vez asociado a un número predefinido de símbolos de origen activos,

en el cual los medios para desactivar el símbolo de origen seleccionado están adaptados para desactivar todos menos uno de los símbolos de origen activos, asociados al símbolo de salida de múltiples etapas identificado, y en el cual el símbolo de origen activo restante comprende un símbolo de origen no desactivado.

11. El descodificador de la reivindicación 10, en el cual el símbolo de origen seleccionado está asociado al menor número de símbolos de salida de múltiples etapas.

12. El descodificador de la reivindicación 1, en el cual (i) los medios para seleccionar uno de los símbolos de origen activos están adaptados para seleccionar un símbolo de origen activo, asociado a un primer símbolo de salida de múltiples etapas, en el que el primer símbolo de salida de múltiples etapas está asociado a un primer conjunto de dos símbolos de origen activos.

13. El descodificador de la reivindicación 12, en el cual al menos uno del primer conjunto de dos símbolos de origen está asociado a un segundo símbolo de salida de múltiples etapas, estando asociado el segundo símbolo de salida de múltiples etapas a un segundo conjunto de dos símbolos de origen activos.

14. El descodificador de la reivindicación 13, en el cual al menos uno entre el segundo conjunto de dos símbolos de origen

está asociado a un tercer símbolo de salida de múltiples etapas, estando asociado el tercer símbolo de salida de múltiples etapas a un tercer conjunto de dos símbolos de origen activos.

15. El descodificador de la reivindicación 1, en el cual los símbolos de comprobación son generados de acuerdo a un código LDPC.