Procedimiento de descodificación iterativa del tipo de paso de mensajes para descodificar un código corrector de errores susceptible de representación mediante un gráfico bipartito que comprende una pluralidad de nodos de variable y una pluralidad de nodos de control,

caracterizado porque, en cada iteración de una pluralidad de iteraciones de descodificación:

- se efectúa una clasificación (720) de los nodos de variable o bien de los nodos de control en función de los grados de fiabilidad respectivos de las informaciones de descodificación disponibles en los vecinajes (Vn(d), Vm(d)) de estos nodos, de modo que un nodo que posee un grado de fiabilidad elevado está clasificado por delante de un nodo que posee un bajo grado de fiabilidad;

- los nodos así clasificados pasan (725), cada uno de ellos, al menos un mensaje (amn, ßmn) a un nodo adyacente, en el orden definido por la citada clasificación

Procedimiento de descodificación en paso de mensajes con una clasificación de los nodos según una fiabilidad de vecinaje.

Campo técnico

La presente invención se refiere a la decodificación de códigos correctores de errores en el campo de las telecomunicaciones y del registro de datos. De manera más precisa, la invención está relacionada con un procedimiento de descodificación iterativo en paso de mensajes de códigos correctores de errores susceptibles de una representación mediante gráfico bipartito, tales como los códigos LDPC (Low Density Parity Check) o los turbocódigos.

Estado de la técnica anterior

Los códigos correctores de errores susceptibles de representación mediante gráfico bipartito abarcan una gran diversidad de códigos, en particular los códigos LDPC, inicialmente descritos por R. Gallager en su artículo titulado "Low density parity check codes", publicado en IEEE Trans. Inform. Theory, vol. IT-8, páginas 21-28, 1962, cuyas interesantes propiedades han sido redescubiertas recientemente, y los turbocódigos introducidos por C. Berrou y cols., en su artículo fundador "Near optimum error correcting coding and decoding": turbocodes, aparecido en IEEE Trans. Inform. Theory, vol. 44, núm. 10, páginas 1261-1271, 1996.

Se denomina gráfico bipartito un gráfico no orientado, cuyo conjunto de nodos está constituido por dos subconjuntos disyuntos tales como dos nodos cualesquiera de un mismo subconjunto que no están unidos entre sí por una arista del gráfico.

Algunos códigos correctores de errores son susceptibles de una representación mediante gráfico bipartito. El gráfico está dividido en un primer subconjunto de nodos asociados a los símbolos que constituyen una palabra de código, y un segundo subconjunto de nodos asociados a las restricciones del código, típicamente a los controles de paridad. Un gráfico bipartito asociado a un grupo de restricciones, se denomina también gráfico de Tanner.

Los símbolos de la palabra de código son, en general, elementos del cuerpo de Galois F₂ = {0,1}, dicho de otro modo de los bits, pero pueden ser, de forma más general, elementos de un cuerpo de característica 2 cualquiera F₂', y por consiguiente de un alfabeto 2^p-ario. En lo que sigue, nos limitaremos sin pérdida de generalidad al caso en que p = 1, es decir, a los códigos binarios.

Los códigos susceptibles de representación mediante gráfico bipartito, pueden ser descodificados por medio de una descodificación iterativa en paso de mensajes, conocida también como de tipo MP (Message Passing) o BP (Belief Propagation). Se encontrará una descripción genérica de este método de descodificación en la tesis de N. Wiberg, titulada "Codes and decoding on general graphs", 1996. La decodificación iterativa de tipo MP es, de hecho, una generalización de algoritmos bien conocidos en el campo de la descodificación, a saber el algoritmo "forward-backward" utilizado para los turbocódigos, y el algoritmo de Gallager para los códigos LDPC.

En un intento de simplificación, recurriremos en lo que sigue al principio de descodificación iterativa por paso de mensajes en el marco de un código LDPC. Consideraremos un código lineal {K,N} donde K es la dimensión del código que representa el número de bits de información, y N es la longitud del código, que representa el número de bits codificados. M = N - K corresponde al número de bits de paridad o, de manera equivalente, al número de restricciones de paridad.

En la Figura 1 se ha ilustrado el gráfico de Tanner de un código lineal {K,N}. Se ha hecho figurar, a la izquierda del gráfico, los nodos correspondientes a los bits del código, denominados también nodos de tipo "variable" o incluso de manera más simple "variables", y a la derecha, los nodos correspondientes a los controles de paridad, denominados también nodos de tipo "control", o incluso de manera más simple "controles". La matriz de incidencia del gráfico corresponde a la matriz de paridad del código que es de dimensión M x N. Así, el gráfico bipartito comprende N nodos de tipo "variable" y M nodos de tipo "control", estando un nodo n de variable ligado a un nodo m de control si, y solo si, h_nm = 1. Por ejemplo, el gráfico de la Figura 1 corresponde a un código (10,5) que posee la matriz de paridad siguiente:

