ES2300716T3

ES2300716T3 - Metodo y sistema para la codificacion de codigos de verificacion de paridad de baja densidad (ldpc) de longitud de bloque corto.

Info

Publication number: ES2300716T3
Application number: ES04255344T
Authority: ES
Inventors: Mustafa Eroz; Feng-Wen Sun; Lin-Nan Lee
Original assignee: DirecTV Group Inc
Current assignee: AT&T MVPD Group LLC
Priority date: 2003-09-04
Filing date: 2004-09-03
Publication date: 2008-06-16
Anticipated expiration: 2024-09-03
Also published as: KR100619206B1; DK1513258T3; US8028224B2; EP1513258B9; US20050060635A1; US7334181B2; CN100382472C; CA2480145A1; HK1076673A1; CA2480145C; EP1513258B1; JP2005102201A; DE602004011861D1; EP1513258A2; US7673226B2; JP3917617B2; KR20050025085A; US20080082894A1; DE602004011861T2; CN1619997A

Abstract

Un transmisor (200) para respaldar la transmisión de una señal codificada de verificación de paridad de baja densidad LDPC, comprende: un codificador de verificación de paridad de baja densidad LDPC (203) configurado para entregar, basado en los bits de información recibida, un código LDPC; un dispositivo de entrelazado de bit (213) y un modulador (205) configurado para modular la señal codificada de LDPC según una constelación de señal que incluye una modulación por desplazamiento de fase 8-PSK; caracterizado en que el dispositivo de entrelazado de bits (213) está configurado para entrelazar los bits de salida del código LDPC escribiendo los datos en serie por columna asociados con el código LDPC en una tabla y leyendo los datos por filas de derecha a izquierda, donde la señal codificada de LDPC representa el código LDPC entrelazado, y el codificador LDPC (203) está configurado para entregar el código LDPC con un índice de código 3/5 y para generar el código LDPC por acumulación de los bits de información recibida en las direcciones de bits de paridad, las direcciones de bits de paridad estando decididas basado en siguiente tabla especificando direcciones de acumuladores de bits de paridad: (Ver tabla)

Description

Método y sistema para la codificación de códigos de verificación de paridad de baja densidad (LDPC) de longitud de bloque corto.

Campo de la invención

El invento actual está relacionado con los sistemas de comunicaciones y más específicamente a los sistemas codificados.

Antecedentes de la invención

Los sistemas de comunicación emplean la codificación para asegurar una comunicación confiable a través de canales de comunicaciones ruidosos. Por ejemplo, en un sistema inalámbrico (o de radio), como una red satelital, las fuentes de ruido abundan, de factores geográficos y ambientales. Estos canales de comunicación exhiben una capacidad fija que se puede expresar en términos de bits por símbolo, en cierta relación señal/ruido (SNR), definiendo un límite superior teórico (conocido como el límite de Shannon). Consecuentemente, la codificación de diseño ha apuntado a lograr índices que se acercan al límite de Shannon. Este objetivo es particularmente útil para los sistemas satelitales limitados en ancho de banda. Uno de los códigos que se acercan al límite de Shannon es el código de verificación de paridad de baja densidad (LDPC).

Tradicionalmente, no se han instalado extensamente los códigos LDPC debido a un número de desventajas. Una desventaja es que la técnica de codificación de LDPC es muy compleja. La codificación de un código de LDPC que usa su matriz de generador requeriría almacenar una matriz dispersa muy grande. Además, los códigos de LDPC requieren que los bloques grandes sean eficaces; por lo tanto, aunque las matrices de verificación de paridad de los códigos de LDPC son dispersas, es un problema almacenar estas matrices.

Desde la perspectiva de la implementación, se enfrentan un número de retos. Por ejemplo, el almacenamiento es una razón importante por la que los códigos de LDPC no han llegado a ser extensos en la práctica. Por consiguiente, la longitud de los códigos de LDPC requiere un mayor espacio de almacenamiento. También, un reto clave en la implementación del código de LDPC ha sido cómo lograr la red de conexión entre varios motores de proceso (nodos) en el decodificador. Además, la carga de cómputo en el proceso de decodificación, específicamente las operaciones del nodo de verificación, plantea un problema.

Le Goff S.Y.: "Channel capacity of bit-interleaved coded modulation scheme using 8-ary signal constellations", IEE Electronic Letters, vol. 38, no. 4, 14 de febrero de 2002 (XP006017828) que describe la modulación codificada de bit entrelazado con las constelaciones de señal 8-aria.

Le Goff S.Y.: "Signal constellations for bit-interleaved coded modulation", IEEE Trans. on Inf Theory, vol. 49, No. 1, enero de 2003, páginas 307-313 describe la modulación codificada de bit entrelazado utilizado junto con los códigos turbo.

Le Goff S.Y.: "Signalling constellations for power-efficient bit-interleaved coded modulation schemes", IEE PROCEEDINGS: COMMUNICATIONS, INSTITUTION OF ELECTRICAL ENGINEERS, GB, 13 de junio de 2003, páginas, 141-148 (XP006020428) que describe constelaciones de señal diferentes para los esquemas de modulación codificada de entrelazado de bit.

Hou J. et al.: "Capacity-approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes", IEEE Trans. on Inform Theory, vol. 49, No. 9, páginas 2141-2155 que describe los esquemas de modulación codificada de ancho de banda eficiente basados en los códigos de verificación de paridad de baja densidad (LDPC).

