Codificación eficiente de códigos LDPC usando matrices de verificación de paridad estructuradas.

Un método de codificar LDPC una secuencia de información s (s0,

s1,..., sk-1) de longitud k ≥ kb * z usando unamatriz modelo mb x nb Hbm, con elementos de matriz p(i,j), i ≥ 0, 1, ..., mb-1 y j ≥ 0, 1, ..., nb-1, para obtener unasecuencia de paridad p (p0, p1, ..., pm-1)' m ≥ mb * z denotado por v, donde v ≥ [v(0) v(1) ... v(mb -1)] y cada elementode v es un vector de columna como v(i) ≥ [piz piz+1 ... p(i+1)z-1]T,I ≥ 0, 1, ..., mb-1,

incluyendo el método

* dividir la secuencia de información s en kb ≥ kb ≥ nb-mb grupos de z bits denotados por u ≥ [u(0) u(1) ... u(kb - 1)],donde cada elemento de u es un vector de columna como sigue**Fórmula**

, i ≥ 0, 1, ..., kb-1;

* determinar v(0) por v(0) ≥

donde x denota el índice de fila de hbm donde la entrada tiene el único valor no negativo que se usa un número imparde veces dentro de hbm y hbm es la kb-ésima columna de la matriz modelo Hbm, donde una matriz de verificación deparidad del código LDPC es una expansión de la matriz modelo Hbm reproduciendo cada p(i, j) negativo por unamatriz todo ceros zxz y cada p(i,j) no negativo por una matriz de permutación Pp(i,j) que es una matriz de identidadzxz cuyas columnas son circulares desplazadas por un tamaño de desplazamiento circular de p(i,j) a la derecha;* determinar v(1), v(2), v(3), ..., v(mb-1) por **Fórmula**

Codificación eficiente de códigos LDPC usando matrices de verificación de paridad estructuradas Campo de la invención

La presente invención se refiere en general a codificar y descodificar datos y, en particular, a un método y aparato para codificar y descodificar datos utilizando códigos de verificación de paridad de baja densidad (LDPC) .

Antecedentes de la invención

Como se describe en la Solicitud de Patente de Estados Unidos número de serie 10/839995, un código de verificación de paridad de baja densidad (LDPC) es un código de bloque lineal especificado por una matriz de verificación de paridad H. En general, un código LDPC se define sobre un campo Galois GF (q) , q º 2. Si q = 2, el

código es un código binario. Todos los códigos de bloque lineal se pueden describir como el producto de un vector de información de k bits s1xk con una matriz de generación de código Gkxn para producir una palabra clave de n bits x1xn, donde la tasa de código es r = k/n. La palabra clave x es transmitida a través de un canal ruidoso, y el vector de señal recibida y se pasa al descodificador para estimar el vector de información s1xk.

Dado un espacio n-dimensional, las filas de G abarcan el subespacio de palabra clave k-dimensional C, y las filas de la matriz de verificación de paridad Hmxn abarcan el espacio dual m-dimensional CI, donde m = n-k. Dado que x = sG y GHT = 0, se deduce que xHT = 0 para todas las palabras clave en el subespacio C, donde “T” (o “T”) denota donde 0 es un vector de fila de todo ceros, y la palabra clave x = [s p] = [s0, s1, …, sk-1, p0, p1, …, pm-1], donde p0, …, pm-1 son los bits de verificación de paridad; y s0, …, sk-1 son los bits sistemáticos, iguales a los bits de información dentro del vector de información.

