PROCESADORES DE NODO PARA SU USO EN DECODIFICADORES DE CONTROL DE PARIDAD.

Un sistema de detección y/o corrección de errores, comprendiendo el sistema:

medios (1500) para generar valores de verosimilitud logarítmica cuantificados a múltiplos enteros de 1/2 ln 2 para producir valores y0 de verosimilitud logarítmica cuantificados a partir de los valores recibidos; un decodificador (358, 600) de paso de mensajes, acoplado a dichos medios para generar valores de verosimilitud logarítmica, para realizar operaciones de decodificación de paso de mensajes usando dichos valores y0 de verosimilitud logarítmica cuantificados como valores de entrada; en el que dicho decodificador (358, 600) de paso de mensajes incluye un dispositivo (1300) para realizar operaciones de procesamiento de nodo que comprende un módulo (1302) acumulador para procesar, en secuencia, mensajes m de entrada correspondientes a una pluralidad de nodos, representando cada mensaje m de entrada un valor de verosimilitud logarítmica cuantificado a múltiplos enteros de 1/2 In 2, recibiéndose un conjunto de mensajes de entrada por nodo, siendo el número de mensajes en un conjunto de mensajes correspondientes a un nodo igual al grado d de dicho nodo, donde d es un entero positivo distinto de cero, y para generar una suma de mensajes total a partir de un conjunto de mensajes m de entrada recibidos secuencialmente correspondientes a un nodo, generándose una suma de nodo total para cada conjunto recibido de mensajes de entrada, teniendo el módulo (1302) acumulador un elemento (1312) de retardo para almacenar una suma continua y un multiplexor (1314), MUX, adaptado para emitir la suma continua, o un cero cuando un primer mensaje en el conjunto de mensajes m de entrada correspondientes al nodo se suministra al módulo acumulador una línea de retardo de mensajes que incluye una unidad (1306) de retardo controlable para almacenar cada uno de los mensajes m de entrada recibidos secuencialmente durante un período de tiempo directamente proporcional al grado d del nodo al que corresponde cada mensaje almacenado; y un módulo (1304) de generación de mensajes para generar mensajes de salida correspondientes a un nodo a partir de la suma total correspondiente al nodo y los mensajes retardados correspondientes a dicho nodo, generando el módulo (1304) de generación de mensajes un mensaje de salida para cada mensaje de entrada recibido correspondiente al nodo

Solicitudes relacionadas

La presente solicitud reivindica el beneficio de la solicitud provisional estadounidense n.º de serie 60/328,469 presentada el 10 de octubre de 2001, y el beneficio de la solicitud provisional estadounidense n.º de serie 60/298,480 presentada el 15 de junio de 2001, y es una continuación en parte de la solicitud de patente 5 estadounidense n.º de serie 09/975,331 presentada el 10 de octubre de 2001.

Campo de la invención

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

Antecedentes

Los códigos de corrección de errores están presentes de manera generalizada en sistemas de comunicaciones y almacenamiento de datos. Recientemente se ha suscitado un considerable interés en una clase de códigos conocidos como códigos de control de paridad de baja densidad (LDPC).

Los códigos LDPC se representan adecuadamente mediante grafos bipartitos, a menudo llamados grafos 15 de Tanner, en los que un conjunto de nodos, los nodos variables, corresponden a bits de la palabra de código y el otro conjunto de nodos, los nodos de restricción, a veces llamados nodos de control, corresponden al conjunto de restricciones de control de paridad que definen el código. Las aristas del grafo conectan nodos variables con nodos de restricción. Un nodo variable y un nodo de restricción se dice que son vecinos si están conectados por una arista en el grafo. Para simplificar, en general asumimos que un par de nodos están conectados como mucho por una 20 arista. A cada nodo variable está asociado un bit de la palabra de código. En algunos casos, algunos de estos bits podrían perforarse, es decir, eliminarse de la palabra de código. Para simplificar, asumiremos de manera general que no se usa ninguna perforación.

Una secuencia de bits asociada en relación de uno a uno con la secuencia de nodos variables es una palabra de código del código si, y solo si, por cada nodo de restricción, los bits vecinos de la restricción (a través de 25 su asociación con nodos variables) suman cero módulo dos, es decir, comprenden un número par de unos. Los decodificadores y algoritmos de decodificación usados para decodificar palabras de código LDPC funcionan intercambiando mensajes dentro del grafo a lo largo de las aristas y actualizando estos mensajes realizando cálculos en los nodos basándose en los mensajes entrantes. Tales algoritmos se denominarán generalmente algoritmos de paso de mensajes. A cada nodo variable en el grafo se le proporciona inicialmente un bit suave (soft bit), 30 denominado valor recibido, que indica una estimación del valor del bit asociado según se determina mediante observaciones a partir de, por ejemplo, el canal de comunicaciones. Idealmente, las estimaciones para bits separados son estadísticamente independientes. Este ideal puede ser, y a menudo es, infringido en la práctica. Una colección de valores recibidos constituye una palabra recibida. Para los fines de esta solicitud, podemos identificar la señal observada por, por ejemplo, el receptor en un sistema de comunicaciones, con la palabra recibida. 35

