Construcción de códigos para códigos LDPC acortados irregulares con buen rendimiento.

Un método para codificar que genera bits de comprobación de paridad (p0,

..., pm-1) basándose en unconjunto de símbolos de comprobación de paridad de baja densidad actual s≥(s0, ..., sk-L-1), comprendiendo elmétodo las etapas de:

adquirir un valor L;

obtener el conjunto de símbolos actual s ≥ (s0, ..., sk-L-1) de longitud (k-L);

obtener un vector s de información relleno con ceros de longitud k mediante rellenando con ceros del conjunto desímbolos actual con L ceros, donde L>0;

utilizar una matriz H y el vector s de información relleno mediante rellenado con ceros para determinar los bits decomprobación de paridad, donde H comprende una sección H1 y una sección H2 y H1 tiene el tamaño m por k y H2tiene el tamaño m por m; y

transmitir los bits de comprobación de paridad junto con el conjunto de símbolos actual s ≥ (s0, ..., sk-L-1);caracterizado por que H1 consiste en dos sub-matrices;

comprendiendo una de las dos sub-matrices columnas que tienen un primer peso de columna y columnas que tienenun segundo peso de columna, siendo el primer peso de columna diferente del segundo peso de columna, estandolas columnas del primer peso de columna y las columnas del segundo peso de columna substancialmenteentrelazados en la sub-matriz; y

comprendiendo la otra de las dos sub-matrices columnas que tienen el primer peso de columna y columnas quetienen el segundo peso de columna, estando las columnas del primer peso de columna y las columnas del segundopeso de columna substancialmente entrelazados en la sub-matriz.

Construcción de códigos para códigos LDPC acortados irregulares con buen rendimiento Campo de la Invención La presente invención se refiere generalmente a la codificación de datos y en particular, a un método para codificar datos utilizando códigos de comprobación de paridad de baja densidad (LDPC – Low Density Parity Check, en inglés) .

Antecedentes de la Invención Un código de comprobación de paridad de baja densidad (LDPC - Low Density Parity Check, en inglés) se define mediante una matriz H de comprobación de paridad, que es una matriz binaria pseudoaleatoria de baja densidad. Por razones de implementación, una sola matriz H es a veces preferida aunque deben soportarse múltiples tasas de código y tamaños de bloque. En este caso, las múltiples tasas de código pueden ser obtenidas acortando un código de LDPC sistemático.

En un código sistemático que mapea k bits de información a n bits codificados, los primeros k bits de los bits codificados son los bits de información. Cuando se realiza el acortamiento, L de los bits de información son puestos a cero y los correspondientes ceros son eliminados de los bits codificados. El acortamiento es llevado a cabo típicamente (lógica o físicamente) poniendo los primeros L bits de información a cero. En algunos codificadores, los ceros directores no cambian el estado del codificador, para que los ceros no tengan que ser proporcionados al circuito de codificación. Para un código de LDPC, el acortamiento poniendo los primeros L bits de información a cero puede lograrse de dos maneras equivalentes. Primero, un vector de información de k bits puede ser puesto con L bits como cero, que se asume que están situados en las posiciones de los primeros L bits de información en lo que sigue sin que se pierda la generalidad. El vector de información de longitud k puede ser proporcionado al codificador (que puede estar basado en la matriz H de (n-k) por n no acortada o en la matriz generadora G de k por n equivalente) , y los L ceros subsiguientemente separados de los bits codificados tras la codificación. En segundo lugar, un vector de información acortado puede ser pasado al codificador que codifica basándose en una matriz H de (n-k) por (n-L) acortada con las primeras L columnas eliminadas, o la matriz G de (k-L) por (n-L) acortada equivalente. No obstante, el código o los códigos de LDPC acortado o acortados resultante o resultantes, es probable que tenga o tengan un bajo rendimiento porque su distribución de peso puede ser inferior a un código particularizado diseñado para esa tasa de código y tamaño de bloque. No está claro cómo construir un código de LDPC acortado que mantenga un buen rendimiento.

