Procedimientos y aparatos para descodificar códigos LDPC.

Un procedimiento de realización del procesamiento de descodificación del paso de mensajes de control de paridad,

usando gráficos vectorizados de LDPC que representan matrices elevadas de control de paridad, por lo cual, en una matriz elevada de control de paridad, los elementos 0 de una matriz H de control de paridad de un código de LDPC proyectado son reemplazados por matrices de ceros de dimensiones ZxZ, y los elementos 1 de la matriz H de control de paridad son reemplazados por matrices de permutación de dimensiones ZxZ, comprendiendo el procedimiento las etapas de:

mantener L conjuntos de mensajes de K bits en un dispositivo (1506, 1607, 1707) de almacenamiento de mensajes, incluyendo cada conjunto de mensajes de K bits los primeros Z mensajes en pasar, donde L y Z son números enteros positivos mayores que uno y K es un número entero positivo distinto de cero, por lo cual cada uno de dichos conjuntos de Z mensajes de K bits es escrito o leído como una unidad individual, usando una instrucción SIMD;

emitir uno de dichos conjuntos leídos de Z mensajes de K bits, desde el dispositivo (1506, 1607, 1707) de almacenamiento de mensajes;

realizar una operación de reordenamiento de mensajes sobre dicho conjunto leído de Z mensajes de K bits, para producir un conjunto reordenado de Z mensajes de K bits;

suministrar, en paralelo, los Z mensajes de K bits en el conjunto reordenado de mensajes a un procesador vectorial (1508, 1608, 1707) de nodos, que incluye Z unidades de procesamiento paralelo de nodos; operar el procesador vectorial (1508, 1608, 1707) de nodos para realizar operaciones de procesamiento de nodos variables, usando como entrada los Z mensajes de K bits suministrados, por lo cual una operación de procesamiento de nodos variables es realizada en cada una de las Z unidades de procesamiento paralelo de nodos, y una operación de procesamiento de nodos variables incluye generar un valor de decisión, y examinar los valores de decisión generados para determinar si ha sido satisfecha una condición de descodificación.

Procedimientos y aparatos para descodificar códigos LDPC Campo de la invención

La presente invención está orientada a procedimientos y aparatos para detectar y / o corregir errores en datos binarios, p. ej., mediante el uso de códigos de control de pandad tales como los códigos de control de pandad de baja densidad (LDPC).

Antecedentes

En la moderna era de la información, los valores binarios, p. ej., unos y ceros, son usados para representar y comunicar diversos tipos de información, p. ej., de vídeo, de audio, información estadística, etc. Lamentablemente, durante el almacenamiento, la transmisión y / o el procesamiento de datos binarios, pueden introducirse errores no intencionalmente, p. ej., un uno puede ser cambiado por un cero o viceversa.

En general, en el caso de la transmisión de datos, un receptor observa cada bit recibido en presencia de ruido o distorsión, y solamente se obtiene una indicación del valor del bit. En estas circunstancias, se interpretan los valores observados como una fuente de bits "blandos". Un bit blando indica una estimación preferida del valor del bit, es decir, un uno o un cero, junto con alguna indicación de la fiabilidad de esa estimación. Si bien el número de errores puede ser relativamente bajo, incluso un pequeño número de errores, o un pequeño nivel de distorsión, puede dar como resultado que los datos sean ¡nutilizables o, en el caso de errores de transmisión, puede requerir la retransmisión de los datos.

A fin de proporcionar un mecanismo para comprobar errores y, en algunos casos, corregir errores, los datos binarios pueden ser codificados para introducir redundancia, cuidadosamente diseñada. La codificación de una unidad de datos produce lo que usualmente se denomina una palabra de código. Debido a su redundancia, una palabra de código incluirá a menudo más bits que la unidad de entrada de datos a partir de la cual se produjo la palabra de código.

Cuando las señales surgidas de las palabras de código transmitidas son recibidas o procesadas, la información redundante incluida en la palabra de código, según lo observado en la señal, puede ser usada para identificar y / o corregir errores en, o eliminar la distorsión de, la señal recibida, a fin de recuperar la unidad original de datos. Tal comprobación y / o corrección de errores puede ser implementada como parte de un proceso de descodificación. En ausencia de errores, o en el caso de errores o distorsiones corregibles, la descodificación puede ser usada para recuperar, de los datos de origen que se están procesando, la unidad original de datos que fue codificada. En el caso de errores irrecuperables, el proceso de descodificación puede producir alguna indicación de que los datos originales no pueden ser recuperados completamente. Tales indicaciones de fallo de descodificación pueden ser usadas para iniciar la retransmisión de los datos.