El número de aristas unidas a un nodo, es decir, a un nodo variable o a un nodo de restricción, se denomina grado del nodo. Un grafo o código regular es uno en el cual todos los nodos variables tienen el mismo grado, digamos j, y todos los nodos de restricción tienen el mismo grado, digamos k. En este caso se dice que el código es un código regular (j, k). Estos códigos fueron inventados originalmente por Gallager (1961). A diferencia de un código “regular”, un código irregular tiene nodos de restricción y/o nodos variables de diferentes grados. Por 40 ejemplo, algunos nodos variables pueden ser de grado 4, otros de grado 3 y otros más de grado 2.

Aunque los códigos irregulares pueden ser más complicados de representar y/o implementar, se ha demostrado que los códigos LDPC irregulares pueden proporcionar un rendimiento superior en la corrección/detección de errores en comparación con los códigos LDPC regulares.

Con el fin de describir de manera más precisa el proceso de decodificación, presentamos el concepto de 45 zócalo en la descripción de grafos LDPC. Un zócalo puede interpretarse como una asociación de una arista en el grafo con un nodo en el grafo. Cada nodo tiene un zócalo para cada arista unida al mismo y las aristas se “insertan en” los zócalos. De esta manera, un nodo de grado d tiene d zócalos unidos al mismo. Si el grafo tiene L aristas entonces hay L zócalos en el lado de nodo variable del grafo, llamados zócalos variables, y L zócalos en el lado de nodo de restricción del grafo, llamados zócalos de restricción. Con fines de identificación y ordenación, los zócalos 50 variables pueden enumerarse 1,…, L de manera que los zócalos variables unidos a un nodo variable aparezcan de manera contigua. En tal caso, si los primeros tres nodos variables tienen grados d1, d2 y d3 respectivamente, entonces los zócalos variables 1,…, d1 están unidos al primer nodo variable, los zócalos variables d1+1,..., d1+d2 están unidos al segundo nodo variable, y los zócalos variables d1+d2+1,…, d1+d2+d3 están unidos al tercer nodo variable. Los zócalos de nodo de restricción pueden enumerarse de manera similar 1,…, L, apareciendo los zócalos 55 de restricción unidos a un nodo de restricción de manera contigua. Una arista puede verse como un emparejamiento de zócalos, procediendo uno de cada par de cada lado del grafo. De esta manera, las aristas del grafo representan un entrelazado o permutación en los zócalos de un lado del grafo, por ejemplo, el lado de nodo variable, al otro, por

ejemplo, el lado de nodo de restricción. Las permutaciones asociadas con estos sistemas son a menudo complejas.

Un grafo 100 bipartito ejemplar que determina un código LDPC regular (3,6) de longitud diez y proporción 1/2 se muestra en la figura 1. Longitud diez indica que hay diez nodos variables V1-V10, cada uno identificado con un bit de la palabra de código X1- X10 (y sin perforación en este caso), generalmente identificados por el número de referencia 102. Proporción 1/2 indica que hay la mitad de nodos de control que de nodos variables, es decir, hay 5 cinco nodos de control C1-C5 identificados por el número de referencia 106. Proporción 1/2 además indica que las cinco restricciones son linealmente independientes, como se comenta más adelante. Cada una de las líneas 104 representa una arista, por ejemplo, un camino de comunicación o conexión, entre los nodos de control y los nodos variables a los que está conectada la línea. Cada arista identifica dos zócalos, un zócalo variable y un zócalo de restricción. Las aristas pueden enumerarse según sus zócalos variables o sus zócalos de restricción. La 10 enumeración de los zócalos variables corresponde a la ordenación de aristas (de arriba hacia abajo) tal como aparece en el lado de nodo variable en el punto en el que se conectan a los nodos variables. La enumeración de los zócalos de restricción corresponde a la ordenación de aristas (de arriba hacia abajo) tal como aparece en el lado de nodo de restricción en el punto en el que se conectan a los nodos de restricción. Durante la decodificación, se pasan mensajes en ambos sentidos a lo largo de las aristas. De esta manera, como parte del proceso de decodificación se 15 pasan mensajes a lo lardo de una arista desde un nodo de restricción hacia un nodo variable y viceversa.