Se recuerda, de manera general, que un código lineal está definido por una matriz generadora G cuyos elementos son valores lineales binarios, y que una palabra de código x = (x₁, x₂, ..., x_N) se obtiene a partir de una palabra de bits de información a = (a₁, a₂, ..., a_k) por medio de:

Puesto que todas las palabras de código verifican los controles de paridad, se tiene la relación:

donde se ha indicado mediante G^T la transformada de la matriz G.

La palabra de código x es transmitida por un canal de comunicación, o registrada en un soporte de datos. Con la recepción o la lectura del soporte, se recupera una versión ruidosa de x, a saber y = (y₁, y₂, ..., y_N). La operación de descodificación consiste en hallar x y con ello a, a partir de la observación y.

Convendremos las notaciones siguientes antes de describir el principio de descodificación iterativa en paso de mensajes:

H(n) designa el conjunto de controles ligados a la variable n en el gráfico bipartito, o dicho de otro modo, el conjunto de nodos adyacentes al nodo n;

H(m) es el conjunto de variables asociadas al control m en el gráfico bipartito, o dicho de otro modo, el conjunto de nodos adyacentes al nodo m;

a_n representa la información a priori concerniente a la variable n del gráfico bipartito, o dicho de otro modo, la información a priori concerniente al n^ésimo bit de la palabra de código. Esta información tiene en cuenta la señal recibida y las características del canal de transmisión. La misma constituye la entrada del descodificador, y es suministrada generalmente por el demodulador en forma de valores flexibles, es decir en términos de probabilidades:

donde p_n^a = Pr(x_n = a|y_n), ain{0,1},

es decir, más cómodamente en forma de una relación logarítmica de probabilidades o LLR:

De ese modo, mediante un ruido BBCG (ruido blanco centrado gaussiano) y una modulación BPSK, el demodulador calcula simplemente:

donde s² es la varianza del ruido.

a_mn representa el mensaje transmitido por la variable n al control minH(n). Por referencia a los turbocódigos, a_mn se conoce incluso como información extrínseca;

ß_nm representa, de manera simétrica, el mensaje transmitido por el control m a la variable ninH(m). El mismo está calificado igualmente como información extrínseca;

hat{a}_n representa la información a posteriori relativa a la variable n; la misma tiene en cuenta a la vez la información a priori a_n y los mensajes ß_nm recibidos por la variable n desde sus controles adyacentes durante la descodificación;

overline{a}_n es el valor rígido correspondiente al valor flexible hat{a}_n,...

1. Procedimiento de descodificación iterativa del tipo de paso de mensajes para descodificar un código corrector de errores susceptible de representación mediante un gráfico bipartito que comprende una pluralidad de nodos de variable y una pluralidad de nodos de control, caracterizado porque, en cada iteración de una pluralidad de iteraciones de descodificación:

- se efectúa una clasificación (720) de los nodos de variable o bien de los nodos de control en función de los grados de fiabilidad respectivos de las informaciones de descodificación disponibles en los vecinajes (V_n^(d), V_m^(d)) de estos nodos, de modo que un nodo que posee un grado de fiabilidad elevado está clasificado por delante de un nodo que posee un bajo grado de fiabilidad;

- los nodos así clasificados pasan (725), cada uno de ellos, al menos un mensaje (a_mn, ß_mn) a un nodo adyacente, en el orden definido por la citada clasificación.

