Un aparato (1500, 1600, 1700) para la realización de operaciones de decodificación de paso de mensajes usando gráficos LDPC convertidos a vectores que representan matrices de comprobación de paridad elevadas por lo que,

en una matriz de comprobación de paridad elevada los elementos cero de una matriz de comprobación de paridad H de un código LDPC proyectado se reemplazan con matrices de Z x Z ceros y los elementos 1 de la matriz de comprobación de paridad H se reemplazan con matrices de permutación de Z x Z comprendiendo el aparato: una memoria (1506) incluyendo un conjunto de localizaciones de memoria para almacenar L conjuntos de Z mensajes de K bits, donde Z es un número entero positivo mayor de uno y K y L son números enteros positivos distintos de cero; un procesador de vectores de nodos (1508) incluyendo Z unidades de procesamiento de nodos en paralelo, cada una de las unidades de procesamiento de nodos (1508) para realizar al menos una de las operaciones de procesamiento de nodos de restricciones y una operación de procesamiento de nodos de variables; y un dispositivo de conmutación (1520) acoplado a la memoria (1506) y al procesador de vectores de nodos (1508), el dispositivo de conmutación (1520) para pasar conjuntos de Z mensajes de K bits, pasado cada conjunto de Z mensajes de K bits en paralelo entre dicha memoria y dicho procesador de vectores de nodos y para reordenar los mensajes en al menos uno de dichos conjuntos de mensajes en respuesta a la información de control de conmutación, un módulo de ordenamiento de mensajes (1504) acoplado a dicho dispositivo 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 mensajes, en el que el módulo de reordenamiento de mansajes (1504) está además acoplado a dicha memoria y genera secuencialmente conjuntos de indicadores, controlando cada uno de los identificadores de conjunto la memoria para acceder a las localizaciones de memoria correspondientes a uno de dichos conjuntos de mensajes en una operación de lectura o escritura única por la que, uno de dichos conjuntos de Z mensajes de K bits se escribe o se lee como una unidad única accediendo a todos los Z mensajes de dicho conjunto usando una instrucción SIMD

Campo de la Invención

La presente invención se dirige a procedimientos y aparatos para la detección y/o corrección de errores en datos binarios, por ejemplo, a través del uso de códigos de comprobación de la paridad, tales como los códigos de comprobación de paridad de baja densidad (LDPC).

Antecedentes

En la era moderna de la información, se usan los valores binarios, es decir, unos y ceros, para representar y comunicar diversos tipos de información, por ejemplo, video, audio, información estadística, etc. Desafortunadamente, durante el almacenamiento, la transmisión y/o el procesamiento de los datos binarios, pueden introducirse errores no intencionados, por ejemplo un uno puede cambiar a cero o viceversa.

Generalmente, en el caso de la transmisión de datos, un receptor observa cada uno de los bits recibidos en presencia de ruido o distorsión y sólo se obtiene una indicación del valor de bit. Bajo estas circunstancias se interpretan los valores observados como una fuente de bits "software". Un bit software indica una estimación preferida del valor de bit, es decir, un uno o un cero, junto con alguna indicación de la fiabilidad de la estimación. Aunque el número de errores puede ser relativamente bajo, incluso un pequeño número de errores o un nivel de distorsión puede dar como resultado que los datos resulten inutilizables, en el caso de errores de transmisión, pueden necesitar la retransmisión de los datos.

Para proporcionar un mecanismo para la comprobación de errores y, en algunos casos, para corregir los errores, los datos binarios pueden codificarse para introducir cuidadosamente una redundancia diseñada. La codificación de una unidad de datos produce lo que comúnmente se denomina como una palabra de código. Debido a su redundancia, una palabra de código a menudo incluirá 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 que surgen de palabras de código transmitidas se reciben o se procesan, la información redundante incluida en la palabra de código como se observa en la señal puede usarse para identificar y/o corregir los errores en las mismas o eliminar distorsión de la señal recibida para recuperar la unidad de datos original. Tal comprobación y/o la corrección de errores pueden implementarse como parte del proceso de decodificación. En ausencia de errores, o en el caso de errores o distorsión corregibles, puede usarse la decodificación para recuperar a partir de los datos fuentes que se están procesando, la unidad de datos original que se codificó. En el caso de errores no recuperables, el proceso de decodificación puede producir una indicación de que los datos originales no pueden recuperarse totalmente. Tales indicaciones de fallo de la decodificación pueden usarse para iniciar la retransmisión de los datos.

