Dispositivo de decodificación, método de decodificación y programa.

Aparato de decodificación de paso de mensajes (300) para decodificar un código de Comprobación de Paridadde Baja Densidad (LDPC) adaptado para implementar una propagación de confianza sobre una representación engráfica Tanner del código LDPC,

en el que la matriz de comprobación correspondiente a la gráfica Tanner de dichocódigo LDPC se representa mediante una combinación de una pluralidad de sub-matrices de PxP, y el código LDPCusa, como sub-matriz:

una matriz unidad de PxP,

una matriz cuasi-unidad, en la que uno o más 1s de una matriz unidad de PxP se sustituyen por 0,una matriz de desplazamiento, en la que dicha matriz unidad o dicha matriz cuasi-unidad se desplazacíclicamente,

una matriz suma de PxP, que es la suma de dos o más de dicha matriz unidad, dicha matriz cuasi-unidad, ydicha matriz de desplazamiento, presentando dicha matriz suma de PxP un peso de filas o columnas de 2 ómayor,

o una matriz cero de PxP,

y dicha combinación incluye matrices suma de PxP,

comprendiendo dicho aparato de decodificación:

unos primeros medios de cálculo (313) adaptados para realizar simultáneamente P cálculos de nodos decomprobación con el fin de decodificar dicho código LDPC y para obtener datos de mensajes correspondientes aP bordes como resultado de dichos P cálculos de nodos de comprobación;

unos segundos medios de cálculo (319) adaptados para realizar simultáneamente P cálculos de nodos variablescon el fin de decodificar dichos códigos LDPC y para obtener datos de mensajes correspondientes a P bordescomo resultado de dichos P cálculos de nodos variables; y

unos medios de almacenamiento de datos de bordes (311 ó 316) adaptados para leer simultáneamente, desdeuna etapa de una FIFO o una palabra de una RAM, y para escribir simultáneamente, en una etapa de una FIFOo una palabra de una RAM, datos de mensajes correspondientes a P bordes, que se obtienen a partir de losprimeros medios de cálculo (313) como resultado de dichos P cálculos de nodos de comprobación o a partir delos segundos medios de cálculo (319) como resultado de dichos P cálculos de nodos variables, estando dichosmedios de almacenamiento de datos de bordes adaptados además para almacenar, en una etapa de una FIFO ouna palabra de una RAM, para una matriz suma, cuyo peso de filas o columnas es 2 o mayor, mensajescorrespondientes a P bordes pertenecientes a una matriz unidad, matriz cuasi-unidad, o matriz dedesplazamiento incluida en la suma con el fin de formar dicha matriz suma cuyo peso de filas o columnas es 2 omayor.

Dispositivo de decodificación, método de decodificación y programa.

Campo tecnico

La presente invención se refiere a un aparato de decodificación, a un método de decodificación, y a un programa. Más particularmente, la presente invención se refiere a un aparato de decodificación y a un método de decodificación para decodificar códigos en los cuales la codificación se realiza usando códigos de comprobación de paridad de baja densidad (códigos LDPC) , y a un programa para los mismos.

Antecedentes de la tecnica

En los últimos años, la investigación, por ejemplo, en los sectores de la comunicación tales como la comunicación móvil y la comunicación en el espacio profundo, y los sectores de la radiodifusión tales como las emisiones de radiodifusión por ondas terrestres o digitales por satélite han progresado notablemente. Junto con esta situación, se ha llevado a cabo activamente una investigación sobre teorías de codificación para conseguir que la codificación y la decodificación con corrección de errores resulten eficaces.

Como límite teórico del rendimiento de un código, se conoce el límite de Shannon que se deduce a partir del denominado teorema de codificación de canales de Shannon (C. E. Shannon) . Se han llevado a cabo investigaciones sobre teorías de codificación con el fin de desarrollar códigos que presenten un rendimiento próximo a este límite de Shannon. En los últimos años, como método de codificación que presenta un rendimiento próximo al límite de Shannon, se han desarrollado, por ejemplo, técnicas para lo que se conoce comúnmente como “turbocodificación”, tal como los códigos convolucionales concatenados en paralelo (PCCC) y los códigos convolucionales concatenados en serie (SCCC) . Además, mientras se ha ido desarrollando esta turbocodificación, se ha estado prestando atención a los códigos de comprobación de paridad de baja densidad (a los que en lo sucesivo se hará referencia como “códigos LDPC”) , los cuales son un método de codificación que se ha conocido durante mucho tiempo.