Una alternativa al uso de un grafo para representar códigos es usar una representación matricial tal como se muestra en la figura 2. En la representación matricial de un código, la matriz H 202, comúnmente denominada matriz de control de paridad, incluye la información relevante de conexión de aristas, nodos variables y nodos de restricción. Para simplificar asumimos que una arista conecta como mucho un par de nodos cualquiera. En la matriz 20 H, cada columna corresponde a uno de los nodos variables mientras que cada fila corresponde a uno de los nodos de restricción. Puesto que hay 10 nodos variables y 5 nodos de restricción en el código ejemplar, la matriz H incluye 10 columnas y 5 filas. La entrada de la matriz correspondiente a un nodo variable particular y a un nodo de restricción particular se ajusta a 1 si hay una arista presente en el grafo, es decir, si los dos nodos son vecinos, de lo contrario se ajusta a 0. Por ejemplo,... [Seguir leyendo]

1. Un sistema de detección y/o corrección de errores, comprendiendo el sistema:

medios (1500) para generar valores de verosimilitud logarítmica cuantificados a múltiplos enteros de 1/2 ln 2 para producir valores y0 de verosimilitud logarítmica cuantificados a partir de los valores recibidos;

un decodificador (358, 600) de paso de mensajes, acoplado a dichos medios para generar valores de 5 verosimilitud logarítmica, para realizar operaciones de decodificación de paso de mensajes usando dichos valores y0 de verosimilitud logarítmica cuantificados como valores de entrada;

en el que dicho decodificador (358, 600) de paso de mensajes incluye un dispositivo (1300) para realizar operaciones de procesamiento de nodo que comprende

un módulo (1302) acumulador para procesar, en secuencia, mensajes m de entrada correspondientes 10 a una pluralidad de nodos, representando cada mensaje m de entrada un valor de verosimilitud logarítmica cuantificado a múltiplos enteros de 1/2 In 2, recibiéndose un conjunto de mensajes de entrada por nodo, siendo el número de mensajes en un conjunto de mensajes correspondientes a un nodo igual al grado d de dicho nodo, donde d es un entero positivo distinto de cero, y para generar una suma de mensajes total a partir de un conjunto de mensajes m de entrada recibidos secuencialmente 15 correspondientes a un nodo, generándose una suma de nodo total para cada conjunto recibido de mensajes de entrada, teniendo el módulo (1302) acumulador un elemento (1312) de retardo para almacenar una suma continua y un multiplexor (1314), MUX, adaptado para emitir la suma continua, o un cero cuando un primer mensaje en el conjunto de mensajes m de entrada correspondientes al nodo se suministra al módulo acumulador 20

una línea de retardo de mensajes que incluye una unidad (1306) de retardo controlable para almacenar cada uno de los mensajes m de entrada recibidos secuencialmente durante un período de tiempo directamente proporcional al grado d del nodo al que corresponde cada mensaje almacenado; y

un módulo (1304) de generación de mensajes para generar mensajes de salida correspondientes a un nodo a partir de la suma total correspondiente al nodo y los mensajes retardados correspondientes a 25 dicho nodo, generando el módulo (1304) de generación de mensajes un mensaje de salida para cada mensaje de entrada recibido correspondiente al nodo.

2. El sistema según la reivindicación 1, en el que el módulo (1304) de generación de mensajes incluye:

un circuito (1320) de resta acoplado a dicho módulo (1302) acumulador y a la unidad de retardo controlable para restar cada valor de mensaje retardado correspondiente al nodo a la suma total 30 correspondiente a dicho nodo.

3. El sistema según la reivindicación 2, en el que dicha unidad (1306) de retardo controlable incluye una entrada para recibir una señal de grado de nodo que indica el grado del nodo correspondiente a los mensajes recibidos por dicha unidad de retardo controlable.

4. El sistema según la reivindicación 3, en el que dicha unidad de retardo controlable se implementa como un 35 dispositivo de almacenamiento de datos de tipo primero en entrar primero en salir.

5. El sistema según la reivindicación 2, en el que dicho módulo (1302) acumulador incluye:

un sumador (1310) que tiene una primera entrada para recibir mensajes m de entrada

un dispositivo (1316) de almacenamiento para almacenar la suma de nodo total generada; y

mediante el cual el elemento (1312) de retardo para almacenar la suma continua generada por dicho 40 sumador (1310) y para emitir dicha suma continua almacenada está acoplado entre dicho sumador (1310) y dicho dispositivo (1316) de almacenamiento.

6. El sistema según la reivindicación 5, en el que dicho (1302) multiplexor (1314), acoplado a dicho elemento (1312) de retardo para recibir desde dicho elemento (1312) de retardo la suma continua almacenada y para emitir uno de la suma continua almacenada y un cero a una segunda entrada de dicho sumador (1310) bajo 45 el control de una señal de reloj de nodo; y

