Procedimiento y dispositivo de decodificación para códigos LDPC, y aparato de comunicación que comprende dicho dispositivo.

Procedimiento de decodificación iterativa de una palabra recibida,

representada por valores de una señal, según un código de matriz de control de paridad, del tipo de paso de mensajes entre dos nodos de variable y dos nodos de control de un grafo bipartito asociado a dicha matriz, caracterizado una etapa de inicialización de por lo menos un mensaje de un nodo de variable, en función de dichos valores, mediante una información representativa de la relación entre la probabilidad de tener el símbolo más probable en la posición correspondiente al nodo de variable y la probabilidad de tener el símbolo actual en dicha posición.

Procedimiento y dispositivo de decodificación para códigos LDPC, y aparato de comunicación que comprende dicho dispositivo.

La presente invención se refiere a un procedimiento y un dispositivo de decodificación, así como a un aparato de comunicación que comprende dicho dispositivo.

La codificación de palabras de información (de una longitud generalmente indicada como K) en palabras de código (de una longitud indicada generalmente como N, con N > K) se utiliza cuando se desea añadir redundancia a las informaciones referidas con el fin de recuperar la totalidad de las informaciones de origen aunque una parte de las mismas sea errónea o se haya perdido, como en el caso de la transmisión de informaciones en un canal con perturbaciones o de su almacenamiento en un soporte sujeto a degradaciones (tales como arañazos en un disco óptico) .

La decodificación llevada a cabo en la recepción (o en la lectura en el caso del almacenamiento) con el fin de recuperar las palabras de información de origen comprende en general una primera fase de corrección de errores, que consiste en recuperar de forma precisa la palabra de código emitida (o almacenada) a partir de la palabra recibida (vocabulario usado también para designar la palabra leída en el caso del almacenamiento) , a pesar de eventuales errores y gracias a la redundancia introducida, y a continuación una fase de "demapping" que consiste en realizar la operación inversa a la efectuada durante la codificación.

En este contexto, se conocen los códigos de matriz de control de paridad con baja densidad, denominados en lo sucesivo códigos LDPC (según la abreviatura de la denominación anglosajona "Low Density Parity Check") , tales como los descritos por ejemplo en el artículo "Low density parity check codes", de R. Gallager en IEEE Trans. Inform. Theor y , vol., IT-8, págs. 21 a 28, 1962.

Estos códigos son particularmente interesantes no solo porque están muy próximos a la capacidad del canal (límite de Shannon) y ofrecen el mejor compromiso posible entre rendimiento y prestaciones (próximos al límite de Gilbert-Varshamov) , sino también porque admiten una decodificación iterativa de tipo paso de mensaje.

