PROCEDIMIENTO DE DESCODIFICACION EN PASO DE MENSAJES CON UNA CLASIFICACION DE LOS NODOS SEGUN UNA FIABILIDAD DE VECINAJE.

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

Tipo: Patente Internacional (Tratado de Cooperación de Patentes). Resumen de patente/invención. Número de Solicitud: PCT/EP2007/057644.

Solicitante: COMMISSARIAT A L'ENERGIE ATOMIQUE.

Nacionalidad solicitante: Francia.

Dirección: BREVALEX 3, RUE DU DOCTEUR LANCEREAUX,75008 PARIS.

Inventor/es: KTENAS,DIMITRI, SAVIN,VALENTIN.

Fecha de Publicación: .

Fecha Concesión Europea: 6 de Enero de 2010.

Clasificación Internacional de Patentes:

  • H03M13/11 ELECTRICIDAD.H03 CIRCUITOS ELECTRONICOS BASICOS.H03M CODIFICACION, DECODIFICACION O CONVERSION DE CODIGO, EN GENERAL (por medio de fluidos F15C 4/00; convertidores ópticos analógico/digitales G02F 7/00; codificación, decodificación o conversión de código especialmente adaptada a aplicaciones particulares, ver las subclases apropiadas, p. ej. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; cifrado o descifrado para la criptografía o para otros fines que implican la necesidad de secreto G09C). › H03M 13/00 Codificación, decodificación o conversión de código para detectar o corregir errores; Hipótesis básicas sobre la teoría de codificación; Límites de codificación; Métodos de evaluación de la probabilidad de error; Modelos de canal; Simulación o prueba de códigos (detección o correción de errores para la conversión de código o la conversión analógico/digital, digital/analógica H03M 1/00 - H03M 11/00; especialmente adaptados para los computadores digitales G06F 11/08; para el registro de la información basado en el movimiento relativo entre el soporte de registro y el transductor G11B, p. ej. G11B 20/18; para memorias estáticas G11C). › usando bits de paridad múltiple.

Clasificación PCT:

  • H03M13/11 H03M 13/00 […] › usando bits de paridad múltiple.
PROCEDIMIENTO DE DESCODIFICACION EN PASO DE MENSAJES CON UNA CLASIFICACION DE LOS NODOS SEGUN UNA FIABILIDAD DE VECINAJE.

Fragmento de la descripció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 F2 = {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 F2', y por consiguiente de un alfabeto 2p-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, hnm = 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 = (x1, x2, ..., xN) se obtiene a partir de una palabra de bits de información a = (a1, a2, ..., ak) 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 GT 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 = (y1, y2, ..., yN). 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;

an 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 pna = Pr(xn = a|yn), 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 s2 es la varianza del ruido.

amn representa el mensaje transmitido por la variable n al control minH(n). Por referencia a los turbocódigos, amn 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 an 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,...

 


Reivindicaciones:

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 (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.

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 (fd(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 (fd(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 (Gj), 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 (an) 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 (Iterf), 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 (Tf), 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 amn' 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 amn' 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 cm=+1 y c=dmax+1 si cm=-1 en la que dmax es el grado máximo de los nodos de control en el gráfico bipartito, y en la que cm=+1 / cm=-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.


 

Patentes similares o relacionadas:

Métodos de adaptación de velocidad para códigos LDPC, del 11 de Marzo de 2020, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Método de adaptación de velocidad de producción de un conjunto de bits codificados a partir de un conjunto de bits de información para la transmisión entre […]

Procedimiento de codificación, procedimiento de descodificación, dispositivo de codificación y dispositivo de descodificación para códigos LDPC estructurados, del 11 de Marzo de 2020, de ZTE CORPORATION: Un procedimiento de codificación para códigos de comprobación de paridad de baja densidad estructurados, LDPC, que comprende: determinar una matriz base MbxNb usada […]

Modulación codificada LDPC en combinación con 256QAM y OFDM, del 7 de Agosto de 2019, de Sun Patent Trust: Un método de generación de señal OFDM, Multiplexación por División de Frecuencia Ortogonal, que comprende: un paso de codificación de codificación […]

Modulación codificada LDPC con código BCH externo en combinación con 256QAM, del 7 de Agosto de 2019, de Sun Patent Trust: Una BICM, codificación y modulación intercalada en bits, procedimiento de codificación que comprende: una primera etapa de codificación de codificar […]

Aparato de comunicación inalámbrica y procedimiento de comunicación inalámbrica, del 24 de Julio de 2019, de Panasonic Intellectual Property Management Co., Ltd: Un dispositivo de comunicación inalámbrica que comprende: un generador de unidad de datos de protocolo de capa física, PPDU, adaptado para generar una unidad de datos […]

Intercalador de bits para un sistema de BICM con códigos de QC-LDPC, del 3 de Julio de 2019, de PANASONIC CORPORATION: Un procedimiento de intercalación de bits para intercalar bits de una palabra de código generada en base a un esquema de codificación de comprobación de paridad de baja densidad […]

Diseño de valores de cambio para códigos LDPC cuasi-cíclicos, del 5 de Junio de 2019, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Un transmisor inalámbrico que comprende un sistema de circuitos de procesamiento que funciona para: codificar bits de información usando una […]

Procedimiento y sistema para transmitir señales satelitales y receptor de las mismas, del 22 de Mayo de 2019, de RAI RADIOTELEVISIONE ITALIANA (S.P.A.): Procedimiento para transmitir una señal satelital que comprende una secuencia de datos MPEG-TS de tipo único que consiste en una secuencia […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .