Método para decodificar un código lineal sobre un anillo R, incluyendo el método:

obtener una palabra de recepción; una etapa de procesado de baja densidad para reducir la densidad de elementos cuyo valor es uno de tal manera que el número de elementos que tienen el valor de uno es menor que un número predeterminado, para una primera matriz de comprobación del código lineal, incluyéndose dicha primera matriz de comprobación en la palabra de recepción; y una etapa de decodificación para decodificar la palabra de recepción a través de un algoritmo de suma producto usando una matriz de comprobación nueva cuya densidad se ha reducido a través de la etapa de procesado de baja densidad; en el que la etapa de procesado de baja densidad incluye: fijar una variable n a un valor inicial, funcionando n como criterio para extracción de filas; una etapa de cálculo de combinación lineal para calcular todas las combinaciones lineales de filas de la primera matriz de comprobación; una etapa de generación de matrices de comprobación para extraer un subconjunto de vectores de peso inferior con el fin de formar un espacio complementario de entre un conjunto de vectores obtenido mediante la combinación lineal calculada a través de la etapa de cálculo de combinación lineal y generar la matriz de comprobación nueva incluyendo todos los vectores del subconjunto de vectores, como elementos de fila, comprendiendo dicha extracción extraer, del conjunto de vectores formado mediante combinación lineal, cualquier combinación lineal que tiene un peso menor que o igual a n; actualizar el valor de n sumando 1; y una etapa de determinación para determinar si el rango de la primera matriz de comprobación concuerda o no con el rango de la matriz de comprobación nueva, y, en caso negativo, volver a y repetir la etapa de generación de matrices de comprobación con el valor actualizado de n; y en el que la etapa de obtención, la etapa de procesado de baja densidad y la etapa de decodificación se realizan para cada palabra de recepción

CAMPO TÉCNICO

La presente invención se refiere a un método de decodificación y a un decodificador, a un programa, a un 5 aparato y a un método de grabación-y-reproducción, y a un aparato y a un método de reproducción, y se refiere, particularmente, a un método de decodificación y a un decodificador, a un programa, a un aparato y a un método de grabación-y-reproducción, y a un aparato y a un método de reproducción que son adecuados para decodificar datos codificados cuya codificación se ha realizado usando un código lineal sobre un anillo R.

10

ANTECEDENTES DE LA TÉCNICA

En los últimos años, mientras se han estado estudiando, con avances considerables, el campo de las comunicaciones, tales como las comunicaciones móviles y las comunicaciones en el espacio profundo, y el campo 15 de la radiodifusión, tal como la radiodifusión por ondas terrestres y la radiodifusión digital por satélite, se ha estudiado activamente, por ejemplo, la teoría de la codificación para aumentar la eficacia de la codificación y decodificación de corrección de errores.

Como límites teóricos del rendimiento de un código se conoce el límite de Shannon presentado por el 20 teorema denominado de codificación de las vías de comunicación de Shannon (C.E. Shannon). La teoría de la codificación se estudia para desarrollar un código que presente un rendimiento que se aproxime al límite de Shannon descrito anteriormente. En los últimos años, se ha desarrollado, como método de codificación que presenta un rendimiento que se aproxima al límite de Shannon, un método al que se hace referencia como la denominada turbocodificación que incluye códigos convolucionales concatenados en paralelo (PCCC), códigos 25 convolucionales concatenados en serie (SCCC), y otros. Además, aparte de los turbocódigos que están siendo desarrollados, se está prestando atención a un método de codificación conocido, es decir, los códigos de comprobación de paridad de baja densidad (a los que se hará referencia en lo sucesivo como códigos LDPC).

El código LDPC fue sugerido por primera vez en, “Low Density Parity Check Codes”, de R. G. Gallager, 30 Cambridge, Massachusetts: M.I.T.Press, 1963 por R. G. Gallager. A continuación, el código LDPC ha recibido atención adicional por parte de D.J.C. MacKay, “Good error correcting codes based on very sparse matrices”, presentado en IEEE Trans. Inf. Theory, IT-45, págs. 399 a 431, 1999, “Analysis of low density codes and improved designs using irregular graphs”, de M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi y D. A. Spielman, en Proceedings of ACM Symposium on Theory of Computing, págs. 249 a 258, 1998, y otros. 35

Según estudios de los últimos años, el rendimiento del código LDPC se aproxima al límite de Shannon con aumentos en la longitud del código. Además, como la distancia mínima del código LDPC es proporcional a la longitud del código, el código LDPC presenta, como características propias, las siguientes ventajas. Es decir, el código LDPC presenta características de una probabilidad alta de errores de bloque y apenas provoca el fenómeno 40 denominado suelo de error que se observa en las características de los turbocódigos de decodificación o similares.

Se describirá detalladamente el código LDPC descrito anteriormente, según la manera expuesta a continuación. El código LDPC es un código lineal y no necesariamente binario. No obstante, en esta memoria descriptiva, el mismo se describirá suponiendo que el código LDPC es binario. 45

La característica principal del código LDPC es que una matriz de comprobación de paridad que define el código LDPC es poco densa. En este caso, la matriz poco densa indica una matriz que incluye muy pocos componentes cuyos valores son “1”. La matriz de comprobación poco densa se designa mediante el carácter de referencia H. La matriz de comprobación poco densa incluye la HLDPC mostrada en la Fig. 1, donde el peso 50 Hamming (el número de “1”) de cada fila es “2” y el de cada columna es, por ejemplo, “4”.

De este modo, al código LDPC definido por una matriz de comprobación H, en donde el peso Hamming de cada una de las filas y columnas es constante, se le hace referencia como código LDPC regular. Por otro lado, a un código LDPC definido por una matriz de comprobación H en donde el peso Hamming de cada una de las filas y 55 columnas no es constante se le hace referencia como código LDPC irregular.

La codificación usando el código LDPC descrito anteriormente se logra mediante una matriz de generación G basada en la matriz de comprobación H y generando una palabra de código mediante la multiplicación de la matriz de generación G por un mensaje de datos binarios. Más específicamente, en primer lugar, un codificador 60 destinado a realizar la codificación por el código LDPC calcula la matriz de generación G, en donde se cumple una ecuación GHT=0, entre la matriz de comprobación H y una matriz transpuesta HT. Cuando la matriz de generación G es una matriz de k x n, el codificador multiplica la matriz de generación G por un mensaje de datos de k bits (vector u) y genera una palabra de código de n bits c (= uG). En la palabra de código generada por el codificador, de un bit de código cuyo valor es “0” se establece una correspondencia con “+1”, y de un bit de código cuyo valor es “1” se 65 establece una correspondencia con “1”. A continuación, la palabra de código se transmite y es recibida en el lado de recepción a través de una vía de comunicación predeterminada.

La decodificación del código LDPC se puede realizar usando un algoritmo propuesto por Gallager, y cuyo nombre fue designado por este último, como decodificación probabilística, es decir, un algoritmo de paso de mensajes por propagación de confianza (belief propagation) sobre una gráfica denominada de Tanner que incluye un modo variable (al que en ocasiones se hace referencia como nodo de mensaje) y un nodo de comprobación. En 5 lo sucesivo, al nodo variable y al nodo de comprobación se les hará referencia simplemente como nodos, según se requiera.

Por ejemplo, la matriz de comprobación de paridad HLDPC mostrada en la Fig. 1 se expresa mediante una gráfica de Tanner mostrada en la Fig. 2. En la gráfica de Tanner mostrada en la Fig. 2, se determina que cada 10 columna de la matriz de comprobación de paridad HLDPC mostrada en la Fig. 1 es un nodo variable y se determina que cada fila es un nodo de comprobación. Además, el nodo variable j-ésimo y el nodo de comprobación i-ésimo están conectados a un elemento cuyo valor es “1” en la fila i-ésima y la columna j-ésima de la matriz de comprobación de paridad HLDPC, como bordes.

15

No obstante, cuando se realiza la decodificación probabilística, el valor de un mensaje transmitido entre los nodos se proporciona en forma de un número real. Posteriormente, existe una necesidad de realizar un seguimiento de la distribución de probabilidad de mensajes que tienen valores consecutivos para una solución analítica, lo cual resulta extremadamente difícil. Por lo tanto, Gallager propuso los algoritmos A y B, como algoritmo para decodificar el código LDPC. 20

Habitualmente, la decodificación del código LDPC se logra realizando los procedimientos mostrados en la Fig. 2. Aquí, en este caso, se determina que un valor de recepción (una secuencia de código recibida) es U0(u0i), se determina que un mensaje transmitido desde el nodo de comprobación es uj, y se determina que un mensaje transmitido desde el nodo variable es vi. Además, en este caso, el mensaje es un valor de número real que indica la 25 probabilidad de que el valor sea “0”, en forma de una denominada razón de verosimilitud logarítmica.

Habitualmente, la decodificación del código LDPC se logra realizando los procedimientos mostrados en la Fig. 3. Aquí, en este caso, se determina que el valor de recepción (la secuencia de código recibida) es U0(u0i), se determina que el mensaje transmitido desde el nodo de comprobación es uj, y se determina que el mensaje 30 transmitido desde el nodo variable es vi, además, en este caso, el mensaje es el valor de un... [Seguir leyendo]

1. Método para decodificar un código lineal sobre un anillo R, incluyendo el método:

obtener una palabra de recepción;

5

una etapa de procesado de baja densidad para reducir la densidad de elementos cuyo valor es uno de tal manera que el número de elementos que tienen el valor de uno es menor que un número predeterminado, para una primera matriz de comprobación del código lineal, incluyéndose dicha primera matriz de comprobación en la palabra de recepción; y

10

una etapa de decodificación para decodificar la palabra de recepción a través de un algoritmo de suma producto usando una matriz de comprobación nueva cuya densidad se ha reducido a través de la etapa de procesado de baja densidad;

en el que la etapa de procesado de baja densidad incluye: 15

fijar una variable n a un valor inicial, funcionando n como criterio para extracción de filas;

una etapa de cálculo de combinación lineal para calcular todas las combinaciones lineales de filas de la primera matriz de comprobación; 20

una etapa de generación de matrices de comprobación para extraer un subconjunto de vectores de peso inferior con el fin de formar un espacio complementario de entre un conjunto de vectores obtenido mediante la combinación lineal calculada a través de la etapa de cálculo de combinación lineal y generar la matriz de comprobación nueva incluyendo todos los vectores del subconjunto de vectores, como elementos 25 de fila, comprendiendo dicha extracción extraer, del conjunto de vectores formado mediante combinación lineal, cualquier combinación lineal que tiene un peso menor que o igual a n;

actualizar el valor de n sumando 1; y

30

una etapa de determinación para determinar si el rango de la primera matriz de comprobación concuerda o no con el rango de la matriz de comprobación nueva, y, en caso negativo, volver a y repetir la etapa de generación de matrices de comprobación con el valor actualizado de n;

y en el que la etapa de obtención, la etapa de procesado de baja densidad y la etapa de decodificación se 35 realizan para cada palabra de recepción.

2. Método de decodificación según la reivindicación 1, en el que el anillo es un campo finito que incluye potencias de números primos, como elementos.

40

3. Método de decodificación según la reivindicación 2, en el que el código lineal incluye un código BCH, o un código de Reed-Solomon sobre el campo finito.

4. Método de decodificación según la reivindicación 1, en el que la etapa de procesado de baja densidad incluye además: 45

una etapa de expansión para expandir la primera matriz de comprobación sobre el campo finito en un subcampo predeterminado del campo finito en un grado predeterminado,

en el que la etapa de cálculo de combinación lineal se proporciona para calcular la combinación lineal de 50 las filas de la matriz de comprobación expandida a través de la etapa de expansión.

5. Decodificador (100) para un código lineal sobre un anillo R, incluyendo el decodificador:

unos medios para obtener una palabra de recepción; 55

unos medios de procesado de baja densidad (110) que ejecutan un procesado de baja densidad para reducir la densidad de elementos cuyo valor es uno de tal manera que el número de elementos que tienen el valor de uno es menor que un número predeterminado, para una primera matriz de comprobación del código lineal, incluyéndose dicha primera matriz de comprobación en la palabra de recepción; y 60

unos medios de decodificación (120) para decodificar la palabra de recepción a través de un algoritmo de suma producto usando una matriz de comprobación nueva cuya densidad se ha reducido a través de los medios de procesado de baja densidad;

65

en el que los medios de procesado de baja densidad (111) incluyen:

unos medios para fijar una variable n a un valor inicial, funcionando n como criterio para extracción de filas;

unos medios de cálculo de combinación lineal para calcular todas las combinaciones lineales de filas de la primera matriz de comprobación; y 5

unos medios de generación de matrices de comprobación (112) para extraer un subconjunto de vectores de peso inferior con el fin de formar un espacio complementario de entre un conjunto de vectores obtenido mediante la combinación lineal calculada a través de los medios de cálculo de combinación lineal y generar la matriz de comprobación nueva incluyendo todos los vectores del subconjunto de vectores, como 10 elementos de fila, comprendiendo dicha extracción extraer, del conjunto de vectores formado mediante combinación lineal, cualquier combinación lineal que tiene un peso menor que o igual a n;

unos medios para actualizar el valor de n sumando 1; y

15

unos medios de determinación para determinar si el rango de la primera matriz de comprobación concuerda o no con el rango de la matriz de comprobación nueva, y, en caso negativo, para volver a los medios de generación de matrices de comprobación con el valor actualizado de n;

y en el que la obtención, el procesado de baja densidad y la decodificación se realizan para cada palabra 20 de recepción.

6. Decodificador según la reivindicación 5, en el que el anillo es un campo finito que incluye potencias de números primos, como elementos.

25