Hasta el momento se han propuesto dos algoritmos principales de decodificación de los códigos LDPC, ya sean códigos binarios (para los cuales los símbolos que representan las informaciones son 0 ó 1, es decir, adoptados en el campo de Galois ( () ) o códigos no binarios (para los cuales los símbolos se adoptan en el campo de Galois GF 2

() con ) .

GFqq >2

El primero, propuesto en el artículo citado previamente con el nombre de "probabilistic decoding" se conoce generalmente (y se denomina en lo sucesivo) como decodificación SPA (de "Sum - Product Algorithm") o BP (de "Belief Propagation") . Este algoritmo se califica generalmente como óptimo puesto que la decodificación SPA converge hacia la máxima verosimilitud a condición de que el grafo bipartito asociado al código LDPC no contenga ciclos. En el caso de los códigos LDPC no binarios, este algoritmo es sin embargo inservible en un sistema real de comunicaciones a causa de su muy amplia dinámica, lo cual acarrea una fuerte inestabilidad de los cálculos efectuados. Además, requiere la realización de un número importante de productos, lo cual lo hace complejo, y depende del conocimiento del ruido térmico.

El segundo algoritmo de decodificación, subóptimo, es conocido principalmente con el nombre de MSA (de "Min-Sum Algorithm") . Es menos complejos que el SPA y es independiente del conocimiento del ruido térmico, aunque presenta, en términos de tasa de errores de bit, una pérdida de prestaciones con respecto al SPA que varía generalmente de 0, 25 dB a 1 dB para un canal AWGN (del inglés "Additive White Gaussian Noise" de ruido blanco gaussiano aditivo) , en función del rendimiento, de la irregularidad o de la longitud del código utilizado.

Así, en este contexto, la invención pretende especialmente proponer una solución para la decodificación de los códigos LDPC, en particular no binarios, que combine buenas prestaciones (por ejemplo con respecto al MSA) y una complejidad reducida con respecto al algoritmo óptimo (algoritmo SPA) .

Así, la invención propone un procedimiento de decodificación iterativa de una palabra recibida, representada por valores de una señal, según un código de matriz de control de paridad, del tipo de paso de mensajes entre dos nodos de variable y dos nodos de control de un grafo bipartito asociado a dicha matriz, caracterizado porque comprende una etapa de inicialización de por lo menos un mensaje de un nodo de variable, en función de dichos valores, mediante una información representativa de la relación entre la probabilidad de tener el símbolo más probable en la posición correspondiente al nodo de variable y la probabilidad de tener el símbolo actual en dicha posición.

Por otra parte, se puede prever según este procedimiento que el mismo comprenda por lo menos una de las etapas siguientes:

- determinación de por lo menos un mensaje, referente a un símbolo determinado, de un nodo de control hacia un nodo de variable determinado, como el valor mínimo adoptado, entre las secuencias de símbolos que verifican la

ecuación en el nodo de control utilizando dicho símbolo determinado en el nodo de variable determinado, por el valor máximo de los mensajes recibidos en el nodo de control desde nodos de variable que no sean el nodo de variable determinado y referentes, cada uno de ellos, al símbolo asociado a este otro nodo de variable en la secuencia que verifica la ecuación;

- determinación de los mensajes de un nodo de variable hacia un nodo de control referentes al conjunto de los símbolos de tal manera que el valor mínimo de dichos mensajes sea nulo.

La solución así propuesta (denominada en lo sucesivo MMA de "Min-Max Algorithm") permite obtener buenas prestaciones para una complejidad reducida, tal como se desprenderá a partir de ejemplos de realización presentados posteriormente.

En la práctica, la etapa de inicialización del mensaje de un nodo de variable comprende, por ejemplo, las siguientes etapas:

- para cada símbolo del alfabeto, determinación de la suma de las relaciones de verosimilitud logarítmica binarias referentes a los bits no nulos del símbolo y en la posición correspondiente al nodo de variable y;

- determinación del mínimo de las sumas determinadas;

- resta, de cada suma determinada, del mínimo determinado.

Por otro lado, se puede prever según este procedimiento una etapa de determinación de una información a posteriori referente a un nodo de variable y a un símbolo, como la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable y referentes al símbolo, en cuyo caso el final del procedimiento iterativo se puede determinar de la manera siguiente:

- para cada nodo de variable, determinación del símbolo para el cual la información a posteriori es mínima;

- si la secuencia de los símbolos así determinados para el conjunto de los nodos de variable es una palabra de código, utilización de dicha palabra de código como palabra estimada.

Según un modo de realización de la etapa de determinación de los mensajes de un nodo de variable hacia un nodo de control dado previsto más arriba, el mismo comprende las siguientes etapas:

- para cada símbolo, determinación de la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable procedentes de un nodo de control que no sea el nodo de control dado y referentes al símbolo;

- determinación del mínimo de entre las sumas determinadas;

- para cada símbolo, resta del mínimo determinado, de la suma determinada referente al símbolo.

Para la realización práctica de la etapa de determinación de por lo menos un mensaje de un nodo de control hacia un nodo de variable determinado, el mismo puede comprender, por ejemplo, las siguientes etapas:

- determinación, para cada símbolo, de un valor intermedio igual al valor mínimo adoptado por el valor máximo de mensajes recibidos en el nodo de control desde una parte solamente de los nodos de variable asociados al nodo de control;

- determinación del valor mínimo adoptado por el valor máximo de entre los valores intermedios y los mensajes recibidos de un nodo de variable asociado al nodo de control y que no pertenecen a dicha parte.

De forma más precisa,... [Seguir leyendo]

1. Procedimiento de decodificación iterativa de una palabra recibida, representada por valores de una señal, según un código de matriz de control de paridad, del tipo de paso de mensajes entre dos nodos de variable y dos nodos de control de un grafo bipartito asociado a dicha matriz, caracterizado una etapa de inicialización de por lo menos un mensaje de un nodo de variable, en función de dichos valores, mediante una información representativa de la relación entre la probabilidad de tener el símbolo más probable en la posición correspondiente al nodo de variable y la probabilidad de tener el símbolo actual en dicha posición.

2. Procedimiento de decodificación según la reivindicación 1, que comprende una etapa de determinación de por lo menos un mensaje, referente a un símbolo determinado, de un nodo de control hacia un nodo de variable determinado, como el valor mínimo adoptado, entre las secuencias de símbolos que verifican la ecuación en el nodo de control utilizando dicho símbolo determinado en el nodo de variable determinado, por el valor máximo de los mensajes recibidos en el nodo de control desde nodos de variable que no sean el nodo de variable determinado y referentes, cada uno de ellos, al símbolo asociado a este otro nodo de variable en la secuencia que verifica la ecuación.

3. Procedimiento de decodificación según la reivindicación 1 ó 2, que comprende una etapa de determinación de los mensajes de un nodo de variable hacia un nodo de control referentes al conjunto de los símbolos de tal manera que el valor mínimo de dichos mensajes sea nulo.

4. Procedimiento de decodificación según una de las reivindicaciones 1 a 3, en el cual la etapa de inicialización del mensaje de un nodo de variable comprende las siguientes etapas:

- para cada símbolo del alfabeto, determinación de la suma de las relaciones de verosimilitud logarítmica binarias referentes a los bits no nulos del símbolo y en la posición correspondiente al nodo de variable y;

- determinación del mínimo de las sumas determinadas;

- resta, de cada suma determinada, del mínimo determinado.

5. Procedimiento de decodificación según una de las reivindicaciones 1 a 4, que comprende una etapa de determinación de una información a posteriori referente a un nodo de variable y a un símbolo, como la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable y referentes al símbolo.

6. Procedimiento de decodificación según la reivindicación 5, que comprende las siguientes etapas:

- para cada nodo de variable, determinación del símbolo para el cual la información a posteriori es mínima;

- si la secuencia de los símbolos así determinados para el conjunto de los nodos de variable es una palabra de código, utilización de dicha palabra de código como palabra estimada.

7. Procedimiento de decodificación según una de las reivindicaciones 3 a 6, considerándose las reivindicaciones 4 y 5 en dependencia de la reivindicación 3, en el cual la etapa de determinación de los mensajes de un nodo de variable hacia un nodo de control dado comprende las siguientes etapas:

- para cada símbolo, determinación de la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable procedentes de un nodo de control que no sea el nodo de control dado y referentes al símbolo;

- determinación del mínimo de entre las sumas determinadas;

- para cada símbolo, resta, del mínimo determinado, de la suma determinada referente al símbolo.

8. Procedimiento de decodificación según una de las reivindicaciones 2 a 7, considerándose las reivindicaciones 3 a 7 en dependencia de la reivindicación 2, en el cual la etapa de determinación de por lo menos un mensaje de un nodo de control hacia un nodo de variable determinado comprende las siguientes etapas:

- determinación, para cada símbolo, de un valor intermedio igual al valor mínimo adoptado por el valor máximo de mensajes recibidos en el nodo de control desde una parte solamente de los nodos de variable asociados al nodo de control;

- determinación del valor mínimo adoptado por el valor máximo de entre los valores intermedios y los mensajes recibidos de un nodo de variable asociado al nodo de control y que no pertenecen a dicha parte.

9. Procedimiento de decodificación según una de las reivindicaciones 1 a 8, que comprende una etapa de determinación del mínimo, entre las parejas de dos símbolos que pertenecen al alfabeto del código, del máximo de dos valores asociados respectivamente a los dos símbolos de cada pareja, que comprende las siguientes subetapas:

- determinación de conjuntos que agrupan, cada uno de ellos, los símbolos a los cuales están asociados valores comprendidos en un intervalo determinado;

- selección de conjuntos, de entre los conjuntos determinados, de tal manera que la reunión de los conjuntos seleccionados contiene por lo menos un número predeterminado de símbolos;

- utilización, como máximo entre dos valores, del valor asociado al símbolo comprendido en el conjunto correspondiente al intervalo superior cuando los valores están asociados a símbolos comprendidos en conjuntos seleccionados correspondientes a intervalos distintos;

- determinación por comparación del máximo entre dos valores cuando los valores están asociados a símbolos comprendidos en conjuntos seleccionados correspondientes a un mismo intervalo.

10. Procedimiento de decodificación según una de las reivindicaciones 1 a 9, en el cual el código es un código de alfabeto no binario.

11. Dispositivo de decodificación iterativa de una palabra recibida, representada por valores de una señal, según un código de matriz de control de paridad, del tipo de paso de mensajes entre dos nodos de variable y dos nodos de control de un grafo bipartito asociado a dicha matriz, caracterizado porque comprende medios de inicialización de por lo menos un mensaje de un nodo de variable, en función de dichos valores, mediante una información representativa de la relación entre la probabilidad de tener el símbolo más probable en la posición correspondiente al nodo de variable y la probabilidad de tener el símbolo actual en dicha posición.

12. Dispositivo de decodificación según la reivindicación 11, que comprende medios de determinación de por lo menos un mensaje, referente a un símbolo determinado, de un nodo de control hacia un nodo de variable determinado, como el valor mínimo adoptado, entre las secuencias de símbolos que verifican la ecuación en el nodo de control utilizando dicho símbolo determinado en el nodo de variable determinado, por el valor máximo de los mensajes recibidos en el nodo de control desde nodos de variable que no sean el nodo de variable determinado y referentes, cada uno de ellos, al símbolo asociado a este otro nodo de variable en la secuencia que verifica la ecuación.

13. Dispositivo de decodificación según la reivindicación 11 ó 12, que comprende medios de determinación de los mensajes de un nodo de variable hacia un nodo de control referentes al conjunto de los símbolos de tal manera que el valor mínimo de dichos mensajes sea nulo.

14. Dispositivo de decodificación según una de las reivindicaciones 11 a 13, en el cual los medios de inicialización del mensaje de un nodo de variable comprenden:

- medios para determinar, para cada símbolo del alfabeto, la suma de las relaciones de verosimilitud logarítmica binarias referentes a los bits no nulos del símbolo y en la posición correspondiente al nodo de variable y;

- medios para determinar el mínimo de las sumas determinadas;

- medios para restar, de cada suma determinada, el mínimo determinado.

15. Dispositivo de decodificación según una de las reivindicaciones 11 a 14, que comprende medios de determinación de una información a posteriori referente a un nodo de variable y a un símbolo, como la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable y referentes al símbolo.

16. Dispositivo de decodificación según la reivindicación 15, que comprende:

- medios para determinar, para cada nodo de variable, el símbolo para el cual la información a posteriori es mínima;

- medios para utilizar la secuencia de los símbolos así determinados para el conjunto de los nodos de variable como palabra estimada si dicha secuencia es una palabra de código.

17. Dispositivo de decodificación según una de las reivindicaciones 13 a 16, considerándose las reivindicaciones 14 y 15 en dependencia de la reivindicación 13, en el cual los medios de determinación de los mensajes de un nodo de variable hacia un nodo de control dado comprenden:

- medios para determinar, para cada símbolo, la suma del mensaje inicial referente al símbolo en dicho nodo de variable y del conjunto de los mensajes recibidos en el nodo de variable procedentes de un nodo de control que no sea el nodo de control dado y referentes al símbolo;

- medios para determinar el mínimo de entre las sumas determinadas;

- para cada símbolo, medios para restar el mínimo determinado, de la suma determinada referente al símbolo.

18. Dispositivo de decodificación según una de las reivindicaciones 12 a 17, considerándose las reivindicaciones 13 a 15 en dependencia de la reivindicación 12, en el cual los medios de determinación de por lo menos un mensaje de un nodo de control hacia un nodo de variable determinado comprenden:

- medios para determinar, para cada símbolo, un valor intermedio igual al valor mínimo adoptado por el valor máximo de mensajes recibidos en el nodo de control desde una parte solamente de los nodos de variable asociados al nodo de control;

- medios para determinar el valor mínimo adoptado por el valor máximo de entre los valores intermedios y los mensajes recibidos de un nodo de variable asociado al nodo de control y que no pertenecen a dicha parte.

19. Dispositivo de decodificación según una de las reivindicaciones 11 a 18, en el cual medios para determinar el mínimo, entre las parejas de dos símbolos que pertenecen al alfabeto del código, del máximo de dos valores asociados respectivamente a los dos símbolos de cada pareja, comprenden:

- medios de determinación de conjuntos que agrupan, cada uno de ellos, los símbolos a los cuales están asociados valores comprendidos en un intervalo determinado;

- medios de selección de conjuntos, de entre los conjuntos determinados, de tal manera que la reunión de los conjuntos seleccionados contiene por lo menos un número predeterminado de símbolos;

- medios que utilizan, como máximo entre dos valores, el valor asociado al símbolo comprendido en el conjunto correspondiente al intervalo superior cuando los valores están asociados a símbolos comprendidos en conjuntos seleccionados correspondientes a intervalos distintos;

- medios para determinar por comparación el máximo entre dos valores cuando los valores están asociados a símbolos comprendidos en conjuntos seleccionados correspondientes a un mismo intervalo.

20. Dispositivo de decodificación según una de las reivindicaciones 11 a 19, en el cual el código es un código de alfabeto no binario.

21. Aparato de comunicación que comprende un dispositivo según una de las reivindicaciones 11 a 20.