Diseño de LDPC estructurado con agrupación de filas de vector.

Un método para operar un transmisor que genera bits de comprobación de paridad p≥

{p0, ..., pm-1} en base a un conjunto de símbolo actual s≥{s0, ..., sk-1}, comprendiendo el método las etapas de:

recibir el conjunto de símbolo actual s≥{s0, ..., sk-1}

usar una matriz H para determinar los bits de comprobación de paridad, y

transmitir los bits de comprobación de paridad junto con el conjunto de símbolo actual;

en donde H es una expansión de una matriz de base Hb a través de una matriz modelo Hbm;

en donde Hb comprende mb filas, una sección Hb1 y una sección Hb2, y Hb2 comprende la columna hb que tiene un peso wh>≥3 y H'b2 que tiene una estructura de doble diagonal con elementos de matriz en la fila i, columna j, iguales a 1 para i≥j, 1 para i≥j+1, y 0 en cualquier otro caso,

caracterizado porque 1's de hb y de Hb1 están dispuestos de tal modo que se pueden formar mb/q grupos de filas de Hbm, teniendo cada grupo q filas, de modo que dentro de cada grupo las filas de Hbm tienen a lo sumo una única entrada no negativa dentro de una columna.

Diseño de LDPC estructurado con agrupación de filas de vector

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

Antecedentes de la invención

Según se ha descrito en la solicitud de Patente de Estados Unidos Serial núm. 1/839995, la cual se incorpora aquí por referencia, un código de comprobación de paridad de baja densidad (LDPC) es un código de bloque lineal especificado por medio de una matriz H de comprobación de paridad. En general, un código LDPC se define por medio de un Campo de Galois GF(q), q>2. Si q=2, el código es un código binario. Todos los códigos de bloque lineales pueden ser descritos como el producto de un vector de información de /c-bits siXk por una matriz generadora de código Gi«n para producir una clave x¡xn de n-bits donde la tasa de código es r=k/n. La clave x se transmite a través de un canal ruidoso, y el vector de señal y recibido se hace pasar hasta el descodificador para estimar el vector de información s¡xk-

Dado un espacio n-dimensional, las filas de G abarcan el subespacio C de clave /c-dimensional, y las filas de matriz Hmxn de comprobación de paridad abarcan el espacio dual C-1- m-dimensional, donde m = n-k. Puesto que x=sG y GHt=, se obtiene que xH- para todas las claves en el subespacio C, donde "T" (o "T") indica transposición de matriz. En la discusión de códigos LDPC, esto se escribe en general como:

HxT = T, (1)

donde es un vector fila de todo ceros, y la clave x=[s p] = [s, s-i,..., sp, p-i,..., pm-i], donde p,..., pm-i son bits de comprobación de paridad; y So,..., Sm 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 distintas de cero en H es baja, es decir, existe solamente un pequeño porcentaje de 1 s en H, lo que permite un mejor comportamiento de corrección de error y una descodificación más simple que usando una H densa. Una matriz de comprobación de paridad puede ser también descrita mediante un grafo bipartito. El grafo bipartito no es solamente una descripción gráfica del código sino también un modelo para el descodificador. En el grafo bipartito, un bit de clave (por lo tanto, cada columna de H) está representado por un nodo de variable en el lado izquierdo, y cada ecuación de comprobación de paridad (por lo tanto, cada fila de H) está representada por un nodo de comprobación en el lado derecho. Cada nodo de variable corresponde a una columna de H y cada nodo de comprobación corresponde a una fila de H, con "nodo de variable" y "columna" de H mencionados de forma intercambiable, como lo son "nodo de comprobación" y "fila" de H. Los nodos de variable están conectados solamente a nodos de comprobación, y los nodos de comprobación están conectados solamente a nodos de variable. Para un código con n bits de clave y m bits de paridad, el nodo de variable v, está conectado al nodo de comprobación c¡ por medio de un borde si el bit de clave / participa en la ecuación de comprobación j, i = , 1,..., n-1, _/ = , 1,..., m-1. En otras palabras, el nodo de variable i está conectado al nodo de comprobación j si la entrada h¡¡ de la matriz de comprobación de paridad H es 1. Reflejando la Ecuación (1), los nodos de variable representan una clave válida si todos los nodos de comprobación tienen paridad par.

A continuación se muestra un ejemplo que ilustra la relación entre la matriz de comprobación de paridad, las ecuaciones de comprobación de paridad, y el grafo bipartito. Supóngase una n = 12, el código de tasa 1/2 está definido por:

n

(2)

con la porción del lado izquierdo correspondiendo a k (= 6) bits de información s, la porción del lado derecho correspondiendo a m (= 6) bits de paridad p. Aplicando (1), la H en (2) define 6 ecuaciones de comprobación de paridad como sigue:

*+*2+*6+*7 =

