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

Un aparato de decodificación (600) para decodificar un código de Control de Paridad de Baja Densidad LDPCadaptado para poner en práctica una propagación de creencia sobre una representación de gráfico de Tanner del códigoLDPC,

en donde la matriz de control de paridad, correspondiente al gráfico de Tanner de dicho código LDPC, estáconstituida por una combinación de una pluralidad de sub-matrices P x P,

en donde cada sub-matriz es una matriz unitaria P x P; una matriz cuasi-unitaria en donde uno o varios `1', que sonelementos de la matriz unitaria P x P se sustituyen por 0; una matriz de desplazamiento en donde dicha matriz unitaria odicha matriz cuasi-unitaria está desplazada de forma cíclica; una matriz suma P x P, que es la suma de dos o más dedicha matriz unitaria de dicha matriz cuasi-unitaria y de dicha matriz de desplazamiento, en donde dicha matriz suma P xP tiene un peso de ponderación de fila o de columna de dos o más; o una matriz nula P x P;

comprendiendo dicho aparato de decodificación:

un primer medio de cálculo (612) adaptado para realizar simultáneamente una primera parte de P cálculos de nodos decontrol calculando:

en donde dc representa el número de `1' en la correspondiente fila de la matriz de control de paridad y vi' representa lossegundos resultados de decodificación en curso (D615) definidos a continuación, para obtener los P primeros resultadosde decodificación en curso W (D612);

la primera memoria (613) adaptada para memorizar los P primeros resultados de decodificación en curso W procedentesdel primer medio de cálculo en una misma dirección;

un segundo medio de cálculo (615) adaptado para realizar una segunda parte de P cálculos de nodos de controlsimultáneamente y para realizar P cálculos de nodos de variables simultáneamente calculando:

ypara obtener P segundos resultados de decodificación en curso vi' (D615)

