“Estudio de Códigos LDPC y su implementación en plataformas reconfigurables”

Pedro Sibaja TeránFrancisco García Ugalde

8vo Coloquio Nacional de Códigos, Criptografía y Áreas Relacionadas

Fuente de informaci

ónADC

Codificación de canal

Modulador

Demodulador

Decodificación de canal

DAC

Formas de onda

bits/seg

bits/seg

bits/seg

bits/seg

Ruido

n(t)

Usuario

Formas de onda

PROTECCIÓN DELA INFORMACIÓN

Canal con codificación

Símbolos Símbolos

k k

CÓDIGO (n, k)

Longitud del bloque = n (n > k)

n - k

Símbolos

Codificadorde Canal

Espacio vectorial dedimensión k

Espacio vectorial dedimensión n

Codificación por Bloque

TM

T

T

H

a

a

a

2

1

Matriz de chequeo de paridad - Códigos LDPC

Un código está especificado por una matriz de chequeo de paridad A

100110

010101

001011

H

100110

010101

001011

H

Gráfico de Tanner

Nodosbit

Nodoschequeo

c1

c2

c3

c4

c5

c6

z1

z2

z3

N = 6

K = 3

bit

chequ

eo

Nodosbit

Nodoschequeo

c1

c2

c3

c4

c5

c6

z1

z2

z3

c1

c2c3

c4c5

c6

z1z2

z3

Gráfico de Tanner …(2)

Codificación LDPC

TM

T

T

A

a

a

a

2

1

21 AIAAH p

I

AG 2

Matriz Generadora

NKKKK

N

N

N

gggg

gggg

gggg

gggg

G

,3,2,1,

,33,32,31,3

,23,22,21,2

,13,12,11,1

1321 Kmmmm m

c = mG

Matriz Generadora – No sistemática

1011000

0101100

0010110

0001011

G

Ejemplo:

c = mG

Para codificar el mensaje m = [1 0 0 1], se suma la primera y la cuarta línea de G (módulo 2) y se obtiene

c = [1 1 0 0 1 0 1]

1000101

0100111

0010110

0001011

'G

Para codificar el mensaje m = [1 0 0 1], se suma la primera y la cuarta línea de G (módulo 2) y se obtiene

c = [0 1 1 1 0 0 1]

c = mG

Matriz Generadora – Sistemática

N

N – K K

1000

0100

0010

0001

1,11,10,1

1,21,20,2

1,11,10,1

1,01,00,0

KNKKK

KN

KN

KN

K

ppp

ppp

ppp

ppp

IPG

TKNIH P-

0TGH 0v TH

Relación entre una Matriz Generadora y una Matriz de Chequeo de Paridad

Codificación LDPC directa - Cuadrática

• Construcción en cascada en vez de gráficas bipartitas

• Forzar a que H tenga una forma triangular inferior

Codificación LDPC

EDC

TBAH

A

C

B

D E

TM

N – M g M – g

M – g

g

11111

111

0A

C

B

D E

TM

N – M g M – g

M – g

g

11111

111

0

2

1

p

p

m

c

T. Richardson and R. Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 638–656, Feb. 2001.

Arquitectura de un codificador LDPC en un FPGA

Principio de un decodificador de pase de mensajes

01110010

1010111010

1101011100

0110110101

10011001

11

11

A

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

z1

z2

z3

z4

z5

Nodosbit

Nodoschequeo

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

z1

z2

z3

z4

z5

Nodosbit

Nodoschequeo

Gráfico de Tanner …(3)

Ciclos en un gráfico de Tanner

Decodificación LDPC

EP BC,1

EPCB,1 EPCB,2 EPCB,M

EP BC,2 EP BC,N-1

Entradasuave2

Salidasuave2

EP BC,NEP BC,3

Entradasuave2

Salidasuave2

Entradasuave2

Salidasuave2

Entradasuave2

Salidasuave2

Entradasuave2

Salidasuave2

EPCBElemento de procesamiento de chequeo-a-bit EP BC Elemento de procesamiento de bit-a-chequeo

Arquitectura paralela para la decodificación LDPC

EPCBElemento de procesamiento de chequeo-a-bit EP BC Elemento de procesamiento de bit-a-chequeo

EP BC

EPCB,1

EPCB,2

EPCB,M

Memoria Memoria EP BC

EP BC

Entradassuaves

Arquitectura serial para la decodificación LDPC

¡Gracias!

Capacidad de detección y correccion

Visualización de 8 palabras de código de 6-elementos

Funciones de similitud

Pasos para calcularp1 = - X-1(- ET-1A + C) m

Operación

x1 = Am

x2 = T-1x1

x3 = -Ex2

x4 = Cm

x5 = x3 + x4

p1 = -X-1x5

2

1

p

p

m

c

Pasos para calcularp2 = -T-1(ET-1A + C) m

Operación

x1 = Am

x6 = Pp1

x7 = x1 + x7

p2 = T-1(x7)

Codificación LDPC …(3)

Funciones de similitud

Matriz Generadora

Un Código de Bloques es un espacio vectorial K-dimensional,

existen K vectores linealmente independientes que designamos como

g0, g1, … , gK – 1

tal que cada palabra de código en c en C pueda ser representado como una combinación lineal de estos

vectores

c = m0g0 + m1g1 + + mK-1gK-1

donde mi f2

Matriz Generadora …(2)

2N N-tuplas constituyenel espacio entero VN

2K N-tuplas constituyenel Sub-Espacio de las Palabras de Código

Estructura de un nodo físico

Nodo lógico k

No. de vecinos

Trama de datos de entrada

Trama de datos de salida

Solamente en nodos variables

Almacenamiento local

Estadode la

máquina

No. de nodos lógicos

Servidorde

envío

EnrutadorDesde/hacia nodos

físicos vecinos

Interface UF Desde/hacia FU

Al-Rawi G, Cioffi J.A Highly Efficient Domain-Programmable Parallel Architecture for Iterative LDPCC Decoding

Department of Electrical Engineering - 2001Stanford University, Stanford, CA 94305

10000100001000010000

00010010000100001000

01000001000010000100

00001000010001000010

00100000100000100001

10001000100010000000

01000100010000001000

00100010000001000100

00010000001000100010

00000001000100010001

11110000000000000000

00001111000000000000

00000000111100000000

00000000000011110000

00000000000000001111

A

Matriz de chequeo de paridad dispersa