Aunque la redundancia de los datos puede aumentar la fiabilidad de los datos a almacenar o transmitidos, se hace a coste de espacio de almacenamiento y/o el uso de un valioso ancho de banda de comunicaciones. Por consiguiente, es deseable añadir redundancia de un modo eficaz, maximizando la magnitud de la capacidad de corrección/detección de errores obtenida para una cantidad determinada de redundancia introducida en los datos.

Con el uso incrementado de las líneas de fibra óptica para las comunicaciones de datos y el aumento de la tasa a la cual pueden leerse los datos y almacenarse en dispositivos de almacenamiento de datos, por ejemplo en dispositivos de disco, cintas, etc., hay una necesidad en aumento no sólo de un uso eficaz de la capacidad de almacenamiento y de transmisión de datos sino también de la capacidad de codificar y decodificar datos a altas tasas de velocidad.

Aunque la eficacia de la codificación y las altas tasas de datos son importantes, para que un sistema de codificación y/o decodificación sea práctico de usar en un amplio intervalo de dispositivos, por ejemplo, dispositivos de consumo, es importante que los codificadores y/o decodificadores se puedan implementar a un coste razonable. Por consiguiente, la capacidad de implementar de forma eficaz los esquemas de codificación/decodificación utilizados para el propósito de la corrección y/o detección de errores en términos, por ejemplo, de coste del hardware, puede ser importante.

A lo largo de años se han usado diversos tipos de esquemas de codificación para los propósitos de corrección de errores. Una clase de códigos, generalmente denominados como "códigos turbo" se inventaron recientemente (1993). Los códigos turbo ofrecen beneficios significativos sobre las técnicas de codificación más antiguas tales como los códigos convolucionales y han encontrado numerosas aplicaciones.

En conjunción con el advenimiento de los códigos turbo, ha habido un interés en aumento en otra clase de códigos relacionados, aparentemente más simples, comúnmente denominados como códigos de comprobación de paridad de baja densidad (LDPC). Los códigos LDPC se inventaron realmente por Gallager hace unos 40 años (1961) pero sólo han pasado a primer plano recientemente. Los códigos turbo y los códigos LDPC son esquemas de codificación que se usan en el contexto de los llamados sistemas de codificación iterativos, esto es, se decodifican usando decodificadores iterativos. Recientemente, se ha mostrado que los códigos LDPC pueden proporcionar muy buen funcionamiento de detección y corrección de errores, superando o igualando el de los códigos turbo para largas palabras de código, por ejemplo tamaños de palabras de código que exceden aproximadamente 1000 bits, dada la selección adecuada de parámetros de codificación LDPC. Además, los códigos LDPC pueden decodificarse potencialmente a velocidades mucho más altas que los códigos turbo.

En muchos esquemas de codificación, las palabras de código más largas son a menudo más resistentes para los propósitos 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 este modo el uso de palabras de código largas puede ser beneficioso en términos de aumentar la capacidad de detectar y corregir errores. Esto es particularmente cierto para los códigos turbo y los códigos LDPC. De este modo, en muchas aplicaciones es deseable el uso de palabras de código largas, por ejemplo, palabras de código que exceden al millar de bits de longitud.

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

El análisis de la complejidad de los algoritmos de procesamiento de la señal usualmente se centra en las cuentas de las operaciones. Cuando se intenta explotar el paralelismo hardware en los sistemas de codificación iterativa, especialmente en el caso de los códigos LDPC, se presenta una complejidad significativa no desde el punto de vista de los requisitos de cálculo sino más bien de los requisitos de encaminamiento. La raíz de los problemas descansa en la construcción de los propios códigos.

Los códigos LDPC y los códigos turbo descansan en el intercalado de mensajes dentro de un proceso iterativo. Para realizar bien el código, el intercalado debe tener buenas propiedades de mezclado. Esto necesita la implementación de un proceso de intercalado complejo.

Los códigos LDPC se representan bien por gráficos bipartitos, a menudo llamados gráficos de Tanner, en los cuales un conjunto de nodos, los nodos de variables, corresponden a los bits de la palabra de código y el otro conjunto de nodos, los nodos de restricciones, a menudo llamados nodos de comprobación, corresponden al conjunto de restricciones de comprobación de paridad que define el código. Las aristas en el gráfico conectan los nodos de variables a los nodos de restricciones. Un nodo de variable y un nodo de restricción se dice que son vecinos si están conectados por una arista en el gráfico. Por simplicidad, generalmente asumimos que un par de nodos se conectan a lo sumo por una arista. A cada uno de los nodos de variable está asociado un bit de la palabra de código.... [Seguir leyendo]