Richardson T.: "The renaissance of Gallager's low-density parity-check codes", IEEE Communications Magazine, agosto de 2003, páginas 126-131 (XP001177711) que revela información de 20 antecedentes de los códigos de verificación de paridad de baja densidad (LDPC).

Calzolari G.P.: "Report on DVB-S2 channel coding standardization effort", CCSDS Sub-Panel 1B Channel Coding, 7 de abril de 2003, Matera, Italia (XP002311762) que analiza la posibilidad del uso de varios esquemas de modulación en conjunto con los códigos de verificación de paridad de baja densidad (LDPC).

Todavía hay la necesidad de un sistema de comunicación LDPC que utilice procesos de codificación y decodificación sencillos. También hay la necesidad del uso eficiente de los códigos LDPC para admitir altas velocidades de datos sin introducir complejidades mayores. También está la necesidad de mejorar el rendimiento de los codificadores y decodificadores de LDPC. También está la necesidad de minimizar los requerimientos de almacenamiento para la implementación de la codificación LDPC.

Resumen de la invención

La actual invención trata éstas y otras necesidades, donde se proporciona un enfoque para codificar códigos de la verificación de paridad de baja densidad (LDPC). Un codificador genera un código de LDPC que tiene un código externo Bose Chaudhuri Hocquenghem (BCH) según una de las tablas 2-8 para la transmisión como la señal codificada LDPC. Cada una de las tablas 2-8 especifica la dirección de los acumuladores de bit de paridad. Se producen los códigos cortos de LDPC con la utilización de los códigos matrices de LDPC que se basan en las tablas 2-8. k_{ldpc} de los bits codificados BCH que están precedidos por ceros ficticios k_{m}-k_{ldpc}. Los bits resultantes se codifican sistemáticamente para generar los bits n_{m}. Se borran los primeros ceros ficticios k_{m}-k_{ldpc} para lograr un código reducido. Para un código LDPC con índice de código de 3/5 que utiliza la modulación 8-PSK (modulación por desplazamiento de fase), un dispositivo de entrelazado asegura los bits de entrelazado del código LPDC de salida con la escritura en serie de los datos asociados con el código LDPC por columnas en una tabla y leyendo los datos por filas de derecha a izquierda. El enfoque proporciona una codificación conveniente ventajosa así como la decodificación de los códigos, mientras se minimizan los recursos de almacenamiento y de procesamiento.

Un aspecto de la presente invención es un método para respaldar transmisión de una señal de verificación de paridad de baja densidad (LDPC) como especificado en las reivindicaciones agregadas.

Según otro aspecto de una presentación de la actual invención, se transmite la señal codificada LDPC modulada por un enlace de satélite en favor de una aplicación satelital de banda ancha.

Son evidentes todavía otros aspectos, características y ventajas de la actual invención de la descripción detallada siguiente, simplemente con la ilustración de un número de presentaciones e implementaciones determinadas, con la inclusión del mejor modo contemplado para realizar la actual invención. La actual invención es también capaz de otras y de diversas presentaciones y se pueden modificar sus varios detalles en los varios aspectos obvios, todos sin salir del rango de la actual invención. Por consiguiente, se deben considerar el dibujo y la descripción como puramente ilustrativos y no como restrictivos.

Breve descripción de los dibujos

La presente invención se ilustra por medio de un modo de ejemplo y no limitándola de esta manera, en las figuras de los dibujos que la acompañan y en los cuáles los números de referencia se refieren a elementos similares y en los que:

La fig. 1 es un diagrama de un sistema de comunicaciones configurado para utilizar los códigos de verificación de paridad de baja densidad (LDPC), según una presentación de la actual invención;

Las figs. 2A y 2B son diagramas de decodificadores LDPC de ejemplo desplegado en el transmisor de la fig. 1:

Las figs. 2C y 2D son diagramas de flujo de los procesos de codificación del codificador LDPC de la fig. 2B para generar códigos de LDPC de longitud de trama corta, según una presentación de la actual invención;

La fig. 3 es un diagrama de un receptor de ejemplo en el sistema de la fig.1;

La fig. 4 es un diagrama de una matriz dispersa de verificación de paridad, según una presentación de la actual invención;

La fig. 5 es un diagrama de un gráfico dividido en dos partes de un código LDPC de la matriz de la fig.4;

La fig. 6 es un diagrama de una submatriz de una matriz dispersa de verificación de paridad, donde la submatriz contiene valores de la verificación de paridad restringida a la región triangular inferior, según una presentación de la actual invención;

La fig. 7 es un gráfico de rendimiento de los códigos de LDPC en los varios índices de código y los esquemas de modulación admitidos por el transmisor de la fig. 2B;

La fig. 8 es un gráfico de rendimiento de los códigos cortos de LDPC en los varios índices de código y los esquemas de modulación admitidos por el transmisor de la fig. 2B; y

La fig. 9 es un diagrama de un sistema informático que puede realizar el proceso de codificación de LDPC, según las presentaciones de la actual invención.

Descripción de la presentación preferida

Se describen un sistema, un método y un software para la codificación eficiente de los códigos de la verificación de paridad de baja densidad (LDPC) de longitud de trama corta. En la siguiente descripción, para propósitos de explicación, se disponen los numerosos detalles específicos para proporcionar a una comprensión completa de la actual invención. Es evidente, sin embargo, para el experto en la técnica que se puede practicar la actual invención sin estos detalles específicos o con un arreglo equivalente. En otros casos, se muestran las estructuras y los dispositivos bien conocidos en forma de un diagrama en bloque para evitar confusiones innecesarias de la actual invención.