Para un código LDPC, la densidad de entradas no cero en H es baja, es decir, solamente hay un pequeño porcentaje de 1s en H, permitiendo un mejor rendimiento de corrección de errores y una descodificación más simple que usando un H denso. Una matriz de verificación de paridad también se puede describir mediante un gráfico bipartito. El gráfico bipartito no es solamente una descripción gráfica del código, sino también un modelo para el descodificador. En el gráfico bipartito, un bit de palabra clave (por lo tanto cada columna de H) se representa por un nodo variable a la izquierda, y cada ecuación de verificación de paridad (por lo tanto cada fila de H) se representa por un nodo de verificación a la derecha. Cada nodo variable corresponde a una columna de H y cada nodo de verificación corresponde a una fila de H, haciéndose referencia de forma intercambiable a “nodo variable” y “columna” de H, así como “nodo de verificación” y “fila” de H. Los nodos variables solamente están conectados a nodos de verificación, y los nodos de verificación solamente están conectados a nodos variables. Para un código con n bits de palabra clave y m bits de paridad, el nodo variable vi está conectado al nodo de verificación cj por un borde si el bit de palabra clave i participa en la ecuación de verificación j, i = 0, 1, …, n-1, j = 0, 1, …, m-1. En otros términos, el nodo variable i se conecta al nodo de verificación j si la entrada hji de la matriz de verificación de paridad H es 1. Reflejando la ecuación (1) , los nodos variables representan una palabra clave válida si todos los nodos de verificación tienen paridad par.

A continuación se muestra un ejemplo para ilustrar la relación entre la matriz de verificación de paridad, las correspondiendo la porción lateral izquierda a k ( = 6) bits de información s, correspondiendo la porción lateral derecha a m ( = 6) bits de paridad o. Aplicando (1) , H en (2) define 6 ecuaciones de verificación de paridad como 50 sigue:

H también tiene el gráfico bipartito correspondiente representado en la figura 1.

Como se ha explicado anteriormente, el receptor obtiene una versión contaminada y de la palabra clave transmitida x. Para descodificar y y determinar la secuencia de información original s, se aplica un algoritmo de descodificación iterativo, tal como propagación de creencia, en base al gráfico bipartito. Se pasa información blanda en el formato de relación de probabilidad log (LLRs) de los bits de palabra clave entre el banco de nodos variables y el banco de nodos de verificación. La iteración se para cuando se cumplen todas las ecuaciones de verificación o se alcanza un límite de iteración permitido máximo.

Un diseño de código LDPC estructurado empieza con una pequeña matriz base mbxnb Hb, hace z copias de Hb, e interconecta las z copias para formar una matriz mxn H grande, donde m = mbxz, n = nbxz. Usando la representación de matriz para crear H a partir de Hb, cada 1 en Hb es sustituido por una submatriz de permutación zxz, y cada 0 en Hb es sustituido por una submatriz todo ceros zxz. Este procedimiento mapea esencialmente cada borde de Hb a un borde vectorial de longitud z en H, cada nodo variable de Hb a un nodo variable de vector de longitud z en H, y cada nodo de verificación de Hb a un nodo de verificación de vector de longitud z en H. Los beneficios de vectorizar una matriz Hb pequeña para crear una matriz H grande son:

1. Usando unos valores diferentes de z, se puede diseñar códigos de tasa kb/nb, donde kb = nb-mb, para muchos tamaños de secuencia de información diferentes k = zxkb a partir de una sola matriz base Hb.

2. Los requisitos de memoria se reducen en gran medida. Con un diseño LDPC estructurado, solamente hay que guardar la matriz base Hb y la permutación para sus 1s, lo que requiere significativamente menos memoria dado que Hb es típicamente mucho más pequeño que H y la permutación puede ser muy simple.

3. La codificación y la descodificación pueden ser realizadas en grupos de bits más bien que por bits únicos. Por ejemplo, un grupo de z mensajes puede ser tomado de la memoria, permutado y pasado entre un nodo variable de vector y un nodo de verificación de vector.

Aunque la filosofía del diseño LDPC estructurado reduce en gran medida la complejidad de la implementación, no existe una técnica para diseñar la matriz base y asignar las matrices de permutación para un tamaño de H deseado dado que dé lugar a un código LDPC que tenga buen rendimiento de corrección de errores y pueda ser codificado y descodificado eficientemente. Por lo tanto, se necesita un método y aparato para diseñar un H estructurado y un método y aparato para codificar y descodificar datos utilizando la matriz H estructurada.

