ES2282671T3

ES2282671T3 - Codificacion de codigos de comprobacion de paridad de baja densidad (ldpc) utilizando una matriz de comprobacion de paridad estructurada.

Info

Publication number: ES2282671T3
Application number: ES03763217T
Authority: ES
Inventors: Mustafa Eroz; Feng-Wen Sun; Lin-Nan Lee
Original assignee: DirecTV Group Inc
Current assignee: DirecTV Group Inc
Priority date: 2002-07-03
Filing date: 2003-07-03
Publication date: 2007-10-16
Anticipated expiration: 2023-07-03
Also published as: AU2003247805A1; US20040054960A1; JP2005520468A; US6963622B2; CN100356697C; ATE498946T1; CA2456485C; HK1153056A1; WO2004006441A2; US20070113142A1; EP1518328B1; JP2005520467A; KR100602027B1; EP1525664A2; US20040153960A1; WO2004006443A1; KR100683600B1; CN1547806A; EP1525664B9; JP3917624B2

Abstract

Un método de codificar que comprende: acceder a laUn método de codificar que comprende: acceder a la memoria (1605, 1607) que almacena información que memoria ((1605, 1607) que almacena información qu representa una matriz de comprobación de paridad e representa una matriz de comprobación de paridadestructurada de códigos de Comprobación de Paridad estructurada de códigos de Comprobación de Parida de Baja Densidad (LDPC), estando la información od de Baja Densidad (LDPC), estando la información rganizada en forma tabular, representando cada filorganizada en forma tabular, representando cada fia de la información en memoria, ocurrencias de valla de la información en memoria, ocurrencias de vaores de uno dentro de una primera columna de un grlores de uno dentro de una primera columna de un gupo de columnas de la matriz de comprobación de parupo de columnas de la matriz de comprobación de pridad, correspondiendo las filas a grupos de columaridad, correspondiendo las filas a grupos de colunas de la matriz de comprobación de paridad, y siemnas de la matriz de comprobación de paridad, y sindo derivadas columnas subsiguientes dentro de cadendo derivadas columnas subsiguientes dentro de caa uno de los grupos de acuerdo a una operación preda uno de los grupos de acuerdo a una operación prdeterminada; inicializar acumuladores de bit de paedeterminada; inicializar acumuladores de bit de pridad a cero, en que los acumuladores de bit de paaridad a cero, en que los acumuladores de bit de pridad corresponden a bits de paridad; acumular el aridad corresponden a bits de paridad; acumular elprimer bit de información con índice jM del grupo primer bit de información con índice jM del grupode orden j de M bits de información en el acumulad de orden j de M bits de información en el acumulaor de bit de paridad en la dirección i especificaddor de bit de paridad en la dirección i especificaa si la entrada de orden j en la columna de orden da si la entrada de orden j en la columna de orden(jM)de la matriz de comprobación de paridad es 1, (jM)de la matriz de comprobación de paridad es 1,donde j=0, 1, 2, 3, ...kldpc/M-1; y emitir una señ donde j=0,1,2,3,...k ldpc/M-1; y emitir una señalal codificada de LDPC basada en la información alm codificada de LDPC basada en la información almacacenada que representa la matriz de comprobación denada que representa la matriz de comprobación de e paridad, caracterizado por, después de la operacparidad, caracterizado por, después de la operacióión de acumular el primer bit de información, las n de acumular el primer bit de información, las sisiguientes operaciones: acumular cada uno de los (guientes operaciones: acumular cada uno de los (M-M-1) bits de información restantes con índice m = 1) bits de información restantes con índice m =jM+jM+1, jM+2, jM+3, ..., (j+1)M-1 del grupo de orden1,jM+2,jM+3,...,(j+1)M-1 del grupo de orden j en u j en uno o más acumuladores de bit de paridad, reno o más acumuladores de bit de paridad, relacionalacionado a cada acumulador de bit de paridad en edo a cada acumulador de bit de paridad en el que el que el primer bit de información con índice jM el primer bit de información con índice jM en el grn el grupo fue acumulado, en una dirección {x+m moupo fue acumulado, en una dirección {x+m mod Mxq} d Mxq} mod(nldpc-kldpc), donde nldpc representa elmod(n ldpc-k ldpc), donde n ldpc representa el tam tamaño de palabra de código, kldpc representa el año de palabra de código, kldpc representa el tamatamaño del bloque de información, x indica la direño del bloque de información, x indica la direcciócción de cada acumulador de bit de paridad en la qn de cada acumulador de bit de paridad en la que eue el primer bit de información con índice jM en el primer bit de información con índice jM en el grl grupo fue acumulada, y q es una constante dependupo fue acumulada, y q es una constante dependientiente de la tasa de código; y después de que todose de la tasa de código; y después de que todos los los bitsde información son evacuados, realizar op bits de información son evacuados, realizar operaeraciones, comenzando con i=1 de acuerdo a, i=1, 2ciones, comenzando con i=1 de acuerdo a, i=1,2,..., ..., nldpc-kldpc-1, para obtener bits de paridad,n ldpc-k ldpc-1, para obtener bits de paridad fin final pi, i=0, 1, 2, ..., nldpc-kldpc-1, en los qal p i, i=0,1,2,...,n ldpc-k ldpc-1, en los que piue pi indica el contenido del acumulador de bit de indica el contenido del acumulador de bit de pari paridad en la dirección i. dad en la dirección i.

Description

Codificación de códigos de comprobación de paridad de baja densidad (LDPC) utilizando una matriz de comprobación de paridad estructurada.

Campo del invento

El presente invento se refiere a sistemas de comunicación, y más particularmente a sistemas codificados.

Antecedentes del invento

Los sistemas de comunicación emplean la codificación para asegurar una comunicación fiable a través de canales de comunicación ruidosos. Estos canales de comunicación exhiben una capacidad fijada que puede estar expresada en términos de bits por símbolo a cierta relación de señal a ruido (SNR), que define un límite superior teórico (conocido como el límite Shannon). Como resultado, el diseño de codificación ha pretendido conseguir tasas o índices que se aproximen a este límite Shannon. Tal clase de códigos que se aproximan al límite Shannon son códigos de Comprobación de Paridad de Baja Densidad (LDPC).

Tradicionalmente, los códigos LDPC no han sido ampliamente desarrollados debido a varios inconvenientes. Un inconveniente es que la técnica de codificación LDPC es muy compleja. Codificar un código LDPC usando su matriz generadora requeriría almacenar una matriz muy grande, no poco densa. Adicionalmente, los códigos LDPC requieren grandes bloques para ser efectivos; consiguientemente, incluso aunque las matrices de comprobación de paridad de códigos LDPC son poco densas, almacenar estas matrices es problemático.

Desde una perspectiva de puesta en práctica, hay que enfrentarse a varios desafíos. Por ejemplo, el almacenamiento es una razón importante por la que los códigos LDPC no han resultado ampliamente expandidos en la práctica. También, un desafío clave en la puesta en práctica del código LDPC ha sido cómo conseguir la red de conexión entre varias máquinas de tratamiento (nudos) en el descodificador. Además, la carga de cálculo en el proceso de descodificación, específicamente las operaciones de nodo de comprobación, plantea un problema.

Por ello, existe la necesidad para un sistema de comunicación de LDPC que emplea procesos de codificación y descodificación simples. Existe también una necesidad para usar códigos LDPC eficientemente para soportar altas tasas de datos, sin introducir mayor complejidad. Existe también una necesidad para mejorar las prestaciones de los codificadores y descodificadores de LDPC. Existe también una necesidad para minimizar los requisitos de almacenamiento para poner en práctica la codificación de LDPC. Existe otra necesidad para un esquema que simplifique la comunicación entre nudos de tratamiento en el descodificador LDPC.

"Sistemas de Kirkman y su aplicación en grabación magnética perpendicular" de Vasic.B (Transacciones de la IEEE sobre Dispositivos Magnéticos, vol. 38, nº 4, Julio de 2002) describe usar matrices de comprobación de paridad estructurada de códigos LPDC y procesos de codificación que usan las matrices de comprobación de paridad estructurada. Los bits de información son acumulados en acumuladores de bit de paridad en los que cada bit de paridad corresponde a un acumulador de bit de paridad.

El documento WO-A2-02/099976, publicado el 12 de diciembre de 2002, describe usar matrices de comprobación de paridad estructurada de códigos LPDC y procesos de codificación que usan las matrices de comprobación de paridad estructurada. Los bits de información son acumulados en acumuladores de bit de paridad en los que cada bit de paridad corresponde a un acumulador de bit de paridad.

Resumen del invento

A estas y otras necesidades está dirigido el presente invento que está definido en las reivindicaciones adjuntas.

Breve descripción de los dibujos

El presente invento está ilustrado a modo de ejemplo, y no a modo de limitación, en las figuras de los dibujos adjuntos y en los que los números de referencia similares se refieren a elementos similares y en los que:

La fig. 1 es un diagrama de un sistema de comunicaciones configurado para utilizar códigos de Comprobación de Paridad de Baja Densidad (LDPC), de acuerdo con una realización del presente invento.

Las figs. 2A y 2B son diagramas de codificadores de LDPC ejemplares desplegados en el transmisor de la fig. 1;

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

La fig. 4 es un diagrama de una matriz de comprobación de paridad poco densa, de acuerdo con una realización del presente invento;

La fig. 5 es un diagrama de un gráfico bipartito de un código de LDPC de la matriz de la fig. 4;

La fig. 6 es un diagrama de una sub-matriz de una matriz de comprobación de paridad poco densa, en la que la sub-matriz contiene valores de comprobación de paridad restringidos a la región triangular inferior, de acuerdo con una realización del presente invento;

La fig. 7 es una gráfica que muestra las prestaciones entre códigos que utilizan una matriz de comprobación de paridad no restringida (matriz H) frente a una matriz H restringida que tiene una sub-matriz como en la fig. 6;

Las figs. 8A y 8B son, respectivamente, un diagrama de un esquema de modulación no de Gray 8-PSK, y una modulación Gray 8-PSK, cada una de los cuales puede ser usada en el sistema de la fig. 1;

La fig. 9 es un gráfico que muestra las prestaciones entre códigos que utilizan el etiquetado Gray frente al etiquetado no de Gray;

La fig. 10 es un diagrama de flujo de la operación del descodificador de LDPC que usa cartografiado no de Gray, de acuerdo con una realización del presente invento;

La fig. 11 es un diagrama de flujo de la operación del descodificador de LDPC de la fig. 3 que usa cartografiado Gray, de acuerdo con una realización del presente invento;

Las figs. 12A-12C son diagramas de las interacciones entre los nudos de comprobación y los nudos de bit en un proceso de descodificación, de acuerdo con una realización del presente invento;

Las figs. 13A y 13B son diagramas de flujo de procesos para calcular mensajes salientes entre los nudos de comprobación y los nudos de bit usando, respectivamente, una aproximación hacia delante y hacia atrás y una aproximación paralela, de acuerdo con distintas realizaciones del presente invento;

Las figs. 14A-14B son gráficos que muestran resultados de simulación de códigos de LDPC generados de acuerdo con distintas realizaciones del presente invento.

Las figs. 15A y 15B son diagramas del borde superior y del borde inferior, respectivamente, de memoria organizada para soportar el acceso estructurado de modo que se realice la aleatoriedad en la codificación LDPC, de acuerdo con una realización del presente invento; y

La fig. 16 es un diagrama de un sistema de ordenador que puede realizar los procesos de codificación y descodificación de códigos LDPC, de acuerdo con realizaciones del presente invento.

Descripción de la realización preferida

Están descritos un sistema, método y software para descodificar eficientemente códigos de Comprobación de Paridad de Baja Densidad (LDPC). En la siguiente descripción, con propósitos de explicación, se han descrito numerosos detalles específicos a fin de proporcionar una total comprensión del presente invento. Es evidente, sin embargo, para un experto en la técnica que el presente invento puede ser puesto en práctica sin estos detalles específicos o con una disposición equivalente. En otros casos, estructuras y dispositivos bien conocidos están mostrados en forma de diagrama de bloques a fin de evitar oscurecer de modo innecesario el presente invento.

La fig. 1 es un diagrama de un sistema de comunicaciones configurado para utilizar códigos de Comprobación de Paridad de Baja Densidad (LDPC), de acuerdo con una realización del presente invento. Un sistema 100 de comunicaciones digitales incluye un transmisor 101 que genera formas de onda de señal a través de un canal de comunicación 103 a un receptor 105. En este sistema 100 discreto de comunicaciones, el trasmisor 101 y tiene una fuente de mensajes que produce un conjunto discreto de mensajes posibles; cada uno de los mensajes posibles tiene una forma de onda de señal correspondiente. Estas formas de onda de señal son atenuadas, o alteradas de otro modo, mediante el canal 103 de comunicaciones. Para combatir el canal de ruido 103, son utilizados códigos de LDPC.

Los códigos de LDPC que son generados por el transmisor 101 habilitan una puesta en práctica de alta velocidad sin incurrir en ninguna pérdida de prestaciones. Estos códigos de LDPC estructurados emitidos desde el transmisor 101 evitan la asignación de un pequeño número de nudos de comprobación a los nudos de bit ya vulnerables a errores de canal en virtud del esquema de modulación (por ejemplo, 8 PSK).

Tales códigos de LDPC tienen un algoritmo de descodificación que puede utilizarse en paralelo, (distinto de los turbocódigos), que ventajosamente implica operaciones simples tales como suma, comparación y una búsqueda en tabla. Además, los códigos de LDPC diseñados cuidadosamente no exhiben ningún signo de piso de error.

De acuerdo con una realización del presente invento, el transmisor 101 genera, usando una técnica de codificación relativamente simple, códigos de LDPC basados en matrices de comprobación de paridad (que facilitan el acceso eficiente a la memoria durante la descodificación) para comunicar con el receptor 105. El trasmisor 101 emplea 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 LDPC ejemplares desplegados en el transmisor de la fig. 1. Como se ha visto en la fig. 2A, un transmisor 200 está equipado con un codificador de LDPC 203 que acepta entrada desde una fuente de información 201 y emite una corriente codificada de mayor redundancia adecuada para el tratamiento de corrección de error en el receptor 105. La fuente de información 201 genera k señales desde un alfabeto discreto, X. Los códigos de LDPC son especificados con matrices de comprobación de paridad. Por otro lado, la codificación de códigos de LDPC requiere, en general, especificar las matrices generadoras. Incluso aunque sea posible obtener matrices generadoras a partir de las matrices de comprobación de paridad utilizando la eliminación Gaussiana, la matriz resultante no es ya poco densa y almacenar una gran matriz generadora puede ser
complejo.

El codificador 203 general señales desde el alfabeto Y a un modulador 205 usando una simple técnica de codificación que hace uso sólo de la matriz de comprobación de paridad imponiendo estructura sobre la matriz de comprobación de paridad. Específicamente, se plantea una restricción sobre la matriz de comprobación de paridad constriñendo cierta parte de la matriz para que sea triangular. La construcción de tal matriz de comprobación de paridad está descrita más completamente a continuación en la fig. 6. Tal restricción da como resultado una pérdida de prestaciones despreciable, y por ello, constituye una compensación atractiva.

El modulador 205 cartografía los mensajes codificados desde el codificador 203 a formas de onda de señal que son transmitidas a una antena de transmisión 207, que emite estas formas de onda sobre el canal de comunicación 103. Consiguientemente, los mensajes codificados son modulados y distribuidos a una antena de transmisión 207. Las trasmisiones desde la antena de transmisión 207 se propagan a un receptor, como se ha descrito 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íclico (CRC), de acuerdo con una realización del presente invento. Bajo este escenario, 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 exterior de BCH concatenado y un código de comprobación de paridad de baja densidad interior. Además, la detección de error es conseguida usando códigos de comprobación de redundancia cíclica (CRC). El codificador 209 de CRC, en una realización ejemplar, codifica usando un código CRC de 8 bits con generador polinómico (x^{5}+x^{4}+x^{3}+x^{2}+1)(x^{2}+x+1)(x+1).

El codificador 203 de LDPC codifica sistemáticamente un bloque de información de tamaño k_{ldpc}, i=(i_{0},i_{1},...,i_{kldpc-1}) sobre una palabra de código de tamaño n_{ldpc}, c=(i_{0},i_{1},...,i_{kldpc-1}, p_{0}, p_{1},...,p_{nldpc-kldpc-1}). La transmisión de la palabra de código empieza en la orden dada desde i_{0} y termina con p_{nldpc-kldpc-1}. Los parámetros (n_{ldpc}, k_{ldpc}) de código de LDPC están dados en la Tabla 1 siguiente.

\vskip1.000000\baselineskip

TABLA 1

1

\newpage

La tarea del codificador 203 de LDPC es determinar los bits de paridad (p_{0}, p_{1},...,p_{nldpc-kldpc-1}) de n_{ldpc-}k_{ldpc} para cada bloque de bits de información k_{ldpc}, (i_{0},i_{1},...,i_{kldpc-1}). El procedimiento es el siguiente. En primer lugar son inicializados los bits de paridad; p_{0}=p_{1}=p_{2}=...= p_{nldpc-kldpc-1} = 0. El primer bit de información, i_{0}, es acumulado en las direcciones de bit de paridad especificadas en la primera fila de las Tablas 3 a 10. Por ejemplo, para una tasa 2/3 (Tabla 3), resulta lo siguiente:

2

3

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

Luego, para los siguientes 359 bits de información, i_{m}, m=1,2,...,359), estos bits son acumulados en direcciones de bit de paridad {x+m mod 360xq} mod(n_{ldpc-}k_{ldpc}), donde x indica la dirección del acumulador de bit de paridad correspondiente al primer bit i_{0}, y q es una tasa de código dependiente constante especificado en la tabla 2. Continuando con el ejemplo, q=60 para tasa 2/3. A modo de ejemplo, para el bit i_{1} de información, son realizadas las siguientes operaciones:

4

Para el 361º bit de información I_{360}, las direcciones de los acumuladores de bit de paridad están dadas en la segunda fila de las tablas 3 a 10. De una manera similar a las direcciones de los acumuladores de bit de paridad para los siguientes 359 bits de información I_{m}, m=361,362,...,719 son obtenidas usando la fórmula {x+m mod360xq} mod(n_{ldpc}-k_{ldpc}) donde x indica las direcciones del acumulador de bit de paridad correspondientes al bit de información, es decir, las entradas en la segunda fila de las tablas 3-10. De modo similar, para cada grupo de 360 nuevos bits de información, se usa una nueva fila de las tablas 3-10 para encontrar las direcciones de los acumuladores de bit de paridad.

Después de que todos los bits de información son evacuados, los bits de paridad final son obtenidos como sigue. En primer lugar se realizan las siguientes operaciones, empezando con i = 1.

p_{i} = p_{i} \oplus p_{i-1}, \ i = 1,2,...,n_{ldpc}-k_{ldpc}-1

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

\vskip1.000000\baselineskip

TABLA 2

5

\vskip1.000000\baselineskip

TABLA 3

6

TABLA 3 (continuación)

7

TABLA 3 (continuación)

8

TABLA 3 (continuación)

9

TABLA 4

10

TABLA 4 (continuación)