1. Un aparato (1500, 1600, 1700) para la realización de operaciones de decodificación de paso de mensajes usando gráficos LDPC convertidos a vectores que representan matrices de comprobación de paridad elevadas por lo que, en una matriz de comprobación de paridad elevada los elementos cero de una matriz de comprobación de paridad H de un código LDPC proyectado se reemplazan con matrices de Z x Z ceros y los elementos 1 de la matriz de comprobación de paridad H se reemplazan con matrices de permutación de Z x Z comprendiendo el aparato:

una memoria (1506) incluyendo un conjunto de localizaciones de memoria para almacenar L conjuntos de Z mensajes de K bits, donde Z es un número entero positivo mayor de uno y K y L son números enteros positivos distintos de cero; un procesador de vectores de nodos (1508) incluyendo Z unidades de procesamiento de nodos en paralelo, cada una de las unidades de procesamiento de nodos (1508) para realizar al menos una de las operaciones de procesamiento de nodos de restricciones y una operación de procesamiento de nodos de variables; y un dispositivo de conmutación (1520) acoplado a la memoria (1506) y al procesador de vectores de nodos (1508), el dispositivo de conmutación (1520) para pasar conjuntos de Z mensajes de K bits, pasado cada conjunto de Z mensajes de K bits en paralelo entre dicha memoria y dicho procesador de vectores de nodos y para reordenar los mensajes en al menos uno de dichos conjuntos de mensajes en respuesta a la información de control de conmutación, un módulo de ordenamiento de mensajes (1504) acoplado a dicho dispositivo 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 mensajes, en el que el módulo de reordenamiento de mansajes (1504) está además acoplado a dicha memoria y genera secuencialmente conjuntos de indicadores, controlando cada uno de los identificadores de conjunto la memoria para acceder a las localizaciones de memoria correspondientes a uno de dichos conjuntos de mensajes en una operación de lectura o escritura única por la que, uno de dichos conjuntos de Z mensajes de K bits se escribe o se lee como una unidad única accediendo a todos los Z mensajes de dicho conjunto usando una instrucción SIMD.

2. El aparato (1500) de la reivindicación 1, en el que el dispositivo de conmutación (1520) incluye circuitería para realizar una operación de rotación de mensajes para reordenar los mensajes incluidos en un conjunto de mensajes.

3. El aparato (1500) de la reivindicación 1, en el que el módulo de reordenamiento de mensajes (1504) almacena información sobre el orden de los conjuntos de los mensajes a leer de la memoria y la información que indica qué reordenamiento de mensajes se realizará por dicho conmutador sobre los conjuntos individuales de mensajes leídos de la memoria.

4. El aparato (1500) de la reivindicación 1, en el que dicho identificador de conjunto es una simple dirección de memoria.

5. El aparato (1500) de la reivindicación 1, en el que dicha pluralidad de unidades de procesamiento de nodos incluye Z unidades de procesamiento de nodos dispuestas en paralelo, funcionando cada una de las Z unidades de procesamiento de nodos en paralelo para procesar un mensaje diferente en cada uno de los conjuntos de Z mensajes pasados entre dicha memoria y dicho procesador de nodos.

6. El aparato (1500) de la reivindicación 5, en el que dicha memoria (1506) incluye una entrada de dirección que permite dirigirse a cada uno de los conjuntos de mensajes como una unidad posibilitando por lo tanto la lectura de un conjunto de mensajes desde dicha memoria en una única operación de lectura de SMID.

7. El aparato de la reivindicación 5, en el que dicha memoria (1506) incluye una entrada de dirección que permite dirigirse a cada uno de los conjuntos de mensajes como dicha unidad posibilitando por lo tanto que un conjunto de mensajes se escriban dentro de dicha memoria en una única operación de escritura de SMID.

8. El aparato (1500) de la reivindicación 5,

en el que el dispositivo de control del decodificador está además acoplado a un dispositivo de control del paso de mensajes; y en el que el dispositivo de control del paso de mensajes especifica un orden diferente en el que se leerán cada uno de los L conjuntos de Z mensajes de la memoria durante el modo de nodos de variables de la operación de procesamiento que durante el modo de nodos de restricciones de la operación de procesamiento.

9. El aparato (1500) de la reivindicación 1, que comprende además un módulo de control del decodificador (1502) acoplado al módulo de ordenamiento de mensajes (1504), incluyendo el módulo de control del decodificador medios para el suministro de información al módulo de ordenamiento de mensajes utilizado para controlar el orden en el que se leerá cada uno de los L conjuntos de Z mensajes de dicha memoria.

10. El aparato (1500) de la reivindicación 9, en el que el módulo de control del decodificador (1502) incluye además