La fig. 1 es un diagrama de un sistema de comunicaciones configurado para utilizar los códigos de verificación de paridad de baja densidad (LDPC), según una presentación de la actual invención. Un sistema de comunicaciones digital 100 incluye un transmisor 101 que genera formas de onda de la señal a través de un canal de comunicaciones 103 a un receptor 105. En este sistema de comunicaciones discreto 100, el transmisor 101 tiene una fuente de mensaje que produce un conjunto discreto de mensajes posibles; cada uno de los mensajes posibles tiene una forma de onda correspondiente de la señal. Se atenúan o de lo contrario se alteran estas formas de onda de la señal por el canal de comunicaciones 103. Para combatir el canal de ruido 103, se utilizan los códigos de LDPC.

A modo de ejemplo, el canal 103 es un enlace satelital que sirve a terminales satelitales (por ejemplo, terminales de apertura muy pequeñas (VSATs)) en favor de las aplicaciones satelitales de banda ancha. Estas aplicaciones incluyen transmisiones satelitales y servicios interactivos (y en conformidad con Transmisión de Vídeo Digital (DVB) - norma S2). Se ha adoptado ampliamente en todo el mundo la norma de transmisión de vídeo digital por satélite (DVB-S) para proporcionar, por ejemplo, la programación de televisión digital por satélite.

Los códigos de LDPC que son generados por el transmisor 101 permiten la implementación de alta velocidad sin incurrir en ninguna pérdida del rendimiento. La salida estructurada de estos códigos de LDPC del transmisor 101 evita la asignación de un número pequeño de nodos de verificación a los nodos de bit ya vulnerables a los errores de canal en virtud del esquema de la modulación (por ejemplo, 8-PSK).

Estos códigos LDPC tienen un algoritmo de decodificación que se pueden poner en paralelo (a diferencia de los códigos turbo), que implica de forma ventajosa operaciones sencillas como la adición, la comparación y la búsqueda en tablas. Además, los códigos LDPC cuidadosamente diseñados no presentan ninguna señal de base de error.

Según una presentación de la actual invención, el transmisor 101 genera, con una técnica de codificación relativamente simple, códigos de LDPC basados en las matrices de verificación de paridad (que facilitan un acceso a memoria eficiente durante la decodificación) para comunicarse con el receptor 105. El transmisor 101 emplea los códigos de LDPC que pueden superar códigos concatenados de turbo+RS (Reed-Solomon), siempre que la longitud del bloque sea suficientemente grande.

Las figs. 2A y 2B son diagramas de codificadores de ejemplo de LDPC desplegados en el transmisor de la fig. 1. Según lo visto en la fig. 2A, un transmisor 200 está equipado con un codificador 203 de LDPC que valida la entrada de información de una fuente de información 201 y saque la secuencia codificada de una redundancia mayor conveniente para el procesamiento de corrección de error en el receptor 105. La fuente de información 201 genera las señales k de un alfabeto discreto, X. Se especifican los códigos de LDPC con las matrices de verificación de paridad. Por otro lado, la codificación de los códigos LDPC requiere, por lo general, la especificación de las matrices del generador. Aunque es posible obtener las matrices del generador de las matrices de verificación de paridad usando la eliminación Gaussiana, la matriz resultante ya no es dispersa y puede ser complejo almacenar una matriz grande de generador.

El codificador 203 genera señales del alfabeto Y a un modulador 205 con una técnica de codificación sencilla que utiliza solamente la matriz de verificación de paridad con la imposición de una estructura en la matriz de verificación de paridad. Específicamente, se pone una restricción en la matriz de verificación de paridad obligando a que cierta porción de la matriz sea triangular. Se describe más detalladamente la construcción de esta matriz de verificación de paridad a continuación en la fig. 6. Esta restricción da lugar a una pérdida insignificante del rendimiento y por lo tanto, constituye una atractiva compensación.

El modulador 205 asocia los mensajes codificados del codificador 203 a las formas de onda de la señal que se transmiten a una antena 207 de transmisión, que emite estas formas de onda por el canal de comunicaciones 103. Por consiguiente, los mensajes codificados se modulan y se distribuyen a una antena 207 de transmisión. Las transmisiones de la antena 207 de transmisión se propagan a un receptor (mostrado en fig. 3), según lo discutido a continuación.

La fig. 2B muestra un codificador de LDPC utilizado con un codificador de Bose Chaudhuri Hocquenghem (BCH) y un codificador de comprobación de redundancia cíclica (CRC), según una presentación de la actual invención. En estas circunstancias, los códigos generados por el codificador 203 de LDPC, junto con el codificador 209 de CRC y el codificador 211 de BCH, tienen un código externo concatenado de BCH y código interno de verificación de paridad de baja densidad (LDPC). Además, se logra la detección de error con los códigos de comprobación de redundancia cíclica (CRC). El codificador CRC 209, en una presentación de ejemplo, codifica con un código CRC de ocho bits con un generador polinómico (x^{5}+x^{4}+x^{3}+x^{2}+1)(x^{2}+x+1)(x+1). Se saca el código CRC al codificador BCH 211.