Los códigos LDPC los propuso por primera vez R. G. Gallager, en “Low Density Parity Check Codes”, Cambridge, Massachusetts: M. I. T. Press, 1963. Después de esto, se volvió a prestar atención a los códigos LDPC en “Good error correcting codes based on ver y sparse matrices”, de D. J. C. MacKay, presentado en la IEEE Trans. Inf. Theor y , IT-45, págs. 399 a 431, 1999, y en “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 Theor y of Computing, págs. 249 a 258, 1998.

A partir de estas investigaciones recientes se está comenzando a saber que, para los códigos LDPC, a medida que la longitud del código aumenta, se puede obtener un rendimiento próximo al límite de Shannon, de manera similar a la turbocodificación. Además, puesto que los códigos LDPC tienen la propiedad de que la longitud mínima es proporcional a la longitud del código, presentan las ventajas de que las características de probabilidad de errores de bloque son buenas, y apenas se produce un fenómeno denominado de suelo de error, el cual se observa en características de decodificación correspondientes a la turbocodificación.

A continuación se describirán detalladamente dichos códigos LDPC. Los códigos LDPC son códigos lineales y no siempre es necesario que sean bidimensionales, pero en este caso, se proporciona una descripción suponiendo que los códigos LDPC son bidimensionales.

Las características más importantes de los códigos LDPC son que la matriz de comprobación de paridad que define los códigos LDPC es dispersa. En este caso, se forma una matriz dispersa de tal manera que el número de 1s en los elementos de la matriz es muy pequeño. Si la matriz de comprobación dispersa se indica como H, ejemplos de la misma incluyen una matriz de comprobación en la cual, tal como se muestra en la Fig. 1, el peso Hamming de cada columna (número de 1s; peso) es “3”, y el peso Hamming de cada fila es “6”.

Tal como se ha descrito anteriormente, a los códigos LDPC definidos por la matriz de comprobación H en la que el peso Hamming de cada fila y cada columna es fijo se les denomina “códigos LDPC regulares”. Por otro lado, a los códigos LDPC definidos por una matriz de comprobación H en la cual el peso Hamming de cada fila y cada columna no es fijo se les denomina “códigos LDPC irregulares”.

La codificación mediante dichos códigos LDPC se logra generando una matriz de generación G sobre la base de la matriz de comprobación H y generando una palabra de código mediante la multiplicación de esta matriz de generación G por un mensaje de información bidimensional. Más específicamente, un aparato de codificación destinado a realizar la codificación según códigos LDPC calcula una matriz de generación G en la cual se cumple la ecuación GHT = 0 con una matriz transpuesta HT de la matriz de comprobación H. En este caso, cuando la matriz de generación G es una matriz de k x n, el aparato de codificación multiplica la matriz de generación G por un mensaje de información de k bits (vector u) , y genera una palabra de código de n bits c (= uG) . La palabra de código generada por este aparato de codificación se transmite con el establecimiento de una correspondencia del bit de código cuyo valor es “0” a “+1” y el establecimiento de una correspondencia del bit de código cuyo valor es “1” a “-1”, y se recibe en el lado de la recepción a través de un canal de comunicaciones predeterminado.

Por otro lado, la decodificación de los códigos LDPC se puede realizar por medio de un algoritmo de paso de mensajes por propagación de confianza (belief propagation) sobre una gráfica denominada de Tanner, la cual se forma con un nodo variable (denominado también nodo de mensaje) y un nodo de comprobación; este algoritmo de paso de mensajes fue propuesto por Gallager y se conoce como “decodificación probabilística”. En lo sucesivo en la presente, a los nodos variables y a los nodos de comprobación también se les hace referencia simplemente como nodos, cuando así resulte apropiado.

No obstante, en la decodificación probabilística, puesto que los mensajes intercambiados entre nodos son valores de números reales, con el fin de hallar una solución analítica, es necesario realizar un seguimiento de la distribución de probabilidad del mensaje que adopta un valor continuo. Esto requiere un análisis que implica un alto grado de dificultad. Por consiguiente, Gallager ha propuesto un algoritmo A o un algoritmo B como algoritmo para decodificar códigos LDPC.

