Acortamiento y perforación de códigos de comprobación de paridad de baja densidad (LDPC) para decodificación de canales.

Método para decodificar canales en un sistema de comunicación usando un código de comprobación deparidad de baja densidad (LDPC) para el cual una matriz de comprobación de paridad tiene N1 columnas,

donde N1 es 16200, teniendo la matriz de comprobación de paridad una parte de información y una parte deparidad, en el que la parte de información tiene K1 columnas, donde K1 es 3240, en el que la parte deparidad tiene (N1-K1) columnas, en el que (N1-K1) es 12960; en el que la parte de información comprendeuna pluralidad de grupos de columnas, teniendo cada grupo de columnas M1 columnas, donde M1 es 360, yel número de grupos de columnas es K1/M1, donde K1/M1 es 9, en el que las secuencias de posiciones de`1' en la 0-ésima columna en el i-ésimo grupo de columnas, i≥0, ..., 8, indicado por ( )

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

Solicitante: SAMSUNG ELECTRONICS CO., LTD..

Nacionalidad solicitante: República de Corea.

Dirección: 129, Samsung-roYeongtong-gu Suwon-si, Gyeonggi-do, 443-742 REPUBLICA DE COREA.

Inventor/es: KIM, JAE-YOEL, YANG, KYEONG, CHEOL, JUNG, PETER, KWON,HWAN-JOON, Jeong,Hong-sil, Lee,Hak-Ju, Lim,Yeon-Ju, Yun,Sung-Ryul, Myung,Seho, Kim,Kyung-Joong.

Fecha de Publicación: .

Clasificación Internacional de Patentes:

  • H03M13/00 SECCION H — 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). › 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).
  • H03M13/11 H03M […] › 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.
  • H03M13/15 H03M 13/00 […] › Códigos cíclicos, es decir, desplazamientos cíclicos de palabras de código que producen otras palabras de código, p. ej. códigos definidos por un generador polinomial, códigos de Bose-Chaudhuri- Hocquenghem [BCH] (H03M 13/17 tiene prioridad).
  • H03M13/29 H03M 13/00 […] › combinando dos o más códigos o estructuras de códigos, p. ej. códigos de productos, códigos de producto generalizados, códigos concatenados, códigos internos y externos.

PDF original: ES-2397540_T3.pdf

 


Fragmento de la descripción:

Acortamiento y perforación de códigos de comprobación de paridad de baja densidad (LDPC) para decodificación de canales Antecedentes de la invención

1. Campo de la invención

La presente invención se refiere en general a un sistema de comunicación usando códigos de comprobación de paridad de baja densidad (LDPC) y, en particular, a un método y un aparato de codificación/decodificación de canales para generar códigos LDPC que tienen diversas longitudes de palabra de código y tasas de codificación a partir de un código LDPC dado.

2. Descripción de la técnica relacionada

En sistemas de comunicación inalámbrica, el rendimiento de enlace disminuye significativamente debido a diversos ruidos en los canales, a un fenómeno de desvanecimiento, y a la interferencia entre símbolos (ISI) . Por tanto, con el fin de realizar sistemas de comunicación digital de alta velocidad que requieren una alta fiabilidad y rendimiento global de datos, tal como la comunicación móvil de próxima generación, difusión digital, e Internet portátil, es necesario desarrollar una tecnología para eliminar el ruido, el desvanecimiento, y la ISI. Recientemente se ha efectuado un estudio intensivo de un código de corrección de errores como método para aumentar la fiabilidad de comunicación recuperando de manera eficaz información distorsionada.

Un código LDPC, introducido por primera vez por Gallager en los años 1960, ha perdido aceptación con el tiempo debido a su complejidad de implementación que no podía resolverse por la tecnología en aquel momento. Sin embargo, como el código turbo, que se descubrió por Berrou, Glavieux y Thitimajshima en 1993, muestra el rendimiento que se aproxima al límite de canales de Shannon, se han efectuado investigaciones sobre la decodificación iterativa y la codificación de canales basándose en un grafo junto con análisis de rendimiento y característica del código turbo. Debido a esta investigación, el código LDPC se estudió de nuevo a finales de los años 1990, y se demostró que el código LDPC tiene un rendimiento que se aproxima al límite de canales de Shannon si se somete a decodificación aplicando una decodificación iterativa basándose en un algoritmo de sumaproducto en un grafo de Tanner (un caso especial de un grafo de factores) correspondiente al código LDPC.

El código LDPC se representa normalmente usando una técnica de representación en grafo, y pueden analizarse muchas características a través de los métodos basados en teoría de grafos, álgebra y teoría de las probabilidades. Generalmente, un modelo en grafo de códigos de canales es útil para la descripción de códigos, y mediante la correlación de información sobre bits codificados con vértices en el grafo y la correlación de las relaciones entre los bits con aristas en el grafo, es posible considerar una red de comunicación en la que los vértices intercambian mensajes predeterminados a través de las aristas, haciendo posible así derivar un algoritmo de decodificación natural. Por ejemplo, un algoritmo de decodificación derivado de un entramado, que puede considerarse como una clase de grafo, puede incluir el algoritmo de Viterbi ampliamente conocido y un algoritmo de Bahl, Cocke, Jelinek y Raviv (BCJR) .

El documento US 2007/0162814 A1 da a conocer un aparato y un método de un sistema de codificación LDPC, que se refiere a codificación y decodificación dentro de un sistema de comunicación.

El código LDPC se define generalmente como una matriz de comprobación de paridad, y puede representarse usando un grafo bipartito, que se denomina grafo de Tanner. El grafo bipartito significa que los vértices que constituyen el grafo se dividen en dos tipos diferentes, y el código LDPC se representa con el grafo bipartito compuesto por vértices, de los que algunos se denominan nodos variables y los demás se denominan nodos de comprobación. Los nodos variables se correlacionan uno a uno con los bits codificados.

Con referencia a las figuras 1 y 2, se realizará una descripción de un método de representación en grafo para el código LDPC.

La figura 1 muestra un ejemplo de una matriz de comprobación de paridad H1 del código LDPC compuesta por 4 filas y 8 columnas. En referencia a la figura 1, puesto que el número de columnas es 8, la matriz de comprobación de paridad H1 implica un código LDPC que genera una palabra de código de longitud 8, y las columnas se correlacionan con 8 bits codificados.

La figura 2 es un diagrama que ilustra un grafo de Tanner correspondiente a H1 de la figura 1.

En referencia a la figura 2, el grafo de Tanner del código LDPC está compuesto por 8 nodos variables x1 (202) , x2

(204) , x3 (206) , x4 (208) , x5 (210) , x6 (212) , x7 (214) y x8 (216) , y 4 nodos de comprobación 218, 220, 222 y 224. Una i-ésima columna y una j-ésima fila en la matriz de comprobación de paridad H1 del código LDPC se correlacionan con un nodo variable xi y un j-ésimo nodo de comprobación, respectivamente. Además, un valor de 1, es decir, un valor diferente a cero, en el punto en el que una i-ésima columna y una j-ésima fila en la matriz de comprobación de paridad H1, del código LDPC se cruzan entre sí, significa que hay una arista entre el nodo variable xi y el j-ésimo nodo de comprobación en el grafo de Tanner de la figura 2.

En el grafo de Tanner del código LDPC, un grado del nodo variable y un nodo de comprobación significa el número de aristas conectadas a cada nodo respectivo, y el grado es igual al número de entradas diferentes a cero en una columna o fila correspondiente al nodo asociado en la matriz de comprobación de paridad del código LDPC. Por ejemplo, en la figura 2, los grados de los nodos variables x1 (202) , x2 (204) , x3 (206) , x4 (208) , x5 (210) , x6 (212) , x7

(214) y x8 (216) son 4, 3, 3, 3, 2, 2, 2 y 2, respectivamente, y los grados de los nodos de comprobación 218, 220, 222 y 224 son 6, 5, 5 y 5, respectivamente. Además, los números de entradas diferentes a cero en las columnas de la matriz de comprobación de paridad H1 de la figura 1, que corresponden a los nodos variables de la figura 2, coinciden con sus grados 4, 3, 3, 3, 2, 2, 2 y 2, y los números de entradas diferentes a cero en las filas de la matriz de comprobación de paridad H1 de la figura 1, que corresponden a los nodos de comprobación de la figura 2, coinciden con sus grados 6, 5, 5 y 5.

Con el fin de representar una distribución de grados para los nodos del código LDPC, una relación del número de nodos variables de grado i respecto al número total de nodos variables se define como fi, y una relación del número de nodos de comprobación de grado j respecto al número total de nodos de comprobación se define como gj. Por ejemplo, para el código LDPC correspondiente a las figuras 1 y 2, f2=4/8, f3=3/8, f4=1/8, y fi=0 para in , 3, 4; y g5=3/4, g6=1/4 y gj=0 para jn5, 6. Cuando una longitud del código LDPC se define como N, es decir, el número de columnas se define como N, y cuando el número de filas se define como N/2, la densidad de entradas diferentes a cero en toda la matriz de comprobación de paridad con la distribución de grados anterior se calcula como la ecuación (1) .

fN + 3 fN + 4 fN 5, 25

4

= .......... (1)

N ⋅ N /2 N

En la ecuación (1) , cuando N aumenta, la densidad de ‘1’ en la matriz de comprobación de paridad disminuye. Generalmente, en cuanto al código LDPC, puesto que la longitud de código N es inversamente proporcional a la densidad de entradas diferentes a cero, el código LDPC con N grande tiene una densidad muy baja. La expresión ‘baja densidad’ en el nombre del código LDPC surge de la relación mencionada anteriormente.

A continuación, con referencia a la figura 3, se realizará una descripción de las características de una matriz de comprobación de paridad de un código LDPC estructurado que va a aplicarse en la presente invención. La figura 3 ilustra esquemáticamente un código LDPC adoptado como la tecnología convencional en DVB-S2, que es una de las normas de difusión digital en Europa.

En la figura 3, N1 indica una longitud de una palabra de código LDPC, K1 proporciona una longitud de una palabra de información, y (N1-K1) proporciona una longitud de paridad. Además, M1 y q se determinan para cumplir q= (N1-K1) /M1. Preferiblemente, K1/M1 debe ser un número entero. Por motivos de conveniencia, la matriz de comprobación de paridad de la figura 3 se denomina primera matriz de comprobación de paridad H1.

Haciendo referencia de nuevo a la figura 3, una estructura de una parte de paridad, es decir, de la K1-ésima columna a la (N1-1) -ésima columna, en la matriz de comprobación... [Seguir leyendo]

 


Reivindicaciones:

1. Método para decodificar canales en un sistema de comunicación usando un código de comprobación de paridad de baja densidad (LDPC) para el cual una matriz de comprobación de paridad tiene N1 columnas, donde N1 es 16200, teniendo la matriz de comprobación de paridad una parte de información y una parte de paridad, en el que la parte de información tiene K1 columnas, donde K1 es 3240, en el que la parte de paridad tiene (N1-K1) columnas, en el que (N1-K1) es 12960; en el que la parte de información comprende una pluralidad de grupos de columnas, teniendo cada grupo de columnas M1 columnas, donde M1 es 360, y el número de grupos de columnas es K1/M1, donde K1/M1 es 9, en el que las secuencias de posiciones de ‘1’ en la 0-ésima columna en el i-ésimo grupo de columnas, i=0, ..., 8, indicado por 10 son 6295 9626 304 7695 4839 4936 1660 144 11203 5567 6347 12557

10691 4988 3859 3734 3071 3494 7687 10313 5964 8069 8296 11090

10774 3613 5208 11177 7676 3549 8746 6583 7239 12265 2674 4292

11869 3708 5981 8718 4908 10650 6805 3334 2627 10461 9285 11120 15 7844 3079 10773

3385 10854 5747

1360 12010 12202

6189 4241 2343

9840 12726 4977,

(1) (2) ( Di )

Ri, 0 , Ri, 0 , ..., Ri, 0 ,

donde un grado de la 0-ésima columna en cada i-ésimo grupo de columnas se indica por Di; en el que la estructura de la parte de información se realiza usando la siguiente regla:

determinar posición de filas con ‘1’, indicada por

(k ) (k )

R ={R +

i, j i, ( j−1)

k=1, 2, …, Di, i=0, …, 8 j=1, …, 359

(k )

Ri, j , mediante

q}mod ( N − K )

donde q es un número entero que cumple q = (N1- K1) /M1 = 36; comprendiendo el método:

(a) demodular (1101) una señal recibida, habiéndose transmitido la señal desde un transmisor usando un acortamiento del código LDPC;

(b) determinar (1103-1109) la información de posición de bits de información acortados usando un patrón 30 de acortamiento predeterminado definido en la siguiente tabla; y

(c) decodificar (1111) la señal demodulada basándose en la información de posición determinada de los bits de información acortados,

donde K2 indica la longitud de bits de información del código LDPC acortado, en el que los bits de información incluyen 168 bits de paridad BCH

Alcance de K2 Método de acortamiento

1) 528≤K2<3240 Para un número entero JJ J ll l − = 360 3240 2K m , acorta todos los bits de información correspondientes a los grupos de columnas π (0) -ésimo, π (1) -ésimo, …, y π (m-1) -ésimo, y adicionalmente acorta 3240-K2-360m bits de información del π (m) -ésimo grupo de columnas. En el presente documento, π indica una función de permutación mostrada en la parte inferior de la tabla. Sin embargo, cuando se acorta una parte de bits de información correspondiente al π (7) =8-ésimo grupo de columnas, los 168 bits de paridad BCH no están sujetos a acortamiento.

2) 168≤K2<528 Acorta todos los bits de información correspondientes a los grupos de columnas π (0) -ésimo, π (1) -ésimo, ..., y π (6) -ésimo, y acorta todos los bits de información excepto los 168 bits de información BCH a partir de los bits de información correspondientes al π (7) =8-ésimo grupo de columnas. Además, acorta adicionalment.

52. K2 bits de información correspondientes al π (8) =0-ésimo grupo de columnas.

π (0) π (1) π (2) π (3) π (4) π (5) π (6) π (7) π (8)

7 3 6 5 2 4 1 8 0

2. Aparato para decodificar canales en un sistema de comunicación usando un código de comprobación de paridad de baja densidad (LDPC) para el cual una matriz de comprobación de paridad tiene N1 columnas,

donde N1 es 16200, teniendo la matriz de comprobación de paridad una parte de información y una parte de paridad, en el que la parte de información tiene K1 columnas, donde K1 es 3240, en el que la parte de paridad tiene (N1-K1) columnas, donde (N1-K1) es 12960; en el que la parte de información comprende una pluralidad de grupos de columnas, teniendo cada grupo de columnas M1 columnas, donde M1 es 360, y el número de grupos de columnas es K1/M1, donde K1/M1 es 9, en el que las secuencias de posiciones de ‘1’

(1) (2) ( Di )

en la 0-ésima columna en el i-ésimo grupo de columnas i=0, ..., 8 indicadas por Ri, 0 , Ri, 0 , ..., Ri, 0 , son 6295 9626 304 7695 4839 4936 1660 144 11203 5567 6347 12557 10691 4988 3859 3734 3071 3494 7687 10313 5964 8069 8296 11090 10774 3613 5208 11177 7676 3549 8746 6583 7239 12265 2674 4292 11869 3708 5981 8718 4908 10650 6805 3334 2627 10461 9285 11120

7844 3079 10773 3385 10854 5747 1360 12010 12202 6189 4241 2343 9840 12726 4977, donde un grado de la 0-ésima columna en cada i-ésimo grupo de columnas se indica por Di;

en el que la estructura de la parte de información se realiza usando la siguiente regla:

(k )

determinar posición de filas con ‘1’, indicada por Ri j , mediante ,

(k ) (k )

R ={R + q}mod ( N − K )

i, ji, ( j−1) 11

k=1, 2, …, Di, i=0, …, 8, j=1, …, 359;

donde q es un número entero que cumple q = (N1- K1) /M1 = 36;

comprendiendo el aparato:

un demodulador (930) para demodular una señal transmitida desde un transmisor usando un acortamiento del código LDPC y recibida mediante el aparato; un determinador (920, 1020) de patrón de acortamiento para determinar información de posición de bits de información acortados usando un patrón de acortamiento predeterminado definido en la siguiente tabla; y un decodificador (940) para decodificar la señal demodulada basándose en la información de posición determinada de los bits de información acortados, donde K2, indica la longitud de bits de información del código LDPC acortado, en el que los bits de información incluyen 168 bits de paridad BCH

Alcance de K2 Método de acortamiento

1) 528≤K2<3240 Para un número entero JJ J ll l − = 360 3240 2K m , acorta todos los bits de información correspondientes a los grupos de columnas π (0) -ésimo, π (1) -ésimo, …, y π (m-1) -ésimo, y adicionalmente acorta 3240-K2-360m bits de información del π (m) -ésimo grupo de columnas. En el presente documento, π indica una función de permutación mostrada en la parte inferior de la tabla. Sin embargo, cuando se acorta una parte de bits de información correspondiente al π (7) =8-ésimo grupo de columnas, los 168 bits de paridad BCH no están sujetos a acortamiento.

2) 168≤K2<528 Acorta todos los bits de información correspondientes a los grupos de columnas π (0) -ésimo, π (1) -ésimo, ..., y π (6) -ésimo, y acorta todos los bits de información excepto los 168 bits de información BCH a partir de los bits de información correspondientes al π (7) =8-ésimo grupo de columnas. Además, acorta adicionalment.

52. K2 bits de información correspondientes al π (8) =0-ésimo grupo de columnas.

π (0) π (1) π (2) π (3) π (4) π (5) π (6) π (7) π (8)

7 3 6 5 2 4 1 8 0

 

Patentes similares o relacionadas:

Método y aparato para la detección de errores en un bloque de datos, del 6 de Septiembre de 2017, de Motorola Solutions, Inc: Un método para la detección de errores en un bloque de datos definido de acuerdo con ETSI TS 102 361-1, que comprende los pasos de: generar […]

Dispositivo y procedimiento de adaptación de velocidad para un sistema de comunicación de datos, del 7 de Septiembre de 2016, de SAMSUNG ELECTRONICS CO., LTD.: Un procedimiento de adaptación de velocidad en un sistema de comunicación de datos, comprendiendo el procedimiento la etapa de: codificación de canal para generar […]

Aparato de transmisión de señal de difusión, aparato de recepción de señal de difusión y métodos correspondiente, del 27 de Julio de 2016, de LG ELECTRONICS INC.: Un método para recibir una señal de difusión en un receptor, comprendiendo el método: recibir una primera señal de difusión que se transmite […]

Aparato de codificación de un indicador de combinación de formato de transporte para un sistema de comunicación móvil CDMA, del 26 de Noviembre de 2014, de SAMSUNG ELECTRONICS CO., LTD.: Un aparato de codificación de Indicador de Combinación de Formato de Transporte TFCI para un sistema de comunicación, que comprende: un generador de secuencia ortogonal […]

Código de corrección de errores adaptativo para comunicaciones de datos a través de una fibra óptica de plástico, del 4 de Junio de 2014, de Knowledge Development for POF, S.L: Metodo para codificar datos digitales para su transmisión a traves de una fibra Optica de plastica , comprendiendo el metodo las etapas de: seleccionar […]

Descodificación de códigos de reacción en cadena por inactivación, del 19 de Marzo de 2014, de Digital Fountain, Inc: Un descodificador para descodificar un código de reacción en cadena, con una pluralidad de símbolos de salida y una pluralidad de símbolos (220, […]

Descodificación de códigos de reacción en cadena por inactivación, del 25 de Diciembre de 2013, de Digital Fountain, Inc: Un procedimiento de descodificación de una secuencia de símbolos de entrada a partir desímbolos de salida […]

Descodificación de códigos de reacción en cadena por inactivación, del 18 de Diciembre de 2013, de Digital Fountain, Inc: Un procedimiento de descodificación de símbolos de origen a partir de símbolos desalida codificados por reacción en […]

Otras patentes de SAMSUNG ELECTRONICS CO., LTD.