El codificador LDPC 203 codifica sistemáticamente un bloque de información de tamaño K_{lpdc}, i = (i_{0}, i_{1}, ..., i_{klpdc-1}) en una palabra codificada de tamaño n_{ldpc}, c = (i_{0}, i_{1}, ..., i_{kldpc-1}, p_{0},p_{1}, ..., p_{nlpdc - kldpc-1}). La transmisión de la palabra de código comienza en el orden dado de i_{0} y termina con p_{nldpc-kldpc-1}. Se dan los parámetros del código LDPC en la siguiente tabla 1.

TABLA 1

1

La tarea del codificador LDPC 203 es determinar los bits de paridad n_{ldpc} - k_{ldpc} (p_{0}, p_{1},.., p_{nldpc-kldpc-1}) para cada bloque k_{ldpc} de bits de información (i_{0}, i_{1}, ..., i_{kldpc-1}). El procedimiento es de la siguiente manera. Primeramente, se inician los bits de paridad; p_{0} = p_{1} = p_{2} = ... = p_{nldpc-kldpc-1} = 0. El primer bit de información, i_{0}, se acumula en la dirección del bit de paridad especificado en la primera fila de las tablas 2-8. Por ejemplo, para el índice 2/3 (tabla 4), los resultados son siguientes:

2

(Todas las adiciones están en GF(2)).

Entonces, para los siguientes 356 bits de información, i_{m,},m =1,2,...,359, estos bits se acumulan en las direcciones de los bits de paridad {x + m mod 360 x q} mod(n_{ldpc} - k_{ldpc}) donde x es la dirección del bit de paridad del acumulador de bit de paridad correspondiente al primer bit i_{0} y q es una constante dependiente del índice de código especificado en la tabla 9. Continuando con el ejemplo, q = 60 para un índice de 2/3. A manera de ejemplo, para el bit de información i_{1} se realizan las siguientes operaciones:

3

Para el bit de información número 361, i_{360}, se dan las direcciones de los acumuladores bits de paridad en la segunda fila de las tablas 2-8. De una manera similar, se obtienen las direcciones de los acumuladores de bit de paridad para los siguientes 359 bits de información i_{m}, m = 361, 362, ..., 719 usando la fórmula {x + mmod 360 x q} mod(n_{ldpc} - k_{ldpc}), donde x denota la dirección del acumulador del bit de paridad que corresponde al bit de información i_{360} es decir, las entradas en la segunda fila de las tablas 2-8. De una manera similar, para cada grupo de 360 bits de información nuevos, se utiliza una nueva fila de las tablas 2-8 para encontrar las direcciones de los acumuladores del bit de paridad.

Se dan las direcciones de los acumuladores del bit de paridad en las tablas 2-8.

TABLA 2

4

TABLA 3

5

TABLA 4

6

TABLA 5

7

TABLA 6

8

TABLA 7

9

TABLA 8

10

Después que se hayan terminado todos los bits de información, se obtiene el último bit de paridad de la siguiente manera. Primero, se realizan las siguientes operaciones comenzando con i=1 p_{1} = p_{i} \oplus p_{i-1}, i= 1,2,...n_{ldpc}-k_{ldpc}-1.

El contenido final de pi, i = 0,1,..., n_{ldpc} - k_{ldpc} - 1 es igual al bit de paridad p_{i}.

TABLA 9

11

El generador polinómico del codificador 211 BCH de corrección de errores t se obtiene con la multiplicación de los primeros polinomios t de la siguiente lista de la tabla 10.

TABLA 10

12