en el que dicho dispositivo (1316) de almacenamiento además incluye una entrada de control para recibir dicha señal de reloj de nodo, almacenando dicho dispositivo (1316) de almacenamiento la suma continua almacenada que va a usarse como la suma de nodo total bajo la dirección de dicha señal de reloj de nodo.

7. El sistema según la reivindicación 6, que comprende además: 50

medios para activar la señal de reloj de nodo para hacer que el multiplexor emita un cero cuando un primer mensaje correspondiente a un nodo se recibe por dicho sumador (1310).

8. El sistema según la reivindicación 7, en el que la señal de reloj de nodo hace que dicho dispositivo (1316) de almacenamiento almacene la suma continua como la suma de nodo total al mismo tiempo que hace que el multiplexor (1314) emita un cero.

9. El sistema según la reivindicación 1, en el que la unidad (1306) de retardo controlable incluye una pluralidad de ubicaciones de almacenamiento de mensajes, siendo el número de ubicaciones de almacenamiento de 5 mensajes en dicha pluralidad de ubicaciones de almacenamiento de mensajes al menos tan grande como el grado más alto de un nodo para el que dicho dispositivo va a realizar operaciones de procesamiento.

10. Un procedimiento de detección y/o corrección de errores, comprendiendo el procedimiento las etapas de:

generar valores de verosimilitud logarítmica cuantificados a múltiplos enteros de 1/2 ln 2 para producir valores y0 de verosimilitud logarítmica cuantificados a partir de valores recibidos; 10

realizar una operación de procesamiento del decodificador de paso de mensajes usando dichos valores y0 de verosimilitud logarítmica cuantificados como valores de entrada;

en el que dicha operación de procesamiento de decodificación de paso de mensajes incluye operaciones de procesamiento de nodo que comprenden las etapas de:

recibir secuencialmente mensajes m de entrada que van a procesarse correspondientes a una 15 pluralidad de nodos, representando cada mensaje m de entrada un valor de verosimilitud logarítmica cuantificado a múltiplos enteros de 1/2 ln 2, recibiéndose un conjunto de mensajes de entrada por nodo, siendo el número de mensajes en un conjunto de mensajes correspondientes a un nodo igual al grado d de dicho nodo, donde d es un entero positivo distinto de cero, y generar una suma de mensajes total a partir de un conjunto de mensajes m 20 de entrada recibidos secuencialmente correspondientes a un nodo, generándose una suma de nodo total para cada conjunto recibido de mensajes de entrada, almacenar una suma continua y multiplexar la suma continua con un cero cuando se recibe un primer mensaje en el conjunto de mensajes m de entrada correspondientes al nodo

retardar, usando una unidad de retardo controlable, cada mensaje m de entrada recibido 25 individual durante un periodo de tiempo directamente proporcional al grado d del nodo al que corresponde dicho mensaje de entrada recibido individual; y

generar mensajes de salida correspondientes a un nodo a partir de la suma total correspondiente al nodo y los mensajes retardados correspondientes a dicho nodo, mediante el cual se genera un mensaje de salida para cada mensaje de entrada recibido correspondiente al 30 nodo.

11. El procedimiento según la reivindicación 10, en el que dicha etapa de retardar cada mensaje m de entrada recibido individual incluye la etapa de:

recibir una señal de control que indica el grado del nodo al que corresponde un mensaje recibido para su procesamiento. 35

12. El procedimiento según la reivindicación 11, que comprende además la etapa de:

sumar cada mensaje m de entrada recibido a la suma continua de mensajes recibidos para generar dicha suma de mensajes total para cada conjunto de mensajes de entrada recibidos.

13. El procedimiento según la reivindicación 12, que comprende además la etapa de:

enclavar la suma continua en un dispositivo (1316) de almacenamiento, una vez que el último mensaje 40 en un conjunto de mensajes de entrada recibidos se ha añadido a la suma continua, siendo la suma continua enclavada la suma de mensajes total.

14. El procedimiento según la reivindicación 13, que comprende además:

sumar un valor de entrada recibido a dicha suma continua antes de enclavar la suma continua en el dispositivo (1316) de almacenamiento. 45

15. El procedimiento según la reivindicación 13, que comprende además la etapa de inicializar la suma continua a cero cada vez que se recibe un mensaje correspondiente a un nodo diferente que el mensaje recibido inmediatamente precedente.

16. El procedimiento según la reivindicación 13, en el que dicho enclavamiento e inicialización se controlan mediante la misma señal de control. 50

17. El procedimiento según la reivindicación 12, que comprende además la etapa de emitir los mensajes de salida generados en secuencia, uno cada vez.

18. El procedimiento según la reivindicación 10, en el que cada mensaje de entrada recibido incluye un bit de signo y un valor de magnitud que, en combinación, comprende dicho valor cuantificado.