Codificación eficiente de códigos LDPC usando matrices de verificación de paridad estructuradas.

Un método de codificar LDPC una secuencia de información s (s0,

s1,..., sk-1) de longitud k ≥ kb * z usando unamatriz modelo mb x nb Hbm, con elementos de matriz p(i,j), i ≥ 0, 1, ..., mb-1 y j ≥ 0, 1, ..., nb-1, para obtener unasecuencia de paridad p (p0, p1, ..., pm-1)' m ≥ mb * z denotado por v, donde v ≥ [v(0) v(1) ... v(mb -1)] y cada elementode v es un vector de columna como v(i) ≥ [piz piz+1 ... p(i+1)z-1]T,I ≥ 0, 1, ..., mb-1,

incluyendo el método

* dividir la secuencia de información s en kb ≥ kb ≥ nb-mb grupos de z bits denotados por u ≥ [u(0) u(1) ... u(kb - 1)],donde cada elemento de u es un vector de columna como sigue**Fórmula**

, i ≥ 0, 1, ..., kb-1;

* determinar v(0) por v(0) ≥

donde x denota el índice de fila de hbm donde la entrada tiene el único valor no negativo que se usa un número imparde veces dentro de hbm y hbm es la kb-ésima columna de la matriz modelo Hbm, donde una matriz de verificación deparidad del código LDPC es una expansión de la matriz modelo Hbm reproduciendo cada p(i, j) negativo por unamatriz todo ceros zxz y cada p(i,j) no negativo por una matriz de permutación Pp(i,j) que es una matriz de identidadzxz cuyas columnas son circulares desplazadas por un tamaño de desplazamiento circular de p(i,j) a la derecha;* determinar v(1), v(2), v(3), ..., v(mb-1) por **Fórmula**

Tipo: Patente Europea. Resumen de patente/invención. Número de Solicitud: E11177322.

Solicitante: Motorola Mobility LLC .

Nacionalidad solicitante: Estados Unidos de América.

Dirección: 600 North US Highway 45 Libertyville, IL 60048 ESTADOS UNIDOS DE AMERICA.

Inventor/es: CLASSON,BRIAN K, BLANKENSHIP,Yufei W, BLANKENSHIP,T. Keith.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • H03M13/11 ELECTRICIDAD.H03 CIRCUITOS ELECTRONICOS BASICOS.H03M CODIFICACION, DECODIFICACION O CONVERSION DE CODIGO, EN GENERAL (por medio de fluidos F15C 4/00; convertidores ópticos analógico/digitales G02F 7/00; codificación, decodificación o conversión de código especialmente adaptada a aplicaciones particulares, ver las subclases apropiadas, p. ej. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; cifrado o descifrado para la criptografía o para otros fines que implican la necesidad de secreto G09C). › H03M 13/00 Codificación, decodificación o conversión de código para detectar o corregir errores; Hipótesis básicas sobre la teoría de codificación; Límites de codificación; Métodos de evaluación de la probabilidad de error; Modelos de canal; Simulación o prueba de códigos (detección o correción de errores para la conversión de código o la conversión analógico/digital, digital/analógica H03M 1/00 - H03M 11/00; especialmente adaptados para los computadores digitales G06F 11/08; para el registro de la información basado en el movimiento relativo entre el soporte de registro y el transductor G11B, p. ej. G11B 20/18; para memorias estáticas G11C). › usando bits de paridad múltiple.

PDF original: ES-2421942_T3.pdf

 


Fragmento de la descripción:

Codificación eficiente de códigos LDPC usando matrices de verificación de paridad estructuradas Campo de la invención

La presente invención se refiere en general a codificar y descodificar datos y, en particular, a un método y aparato para codificar y descodificar datos utilizando códigos de verificación de paridad de baja densidad (LDPC) .

Antecedentes de la invención

Como se describe en la Solicitud de Patente de Estados Unidos número de serie 10/839995, un código de verificación de paridad de baja densidad (LDPC) es un código de bloque lineal especificado por una matriz de verificación de paridad H. En general, un código LDPC se define sobre un campo Galois GF (q) , q º 2. Si q = 2, el

código es un código binario. Todos los códigos de bloque lineal se pueden describir como el producto de un vector de información de k bits s1xk con una matriz de generación de código Gkxn para producir una palabra clave de n bits x1xn, donde la tasa de código es r = k/n. La palabra clave x es transmitida a través de un canal ruidoso, y el vector de señal recibida y se pasa al descodificador para estimar el vector de información s1xk.

Dado un espacio n-dimensional, las filas de G abarcan el subespacio de palabra clave k-dimensional C, y las filas de la matriz de verificación de paridad Hmxn abarcan el espacio dual m-dimensional CI, donde m = n-k. Dado que x = sG y GHT = 0, se deduce que xHT = 0 para todas las palabras clave en el subespacio C, donde “T” (o “T”) denota donde 0 es un vector de fila de todo ceros, y la palabra clave x = [s p] = [s0, s1, …, sk-1, p0, p1, …, pm-1], donde p0, …, pm-1 son los bits de verificación de paridad; y s0, …, sk-1 son los bits sistemáticos, iguales a los bits de información dentro del vector de información.

Para un código LDPC, la densidad de entradas no cero en H es baja, es decir, solamente hay un pequeño porcentaje de 1s en H, permitiendo un mejor rendimiento de corrección de errores y una descodificación más simple que usando un H denso. Una matriz de verificación de paridad también se puede describir mediante un gráfico bipartito. El gráfico bipartito no es solamente una descripción gráfica del código, sino también un modelo para el descodificador. En el gráfico bipartito, un bit de palabra clave (por lo tanto cada columna de H) se representa por un nodo variable a la izquierda, y cada ecuación de verificación de paridad (por lo tanto cada fila de H) se representa por un nodo de verificación a la derecha. Cada nodo variable corresponde a una columna de H y cada nodo de verificación corresponde a una fila de H, haciéndose referencia de forma intercambiable a “nodo variable” y “columna” de H, así como “nodo de verificación” y “fila” de H. Los nodos variables solamente están conectados a nodos de verificación, y los nodos de verificación solamente están conectados a nodos variables. Para un código con n bits de palabra clave y m bits de paridad, el nodo variable vi está conectado al nodo de verificación cj por un borde si el bit de palabra clave i participa en la ecuación de verificación j, i = 0, 1, …, n-1, j = 0, 1, …, m-1. En otros términos, el nodo variable i se conecta al nodo de verificación j si la entrada hji de la matriz de verificación de paridad H es 1. Reflejando la ecuación (1) , los nodos variables representan una palabra clave válida si todos los nodos de verificación tienen paridad par.

A continuación se muestra un ejemplo para ilustrar la relación entre la matriz de verificación de paridad, las correspondiendo la porción lateral izquierda a k ( = 6) bits de información s, correspondiendo la porción lateral derecha a m ( = 6) bits de paridad o. Aplicando (1) , H en (2) define 6 ecuaciones de verificación de paridad como 50 sigue:

H también tiene el gráfico bipartito correspondiente representado en la figura 1.

Como se ha explicado anteriormente, el receptor obtiene una versión contaminada y de la palabra clave transmitida x. Para descodificar y y determinar la secuencia de información original s, se aplica un algoritmo de descodificación iterativo, tal como propagación de creencia, en base al gráfico bipartito. Se pasa información blanda en el formato de relación de probabilidad log (LLRs) de los bits de palabra clave entre el banco de nodos variables y el banco de nodos de verificación. La iteración se para cuando se cumplen todas las ecuaciones de verificación o se alcanza un límite de iteración permitido máximo.

Un diseño de código LDPC estructurado empieza con una pequeña matriz base mbxnb Hb, hace z copias de Hb, e interconecta las z copias para formar una matriz mxn H grande, donde m = mbxz, n = nbxz. Usando la representación de matriz para crear H a partir de Hb, cada 1 en Hb es sustituido por una submatriz de permutación zxz, y cada 0 en Hb es sustituido por una submatriz todo ceros zxz. Este procedimiento mapea esencialmente cada borde de Hb a un borde vectorial de longitud z en H, cada nodo variable de Hb a un nodo variable de vector de longitud z en H, y cada nodo de verificación de Hb a un nodo de verificación de vector de longitud z en H. Los beneficios de vectorizar una matriz Hb pequeña para crear una matriz H grande son:

1. Usando unos valores diferentes de z, se puede diseñar códigos de tasa kb/nb, donde kb = nb-mb, para muchos tamaños de secuencia de información diferentes k = zxkb a partir de una sola matriz base Hb.

2. Los requisitos de memoria se reducen en gran medida. Con un diseño LDPC estructurado, solamente hay que guardar la matriz base Hb y la permutación para sus 1s, lo que requiere significativamente menos memoria dado que Hb es típicamente mucho más pequeño que H y la permutación puede ser muy simple.

3. La codificación y la descodificación pueden ser realizadas en grupos de bits más bien que por bits únicos. Por ejemplo, un grupo de z mensajes puede ser tomado de la memoria, permutado y pasado entre un nodo variable de vector y un nodo de verificación de vector.

Aunque la filosofía del diseño LDPC estructurado reduce en gran medida la complejidad de la implementación, no existe una técnica para diseñar la matriz base y asignar las matrices de permutación para un tamaño de H deseado dado que dé lugar a un código LDPC que tenga buen rendimiento de corrección de errores y pueda ser codificado y descodificado eficientemente. Por lo tanto, se necesita un método y aparato para diseñar un H estructurado y un método y aparato para codificar y descodificar datos utilizando la matriz H estructurada.

“LDPC coding for OFDMA PJY” IEEE 802.16 BROADBAND WIRELESS ACCESS WORKING GROUP, 1 Mayo 2004, páginas 0-11, XP002438609, describe codificación LDPC para OFDMA PHY para el estándar 802.16d.

Cláusulas que exponen aspectos adicionales y que son útiles para la comprensión de la presente invención

1. Un método para operar un transmisor que genera bits de verificación de paridad p = (p0, …, pm-1) en base a un conjunto de símbolos corriente s = (s0, …, sk-1) , incluyendo el método los pasos de:

recibir el conjunto de símbolos corriente s = (s0, …, sk-1) ;

usar una matriz H para determinar los bits de verificación de paridad; y

transmitir los bits de verificación de paridad junto con el conjunto de símbolos corriente;

donde H es una expansión de una matriz base Hb, incluyendo Hb una sección Hb1 y una sección Hb2, incluyendo Hb2 una primera parte que tiene una columna hb que tiene un peso impar superior a 2, e incluyendo una segunda parte H'b2 elementos de matriz para la fila i, columna j igual a

para i = j, 1 para i = j+1,

en otro caso;

donde la expansión de la matriz base Hb usa idénticas submatrices para 1s en cada columna de la segunda parte H'b2, y donde la expansión usa submatrices pareadas para un número par de 1s en hb; y

2. El método de la cláusula 1 donde Hb se expande sustituyendo cada entrada de Hb por una submatriz de tamaño 10 zxz para producir H.

3. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento cero de Hb por una submatriz cero de tamaño zxz para producir H.

4. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento no cero de Hb por una submatriz no cero para producir H.

5. El método de la cláusula 1 donde Hb se expande sustituyendo cada elemento no cero de Hb por una submatriz de permutación no cero para producir H. 20

6. El método de la cláusula 1, donde:

donde el vector hb tiene un peso impar wh> = 3.

7. Un aparato incluyendo:

... [Seguir leyendo]

 


Reivindicaciones:

1. Un método de codificar LDPC una secuencia de información s (s0, s1, ..., sk-1) de longitud k = kb * z usando una matriz modelo mb x nb Hbm, con elementos de matriz p (i, j) , i = 0, 1, …, mb-1 y j = 0, 1, …, nb-1, para obtener una secuencia de paridad p (p0, p1, …, pm-1) ' m = mb * z denotado por v, donde v = [v (0) v (1) … v (mb -1) ] y cada elemento de v es un vector de columna como v (i) = [piz piz+1 … p (i+1) z-1]T, I = 0, 1, …, mb-1,