Si bien la redundancia de datos puede aumentar la fiabilidad de los datos a almacenar o transmitir, es a cambio del coste de espacio de almacenamiento y / o del uso del valioso ancho de banda de las comunicaciones. En consecuencia, es deseable añadir redundancia de manera eficaz, maximizando la magnitud de la capacidad ganada de corrección / detección de errores, para una magnitud dada de redundancia introducida en los datos.

Con el creciente uso de líneas de fibra óptica para la comunicación de datos, y los aumentos en la velocidad a la cual los datos pueden ser leídos de, y almacenados en, dispositivos de almacenamiento, p. ej., unidades de disco, cintas, etc., hay una creciente necesidad, no solamente de un uso eficaz de la capacidad de almacenamiento y transmisión de datos, sino también de la capacidad de codificar y descodificar datos a altas tasas de velocidad.

Si bien son importantes la eficacia de codificación y las altas velocidades de datos, para que un sistema de codificación y / o descodificación sea práctico para su uso en una amplia gama de dispositivos, p. ej., dispositivos de consumo, es importante que los codificadores y / o descodificadores sean capaces de ser implementados a un coste razonable. En consecuencia, la capacidad de implementar eficazmente los esquemas de codificación / descodificación usados con fines de corrección y / o detección de errores, p. ej., en términos de costes de hardware, puede ser importante.

Diversos tipos de esquemas de codificación han sido usados a lo largo de los años con fines de corrección de errores. Una clase de códigos, generalmente mencionados como "turbo-códigos", fueron inventados recientemente (1993). Los turbo-códigos ofrecen significativos beneficios sobre técnicas más antiguas de codificación, tales como los códigos convolutivos, y han tenido numerosas aplicaciones.

Conjuntamente con la llegada de los turbo-códigos, ha habido creciente interés en otra clase de códigos relacionados, aparentemente más sencillos, usualmente denominados códigos de control de paridad de baja densidad (LDPC). Los códigos de LDPC fueron efectivamente inventados por Gallager alrededor de 40 años atrás (1961), pero solo recientemente han llegado a destacarse. Los turbo-códigos y los códigos de LDPC son esquemas de codificación que son usados en el contexto de los denominados sistemas de codificación iterativa, es decir, son descodificados usando

descodificadores iterativos. Recientemente, se ha mostrado que los códigos de LDPC pueden proporcionar muy buenas prestaciones de detección y corrección de errores, sobrepasando o igualando las de los turbo-códigos para grandes palabras de código, p. ej., con tamaños de palabra de código que superan aproximadamente 1.000 bits, dada una selección adecuada de parámetros de codificación de LDPC. Además, los códigos de LDPC, en potencia, pueden ser descodificados a velocidades mucho mayores que los turbo-códigos.

En muchos esquemas de codificación, las palabras de código más largas son a menudo más flexibles para fines de detección y corrección de errores, debido a la interacción de la codificación sobre un mayor número de bits. De tal modo, el uso de palabras de código largas puede ser beneficioso en términos del aumento de la capacidad de detectar y corregir errores. Esto es especialmente cierto para los turbo-códigos y los códigos de LDPC. Así, en muchas aplicaciones es deseable el uso de palabras de código largas, p. ej., palabras de código que superan los mil bits de longitud.

La principal dificultad hallada en la adopción de la codificación de LDPC y la Turbo-codificación en el contexto de las palabras de código largas, donde el uso de tales códigos ofrece la mejor promesa, es la complejidad de implementar estos sistemas de codificación. En un sentido práctico, la complejidad se traduce directamente en el coste de implementación. Ambos sistemas de codificación son significativamente más complejos que los sistemas de codificación usados tradicionalmente, tales como los códigos convolutivos y los códigos de Reed-Solomon.

El análisis de complejidad de los algoritmos de procesamiento de señales se centra usualmente en totales de operaciones. Al intentar explotar el paralelismo de hardware en sistemas de codificación iterativa, especialmente en el caso de los códigos de LDPC, una significativa complejidad surge, no de los requisitos de cálculo, sino más bien de los requisitos de encaminamiento. La raíz del problema está en la construcción de los códigos en sí.