en donde Φ (x) se define como la función In (tanh (x/2)), uoi es un valor inicial para datos recibidos para decodificarse y dvrepresenta el número de `1' en la correspondiente columna de la matriz de control de paridad; y

una segunda memoria (610) adaptada para memorizar los P segundos resultados de decodificación en curso vi' a partirdel segundo medio de cálculo en una misma dirección.

Aparato de decodificación, método de decodificación y programa

CAMPO TÉCNICO

La presente invención se refiere a un aparato de decodificación, un método de decodificación y un programa. Más en particular, la presente invención se refiere a un aparato de decodificación y un método de decodificación para decodificar códigos en los que se realiza la codificación utilizando códigos de control de paridad de baja densidad (códigos LDPC) y para un programa relacionado.

ANTECEDENTES DE LA INVENCIÓN

En los últimos años, la investigación en, a modo de ejemplo, los campos de comunicación tales como la comunicación móvil y la comunicación de espacio profundo y los campos de difusión tales como las difusiones digitales por satélite o de ondas terrestres ha progresado de forma notoria. Junto con esta situación, la investigación sobre las teorías de codificación para obtener una decodificación y codificación de corrección de errores eficiente se ha realizado de forma activa.

Como un límite teórico de la realización de códigos, se conoce el denominado límite de Shannon implicado por el así denominado teorema de codificación de canales de Shannon (C.E. Shannon) . La investigación sobre las teorías de codificación se ha realizado para la finalidad de desarrollar códigos que presentan una ejecución cercana a este límite de Shannon. En los últimos años, como un método de codificación que presenta una ejecución cercana al límite de Shannon, a modo de ejemplo, se han desarrollado técnicas para lo que se suele denominar “codificación turbo”, tal como códigos convolucionales concatenados paralelos (PCCC) y códigos convolucionales concatenados en serie (SCCC) . Además, mientras se ha desarrollado esta codificación turbo, los códigos de control de paridad de baja densidad (en adelante referidos como “código LDPC”) , que es un método de codificación que ha sido conocido durante un largo periodo de tiempo, han atraído la atención.

Los códigos LDPC fueron propuestos primero en R.G. Gallager, “Códigos de Control de Paridad de Baja Densidad”, Cambridge, Massachusetts: M.I. T. Press, 1963. Más adelante, los códigos LDPC volvieron a atraer la atención en el Documento D. J.C. MacKay, “Códigos de corrección de errores adecuados basados en matrices muy escasas de elementos”, presentado a IEEE Trans. Inf. Theor y , IT-45, páginas 399-431, 1999 y M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi y D. A. Spielman, “Análisis de códigos de baja densidad y diseños mejorados utilizando gráficos irregulares”, en Proceedings of ACM Symposium on Theor y of Computing, páginas 249-258, 1998.

A partir de esta reciente investigación comienza a conocerse que, para los códigos LDPC, a medida que aumenta la longitud del código, se puede obtener un rendimiento próximo al límite de Shannon, de forma similar a la denominada codificación turbo. 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, tienen las ventajas operativas de que las características de la probabilidad de errores de bloques son buenas y un así denominado fenómeno de límite inferior de errores, que se observa en las características de decodificación de la codificación turbo, es difícil que ocurra.

Dichos códigos LDPC se describirán a continuación, en detalle. Los códigos LDPC son códigos lineales y no siempre necesitan ser bidimensionales, pero aquí se proporciona una descripción suponiendo que los códigos LDPC son bidimensionales.

Las principales características de los códigos LDPC son que la matriz de control de paridad, que define los códigos, LDPC es escasa de elementos. En este caso, una matriz escasa se forma de tal manera que el número de ‘1’ en los elementos de la matriz es muy pequeño. Si la matriz de control escasa se indica como H, sus ejemplos incluyen una matriz de control en la que, según se ilustra en la Figura 1, el peso de ponderación de Hamming de cada columna (número de ‘1’; peso) es “3” y el peso de Hamming de cada fila es “6”.

Según se describió anteriormente, los códigos LDPC definidos por la matriz de control H, en donde el peso de Hamming de cada fila y de cada columna es fijo, se denominan “códigos LDPC regulares”. Por otro lado, los códigos LDPC definidos por una matriz de control H en donde el peso de Hamming de cada fila y de cada columna no es fijo, se denominan “códigos LDPC irregulares”.

La codificación por dichos códigos LDPC se realiza generando una matriz de generación G sobre la base de la matriz de control H y generando una palabra de código multiplicando esta matriz de generación G por un mensaje de información bidimensional. Más concretamente, un aparato de codificación para realizar la codificación mediante códigos LDPC calcula una matriz de generación G en donde la ecuación GHT = 0 se mantiene con una matriz de transposición HT de la matriz de control H. En este caso, cuando la matriz de generación G es una matriz 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 bit de código cuyo

valor es “0” siendo objeto de mapeado a “+1” y el bit de código cuyo valor es “1” siendo objeto de mapeado a “-1” y se recibe en el lado de recepción a través de un canal de comunicación predeterminado.

Por otro lado, la decodificación de los códigos LDPC se puede realizar mediante un algoritmo de paso de mensajes mediante la propagación de creencia en un así denominado gráfico de Tanner, que está constituido por un nodo de variable (también denominado un nodo de mensaje) y un nodo de control; este algoritmo de paso de mensaje fue propuesto por Gallager y es conocido como “decodificación probabilística”. En adelante, los nodos de variables y los nodos de control se refieren también simplemente como nodos, en donde sea adecuado.

Sin embargo, en la decodificación probabilística, puesto que los mensajes intercambiados entre nodos son valores de números reales, con el fin de encontrar una solución analítica, es necesario efectuar un seguimiento de la distribución de probabilidad del mensaje que toma un valor continuo. Esto necesita un análisis que implica un alto grado de dificultad. En consecuencia, Gallager ha propuesto un algoritmo A o un algoritmo B como un algoritmo para decodificar códigos LDPC.

En general, la decodificación de los códigos LDPC se realiza en conformidad con el procedimiento ilustrado en la Figura 2. En este caso, el valor de recepción se indica como U0 (u0i) , la salida del mensaje desde el nodo de control se indica como uj y la salida de mensaje desde el nodo de variable se indica como vi. En este caso, el mensaje es un valor de número real tal como el “0” – semejanza del valor se representa por una así denominada ratio de probabilidad logarítmica.

En la decodificación de los códigos LDPC, inicialmente, según se ilustra en la Figura 2, en la etapa S11, se recibe el valor de recepción u0 (u0i) , se inicializa a 0 el mensaje uj y una variable k que toma un valor entero como un contador para un proceso iterativo se inicializa a 0. A continuación, el proceso prosigue con la etapa S12. En la etapa S12, basada en el valor u0 (u0i) recibido, se determina un mensaje vi realizando un cálculo representado en la ecuación (1) . Además, sobre la base de este mensaje vi, se determina un mensaje uj realizando un cálculo representado en la ecuación (2) .

En este caso, dv y dc, en las ecuaciones (1) y (2) son parámetros, respectivamente, que indican el número de '1' en la dirección vertical (en la dirección de filas) y en la dirección horizontal (en la dirección de columnas) de la matriz de control H y que se pueden seleccionar según se desee. A modo de 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 la entrada del mensaje desde un borde desde el que procede un mensaje no se utiliza como un parámetro para un cálculo de suma o producto, la gama del cálculo de suma o producto es desde 1 a dv - 1 o 1 a dc - 1. En la práctica, el cálculo indicado en la ecuación (2) se realiza creando, por anticipado, una tabla de una función R (v1, v2) , representada en la ecuación (3) , que se define con una salida con respecto a dos entradas v1 y v2 y utilizando esta tabla continuamente (de forma recursiva) , según... [Seguir leyendo]

1. Un aparato de decodificación (600) para decodificar un código de Control de Paridad de Baja Densidad LDPC adaptado para poner en práctica una propagación de creencia sobre una representación de gráfico de Tanner del código LDPC, en donde la matriz de control de paridad, correspondiente al gráfico de Tanner de dicho código LDPC, está constituida por una combinación de una pluralidad de sub-matrices P x P,

en donde cada sub-matriz es una matriz unitaria P x P; una matriz cuasi-unitaria en donde uno o varios ‘1’, que son elementos de la matriz unitaria P x P se sustituyen por 0; una matriz de desplazamiento en donde dicha matriz unitaria o dicha matriz cuasi-unitaria está desplazada de forma cíclica; una matriz suma P x P, que es la suma de dos o más de dicha matriz unitaria de dicha matriz cuasi-unitaria y de dicha matriz de desplazamiento, en donde dicha matriz suma P x P tiene un peso de ponderación de fila o de columna de dos o más; o una matriz nula P x P;

comprendiendo dicho aparato de decodificación:

un primer medio de cálculo (612) adaptado para realizar simultáneamente una primera parte de P cálculos de nodos de control calculando:

en donde dc representa el número de ‘1’ en la correspondiente fila de la matriz de control de paridad y vi’ representa los segundos resultados de decodificación en curso (D615) definidos a continuación, para obtener los P primeros resultados de decodificación en curso W (D612) ;

la primera memoria (613) adaptada para memorizar los P primeros resultados de decodificación en curso W procedentes del primer medio de cálculo en una misma dirección;

un segundo medio de cálculo (615) adaptado para realizar una segunda parte de P cálculos de nodos de control simultáneamente y para realizar P cálculos de nodos de variables simultáneamente calculando:

para obtener P segundos resultados de decodificación en curso vi’ (D615)

en donde  (x) se define como la función In (tanh (x/2) ) , uoi es un valor inicial para datos recibidos para decodificarse y dv representa el número de ‘1’ en la correspondiente columna de la matriz de control de paridad; y

una segunda memoria (610) adaptada para memorizar los P segundos resultados de decodificación en curso vi’ a partir del segundo medio de cálculo en una misma dirección.

2. El aparato de decodificación según la reivindicación 1, en donde dicho primer medio de cálculo comprende P calculadores para realizar dicha primera parte de los P cálculos de nodos de control y

dicho segundo medio de cálculo comprende P calculadores para realizar dicha segunda parte de los P cálculos de nodos de control y dichos P cálculos de nodos de variables.

3. El aparato de decodificación según la reivindicación 1, en donde dicha segunda memoria comprende dos memorias de acceso aleatorio (RAMs) de puerto único.

4. El aparato de decodificación según la reivindicación 3, en donde dichas memorias RAMs de puerto único memorizan, de forma alternada, dichos segundos resultados de decodificación en curso en unidades de dichos segundos resultados de decodificación en curso correspondientes a P bordes de dicha matriz de control.

5. El aparato de decodificación según la reivindicación 3, en donde dichas dos memorias de acceso aleatorio (RAMs) de puerto único efectúan la lectura, cada una, de dichos segundos resultados de decodificación en curso, memorizados en la misma dirección.

6. El aparato de decodificación según la reivindicación 1, en donde dicha segunda memoria memoriza, en una misma dirección, dichos segundos resultados de decodificación en curso correspondientes a P bordes pertenecientes a una

matriz unitaria cuyo peso de ponderación es 1, una matriz cuasi-unitaria o una matriz de desplazamiento cuando las submatrices cuyo peso de ponderación de fila o de columna es 2 o más desde entre las sub-matrices que representan dicha matriz de control están representadas en la forma de la suma de la matriz unitaria cuyo peso de ponderación es 1, la matriz cuasi-unitaria o la matriz de desplazamiento.

7. El aparato de decodificación según la reivindicación 1, que comprende, además:

medios de memorización de la información recibida (616) para memorizar la información recibida de códigos LDPC y para la lectura simultánea de P elementos de información recibida.

8. El aparato de decodificación según la reivindicación 7, en donde dicho medio de memorización de la información recibida memoriza dicha información recibida en tal manera que dicha información recibida pueda ser objeto de lectura en la secuencia necesaria para dicha segunda parte de los P cálculos de nodo de control y dichos P cálculos de nodos de variables.

9. El aparato de decodificación según la reivindicación 1, que comprende, además:

medios de redisposición (611, 614) para redisponer los primeros resultados de decodificación en curso obtenidos por dicho primer medio de cálculo realizando dicha primera parte de los P cálculos de nodos de control o los segundos resultados de decodificación en curso obtenidos por dicho segundo medio de cálculo realizando dicha segunda parte de los P cálculos de nodos de control y dichos P cálculos de nodos de variables.

10. El aparato de decodificación según la reivindicación 9, en donde dicho medio de redisposición comprende un dispositivo desplazador de rotación.

11. Un método de decodificación para decodificar un código de control de paridad de baja densidad LDPC, adaptado para poner en práctica una propagación de creencia en una representación de gráficos de Tanner del código LDPC, en donde la matriz de control de paridad correspondiente al gráfico de Tanner de dicho código LDPC está constituida por una combinación de una pluralidad de sub-matrices de P x P,

en donde cada sub-matriz es una matriz unitaria P x P; una matriz cuasi-unitaria en donde uno o más ‘1’, que son elementos de una matriz unitaria P x P, se sustituyen por ‘0’; una matriz de desplazamiento en donde dicha matriz unitaria o dicha matriz cuasi-unitaria se desplaza de forma cíclica; una matriz suma P x P, que es la suma de dos o más de dicha matriz unitaria, de dicha matriz cuasi-unitaria y de dicha matriz de desplazamiento, en donde dicha matriz suma P x P tiene un peso de ponderación de fila o de columna de dos o más o una matriz nula (P x P) ;

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

realizar simultáneamente una primera parte de P cálculos de nodos de control calculando:

en donde dc representa el número de ‘1’ en la correspondiente fila de la matriz de control de paridad y vi’ representa los segundos resultados de decodificación en curso (D615) definidos a continuación, para obtener los P primeros resultados de decodificación en curso W (D612) utilizando el primer medio de cálculo (612) ;

memorizar los P primeros resultados de decodificación en curso W a partir del primer medio de cálculo en una misma dirección de una primera memoria (613) ;

realizar una segunda parte de P cálculos de nodos de control simultáneamente y realizar P cálculos de nodos de variables simultáneamente calculando:

para obtener P segundos resultados de decodificación en curso vi’ (D615) utilizando el segundo medio de cálculo (615) , en donde  (x) se define como la función In (tanh (x/2) ) , uoi es un valor inicial para datos recibidos para decodificarse y dv representa el número de ‘1’ en la correspondiente columna de la matriz de control de paridad; y

memorizar los P segundos resultados de decodificación en curso vi’ a partir del segundo medio de cálculo en una misma dirección de una segunda memoria (610) .

12. Un programa para permitir a un ordenador decodificar un código de Control de Paridad de Baja Densidad poniendo en práctica el método de la reivindicación 11.

NODO DE CONTROL

NODO DE VARIABLES

NODO DE VARIABLES

NODO DE CONTROL

RETARDO9 RELOJ

RETARDO9 RELOJ

RETARDO5 RELOJ

CIRCUITO DESPLAZ. CÍCLICO

MEMORIA PARADATOS RECIBIDOS

LLRDERECEPCIÓN

CIRCUITO DESPLAZ. CÍCLICO

RETARDO 9SEÑALESRELOJ

RETARDO 9SEÑALESRELOJ

RETARDO5SEÑALES

RETARDO9SEÑALESRELOJ

RETARDO9SEÑALESRELOJ

RETARDO 9SEÑALESRELOJ

RETARDO 9SEÑALESRELOJ

RETARDO 5SEÑALESRELOJ

RETARDO 5SEÑALESRELOJ