El satélite de transmisión de video digital estándar (DVB-S2) utiliza códigos de LDPC, y define una matriz H para cada tasa de código deseada. El DVB-S2 define diez tasas de código de LDPC diferentes, 1/4, 1/3, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 8/9 y 9/10, todas con una longitud de bloque codificado de n = 64800 bits. Para cada tasa de código, se especifica una matriz H de comprobación de paridad diferente – no se utiliza el acortamiento en el estándar. Como es conocido en el sector los códigos de LDPC irregulares ofrecen un mejor rendimiento que los códigos de LDPC regulares. El término regular cuando se utiliza para un código de LDPC significa que todas las filas de H tienen el mismo número de 1’s, y todas las columnas de H tienen un mismo número de 1’s, donde el número de 1’s en una fila o columna se denomina también el peso de la fila o columna. Si no el código de LDPC es considerado irregular. En un sentido más estricto, el término regular puede ser también aplicado bien a las filas o bien a las columnas (es decir, una matriz puede tener pesos de columna regulares, pero pesos de fila irregulares) , y puede ser también aplicado a una sub-matriz de una matriz (por ejemplo, una sub-matriz de una matriz es regular cuando todas las columnas de la sub-matriz tienen el mismo peso de columna y todas las filas de la sub-matriz tienen el mismo peso de fila) . Debido a que se desean códigos irregulares para un buen rendimiento, el DVB-S2 define múltiples matrices H, cada una con una distribución de peso deseada para un buen rendimiento y esa tasa de código. Los números de columnas de cada peso se muestran en la Tabla 1 para todas las tasas de código del DVB-S2.

Tabla 1. Número de Columnas de Varios Pesos en DVB.

Tasa de Código 13 12 11 8 4 3 2 1

1/4 5400 10800 48599 1

1/3 7200 14400 43199 1

1/2 12960 19440 32399 1

3/5 12960 25920 25919 1

2/3 4320 38880 21599 1

3/4 5400 43200 16199 1

4/5 6480 45360 12959 1

5/6 5400 48600 10799 1

8/9 7200 50400 7199 1

9!10 6480 51840 6479 1

Algunos diseños de código, tales como el código de LDPC de Intel propuesto para el para 802.16, sólo tienen una matriz H y utilizan el acortamiento para obtener otras tasas de código, pero los códigos tras el acortamiento no se comportan muy bien. La porción de H correspondiente a los bits de información (denotada por H1) es regular (y por lo tanto toda la matriz se denomina a veces semi-regular) , y tras el acortamiento la distribución de peso del código es mala comparada con un buen diseño. Los buenos diseños de LDPC tienden a no tener un peso de columna regular en H1.

LIY et al: “Design of Efficiently Encodable Moderate-Length High-Rate Irregular LDPC Codes” IEEE TRANSACTIONS ON COMUNICATIVOS, IEEE SERVICE CENTER, PISCATA WAY, NJ, US, vol. 52, nº 4, 1 de Abril de 2004 (2004-04-01) , páginas 564-571, XP011111852 ISSN: 0090-6778, describe métodos de acuerdo con el preámbulo de la reivindicación 1.

TIFFANY JING LI, RUIYUAN HU: “Robust Distributed Source Encoding using LDPC Codes” Marzo de 2004 (200403) , página 1, XP002506615 Lehigh University, muestra un código de LDPC acortado.

Breve Descripción de los Dibujos La FIG. 1 muestra una distribución de peso de columna de una matriz de comprobación de paridad con peso de columna no-entrelazada en H1, es decir, las columnas del mismo peso están agrupadas. El tamaño del código es (2000, 1600) .

La FIG. 2 muestra una distribución de peso de columna de una matriz de comprobación de paridad con peso de columna entelazado en H1. El tamaño del código es (2000, 1600) .

La FIG. 3 muestra el rendimiento de FER de códigos no acortados de tamaño (2000, 1600) .

