Códigos de comprobación de paridad de baja densidad ( LDPC) de tasa compatible con H-ARQ para aplicaciones de alto rendimiento.

Un procedimiento para generar códigos de tasa compatible LDPC basados en protografos de tasa alta a partirde códigos de tasa baja para codificar datos para su transmisión a través de un canal de comunicaciones:

en el que dichos códigos de tasa baja son códigos padres, comprendiendo el procedimiento:generar dichos códigos padre mediante:

copiar un grafo base;

permutar puntos de extremo de aristas de un mismo tipo en copias de dicho grafo base paraproducir un grafo permutado; y

podar nodos de entrada sistemáticos (20) en dicho grafo permutado y dichas aristasconectadas a los mismos;

perforar un subconjunto de bits de palabra de código (30), comprendiendo:

perforar de manera progresiva nodos variables (20) para obtener un código deseado a partirde un código anterior en una familia de tasa compatible del código padre respectivo;

donde dicha etapa de perforar de manera progresiva nodos variables (20) para obtener uncódigo deseado a partir de un código anterior comprende:

perforar de manera progresiva dichos nodos variables (20) de un conjunto de nodosvariables redundantes no perforados (20) de cardinalidad rm-1, donde rm-1 es el númerode elementos del conjunto de nodos variables redundantes no perforados (20) delcódigo anterior y donde los nodos variables redundantes no perforados (20) del códigoanterior pueden perforarse para proporcionar el código de una tasa deseada;

donde dicha etapa de perforar de manera progresiva nodos variables (20) del conjuntode nodos variables redundantes no perforados (20) comprende una etapa deinicialización que comprende:

calcular para cada nodo de comprobación (25) conectado a al menos un nodovariable redundante (20) el número de nodos variables perforados (20)conectados a dicho nodo de comprobación (25);

hallar dicho conjunto de nodos variables redundantes no perforados (20);calcular para cada nodo variable redundante no perforado (20) el número detales nodos de comprobación (25) conectados al nodo variable redundante noperforado (20) que están conectados solamente a un nodo variable perforado(20); y

calcular para cada nodo variable redundante no perforado (20) la suma de nodosvariables perforados (20) conectados a tales nodos de comprobación (25) queestán conectados a dicho nodo variable redundante no perforado (20).

Códigos de comprobación de paridad de baja densidad (LDPC) de tasa compatible con H-ARQ para aplicaciones de alto rendimiento

ANTECEDENTES

Campo

La presente invención se refiere en general a las comunicaciones y, en particular, a codificación de tasa compatible con solicitudes automáticas híbridas (H-ARQ) para aplicaciones de alto rendimiento.

Antecedentes

En general, en el caso de transmisión de datos, un receptor observa cada bit recibido en presencia de ruido o distorsión, obteniéndose solamente una indicación del valor del bit. En estas circunstancias, los valores observados se interpretan como una fuente de bits de "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. Aunque el número de errores puede ser relativamente bajo, un pequeño número de errores o nivel de distorsión puede dar como resultado que los datos sean inservibles o, en el caso de errores de transmisión, puede ser necesario retransmitir los datos.

Con el fin de proporcionar un medio para comprobar los errores y, en algunos casos, corregir los errores, pueden codificarse datos binarios para introducir una redundancia cuidadosamente diseñada. La codificación de una unidad de datos produce lo que se denomina comúnmente palabra de código. Debido a su redundancia, una palabra de código incluye normalmente más bits que la unidad de entrada de datos a partir de la cual se generó la palabra de código.

Cuando se reciben o se procesan señales que surgen a partir de palabras de código transmitidas, la información redundante incluida en la palabra de código observada en la señal puede utilizarse para identificar y/o corregir errores en o eliminar distorsión de la señal recibida con el fin de recuperar la unidad de datos original. Tal comprobación y/o corrección de errores pueden implementarse como parte de un proceso de decodificación. En ausencia de errores, o en el caso de errores o una distorsión que pueden corregirse, la decodificación puede utilizarse para recuperar a partir de los datos fuente que se están procesando la unidad de datos original que se codificó. En el caso de errores que no pueden recuperarse, el proceso de decodificación puede producir alguna indicación de que los datos originales no pueden recuperarse completamente. Estas indicaciones de fallos de decodificación pueden utilizarse para iniciar retransmisiones de los datos.