Los códigos de LDPC y los turbo-códigos se apoyan en la intercalación de mensajes dentro de un proceso iterativo. A fin de que el código rinda bien, la intercalación debe tener buenas propiedades de mezcla. Esto hace necesaria la implementación de un complejo proceso de intercalación.

Los códigos de LDPC están bien representados por gráficos bipartitos, a menudo llamado gráficos de Tanner, en los cuales un conjunto de nodos, los nodos variables, corresponde a los bits de la palabra de código, y el otro conjunto de nodos, los nodos de restricción, a menudo llamados nodos de verificación, corresponden al conjunto de restricciones de control de paridad que definen el código. Los bordes en el gráfico conectan nodos variables con nodos de restricción. Un nodo variable y un nodo de restricción se dicen vecinos si están conectados por un borde en el gráfico. Para simplificar, suponemos en general que un par de nodos está conectado por un borde, a lo sumo. A cada nodo variable está asociado un bit de la palabra de código. En algunos casos, algunos de estos bits podrían ser punzados o conocidos, según se expone adicionalmente más adelante.

Una secuencia de bits asociada uno a uno con la secuencia de nodos variables es una palabra de código del código si y solo si, para... [Seguir leyendo]

1. Un procedimiento de realización del procesamiento de descodificación del paso de mensajes de control de paridad,

usando gráficos vectorizados de LDPC que representan matrices elevadas de control de paridad, por lo cual, en una matriz elevada de control de paridad, los elementos 0 de una matriz H de control de paridad de un código de LDPC proyectado son reemplazados por matrices de ceros de dimensiones ZxZ, y los elementos 1 de la matriz H de control de paridad son reemplazados por matrices de permutación de dimensiones ZxZ, comprendiendo el procedimiento las etapas de:

mantener L conjuntos de mensajes de K bits en un dispositivo (1506, 1607, 1707) de almacenamiento de mensajes, incluyendo cada conjunto de mensajes de K bits los primeros Z mensajes en pasar, donde L y Z son números enteros positivos mayores que uno y K es un número entero positivo distinto de cero, por lo cual cada uno de dichos conjuntos de Z mensajes de K bits es escrito o leído como una unidad individual, usando una instrucción SIMD;

emitir uno de dichos conjuntos leídos de Z mensajes de K bits, desde el dispositivo (1506, 1607, 1707) de almacenamiento de mensajes;

realizar una operación de reordenamiento de mensajes sobre dicho conjunto leído de Z mensajes de K bits, para producir un conjunto reordenado de Z mensajes de K bits;

suministrar, en paralelo, los Z mensajes de K bits en el conjunto reordenado de mensajes a un procesador vectorial (1508, 1608, 1707) de nodos, que incluye Z unidades de procesamiento paralelo de nodos; operar el procesador vectorial (1508, 1608, 1707) de nodos para realizar operaciones de procesamiento de nodos variables, usando como entrada los Z mensajes de K bits suministrados, por lo cual una operación de procesamiento de nodos variables es realizada en cada una de las Z unidades de procesamiento paralelo de nodos, y una operación de procesamiento de nodos variables incluye generar un valor de decisión, y

examinar los valores de decisión generados para determinar si ha sido satisfecha una condición de descodificación.

2. El procedimiento de la reivindicación 1, que comprende adicionalmente: generar un identificador de conjunto de mensajes que indica el conjunto de Z mensajes de K bits a emitir por el dispositivo (1506, 1607, 1707) de almacenamiento de mensajes.

3. El procedimiento de la reivindicación 2, en el cual la etapa de emitir uno de dichos conjuntos de Z mensajes de K bits

incluye: realizar la operación SIMD de salida usando dicho identificador de conjunto de mensajes para identificar el conjunto de Z mensajes de K bits a emitir como una unidad individual.

4. El procedimiento de la reivindicación 1, que comprende además: realizar una segunda operación de reordenamiento

de mensajes, siendo realizada la segunda operación de reordenamiento de mensajes sobre un conjunto de Z mensajes de K bits emitidos desde el procesador vectorial (1508, 1608, 1708) de nodos, para producir un conjunto reordenado de mensajes de descodificador generados.

5. El procedimiento de la reivindicación 4, en el cual la etapa de realizar una segunda operación de reordenamiento de