La FIG. 4 muestra el rendimiento de FER de los códigos de (1200, 800) acortados de los códigos de (2000, 1600) en 800 bits.

La FIG. 5 muestra el rendimiento de FER de los códigos de (800, 400) acortados de los códigos de (2000, 1600) en 1200 bits.

Descripción Detallada de los Dibujos Esta invención propone y utiliza una matriz H irregular que se comporta bien no acortada o acortada. La matriz y sus versiones acortadas pueden ser utilizadas para codificación y descodificación. voy aquí (0009

Para un código que toma k bits de información y genera n bits de código, la matriz H se divide en dos partes H = [H1 H2], donde H1 tiene un tamaño de m por k y H2 tiene un tamaño de m por m, m=n-k. H1 corresponde a los bits de información no acortados y H2 corresponde a los bits de paridad, de manera que . Cuando se acortan las primeras L posiciones de s, las primeros L columnas de H1 son esencialmente eliminadas.

H1 es determinística porque está definida una estructura de peso de columna particular. H2 es no determinística porque puede ser regular o irregular, tener cualquier estructura o estar construida aleatoriamente. Una H2 preferida puede ser similar a la descrita en la Solicitud de Patente de US Nº 10/839995 “Method And Apparatus For Encoding And Decoding Data” en la propuesta de LDPC de Intel para 802.16 (aproximadamente triangular inferior, teniendo todas las columnas peso 2 excepto la última columna que tiene peso 1, los 1’s de una columna están sobre cada uno de ellos, el 1 superior está en la diagonal. Matemáticamente la matriz H2 de m por m se describe siendo la entrada de la fila i columna j 1 si i=j, e i=j+1, 0<=i<=m-1, 0<=j<=m-1.)

Un ejemplo de la matriz H2 es:

. Donde h es peso desigual > 2, y puede ser h=[1 0 0 0 1 0 0 0 1 0 … 0]T. Otra realización de ejemplo de H2 es . 5

Para códigos irregulares que tienen un mejor rendimiento que los códigos regulares, las columnas de varios pesos pueden estar dispuestas en cualquier orden sin afectar al rendimiento, puesto que permutar el orden de los bits de código no afecta al rendimiento en la corrección de error. Los pesos de columna están por tanto típicamente distribuidos sin ningún orden particular. Por ejemplo, todas las... [Seguir leyendo]

1. Un método para codificar que genera bits de comprobación de paridad (p0, …, pm-1) basándose en un conjunto de símbolos de comprobación de paridad de baja densidad actual s= (s0, …, sk-L-1) , comprendiendo el método las etapas de:

adquirir un valor L;

obtener el conjunto de símbolos actual s = (s0, …, sk-L-1) de longitud (k-L) ;

obtener un vector s de información relleno con ceros de longitud k mediante rellenando con ceros del conjunto de símbolos actual con L ceros, donde L>0;

utilizar una matriz H y el vector s de información relleno mediante rellenado con ceros para determinar los bits de comprobación de paridad, donde H comprende una sección H1 y una sección H2 y H1 tiene el tamaño m por k y H2 tiene el tamaño m por m; y

transmitir los bits de comprobación de paridad junto con el conjunto de símbolos actual s = (s0, …, sk-L-1) ;

caracterizado por que H1 consiste en dos sub-matrices;

comprendiendo una de las dos sub-matrices columnas que tienen un primer peso de columna y columnas que tienen un segundo peso de columna, siendo el primer peso de columna diferente del segundo peso de columna, estando las columnas del primer peso de columna y las columnas del segundo peso de columna substancialmente entrelazados en la sub-matriz; y

comprendiendo la otra de las dos sub-matrices columnas que tienen el primer peso de columna y columnas que tienen el segundo peso de columna, estando las columnas del primer peso de columna y las columnas del segundo 20 peso de columna substancialmente entrelazados en la sub-matriz.

2. El método de la reivindicación 1, en el que:

3. El método de la reivindicación 1, en el que:

.