7. Decodificador según la reivindicación 6, en el que el código lineal incluye un código BCH, o un código de Reed-Solomon sobre el campo finito.

8. Decodificador según la reivindicación 5, en el que los medios de procesado de baja densidad incluyen además unos medios de expansión (161) para expandir la matriz de comprobación sobre el campo finito en un 30 subcampo predeterminado del campo finito en un grado predeterminado,

en el que los medios de cálculo de combinación lineal calculan la combinación lineal de filas de la primera matriz de comprobación expandida a través de los medios de expansión.

35

9. Decodificador según la reivindicación 5, que incluye además unos medios de decodificación por decisión flexible para ejecutar una decodificación, por decisión flexible, de datos que han sido sometidos a una codificación de Reed-Solomon seguida por una codificación convolucional y una decodificación convolucional

en el que los medios de procesado de baja densidad reducen la densidad de los elementos cuyo valor es 40 uno para la primera matriz de comprobación del código lineal con el fin de generar la matriz de comprobación nueva que se usa para la decodificación por decisión flexible por parte de los medios de decodificación por decisión flexible.

10. Decodificador según la reivindicación 8, en el que la decodificación por decisión flexible por parte de 45 los medios de decodificación por decisión flexible, el procesado de baja densidad por parte de los medios de procesado de baja densidad y la decodificación por parte de los medios de decodificación se realizan de manera repetitiva.

11. Unidad de almacenamiento que incluye un programa para su carga en un ordenador con el fin de 50 decodificar un código lineal sobre un anillo R, provocando el programa que el ordenador ejecute un procesado de acuerdo con el método según cualquiera de las reivindicaciones 1 a 4.

12. Aparato de grabación-y-reproducción (270) para grabar datos en un soporte de grabación y reproducir los datos grabados en el soporte de grabación, incluyendo el aparato de grabación-y-reproducción: 55

unos medios de grabación (271) para grabar datos codificados usando un código lineal sobre un anillo R sobre el soporte de grabación (272);

unos medios de reproducción (273) para reproducir los datos grabados por los medios de grabación; y 60

un decodificador según cualquiera de las reivindicaciones 5 a 10.

13. Aparato de grabación-y-reproducción según la reivindicación 12, en el que los datos están codificados usando N unidades de codificación de Reed-Solomon en secuencia, y en el que dicho decodificador comprende N 65 unidades de decodificación de Reed-Solomon en secuencia, comprendiendo cada unidad de decodificación el decodificador según la reivindicación 8.

14. Aparato de grabación-y-reproducción según la reivindicación 12, en el que el procesado de baja densidad por parte de los medios de procesado de baja densidad y la decodificación por parte de los medios de decodificación se realizan de manera repetitiva.

15. Método de grabación-y-reproducción para un aparato de grabación-y-reproducción para grabar datos 5 sobre un soporte de grabación y reproducir los datos grabados sobre el soporte de grabación, estando caracterizado el método de grabación-y-reproducción porque incluye:

una etapa de control de grabación para codificar datos usando un código lineal sobre un anillo R que graba los datos sobre el soporte de grabación; 10

una etapa de control de reproducción para reproducir los datos grabados bajo el control de la etapa de control de grabación;

y el método de decodificación según cualquiera de las reivindicaciones 1 a 4, en el que la etapa de 15 procesado de baja densidad se realiza para la primera matriz de comprobación del código lineal.

16. Aparato de reproducción (360) para reproducir datos grabados sobre un soporte de grabación, incluyendo el aparato de reproducción:

20

unos medios de reproducción (273) para reproducir datos codificados usando un código lineal sobre un anillo R y grabados sobre el soporte de grabación (272); y

un decodificador según cualquiera de las reivindicaciones 5 a 10.

25

17. Aparato de reproducción según la reivindicación 16, en el que los datos están codificados usando N unidades de codificación de Reed-Solomon en secuencia, y en el que dicho decodificador comprende N unidades de decodificación de Reed-Solomon en secuencia, comprendiendo cada unidad de decodificación el decodificador según la reivindicación 8.

30

18. Aparato de reproducción según la reivindicación 16, en el que el procesado de baja densidad por parte de los medios de procesado de baja densidad y la decodificación por parte de los medios de decodificación se realizan de manera repetitiva.

19. Método de reproducción para un aparato de reproducción para reproducir datos grabados sobre un 35 soporte de grabación, incluyendo el método de reproducción:

una etapa de control de reproducción para controlar la reproducción de datos codificados usando un código lineal sobre un anillo R y grabados sobre el soporte de grabación;

40

y el método de decodificación según cualquiera de las reivindicaciones 1 a 4, en el que la etapa de procesado de baja densidad se realiza para la primera matriz de comprobación del código lineal.