11

TABLA 4 (continuación)

12

TABLA 4 (continuación)

13

TABLA 5

14

TABLA 5 (continuación)

15

TABLA 5 (continuación)

16

TABLA 6

17

TABLA 6 (continuación)

18

TABLA 6 (continuación)

19

TABLA 7

20

TABLA 7 (continuación)

21

TABLA 7 (continuación)

22

TABLA 8

23

TABLA 8 (continuación)

24

TABLA 8 (continuación)

25

TABLA 9

26

TABLA 9 (continuación)

27

TABLA 9 (continuación)

28

TABLA 9 (continuación)

29

TABLA 10

30

TABLA 10 (continuación)

31

TABLA 10 (continuación)

32

TABLA 10 (continuación)

33

\newpage

En lo que se refiere al codificador 211 de BCH, los parámetros de código de BCH están enumerados en la tabla 11.

\vskip1.000000\baselineskip

TABLA 11

34

Se ha observado que en la tabla anterior, n_{bch} = k_{idpc}

El generador de polinomios del error t que corrige el codificador 211 BCH es obtenido multiplicando los primeros polinomios t en la siguiente lista de la Tabla 12.

TABLA 12

35

La codificación de BCH de los bits de información m=(m_{kbch-1}, m_{kbch-2},..., m_{1}, m_{0}) sobre una palabra código c = (m_{kbch-1}, m_{kbch-2},..., m_{1}, m_{0}, d_{nbch-kbch-1}, d_{nbch-kbch-2},..., d_{1}, d_{0}) es conseguida como sigue. El mensaje polinómico
m(x) = m_{kbch-1}x^{kbch-1}+ m_{kbch-2}x^{kbch-2}+...+ m_{1}x+ m_{0} es multiplicado por x^{nbch-kbch}. A continuación, x^{nbch-kbch} m(x) es dividido por g(x). Con d(x)=d_{nbch-kbch-1}x^{nbch-kbch-1}+...+d_{1}x+d_{0} como el resto, la palabra de código polinómica es ajustada como sigue: c(x) = x^{nbch-kbch} m(x)+d(x).

Los códigos de LDPC anteriores, en una realización ejemplar, pueden ser usados en una variedad de aplicaciones de vídeo digital, tales como transmisión de paquetes de MPEG (Grupo Experto de Imágenes en Movimiento).

La fig. 3 es un diagrama de un receptor ejemplar en el sistema de la fig. 1. En el lado de la recepción,1 receptor 300 incluye un desmodulador 301 que realiza la desmodulación de señales recibidas desde el transmisor 200. Estas señales son recibidas en una antena de recepción 303 para desmodulación. Después de la desmodulación, las señales recibidas son avanzadas a un descodificador 305, que intenta reconstruir los mensajes de fuente original generando mensajes, X', en unión con un generador métrico 307 de bits. Con cartografiado no de Gray, el generador métrico 307 de bits intercambia información de probabilidad con el descodificador 305 hacia atrás y hacia delante (de modo iterativo) durante el proceso de descodificación, que está detallado en la fig. 10. Alternativamente, si es usado cartografiado Gray (de acuerdo con una realización del presente invento) una pasada del generador métrico de bits es suficiente, en el que otros intentos de generación métrica de bits después cada iteración del descodificador de LDPC es probable que produzcan mejoras de prestaciones limitadas; esta aproximación está descrita más completamente con respecto a la fig. 11. Para apreciar las ventajas ofrecidas por el presente invento, es instructivo examinar cómo son generados los códigos de LDPC, como se ha descrito en la fig. 4.

La fig. 4 es un diagrama de una matriz de comprobación de paridad poco densa, de acuerdo con una realización del presente invento. Los códigos de LDPC son códigos de bloque lineal, largos con matriz de comprobación de paridad H_{(n-k)xn} poco densa. Típicamente la longitud del bloque, n, oscila desde miles a cientos de miles de bits. Por ejemplo, una matriz de comprobación de paridad para un código de LDPC de longitud n=8 y tasa ½ está mostrada en la fig. 4. El mismo código puede ser representado de manera equivalente por el gráfico bipartito, por la fig. 5.

La fig. 5 es un diagrama de un gráfico bipartito de un código de LDPC de la matriz de la fig. 4. Las ecuaciones de comprobación de paridad implican que para cada nodo de comprobación, la suma (sobre GF (Campo de Galois) (2)) de todos los nudos de bits adyacentes es igual a cero. Como se ha visto en la figura, los nudos de bits ocupan el lado izquierdo del gráfico y están asociados con uno o más nudos de comprobación, de acuerdo con una relación predeterminada. Por ejemplo, correspondiendo al nodo de comprobación, m_{1}, existe la siguiente expresión n_{1}+n_{4}+n_{5}+n_{8}=0 con respecto a los nudos de bit.

Volviendo al receptor 303, el descodificador 305 de LDPC es considerado un descodificador para pasar mensajes, por lo que el descodificador 305 intenta encontrar los valores de nudos de bits. Para cumplir esta tarea, los nudos de bits y los nudos de comprobación se comunican de modo iterativo entre sí. La naturaleza de esta comunicación es descrita a continuación.

Desde los nudos de comprobación a los nudos de bits, cada nodo de comprobación proporciona a un nodo de bit adyacente una estimación ("opinión") relativa al valor de ese nodo de bit basada en la información que llega desde otros nodos de bit adyacentes. Por ejemplo, en el ejemplo anterior si la suma de n_{4}, n_{5} y n_{8} "se parece como" 0 a m_{1}, entonces m_{1} indicaría a n_{1} que el valor de n_{1} se cree que es 0 (ya que n_{1}+n_{4}+n_{5}+n_{8}=0); de otro modo m_{1} indica a n_{1} que el valor de n_{1} se cree que es 1. Adicionalmente, para la descodificación de decisión de software, es añadida una medida de fiabilidad.

Desde los nodos de bit a los nodos de comprobación, cada nodo de bit retransmite a un nodo de comprobación adyacente una estimación acerca de su propio valor basada en la realimentación que llega desde sus otros nodos de comprobación adyacentes. En el ejemplo anterior n_{1} tiene sólo dos nodos de comprobación adyacentes m_{1} y m_{3}. Si la realimentación que llega desde m_{3} a n_{1} indica que el valor de n_{1} es probablemente 0, entonces n_{1} notificaría a m_{1} que una estimación del propio valor de n_{1} es 0. Para el caso en que el nodo de bit tiene más de dos nodos de comprobación adyacente, el nodo de bit realiza un voto de mayoría (decisión de software) sobre la realimentación que llega desde otros nodos de comprobación adyacentes antes de informar que la decisión al nodo de comprobación lo comunica. El proceso anterior es repetido hasta que todos los nodos de bit se considera que están correctos (es decir, son satisfechas todas las ecuaciones de comprobación de paridad) o hasta que es alcanzado un número máximo predeterminado de iteraciones, por lo que es declarado un fallo de descodificación.

La fig. 6 es un diagrama de una submatriz de una matriz de comprobación de paridad poco densa, en que la submatriz contiene valores de comprobación de paridad restringidos a la región triangular inferior, de acuerdo con una realización del presente invento. Como se ha descrito previamente, el codificador 203 (de las figs. 2A y 2B) puede emplear una técnica de codificación simple restringiendo los valores del área triangular inferior de la matriz de comprobación de paridad. De acuerdo con una realización del presente invento, la restricción impuesta en la matriz de comprobación de paridad es de la forma:

36

donde B es triangular inferior.

Cualquier bloque de información i=(i_{0},i_{1},...,i_{k-1}) es codificado a una palabra de código c=(i_{0},i_{1},...,i_{k-1},p_{0},p_{1},...,p_{n-k-1}) usando Hc^{T}= 0, y resolviendo de modo recursivo para bits de paridad; por ejemplo,

37

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