medios para el suministro de un índice de aristas al módulo de ordenamiento de mensajes (1504) que controla la generación de los identificadores de conjuntos suministrados a dicha memoria.

11. El aparato (1500) de la reivindicación 10, que comprende además una memoria de grados (1510) acoplada con el procesador de vectores de nodos (1508) para el almacenamiento de un conjunto de información del grado de los nodos.

12. El aparato (1500) de la reivindicación 11, en el que el módulo de control (1502) genera además un índice de nodos usado para determinar qué información del grado de los nodos en el conjunto almacenado de la información del grado de los nodos se aplicará al procesador de vectores de nodos en cualquier momento determinado.

13. El aparato (1600) de la reivindicación 1, que comprende además:

un segundo procesador de vectores de nodos (1609, 1608) acoplado a dicha memoria, incluyendo el segundo procesador de vectores de nodos unidades de procesamiento de nodos, cada una de las unidades de procesamiento de nodos para realizar una operación de procesamiento de nodos de restricciones, en el que dicho procesador de vectores de nodos es un procesador de nodos de variables para la realización de las operaciones de procesamiento de comprobación de paridad del decodificador de nodos de variables; en el que dicho segundo procesador de nodos es un procesador de nodos de restricciones (1609) para la realización de las operaciones de procesamiento del decodificador de comprobación de la paridad de nodos de restricciones.

14. El aparato (1600) de la reivindicación 13, que comprende además:

la memoria adicional (1607, 1606) que acopla dicho procesador de vectores de nodos a dicho segundo procesador de vectores de nodos, incluyendo la memoria adicional un conjunto de localizaciones de memoria para el almacenamiento de L conjuntos de Z mensajes de K bits.

15. El aparato (1600) de la reivindicación 14, que comprende además:

un segundo dispositivo de conmutación (1620, 1621) que acopla dicho procesador de vectores de nodos a dicha memoria adicional, un segundo dispositivo de conmutación para pasar conjuntos de Z mensajes de K bits entre dicho procesador de vectores de nodos y dicha memoria adicional y para reordenar los mensajes en al menos uno de los conjuntos de mensajes pasado por el segundo conmutador.

16. El aparato (1600) de la reivindicación 13, que comprende además:

un verificador de comprobación de paridad (1614), acoplado a dicho procesador de vectores de nodos, para determinar a partir de una salida de cada una de las unidades de procesamiento incluidas en el mismo, cuándo se ha completado satisfactoriamente la operación de decodificación de comprobación de paridad.

17. Un procedimiento para la realización del procesamiento de decodificación del paso de mensajes para la decodificación de gráficos de LDPC convertidos a vectores que representan matrices de comprobación de paridad elevadas por lo que en una matriz de comprobación de paridad elevada, los elementos cero de una matriz de comprobación de paridad H de un código LDPC proyectado se reemplazan con matrices de Z x Z ceros y los elementos 1 de la matriz de comprobación de paridad H se reemplazan con matrices de permutación de Z x Z que comprenden las etapas de:

almacenar L conjuntos de mensajes de K bits en una memoria (1506), incluyendo cada uno de los conjuntos de mensajes de K bits en primer lugar Z mensajes, donde Z es un número entero positivo mayor que uno y K y L son números enteros positivos distintos de cero; leer uno de dichos conjuntos de mensajes de K bits de la memoria (1506); realizar una operación de reordenamiento de mensajes en dicho conjunto de mensajes de K bits leídos para producir un conjunto reordenado de Z mensajes de K bits; suministrar, en paralelo, los Z mensajes en el conjunto reordenado de mensajes a un procesador de vectores de nodos (1508); y que opera el procesador de vectores de nodos (1508) para realizar las operaciones del decodificador de paso de mensajes usando Z mensajes suministrados como entrada, incluyendo dicho procesador de vectores de nodos (1508) Z unidades de procesamiento en paralelo, por lo que cada una de las unidades de procesamiento de nodos realiza al menos una operación de procesamiento de nodos de restricciones y una operación de procesamiento de nodos de variables, comprendiendo el procedimiento además:

generar un identificador de conjunto indicando el conjunto de Z mensajes a leer de la memoria (1506), en el que la etapa de leer uno de dichos conjuntos de mensajes de K bits incluye:

realizar una única operación de lectura usando dicho identificador de conjunto para acceder con dicha operación de lectura única a todos los Z mensajes de K bits de dicho conjunto como una única unidad usando una instrucción SMID.

18. El procedimiento de la reivindicación 17, en el que dichas operaciones del decodificador de paso de mensaje generan un conjunto de Z mensajes de decodificador a partir de los Z mensajes en el conjunto de mensajes reordenados suministrado.