En general, la decodificación de los códigos LDPC se realiza de acuerdo con el procedimiento mostrado en la Fig. 2. En este caso, el valor de recepción se indica como U0 (u0i) , la salida de mensaje del código de comprobación se indica como uj, y la salida del mensaje del nodo variable se indica como vi. En este caso, el mensaje es un valor de número real de tal manera que la probabilidad de “0” del valor se representa mediante la denominada razón de verosimilitud logarítmica.

Inicialmente, en la decodificación de los códigos LDPC, tal como se muestra en la Fig. 2, en la etapa S11, se recibe el valor de recepción U0 (u0i) , el mensaje uj se inicializa a 0, y una variable k que adopta un entero como contador para un proceso iterativo se inicializa a 0. A continuación, el proceso prosigue hacia la etapa S12. En la etapa S12, sobre la base del valor recibido U0 (u0i) , se determina un mensaje vi realizando un cálculo que se muestra en la ecuación (1) . Además, sobre la base de este mensaje vi, se determina un mensaje uj realizando un cálculo que se muestra en la ecuación (2) .

d -1

v

v = u +Lu ... (1)

i0i j j=1

( u Jd -1v

c

tanh j =dtanh (i J ... (2) 2 i=1 2

En este caso, dv y dc de las ecuaciones (1) y (2) son parámetros respectivamente que indican el número de 1s en la dirección vertical (en la dirección de las filas) y en la dirección horizontal (en la dirección de las columnas) de la matriz de comprobación H y que se pueden seleccionar según se desee. Por ejemplo, en el caso de un código (3, 6) , dv=3 y dc=6.

En el cálculo de cada una de las ecuaciones (1) y (2) , puesto que el mensaje introducido desde un borde desde el cual se va a dar salida a un mensaje no se usa como parámetro para un cálculo de suma o producto, el intervalo del cálculo de suma o producto está entre 1 y dv -1... [Seguir leyendo]

1. Aparato de decodificación de paso de mensajes (300) para decodificar un código de Comprobación de Paridad de Baja Densidad (LDPC) adaptado para implementar una propagación de confianza sobre una representación en gráfica Tanner del código LDPC, en el que la matriz de comprobación correspondiente a la gráfica Tanner de dicho código LDPC se representa mediante una combinación de una pluralidad de sub-matrices de PxP, y el código LDPC usa, como sub-matriz:

una matriz unidad de PxP,

una matriz cuasi-unidad, en la que uno o más 1s de una matriz unidad de PxP se sustituyen por 0,

una matriz de desplazamiento, en la que dicha matriz unidad o dicha matriz cuasi-unidad se desplaza cíclicamente,

una matriz suma de PxP, que es la suma de dos o más de dicha matriz unidad, dicha matriz cuasi-unidad, y dicha matriz de desplazamiento, presentando dicha matriz suma de PxP un peso de filas o columnas de 2 ó mayor,

o una matriz cero de PxP,

y dicha combinación incluye matrices suma de PxP,

comprendiendo dicho aparato de decodificación:

unos primeros medios de cálculo (313) adaptados para realizar simultáneamente P cálculos de nodos de comprobación con el fin de decodificar dicho código LDPC y para obtener datos de mensajes correspondientes a P bordes como resultado de dichos P cálculos de nodos de comprobación;

unos segundos medios de cálculo (319) adaptados para realizar simultáneamente P cálculos de nodos variables con el fin de decodificar dichos códigos LDPC y para obtener datos de mensajes correspondientes a P bordes como resultado de dichos P cálculos de nodos variables; y

unos medios de almacenamiento de datos de bordes (311 ó 316) adaptados para leer simultáneamente, desde una etapa de una FIFO o una palabra de una RAM, y para escribir simultáneamente, en una etapa de una FIFO

o una palabra de una RAM, datos de mensajes correspondientes a P bordes, que se obtienen a partir de los primeros medios de cálculo (313) como resultado de dichos P cálculos de nodos de comprobación o a partir de los segundos medios de cálculo (319) como resultado de dichos P cálculos de nodos variables, estando dichos medios de almacenamiento de datos de bordes adaptados además para almacenar, en una etapa de una FIFO o una palabra de una RAM, para una matriz suma, cuyo peso de filas o columnas es 2 o mayor, mensajes correspondientes a P bordes pertenecientes a una matriz unidad, matriz cuasi-unidad, o matriz de desplazamiento incluida en la suma con el fin de formar dicha matriz suma cuyo peso de filas o columnas es 2 o mayor.

2. Aparato de decodificación según la reivindicación 1, en el que dichos primeros medios de cálculo tienen P dispositivos de cálculo de nodos de comprobación para realizar cálculos de nodos de comprobación, y

dichos segundos medios de cálculo tienen P dispositivos de cálculo de nodos variables para realizar cálculos de nodos variables.

3. Aparato de decodificación según la reivindicación 1, que comprende además:

unos medios de almacenamiento de información recibida (318) para almacenar la información recibida de códigos LDPC y para leer simultáneamente P elementos de dicha información recibida.

4. Aparato de decodificación según la reivindicación 3, en el que dichos medios de almacenamiento de información recibida almacenan dicha información recibida, de tal manera que la información recibida se pueda leer en la secuencia necesaria para dicho cálculo de nodos variables.

5. Aparato de decodificación según la reivindicación 1, que comprende además:

6. Aparato de decodificación según la reivindicación 5, en el que dichos medios de reorganización comprenden un desplazador de barril.

7. Método de decodificación usado por un aparato de decodificación de paso de mensajes (300) para decodificar un código de Comprobación de Paridad de Baja Densidad (LDPC) adaptado para implementar una propagación de confianza sobre una representación en gráfica Tanner del código LDPC, en el que la matriz de comprobación correspondiente a la gráfica Tanner de dicho código LDPC se representa mediante una combinación de una pluralidad de sub-matrices de PxP, y el código LDPC usa, como sub-matriz:

unos medios de reorganización (314, 320) para reorganizar mensajes obtenidos como resultado de dichos P cálculos de nodos de comprobación o dichos P cálculos de nodos variables.

una matriz unidad de PxP,

una matriz cuasi-unidad, en la que uno o más 1s de una matriz unidad de PxP se sustituyen por 0,

una matriz de desplazamiento, en la que dicha matriz unidad o dicha matriz cuasi-unidad se desplaza cíclicamente,

una matriz suma de PxP, que es la suma de dos o más de dicha matriz unidad, dicha matriz cuasi-unidad, y dicha matriz de desplazamiento, presentando dicha matriz suma de PxP un peso de filas o columnas de 2 o mayor,

o una matriz cero de PxP,

y dicha combinación incluye unas matrices suma de PxP,

comprendiendo dicho método de decodificación las siguientes etapas de método:

realizar simultáneamente P cálculos de nodos de comprobación con el fin de decodificar dicho código LDPC y obtener datos de mensajes correspondientes a P bordes como resultado de dichos P cálculos de nodos de comprobación usando unos primeros medios de cálculo (313) ;

realizar simultáneamente P cálculos de nodos variables con el fin de decodificar dichos códigos LDPC y obtener datos de mensajes correspondientes a P bordes como resultado de dichos P cálculos de nodos variables usando unos segundos medios de cálculo (319) ; y

leer simultáneamente, desde una etapa de una FIFO de unos medios de almacenamiento de datos de bordes (311 ó 316) o una palabra de una RAM de los medios de almacenamiento de datos de bordes (311 ó 316) , y escribir simultáneamente, en una etapa de una FIFO de los medios de almacenamiento de datos de bordes (311 ó 316) o una palabra de una RAM de los medios de almacenamiento de datos de bordes (311 ó 316) , datos de mensajes correspondientes a P bordes, que se obtienen a partir de los primeros medios de cálculo (313) como resultado de dichos P cálculos de nodos de comprobación o a partir de los segundos medios de cálculo (319) como resultado de dichos P cálculos de nodos variables, incluyendo almacenar, en una etapa de una FIFO o una palabra de una RAM, para una matriz suma cuyo peso de filas o columnas es 2 ó mayor, mensajes correspondientes a P bordes pertenecientes a una matriz unidad, matriz cuasi-unidad, o matriz de desplazamiento incluida en la suma con el fin de formar dicha matriz suma cuyo peso de filas o columnas es 2 o mayor.

8. Programa de ordenador para permitir que un ordenador decodifique códigos LDPC realizando todas las etapas del método de la reivindicación 7.