jc, + x4 + x7 + x, = x2 + x5 + x6 + x + x9 = O x + Xj + x9 -i- x1 = o x, +x4 + x, +xM = x3 + Xj + x6 + X|! =

H tiene también el grato bipartito correspondiente mostrado en la Figura 1

(3)

El código LDPC general descrito con anterioridad puede no ser fácil de ¡mplementar en la práctica. Con frecuencia se introducen estructuras en la matriz de comprobación de paridad para permitir una rápida codificación y descodificación sin sacrificar el comportamiento de corrección de error. Un diseño de código LDPC estructurado empieza con una pequeña matriz de base Hb binaria de m* x nb, hace z copias de Hb, e interconecta las z copias para formar una gran matriz H de m x n, donde m = mb x z, n = n* x z. Usando la representación de matriz, para construir una H a partir de Hb, cada 1 en Hb se sustituye por una submatriz de permutación zxz, y cada en Hb se sustituye por una submatriz de todo cero zxz. La representación de la expansión de Hb se denomina matriz modelo y se indica mediante Hbm. Así, Hbm es simplemente una notación abreviada para H cuando z es conocido. Este procedimiento mapea esencialmente cada borde de Hb respecto a un borde de vector de longitud z en H, cada nodo de variable de Hb respecto a un nodo de variable de vector de longitud z en H, y cada nodo de comprobación de Hb respecto a un nodo de comprobación de vector de longitud z en H. Para un LDPC estructurado, la submatriz de zxz puede ser una matriz de permutación, una suma de matrices de permutación, o cualquier tipo de matriz binaria. Puesto que una matriz de permutación P tiene un solo 1 en cada fila y un solo 1 en cada columna, la distribución de peso de la matriz H expandida es la misma que en la matriz de base Hb si se usa la submatriz de permutación. Por lo tanto, la distribución de peso de Hb se elige tan próxima a la distribución de peso final deseada como sea posible. Las submatrices de permutación que comprenden H pueden ser muy simples sin comprometer el rendimiento, tal como desplazamientos cíclicos simples y/o inversiones de bits. En el caso de desplazamientos cíclicos, se puede escribir Hbm sustituyendo los 1 s en Hb por números enteros no negativos que representan la magnitud del desplazamiento y los s en Hb se sustituyen por 1. En el transmisor, un vector u de k bits de información se codifica en base a H (o equivalentemente Hbm) para producir un vector xden bits de código, donde k=n-m=zxkb, kb = (nb - mb). El vector x se envía a través de un canal ruidoso y se recibe un vector y de n señales contaminadas. En el receptor, el descodificador de LDPC intenta estimar x en base al vector y recibido y a la matriz H de comprobación de paridad. El receptor obtiene una versión y contaminada de la clave x transmitida. Para descodificar y, y estimar la secuencia s de información original, un algoritmo de descodificación iterativa, tal como propagación de suma producto, se aplica normalmente en base al grafo bipartito. Información blanda en formato de relaciones de probabilidad de inicio de sesión (LLR) de los bits de clave, se hace pasar entre el banco de nodos de variable y el banco de nodos de comprobación. La iteración se detiene ya sea cuando todas las ecuaciones de comprobación han sido satisfechas o ya sea cuando se alcanza un límite de iteración máximo permitido.

Los códigos LDPC estructurados pueden ser descodificados también con un descodificador por capas. Un descodificador por capas tiene típicamente hardware para procesar una fila entera de una sola vez. El descodificador por capas puede reducir potencialmente el número de iteraciones requeridas para conseguir un nivel de rendimiento dado, e incrementar potencialmente el rendimiento si no existe hardware suficiente para procesar todas las filas de bloque de una sola vez. También se puede usar... [Seguir leyendo]

1.- Un método para operar un transmisor que genera bits de comprobación de paridad p={po, pm-i} en base a un conjunto de símbolo actual s={s,..., sm}, comprendiendo el método las etapas de:

recibir el conjunto de símbolo actual s={so, s^}

usar una matriz H para determinar los bits de comprobación de paridad, y

transmitir los bits de comprobación de paridad junto con el conjunto de símbolo actual;

en donde H es una expansión de una matriz de base Hb a través de una matriz modelo Hbm;

en donde Hb comprende mb filas, una sección Hm y una sección Hb2, y Hb2 comprende la columna hb que tiene un peso Wh>=3 y Hb2 que tiene una estructura de doble diagonal con elementos de matriz en la fila /', columna j, iguales a 1 para /=_/, 1 para /=y+1, y en cualquier otro caso,

caracterizado porque 1 s de hb y de Hm están dispuestos de tal modo que se pueden formar rrib/q grupos de filas de Hbm, teniendo cada grupo q filas, de modo que dentro de cada grupo las filas de Hbm tienen a lo sumo una única entrada no negativa dentro de una columna.