Los sistemas de comunicaciones necesitan funcionar normalmente a varias tasas diferentes. Una manera de hacer que la implementación sea lo más sencilla posible y proporcionar la codificación y decodificación a las diferentes tasas es utilizar códigos de comprobación de paridad de baja densidad (LDPC) . En particular, los códigos LDPC se utilizan para generar códigos de mayor tasa perforando códigos de menor tasa. Con los sistemas de comunicaciones que utilizan adaptación de tasa puede ser necesario ajustar la tasa de transmisión de datos según las condiciones y necesidades del sistema. La adaptación de tasa permite que un sistema de comunicaciones, y sus componentes, adapten de manera flexible y eficaz la tasa de transmisión de datos a las condiciones de canal actuales. Por ejemplo, los diseños habituales de corrección de errores seleccionan un código fijo, presentando el código una determinada tasa y capacidad de corrección. Para añadir flexibilidad con el fin de manejar diferentes cantidades de datos que presentan diferentes necesidades de protección contra los errores, la tasa se adapta a condiciones de canal variables en el tiempo, además de compensar parámetros que no se conocen en profundidad.

Para una codificación flexible de canal, los bits de datos pueden agruparse en bloques de tamaño variable, y estos bloques pueden codificarse con diferentes cantidades de redundancia. En lugar de utilizar varios códigos de corrección diferentes de errores para codificar los diferentes grupos de bits, es deseable utilizar un único código padre que pueda adaptarse a varias tasas. Esto se denomina codificación de tasa compatible. Con el rápido desarrollo de los sistemas de comunicaciones móviles, existe una necesidad en la técnica de códigos LDPC de tasa compatible adecuados para aplicaciones de ARQ híbrido de alto rendimiento.

Los procedimientos LDPC pueden recuperar palabras de código en entornos muy ruidosos. Dos ejemplos de modelos de canal de comunicaciones son el canal de borrado binario (BEC) y el canal simétrico binario (BSC) . Estos canales se ilustran en las Figuras 1A y 1B. La entrada es binaria ya que comprende bits que tienen el valor 0 ó 1.

Con respecto a las salidas, el BEC tiene una salida de 0, 1 o de borrado. La probabilidad de que un bit se haya transferido correctamente es 1-p y la probabilidad de que un bit se haya transferido de manera errónea, es decir, se haya borrado, es p. Con el BSC, la salida es 0 ó 1. La probabilidad de que un bit se haya transferido correctamente

es 1-p y la probabilidad de que un bit se haya transferido de manera errónea, es decir, se haya recibido un cero cuando se envió un uno y viceversa, es p.

Los códigos LDPC son códigos lineales que se generan a partir de grafos bipartitos dispersos. Un grafo bipartito, también llamado bigrafo, es un conjunto de vértices de grafo divididos en dos conjuntos disjuntos de manera que ningún par de vértices de grafo del mismo conjunto son adyacentes. Un grafo bipartito es un caso especial de un grafo k-partito, donde k = 2. Si hay p y g vértices de grafo en dos conjuntos, el grafo bipartito completo se denota Kp, q. Disperso quiere decir que el código LDPC es una clase especial de códigos de bloques lineales cuya matriz de comprobación de paridad H tiene una baja densidad de unos. Esta dispersión permite una decodificación de baja complejidad, lo que da lugar a una implementación sencilla. La Figura 2 es un ejemplo de un grafo de este tipo. El grafo contiene V nodos variables, vi en lado izquierdo, y C nodos de comprobación, cj en el lado derecho. Los V nodos variables también pueden denominarse nodos sistemáticos o de mensaje.

El grafo bipartito puede representarse mediante una matriz de adyacencia simplificada H con C filas y V columnas. Véase la Figura 3. La Figura 3 es un ejemplo de un matriz binaria dispersa H de comprobación de paridad C x V. Si un nodo de comprobación j-ésimo está conectado a un nodo variable i-ésimo mediante una arista, es decir, los dos nodos son adyacentes, entonces hay un uno en la columna i-ésima y en la fila j-ésima de una matriz de comprobación de paridad H. Es decir, la intersección de una fila i-ésima y una columna j-ésima contiene un "1" cuando una arista une el vértice correspondiente y un "0" cuando no hay ninguna arista. Se dice que un nodo variable y un nodo de restricción (o de comprobación) son adyacentes si están conectados mediante una arista en el grafo. Las aristas, E, del grafo conectan nodos variables con nodos de restricción o de comprobación, y cada arista corresponde a una entrada distinta de cero en la matriz de comprobación de paridad. Cada fila de la matriz H corresponde a un nodo de comprobación y representa una comprobación de paridad y cada columna corresponde a uno de los nodos variables y representa un símbolo demodulado. Puesto que hay 5 nodos variables y 3 nodos de comprobación, la matriz incluye 5 columnas y 3 filas.