Se logra la codificación BCH de bits de información m= (m_{k_{bch}-1}, m_{k_{bch}-2}, m= (m_{1}, m_{0}) en una palabra de códifo c = (m_{k_{bch}-1}, m_{k_{bch}-2}, ..., m_{1}, m_{0}, ..., d_{n_{bch}-k_{bcn}-2}, ..., d_{1}, d_{0}) de la siguiente manera. El mensaje polinómico m(x)= m_{k_{bch}-1}x^{k_{bch}-1} + m_{k_{bch}-2}x^{k_{bch}-2} + m_{1}x + m_{0} se multiplica por x^{n_{bch} - k_{bch}}. Seguidamente x^{n_{bch} - k_{bch}} m(x) se divide por g(x). Con d(x) = d_{n_{bch} - k_{bch}-1}x^{n_{bch} - k_{bch}-1} + ... + d_{1}x + d_{0} como el residuo, la palabra de código polinómica se establece de la siguiente manera: c(x) = x^{n_{bch} - k_{bch}} m(x) + d(x).

Según lo visto en la fig. 2B, las salidas del codificador 203 de LDPC a un dispositivo de entrelazado de bit 213. A modo de ejemplo, se utilizan los formatos de modulación 8-PSK, 16-APSK, y 32-APSK. Los datos se escriben en serie por columnas en el dispositivo de entrelazado (de arriba a abajo) y se lee en serie por columnas (de izquierda a derecha). Sin embargo, en el caso del índice de código 3/5 con 8 -PSK, se ha determinado que la lectura de los datos de derecha a izquierda, en vez de izquierda a derecha, produce un mejor rendimiento (según lo ilustrado en la fig. 7).

Está especificada en la tabla 11 la configuración del dispositivo de entrelazado en bloque para cada formato de modulación.

TABLA 11

13

Las figs. 2C y 2D son diagramas de flujo de los procesos de codificación del codificador LDPC de la fig. 2B para generar códigos de LDPC de longitud de trama corta, según una presentación de la actual invención; En el paso 211, los bits de información se reciben y se procesan en la cadena de codificadores 209, 211, y 203. Por lo tanto, el codificador 203 de LDPC genera códigos de LDPC con los códigos externos de BCH basados en los bits de información recibidos, como en el paso 223. Los códigos también contienen el código de CRC. En el paso 225, el dispositivo de entrelazado 213 altera los bits codificados, como se describe anteriormente. Después, se representan los códigos de LDPC por las señales que están moduladas, por el paso 227, para la transmisión por el canal 103, que en una expresión ejemplar, es un enlace satelital a uno o más terminales satelitales (paso 229).

Según lo analizado, se codifican sistemáticamente los bits k_{ldpc} para generar bits n_{ldpc}. Según una presentación de la actual invención, n_{ldpc} es 16200 bits, que es una longitud corta de bloque. Dada la longitud relativamente corta de estos códigos, los códigos de LDPC que tienen longitudes aproximadas de 16200 bits o menos se consideran códigos de longitud de bloque "corto".

Según una presentación de la actual invención, los códigos de bloque corto se generan a partir de versiones reducidas de códigos "madre" ligeramente más largos (k_{m}, n_{m}) de tamaño de bloque n_{m}>16200. Como se muestra en la figura 2D, k_{ldpc} de los bits codificados BCH están precedidos por k_{m}-k_{ldpc} que son ceros ficticios (según el paso 251). Los bits resultantes k_{m} se codifican sistemáticamente para generar bits n_{m}, como en el paso 253. Se borran los primeros ceros ficticios k_{m}-k_{ldpc}, como en el paso 255 y se transmitirán (paso 257) los bits resultantes n_{ldpc} = 16200. Se observa que
k_{m} - k_{ldpc} = n_{m} - n_{ldpc}.

Se proporcionan los parámetros de códigos de longitud de trama corta en la tabla 12 de la siguiente manera:

\vskip1.000000\baselineskip

TABLA 12

14

\vskip1.000000\baselineskip

Se realizaron las simulaciones de rendimiento de estos códigos como se muestra en la fig. 8.

Las tablas 13-15 proporcionan otros índices de código de ejemplo, 1/3, 1/5 y 2/5 para n_{ldpc}, de 16200 bits:

TABLA 13

15

\vskip1.000000\baselineskip

\vskip1.000000\baselineskip

TABLA 14

16

\vskip1.000000\baselineskip

\vskip1.000000\baselineskip

TABLA 15

17

El enfoque anterior para el diseño de códigos de LDPC, en la manera prevista en las tablas 2-8 y 13-15, permite un almacenamiento ventajoso y la recuperación de la información relevante con respecto a los grupos de nodos de bit y de los nodos de verificación repartidos que se colocarán siempre en ubicaciones de memoria contiguas dentro de la memoria (por ejemplo, memoria de acceso aleatorio (RAM)). Además, esto permite la utilización de un solo banco de RAM, de esta manera se minimiza el tamaño del circuito integrado. Como mencionado, los códigos LDPC arriba se puede utilizar en diversas aplicaciones de vídeo digital, como transmisión en paquete MPEG (Motion Pictures Expert Group).

La Fig. 3 es un diagrama de un receptor de ejemplo en el sistema de la Fig. 1. En el lado de la recepción, un receptor 300 incluye un demodulador 301 que realiza la demodulación de señales recibidas del transmisor 200. Estas señales se reciben en una antena 303 de recepción para la demodulación. Después de la demodulación, las señales recibidas se envían a un decodificador 305, que intenta reconstruir los mensajes originales de la fuente generando mensajes, x', conjuntamente con un generador métrico 307 de bit. El generador métrico 307 de bit puede intercambiar información con el decodificador 305 hacia delante y hacia atrás (iterativamente) durante el proceso de decodificación. Se describen más completamente estos enfoques de decodificación en la aplicación pendiente, titulada "Method and System for Routing in Low Density Parity Check (LDPC) Decoders," archivado el 3 de julio de 2003 (No. de serie 10/613.824; caso del abogado PD-203009). Para apreciar las ventajas ofrecidas por la actual invención, es instructivo examinar cómo se generan los códigos de LDPC, según lo discutido en la Fig. 4.

La Fig. 4 es un diagrama de una matriz dispersa de verificación de paridad, según una presentación de la actual invención. Los códigos LDPC son códigos en bloque largos y lineales con una matriz dispersa de verificación de paridad H_{(n-k)xn.} Por lo general, la longitud n del bloque, que abarca desde los miles a las decenas de miles de bits. Por ejemplo, se muestra en la Fig. 4 una matriz de verificación de paridad para un código LDPC de longitud n=8 e índice 1/2. Se puede representar de manera equivalente el mismo código con el gráfico en dos partes, según la Fig. 5.

La Fig. 5 es un diagrama de un gráfico en dos partes de un código de LDPC de la matriz de la Fig. 4. Las ecuaciones de verificación de paridad significan que para cada nodo de verificación, la suma (por GF (Campo Galois)(2)) de todos los nodos adyacentes de bit es igual a cero. Según lo considerado en la figura, los nodos de bit ocupan el lado izquierdo del gráfico y se asocian a uno o más nodos de verificación, según una relación predeterminada. Por ejemplo, correspondiente al nodo de verificación m_{1}, existe la expresión siguiente n_{1} + n_{4} + n_{5} + n_{8} = 0 con respecto a los nodos de bit.

De regreso al receptor 303, el decodificador 305 de LDPC se considera un decodificador de paso de mensaje, por el que el decodificador 305 intenta encontrar los valores de los nodos de bit. Para lograr esta tarea, los nodos de bit y los nodos de verificación se comunican iterativamente entre sí. Se describe a continuación la naturaleza de esta comunicación.

De los nodos de verificación a los nodos de bit, cada nodo de verificación proporciona a un nodo adyacente de bit un estimado ("opinión") con respecto al valor de ese nodo de bit basado en la información que venía de otros nodos adyacentes de bit. Por ejemplo, en el ejemplo anterior si la suma de n_{4}, n_{5} y n_{8}, "parece" un 0 para m_{1}, entonces m_{1}, indicaría a n_{1}, que el valor de n_{1}, se cree que sea 0 (ya que n_{1} + n_{4} + n_{5} + n_{8} = 0); si no m_{1}, indica a n_{1},, que el valor de n_{1}, se cree que sea 1. Además, para la decodificación de decisión cuantificada, se agrega una medida de confiabilidad.

De los nodos de bit a los nodos de verificación, cada nodo de bit transmite a un nodo adyacente de verificación un estimado sobre su propio valor basado en la retroalimentación que viene de sus otros nodos adyacentes de verificación. En el ejemplo anterior n_{1} tiene solamente dos nodos adyacentes de verificación m_{1} y m_{3.} Si la retroalimentación que viene de m_{3} a n_{1} indica que el valor de n_{1} es probablemente 0, entonces n_{1} notificaría a m_{1} que un estimado del valor propio de n_{1} es 0. Para el caso en el que el nodo de bit tiene más de dos nodos adyacentes de verificación, el nodo de bit realiza una mayoría de votos (decisión cuantificada) en la retroalimentación que viene de sus otros nodos adyacentes de verificación antes de informar esa decisión al nodo de verificación con el que se comunica. Se repite el proceso anterior hasta que se considere que están correctos todos los nodos de bit (es decir, están satisfechas todas las ecuaciones de verificación de paridad) o hasta que se alcanza un número máximo predeterminado de iteraciones, por el que se declara un fallo de decodificación.

La Fig. 6 es un diagrama de una submatriz de una matriz dispersa de verificación de paridad, donde la submatriz contiene valores de la verificación de paridad restringida a la región triangular inferior, según una presentación de la actual invención. Según se describe anteriormente, el codificador 203 (de las Figs. 2A y 2B) puede utilizar una técnica de codificación sencilla con la restricción de los valores del área triangular inferior de la matriz de verificación de paridad. Según una presentación de la actual invención, la restricción impuesta en la matriz de verificación de paridad es de la forma:

18

donde B es el triangular inferior.

\newpage

Cualquier bloque de información i = (i_{0}, i_{1},..., i_{k-1}) está codificado en una palabra de código c = (i_{0}, i_{1},..., i_{k-1}, p_{0}, p_{1},..., p_{n-k-1}) utilizando Hc^{T}=0, y resolviendo repetidamente para los bits de paridad, por ejemplo,

19

y de forma similar para p_{2}, p_{3},..., p_{n-k-1}.

La Fig. 7 es un gráfico de rendimiento de los códigos de LDPC en los varios índices de código y los esquemas de modulación admitidos por el transmisor de la Fig. 2B; Según lo considerado, el índice de 3/5, 8-PSK rivaliza con el rendimiento de los códigos de LDPC que utilizan QPSK.

La Fig. 8 muestra los resultados de la simulación de códigos de LDPC de tamaño de bloque corto, según una presentación de la actual invención. La tabla 16 proporciona el rendimiento estimado en el índice de error de paquete (PER) de 10^{-7} para códigos cortos (n_{ldpc}= 16200).

TABLA 16

20

La Fig. 9 ilustra un sistema informático en el que se puede implementar una presentación según la actual invención. El sistema informático 900 incluye un 901 u otro mecanismo de comunicación para la comunicación de la información y un procesador 903 acoplado al bus 901 para el procesamiento de la información. El sistema informático 900 también incluye la memoria principal 905, como la memoria de acceso aleatorio (RAM) u otro dispositivo de almacenamiento dinámico, acoplado al bus 901 para guardar la información y las instrucciones que debe ejecutar el procesador 903. También se puede utilizar la memoria principal 905 para guardar las variables temporales u otra información intermedia durante la ejecución de las instrucciones que debe ejecutar el procesador 903. El sistema informático 900 incluye además una memoria de sólo lectura (ROM) 907 u otro dispositivo de almacenamiento estático acoplado al bus 901 para guardar la información y las instrucciones estáticas para el procesador 903. Se acopla además un dispositivo de almacenamiento 909, como un disco magnético o disco óptico, es adicionalmente acoplado al bus 901 para guardar la información y las instrucciones.

Se puede acoplar el ordenador, sistema 900 por medio del bus 901 a una pantalla 911, como un tubo de rayos catódicos (CRT), una pantalla de cristal líquido, una pantalla de matriz activa o una pantalla de plasma, para la visualización de la información para el usuario del ordenador. Se acopla al bus 901 un dispositivo de entrada 913, como un teclado incluyendo teclas alfanuméricas y otras para la información de comunicación y la selección de comando para el procesador 903. Otro tipo de dispositivo de entrada de información del usuario es el control de cursor 915, como un ratón, una bola de control del cursor (trackball) o las teclas de dirección del cursor para la comunicación de la información de la dirección y de las selecciones de comando para el procesador 903 y para el control del movimiento del cursor en la pantalla 911.

Según una presentación de la invención, el sistema informático 900 proporciona la generación de los códigos de LDPC en respuesta al procesador 903 que ejecuta un arreglo de instrucciones contenidas en la memoria principal 905. Se pueden leer estas instrucciones en la memoria principal 905 de otro medio de lectura por computador, como el dispositivo de almacenamiento 909. La ejecución del arreglo de instrucciones contenidas en la memoria principal 905 hace al procesador 903 realizar los pasos de proceso descritos aquí. Se pueden también emplear uno o más procesadores en un arreglo de procesamiento múltiple para ejecutar las instrucciones contenidas en la memoria principal 905. En presentaciones alternativas, se puede utilizar la circuitería cableada en lugar de o conjuntamente con las instrucciones del software para implementar la presentación de la actual invención. Por consiguiente, las presentaciones de la actual invención no están limitadas a ninguna combinación específica de circuitería de hardware y de software.

El sistema informático 900 también incluye una interfaz de comunicaciones 917 acoplado al bus 901. El interfaz de comunicaciones 917 proporciona a una comunicación de datos de dos vías acoplada a un enlace de red 919 conectada a una red local 921. Por ejemplo, el interfaz de comunicaciones 917 puede ser una tarjeta de línea de suscriptor digital (DSL) o un módem, una tarjeta de red digital de servicios integrados (ISDN), un módem de cable, o un módem telefónico para proporcionar a una conexión de comunicación de datos el tipo de línea telefónica correspondiente. Como otro ejemplo, el interfaz de comunicaciones 917 puede ser una tarjeta de red de área local (LAN) (por ejemplo, para Ethernet^{TM} o una red del modo de transferencia asíncrona (ATM)) para proporcionar a una conexión de comunicación de datos LAN compatible. Se pueden también implementar los enlaces inalámbricos. En cualquiera de estas implementaciones, el interfaz de comunicaciones 917 envía y recibe las señales eléctricas, electromagnéticas u ópticas que llevan las secuencias de datos digitales que representan varios tipos de información. Además, el interfaz de comunicaciones 917 puede incluir los dispositivos periféricos de interfaz, como un interfaz de bus serie universal (USB), una interfaz PCMCIA (Personal Computer Memory Card International Association), etc.

Por lo general, el enlace 919 de red proporciona la comunicación de datos a través de una o más redes a otros dispositivos de datos. Por ejemplo, el enlace 919 de red puede proporcionar una conexión a través de la red local 921 a un ordenador principal 923, que tiene conectividad a una red 925 (por ejemplo, una red de área amplia (WAN) o la red de comunicaciones global de datos de paquete ahora llamada comúnmente "Internet") o al equipo de datos operado por el suministrador del servicio. La red local 921 y la red 925 utilizan señales eléctricas, electromagnéticas u ópticas para transportar la información y las instrucciones. Las señales a través de las varias redes y las señales en el enlace de red 919 y a través del interfaz de comunicaciones 917, que comunican datos digitales con el sistema informático 900, son formas de ejemplo de las ondas de portadora que llevan la información y las instrucciones.

El sistema informático 900 puede enviar mensajes y recibir datos, incluyendo el código del programa, a través de la(s) red(es), del enlace 919 de red y del interfaz de comunicaciones 917. En el ejemplo de Internet, un servidor (no mostrado) pudo transmitir el código solicitado que pertenecía a un programa de aplicación para poner una presentación en ejecución de la actual invención a través de la red 925, de la red local 921 y del interfaz de comunicaciones 917. El procesador 903 puede ejecutar el código transmitido mientras que se recibe y/o guarda el código en el dispositivo de almacenamiento 99 o en otro almacenamiento permanente para ser ejecutada con posterioridad. De esta manera, el sistema informático 900 puede obtener el código de aplicación como una onda de portadora.

El término "medio de lectura por ordenador" según lo utilizado aquí se refiere a cualquier medio que participe en el suministro de instrucciones al procesador 903 para la ejecución. Este medio puede tomar muchas formas, con la inclusión pero no limitado a medio permanente, medio volátil y medio de transmisión. Los medios permanentes incluyen, por ejemplo, discos ópticos o magnéticos, como el dispositivo de almacenamiento 909. Los medios volátiles incluyen la memoria dinámica, como la memoria principal 905. Los medios de transmisión incluyen los cables coaxiales, cable de cobre y la fibra óptica, incluyendo los cables que comprende el bus 901. Los medios de transmisión pueden también tomar la forma de ondas acústicas, ópticas o electromagnéticas, como los generados durante las comunicaciones de datos infrarrojas (IR) de radiofrecuencia (RF). Las formas comunes de medios de lectura por ordenador incluyen, por ejemplo, el disquete, el disco flexible, el disco duro, la cinta magnética, cualquier otro soporte magnético, un CD-ROM, un CDRW, un DVD, cualquier otro medio óptico, tarjetas perforadas, cinta de papel, hojas de marca óptica, cualquier otro medio físico con patrones de orificios u otro instrumento ópticamente reconocible, una RAM, una PROM y una EPROM, una FLASH EPROM, cualquier chip o cartucho de memoria, una onda portadora o cualquier otra forma que el ordenador pueda leer.

Pueden estar involucradas varias formas de medios de lectura por ordenador en el suministro de las instrucciones a un procesador para la ejecución. Por ejemplo, puede que las instrucciones para llevar a cabo al menos una parte de la actual invención estén inicialmente en un disco magnético de un ordenador remoto. En esas circunstancias, el ordenador remoto carga las instrucciones en la memoria principal y envía las instrucciones por una línea telefónica con un módem. Un módem de un sistema informático local recibe los datos por la línea telefónica y utiliza un transmisor infrarrojo para convertir los datos a una señal infrarroja y para transmitir la señal infrarroja a un dispositivo de cómputo portátil, como una PDA (Personal Digital Assistance) y un ordenador portátil. Un detector infrarrojo en el dispositivo de cómputo portátil recibe la información y las instrucciones llevadas por la señal infrarroja y coloca los datos en un bus. El bus transporta los datos a la memoria principal, de la que un procesador extrae y ejecuta las instrucciones. Las instrucciones recibidas por la memoria principal se pueden almacenar de manera opcional en un dispositivo de almacenamiento antes o después de que el procesador las ejecute.

Por consiguiente, los varios ejemplos de la actual invención proporcionan que un codificador LDPC genere un código de LDPC que tiene un código externo Bose Chaudhuri Hocquenghem (BCH) según una de las Tablas 2-8 para la transmisión como una señal codificada de LDPC. Cada una de las Tablas 2-8 especifica la dirección de los acumuladores de bit de paridad. Se producen los códigos cortos de LDPC con la utilización de los códigos matrices de LDPC que se basan en las Tablas 2-8. k_{ldpc} de los bits codificados BCH que están precedidos por ceros ficticios k_{m} - k_{ldpc}. Se codifican sistemáticamente los bits resultantes k_{m} para generar bits n_{m.} Se borran los primeros ceros ficticios k_{m} - k_{ldpc,} para producir un código más corto. Para un código de LDPC con índice del código de 3/5 que utiliza modulación 8-PSK (modulación por desplazamiento de fase), un dispositivo de entrelazado proporciona los bits entrelazados del código de la salida LDPC con la escritura en serie de los datos por columna asociados al código de LDPC en una tabla y leyendo los datos por filas de derecha a izquierda. El enfoque anterior produce una complejidad reducida sin sacrificar el rendimiento.

Mientras que la actual invención se ha descrito en conexión con un número de presentaciones y de implementaciones, la actual invención no esta así limitada pero cubre varias modificaciones obvias y arreglos equivalentes, que caen dentro del ámbito de las declaraciones añadidas.

Claims

1. Un transmisor (200) para respaldar la transmisión de una señal codificada de verificación de paridad de baja densidad LDPC, comprende:

un codificador de verificación de paridad de baja densidad LDPC (203) configurado para entregar, basado en los bits de información recibida, un código LDPC; un dispositivo de entrelazado de bit (213) y

un modulador (205) configurado para modular la señal codificada de LDPC según una constelación de señal que incluye una modulación por desplazamiento de fase 8-PSK;

caracterizado en que el dispositivo de entrelazado de bits (213) está configurado para entrelazar los bits de salida del código LDPC escribiendo los datos en serie por columna asociados con el código LDPC en una tabla y leyendo los datos por filas de derecha a izquierda, donde la señal codificada de LDPC representa el código LDPC entrelazado, y el codificador LDPC (203) está configurado para entregar el código LDPC con un índice de código 3/5 y para generar el código LDPC por acumulación de los bits de información recibida en las direcciones de bits de paridad, las direcciones de bits de paridad estando decididas basado en siguiente tabla especificando direcciones de acumuladores de bits de paridad:

21

2. Un transmisor (200) según la reivindicación 1, comprende además:

un codificador Bose Chaudhuri Hocquenghem BCH (211) acoplado al codificador LDPC (203) y configurado para proporcionar un código externo al código LDPC.

3. Un transmisor (200) según la reivindicación 1, donde la señal modulada se transmite por un enlace satelital (103) a favor de una aplicación satelital de banda ancha.

\newpage

4. Un método de transmisión para respaldar la transmisión de la señal del código de verificación de paridad de baja densidad LDPC, el método comprende los pasos del método de:

salida, basado en los bits de información recibidos, de un código LDPC utilizando un codificador LDPC (203);

entrelazar bits del código de salida LDPC; y

modulación de la señal codificada LDPC según una constelación de señal que incluye la modulación por desviación de fase 8-PSK,

caracterizado en que:

el paso del método de entrelazar comprende escribir en serie datos asociados con el código LDPC por columnas en una tabla y leer los datos por fila de derecha a izquierda, en donde la señal codificada LDPC representa el código LDPC entrelazado, la tabla especificando direcciones de acumuladores de bits de paridad:

22

y en donde el paso del método de salida comprende entregar el código LDPC con un índice de código 3/5 y generar el código LDPC por acumulación de los bits de información recibidos en las direcciones de bits de paridad, estando basadas las direcciones de bits de paridad en las siguientes.

5. Un método según la reivindicación 4, comprende además:

la realización de la codificación Bose Chaudhuri Hocquenghem BCH de los bits de información recibidos para proporcionar un código externo al código LDPC.

6. Un método según la reivindicación 5, donde la señal modulada se transmite por un enlace satelital (103) a favor de una aplicación satelital de banda ancha.