2. Procedimiento de descodificación según la reivindicación 1, caracterizado porque la citada clasificación comprende, para cada nodo a clasificar, el cálculo de una medición de fiabilidad (f_d(n), (tilde{f}_d(m)) de las informaciones presentes, enviadas o recibidas por los nodos situados a menos de una distancia (d) predeterminada de estos últimos en el seno del gráfico bipartito, y la selección de los valores de las mediciones así obtenidos.

3. Procedimiento de descodificación según la reivindicación 2, caracterizado porque, para cada iteración de la citada pluralidad, opera secuencialmente sobre los nodos clasificados en el orden definido por la citada clasificación, y porque, para cada nodo clasificado (825), se calculan los mensajes con destino a los nodos que le son adyacentes (835) y, para cada uno de los citados nodos adyacentes, los mensajes con destino a los propios nodos adyacentes a éste (830).

4. Procedimiento de descodificación según la reivindicación 1, caracterizado porque la citada clasificación comprende, para cada nodo a clasificar, el cálculo de una medición de fiabilidad (f_d(n), (tilde{f}_d(m)) de las informaciones presentes, enviadas o recibidas por los nodos situados a menos de una distancia (d) predeterminada de este nodo en el seno del gráfico bipartito, y porque se agrupan los nodos por intervalos de valores de la citada medición.

5. Procedimiento de descodificación según la reivindicación 4, caracterizado porque la medición de fiabilidad es en valores enteros, y porque, para cada uno de los citados valores enteros, se almacenan en una zona de memoria que se les ha asociado, los índices de los nodos cuya medición de fiabilidad sea igual a ese valor.

6. Procedimiento de descodificación según la reivindicación 4 ó 5, caracterizado porque, para cada iteración de la citada pluralidad, se opera secuencialmente sobre los grupos de nodos en el orden definido por la citada clasificación, y porque, para cada grupo de nodos (G_j), se calculan los mensajes con destino a los nodos que le son adyacentes (935) y, para cada uno de los citados nodos adyacentes, los mensajes con destino a los propios nodos adyacentes a estos últimos (930).

7. Procedimiento de descodificación según una de las reivindicaciones anteriores, caracterizado porque cada iteración de la citada pluralidad comprende, además, para cada nodo de variable de dicho gráfico bipartito, una etapa de cálculo (740, 840, 940) de una información a posteriori (hat{a}_n) en función de una información a priori (a_n) ya presente en ese nodo y de los mensajes recibidos (ß_mn) por ese nodo provenientes de los nodos de control adyacentes.

8. Procedimiento de descodificación según la reivindicación 7, caracterizado porque la etapa de cálculo de información a posteriori va seguida de una etapa de decisión (750, 850, 950) sobre el valor rígido (hat{a}_n) de la citada variable.

9. Procedimiento de descodificación según la reivindicación 8, caracterizado porque se comprueba (760, 860, 960) si los valores rígidos de las variables así obtenidos, verifican los controles de paridad asociados a todos los nodos de control del gráfico, y porque, en caso afirmativo, se proporciona como palabra descodificada la palabra constituida por los citados valores rígidos.

10. Procedimiento de descodificación según una de las reivindicaciones anteriores, caracterizado porque la clasificación se interrumpe después de un número de iteraciones de descodificación predeterminado (Iter_f), prosiguiendo el procedimiento de descodificación a continuación sus iteraciones de descodificación en ausencia de la citada clasificación de los citados nodos de variables o bien de los citados nodos de control.

11. Procedimiento de descodificación según la reivindicación 7, caracterizado porque la clasificación se interrumpe si el mínimo, en valor absoluto, de las diferencias entre los valores a posteriori y los valores a priori de las citadas variables, es superior a un valor de umbral predeterminado (T_f), prosiguiendo a continuación el procedimiento de descodificación sus iteraciones de descodificación en ausencia de dicha clasificación de los citados nodos de variables o bien de los citados nodos de control.

12. Procedimiento de descodificación según una de las reivindicaciones anteriores, caracterizado porque el citado código corrector de errores es un turbocódigo.

13. Procedimiento de descodificación según una de las reivindicaciones 1 a 11, caracterizado porque el citado código corrector de errores es un código LDPC (K,N) representado por un gráfico bipartito de N nodos de variable y M = N-K nodos de control.

14. Procedimiento de descodificación según la reivindicación 13, caracterizado porque el mensaje ß_mn de un nodo de control de índice min{1,..,M} a un nodo de variable de índice nin{1,..,N}, se calcula mediante:

en la que a_mn' designa el mensaje del nodo de variable de índice n' al nodo de control de índice m, H(m) el conjunto de los nodos de variable adyacentes al nodo de control de índice m, sgn(x)=1 si x es positivo y sgn (x)=-1 si no lo es, y 41

15. Procedimiento de descodificación según la reivindicación 13, caracterizado porque el mensaje ß_mn de un nodo de control de índice min{1,..,M} a un nodo de variable de índice nin{1,..,N}, se calcula mediante:

en la que a_mn' designa el mensaje del nodo de variable de índice n' al nodo de control de índice m, H(m) el conjunto de los nodos de variable adyacentes al nodo de control de índice m, sgn(x)=1 si x es positiva, y sgn(x)=-1 si no lo es.

16. Procedimiento de descodificación según las reivindicaciones 5 y 15, caracterizado porque la clasificación recae sobre los nodos de control, porque la citada distancia predeterminada es igual a 2, y porque la medición de fiabilidad de un nodo de control de índice m se calcula mediante:

en la que H(m) designa el conjunto de los nodos de variable adyacentes al nodo de control de índice m, H(n) el conjunto de los nodos de control adyacentes al nodo de variable de índice n, Card(.) designa el cardinal de un conjunto, con c=0 si c_m=+1 y c=d_max+1 si c_m=-1 en la que d_max es el grado máximo de los nodos de control en el gráfico bipartito, y en la que c_m=+1 / c_m=-1 significan respectivamente que el control de paridad ha sido verificado/ no ha sido verificado, para el nodo de control de índice m.

17. Programa de ordenador que comprende medios lógicos adaptados para llevar a cabo las etapas del procedimiento de descodificación según una de las reivindicaciones que anteceden, cuando es ejecutado por un ordenador.