La fig. 7 es un gráfico que muestra rendimientos entre códigos que utilizan la matriz de comprobación de paridad sin restringir (matriz H) frente a la matriz H restringida de la fig. 6. El gráfico muestra la comparación de prestaciones entre dos códigos LDPC: uno con una matriz de comprobación de paridad general y el otro con una matriz de comprobación de paridad restringida para ser triangular inferior para simplificar la codificación. El esquema de modulación, para esta simulación, es 8-PSK. La pérdida de prestaciones está adentro de 0,1 dB. Por ello, la pérdida de prestaciones es despreciable basado en la restricción de las matrices H triangulares inferiores, mientras que la ganancia en simplicidad de la técnica de codificación es significativa. Consiguientemente, cualquier matriz de comprobación de paridad que sea equivalente a una triangular inferior o triangular superior bajo la permutación de fila y/o columna puede ser utilizada para el mismo propósito.

Las figs. 8A y 8B son, respectivamente, un diagrama de un esquema de modulación no de Gray 8-PSK, y una modulación Gray 8-PSK, cada uno de los cuales puede ser usado en el sistema de la fig. 1. El esquema no de Gray 8 PSK de la fig. 8A puede ser utilizado en el receptor de la fig. 3 para proporcionar un sistema que requiere una Tasa de Borrado De Marco (FER) muy baja. Este requisito puede también ser satisfecho usando un esquema Gray 8-PSK, como se ha mostrado en la fig. 8B, en unión con un código exterior, tal como código de Bose, Chaudhuri, y Hocquenghem (BCH), Hamming, o Reed-Solomon (RS).

Bajo este esquema, no hay necesidad para iterar entre el descodificador 305 de LDPC (fig. 3) y el generador métrico 307 de bits, que puede emplear modulación 8-PSK. En ausencia de un código exterior, el descodificador 305 de LDPC que usa etiquetado Gray exhibe un suelo de error temprano, como se ha mostrado después en la fig. 9.

La fig. 9 es un gráfico que muestra las prestaciones entre códigos que utilizan etiqueta Gray contra los que utilizan etiqueta no de Gray de las figs. 8A y 8B. El suelo de error proviene del hecho de que suponiendo una realimentación correcta desde el descodificador 305 de LDPC, la regeneración de métricas de bit de 8-PSK es más exacta con el etiquetado no de Gray ya que los dos símbolos 8-PSK con dos bits conocidos están además separados con etiquetado no de Gray. Esto puede ser visto de manera equivalente como funcionando a una Relación de Señal a Ruido (SNR) más elevada. Por ello, incluso aunque asíntotas de error del mismo código LDPC que usan etiquetado Gray o no de Gray tienen la misma pendiente (es decir, paralelas entre sí), la que tiene etiquetado no de Gray pasa a través del FER inferior a cualquier SNR.

Por otro lado, para sistemas que no requieren un FER muy bajo, el etiquetado Gray sin ninguna iteración entre el descodificador 305 de LDPC, y el generador métrico 307 de bits de 8-PSK puede ser más adecuado debido a que la regeneración de métricas de bit de 8-PSK antes de cada iteración del descodificador LDPC provoca una complejidad tradicional. Además, cuando el etiquetado Gray es usado, la regeneración de métricas de bit de 8-PSK antes de cada iteración del descodificador LDPC rinde solo una mejora de prestaciones muy ligera. Como se ha mencionado previamente, el etiquetado Gray sin iteración puede ser usado para sistemas que requieren muy bajo FER, siempre que haya implantado un código exterior.

La elección entre etiquetado Gray y etiquetado no de Gray, depende también de las características del código LDPC. Típicamente, cuanto mayores son los grados de nodo de bit o de comprobación, mejor es para el etiquetado Gray, debido a que para mayores grados de nodo, la realimentación inicial desde el descodificador 305 de LDPC al generador métrico 307 de bits de 8-PSK (o modulación de orden similar más elevada) se deteriora más con el etiquetado no de Gray.

Cuando la modulación 8-PSK (u orden más elevada similar) es utilizada con un descodificador binario, es reconocido que los tres bits (o más) de un símbolo no son recibidos "igualmente ruidosos". Por ejemplo con el etiquetado Gray 8-PSK, el tercer bit de un símbolo es considerado más ruidoso para el descodificador que los otros dos bits. Por ello, el diseño de código LDPC no asigna un número pequeño de bordes a aquellos nodos de bits representados por terceros bits "más ruidosos" del símbolo 8-PSK de manera que aquellos bits no son penalizados dos veces.

La fig. 10 es un diagrama de flujo del funcionamiento del descodificador LDPC que usa cartografiado no de Gray, de acuerdo con una realización del presente invento. Bajo esta aproximación, el descodificador LDPC y el generador métrico de bit iteran uno después del otro. En este ejemplo, es utilizada la modulación 8-PSK; sin embargo, los mismos principios se aplican a otros esquemas de modulación más elevada también. Bajo este escenario, se ha supuesto que el desmodulador 301 emite un vector de distancia, d, que indica las distancias entre puntos de símbolo ruidosos recibidos y puntos de símbolo 8-PSK al generador métrico 307 de bits, por lo que los componentes de vector son como sigue:

38

El generador métrico 307 de bits de 8-PSK comunica con el descodificador 305 de LDPC para intercambiar una información de probabilidad a priori y una información de probabilidad a posteriori, que respectivamente son representados como u y a. Es decir, los vectores u y a representan respectivamente probabilidades a priori y a posteriori de las relaciones de probabilidad de logaritmo de bits codificados.

El generador métrico 307 de bits de 8-PSK genera las relaciones de probabilidad a priori para cada grupo de tres bits como sigue. En primer lugar, es obtenida información extrínseca sobre los bits codificados:

\vskip1.000000\baselineskip

e_{j}=a_{j}-u_{j} \hskip1cm j=0,1,2.

\vskip1.000000\baselineskip

A continuación, las probabilidades del símbolo 8-PSK, p_{i}i=0,1,...,7, son determinadas.

\vskip1.000000\baselineskip

*y_{j}=-f(0,e_{j}) \hskip1cm j=0,1,2.

\vskip1.000000\baselineskip

donde \hskip0,1cm f(a,b)=max(a,b)+LUT_{f}(a,b) \hskip0,3cm con \hskip0,1cmLUT_{f}(a,b)=ln(1+e^{-|a-b|})

\vskip1.000000\baselineskip

*x_{j}=y_{j}+e_{j} \hskip1cm j=0,1,2.

*p_{0}=x_{0}+x_{1}+x_{2} \hskip1cm p_{4}=y_{0}+x_{1}+x_{2}

p_{1}=x_{0}+x_{1}+y_{2} p_{5}=y_{0}+x_{1}+y_{2}

p_{2}=x_{0}+y_{1}+x_{2} p_{6}=y_{0}+y_{1}+x_{2}

p_{3}=x_{0}+y_{1}+y_{2} p_{7}=y_{0}+y_{1}+y_{2}

\vskip1.000000\baselineskip

A continuación, el generador métrico 307 de bits determina relaciones de probabilidad logarítmicas a priori de los bits codificados como entrada al descodificador 305 de LDPC, como sigue:

\vskip1.000000\baselineskip

U_{0}=f(d_{0}+p_{0},d_{1}+p_{1},d_{2}+p_{2},d_{3}+p_{3})-f(d_{4}+p_{4},d_{5}+p_{5},d_{6}+p_{6},d_{7}+p_{7})-e_{0}

U_{1}=f(d_{0}+p_{0},d_{1}+p_{1},d_{4}+p_{4},d_{5}+p_{5})-f(d_{2}+p_{2},d_{3}+p_{3},d_{6}+p_{6},d_{7}+p_{7})-e_{1}

U_{2}=f(d_{0}+p_{0},d_{2}+p_{2},d_{4}+p_{4},d_{6}+p_{6})-f(d_{1}+p_{1},d_{3}+p_{3},d_{5}+p_{5},d_{7}+p_{7})-e_{2}

\vskip1.000000\baselineskip

se ha observado que la función f(.) con más de dos variables puede ser evaluada de manera recurrente; por ejemplo
f(a,b,c)=f(f(a,b),c).

El funcionamiento del descodificador 305 de LDPC que utiliza cartografiado no de Gray está descrito a continuación. En la operación 1001, el descodificador 305 de LDPC inicializa las relaciones de probabilidad logarítmica de los bits codificados, v, antes de la primera iteración de acuerdo con lo siguiente (y como se ha mostrado en la fig.
12A):

v_{n->k1}=u_{n} \hskip1cm n=0,1,...,N-1 \hskip1cm i=1,2,...,grado(nodo \ n \ de \ bit)

Aquí, V_{n}_{->k1} indica el mensaje que va desde el nodo de bit n a su nodo de comprobación adyacente k_{j}, u_{n} indica la salida del desmodulador para el bit n y N es el tamaño de la palabra de código.

En la operación 1003, un nodo de comprobación, k, es actualizado, por lo que la entrada v produce la salida w. Como se ha visto en la fig. 12B, los mensajes entrantes al nodo de comprobación k desde sus nodos de bit adyacente d_{c} son indicados por v_{n1->k},v_{n2->k},...,v_{ndc->k}. El objetivo es calcular los mensajes salientes desde el nodo de comprobación k de nuevo a los nodos de bit adyacentes d_{c}. Estos mensajes están indicados por w_{k\rightarrow n1},w_{k\rightarrow n2},...,w_{k\rightarrow ndc}, donde

w_{k->n1}=g(v_{n1->k},v_{n2->k},...,v_{nl-1->k},v_{n1+1->k},...,v_{ndc->k})