2.- El método de la reivindicación 1, en donde las filas de la matriz modelo Hbm pueden ser permutadas de tal modo que cada dos filas consecutivas no intersecten.

3.- El método de la reivindicación 1, en donde, cuando se expande la matriz de base Hb a matriz de comprobación de paridad H, se usan submatrices idénticas para cada uno de los 1s en cada columna de Hb2, y la expansión usa submatrices apareadas para un número par de 1 s en hb.

4 - El método de la reivindicación 3, en donde las submatrices son zxz matrices de identidad desplazadas.

5.- Un aparato que comprende:

medios de almacenamiento para almacenar una matriz H; y,

lógica digital que recibe un bloque de información s=(so,..., Sm), que determina bits de comprobación de paridad p=(p, pm.i) en base al conjunto de símbolo actual s = (so,..., sm) y a la matriz H, y que

transmite los bits de comprobación de paridad junto con el conjunto de símbolo actual;

en donde H es una expansión de una matriz de base Hb a través de una matriz modelo Hbm,

en donde Hb comprende rrib filas, una sección Hbi y una sección Hb2, y Hb2 comprende la columna hb que tiene un peso wb>=3 y Hb2 que tiene una estructura de doble diagonal con elementos de matriz en la fila /, columna j, iguales a 1 para /=_/, 1 para i=j+1, y en cualquier otro caso;

caracterizado porque los 1 s de hb y Hm están dispuestos de tal modo que se pueden formar mt/q grupos de filas de Hbm, teniendo cada grupo q filas, de modo que dentro de cada grupo las filas de Hbm tienen a lo sumo una única entrada no negativa dentro de una columna.

6.- El aparato de la reivindicación 5, en donde filas de la matriz modelo Hbm pueden ser permutadas de tal modo que cada dos filas consecutivas no intersecten.

7.- El aparato de la reivindicación 5, en donde, cuando se expande la matriz de base Hb hasta matriz de comprobación de paridad H, se usan submatrices idénticas para cada uno de los 1 s en cada columna de Hb2, y la expansión usa submatrices apareadas para un número par de 1 s en hb.

8.- El aparato de la reivindicación 7, en donde las submatrices son zxz matrices de identidad desplazadas.

9.- Un método para operar un receptor que estima un bloque información s=(s,..., sm), comprendiendo el método las etapas de:

recibir un vector de señal;

estimar el bloque de información s=( So,..., sm) en base al vector de señal recibido y a una matriz de comprobación de paridad H;

en donde H es una expansión de una matriz de base Hb a través de una matriz modelo Hbm,

en donde Hb comprende mb filas, una sección Hm y una sección Hb2, y Hb2 comprende la columna hb que tiene el peso wb>=3 y Hb2 que tiene una estructura de doble diagonal con elementos de matriz en la fila /, columna j, iguales a 1 para /=_/, 1 para i=j+1, y en cualquier otro caso;

caracterizado porque 1 s de hb y de Hbi están dispuestos de tal modo que se pueden formar rrib/q grupos de las filas de Hbm teniendo cada grupo q filas de modo que dentro de cada grupo las filas de Hbm tienen a lo sumo una única entrada no negativa dentro de una columna.

1.- El método de la reivindicación 9, en donde filas de la matriz modelo Hbm pueden ser permutadas de tal modo 5 que cada dos filas consecutivas no intersecten.

11.- El método de la reivindicación 9, en donde, cuando se expande la matriz de base Hb hasta matriz de comprobación de paridad H, se usan submatrices idénticas para cada uno de los 1 s en cada columna de Hb2 y la expansión usa submatrices apareadas para un número par de 1 s en hb.

12.- Un aparato que comprende:

medios de almacenamiento para almacenar una matriz H; y,

lógica digital que recibe un vector de señal y que estima el bloque de información s=(s,..., sk-i), en base al vector de señal recibido y a la matriz H;

en donde H es una expansión de una matriz de base Hb a través de una matriz modelo Hbm,

en donde Hb comprende mb filas, una sección Hbi y una sección Hb2, y Hb2 comprende la columna hb que 15 tiene un peso wb>=3 y Hb2 que tiene una estructura de doble diagonal con elementos de matriz en la fila /,

columna j, iguales a 1 para ¡=j, 1 para ¡=¡+1, y en cualquier otro caso;

caracterizado porque los 1 s de hb y Hm están dispuestos de tal modo que se pueden formar rru/q grupos de las filas de Hbm, teniendo cada grupo q filas, de modo que dentro de cada grupo las filas de Hbm tienen a lo sumo una única entrada no negativa dentro de una columna.

13.- El aparato de la reivindicación 12, en donde las filas de la matriz modelo Hbm pueden ser permutadas de tal

modo que dos filas consecutivas no intersecten.