El número de símbolos demodulados o de nodos variables N es la longitud del código LDPC. El número de elementos distintos de cero en una fila (columna) se define como el peso dc (dv) de la fila (columna) . Un grafo o código regular es uno en el que todos los nodos variables tienen el mismo grado, por ejemplo j, y todos los nodos de restricción tienen el mismo grado, por ejemplo k. En este caso, decimos que el código es un código regular (j, k) . Por otro lado, un código irregular tiene nodos de restricción y/o nodos variables de grados diferentes. Por ejemplo, algunos nodos variables pueden ser de grado 4, otros de grado 3 y otros de grado 2.

A cada nodo variable se le asocia un bit de palabra de código. Una secuencia de bits asociados uno a uno con la secuencia de nodos variables es una palabra de código del código si y solo si para cada nodo de restricción, los bits adyacentes de la restricción (a través de su asociación con nodos variables) suman cero módulo dos, es decir, comprenden un número par de unos. En algunos casos, parte de estos bits pueden perforarse o pueden... [Seguir leyendo]

donde dicho medio para perforar un subconjunto de bits de palabra de código (30) comprende un medio para perforar de manera progresiva nodos variables (20) para obtener un código deseado a partir de un código anterior,

en el que dicho medio para perforar de manera progresiva nodos variables (20) para obtener un código 5 deseado a partir de un código anterior comprende:

un medio para perforar de manera progresiva dichos nodos variables (20) de un conjunto de nodos variables redundantes no perforados (20) de cardinalidad rm-1, donde rm-1 es el número de elementos del conjunto de nodos variables redundantes no perforados (20) del código anterior y donde los nodos variables redundantes no perforados (20) del código anterior pueden perforarse para

proporcionar el código de una tasa deseada;

donde dicho medio para perforar de manera progresiva nodos variables (20) del conjunto de nodos variables redundantes no perforados (20) comprende un medio de inicialización que comprende:

un medio para calcular para cada nodo de comprobación (25) conectado a al menos un nodo variable redundante (20) el número de nodos variables perforados (20) conectados a dicho

nodo de comprobación (25) ;

un medio para calcular para cada nodo variable redundante no perforado (20) el número de dichos nodos de comprobación (25) conectados a cada nodo variable no perforado (20) , donde cada dicho nodo de comprobación (25) está conectado solamente a un dicho nodo variable perforado (20) ; y

un medio para calcular para cada dicho nodo variable redundante no perforado (20) la suma de dichos nodos variables perforados (20) conectados a tales nodos de comprobación que están conectados a dicho nodo variable redundante no perforado (20) .

3. El medio según la reivindicación 2, en el que el medio comprende un codificador (552) adaptado para generar códigos de tasa alta a partir de códigos de tasa baja, que comprende:

una memoria (2605) , en la que dicho codificador (552) está adaptado para ejecutar instrucciones almacenadas en dicha memoria (2605) , que comprenden:

perforar un subconjunto de bits de palabra de código (30) .

4. El medio según la reivindicación 2, en el que el medio comprende un terminal de acceso (106) que genera códigos de tasa alta a partir de códigos de tasa baja, que comprende:

un transmisor (2608) ;

un receptor (2610) conectado de manera operativa a dicho transmisor (2608) ;

un procesador (2602) conectado de manera operativa a dicho transmisor (2608) y a dicho receptor (2610) ;

una antena (2614) conectada de manera operativa a dicho transmisor (2608) y a dicho receptor (2610) ; y

una memoria (2605) conectada de manera operativa a dicho procesador (2602) , en la que dicho terminal de

acceso (106) está adaptado para ejecutar instrucciones de software almacenadas en dicha memoria (2605) que comprenden:

perforar un subconjunto de bits de palabra de código (30) .

redundantes

a perforar

Suelo

redundantes

a perforar para pasar de

redundantes redundantes

redundantes

redundante

redundante

la cintura

redundantes

Suelo

redundantes

redundantes redundantes

redundantes

redundante

redundante