19. El procedimiento de la reivindicación 17, que comprende además:

realizar una segunda operación de reordenamiento de mensajes, realizándose la segunda operación de reordenamiento de mensajes sobre el conjunto generado de Z mensajes del decodificador para producir un conjunto reordenado de mensajes del decodificador generados.

20. El procedimiento de la reivindicación 19, que comprende además:

almacenar el conjunto reordenado de mensajes del decodificador generados en dicha memoria.

21. El procedimiento de la reivindicación 20, en el que la etapa de almacenar el conjunto reordenado de mensajes del decodificador generados incluye realizar una operación de escritura SMID para escribir dicho conjunto reordenado de mensajes del decodificador generados en la memoria.

22. El procedimiento de la reivindicación 19, en el que la etapa de realizar una segunda operación de reordenamiento de mensajes incluye realizar la inversa de la operación de reordenamiento de mensajes realizado sobre dicho conjunto de mensajes de K bits leídos desde la memoria.

23. El procedimiento de la reivindicación 17, que comprende además:

acceder a la información de permutación del conjunto de mensajes almacenados; y en el que la etapa de realización de una operación de reordenamiento de mensajes incluye la etapa de: realizar dicho reordenamiento como una función de la información de permutación del conjunto de mensajes almacenados accedidos.

24. El procedimiento de la reivindicación 22, en el que dicha información de permutación del conjunto de mensajes incluye información de rotación cíclica.

25. El procedimiento de la reivindicación 17, en el que dichas operaciones del decodificador de paso de mensajes son operaciones de procesamiento de nodos de variables, incluyendo cada una de las operaciones de procesamiento de nodos de variables un valor de decisión, y en el que el procedimiento comprende además:

examinar los valores de decisión generados operando el procesador de vectores para determinar si se ha satisfecho una condición de decodificación.

26. Un procedimiento de realización del procesamiento de decodificador de paso de mensajes para decodificar los gráficos LDPC convertidos a vectores que representan las matrices de comprobación de paridad elevadas por lo que en una matriz de comprobación de paridad elevada, los elementos cero de una matriz de comprobación de paridad H de un código LDPC proyectado se reemplazan con matrices de Z x Z ceros y los elementos 1 de la matriz de comprobación de paridad H se reemplazan con matrices de permutación de Z x Z, comprendiendo el procedimiento las etapas de:

operar un procesador de vectores de nodos (1508) para generar un conjunto de Z mensajes de K bits, a almacenar en un dispositivo de memoria (1506) para almacenar L conjuntos de Z mensajes de K bits, donde Z es un número entero positivo mayor de uno y K y L son números enteros positivos distintos de cero, incluyendo dicho procesador de vectores de nodos (1508) Z unidades de procesamiento en paralelo, por lo que cada una de las unidades de procesamiento de nodos realiza al menos una de las operaciones de procesamiento de nodos de restricciones y una operación de procesamiento de nodos de variables; realizar una operación de reordenamiento de mensajes en el conjunto generado de Z mensajes de K bits para producir un conjunto reordenado de Z mensajes de K bits; realizar una única operación de escritura para almacenar el conjunto reordenado de Z mensajes de K bits en dicho dispositivo de memoria (1506), en el que la etapa de realizar una operación de escritura única para almacenar el conjunto de Z mensajes de K bits reordenados comprende realizar una única operación de escritura usando un identificador de conjunto para escribir con dicha única operación de escritura todos los Z mensajes de K bits de dicho conjunto reordenado como una única usando una instrucción SIMD.

27. El procedimiento de la reivindicación 26, en el que la etapa de operar el procesador de vectores de nodos para generar un conjunto de Z mensajes de K bits, incluye la etapa de:

realizar, en paralelo, las Z operaciones de procesamiento de nodos, generando cada una de las operaciones de procesamiento de nodos un mensaje en dicho conjunto de Z mensajes de K bits.

28. El procedimiento de la reivindicación 26, en el que las Z operaciones de procesamiento de nodos son operaciones de procesamiento de nodos de variables.

29. El procedimiento de la reivindicación 28, en el que las Z operaciones de procesamiento de nodos son operaciones de procesamiento de nodos de restricciones.

5 30. El procedimiento de la reivindicación 28, en el que realizar una operación de reordenamiento de mensajes en el conjunto generado de Z mensajes de K bits incluye:

girar los mensajes en el conjunto de Z mensajes de K bits realizando una operación de conmutación para reordenar los mensajes en el conjunto de mensajes.