incluyendo el método * dividir la secuencia de información s en kb = kb = nb-mb grupos de z bits denotados por u = [u (0) u (1) … u (kb - 1) ], donde cada elemento de u es un vector de columna como sigue

, i = 0, 1, …, kb-1;

* determinar v (0) por v (0) =

donde x denota el índice de fila de hbm donde la entrada tiene el único valor no negativo que se usa un número impar de veces dentro de hbm y hbm es la kb-ésima columna de la matriz modelo Hbm, donde una matriz de verificación de paridad del código LDPC es una expansión de la matriz modelo Hbm reproduciendo cada p (i, j) negativo por una matriz todo ceros zxz y cada p (i, j) no negativo por una matriz de permutación Pp (i, j) que es una matriz de identidad zxz cuyas columnas son circulares desplazadas por un tamaño de desplazamiento circular de p (i, j) a la derecha;

* determinar v (1) , v (2) , v (3) , …, v (mb-1) por 25

2. El método de la reivindicación 1, donde la matriz modelo incluye dos submatrices, [Hbm1 Hbm2], donde la primera matriz es de dimensión mb x kb, y Hbm2 es de dimensión mb x mb y además Hbm2 tiene la estructura siguiente y hay whº 3 entradas no negativas en hbm

3. El método de la reivindicación 1, donde el producto de la forma Pp (i, j) u (j) se implementa por un desplazador en 35 cilindro de tamaño z.


 

Patentes similares o relacionadas:

Procedimiento de codificación, procedimiento de descodificación, dispositivo de codificación y dispositivo de descodificación para códigos LDPC estructurados, del 11 de Marzo de 2020, de ZTE CORPORATION: Un procedimiento de codificación para códigos de comprobación de paridad de baja densidad estructurados, LDPC, que comprende: determinar una matriz base MbxNb usada […]

Métodos de adaptación de velocidad para códigos LDPC, del 11 de Marzo de 2020, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Método de adaptación de velocidad de producción de un conjunto de bits codificados a partir de un conjunto de bits de información para la transmisión entre […]

Modulación codificada LDPC en combinación con 256QAM y OFDM, del 7 de Agosto de 2019, de Sun Patent Trust: Un método de generación de señal OFDM, Multiplexación por División de Frecuencia Ortogonal, que comprende: un paso de codificación de codificación […]

Modulación codificada LDPC con código BCH externo en combinación con 256QAM, del 7 de Agosto de 2019, de Sun Patent Trust: Una BICM, codificación y modulación intercalada en bits, procedimiento de codificación que comprende: una primera etapa de codificación de codificar […]

Aparato de comunicación inalámbrica y procedimiento de comunicación inalámbrica, del 24 de Julio de 2019, de Panasonic Intellectual Property Management Co., Ltd: Un dispositivo de comunicación inalámbrica que comprende: un generador de unidad de datos de protocolo de capa física, PPDU, adaptado para generar una unidad de datos […]

Intercalador de bits para un sistema de BICM con códigos de QC-LDPC, del 3 de Julio de 2019, de PANASONIC CORPORATION: Un procedimiento de intercalación de bits para intercalar bits de una palabra de código generada en base a un esquema de codificación de comprobación de paridad de baja densidad […]

Diseño de valores de cambio para códigos LDPC cuasi-cíclicos, del 5 de Junio de 2019, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Un transmisor inalámbrico que comprende un sistema de circuitos de procesamiento que funciona para: codificar bits de información usando una […]

Procedimiento y sistema para transmitir señales satelitales y receptor de las mismas, del 22 de Mayo de 2019, de RAI RADIOTELEVISIONE ITALIANA (S.P.A.): Procedimiento para transmitir una señal satelital que comprende una secuencia de datos MPEG-TS de tipo único que consiste en una secuencia […]

Utilizamos cookies para mejorar nuestros servicios y mostrarle publicidad relevante. Si continua navegando, consideramos que acepta su uso. Puede obtener más información aquí. .