1 8vo Coloquio Nacional de Códigos, Criptografía y Áreas Relacionadas“Estudio de Códigos LDPC y su implementación en plataformas reconfigurables” Pedro Sibaja Terán Francisco García Ugalde

2 Decodificación de canalCanal con codificación Fuente de información ADC Codificación de canal Modulador Demodulador Decodificación de canal DAC  Formas de onda bits/seg Ruido n(t) Usuario PROTECCIÓN DE LA INFORMACIÓN

3 Longitud del bloque = n (n > k)Codificación por Bloque Longitud del bloque = n (n > k) k Codificador de Canal k n - k Símbolos Símbolos Símbolos Espacio vectorial de dimensión k Espacio vectorial de dimensión n CÓDIGO (n, k)

4 Matriz de chequeo de paridad - Códigos LDPCUn código está especificado por una matriz de chequeo de paridad A

5 Gráfico de Tanner c1 c2 z1 c3 z2 c4 z3 c5 c6 chequeo Nodos bit bitK = 3

6 Gráfico de Tanner …(2) Nodos bit chequeo c1 c2 c3 c4 c5 c6 z1 z2 z3 c1

7 Codificación LDPC

8 Matriz Generadora c = mG

9 Matriz Generadora – No sistemáticaEjemplo: c = mG Para codificar el mensaje m = [ ], se suma la primera y la cuarta línea de G (módulo 2) y se obtiene c = [ ]

10 c = [0 1 1 1 0 0 1] Matriz Generadora – Sistemáticac = mG Para codificar el mensaje m = [ ], se suma la primera y la cuarta línea de G (módulo 2) y se obtiene N c = [ ] N – K K

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

12 Codificación LDPC directa - CuadráticaConstrucción en cascada en vez de gráficas bipartitas Forzar a que H tenga una forma triangular inferior

13 Codificación LDPC 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

14 Arquitectura de un codificador LDPC en un FPGA

15 Principio de un decodificador de pase de mensajes

16 Ciclos en un gráfico de Tanner1 2 3 4 5 6 7 8 9 10 z Nodos bit chequeo Ciclos en un gráfico de Tanner

17 Decodificación LDPC

18 Arquitectura paralela para la decodificación LDPCSalida suave2 Salida suave2 Salida suave2 Salida suave2 Salida suave2 Entrada suave2 Entrada suave2 Entrada suave2 Entrada suave2 Entrada suave2 EP BC,1 EP BC,2 EP BC,3 EP BC,N-1 EP BC,N EPCB,1 EPCB,2 EPCB,M EP BC EPCB Elemento de procesamiento de chequeo-a-bit Elemento de procesamiento de bit-a-chequeo

19 Arquitectura serial para la decodificación LDPCEPCB Elemento de procesamiento de chequeo-a-bit EP BC Elemento de procesamiento de bit-a-chequeo EPCB,1 EPCB,2 EPCB,M Memoria Entradas suaves

20 ¡Gracias!

21 Capacidad de detección y correccion

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

23 Funciones de similitud

24 Codificación LDPC …(3) Pasos para calcular p1 = - X-1(- ET-1A + C) mp2 = -T-1(ET-1A + C) m Operación x1 = Am x2 = T-1x1 x3 = -Ex2 x4 = Cm x5 = x3 + x4 p1 = -X-1x5 Operación x1 = Am x6 = Pp1 x7 = x1 + x7 p2 = T-1(x7)

25 Funciones de similitud

26 Matriz Generadora c = m0g0 + m1g1 +  + mK-1gK-1Un 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

27 Matriz Generadora …(2) 2N N-tuplas constituyen el espacio entero VN2K N-tuplas constituyen el Sub-Espacio de las Palabras de Código

28 Estructura de un nodo físicoSolamente en nodos variables No. de vecinos Estado de la máquina Trama de datos de entrada Trama de datos de salida Nodo lógico k Almacenamiento local No. de nodos lógicos Servidor de envío Interface UF Desde/hacia FU Enrutador Desde/hacia nodos físicos vecinos Al-Rawi G, Cioffi J. A Highly Efficient Domain-Programmable Parallel Architecture for Iterative LDPCC Decoding Department of Electrical Engineering Stanford University, Stanford, CA 94305

29 Matriz de chequeo de paridad dispersa