La función g() es definida como sigue:

g(a,b)=sign(a)x sign(b)x\{min(|a|,|b|\}+LUT_{g}(a,b),

donde LUT_{g}(a,b)=ln(1+e^{-|a+b|})-ln(1+e^{-|a-b|}). Similar a la función f, la función g con más de dos variables puede ser evaluada de modo recurrente.

A continuación el decodificador 305, por la operación 1205, emite una información de probabilidad a posteriori (fig. 12C), de tal manera que:

a_{n} = u_{n} + \sum\limits_{j} w_{kj\rightarrow n}

Por la operación 1007, se determina si son satisfechas todas las ecuaciones de comprobación de paridad. Si estas ecuaciones de comprobación de paridad no son satisfechas, entonces el descodificador 305, como en la operación 1009, vuelve a derivar las métricas de bit de 8-PSK y la entrada del canal u_{n}. A continuación, el nodo de bit es actualizado, como en la operación 1011. Como se ha mostrado en la fig. 14C, los mensajes entrantes al nodo de bit n desde sus nodos de comprobación adyacentes d_{v} son indicados por w_{k1\rightarrow n},w_{k2\rightarrow n},...,w_{kdv\rightarrow n}. Los mensajes salientes desde el nodo de bit n son calculados de nuevo a los nodos de comprobación adyacentes d_{v}; tales mensajes están indicados por v_{n\rightarrow k1},v_{n\rightarrow k2},...,v_{n\rightarrow kdv},y son calculados como sigue:

v_{n\rightarrow k1} = u_{n} + \sum\limits_{j} w_{kj\rightarrow n}

En la operación 1013, el descodificador 305 emite la decisión de hardware (en el caso de que sean satisfechas todas las ecuaciones de comprobación de paridad):

39

La aproximación anterior es apropiada cuando es utilizado el etiquetado no de Gray. Sin embargo, cuando es implantado el etiquetado Gray, se ejecuta el proceso de la fig. 11.

La fig. 11 es un diagrama de flujo del funcionamiento del descodificador de LDPC de la fig. 3 que usa cartografiado Gray, de acuerdo con una realización del presente invento. Cuando es usado el etiquetado Gray, son generadas ventajosamente las métricas de bit solo una vez antes de que el descodificador de LDPC, ya que regenerar métricas de bit después de cada iteración del descodificador de LDPC puede producir una mejora de prestaciones nominal. Como con las operaciones 1001 y 1003 de la fig. 10, la inicialización de las relaciones de probabilidad logarítmica de bits codificados, v, son realizadas, y el nodo de comprobación es actualizado, por las operaciones 1101 a 1103. A continuación, el nodo de bit n es actualizado, como en la operación 1105. Después de ello, el descodificador emite la información de probabilidad a posteriori (operación 1107). En la operación 1109, se ha hecho una determinación de si son satisfechas todas las ecuaciones de comprobación de paridad; si es así, el descodificador emite la decisión de hardware (operación 1111). De otro modo, se repiten las operaciones 1103 a 1107.

La fig. 13A es un diagrama de flujo del proceso para calcular los mensajes salientes entre los nodos de comprobación y los nodos de bit usando una aproximación hacia delante y hacia atrás, de acuerdo con una realización del presente invento. Para un nodo de comprobación con bordes adyacentes d_{c}, se realizan el cálculo de d_{c}(d_{c}-1) y numerosas funciones g(.,.). Sin embargo, la aproximación hacia delante y hacia atrás reduce la complejidad del cálculo a 3(d_{c}-2), en que están almacenadas d_{c}-1 variables.

Con referencia a la fig. 12B, los mensajes entrantes al nodo de comprobación k desde los d_{c} nodos de bit están indicados por v_{n1\rightarrow k},v_{n2\rightarrow k},...,v_{ndc\rightarrow k}. Se ha deseado que los mensajes salientes sean calculados desde el nodo de comprobación k hacia atrás a los d_{c} nodos de bit adyacentes; estos mensajes salientes están indicados por w_{k\rightarrow n1},w_{k\rightarrow n2},...,w_{k\rightarrow ndc}.

Bajo la aproximación hacia delante y hacia atrás para calcular estos mensajes salientes, las variables avanzadas, f_{1}, f_{2},...,f_{dc}, son definidas como sigue:

f_{1}=v_{1\rightarrow k}

f_{2}=g(f_{1},v_{2\rightarrow k})

f_{3}=g(f_{2},v_{3\rightarrow k})

\cdot \cdot \cdot

f_{dc}=g(f_{dc-1},v_{dc\rightarrow k})

En la operación 1301, estas variables avanzadas son calculadas, y almacenadas, por la operación 1303.

De manera similar, las variables atrasadas, b_{1}, b_{2},...,b_{dc} son definidas como sigue:

b_{dc}=v_{dc\rightarrow k}

b_{dc-1}=g(b_{dc},v_{dc-1\rightarrow k})

\cdot \cdot \cdot

b_{1}=g(b_{2},v_{1\rightarrow k})

En la operación 1305, estas variables atrasadas son a continuación calculadas. Después de ello, son calculados los mensajes salientes, como en la operación 1307, basado en las variables avanzadas almacenadas y las variables atrasadas calculadas. Los mensajes salientes son calculados como sigue:

W_{k\rightarrow 1}=b_{2}

W_{k\rightarrow 1}=g(f_{l-1},b_{i+1}) \hskip1cm i=2,3,...,d_{c}-1

W_{k\rightarrow dc}=f_{dc-1}

Bajo esta aproximación, solo las variables avanzadas, f_{2},f_{3},...,f_{dc}, son requeridas para ser almacenadas. Como las variables atrasadas b_{i} son calculadas, los mensajes salientes W_{k\rightarrow 1}, son calculados simultáneamente, negando por ello la necesidad de almacenar las variables atrasadas.

La carga del cálculo puede ser además mejorada por una aproximación paralela, como se ha descrito a continuación.

La fig. 13B es un diagrama de flujo del proceso para calcular mensajes salientes entre los nodos de comprobación y los nodos de bit usando una aproximación paralela, de acuerdo con una realización del presente invento. Para un nodo de comprobación k con entradas v_{n1\rightarrow k},v_{n2\rightarrow k},...,v_{ndc\rightarrow k} desde los d_{c} nodos de bit adyacentes, es calculado el siguiente parámetro, como en la operación 1311:

\gamma_{k}=g(v_{n1\rightarrow k},v_{n2\rightarrow k},...,v_{ndc\rightarrow k})

Se ha observado que la función g(.,.) puede ser expresada también como sigue:

g(a,b) = ln \frac{1 + e^{a+b}}{e^{a} + e^{b}}

Explotando la naturaleza recurrente de la función g(.,.), resulta la siguiente expresión:

40

Consiguientemente, w_{k\rightarrow nl} puede ser resuelto de la siguiente manera:

41

El término ln(.) de la anterior ecuación puede ser obtenido usando una tabla de búsqueda LUT_{x} que representa la función ln|e^{x}-1| (operación 1313). De modo distinto a las otras tablas de búsqueda LUT_{f} o LUT_{g}, la tabla LUT_{x} requeriría probablemente tantas entradas como número de niveles de cuantificación. Una vez que se ha obtenido \gamma_{k} el cálculo de w_{k->nl} para todos los n_{l} puede ocurrir en paralelo usando la anterior ecuación, por la operación 1315.

La latencia de cálculo de \gamma_{k} es ventajosamente log_{2}(d_{c}).

\newpage

Las figs. 14A-14C son gráficos que muestran resultados de simulación de códigos LDPC generados de acuerdo con distintas realizaciones del presente invento. En particular las figs. 14A-14C, muestran las prestaciones de códigos LDPC con modulación de mayor orden y tasas de código de 3/4 (QPSK, 1485 bits/símbolo), 2/3 (8-PSK, 1980 bits/símbolo), y 5/6 (8-PSK, 2474 bits/símbolo).

Existen dos aproximaciones generales para realizar las interconexiones entre nodos de comprobación y nodos de bit: (1) una aproximación completamente paralela, y (2) una aproximación parcialmente paralela. En arquitectura completamente paralela, todos los nodos y sus interconexiones son puestos en práctica físicamente. La ventaja de esta arquitectura es la velocidad.

La arquitectura completamente paralela, sin embargo, puede implicar mayor complejidad al realizar todos los nodos y sus conexiones. Por ello con la arquitectura completamente paralela, puede requerirse un tamaño de bloque menor para reducir la complejidad. En ese caso, para la misma frecuencia de reloj, puede resultar una reducción proporcional en la salida total y alguna degradación en prestaciones de FER frente a Es/No.

La segunda aproximación para poner en práctica códigos LDPC es realizar físicamente sólo un subconjunto del número total de los nodos y usar solamente este número limitado de nodos "físicos" para procesar todos los nodos "funcionales" del código. Incluso aunque las operaciones del descodificador LDPC pueden ser hechas extremadamente simples y pueden ser realizadas en paralelo, el desafío adicional en el diseño es cómo es establecida la comunicación entre nodos de bit y nodos de comprobación distribuidos "aleatoriamente". El descodificador 305 (de la fig. 3), de acuerdo con una realización del presente invento, accede a este problema accediendo a la memoria de un modo estructurado, como para realizar un código similarmente aleatorio. Esta aproximación es explicada con respecto a las figs. 15A y 15B.

Las figs. 15A y 15B son diagramas del borde superior y borde inferior, respectivamente, de la memoria organizada para soportar el acceso estructurado de modo que realice una aleatoriedad en la codificación LDPC, de acuerdo con una realización del presente invento. El acceso estructurado puede ser conseguido sin comprometer las prestaciones de un código verdaderamente aleatorio focalizando sobre la generación de la matriz de comprobación de paridad. En general, una matriz de comprobación de paridad puede ser especificada por las conexiones de los nodos de comprobación con los nodos de bit. Por ejemplo, los nodos de bits pueden ser divididos en grupos de un tamaño fijo, que con propósitos ilustrativos es 392. Adicionalmente, suponiendo los nodos de comprobación conectados al primer grado de bit de grado 3, por ejemplo, son numerados como a, b y c a continuación los nodos de comprobación conectados al segundo nodo de bit son numerados como a+p, b+p y c+p, los nodos de comprobación conectados al tercer nodo de bit son numerados como a+2p, b+2p, c+2p, etc.; donde p=(número de nodos de comprobación)/392. Para el siguiente grupo de 392 nodos de bit, los nodos de comprobación conectados al primer nodo de bit son diferentes de a, b y c de modo que con una elección adecuada de p, todos los nodos de comprobación tienen el mismo grado. Una búsqueda aleatoria es realizada sobre las constantes libres de tal modo que el código resultante LDPC es de ciclo 4 y de ciclo 6 libres. Debido a las características estructurales de la matriz de comprobación de paridad del presente invento, la información de borde puede ser almacenada para permitir el acceso concurrente a un grupo de valores de borde relevantes durante la descodificación.

En otras palabras, la aproximación del presente invento facilita el acceso a la memoria durante el tratamiento del nodo de comprobación y del nodo de bit. Los valores de los bordes en el gráfico bipartito pueden ser almacenados en un medio de almacenamiento, tal como una memoria de acceso aleatorio (RAM). Se ha observado que para un código LDPC verdaderamente aleatorio durante el tratamiento del nodo de comprobación y del nodo de bit, los valores de los bordes necesitarían ser accedidos uno por uno de una manera aleatoria. Sin embargo, tal esquema de acceso tradicional sería demasiado lento para una aplicación de tasa de datos elevada. Las RAM de las figs. 15A y 15B están organizadas de una manera, por lo que un gran grupo de bordes relevantes puede ser recogido en un ciclo de reloj; consiguientemente estos valores son colocados "juntos" en la memoria, de acuerdo con un esquema o disposición predeterminado. Se ha observado que, en realidad, incluso con un código verdaderamente aleatorio, para un grupo de nodos de comprobación (y respectivamente nodos de bit), los morder relevantes pueden ser colocados a continuación uno de otro en la RAM, pero entonces los bordes relevantes adyacentes a un grupo de nodos de bit (respectivamente nodos de comprobación) serán dispersados aleatoriamente en la RAM. Por ello, la "simultaneidad", bajo el presente invento, proviene del diseño de las propias matrices de comprobación de paridad. Es decir, el diseño de la matriz de comprobación asegura que los bordes relevantes para un grupo de nodos de bit y nodos de comprobación son simultáneamente colocados juntos en la RAM.

Como se ha visto en las figs. 15A y 15B, cada caja contiene el valor de un borde, que es de múltiples bits (por ejemplo 6). La RAM del borde de acuerdo con una realización del presente invento está dividida en dos partes: RAM 1501 de borde superior (fig. A) y RAM 1503 de borde inferior (fig. 15B). La RAM 1503 del borde inferior contiene los bordes entre los nodos de bit de grado 2, por ejemplo, y nodos de comprobación. La RAM de borde superior contiene los bordes entre nodos de bit de grado mayor de 2 y nodos de comprobación. Por ello, para cada nodo de comprobación, 2 bordes adyacentes son almacenados en la RAM 1503 inferior, y el resto de los bordes son almacenados en la RAM 1501 de borde superior. Por ejemplo, los tamaños de la RAM 1501 de borde superior y de la RAM 1503 de borde inferior para distintas tasas de código están dados en la tabla 14:

TABLA 14

42

Basado en la tabla 14, una RAM de borde de tamaño 576 x 392 es suficiente para almacenar las métricas de borde para todas las tasas de código de 1/2, 2/3, 3/4 y 5/6.

Como se ha observado, bajo este escenario ejemplar, un grupo de 392 nodos de bit y 392 nodos de comprobación son seleccionados para tratar al mismo tiempo. Para tratar 392 nodos de comprobación, q=d_{c}-2 filas consecutivas son accedidas desde la RAM 1501 de borde superior, y 2 filas consecutivas desde la RAM 1503 de borde inferior. El valor de d_{c} depende del código específico, por ejemplo d_{c}=7 para tasa 1/2, d_{c}=10 para tasa 2/3, d_{c}=16 para tasa 3/4 y d_{c} =22 para tasa 5/6 para los códigos anteriores. Desde luego son posibles otros valores de d_{c} para otros códigos. En este caso, q+2 es el grado de cada nodo de comprobación.

Para el tratamiento del nodo de bit, si el grupo de 392 nodos de bit tiene grado 2, sus bordes están situados en 2 filas consecutivas de la RAM 1503 de borde inferior. Si los nodos de bit tienen grado d>2, sus bordes están situados en algunas d filas de la RAM 1501 de borde superior. La dirección de estas d filas puede ser almacenada en una memoria no volátil, tal como una Memoria Sólo de Lectura (ROM). Los bordes en una de las filas corresponden a los primeros bordes de 392 nodos de bits, los bordes de otra fila corresponden a los segundos bordes de 392 nodos de bit, etc. Además para cada fila, el índice de columna del borde que pertenece al primer nodo de bit en el grupo de 392 puede ser también almacenado en la ROM. Los bordes que corresponden al segundo, tercero, etc., nodos de bit siguen el índice de la columna de comienzo de una manera "envuelta alrededor". Por ejemplo, si el borde de orden j de la fila pertenece al primer nodo de bit entonces el borde de orden (j+1) pertenece al segundo nodo de bit y el borde de orden (j+2) pertenece al tercer nodo de bit,..., y el borde de orden (j-1) pertenece al nodo de bit de orden 392.

Con la organización mostrada en las figs. 15A y 15B, la velocidad de acceso de memoria es muy mejorada durante la codificación LDPC.

La fig. 16 ilustra un sistema de ordenador sobre el que puede ser puesta en práctica una realización de acuerdo con el presente invento. El sistema de ordenador 1600 incluye una línea de transmisión o bus 1601 u otro mecanismo de comunicación para comunicar información, y un procesador 1603 acoplado a la línea de transmisión 1601 para tratar la información. El sistema de ordenador 1600 también incluye memoria principal 1605, tal como una memoria de acceso aleatorio (RAM) u otro dispositivo de almacenamiento dinámico, acoplado a la línea de transmisión 1601 para almacenar información e instrucciones que han de ser ejecutadas por el procesador 1603. La memoria principal 1605 puede también ser usada para almacenar temporalmente variables u otra información intermedia durante la ejecución de instrucciones que han de ser ejecutadas por el procesador 1603. El sistema de ordenador 1600 incluye además una memoria sólo de lectura (ROM) 1607 u otro dispositivo de almacenamiento estático acoplado a la línea de transmisión 1601 para almacenar información e instrucciones estáticas para el procesador 1603. Un dispositivo de almacenamiento 1609, tal como un disco magnético o disco óptico, está acoplado adicionalmente a la línea de transmisión 1601 para almacenar información e instrucciones.

El sistema de ordenador 1600 puede estar acoplado a través de la línea de transmisión 1601 a una pantalla de presentación 1611, tal 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 presentar información a un usuario del ordenador. Un dispositivo de entrada 1613, tal como un teclado que incluye teclas alfanuméricas y otras, está acoplado a la línea de transmisión 1601 para comunicar información y mandar u ordenar selecciones al procesador 1603. Otro tipo de dispositivo de entrada de usuario es el control por cursor 1615, tal como un ratón, una bola, o teclas de dirección del cursor para comunicar información de dirección y ordenar selecciones al procesador 1603 para controlar el movimiento del cursor sobre la pantalla de presentación 1611.

De acuerdo con una realización del invento, la generación de códigos LDPC es proporcionada por el sistema de ordenador 1600 en respuesta al procesador 1603 que ejecuta una disposición de instrucciones contenidas en la memoria principal 1605. Tales instrucciones pueden ser leídas en la memoria principal 1605 desde otro medio legible por ordenador, tal como el dispositivo de almacenamiento 1609. La ejecución de la disposición de instrucciones contenidas en la memoria principal 1605 hace que el procesador 1603 realice las operaciones del proceso descritas aquí. Uno o más procesadores en una disposición de tratamiento múltiple pueden también ser empleados para ejecutar las instrucciones contenidas en la memoria principal 1605. En realizaciones alternativas, pueden usarse circuitos cableados de hardware en lugar de o en combinación con instrucciones de software para poner en práctica la realización del presente invento. Así, realizaciones del presente invento no están limitadas a ninguna combinación específica de circuitos de hardware y software.

El sistema de ordenador 1600 también incluye un enlace de comunicación 1617 acoplado a la línea de transmisión 1601. El enlace de comunicación 1617 proporciona una comunicación de datos de dos sentidos que se acopla a un enlace de red 1619 conectado a una red local 1621. Por ejemplo, el enlace de comunicación 1617 puede ser una tarjeta o módem de línea de abonado digital (DSL), una tarjeta de red digital de servicios integrados (ISDN), un módem por cable, o un módem telefónico para proporcionar una conexión de comunicación de datos a un tipo correspondiente de línea telefónica. Como otro ejemplo, el enlace de comunicación 1617 puede ser una tarjeta de red de área local (LAN) (por ejemplo para Ethernet™ o una red de Modelo de Transferencia Asíncrona (ATM)) para proporcionar una conexión de comunicación de datos a una LAN compatible. Los enlaces inalámbricos pueden también ser utilizados. En cualquiera de tales puestas en práctica, el enlace de comunicación 1617 envía y recibe señales eléctricas, electromagnéticas u ópticas que transportan corrientes de datos digitales que representan distintos tipos de información. Además, el enlace de comunicación 1617 puede incluir dispositivos de enlace periféricos, tales como un enlace de Línea de Transmisión o Bus en Serie Universal (USB), un enlace de (Asociación Internacional de Tarjeta de Memoria de Ordenador Personal) PCMCIA, etc.

El enlace de red 1619 proporciona típicamente comunicación de datos a través de una o más redes a otros dispositivos de datos. Por ejemplo, el enlace de red 1619 puede proporcionar una conexión a través de una red local 1621 a un ordenador anfitrión 1623, que tiene conectividad con una red 1625 (por ejemplo una red de área amplia (WAN) o la red de comunicación global de paquetes de datos corrientemente denominada ahora como "Internet") o con un equipo de datos accionado por el proveedor de servicios. La red local 1621 y la red 1625 usan ambas señales eléctricas, electromagnéticas u ópticas para transportar información e instrucciones. Las señales a través de las distintas redes y las señales en el enlace de red 1619 y a través del enlace de comunicación 1617, que comunica datos digitales con el sistema de ordenador 1600, son formas ejemplares de ondas portadoras que soportan la información e instrucciones.

El sistema de ordenador 1600 puede enviar mensajes y recibir datos, incluyendo código de programa, a través de la red o redes, el enlace de red 1619, y el enlace de comunicación 1617. En el ejemplo de Internet, un servidor (no mostrado) podría transmitir el código requerido que pertenece a un programa de aplicación para poner en práctica una realización del presente invento a través de la red 1625, la red local 1621 y el enlace de comunicación 1617. El procesador 1603 puede ejecutar el código trasmitido mientras está siendo recibido y/o almacenar el código en el dispositivo de almacenamiento 169, u otro almacenamiento no volátil para posterior ejecución. De esta manera, el sistema de ordenador 1600 puede obtener un código de aplicación en forma de una onda portadora.

El término "medio legible por ordenador" como es usado aquí se refiere a cualquier medio que participa en proporcionar instrucciones al procesador 1603 para su ejecución. Tal medio puede tener muchas formas, incluyendo pero no estando limitado a medios no volátiles, medios volátiles, y medios de transmisión. Los medios no volátiles incluyen, por ejemplo, discos ópticos o magnéticos, tales como el dispositivo de almacenamiento 1609. Los medios volátiles incluyen memoria dinámica, tal como la memoria principal 1605. Los medios de transmisión incluyen cables coaxiales, hilos de cobre y fibra óptica, incluyendo los hilos que comprende la línea de transmisión 1601. Los medios de transmisión pueden también tener la forma de ondas acústicas, ópticas o electromagnéticas, tales como las generadas durante las comunicaciones de datos a frecuencia de radio (RF) e infrarrojos (IR). Formas comunes de medios legibles por ordenador incluyen, por ejemplo, un disquete, un disco flexible, disco duro, cinta magnética, cualquier otro medio magnético, un CD-ROM, CDRW, DVD, cualquier otro medio óptico, tarjetas perforadas, cinta de papel, láminas de marca óptica, cualquier otro medio físico con diseños de agujeros o otros índices ópticamente reconocibles, una RAM, una PROM, una EPROM, una FLASH_EPROM, cualquier otro chip o cartucho de memoria, una onda portadora, cualquier otro medio a partir del cual pueda leer un ordenador.

Distintas formas de medios legibles por ordenador puede estar implicadas en proporcionar instrucciones a un procesador para su ejecución. Por ejemplo, las instrucciones para llevar a la práctica al menos parte del presente invento pueden ser originadas inicialmente en un disco magnético de un ordenador remoto. En tal escenario, el ordenador remoto carga las instrucciones en la memoria principal y envía las instrucciones sobre una línea telefónica usando un módem. Un módem de un sistema de ordenador local recibe los datos en la línea telefónica y usa un transmisor de infrarrojos para convertir los datos en una señal infrarroja y transmitir la señal infrarroja a un dispositivo informático portátil, tal como una agenda digital personal (PDA) y un portátil. Un detector de infrarrojos en el dispositivo informático portátil recibe la información e instrucciones nacidas mediante la señal infrarroja y sitúa los datos en una línea de transmisión o bus. La línea de transmisión transporta los datos a la memoria principal, desde la cual el procesador recupera y ejecuta las instrucciones. La instrucciones recibidas por la memoria principal pueden ser almacenadas opcionalmente en un dispositivo de almacenamiento bien antes o bien después de la ejecución por el procesador.

Consiguientemente, las distintas realizaciones del presente invento proporcionan una aproximación para codificar códigos de Comprobación de Paridad de Baja Densidad (LDPC) estructurados. La estructura de los códigos LDPC es proporcionada restringiendo parte de la matriz de comprobación de paridad para que sea triangular inferior y/o satisfaciendo otros requisitos tales como que la comunicación entre nodos de bit y nodos de comprobación del descodificador es simplificada. La memoria de almacenamiento de información que respetar que representa la abate de comprobación La claridad estructurada es accedida. La información es organizada en forma tabular, en la que cada fila representa ocurrencias de valores de uno dentro de una primera columna de un grupo de columnas de la matriz de comprobación de paridad. Las filas corresponden a grupos de columna de la matriz de comprobación de paridad, en la que columnas subsiguientes dentro de cada uno de los grupos son derivadas de acuerdo con una operación predeterminada (por ejemplo desplazamiento cíclico, suma, etc.). Una señal codificada LDPC basada en la información almacenada representa la matriz de comprobación de paridad. De acuerdo con una realización del presente invento, un codificador de Bose Chaudhuri Hocquenghem (BCH) es utilizado por el transmisor para codificar una señal de entrada que usa códigos BCH, en los que la señal codificada de LDPC correspondiente a la señal de entrada representa un código que tiene un código BCH exterior y un código LDPC interior. Además, un codificador de comprobación de redundancia cíclica (CRC) es suministrado para codificar la señal de entrada de acuerdo con un código CRC. La anterior aproximación produce una complejidad reducida sin sacrificar prestaciones.

Aunque el presente invento ha sido descrito en conexión con varias realizaciones y puestas en práctica, el presente invento no está así limitado a ello sino que cubre varias modificaciones y disposiciones equivalentes obvias, que caen dentro del propósito de las reivindicaciones adjuntas.

Claims

1. Un método de codificar que comprende: acceder a la memoria ((1605, 1607) que almacena información que representa una matriz de comprobación de paridad estructurada de códigos de Comprobación de Paridad de Baja Densidad (LDPC), estando la información organizada en forma tabular, representando cada fila de la información en memoria, ocurrencias de valores de uno dentro de una primera columna de un grupo de columnas de la matriz de comprobación de paridad, correspondiendo las filas a grupos de columnas de la matriz de comprobación de paridad, y siendo derivadas columnas subsiguientes dentro de cada uno de los grupos de acuerdo a una operación predeterminada; inicializar acumuladores de bit de paridad a cero, en que los acumuladores de bit de paridad corresponden a bits de paridad; acumular el primer bit de información con índice jM del grupo de orden j de M bits de información en el acumulador de bit de paridad en la dirección i especificada si la entrada de orden j en la columna de orden (jM)de la matriz de comprobación de paridad es 1, donde j=0,1,2,3,...k_{ldpc}/M-1; y emitir una señal codificada de LDPC basada en la información almacenada que representa la matriz de comprobación de paridad, caracterizado por, después de la operación de acumular el primer bit de información, las siguientes operaciones: acumular cada uno de los (M-1) bits de información restantes con índice m =jM+1,jM+2,jM+3,...,(j+1)M-1 del grupo de orden j en uno o más acumuladores de bit de paridad, relacionado a cada acumulador de bit de paridad en el que el primer bit de información con índice jM en el grupo fue acumulado, en una dirección {x+m mod Mxq} mod(n_{ldpc}-k_{ldpc}), donde n_{ldpc} representa el tamaño de palabra de código, k_{ldpc} representa el tamaño del bloque de información, x indica la dirección de cada acumulador de bit de paridad en la que el primer bit de información con índice jM en el grupo fue acumulada, y q es una constante dependiente de la tasa de código; y después de que todos los bits de información son evacuados, realizar operaciones, comenzando con i=1 de acuerdo a, i=1,2,...,n_{ldpc}-k_{ldpc}-1, para obtener bits de paridad final p_{i}, i=0,1,2,...,n_{ldpc}-k_{ldpc}-1, en los que p_{i} indica el contenido del acumulador de bit de paridad en la dirección i.

2. Un método según la reivindicación 1ª, en el que el funcionamiento predeterminado especifica la operación de: realizar un desplazamiento cíclico por q posiciones en la primera columna de cada una del grupo de columnas.

3. Un método según la reivindicación 1ª, en el que M=360.

4. Un método según la reivindicación 1ª, en el que la constante q dependiente del código es 60, 30, 90, 45, 36, 72, 20 y 18 para tasas de código 2/3, 5/6, 1/2, 3/4, 4/5, 3/5, 8/9, y 9/10, respectivamente.

5. Un método según la reivindicación 1ª, que comprende además: modular la señal codificada LDPC de acuerdo con una constelación de señal que incluye uno de entre Codificado de Desfase de 8-PSK, Modulación de Amplitud en Cuadratura de 16-QAM, Codificado de Desfase en Cuadratura QPSK, Codificado de Desfase en Amplitud de 16-APSK y 32-APSK.

6. Un método según la reivindicación 1ª, en el que los bits de información son obtenidos codificando una señal de entrada de acuerdo con códigos de Bose Chaudhuri Hocquenghem (BCH).

7. Un método según la reivindicación 6ª, en el que el número de bits de BCH redundante es n_{BCH}-k_{BCH}=16*t en el que t representa la capacidad de corregir error del código BCH, n_{BCH} es el tamaño de la palabra de código del código BCH y k_{BCH} es el tamaño del bloque de información del código BCH.

8. Un método según la reivindicación 6ª, en el que la capacidad de corrección de error del código BCH es 12 bits cuando es usado en concatenación con códigos LDPC de tasa 1/2, 3/4, 4/5 y 3/5, es 10 bits cuando es usado en concatenación con códigos LDPC de tasa 2/3 y 5/6, y es 8 bits cuando es usado en concatenación con códigos LDPC de tasa 8/9 y 9/10.

9. Un método según la reivindicación 1ª, en el que M=360 y los índices de fila de 1 en la columna de orden (jM), j=0,1,2,3,...,(k_{ldpc}/360)-1, de la matriz de comprobación de paridad están dados en la fila de orden j de acuerdo con una de las Tablas 1-8:

TABLA 1

43

TABLA 1 (continuación)

44

TABLA 1 (continuación)

45

TABLA 2

46

TABLA 2 (continuación)

47

TABLA 2 (continuación)

48

TABLA 2 (continuación)

49

TABLA 3

50

TABLA 3 (continuación)

51

TABLA 3 (continuación)

52

TABLA 4

53

TABLA 4 (continuación)

54

TABLA 4 (continuación)

55

TABLA 5

56

TABLA 5 (continuación)

57

TABLA 5 (continuación)

58

TABLA 6

59

TABLA 6 (continuación)

60

TABLA 6 (continuación)

61

TABLA 7

62

TABLA 7 (continuación)

63

TABLA 7 (continuación)

64

TABLA 7 (continuación)

65

TABLA 8

66

TABLA 8 (continuación)

67

TABLA 8 (continuación)

68

TABLA 8 (continuación)

69

\newpage

10. Un método según la reivindicación 9ª, en el que los índices de fila de 1 en otros índices m de columna, m módulo 360\neq0 y m<k_{ldpc} de la matriz de comprobación de paridad están dados por {x+m mod 360xq} mod(n_{ldpc}-k_{ldpc}) donde q=60 para código LDPC de tasa 2/3, q=30 para código LDPC de tasa 5/6, q=90 para código LDPC de tasa 1/2, q=45 para código LDPC de tasa 3/4, q=36 para código LDPC de tasa 4/5, q=72 para código LDPC de tasa 3/5, q=20 para código LDPC de tasa 8/9, q=18 para código LDPC de tasa 9/10, en el que x indica una entrada en la fila de orden j de las Tablas 1-8, donde j=int{m/360}, e int{.} indica la función entero, estando dados los índices de fila de 1 en el índice de columna m=k_{ldpc}+j, j=0,1,2,...,n_{ldpc}-k_{ldpc}-2, de la matriz de comprobación de paridad por j y j+1, estando dados el índice de fila de 1 en el índice de columna n_{ldpc}-1 de la matriz de comprobación de paridad por n_{ldpc}-k_{ldpc} -1.

11. Un medio legible por ordenador que soporta instrucciones para codificar, estando dispuestas, dichas instrucciones, al producirse su ejecución, para hacer que uno o más procesadores realicen el método de cualquiera de las reivindicaciones 1ª a 10ª.

12. Un codificador para generar palabras de código de Comprobación de Paridad de Baja Densidad (LDPC), que comprende memoria (1605, 1607) que almacena información que representa una matriz de comprobación de paridad estructurada de los códigos LDPC, estando la información organizada en forma tabular, representando cada fila de la información en memoria, ocurrencias de valores de uno dentro de una primera columna de un grupo de columnas de la matriz de comprobación de paridad, correspondiendo las filas a grupos de columnas de la matriz de comprobación de paridad, y siendo derivadas columnas subsiguientes dentro de cada uno de los grupos a una operación predeterminada; medios para recuperar la información almacenada que representa la matriz de comprobación de paridad para emitir una señal codificada LDPC; y medios para inicializar los acumuladores de bit de paridad a cero, en el que el primer bit de información con índice jM del grupo de orden j de M bits de información es acumulada en el acumulador de bit de paridad en la dirección i especificada si la entrada de orden j en la columna de orden (jM)de la matriz de comprobación de paridad es 1, donde j=0,1,2,3,...k_{ldpc}/M-1; caracterizado por: medios para acumular cada uno de los (M-1) bits de información restantes con índice m =jM+1,jM+2,jM+3,...,(j+1)M-1 del grupo de orden j en uno o más acumuladores de bit de paridad, relacionado a cada acumulador de bit de paridad en el que el primer bit de información con índice jM en el grupo fue acumulado, en una dirección {x+m mod Mxq} mod(n_{ldpc}-k_{ldpc}), donde n_{ldpc} representa el tamaño de palabra de código, k_{ldpc} representa el tamaño del bloque de información, x indica la dirección de cada acumulador de bit de paridad en la que el primer bit de información con índice jM en el grupo fue acumulada, y q es una constante dependiente de la tasa de código; y medios para realizar operaciones, después de que todos los bits de información son evacuados, comenzando con i=1 de acuerdo ap_{i} = p_{i} \oplus p_{i-l}, i=1,2,...,n_{ldpc}-k_{ldpc}-1, para obtener bits de paridad final p_{i}, i=0,1,2,...,n_{ldpc}-k_{ldpc}-1, en el que p_{i} indica el contenido del acumulador de bit de paridad en la dirección i.

13. Un codificador según la reivindicación 12ª, en el que la operación predeterminada especifica un desplazamiento cíclico por q posiciones en la primera columna de cada una del grupo de columnas.

14. Un codificador según la reivindicación 12ª, en el que M=360.

15. Un codificador según la reivindicación 12ª, en el que la constante q dependiente del código es 60, 30, 90, 45, 36, 72, 20 y 18 para tasas de código 2/3, 5/6, 1/2, 3/4, 4/5, 3/5, 8/9, y 9/10, respectivamente.

16. Un codificador según la reivindicación 12ª, en el que la señal codificada LDPC es modulada de acuerdo con una constelación de señal que incluye uno de entre Codificado de Desfase de 8-PSK, Modulación de Amplitud en Cuadratura de 16-QAM, Codificado de Desfase en Cuadratura QPSK, Codificado de Desfase en Amplitud de 16-APSK y 32-APSK.

17. Un codificador según la reivindicación 12ª, que comprende además un codificador de Bose Chaudhuri Hocquenghem (BCH), en el que los bits de información son obtenidos a partir del codificador BCH que está configurado para codificar una señal de entrada usando códigos de (BCH).

18. Un codificador según la reivindicación 17ª, en el que el número de bits de BCH redundantes es n_{BCH}-k_{BCH}=16*t en el que t representa la capacidad de corregir error del código BCH, n_{BCH} es el tamaño de la palabra de código del código BCH y k_{BCH} es el tamaño del bloque de información del código BCH.

19. Un codificador según la reivindicación 17ª, en el que la capacidad de corrección de error del código BCH es 12 bits cuando es usado en concatenación con códigos LDPC de tasa 1/2, 3/4, 4/5 y 3/5, es 10 bits cuando es usado en concatenación con códigos LDPC de tasa 2/3 y 5/6, y es 8 bits cuando es usado en concatenación con códigos LDPC de tasa 8/9 y 9/10.

20. Un transmisor para transmitir palabras de código de Comprobación de Paridad de Baja Densidad (LDPC), que comprende el codificador de cualquiera de las reivindicaciones 12ª a 19ª.