“LDPC coding for OFDMA PJY” IEEE 802.16 BROADBAND WIRELESS ACCESS WORKING GROUP, 1 Mayo 2004, páginas 0-11, XP002438609, describe codificación LDPC para OFDMA PHY para el estándar 802.16d.

Cláusulas que exponen aspectos adicionales y que son útiles para la comprensión de la presente invención

1. Un método para operar un transmisor que genera bits de verificación de paridad p = (p0, …, pm-1) en base a un conjunto de símbolos corriente s = (s0, …, sk-1) , incluyendo el método los pasos de:

recibir el conjunto de símbolos corriente s = (s0, …, sk-1) ;

usar una matriz H para determinar los bits de verificación de paridad; y

transmitir los bits de verificación de paridad junto con el conjunto de símbolos corriente;

donde H es una expansión de una matriz base Hb, incluyendo Hb una sección Hb1 y una sección Hb2, incluyendo Hb2 una primera parte que tiene una columna hb que tiene un peso impar superior a 2, e incluyendo una segunda parte H'b2 elementos de matriz para la fila i, columna j igual a

para i = j, 1 para i = j+1,

en otro caso;

donde la expansión de la matriz base Hb usa idénticas submatrices para 1s en cada columna de la segunda parte H'b2, y donde la expansión usa submatrices pareadas para un número par de 1s en hb; y

2. El método de la cláusula 1 donde Hb se expande sustituyendo cada entrada de Hb por una submatriz de tamaño 10 zxz para producir H.

3. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento cero de Hb por una submatriz cero de tamaño zxz para producir H.

4. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento no cero de Hb por una submatriz no cero para producir H.

5. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento no cero de Hb por una submatriz de permutación no cero para producir H. 20

6. El método de la cláusula 1, donde:

donde el vector hb tiene un peso impar wh> = 3.

7. Un aparato incluyendo:

1. Un método de codificar LDPC una secuencia de información s (s0, s1, ..., sk-1) de longitud k = kb * z usando una matriz modelo mb x nb Hbm, con elementos de matriz p (i, j) , i = 0, 1, …, mb-1 y j = 0, 1, …, nb-1, para obtener una secuencia de paridad p (p0, p1, …, pm-1) ' m = mb * z denotado por v, donde v = [v (0) v (1) … v (mb -1) ] y cada elemento de v es un vector de columna como v (i) = [piz piz+1 … p (i+1) z-1]T, I = 0, 1, …, mb-1,

incluyendo el método * dividir la secuencia de información s en kb = kb = nb-mb grupos de z bits denotados por u = [u (0) u (1) … u (kb - 1) ], donde cada elemento de u es un vector de columna como sigue

, i = 0, 1, …, kb-1;

* determinar v (0) por v (0) =

donde x denota el índice de fila de hbm donde la entrada tiene el único valor no negativo que se usa un número impar de veces dentro de hbm y hbm es la kb-ésima columna de la matriz modelo Hbm, donde una matriz de verificación de paridad del código LDPC es una expansión de la matriz modelo Hbm reproduciendo cada p (i, j) negativo por una matriz todo ceros zxz y cada p (i, j) no negativo por una matriz de permutación Pp (i, j) que es una matriz de identidad zxz cuyas columnas son circulares desplazadas por un tamaño de desplazamiento circular de p (i, j) a la derecha;

* determinar v (1) , v (2) , v (3) , …, v (mb-1) por 25

2. El método de la reivindicación 1, donde la matriz modelo incluye dos submatrices, [Hbm1 Hbm2], donde la primera matriz es de dimensión mb x kb, y Hbm2 es de dimensión mb x mb y además Hbm2 tiene la estructura siguiente y hay whº 3 entradas no negativas en hbm

3. El método de la reivindicación 1, donde el producto de la forma Pp (i, j) u (j) se implementa por un desplazador en 35 cilindro de tamaño z.