mensajes incluye realizar la inversa de la operación de reordenamiento de mensajes realizada sobre dicho conjunto de Z mensajes de K bits emitido por el dispositivo (1506, 1607, 1707) de almacenamiento de mensajes.

6. El procedimiento de la reivindicación 5, en el cual dicha operación de reordenamiento de mensajes es realizada como una función de la información de permutación del conjunto de mensajes, que incluye información de rotación cíclica.

7. El procedimiento de la reivindicación 1, que comprende adicionalmente: acceder a información almacenada de permutación de conjuntos de mensajes; y en el cual la etapa de realizar una operación de reordenamiento de mensajes incluye la etapa de: realizar dicho reordenamiento como una función de la información almacenada de permutación de conjuntos de mensajes a la que se ha accedido.

8. Un aparato (1500, 1600, 1700) para realizar operaciones de descodificación del paso de mensajes de control de paridad, usando gráficos de LDPC vectorizados que representan matrices elevadas de control de paridad, por lo cual, en una matriz elevada de control de paridad, los elementos 0 de una matriz H de control de paridad de un código de LDPC proyectado son reemplazados por matrices de ceros de dimensiones ZxZ, y los elementos 1 de la matriz H de control de paridad son reemplazados por matrices de permutación de dimensiones ZxZ, comprendiendo el aparato:

un origen (1506, 1607, 1707) de mensajes para suministrar al menos un conjunto de Z mensajes de K bits desde

uno cualquiera de entre al menos L conjuntos de Z mensajes de K bits, donde Z es un número entero positivo mayor que uno y K y L son números enteros positivos distintos de cero, por lo cual cada uno de dichos conjuntos de Z mensajes de K bits es escrito o leído como una unidad individual usando una instrucción SIMD;

un procesador vectorial (1508, 1608, 1708) de nodos que incluye Z unidades de procesamiento paralelo de nodos, siendo cada unidad de procesamiento de nodos para realizar una operación de procesamiento de nodos variables que incluye generar un valor de decisión;

un dispositivo (1520, 1620, 1720) de conmutación acoplado con el origen (1506, 1607, 1707) de mensajes y con el procesador vectorial (1508, 1608, 1708) de nodos, el dispositivo (1520, 1620, 1720) de conmutación para pasar conjuntos de Z mensajes de K bits, cada conjunto de Z mensajes de K bits pasado en paralelo, entre dicho origen (1506, 1607, 1707) de mensajes y dicho procesador vectorial (1506, 1608, 1708) de nodos, y para reordenar los mensajes en al menos uno de dichos conjuntos pasados de Z mensajes de K bits, en respuesta a información de control de conmutación;

un verificador vectorial (1514, 1614, 1714) de control de paridad, adaptado para examinar los valores de decisión generados, para determinar si ha sido satisfecha una condición de descodificación.

9. El aparato de la reivindicación 8, en el cual dicho origen (1506, 1607, 1707) de mensajes es un dispositivo de memoria.

10. El aparato de la reivindicación 8, que comprende adicionalmente:

un módulo (1504, 1604, 1704) de control de ordenamiento de mensajes, acoplado con dicho dispositivo (1520, 1620, 1720) de conmutación, para generar dicha información de control de conmutación, usada para controlar el reordenamiento de mensajes en dicho al menos un conjunto de Z mensajes de K bits.

11. El aparato de la reivindicación 10, en el cual el dispositivo (1520, 1620, 1720) de conmutación incluye circuitos para realizar una operación de rotación de mensajes para reordenar los mensajes incluidos en dicho al menos un conjunto de Z mensajes de K bits.

12. El aparato de la reivindicación 10, en el cual el módulo (1504, 1604, 1704) de control de ordenamiento de mensajes almacena información sobre el orden en el cual los conjuntos de Z mensajes de K bits han de ser recibidos desde dicho origen (1506, 1607, 1707) de mensajes, e información que indica qué reordenamiento de mensajes ha de ser realizado por dicho conmutador sobre conjuntos individuales de Z mensajes de K bits recibidos desde dicho origen (1506, 1607, 1707) de mensajes.

13. El aparato de la reivindicación 10, en el cual el módulo (1504, 1604, 1704) de control de ordenamiento de mensajes está adicionalmente acoplado con dicho origen (1506, 1607, 1707) de mensajes y genera secuencialmente identificadores de conjunto, controlando cada identificador de conjunto al origen (1506, 1607, 1707) de mensajes para emitir un conjunto de Z mensajes de K bits.