La versión digital de esta tesis está protegida por la Ley de Derechos de Autor del Ecuador.
Los derechos de autor han sido entregados a la “ESCUELA POLITÉCNICA NACIONAL”
bajo el libre consentimiento del (los) autor(es).
Al consultar esta tesis deberá acatar con las disposiciones de la Ley y las siguientes
condiciones de uso:
· Cualquier uso que haga de estos documentos o imágenes deben ser sólo para efectos
de investigación o estudio académico, y usted no puede ponerlos a disposición de otra
persona.
· Usted deberá reconocer el derecho del autor a ser identificado y citado como el autor de
esta tesis.
· No se podrá obtener ningún beneficio comercial y las obras derivadas tienen que estar
bajo los mismos términos de licencia que el trabajo original.
El Libre Acceso a la información, promueve el reconocimiento de la originalidad de las ideas
de los demás, respetando las normas de presentación y de citación de autores con el fin
de no incurrir en actos ilegítimos de copiar y hacer pasar como propias las creaciones de
terceras personas.
Respeto hacia sí mismo y hacia los demás.
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA ELÉCTRICA Y
ELECTRÓNICA
ANÁLISIS Y SIMULACIÓN EN MATLAB DEL MÉTODO DE
DETECCIÓN Y CORRECCIÓN DE ERRORES REED-SOLOMON
(204,188) UTILIZADO EN LA NORMA ISDB-TB E
IMPLEMENTACIÓN EN UN FPGA
PROYECTO PREVIO A LA OBTENCIÓN DEL TÍTULO DE INGENIERO EN
ELECTRÓNICA Y TELECOMUNICACIONES
LENÍN ALEXIS AGUIRRE SÁNCHEZ
ESTEBAN PATRICIO GORDÓN UBIDIA
DIRECTOR: ING. Ph.D. PABLO ANÍBAL LUPERA MORILLO
Quito, junio 2016
ii
DECLARACIÓN
Nosotros, Lenín Alexis Aguirre Sánchez y Esteban Patricio Gordón Ubidia,
declaramos bajo juramento que el trabajo aquí descrito es de nuestra autoría; que
no ha sido previamente presentado para ningún grado o calificación profesional; y
que hemos consultado las referencias bibliográficas que se incluyen en este
documento.
A través de la presente declaración cedemos nuestros derechos de propiedad
intelectual correspondientes a este trabajo, a la Escuela politécnica Nacional, según
lo establecido por la Ley de propiedad intelectual, por su Reglamento y por la
normatividad institucional vigente.
Lenín Alexis Aguirre Sánchez Esteban Patricio Gordón Ubidia
iii
CERTIFICACIÓN
Certifico que el presente trabajo fue desarrollado por Lenín Alexis Aguirre Sánchez y Esteban Patricio Gordón Ubidia, bajo mi supervisión.
Ing. Ph.D. Pablo Aníbal Lupera Morillo
DIRECTOR DEL PROYECTO
AGRADECIMIENTO
iv
“DAR GRACIAS A DIOS POR LO QUE SE TIENE, ALLÍ EMPIEZA EL ARTE DE
VIVIR”
El éxito radica en aprovechar los medios y las facilidades que la vida nos ofrece;
nos convertimos en personas exitosas cuando nuestros logros se ponen a
disposición de los demás.
Mi agradecimiento eterno a mis padres Marcia y Víctor, primeros educadores en mi
vida quienes con su ejemplo de trabajo, esfuerzo, dedicación y amor cultivan en mí
los conocimientos y valores necesarios para el desenvolvimiento en la sociedad.
A mi hermano Víctor Fabián, quien siempre ha estado a mi lado de manera
incondicional. A toda mi familia, por compartir los buenos y malos momentos siendo
soporte indispensable para seguir adelante.
De manera especial mi agradecimiento al Doctor Pablo Lupera, pilar fundamental
en la realización de la presente, quien dedicó su tiempo, paciencia y vastos
conocimientos para guiarnos en el camino acertado a fin de llevar a buen término
la ejecución de este trabajo investigativo.
Mi agradecimiento profundo a la institución del saber; La Escuela Politécnica
Nacional, en la cual me he formado con los más altos valores y conocimientos a lo
largo de estos años de preparación académica profesional, a sus docentes que
realizan una actividad creadora y transformadora contribuyendo de esta manera a
que los jóvenes podamos adquirir los conocimientos necesarios a fin de ser útiles
y retribuir a nuestra sociedad.
Lenín
AGRADECIMIENTO
v
Doy gracias a Dios por bendecirme para poder culminar este sueño tan anhelado,
gracias por darme una familia maravillosa.
A mis padres, María Fernanda y Hugo, porque han sido mi soporte, apoyo y consejo
en todos los pasos y decisiones desde el inicio hasta el final de mi carrera y a lo
largo de toda mi vida. Gracias por ser mi ejemplo y por estar siempre a mi lado, a
ustedes les debo lo que soy ahora.
A mis hermanos Vanesa y Ricardo, por su apoyo y cariño permanente que me
impulsa a seguir adelante.
A mi abuelita Bachita, por ser un ejemplo de amor en mi vida. Gracias por todo el
apoyo y cariño que me brinda en el día a día de mi vida.
A mi compañero de tesis Lenin Aguirre por el esfuerzo, dedicación y paciencia
durante la elaboración de este proyecto. Porque sé que siempre podré contar con
su apoyo cualquiera sea la circunstancia.
A mi director de tesis Ing. Ph.D. Pablo Lupera por su tiempo y colaboración brindada
durante la elaboración de este proyecto.
A la Escuela Politécnica Nacional ya que fueron en sus aulas en donde recibí el
conocimiento intelectual para llegar a ser el profesional que hoy soy.
A mis amigos quienes estuvieron conmigo durante todos estos años de estudios y
con quienes hemos vivido grandes momentos. Gracias por el apoyo y por el empuje
que me brindaron para seguir adelante en momentos de complicación en la
universidad, principalmente a Vane, Taty, Moni, Juanfer, Telmo.
Esteban Gordón Ubidia
DEDICATORIA
vi
A la memoria de mis abuelitos Dorila y Ernesto, personas
excepcionales que llenaron mi vida de experiencias,
conocimientos, valores y un profundo amor.
Mi eterna inspiración para luchar en la consecución
de mis objetivos propuestos.
La presencia de su ausencia, hace que
permanezcan siempre en mi corazón.
A mis padres Marcia y Víctor, por su apoyo absoluto
a lo largo de mi existencia.
A mi hermano Víctor Fabián, por ser mi ejemplo
de dedicación y responsabilidad.
A mis abuelitos Delia y Augusto
por sus sabios consejos.
A mi amor Gisella, que ha estado siempre a mi lado brindándome
cariño y confianza en todo este tiempo.
A mis amigos Esteban, Telmo, Luis, Juan Fer, Vane, Taty, Moni, Marlon y Marco
amigos incondicionales que compartieron conmigo los años de estudio.
LENÍN
DEDICATORIA
vii
Dedico este trabajo a mis padres, hermanos y abuelita con
todo mi cariño y amor porque hicieron todo para que
lograra mis sueños y metas, por estar siempre
conmigo cada día de mi vida, a ustedes por
siempre mi corazón y mi agradecimiento.
Gracias por todo, los amo mucho!
Esteban Gordón Ubidia
CONTENIDO
viii
RESUMEN ........................................................................................................................ XX
PRESENTACIÓN............................................................................................................ XXI
CAPÍTULO 1
FUNDAMENTOS TEÓRICOS .......................................................................................... 1
1.1 INTRODUCCIÓN A LA TELEVISIÓN DIGITAL TERRESTRE ISDB-Tb ... 1
1.1.1 NORMA BRASILEÑA ABNT NBR ......................................................... 2
1.1.1.1 Características Generales ................................................... 2
1.1.1.2 Codificación externa ............................................................. 5
1.2 CODIFICACIÓN DE CORRECCIÓN DE ERRORES..................................... 6
1.2.1 DISTANCIA MÍNIMA DE UN CÓDIGO ................................................. 6
1.2.2 CÓDIGOS FEC......................................................................................... 6
1.2.3 CÓDIGOS DE BLOQUE LINEAL .......................................................... 7
1.2.4 CÓDIGOS CÍCLICOS.............................................................................. 8
1.2.5 CÓDIGOS BCH ........................................................................................ 9
1.3 REED-SOLOMON.............................................................................................. 10
1.3.1 FUNDAMENTOS MATEMÁTICOS ..................................................... 10
1.3.1.1 Teoría de Conjuntos ........................................................... 11
1.3.1.2 Teoría de Grupos ................................................................ 14
1.3.1.3 Teoría de Anillos ................................................................. 16
1.3.1.4 Teoría de Campos .............................................................. 17
1.3.1.5 Teoría de los Campos de Galois...................................... 19
1.3.2 CONCEPTOS ALGEBRAICOS BÁSICOS......................................... 20
1.3.2.1 Aritmética de Módulo 2 ...................................................... 20
1.3.2.2 Estructura Polinomial ......................................................... 21
1.3.3 CODIFICACIÓN Y DECODIFICACIÓN DEL CÓDIGO REED-
SOLOMON .............................................................................................. 22
1.3.3.1 Polinomio Primitivo ............................................................. 24
1.3.3.2 Polinomio Generador ......................................................... 25
1.3.3.3 Ejemplo de Codificación RS(15,9) ................................... 25
1.3.3.4 Ejemplo de Decodificación RS(15,9) ............................... 36
ix
1.3.3.5 Parámetros iniciales para el cálculo del código RS
abreviado (204,188) .......................................................... 55
1.4 MODULACIÓN ................................................................................................... 56
1.4.1 QPSK........................................................................................................ 56
1.4.2 OFDM ....................................................................................................... 57
1.4.3 Diagrama Modulación a utilizarse en la simulación.......................... 60
1.5 RUIDO GAUSSIANO Y DESVANECIMIENTO ............................................. 61
1.5.1 Ruido Gaussiano .................................................................................... 61
1.5.2 Desvanecimiento de una Señal ........................................................... 62
CAPÍTULO 2
SIMULACIÓN Y ANÁLISIS DEL DESEMPEÑO DEL CODIFICADOR REED-
SOLOMON UTILIZANDO MATLAB ............................................................................. 63
2.1 PROCEDIMIENTO Y SOLUCIÓN..................................................................... 63
2.1.1 DIAGRAMAS DE FLUJO DE LOS PARÁMETROS INICIALES........ 64
2.1.1.1 Generación del Polinomio Primitivo ........................................... 64
2.1.1.2 Campo de Galois .......................................................................... 65
2.1.1.3 Operación de Suma GF ............................................................... 66
2.1.1.4 Operación XOR ............................................................................. 67
2.1.1.5 Establecimiento del Polinomio Generador................................ 68
2.1.1.6 Suma XOR ..................................................................................... 68
2.1.1.7 Operación de Redondeo .............................................................. 70
2.1.2 DIAGRAMAS DE FLUJO DE LA CODIFICACIÓN .............................. 71
2.1.2.1 Codificador ..................................................................................... 71
2.1.3 DIAGRAMAS DE FLUJO DE TRANSMISIÓN ..................................... 72
2.1.3.1 Modulador ...................................................................................... 72
2.1.3.2 Generador de Ruido ..................................................................... 73
2.1.3.3 Demodulador ................................................................................. 74
2.1.4 DIAGRAMAS DE FLUJO DE LA DECODIFICACIÓN ........................ 74
2.1.4.1 Cálculo de los Síndromes ............................................................ 75
2.1.4.2 Algoritmo de Berlekamp-Massey................................................ 76
2.1.4.3 Polinomio localizador de error .................................................... 78
x
2.1.4.4 Polinomio evaluador del error ..................................................... 79
2.1.4.5 Magnitud del error ......................................................................... 80
2.1.4.6 Decodificador ................................................................................. 82
2.1.5 DIAGRAMA DE FLUJO RUTINA PRINCIPAL REED-SOLOMON ... 83
2.1.6 RESULTADOS DE LA SIMULACIÓN DE LOS ALGORITMOS DEL
CODIFICADOR REED-SOLOMON ....................................................... 83
2.1.6.1 Ejemplo y resultados de la codificación RS (15,9) ................. 84
2.1.6.2 Ejemplo y resultados de la codificación RS (204,188) .......... 91
2.2 EFICIENCIA DEL ALGORITMO FRENTE AL NIVEL DE ERROR .............110
CAPÍTULO 3
IMPLEMENTACIÓN DEL CODIFICADOR Y DECODIFICADOR RS ...................120
3.1 CARACTERÍSTICAS DE LA TARJETA FPGA SPARTAN 3E ....................120
3.1.1 MÓDULO INTERFAZ_SPI ....................................................................123
3.1.2 MÓDULO INTERFAZ_USUARIO.........................................................125
3.1.3 MÓDULO ALGORITMO_CONTROL ...................................................127
3.1.4 COMUNICACIÓN UART........................................................................127
3.2 LENGUAJE VHDL .............................................................................................129
3.2.1 VENTAJAS DEL LENGUAJE VHDL ....................................................129
3.2.2 CARACTERÍSTICAS DEL LENGUAJE VHDL ...................................130
3.2.2.1 Descripción textual normalizada...............................................130
3.2.2.2 Extenso rango de capacidad descriptiva ................................130
3.2.3 MODELADO VHDL.................................................................................130
3.2.3.1 Declaración de Entidad ..............................................................130
3.2.3.2 Cuerpo de Arquitectura ..............................................................131
3.2.4 TIPO DE DESCRIPCIÓN ......................................................................131
3.2.4.1 Descripción de comportamiento ...............................................131
3.2.4.2 Descripción de flujo de datos ....................................................131
3.2.4.3 Descripción estructural...............................................................132
3.2.4.4 Descripción mixta ........................................................................132
3.3 TRANSFORMACIÓN DEL ALGORITMO DESARROLLADO EN MATLAB
A LENGUAJE VHDL...........................................................................................132
xi
3.4 SIMULACIÓN DEL CODIFICADOR RS(15,9) EN ISIM SIMULATOR DE
XILINX...................................................................................................................136
3.5 IMPLEMENTACIÓN FÍSICA DEL CODIFICADOR Y DECODIFICADOR RS
(15,9) ....................................................................................................................138
3.5.1 GUÍA DE USO DEL PANEL DE CONTROL DE ALGORITMOS
PROGRAMADOS EN TARJETA FPGA ..............................................139
3.5.2 RECURSOS UTILIZADOS EN LA TARJETA FPGA SPARTAN 3E
PARA EL CODIFICADOR Y DECODIFICADOR RS (15,9) ............150
CAPÍTULO 4
CONCLUSIONES Y RECOMENDACIONES.............................................................151
4.1 CONCLUSIONES .........................................................................................151
4.2 RECOMENDACIONES................................................................................153
BIBLIOGRAFÍA ..............................................................................................................155
ANEXO A:
CÓDIGO FUENTE GENERACIÓN POLINOMIO PRIMITIIVO.
ANEXO B:
CÓDIGO FUENTE GENERACIÓN CAMPO DE GALOIS Y TABLA XOR.
ANEXO C:
CÓDIGO FUENTE DEL CODIFICADOR REED-SOLOMON (15,9).
ANEXO D:
CÓDIGO FUENTE DEL GENERADOR DE ERROR, RS(15,9)
ANEXO E:
CÓDIGO FUENTE DEL ALGORITMO SÍNDROMES, RS(15,9).
ANEXO F:
CÓDIGO FUENTE DEL ALGORITMO BERLEKAMP-MASSEY, RS(15,9).
ANEXO G:
CÓDIGO FUENTE DEL ALGORITMO POLINOMIO LOCALIZADOR, RS(15,9).
ANEXO H:
CÓDIGO FUENTE DEL ALGORITMO POLINOMIO EVALUADOR DEL ERROR,
RS(15,9).
xii
ANEXO I:
CÓDIGO FUENTE DEL ALGORITMO MAGNITUD DEL ERROR, RS(15,9).
ANEXO J:
CÓDIGO FUENTE DEL DECODIFICADOR REED-SOLOMON (15,9).
ANEXO K:
CÓDIGO FUENTE DEL CODIFICADOR REED-SOLOMON (204,188).
ANEXO L:
CÓDIGO FUENTE DEL MODULADOR OFDM
ANEXO M:
CÓDIGO FUENTE DEL GENERADOR DE RUIDO, RS(204,188)
ANEXO N:
CÓDIGO FUENTE DEL DEMODULADOR OFDM
ANEXO O:
CÓDIGO FUENTE DEL ALGORITMO SÍNDROMES, RS(204,188).
ANEXO P:
CÓDIGO FUENTE DEL ALGORITMO BERLEKAMP-MASSEY, RS(204,188).
ANEXO Q:
CÓDIGO FUENTE DEL ALGORITMO POLINOMIO LOCALIZADOR, RS(204,188).
ANEXO R:
CÓDIGO FUENTE DEL ALGORITMO POLINOMIO EVALUADOR DEL ERROR,
RS(204,188).
ANEXO S:
CÓDIGO FUENTE DEL ALGORITMO MAGNITUD DEL ERROR, RS(204,188).
ANEXO T:
CÓDIGO FUENTE DEL DECODIFICADOR REED-SOLOMON RS(204,188).
ANEXO U:
CÓDIGO FUENTE DEL CODIFICADOR Y DECODIFICADOR REED-SOLOMON
(15,9) EN FPGA.
ANEXO V:
CÓDIGO FUENTE DE LA SIMULACIÓN DEL CODIFICADOR REED-SOLOMON
(15,9) EN FPGA.
ANEXO W:
CÓDIGO FUENTE DEL CODIFICADOR REED-SOLOMON (204,188) EN FPGA.
xiii
ANEXO X:
CÓDIGO FUENTE DEL DECODIFICADOR REED-SOLOMON (204,188) EN
FPGA.
ANEXO Y:
INSTALACIÓN PAQUETES DE COMUNICACIÓN MATLAB.
ANEXO Z:
INTERFAZ GRÁFICA PRINCIPAL (MAIN).
xiv
ÍNDICE DE FIGURAS
CAPÍTULO 1
Figura 1.1 Visión general del sistema de transmisión de TV digital ........................... 2
Figura 1.2 Transmisión del TSP ....................................................................................... 5
Figura 1.3 Formato de paquetes TSP MPEG y transmisión TSP ............................... 6
Figura 1.4 Circuito de registro de desplazamiento con realimentación lineal ......... 34
Figura 1.5 Berlekamp-Masey .......................................................................................... 42
Figura 1.6 Recíprocos de raíces y correspondiente posición................................... 53
Figura 1.7 Diagrama de constelaciones modulación QPSK ...................................... 56
Figura 1.8 Multiportadora convencional frente a portadoras ortogonales ............... 59
Figura 1.9 Espectro de una señal OFDM vs FDM....................................................... 60
Figura 1.10 Transmisor con modulación OFDM .......................................................... 60
Figura 1.11 Receptor con modulación ODFM.............................................................. 61
Figura 1.12 Ruido Gaussiano ......................................................................................... 62
Figura 1.13 Desvanecimiento de una Señal................................................................. 62
CAPÍTULO 2
Figura 2.1 Sistema de Transmisión ............................................................................... 63
Figura 2.2 Algoritmo para la generación del Polinomio Primitivo ............................ .64
Figura 2.3 Campo de Galois .......................................................................................... .65
Figura 2.4 Suma GF ........................................................................................................ .66
Figura 2.5 Tabla XOR ..................................................................................................... .67
Figura 2.6 Procedimiento para el establecimiento del Polinomio Generador ........ .68
Figura 2.7 Suma XOR ..................................................................................................... .69
Figura 2.8 Procedimiento de la operación de Redondeo .......................................... .70
Figura 2.9 Codificador RS – parte 1 ............................................................................. .71
Figura 2.10 Codificador RS – parte 2 ........................................................................... .72
Figura 2.11 Modulador .................................................................................................... .73
Figura 2.12 Generador de Ruido ................................................................................... .73
Figura 2.13 Demodulador ............................................................................................... .74
Figura 2.14 Cálculo de los Síndromes - parte 1 ......................................................... .75
xv
Figura 2.15 Cálculo de los Síndromes - parte 2 ......................................................... .75
Figura 2.16 Berlekamp-Massey - parte 1 ..................................................................... .76
Figura 2.17 Berlekamp-Massey - parte 2 ..................................................................... .77
Figura 2.18 Berlekamp-Massey - parte 3 ..................................................................... .78
Figura 2.19 Polinomio localizador - parte 1 ................................................................. .78
Figura 2.20 Polinomio localizador - parte 2 ................................................................. .79
Figura 2.21 Polinomio evaluador del error................................................................... .79
Figura 2.22 Magnitud del error - parte 1....................................................................... .80
Figura 2.23 Magnitud del error - parte 2....................................................................... .81
Figura 2.24 Decodificación ............................................................................................. .82
Figura 2.25 Rutina Principal REED-SOLOMON ......................................................... .83
Figura 2.26 Menú principal del simulador de Matlab ................................................. .84
Figura 2.27 Interfaz Codificación RS (15,9) ............................................................... .85
Figura 2.28 Entrada de datos......................................................................................... .85
Figura 2.29 Parámetro Campo Galois .......................................................................... .86
Figura 2.30 Tabla XOR de las operaciones entre los elementos del campo de Galois
para un codificador RS(15,9) ........................................................................................ .86
Figura 2.31 Polinomio Primitivo para el codificador RS(15,9) ................................. .86
Figura 2.32 Polinomio Generador para el codificador RS(15,9) ............................. .87
Figura 2.33 Opción para la codificación RS(15,9) en el simulador de Matlab ....... 87
Figura 2.34 Ejemplo de una palabra codificada con RS (15,9) ............................... .87
Figura 2.35 Simulación de la Codificación RS(15,9) en Simulinlk ........................... .88
Figura 2.36 Interfaz de decodificación Reed-Solomon (15,9) ................................. .88
Figura 2.37 Ingreso de errores para la decodificación RS(15,9) ............................ .89
Figura 2.38 Parámetros generados en la Decodificación RS(15,9) ....................... .89
Figura 2.39 Resultados de la Decodificación RS(15,9) ............................................ .90
Figura 2.40 Simulación de la Decodificación en Simulink......................................... .90
Figura 2.41 Bloques internos del algoritmo de Decodificación ................................ .91
Figura 2.42 Interfaz de la Codificación RS(204,188) ................................................ .92
Figura 2.43 Parámetros de Inicio del codificador RS (204,188) ............................. .93
Figura 2.44 Simulación ................................................................................................... .93
Figura 2.45 Palabra Codificada ..................................................................................... .94
Figura 2.46 Opciones del codificador RS (204,188) ................................................. .94
xvi
Figura 2.47 Simulación de la Codificación RS (204,188) en Simulink .................... .95
Figura 2.48 Interfaz de la modulación en el codificador RS(204,188) ................... .96
Figura 2.49 Representación discreta de la Palabra Codificada ............................... .96
Figura 2.50 Diagrama de constelación del modulador antes de la transmisión .... .97
Figura 2.51 Transformada Inversa de Fourier de la palabra codificada ................. .97
Figura 2.52 Señal después de pasar por DAC ........................................................... .98
Figura 2.53 Señal modulada a transmitirse ................................................................. .98
Figura 2.54 Opciones de intervalo de guarda en la simulación ............................... .99
Figura 2.55 Señal Modulada a 1/4 de intervalo de guarda ....................................... .99
Figura 2.56 Señal Modulada a 1/8 de intervalo de guarda ....................................... .99
Figura 2.57 Señal Modulada a 1/16 de intervalo de guarda ....................................100
Figura 2.58 Señal Modulada a 1/32 de intervalo de guarda. ..................................100
Figura 2.59 SNR y Ps.....................................................................................................100
Figura 2.60 Resultados del proceso de Demodulación ............................................101
Figura 2.61 Señal Recibida con ruido..........................................................................101
Figura 2.62 Señal en fase y cuadratura en el proceso de demodulación .............102
Figura 2.63 Señal recibida después del conversor analógico a digital ..................102
Figura 2.64 Señal recuperada con errores en el receptor .......................................103
Figura 2.65 Diagrama de bloques del canal simulado en Simulink ........................103
Figura 2.66 Diagrama de constelación del Demodulador en el receptor...............104
Figura 2.67 Interfaz para la decodificación de la señal ............................................104
Figura 2.68 Interfaz completa del proceso de Decodificación .................................105
Figura 2.69 Datos de entrada .......................................................................................105
Figura 2.70 Parámetros del Proceso de Decodificación RS (204,188) ................107
Figura 2.71 Palabra Decodificada RS (204,188) ......................................................108
Figura 2.72 Simulación de la Decodificación..............................................................109
Figura 2.73 Interfaz gráfica con los valores completos de la decodificación ........110
Figura 2.74 Errores vs Potencia de Ruido .................................................................112
Figura 2.75 Número de errores vs número de transmisiones para Ps (0.0008) ..113
Figura 2.76 Número de errores vs número de transmisiones para Ps (0.0009) ..113
Figura 2.77 Número de errores vs número de transmisiones para Ps (0.0010) ..113
Figura 2.78 Número de errores vs número de transmisiones para Ps (0.0011) ..114
Figura 2.79 Número de errores vs número de transmisiones para Ps (0.0012) ..114
xvii
Figura 2.80 Número de errores vs número de transmisiones para Ps (0.0013) ..114
Figura 2.81 Número de errores vs número de transmisiones para Ps (0.0014) .115
Figura 2.82 Número de errores vs número de transmisiones para Ps (0.0015) .115
Figura 2.83 Número de errores vs número de transmisiones para Ps (0.0020) ..115
Figura 2.84 Modulación con potencia de ruido de Ps (0.00002) ...........................116
Figura 2.85 Señal recibida sin ruido ............................................................................117
Figura 2.86 Diagrama de constelaciones señal sin errores .....................................117
Figura 2.87 Modulación con potencia de ruido de Ps (0.02) ..................................118
Figura 2.88 Señal recibida con ruido ...........................................................................118
Figura 2.89 Diagrama de constelaciones señal con errores ...................................119
CAPÍTULO 3
Figura 3.1 Tarjeta FPGA Spartan-3E utilizada en el proyecto ................................120
Figura 3.2 Módulos de una tarjeta FPGA ..................................................................121
Figura 3.3 Componentes de la Interfaz SPI ..............................................................122
Figura 3.4 Comunicación SPI .......................................................................................123
Figura 3.5 Diagrama de bloques del módulo Interfaz SPI ......................................124
Figura 3.6 Estados de control del módulo SPI ...........................................................125
Figura 3.7 Diagrama de bloques del puerto de entrada ...........................................126
Figura 3.8 Diagrama de bloques del puerto de salida ..............................................127
Figura 3.9 Diagrama de Bloques del sistema de transmisión y recepción digital 128
Figura 3.10 Ícono de la herramienta Matlab HDL Coder..........................................133
Figura 3.11 Selección del nombre del archivo VHDL ...............................................133
Figura 3.12 Selección de la función de Matlab para la transformación .................134
Figura 3.13 Parámetros para la generación del archivo VHDL ...............................134
Figura 3.14 Ventana de generación de código VHDL exitosa .................................135
Figura 3.15 Script VHDL generado en Matlab ...........................................................135
Figura 3.16 Esquema de circuito Codificador RS(15,9) ..........................................136
Figura 3.17 Simulación del codificador RS(15,9) .....................................................137
Figura 3.18 Sistema de comunicación entre PC y tarjeta FPGA ............................138
Figura 3.19 Prueba del codificador y decodificador RS en la tarjeta FPGA .........139
Figura 3.20 Menú principal de la interfaz del codificador .........................................140
xviii
Figura 3.21 Interfaz para la ejecución en la tarjeta FPGA .......................................140
Figura 3.22 Ingreso de la palabra de información .....................................................141
Figura 3.23 Circuito de comunicación entre FPGA y PC .........................................141
Figura 3.24 Menú de inicio de Windows .....................................................................142
Figura 3.25 Pantalla de panel de control ....................................................................142
Figura 3.26 Pantalla de Administración de dispositivos ...........................................143
Figura 3.27 Puertos serial activados en el computador ...........................................143
Figura 3.28 Configuración del bloque de comunicación...........................................144
Figura 3.29 Bloques de comunicación serial..............................................................144
Figura 3.30 Parámetros de configuración del bloque de control de comunicación
serial ..................................................................................................................................145
Figura 3.31 Diagrama de bloques de comunicación serial con sus parámetros….146
Figura 3.32 Display de Codificación en Simulink .......................................................147
Figura 3.33 Interfaz FPGA con la palabra codificada recibida en PC ....................147
Figura 3.34 Display de codificación con los datos binarios .....................................148
Figura 3.35 Ingreso de errores en el proceso de decodificación ............................148
Figura 3.36 Inicio de la Decodificación de una palabra errada ...............................148
Figura 3.37 Display de decodificación en Simulink ...................................................149
Figura 3.38 Display de decodificación con los datos binarios .................................149
Figura 3.39 Interfaz FPGA con la palabra decodificada ...........................................150
Figura 3.40 Recursos utilizados en tarjeta FPGA Spartan 3E para el codificador y
decodificador RS (15,9) ................................................................................................150
xix
ÍNDICE DE TABLAS
CAPÍTULO 1
Tabla 1.1 Parámetros principales del sistema de transmisión .................................... 4
Tabla 1.2 Polinomios primitivos de grado 2 a 21 ......................................................... 25
Tabla 1.3 Suma módulo 2................................................................................................ 29
Tabla 1.4 Campos de Galois !"(2#) ............................................................................ 30
Tabla 1.5 Codificación por medio de registro de desplazamiento con realimentación
lineal .................................................................................................................................... 36
Tabla 1.6 Iteraciones del algoritmo Berlekamp-Masey............................................... 43
CAPÍTULO 2
Tabla 2.1 Elementos del campo de Galois .................................................................. .65
Tabla 2.2 Campo de Galois – Matlab ........................................................................... .70
Tabla 2.3 Bits errados en el ejemplo de codificación RS(204,188). .......................107
Tabla 2.4 Resultados estadísticos de números de errores producidos por ruido ......
...........................................................................................................................................111
CAPÍTULO 3
Tabla 3.1 Puertos de la Interfaz_Usuario....................................................................126
xx
ÍNDICE DE ECUACIONES
CAPÍTULO 1
Ecuación 1.1 Polinomio Generador .............................................................................. .25
Ecuación 1.2 Campo de Galois Reed-Solomon (15,9) .............................................. .26
Ecuación 1.3 Polinomio Primitivo Reed-Solomon (15,9)........................................... .26
Ecuación 1.4 Polinomio Generador expandido........................................................... .31
Ecuación 1.5 Polinomio Generador Reed-Solomon (15,9) ....................................... .31
Ecuación 1.6 Cálculo de la paridad............................................................................... .32
Ecuación 1.7 Palabra codificada ................................................................................... .34
Ecuación 1.8 Síndromes ................................................................................................. .37
Ecuación 1.9 Discrepancia entre síndromes ............................................................... .41
Ecuación 1.10 Polinomio localizador del error ............................................................ .41
Ecuación 1.11 Polinomio Auxiliar inicial ....................................................................... .41
Ecuación 1.12 Complejidad Lineal ................................................................................ .41
Ecuación 1.13 Polinomio Auxiliar .................................................................................. .41
Ecuación 1.14 Iteraciones en curso .............................................................................. .41
Ecuación 1.15 Polinomio evaluador del error.............................................................. .53
Ecuación 1.16 Algoritmo de Forney ............................................................................. .53
Ecuación 1.17 Palabra de Información decodificada ................................................. .55
Ecuación 1.18 Campo de Galois Reed-Solomon (204,188) ..................................... .55
Ecuación 1.19 Polinomio Primitivo Reed-Solomon (204,188) .................................. .55
Ecuación 1.20 Polinomio Primitivo Reed-Solomon (204,188) .................................. .56
Ecuación 1.21 Señal OFDM ........................................................................................... .58
xxi
RESUMEN
Este trabajo tiene como objetivo realizar una descripción completa de la codificación
y decodificación Reed- Solomon descrita en el estándar internacional de televisión
digital terrestre ISDB-Tb. Para la elaboración de este documento se han utilizado
numerosas y variadas fuentes de información, pero el documento de referencia
básico para el desarrollo aquí presentado es el estándar brasileño de televisión
digital terrestre ABNT NBR 15601.
Este proyecto de titulación denominado “ANÁLISIS Y SIMULACIÓN EN MATLAB
DEL MÉTODO DE DETECCIÓN Y CORRECCIÓN DE ERRORES REED-
SOLOMON (204,188) UTILIZADO EN LA NORMA ISDB-TB E IMPLEMENTACIÓN
EN UN FPGA” se enfoca en analizar la estructura del codificador Reed-Solom.
Para el presente proyecto se plantea construir un algoritmo del codificador y
decodificador utilizando Matlab y posterior implementación en la tarjeta FPGA
Spartan 3E en lenguaje VHDL.
Con el fin de facilitar la comprensión y el uso de los algoritmos, se crea una interfaz
gráfica amigable para el usuario donde se podrá desplegar la simulación y
verificación del objetivo del proyecto.
La interfaz abarca cinco etapas, cada una con una función específica. La etapa de
codificación toma la señal de información ingresada por el usuario y la codifica. La
etapa de modulación acopla a la información codificada para su transmisión por un
canal. La etapa de generación de ruido, altera la información dentro del canal para
generar errores aleatorios antes de su llegada al receptor. La etapa de
demodulación recupera la información codificada con errores. Finalmente la etapa
de decodificación detecta errores y los corrige para entregar al usuario la palabra
original.
xxii
PRESENTACIÓN
El desarrollo del Proyecto, es presentado en cuatro capítulos, como se explica a
continuación:
En el Capítulo 1 se describe los conocimientos teóricos pertinentes al estudio de la
norma de ISDB-Tb. Bases del código RS (FEC, BCH, Cíclicos y códigos de bloque).
Además un estudio general de la modulación OFDM y de los tipos de ruido y
desvanecimientos en el canal. Se presenta un ejemplo de codificación y
decodificación Reed-Solomon (15,9).
En el Capítulo 2 se describe el funcionamiento del codificador y decodificador Reed-
Solomon (204,188). También se describe el desarrollo de los correspondientes
Scripts para los bloques de codificación Reed-Solomon, modulación, generador de
ruido, demodulación y decodificación Reed-Solomon y se presentara las pruebas
de la simulación, con sus respectivos resultados y el análisis de los mismos. Se
analiza la eficiencia del algoritmo.
En el Capítulo 3 se presenta las características de la tarjeta FPGA a utilizarse, una
introducción al lenguaje VHDL y el procedimiento para el diseño en dichas tarjetas.
Se describe el proceso de transformación de un algoritmo en Matlab a VHDL del
codificador y decodificador Reed-Solomon (204,188). Además se describirán y
realizarán las pruebas.
En el Capítulo 4 se presenta las conclusiones obtenidas en el desarrollo del
proyecto y las recomendaciones relacionadas con la implementación del algoritmo.
Finalmente se incluyen anexos correspondientes a los códigos fuente desarrollados
en “Matlab” e “Ise Design Suite” de Xilinx para la tarjeta FPGA y el paquete de
instalación de comunicación serial para Matlab.
1
CAPÍTULO 1
FUNDAMENTOS TEÓRICOS
1.1 INTRODUCCIÓN A LA TELEVISIÓN DIGITAL TERRESTRE
ISDB-Tb [1][2]
ISDB-T (Integrated Services for Digital Broadcasting - Terrestrial) [1] es originaria
de Japón, desarrollada a partir de la década de 1990, periodo en el cual ya existían
los estándares ATSC1 y DVB-T2, norteamericanos y europeos respectivamente.
Gracias a esto su desarrollo parte con una ventaja clara sobre los estándares ya
existentes debido a que su estructuración nace de las debilidades y fortalezas
presentadas por sus antecesores. En 1999 se lo lanza como el estándar Japonés
de Televisión digital terrestre (TDT)3.
Después de 7 años Brasil decide adoptar el estándar Japonés como motor de
origen de un estándar propio, ya con mejoras y modificaciones como el empleo de
MPEG44 para la compresión de datos. Estos cambios se los realiza con una
estrecha colaboración de Japón. Posteriormente se lanza el estándar Brasileño
ISDB-Tb (Integrated Services for Digital Broadcasting – Terrestrial con
modificaciones brasileñas) [1].
El 29 de abril de 2009 ISDB-Tb fue certificado oficialmente por la Unión
Internacional de Telecomunicaciones (UIT) con su arquitectura de middleware
Ginga5, desarrollado como primera recomendación internacional para entornos
multimedia interactivos para TV Digital. En marzo de 2010 Ecuador adopta el
1 ATSC (Advanced Television Systems Committee): Comité de Sistemas de Televisión Avanzada, organización que se encarga del desarrollo de los estándares de televisión digital de Estados Unidos. 2 DVB-T (Digital Video Broadcasting-Terrestrial): Difusión de Video Digital Terrestre, estándar creado por la
organización europea Digital Video Broadcasting para transmisión de Tel evisión Digital Terrestre 3 TDT: Televisión Digital Terrestre 4 MPEG4 (Moving Picture Experts Group 4): Método de compresión de audio y video. 5 GINGA: Ginga es el nombre del middleware de la Recomendación ITU-T para servicios de IPTV y del
Sistema Nipo-Brasileño de TV Digital Terrestre (ISDB-TB).
2
estándar tecnológico japonés-brasileño para la aplicación de la Televisión Digital
Terrestre en el país de acuerdo a la Resolución N°. 084-05-CONATEL-2010. [1]
1.1.1 NORMA BRASILEÑA ABNT NBR [2]
La Asociación Brasileña de Normas Técnicas (ABNT) publicó el documento que se
encarga de atender los aspectos relativos a la transmisión en la norma de televisión
digital ISDB-Tb. La presente norma ofrece una perspectiva del tipo de información
que el sistema permite enviar, recibir y procesar por medio de sus bloques internos.
En la Figura 1.1 se indica el diagrama de bloques de los procesos embebidos en
televisión digital.
Figura 1.1 Visión general del sistema de transmisión de TV digital. [2]
1.1.1.1 Características Generales
Las características generales de la norma brasileña son:
· Transmisión de televisión fija, móvil y portátil.
· Transmisión simultánea de calidad de imagen en alta definición HDTV (high
definition television) y definición estándar SDTV (standard definition
television) dentro de una única banda.
· Introducción de interactividad por medio de la arquitectura de
implementación de referencia del middleware nombrada Ginga, que se
encuentra dividida en tres módulos Ginga-NCL (Nested Context Language),
Ginga-J (Java) y Ginga-CC (Common Core). [1]
3
· Sistema robusto contra inferencias (mejor respuesta contra el ruido
impulsivo6).
· Uso de redes de frecuencia única, no es necesario el paso por repetidores
de frecuencia para reproducir la misma señal, lo que representa un ahorro
en el espectro electromagnético.
· Uso de modulación OFDM (ortogonal frecuency division modulation) con
flexibilidad de modular las subportadoras en QPSK7, 16QAM8 y 64QAM9,
según sea la necesidad del sistema en el que se encuentra empleado.
· Aplicación de interliving (entrelazado en tiempo y frecuencia).
· Transmisión jerárquica (mejora el aprovechamiento del ancho de banda en
un mismo canal para transmisión de varios servicios).
· Compresión de audio y video en MPEG-210 y MPEG-4.
· Utiliza el canal de 6 MHz dividido en 13 segmentos.
· Para televisión móvil y portátil se utiliza un solo segmento denominado one-
seg11.
· Existen tres modos de transmisión (Modo 1, 2 y 3) que permiten distintos
números de portadoras (transmisión multiportadora).
· Utiliza un código de corrección de errores Reed-Solomon (RS) abreviado
(204,188).
En la Tabla 1.1 se detallan los principales parámetros utilizados en televisión
digital ISDB-Tb para la transmisión.
6 Ruido Impulsivo: Es el tipo de ruido cuya amplitud o intensidad aumenta bruscamente durante un impulso breve. 7 QPSK (Quadrature Phase Shift Keying): Modulación por desplazamiento de fase en cuadratura. 8 16QAM (Quadrature Amplitude Modulation): los datos se dividen en grupos de 4 bits. Las 16 posibles combinaciones varían la amplitud y la fase de la portadora, la cual por tal razón puede tomar 16 estados diferentes. 9 64QAM (Quadrature Amplitude Modulation): los datos se dividen en grupos de 8 bits. Las 64 posibles
combinaciones varían la amplitud y la fase de la portadora, la cual por tal razón puede tomar 64 estados diferentes. 10 MPEG-2: (Moving Picture Experts Group 2): Método de compresión de audio y video. 11One-seg: Servicio de transmisión de televisión digital terrestre y datos complementarios, diseñado para
ser captado en dispositivos móviles.
4
Tabla 1.1 Parámetros principales del sistema de transmisión. [2]
Parámetros Valores
1 Número de segmentos 13
2 Ancho del segmento 6.000/14 = 428,57 kHz
3 Banda UHF
5,575 MHz (modo 1)
5,573 MHz (modo 2)
5,572 MHz (modo 3)
4 Número de portadoras
1 405 (modo 1)
2.809 (modo 2)
5.617 (modo 3)
5 Método de modulación DQPSK, QPSK, 16-QAM, 64-QAM
6 Duración de los símbolos
activos
252μs (modo 1)
504μs (modo 2)
1.008μs (modo 3)
7 Separación de portadoras
Bws/108 = 3,968 kHz (modo 1)
Bws/216 = 1,984 kHz (modo 2)
Bws/432 = 0,992 kHz (modo 3)
8 Duración del intervalo de
guarda
1/4, 1/8, 1/16, 1/32 de la duración del símbolo
activo
63; 31,5; 15,75; 7,875μs (modo 1)
126; 63; 31,5; 15,75μs (modo 2)
252; 126; 63; 31,5μs (modo 3)
9 Duración total de los símbolos
315; 283,5; 267,75; 259,875μs (modo 1)
628; 565; 533,5; 51 7,75μs (modo 2)
1 260; 1 134; 1 071; 1 039,5μs (modo 3)
10 Duración del cuadro de
transmisión 204 símbolos OFDM
11 Codificación de canal
Código convolucional, tasa = 1/2 con 64
estados
Punzado12 para las tasas 2/3, 3/4, 5/6, 7/8
12 Punzado: Descarte de bit seleccionado, según un criterio definido, los valores de la salida del codificador
convolucional son convertidos en un flujo binario en serie.
5
12 Entrelazamiento interno
Entrelazamiento intra e inter-segmentos
(entrelazamiento en frecuencia)
Entrelazamiento convolucional con
profundidad de interleaving
0; 380; 760; 1.520 símbolos (modo 1)
0; 190; 380; 760 símbolos (modo 2),
0; 95; 190; 380 símbolos (modo 3)
Como puede observarse el estándar tiene una amplia gama de parámetros
configurables, lo que lo convierte en un sistema flexible y seguro que permite
adaptarse a distintas situaciones de transmisión según cómo sea configurado.
1.1.1.2 Codificación Externa [2]
Las señales de audio, video y datos ingresan al compresor MPEG, del cual se
derivan las salidas TS (Transport Stream), estas múltiples salidas alimentan al
remultiplexor el cual las transforma en un haz de transporte TSP (Transport Stream
Packet), señal ráfaga de 188 bytes. Se debe entonces obligatoriamente aplicar el
código Reed-Solomon para que el TSP resultante sea convertido en otro de longitud
de 204 bytes, consistiendo en 188 bytes de datos de programa y 16 bytes de
paridad. El flujo de bits ya no es llamado TSP sino BTS (Broadcast Transport
Stream).
En la figura 1.2 se presenta el diagrama de bloques de la transmisión del Transport
Stream Packet. Donde CAB representa a la cabecera de cada TSP seguido de la
carga útil y los respectivos bits de paridad.
Figura 1.2 Transmisión del TSP [2].
6
Debido al tamaño del TSP (204 bytes), un RS abreviado (204,188) se debe aplicar
obligatoriamente en cada TSP como un código externo. La codificación RS
abreviada (204,188) se debe generar agregando 51 bytes en el comienzo de la
entrada de los datos del código RS (255,239), y entonces después de aplicar la
codificación externa esos 51 bytes se deben remover obligatoriamente. El código
RS abreviado (204, 188) puede corregir hasta 8 bytes aleatorios erróneos entre los
204 bytes. La Figura 1.3 muestra el formato de datos TSP MPEG y el TSP protegido
por codificación RS
Figura 1.3 Formato de paquetes TSP MPEG y transmisión TSP. [2]
1.2 CODIFICACIÓN DE CORRECCIÓN DE ERRORES
1.2.1 DISTANCIA MÍNIMA DE UN CÓDIGO [3]
La distancia de un código hace referencia al número de bits diferentes entre dos
palabras del mismo tamaño.
La distancia mínima de un código de bloque lineal se define como la distancia más
pequeña entre cualquier par de palabras de código. Es decir la distancia mínima es
el peso del código, que refiere al número de 1s que tiene la palabra; y se transforma
en la medida mínima de la capacidad de detectar y corregir errores.
De esta manera un código que posee distancia mínima puede detectar un número
de errores igual a la distancia mínima menos uno pero puede corregir solamente la
mitad de los errores posibles detectados.
7
1.2.2 CÓDIGOS FEC [3]
Los códigos FEC (Forward error correction) como su nombre lo dice son códigos
utilizados para la detección y corrección de errores, sin necesidad de retransmisión
de la información original, debido a que su aplicación se la realiza en sistemas sin
retorno o sistemas en tiempo real.
La capacidad de corrección de errores se logra añadiendo un número de bits de
redundancia a la palabra original. De esta manera se forma la palabra código, la
cual se la envía al receptor donde por medio de los respectivos algoritmos para
corrección de errores se logra encontrar el error y determinar la palabra original.
Este tipo de códigos tiene como objetivo la corrección de errores, disminución de la
potencia de transmisión e incremento de la efectividad de los sistemas de
comunicación. Los tipos de codificación más usados son los códigos de bloque.
1.2.3 CÓDIGOS DE BLOQUE LINEAL [4][5]
Códigos de bloque consisten en técnicas para la transformación de un conjunto de
valores binarios $, en otro más largo %, en el cual se agregan bits de redundancia.
Los bits de redundancia que fueron aumentados corresponden a % & $,
denominados bits de redundancia. Este tipo de codificación no posee memoria y su
ventaja es que se pueden diseñar con una distancia mínima prefi jada y la
complejidad de la codificación crece linealmente con el aumento de n.
En la codificación se encuentra establecido un cierto número de combinaciones de
bits, a las cuales se les denomina palabras de código. Cuando se produce la
transmisión de datos al receptor, pueden suceder dos eventos, el primero que el
transmisor envíe una palabra código válida o que el transmisor envíe una palabra
código no válida. Cuando se tiene una palabra código no válida, el receptor solicita
al transmisor que vuelva a enviar la información a lo que se denomina ARQ
8
(Automatic Repeat reQuest), o a su vez el receptor recupera el bloque original por
medio de códigos FEC13.
El código bloque utiliza “suma módulo 2”14, de esta manera se puede formar una
palabra código por medio de dos palabras previas.
Una de las subclases de los códigos de bloque son los códigos cíclicos, que se
describen a continuación.
1.2.4 CÓDIGOS CÍCLICOS [4][5]
Los códigos cíclicos se caracterizan por su estructura matemática perfectamente
definida, gracias a lo cual se han desarrollado esquemas de decodificación muy
eficientes para ellos. Su ventaja sobre otros tipos de códigos es su facilidad de
codificar.
Para que un código binario sea cíclico debe cumplir las siguientes propiedades
fundamentales:
· Linealidad: la suma de dos palabras de información codificadas en el código
forman otra palabra de código.
· Cíclica: el desplazamiento cíclico de cualquier palabra de código también es
una palabra del código.
Es decir, si:
' = * ['+, '-, � , './0, './-] es una palabra código,
'1 = *3'./-,'+, '-,� , './04 también lo es.
13 FEC (Forward Error Correction): Corrección de errores hacia adelante, permite la corrección de un código en el receptor sin solicitar retransmisión 14 Suma módulo 2: Suma sobre números binarios donde no se toma en cuenta las unidades que se debe
llevar al siguiente nivel.
9
Con un polinomio binario es posible representar estos códigos, permitiendo realizar
la codificación y el cálculo del síndrome15 de manera eficiente. A cada palabra del
código de la forma:
' = ['+, '-, � , './0*, './-]
se puede representar con un polinomio:
'(5) = *'+* 6* '-5 6 7*6 *'./05./0 6*'./-*5./-*
que es el resultado de la multiplicación de cada una de las entradas de la palabra
código por un monomio16 5 8, donde 9 es la posición de dicha entrada en '. El
desplazamiento cíclico se consigue como el producto de '(5) por 5, tal que:
5'(5) = **'+5 6* '-50*6*'./0*5./-* 6*'./-*5.
1.2.5 CÓDIGOS BCH [4][5]
Los códigos BCH obtienen su nombre gracias a las siglas de sus tres autores: Bose,
Ray-Chandhuri y Hocquengheim. Estos códigos poseen una longitud17 y una
distancia18 designada. Es una clase importante de los códigos de bloque lineales.
Un tipo de códigos BCH son los códigos BCH binarios, los cuales se encuentran
caracterizados por los parámetros : que representan a cualesquier entero positivo
y ; que es menor que (2: & <)>2. Con estos parámetros se pueden detallar las
siguientes propiedades:
· Longitud de bloque %* = * 2? *& *<
15 Síndrome: resultado de la revisión de paridad en una palabra codificada. 16 Monomio: Expresión algebraica que consta de un solo término. 17 Longitud de un código: Número de símbolos que posee el código 18 Distancia de un código: Diferencia entre una palabra código válida y otra.
10
· Número de bits del mensaje $* @ *%* & *:; · Distancia mínima A:9%* @ *2;* 6 *<
Estos códigos pueden detectar y corregir hasta t errores aleatorios en cada palabra
código.
El estudio más detallado de la construcción de este tipo de códigos está más allá
del objetivo del presente proyecto.
1.3 REED-SOLOMON [4][5]
La codificación Reed-Solomon (RS) es un esquema de codificación de bloque que
puede detectar y corregir ráfagas de errores menores o iguales que ;19, determinado por la cantidad de redundancia con la que se ha diseñado el código.
Se lo utiliza no solo en transmisiones de televisión digital sino también en
numerosas aplicaciones como en reproductores de CD, telefonía móvil para la
transmisión de video en 3G con corrección de errores, sondas espaciales y
grabadoras digitales. Se tiene una gran complejidad en el proceso computacional,
pero este problema ha sido superado gracias a la implementación de circuitos
integrados en gran escala. Este tipo de código surge de una familia llamada códigos
de bloque, en que el codificador procesa un bloque de símbolos, a los que agrega
redundancia para generar otro bloque de una longitud mayor de símbolos
codificados. [4]
Los códigos Reed-Solomon son códigos FEC, no binarios, bloque lineal, cíclicos y
son una subclase de los códigos BCH. El código fue inventado por Irving S. Reed
y Gustave Solomon (de ahí su nombre) en el año de 1960. [5]
19 t: capacidad de corrección de errores de un código.
11
1.3.1 FUNDAMENTOS MATEMÁTICOS [6]
Se analizarán resumida y brevemente los principios matemáticos que hoy en día se
conoce con el nombre de álgebra abstracta. Dicha matemática estudia diversas
estructuras algebraicas como grupos, anillos, espacios vectoriales o campos que
fueron definidas debidamente en el siglo XIX. En esta área, los elementos
combinados por diversas operaciones no pueden ser interpretables como números,
ya que no es una simple ramificación de la aritmética. Este tipo de matemáticas
surgen de la necesidad de observar con nitidez lo intrínseco de las afirmaciones
lógicas en las que se basan todas las matemáticas y fueron motivadas por la
necesidad de más exactitud en las definiciones, ya que sirven también como hilo
unificador que entrelaza a casi todas las matemáticas. El álgebra abstracta fue
conocida en el siglo XX como álgebra moderna.
A continuación se explicarán conceptos básicos de la estructura algebraica utilizada
para la creación del código Reed-Solomon
1.3.1.1 Teoría de Conjuntos [6]
El término conjunto da una noción de un objeto primitivo, es decir, no se lo puede
definir o enunciar en función de otros términos más sencillos, causa por la cual la
noción intuitiva que se tiene de conjunto es un sinónimo de agrupación, colección,
clase, etc.
1.3.1.1.1 Definiciones utilizadas en la teoría de conjuntos [6]
· Igualdades de conjuntos
Un conjunto está totalmente determinado por sus elementos. Por ello, la igualdad
de conjuntos se establece como: Dos conjuntos son iguales si y solo si, tienen los
mismos elementos:
B = C
12
· Conjunto vacío
El conjunto que no contiene ningún elemento se llama el conjunto vacío y se denota
por D o simplemente {}. Existe un único conjunto vacío, ya que lo único que distingue
a un conjunto son sus elementos.
· Subconjuntos
El conjunto de B se dirá que es un subconjunto del conjunto C si todo elemento en
B es un elemento de C, B E CF
1.3.1.1.2 Operaciones con conjuntos
Dados dos conjuntos se pueden combinar para formar nuevos conjuntos. Se puede
usar el mismo procedimiento para cualquier número de conjuntos, ya sean finitos o
infinitos.
· Unión
La unión de los dos conjuntos B y C, escrita B* G C, es el conjunto:
{5|5 H B*I*5 H C}
Cuando se dice que*5 está en B o 5 está en C, se quiere decir que 5 está al menos
en uno de los dos B*I*C y puede ser que esté en ambos.
· Intersección
La intersección de los dos conjuntos B y C, escrita B JC, es el conjunto:
{5|5 H B*K*5 H C}
13
La intersección de B y C es el conjunto de todos los elementos que están en ambos
B y C.
· Diferencia
Dados dos conjuntos B y C, entonces el conjunto diferencia B &C es el conjunto:
{5 H B*|*5 L C}
Resulta eliminar de B cualquier elemento que esté en C.
· Complemento
Sea B un subconjunto cualquiera, escrita BM , de un conjunto referencial
N(universo). El complementario de B, es el subconjunto de N constituido por
aquellos elementos que no pertenecen a B.
BM = {5 H NB*|*5 L B} = N & B
· Diferencia simétrica
Dados dos subconjuntos B y C, escrita BOC, es el conjunto (B &C) G (C &B), con
todos los elementos que pertenecen, o bien a B, o bien a C, pero no a ambos a la
vez.
· Producto cartesiano
Sean {P, '* H B} y {Q, A* H C}, se dirá que los pares ordenados (P, Q) y (', A) son
iguales, que se escribe (P, Q) = * (', A), si y solo si P = ' y Q = A.
14
1.3.1.1.3 Propiedades de conjuntos
Sean B, C, R conjuntos cualesquiera, la relación de inclusión cumple con las
propiedades que se dan a continuación:
a. Asociativa : B G (C G R) = (BG C) G R
b. Conmutativa: B GC = C G B
c. Idempotencia: B* G B = B
d. Simplificativa: B G (C J B) = B
e. Distributiva: B G (C J R) = (BG C) J (B G R) f. Complemento: B* G B´ = N
g. Reflexiva: B E B
h. Transitiva: B E C y C E R entonces B* E R
i. Antisimétrica: si B E C y C E R entonces B = C
1.3.1.2 Teoría de Grupos [7][8]
El objeto algebraico conocido como grupo es un pilar fundamental de la gran
estructura que hoy se llama algebra abstracta.
Un conjunto G no vacío de elementos, se dice que forma un grupo si en G está
definida una operación binaria, llamada producto y denotada por (S) tal que:
a) P, Q* H ! implica que P S Q H !
b) P, Q, '* H ! implica que P S (Q S ') = (P S Q) S ' (ley asociativa)
c) Existe un elemento T* H ! tal que P S T = T S P = P para todo P H ! (existencia
de un elemento identidad en !).
d) Para todo P H ! existe un elemento P/- H ! tal que P S P/- = P/- S P = T (existencia de inversos en !).
Considerando la anterior definición, se puede afirmar que para todo conjunto no
vacío N, el conjunto ! sea un grupo.
15
Un grupo G se dice que es conmutativo si para cualesquiera P, Q* H ! se tiene: P SQ = Q S P. Si un grupo no cumple con dicha condición se llama no conmutativo.
Otra característica de un grupo !, es el número de elementos de que consta,
cuando este número es finito se dice que ! es un grupo finito. En tal caso si el
conjunto N contiene % elementos, entonces el grupo ! tiene % elementos.
1.3.1.2.1 Propiedades de los grupos
Si ! es un grupo entonces:
a) El elemento identidad de ! es único.
b) Todo P H ! tiene un inverso único en !.
c) Para todo P H !, (P/-)/- = P.
d) Para P,Q H !, (P S Q)/- = Q/- S P/-.
1.3.1.2.2 Subgrupos
Si U es un subgrupo de ! y V es un subgrupo de U, entonces V es un subgrupo de
!.
Para tener el criterio y poder decidir si un subconjunto dado de un grupo es un
subgrupo, podemos mencionar las siguientes propiedades:
Un subconjunto no vacío U del grupo ! es un subgrupo de ! si y sólo si:
a) P, Q H U implica que P S Q H U.
b) P H U implica que P/- H U.
1.3.1.2.3 Homomorfismo
El homomorfismo es la simplificación de un objeto real en un modelo cuyos
resultados se basan en términos probabilísticos. El objetivo del homomorfismo es
16
obtener resultados probables. Se puede decir que el homomorfismo se refiere a
que dos sistemas tienen una parte de su estructura igual.
1.3.1.2.4 Isomorfismo
Isomorfismo etimológicamente significa “igual forma”, por lo tanto se refiere a la
estructuración de sistemas similares al original
1.3.1.2.5 Automorfismo
Por automorfismo de un grupo ! se entenderá un isomorfismo de ! sobre sí mismo.
1.3.1.2.6 Permutaciones
Dentro de un grupo, la permutación hace referencia a la variación de la estructura,
orden y disposición de los elementos de éste.
1.3.1.3 Teoría de Anillos [7]
El concepto abstracto de anillos surge del conjunto de los enteros, a diferencia de
los grupos que tienen su origen en el conjunto de aplicaciones o permutaciones de
un conjunto sobre sí mismo. Un anillo es completamente diferente de un grupo, ya
que es un sistema bioperacional, en el que hay definidas dos operaciones: adición
y multiplicación.
Un conjunto no vacío W se dice que es un anillo asociativo, si en W están definidas
dos operaciones, denotadas por “6” y “S”, tales que para cualquiera P, Q, ' de W:
a) P 6 Q está en W.
b) P 6 Q = Q 6 PF c) (P 6 Q) 6 ' = P 6 (Q 6 '). d) Hay un elemento 0 en R tal que P 6 X = P (para todo P en W).
e) Existe un elemento &P en R tal que P 6 (&P) = XF
17
f) P S Q*TY;P*T%*WF g) P S (Q S ') = (P S Q) S '. h) P S (Q 6 ') = P S Q 6 P S ' y (Q 6 ') S P = Q S P 6 ' S P (las dos leyes
distributivas).
1.3.1.3.1 Anillos euclidianos
Un dominio entero W se dice que es un anillo euclidiano, si para todo P Z X*en W
está definido un entero no negativo A(P) tal que:
a) Para cualesquiera P, Q H W, ambos distintos de cero, A(P) \ A(PQ)F b) Para cualesquiera P, Q H W, ambos distintos de cero, existen ;, ^ H W tales
que P = ;Q 6 ^, donde ^ = X o A(^) _ A(Q)F
No se asigna valor alguno a A(X)F Los enteros sirven como un ejemplo de anillo
euclidiano, donde A(P) = valor absoluto de P, actúa como la función que la
definición requiere.
1.3.1.3.2 Anillos de polinomios
Se denomina anillo de polinomios en la variable indeterminada 5, y representando
por "[5], al conjunto de todos los polinomios de la forma P+ 6*P-5� F6*P.5., donde
% puede ser cualquier entero no negativo y donde los coeficientes P+, P-, P0, � , P.
están todos en ". Para que "[5] sea un anillo se debe cumplir que dos de sus
elementos sean iguales y debe ser posible sumarlos y multiplicarlos de forma que
los axiomas definitorios de un anillo se verifiquen en "[5]F
1.3.1.4 Teoría de Campos [7]
Un campo es un anillo conmutativo20, en el que se puede dividir sus elementos por
cualquier elemento distinto de cero.
20 Anil lo conmutativo: Un anillo donde la operación multiplicación es conmutativa.
18
Los campos han proporcionado una forma distinta de ver el álgebra, de tal manera
que son una parte importante en aplicaciones de la teoría de números. También es
aplicado en la teoría de ecuaciones que trata acerca de las raíces de polinomios.
Estas teorías están relacionadas a las ideas propuestas por el matemático francés
Evaristo Galois que han servido como inspiración y guía para el álgebra de la
actualidad.
1.3.1.4.1 Extensión de campos
La extensión de un campo es la relación de un campo con otro, sean " y ` campos;
se dice que ` es una extensión de ", si *` contiene a*"*; es decir, ` es una
extensión de ", si "* es un subcampo de `F
Se denota el grado de `*sobre " como [`a "]F Es de particular interés el caso en
que [` b "] es finito, es decir, el caso en que ` es de dimensión finita como espacio
vectorial sobre "F Esta situación se describe diciendo que ` es una extensión finita
de "F
Un elemento P H `,*se dice que es algebraico sobre ", si existen elementos
c+,c-,�,c. en ", no todos 0, tales que c+ P. 6*c- P./- 6*�6c.= XF*
1.3.1.4.2 Raíces de polinomios
Se tiene un polinomio d(5) en "[5], se necesita encontrar un campo extensión `
de " en el que d(5) tenga una raíz. El objetivo es generar y construir el campo `F*
Si d(5) H "[5] entonces un elemento P que se encuentra en algún campo extensión
de ", se llama raíz de*d(5) si*d(P) = XF
19
1.3.1.5 Teoría de los Campos de Galois [7]
La definición de dos operaciones conocidas como suma y multiplicación módulo
dos (e,f) dentro y fuera de un campo respectivamente y definiendo los siguientes
axiomas generan el Campo de Galois o extensión de un Anillo.
· Clausurativo. (g*x,y**h*i)a(xe y)* H i
· Asociativo. (g*x,y, z**h*i)a(xe y)e z = xe (y e z) * H i
· Existencia de neutro (o idéntico). *(j*k* H i)(g*x H i)ax e k = ke x = x · Existencia del inverso. (g*x H i)(j*l* H i)axe y = ye x = k · Conmutativo. (g*x H i)(j*y* H i)a xe y = y e x · Distributivo. (g*x,x, z H i)ax f (ye z) = (x f y) e (x f z)
Al evaluar los axiomas en el campo se puede dar dos opciones, la primera si el
campo (i,e) cumple con los axiomas conmutativo y existencia del neutro, se dice
que el campo es un anillo con elemento neutro y si el campo (i,e,f) es un anillo
conmutativo con elemento neutro y cumple con los axiomas de existencia de
inverso y de neutro respecto a la operación suma módulo 2, se dice que el campo
es un campo de Galois.
Dado un polinomio*d(5) en "[5], se asocia con d(5) un grupo al que se llamará
grupo de Galois de**d(5)F Las raíces de un polinomio tienen una estrecha relación
con su grupo de Galois. El grupo de Galois resultará ser un cierto grupo de
permutaciones de las raíces del polinomio.
El grupo de Galois de d(5) quedará definido como un cierto grupo de automorfismos
del campo de descomposición de d(5) sobre "F Los subgrupos del grupo de Galois
y los subcampos del campo de descomposición21, mantienen una dualidad que
expresa el teorema fundamental de la teoría de Galois.
21 Campo de descomposición: conjunto de raíces de un polinomio.
20
1.3.2 CONCEPTOS ALGEBRAICOS BÁSICOS [9][10]
1.3.2.1 Aritmética de Módulo 2
El presente estudio se basa en códigos binarios, en los cuales se utiliza un alfabeto
simple con dos símbolos 0 y 1. La codificación y decodificación en este tipo de
códigos envuelve operaciones de aritmética binaria de suma y multiplicación
módulo 2.
El signo a usarse en suma módulo 2 será el (+) en lugar del símbolo especial , el
uso de esta terminología evitará confusiones debido a que el proyecto se basa en
aritmética binaria.
La suma binaria módulo 2 se opera de la siguiente manera:
X* 6 *X* = *X!<* 6 *X* = *<!X* 6 *<* = *<!<* 6 *<* = *X!
Por la operación de suma módulo 2, se obtiene iguales resultados si < = &*<.
Es claro observar que la resta es igual que la adición en la aritmética binaria.
La resta módulo 2 se opera de la siguiente manera:
X & *X* = *X!< & *X* = *<!X & *<* = *<!< & *<* = *X!
La multiplicación módulo 2 se opera de la siguiente manera:
21
X* × *X* = *X!<* × *X* = *X!X* × *<* = *X!<* × *<* = *<!
La división es normal ya que se tiene:
<* ÷ *<* = *<!X* ÷ *<* = *X
!
No es permitida la división para 0.
Su correspondencia en la lógica binaria de la suma y la multiplicación módulo 2, es
la operación mW*noRUNpqrB y Bst*respectivamente.
1.3.2.2 Estructura Polinomial
Los polinomios permiten realizar cálculos y analizar resultados de modo práctico,
por estas facilidades muchas funciones importantes se aproxima con polinomios.
Polinomio se llama a una expresión de la forma:
d(5) = P+ 6P-5- 6P050 676 P./-5./- 6P.5.
P+ Z X
Si y sólo si %, % & <, % & 2, …, sean números positivos. El dominio de cualquier
polinomio es W = (−∞, ∞).
El polinomio d(5) se dice que se encuentra ordenado en forma decreciente con
relación a las potencias de 5, si d(5) se escribe como:
22
d(5) = P.5. 6 P./-5./- 6 P./05./0 676P-5 6 P+
A continuación se describe paso a paso el proceso de codificación y decodificación
Reed-Solomon.
1.3.3 CODIFICACIÓN Y DECODIFICACION DEL CÓDIGO REED-SOLOMON
[5][11][12][13] [14]
Para el entendimiento del proceso de codificación y decodificación del código RS
(204,188) utilizado en el estándar de televisión digital ISDB-Tb, se analizará un
código RS(15,9) debido a que el código original del estándar es muy amplio para
poder detallarlo por escrito. Con esto no se altera el presente estudio debido a que
la estructuración, características y proceso de dichos códigos son iguales y crecen
linealmente con el tamaño de procesamiento de información. El código RS(15,9)
facilitará la descripción del proceso y ayudará a la comprensión del lector.
El código trabaja con símbolos, los cuales se forman por grupos de bits en lugar de
bits individuales. Un símbolo es una secuencia de : bits individuales que aparecen
en serie y es erróneo cuando al menos un bit del símbolo tiene error. En este tipo
de codificación se establece una correspondencia entre el símbolo a codificar y un
elemento del campo de Galois.
En la codificación Reed-Solomon (RS) se usa la representación Wp(%, $)*que tiene
las siguientes características:
· : bits consecutivos agrupados forman un símbolo.
· $ símbolos de información en cada secuencia codificada.
· u símbolos de paridad en cada secuencia codificada.
· Longitud de la secuencia codificada, % = $ 6 u símbolos.
· % = 2? & <, donde 2? es el número total de símbolos en el campo de Galois
(!") con los que se forma la secuencia codificada.
· Corrige hasta t símbolos erróneos en la secuencia codificada, donde ; = u>2. · Distancia mínima*A?8. = 2; 6 < = % & $ 6 <.
23
La longitud de bloque del código RS es una unidad menor que el tamaño de un
símbolo de código, y la distancia mínima es mayor en uno que el número de
símbolos de verificación de paridad.
El !" es un campo finito y está formado por d elementos, en donde d siempre es
número primo, todos los campos finitos poseen característica prima. El campo
!"(d) se lo puede extender a un campo de*!"(d?) elementos, en donde : es
cualquier número entero positivo que tiene un valor mayor que 2. Para la
generación de códigos RS, los elementos del campo de Galois serán d = 2.
Los elementos del campo de Galois se representan con el X, <, v y los subsiguientes
se generan multiplicando el anterior por α, así la secuencia queda formada hasta el
elemento w por:
" = ~X, <, c, c0 , c�, � , c� �
También se puede representar los siguientes valores X,<, c como c/�.� , c+, c-
respectivamente:
" = ~c/�.� , c+ ,c-, c0, c�, � , c� �
Cada uno de los elementos del campo !", representan un símbolo. Dependiendo
del codificador RS que se va a crear, se establece el número finito de elementos,
obteniendo secuencias de 2? elementos.
!"(2?) = {X, <, c, c0, c�, � , c?/0}
Para cerrar la secuencia y dar un campo finito de elementos en GF(2m) se
establece:
c(0�/-)6< = X
24
Mediante la condición mencionada, cualquier elemento del campo que tenga una
potencia igual o mayor que 2? & < se puede transformar a un elemento con una
potencia menor que 2? &<:
c(0��.)=c(0�/-)c(.�-)=c(.�-)
De esta manera, una secuencia infinita F de elementos se puede reducir en una
secuencia finita F’ de la siguiente manera:
" = ~X, <, c, c0, � , c0�/0, c0�/- , c0� , c0��-, � �
"� = ~X, c+, c-, c0 ,� , c0�/0, c+ , c-, c0, � �
En el campo finito !"(2?) se tendrán, 2? elementos consolidados de la siguiente
manera:
!"(2?) = ~X, c+, c-, c0, � , c0�/0�
1.3.3.1 Polinomio Primitivo
Definimos un polinomio primitivo o no reducible como aquel que no se puede
factorizar en un producto de polinomios de menor grado.
Dado d(5) de grado m que cumple con el menor entero n, d(5) divide a 5. & < y
% = 2? & < donde : puede tomar cualquier valor entero positivo.
En la tabla 1.2 se incluyen los polinomios primitivos calculados hasta el grado 21.
Los polinomios primitivos se utilizan para la generación de los campos finitos de
Galois, estos últimos permiten la generación de los códigos RS.
25
Tabla 1.2 Polinomios primitivos de grado 2 a 21 [5].
d0(5) = 50 6 5 6 < d-0(5) = 5-0 6 5� 65# 6 5 6 <
d�(5) = 5� 6 5 6 < d-�(5) = 5-� 6 5# 65� 6 5 6 <
d#(5) = 5# 6 5 6 < d-#(5) = 5-# 6 5� 65� 6 5 6 <
d�(5) = 5� 6 50 6 < d-�(5) = 5-� 65 6 <
d�(5) = 5� 6 5 6 < d-�(5) = 5-� 6 5� 65� 6 50 6 <
d�(5) = 5� 6 5 6 < d-�(5) = 5-� 65� 6 < d�(5) = 5� 65# 6 5� 6 50 6< d-�(5) = 5-� 65� 6 <
d�(5) = 5� 6 5# 6 < d-�(5) = 5-� 6 5� 6 50 6 5 6 <
d-+(5) = 5-+ 65� 6 < d0+(5) = 50+ 6 5� 6<
d--(5) = 5-- 650 6 < d0-(5) = 50- 6 50 6<
1.3.3.2 Polinomio Generador
En general el polinomio 5. 6< y sus factores, son una parte importante en la
creación del código a ser estudiado. Sea �(5) un polinomio de grado % & $, que es
un factor de 5. 6 <.
Se constituye �(5) como:
�(5) = <6 � �8 *o8 6o./�./�/-
8�-************(�F�)
Donde el coeficiente �8 es igual a 0 o 1.
1.3.3.3 Ejemplo de Codificación RS(15,9)
Se desea codificar la secuencia 1111 0000 0000 1100 0000 0000 0000 0000 1000
empleando un código RS con $ = � símbolos de información, % = <� símbolos de
tamaño de palabra código,*: = � bits individuales en cada símbolo y capaz de
26
corregir ; = � errores. Para generar este código se emplean los campos de Galois
de orden 2#.
1.3.3.3.1 Calculo de los elementos del campo GF
Para el RS(15,9), el campo de Galios GF(2#) es el siguiente:
!"(2#) = {X, c+ , c-, c0, � , c-#}************(�F�)
Cualquier operación que se realice sobre un elemento genera otro elemento del
campo, de esta manera el campo tiene un tamaño finito. Para ello, para el ejemplo
RS(15,9) se emplea el polinomio primitivo de !" de orden 2#, obtenido del Tabla
1.2.
d(5) = < 6 5 6 5#************(�F�)
Donde el grado del polinomio es :* = *�. Con esto se obtiene 2# = <� elementos
en el campo definido por d(5). Se calculan las raíces de d(5), las cuales
corresponden a los valores de 5 que al ser evaluados dan como resultado d(5) =X. Los elementos binarios 1 y 0 no son raíces del polinomio, debido a que aplicando
la suma módulo 2, se tiene:
d(<) = < 6 <6 <# = <
d(X) = < 6 X6 X# = <
En álgebra, se establece que un polinomio de grado : debe tener : raíces. Por
tanto, para este ejemplo las raíces deben ser cuatro. Notoriamente surge un
conflicto, ya que las cuatro raíces no se encuentran en el mismo campo finito como
los coeficientes de d(5). Para esto se puede extender el campo !"(2#), ubicación
en la cual se encuentran el resto de raíces. Se define como una raíz del polinomio
d(5) a*c. Por lo tanto, es posible escribir lo siguiente:
d(c) = X <6c 6c#= X
27
c#= &<&c
Dado que en el campo binario 6<* = &< y c= &c debido a que c 6c= X, c# *se
puede representar como:
c#= &c# c#= <6c
c#*se expresa como una suma ponderada de c más términos que tienen órdenes
inferiores. De hecho todas las potencias de c*pueden ser expresadas de la misma
forma. Por ejemplo en c� se tiene:
c�=c#×c= (<6c) c=c 6c0
De la misma manera para los demás exponentes de c:
c�=c�×c= (c 6c0) c=c�6c0
c�=c�×c= (c�6c0) c=c#6c�= <6c 6c� c�=c�×c= (<6c 6c�) c=c 6c06c#= <6c 6<6c0= <6c0 c�=c�×c= (<6c0) c=c 6c� c-+=c�×c= (c 6c�) c=c06c#= <6c 6c0 c--=c-+×c= (<6c 6c0) c=c 6c06c�
c-0=c--×c= (c 6c06c�) c=c06c�6c#= <6c 6c06c�
c-�=c-0×c= (<6c 6c06c�) c=c 6c06c�6c#= <6c 6c 6c06c�= < 6c06c�
c-#=c-�×c= (< 6c06c�) c=c 6c�6c#= <6c 6c 6c�= < 6c�
Como se había explicado, se cierra la secuencia por medio de:
c(0�/-)6< = X
Además cualquier elemento que se encuentra fuera del campo de Galios !"(2#) es
igual a uno de los elementos del campo !"(2#) = {X, c+ , c-, c0, � , c-#} de la
siguiente manera:
28
c-�=c-#×c= (<6c�) c=c 6c#= <6c 6c= < =c+
c-�=c = c�- c0#=c� = c��
c-�=c0 = c�0 c0�=c-+ = c#+
c-�=c� = c�� c0�=c-- = c#-
c-�=c# = c�# c0�=c-0 = c#0
c0+=c� = c�� c0�=c-� = c#�
c0-=c� = c�� c0�=c-# = c##
c00=c� = c�� c�+= < = c#�
c0�=c� = c��
Esto quiere decir que la serie de elementos se repiten, entonces los 16 elementos
del campo finito de !"(2#) son:
{X, c+, c-,c0, c�, c#, c�, c� ,c�, c�, c�,c-+, c-- , c-0, c-�, c-#}
1.3.3.3.2 Operaciones entre los elementos del campo de Galois
Las operaciones entre los elementos del campo pueden ser sumas o
multiplicaciones módulo 2, con la característica de que al ser aplicadas entre 2
elementos, da como resultado un tercero del mismo campo. La multiplicación
módulo 2 se opera de la misma manera que una multiplicación aritmética normal.
En la tabla 1.3 se presenta la sumatoria módulo 2 de los valores que pueden tomar
cada, las cuales facilitan la realización de las operaciones de elementos de potencia
alta. Adicional se da una pequeña directriz de la utilización de la tabla y ejemplos
de sumatoria.
29
Ta
bla
1.3
Su
ma
mó
du
lo 2
.
X c+
c-
c0
c�
c#
c�
c�
c�
c�
c�
c-
+ c-
- c-
0 c-
� c-
# c+
X
c#
c�
c-#
c-
c-+
c-�
c�
c0
c�
c�
c-0
c--
c�
c�
c-
c#
X c�
c�
c+
c0
c-
- c-
# c-
+ c�
c�
c�
c-
� c-
0 c�
c0
c�
c�
X
c�
c-+
c-
c�
c-0
c+
c--
c#
c�
c�
c-#
c-�
c�
c-#
c�
c�
X c�
c-
- c0
c#
c-
� c-
c-
0 c�
c-
+ c�
c+
c#
c-
c+
c-
+ c�
X
c�
c-0
c�
c�
c-#
c0
c-�
c�
c--
c�
c�
c-+
c0
c-
c--
c�
X c�
c-
� c#
c�
c+
c�
c-
# c�
c-
0 c�
c-
� c-
- c�
c0
c-
0 c�
X
c-+
c-#
c�
c�
c-
c#
c+
c�
c�
c�
c-#
c-0
c#
c�
c-�
c-+
X c-
- c+
c�
c�
c0
c�
c-
c�
c0
c-
+ c+
c-
� c�
c#
c-
# c-
- X
c-0
c-
c�
c�
c�
c�
c�
c�
c�
c--
c-
c-#
c�
c�
c+
c-0
X c-
� c0
c�
c-
+ c#
c-
+ c�
c�
c#
c-
0 c0
c+
c�
c�
c-
c-
� X
c-#
c�
c�
c--
c--
c-0
c�
c�
c�
c-�
c�
c-
c�
c�
c0
c-#
X c+
c#
c-
+ c-
0 c-
- c-
� c�
c-
+ c�
c-
# c#
c0
c�
c�
c�
c+
X
c-
c�
c-�
c�
c-0
c-#
c�
c--
c�
c+
c�
c�
c-+
c�
c#
c-
X c0
c-
# c�
c�
c-
� c+
c�
c-
0 c�
c-
c�
c#
c-
- c-
+ c�
c0
X
Do
nde
:
X=c/
�.� ***************c
+ =<****************c-=v
Pa
ra la
util
iza
ció
n d
e l
a t
ab
la,
se d
eb
e b
usca
r lo
s e
lem
ent
os
a
su
ma
rse
e
n la
p
rim
era
fil
a
y la
p
rim
era
co
lum
na
re
spe
ctiv
am
ent
e,
lue
go
se
b
usca
rá
el
ele
me
nto
q
ue
se
pre
sent
a e
n e
l p
unto
de
cru
ce e
ntre
la
fila
y c
olu
mna
de
los
e
lem
ent
os
com
o e
jem
plo
te
nem
os:
Eje
mp
lo d
e s
uma
tori
a:
En
azu
l:
c�6c
� =c#
En
nara
nja
: c
� 6c-
# =c+
En
verd
e:
c06c
-+=c
#
30
1.3.3.3.3 Representación polinomial de los elementos GF
Para un mejor entendimiento del campo de Galois se presenta su estructura en
términos de 0s y 1s y de esta manera se relacionan los símbolos binarios (vectores)
con los elementos del campo GF.
En la tabla 1.4 se muestra las diferentes formas en las cual podemos representar
el campo i�(2#) generado por el polinomio primitivo correspondiente.
d(5) = <6 5 6 5#
Tabla 1.4 Campos de Galois ��(��). Forma Potencial Forma Polinomial Forma Vectorial
X X X*X*X*X c+ ******< <*X*X*X
c- ************c X*<*X*X
c0 *******************c0 X*X*<*X
c� ****************************c� X*X*X*<
c# *****<6c <*<*X*X
c� ***********c6c0 X*<*<*X
c� *******************c06c� X*X*<*<
c� *****<6c*********6c� <*<*X*<
c� <******** 6c0 <*X*<*X
c� ***********c*********6c� X*<*X*<
c-+ *****<6c 6c0 <*<*<*X
c-- ***********c6c0 6c� X*<*<*<
c-0 *****<6c 6c0 6c� <*<*<*<
c-� *****<******* 6c0 6c� <*X*<*<
c-# <******************6c� <*X*X*<
31
1.3.3.3.4 Cálculo del polinomio generador
El polinomio generador ayuda a encontrar los elementos de un campo de Galois
!"(2.) y para su construcción se deben tomar 2; raíces consecutivas de tal forma
que el polinomio generador representado por �(5) tiene la siguiente forma:
�(5) = (56c)(5 6c0)� (5 6c0� )************(�F�) �(5) = �+ 6�-5 6 �050 676�0�/-50�/- 6 50�
Entonces para el código RS(15,9), el polinomio es el siguiente:
�(5) = (56c)(5 6c0)(5 6c�)(5 6c#)(5 6c�)(5 6c�) �(5) = (506c� 5 6c�)(50 6c� 5 6c�)(50 6c� 5 6c--)
�(5) = (5#6c� 5� 6c� 50 6c� 5� 6c-0 506c-0 5 6c� 506c-+ 5 6c-+)(506c� 5 6c--) �(5) = (5#6c-� 5� 6c� 50 c� 5 6c-+)(506c� 5 6c--)
�(5) = 5� 6c� 5� 6c-- 5# 6c-� 5� 6c00 5# 6c0# 5� 6c� 5#6c-� 5� 6c-� 50 6c� 5�6c-0 5-06c-# 5 6c-+ 50 6c-� 5 6c0-
�(5) = 5�6c-+ 5� 6c-# 5# 6c# 5�6c� 50 6c� 5 6c� ************(�F�)
El polinomio encontrado es la clave para la codificación de la palabra de información
y se observa que el grado del polinomio generador es igual al número de símbolos
de paridad.
1.3.3.3.5 Cálculo de la palabra codificada
Para codificar la secuencia binaria 9 se seleccionan los bits de información de cuatro
en cuatro que constituyen los símbolos de la secuencia de información y se
construye el polinomio 9(5) transformando cuatro bits en un elemento de !"(2#) a
partir de su representación polinómica, lo que da como resultado:
secuencia binaria de información
9 = <<<<*XXXX*XXXX*<<XX*XXXX*XXXX*XXXX*XXXX*<XXX
32
secuencia de símbolos de información
9 = v-0 *X*X*v#*X*X*X*X*<, $ = �
polinomio de los símbolos de información
9(5) = v-0 6 X5- 6X50 6 v#5� 6 X5# 6X5� 6 X5� 6 X5� 6<5�
9(5) = v-0 6v#5� 6 5�
Al realizar la codificación RS es fundamental tomar en cuenta la estructura de la
palabra de información o mensaje 9(5) y de la paridad u(5).
%
Paridad u(5) Mensaje*9(5) v-0 0 0 v# 0 0 0 0 1
u = % & $ = 2; símbolos $ símbolos
Para realizar la codificación se requiere desplazar los coeficientes del mensaje en
% & $ posiciones:
9(5)F 50� = 9(5)F5� = (v-0 6v#5� 6 5�)5� = v-05� 6 v#5� 6 5-# = q(5)
Posteriormente se divide q(5) para �(5):
q(5)�(5) =
�(5)F50��(5) = �(5)F 5./�
�(5) = �(5)F5 �(5) ************(�F ¡)
El proceso indicado para el ejemplo RS(15,9) se muestra a continuación:
33
5-# **************************************************************6c
#5�*****************************6c
-05�
5�6c
-+5�6c
-#5#6c
#5�6c
�506c
�56
c�
5-#c-
+5-
�c-
#5-
0 ***c#
5-- ****c�
5-+ *c
�5�***c
�5�
5�6c
-+5�6c
-05�6c
-5�6c
�5#6c
�50
6c-#56
c�
********c
-+5-
�c-
#5-
0c#
5--c�
5-+ ***c�
5�*c
�5�
********c
-+5-
�c0
+5-
0c0
#5-
-c-
#5-
+c-
�5�c-
�5�
c-�5�
************************c
-05-
0c-
#5-
- **c�
5-+ ***c�
5�c-
05�c-
�5�c-
05�
***********************c
-05-
0c0
05-
- *c0�5-
+c-
�5�
c-�5�c0
-5�c-
�5�
*****************************************c-
5-- ****c�
5-+ **c-
#5�
c-+5�c-
-5�
c-+5�
*****************************************c-
5-- **c
--5-
+c-
�5�**c
�5�**c
�5�
c-+5�c�
5�
*********************************************************c
�5-
+ **c�
5�**c
+5�**c
�5�**************c�
5�
*********************************************************c
�5-
+c-
�5�c0
05�*c
-05�
c-#5�c-
�5�c-
#5#
***************************************************************************************c
�5�
* *c�5�*c
-#5�
c-05�c-
#5#
***************************************************************************************c
�5�
c-�5�**c
0�5�c-
�5�
c-�5#c-
�5�*c
-�50
***************************************************************************************************c
-#5�**c
�5�***c
-5�**c
�5#c-
�5�*c
-�50
***************************************************************************************************c
-#5�c0
#5�c0
�5�c-
�5#
c0+5�
c0�50
c0+5
*******************************************************************************************************************c�
5�c-
05�**************c-
-5�**c
050
c0+5
*******************************************************************************************************************c�
5�c-
�5�
c-�5#*c
�5�c-
-50c-
#5*c-
-
**c-
-5�**c
#5#*c
05�**c
�50c-
05*c-
-
34
Como residuo de la división se tiene:
u(5) =c--6c-0 5 6c� 50 6c0 5� 6c# 5# 6c-- 5�
La palabra codificada se encuentra expresada como:
r(5) = u(5)|q(5)************(�F¢) r(5) =c--6c-0 5 6c� 50 6c0 5� 6c# 5# 6c-- 5� 6c-0 5� 6c# 5�6 5-#
r = (c--c-0c�c0c#c-- *c-0 X*X c# X*X*X*X* c+)
La Palabra codificada con la representación !"(2#) es:
r =c-- *c-0 *c�*c0*c#*c-- | * c-0 X*X* c# X*X*X*X* c+
Finalmente la palabra codificada con la representación binaria:
|X<<<|<<<<|X<X<|XX<X|<<XX|X<<<|<<<<|XXXX|XXXX|<<XX|XXXX|XXXX|XXXX|XXXX|<XXX
Otra manera utilizada para el cálculo de la palabra codificada es el registro de
desplazamiento con realimentación lineal. El método de división será factible para
el cálculo de códigos pequeños, para el actual proyecto no será factible utilizarlo
debido a que un código (204, 188) presentaría un cálculo muy extenso. En la figura
1.4 se muestra el circuito de registro de desplazamiento con realimentación lineal
para el ejemplo a estudiar:
Figura 1.4 Circuito de registro de desplazamiento con realimentación lineal.
35
En la figura 1.4 se tiene el circuito LFSR (linear feedback shift register) de (n-k)
etapas para el ejemplo propuesto. El LFSR se implementa en función del polinomio
generador �(5), en donde los coeficientes de los multiplicadores son iguales a los
coeficientes del polinomio generador. Para el ejemplo se codifica en un formato
(15,9). Cada etapa contiene un símbolo de 4 bits. Las operaciones en el registro de
desplazamiento se hacen entre símbolos y no entre bits.
A continuación se presenta el procedimiento del circuito LFSR:
· El switch 1 da paso a los k símbolos de la información durante los k ciclos
del reloj, se observa el comportamiento de los estados del registro de
desplazamiento (n-k).
· El switch 2 debe permanecer en la posición inferior durante los primeros k
ciclos del reloj ya que la información original sin ser procesada sale del
circuito y son los primeros elementos de la palabra codificada.
· Después de que toda la palabra de información ha salido a través del switch
2, este cambia a la posición superior y el switch 1 impide el paso.
· Los siguientes (n-k) ciclos del reloj se desplazan los símbolos de paridad
hacia la salida desde el registro de desplazamiento,
· La secuencia de símbolos a la salida serán los del mensaje seguido por los
de paridad.
Después de los nueve primeros ciclos del reloj, el contenido del LFSR son los
símbolos de paridad:
!
c--,c#,c0,c� ,c-0,c--
Con cada pulso del reloj los símbolos contenidos en el LFSR se envían hacia la
salida, quedando nuevamente en X el LFSR.
En la tabla 1.5 se presentan los resultados del circuito de la figura 1.4:
36
Tabla 1.5 Codificación por medio de registro de desplazamiento con
realimentación lineal.
qs RU` SW1 SW1
SIMBOLO
SW2 PO P1 P2 P3 P4 P5 OUT
X X ON X 2 X X X X X X X
c+ < ON c+ 2 c� c� c� c# c-# c-+ c+ X 2 ON c-+ 2 c- c-0 c� c� c-# c-0 X
X � ON c-0 2 c� c-- c-+ c� c� c- X
X � ON c- 2 c� c-0 c� c+ c� c� X
X � ON c� 2 c-# c-0 c� c� c� c# X
c# � ON X 2 X c-# c-0 c� c� c� c# X £ ON c� 2 c+ c� c� c- c# c-# X
X ¤ ON c-# 2 c� c0 c-- X c-0 c-# X
c-0 � ON c� 2 c-- c-0 c� c0 c# c-- c-0 - <X OFF X < X c-- c-0 c� c0 c# c-- - << OFF X < X X c-- c-0 c� c0 c# - <2 OFF X < X X X c-- c-0 c� c0 - <� OFF X < X X X X c-- c-0 c� - <� OFF X < X X X X X c-- c-0 - <� OFF X < X X X X X X c--
1.3.3.4 Ejemplo de decodificación RS(15,9)
Para el ejemplo de la decodificación se insertan errores a la palabra codificada,
r = *c�6 *c-06*c�6*c06 *c#6c-6*c-06 X6 X6 *c#6 X6 X6 X6 *c�6c+ r = *c�*c-0*c�*c0*c#*c- * | c-0 X*X c# X*X*X c�*c+ |X<X<|<<<<|X<X<|XX<X|<<XX|X<XX|<<<<|XXXX|XXXX|<<XX|XXXX|XXXX|XXXX|X<<X|<XXX
1.3.3.4.1 Cálculo de los Síndromes
Al realizar la revisión de la paridad en la palabra codificada ¥(v) con o sin errores
recibida por el decodificador se tiene como resultado el valor del síndrome. Es decir
37
que se evaluará el polinomio con los % & $ símbolos de los cuales está conformado
el síndrome, en el caso a estudiarse tenemos un Wp(<�,�) con 6 símbolos en el
vector. Por lo tanto se tiene que el síndrome puede ser definido como:
p8 = ¥(5)|¦�c§***********9 = <, �** , % & $************(�F¨)
Si al evaluar el vector síndrome de la palabra recibida, el resultado es igual a cero,
dicha palabra será una palabra código válida, de otro modo al ser el resultado
diferente de cero, se tendrá una palabra de código con errores.
Se presenta el cálculo para el ejemplo.
Primero se evaluará la palabra código con los seis símbolos pertenecientes al
síndrome, es decir:
c,c0, c�*c#, c� *y** c�
Con la palabra codificada:
¥(5) =c�6c-0 5 6c� 50 6c0 5� 6c# 5# 6c- 5� 6c-0 5� 6c# 5� 6c� 5-� 65-#
Se comenzará evaluando en *c,
p- = ¥(c) p- =c�6c-�6c--6c�6c�6c�6c-�6c-�6c-�6c-# p- =c06c#6c� p- =c-+6c� p- =c-, primer síndrome,
Se evaluará en c0 , p0 = ¥(c0) p0 =c�6c-#6c-�6c�6c-06c--6c�6c�6c-6c-�
p0 =c�6c+6c-#
p0 =c-�6c-#
38
p0 =c0, segundo síndrome,
Se evaluará en c�, p� = ¥(c�) p� =c�6c+6c+6c--6c-6c-6c+6c-6c-#6c-0
p� =c06c#6c�
p� =c-+6c� p� =c+, tercer síndrome,
Se evaluará en c#, p# = ¥(c#) p# =c�6c-6c06c-#6c�6c�6c�6c-+6c-06c--
p# =c�6c-�6c+6c+ p# =c�6c-� p# =c�, cuarto síndrome,
Se evaluará en c�, p� = ¥(c�) p� =c�6c06c#6c06c�6c--6c-06c#6c-+6c-+
p� =c+, quinto síndrome y finalmente
Se evaluará en c� , p� = ¥(c�) p� =c�6c�6c�6c�6c-�6c-6c�6c-�6c�6c� p� =c�6c-+ p� =c-�, sexto síndrome.
Se tendrá el vector síndrome de la siguiente manera:
p8 = (c-, c0, c+, c�, c+, c-�)
39
El vector síndrome resultante es diferente de cero, por lo tanto la palabra código
que llegó al receptor posee errores.
Al evaluar la palabra código válida se obtiene:
¥(5) =c--6c-0 5 6c� 50 6c0 5� 6c# 5# 6c-- 5� 6c-0 5� 6c# 5� 65-#
N- = ¥(c) N- =c--6c-�6c--6c�6c�6c-�6c-�6c-�6c-#
N- =c�6c� 6c 6c�6c-# N- =c 6c
N- = X
N0 = ¥(c0) N0 =c--6c-#6c-�6c�6c-06c0-6c0#6c006c0�
N0 =c-+6c�6c�6c� N0 =c-�6c-�
N0 = X
N� = ¥(c�) N� =c--6c-�6c-�6c--6c0�6c�+6c�-6c#06c-�
N� =c--6 <6c-0
N� = < 6 <
N� = X
N# = ¥(c#) N# =c--6c-�6c-�6c-#6c0+6c�-6c��6c#+6c��
N# =c-�6c�6c-+ N# =c�6c� N# = X
N� = ¥(c�)
40
N� =c--6c-�6c-�6c-�6c0#6c��6c#06c#�6c�+
N� =c06c�6c-0 N� =c-06c-0= X
N� = ¥(c�) N� =c--6c-�6c0-6c0+6c0�6c#-6c#�6c��6c�#
N� =c�6c�6c� N� =c�6c� N� = X
Se tendrá el vector síndrome de la siguiente manera:
N8 = (X)
De esta manera se logrará demostrar que la palabra codificada que llegó al
receptor será válida sin errores.
1.3.3.4.2 Cálculo del Polinomio detector de error:
El algoritmo más eficiente para la decodificación de códigos bloque cíclicos binarios
es el algoritmo de Berlekamp-Masey, cuya complejidad crece linealmente con la
distancia mínima del código. Permitirá encontrar el polinomio localizador de errores,
siempre y cuando el número de errores producidos no supere la capacidad
correctora ; del código. Caso contrario el algoritmo producirá un polinomio que no
cumpla con las propiedades del polinomio localizador o un polinomio que cumpla
con estas propiedades pero incorrecto, en ambos casos la decodificación será
equivocada, siendo esta una limitante de Berlekamp-Masey.
El polinomio localizador de errores permitirá el cálculo de la ubicación exacta dentro
de la palabra que llega al receptor y tendrá la siguiente forma:
*©(5) = ©0�(5), de grado menor o igual que ;.
41
Berlekamp-Massey es un algoritmo iterativo que analizará los valores de los
síndromes de forma como se muestra en los siguientes pasos:
a) Calcular los síndromes p-,*** p0,�FFp0�
b) Inicializar *©+(5) = <, U = <, ª(5) = 5*K*$ = X
c) Calcular O�= p� 6« ¬8(�/-) Fp�/8®¯°8�- ************(�F±) d) Modificar ©(�)(5) = ©(�/-)(5)& O�ª(5)************(�F�²) e) Si 2U @ $, ir al paso f) caso contrario ir al paso g)
f) Igualar U = $ & U�& <*y ª(5) = ©(�/-)(5)>*O�, ir al paso h)************(�F��) g) Igualar U = U�&<************(�F��) h) Igualar ª(5) = 5ª(5)************(�F��) i) Si $ _ 2;,entonces $ = $ 6 <* e ir al Paso c)************(�F��)
Dónde:
Polinomio localizador de error ©(5) Polinomio: ©(5) = ©0�(5) ª�(5): Polinomio auxiliar, permite calcular ©(5) p� : Síndrome
O: Discrepancia entre síndromes
$: Iteraciones en curso
U: Complejidad lineal
La complejidad de un algoritmo tiene que ver con el número de operaciones
elementales necesarias el cual dependerá del número de datos de entrada que se
posean para resolver el problema dado.
Complejidad lineal corresponde al comportamiento de dicha complejidad en su
crecimiento disminución de forma lineal.
42
Para resumir el procedimiento Berlekamp-Massey se tiene a continuación el
diagrama de flujo de dicho algoritmo:
BERLEKAMP-MASEY
Inicialización de Variables
Calcular la
discrepancia
∆
Modificar polinomio Λ(x(
2L ≥ k
L = k - Lk – 1
T(x) = Λ(k-1) * Sk-i
T(x) = x T(x)
FIN
No
Si
L = Lk – 1
K<2t
T(x) = x T(x)
Λ(x(
No
Si
Figura 1.5 Berlekamp-Massey.
43
Para el ejemplo se calculará el polinomio localizador de error, se presentará la tabla
con los resultados de las iteraciones calculadas y posterior a este se presentará el
cálculo de cada una de las iteraciones con su respectiva explicación, la última fila
presenta el polinomio localizador de errores.
Tabla 1.6 Iteraciones del algoritmo Berlekamp-Massey.
³ µ³ ¶³(·) O³ ¸³ ¹³(·) X - < - X 5
< c- <6c- 5 c- < c-# 5
2! c0 <6c- 5 X < c-# 50 �! c+ <6c- 5 6c-� 50 c-# 2 c- 5 6c0 50 �! c� <6c� 5 6c� 50 c� 2 c- 50 6c0 5� �! c+ < 6c� 56c� 50 6c� 5� c� � c-+ 5 6c0 50 6c+ 5� �! c-� < 6c+ 56c� 50 6c- 5� c-# & &
Se detalla el procedimiento del cálculo siguiendo los pasos previamente descritos:
Valores iniciales:
$ = X,**********************©�(5) = <,****************U� = X*******************K******************ª�(5) = 5*
Primera Iteración
En el primer paso se toma $ = < y se calcula la discrepancia O-
O�= p� 6 � ¬8 (�/-) F p�/8®¯°
8�-
O-= p- 6 � ¬8(-/-) Fp-/8°¯°
8�-= p- 6�¬8(+) F p-/8
º
8�-
O-= v-
44
Usando los valores iniciales se calcula ©-(5)
©�(5) = ©�/-(5) 6 O� Fª�/-(5) ©-(5) = ©-/-(5) 6 O-Fª-/-(5) = ©+(5) 6 v-5 = <6 v-5
Se verifica el cumplimiento de la siguiente condición
2U�/- @ $
2U-/- @ $
2U+ @ $
2 × X @ < NO
Entonces se calcula el siguiente U-
U� = $ & U�/- U- = < & U-/- = < & U+ = <& X = <
Y el primer polinomio auxiliar
ª�(5) = ©�/-(5)O�
ª-(5) = ©-/-(5)O- = ©+(5)
O- = <v- = v-# **»** <v- = ¼*****v-v-# = v-� = <
ª�(5) = 5F ª-(5) ª-(5) = * v-#5
Calculo de número de iteración
$ _ 2; < _ �*********************$ = $ 6 < = <6 <
$ = 2
45
Segunda Iteración
Se toma $ = 2 y se calcula la discrepancia O0
O0= p0 6 � ¬8(0/-) Fp0/8½¯°
8�-=c06¬8(-)p- =c06c-c-
O0= v0 6 v0 = v/8.� = X
Utilizando ©-**K***ª- se calcula ©0(5)!
©0(5) = ©0/-(5) 6 O0F ª0/-(5) = <6 v-5 6 X(c-# 5) = < 6v-5
Se evalúa la condición
2U�/- @ $
2U0/- @ $
2U- @ 2
2 × < @ 2 SI
En este caso
U� = U�/- U0 = U0/- = U- = <
Y el segundo polinomio auxiliar
ª�(5) = 5F ª�/-(5) ª0(5) = *v-#50
Calculo de número de iteración
46
$ _ 2; 2 _ �*********************$ = $ 6 < = 26 <
$ = �
Tercera Iteración
Se toma $ = � y se calcula la discrepancia O�
O�= p� 6 � ¬8(�/-) Fp�/8¾¯°
8�-= p� 6 ¬8(0)p0 =c+6c-c0
O0= v+ 6 v� = v-#
Utilizando ©0**K***ª0 se calcula ©�(5)
©�(5) = ©�/-(5) 6 O�F ª�/-(5) = <6 v-5 6c-#c-# 50 = < 6v-5 6c-� 50
Se evalúa la condición
2U�/- @ $
2U�/- @ �
2 × < @ � NO
En este caso
U� = $ & U�/- U� = �& U�/- = �& U0 = � & < = 2
Y el tercer polinomio auxiliar
ª�(5) = ©�/-(5)O� = ©0(5)
O� = <6c- 5v-# = v- 6v05****
ª�(5) = 5F ª�(5)
47
ª�(5) = *5(v- 6c0 5) = (5v- 6c0 50)
Calculo de número de iteración
$ _ 2; � _ �*********************$ = $ 6 < = �6 < = �
$ = �
Cuarta Iteración
Se toma $ = � y se calcula la discrepancia O#
O#= p# 6 � ¬8(#/-) Fp#/8¿¯°
8�-= p# 6 ¬-(�)p� 6¬0(�)p� =c�6c-c+6c-�c0
O#=c�
Utilizando ©�**K***ª� se calcula ©#(5)
©#(5) = ©#/-(5) 6 O#F ª#/-(5) = <6 v-5 6c-� 50 6c� 5 6c� 50 = < 6c-- 5 6c� 50
Se evalúa la condición
2U�/- @ $
2U#/- @ �
2 × 2 @ � SI
En este caso
U� = U�/- U# = U#/- = U� = 2
48
Y el cuarto polinomio auxiliar
ª�(5) = 5F ª�/-(5) ª#(5) = *v-50 6v05�
Calculo de número de iteración
$ _ 2; � _ �********************* $ = �
Quinta Iteración
Se toma $ = � y se calcula la discrepancia O�
O�= p� 6 � ¬8(�/-) Fp�/8À¯°
8�-=c+6¬-(#)p# 6 ¬0(#)p� =c+6c--c� 6c�c+
O�=c+6c# 6c�= v0
Utilizando ©#**K***ª# se calcula ©�(5)
©�(5) = ©�/-(5) 6 O�F ª�/-(5) = <6 v--5 6 v�50 6c0 (c- 50 6c0 5�) = < 6v--5 6 v�50 6c� 50 6c# 5� = < 6c-- 5 6 v--50 6c# 5�
Se evalúa la condición
2U�/- @ $
2U�/- @ �
2 × 2 @ � NO
En este caso
49
U� = $ & U�/- U� = �& U�/- = �& U# = � & 2 = �
Y el quinto polinomio auxiliar
ª�(5) = ©�/-(5)O� = <6c-- 5 6c� 50
v0 = v-� 6v�5 6c� 50****
ª�(5) = 5F ª�(5) ª�(5) = *5(v-� 6c� 5 6c� 50) = v-�5 6c� 50 6c� 5�
Calculo de número de iteración
$ _ 2; � _ �*********************$ = $ 6 < = �6 < = �
$ = �
Sexta Iteración
Se toma $ = � y se calcula la discrepancia O�
O�= p� 6 � ¬8(�/-) Fp�/8Á¯°
8�-= p� 6 ¬-(�)p� 6¬0(�)p# 6¬�(�)p� =c-�6c--6c#6c#
O�=c#
Utilizando ©�**K***ª� se calcula ©0(5)
©�(5) = ©�/-(5) 6 O�F ª�/-(5)= < 6 v--5 6 v--50 6c# 5� 6c# (c-� 5 6c� 50 6c� 5�)
= < 6c� 5 6c# 50 6c� 5�
Donde se tiene como resultado
50
©(5) = <6c� 5 6c# 50 6c� 5�
como el polinomio localizador de error
Ya encontrado este polinomio es necesario factorizarlo para así determinar las
ubicaciones del error, para esto procedemos a evaluarlo verificando uno a uno si
cada elemento c� sobre el cual se evalúa, es raíz del polinomio ©(5). Este tipo de
factorización a usar para encontrar las raíces se la denomina búsqueda de Chien y
se detalla a continuación.
©(c+) = <6c�6c#6c� ©(c+) = <6c� 6c 6c#6c�= X* Â WBqÃ
©(c-) = <6c-+6c�6c� ©(c-) = <6c 6c0=c�*Z X
©(c0) = <6c--6c�6c�
©(c0) = X Â WBqÃ
©(c�) = <6c-06c-+6c-0 ©(c�) = <6c-+=c�*Z X
©(c#) = <6c-�6c-06c+ ©(c#) = <6c-06c-0=c-*Z X
©(c�) = <6c-#6c-#6c-� ©(c�) = <6c�=c-#*Z X
©(c�) = <6c-�6c-�6c0-
©(c�) =c-6c�=c-- *Z X
©(c�) = <6c-�6c-�6c0#
51
©(c�) = <6c-6c�6c�=c+*Z X
©(c�) = <6c-�6c0+6c0�
©(c�) = <6c06c�6c-0=c�*Z X
©(c�) = <6c-�6c006c�+
©(c�) = <6c�6c�6c+=c# *Z X
©(c-+) = < 6c-�6c0#6c��
©(c-+) = < 6c#6c� 6c�= X* Â WBqÃ
©(c--) = < 6c0+6c0�6c��
©(c--) = < 6c�6c--6c�=c�*Z X
©(c-0) = < 6c0-6c0�6c��
©(c-0) = < 6c�6c-�6c�=c�*Z X
©(c-�) = < 6c006c�+6c#0
©(c-�) =c�6c-0=c0*Z X
©(c-#) = < 6c0�6c�06c#�
©(c-#) =c�6c0=c+*Z X
Con estos resultados se puede concluir que las raíces de ©(5) son:
c+, c0 K* c-+
La ubicación de los errores serán los correspondientes a los recíprocos de las
raíces calculadas.
Los recíprocos de las raíces seguirán la siguiente regla detallada a continuación:
52
α0
α1
α2
α3
α4
α5
α6
α7
α8
α9
α10
α11
α12
α13
α14
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
x14
RAÍCES POSICIONES
α0
α1
α2
α3
α4
α5
α6
α7
α8
α9
α10
α11
α12
α13
α14
x0
x5
x13
RAÍCES POSICIONES
Figura 1.6 Recíprocos de raíces y correspondiente posición.
En el segundo diagrama en azul se puede observar los recíprocos entre las raíces
y su correspondiente posición, es decir que si se tiene como resultado la raíz c+, su correspondiente será la misma raíz y su posición 5+; si se tiene c0, su
correspondiente será c-� y su posición 5-�; y si se tiene c-+ su correspondiente es
c� y su posición 5�, como se puede ver en el diagrama en rojo el cual pertenece al
ejemplo a estudiarse en este proyecto.
Por lo tanto las posiciones de los errores son:
5+,5�*K*5-�
53
Para determinar los valores de los errores se definirá el polinomio evaluador de
errores ¼(5), en la forma
¼(5) = p(5) × ©(5)************(�F��)
Donde p(5) es el polinomio de síndromes a utilizarse
p(5) = p-5 6 p050 676 p�5 �
El polinomio ¼(5)*relaciona la ubicación y magnitud del error
¼(5) = < 6 (p- 6©-)5 6 (p0 6 ©-p- 6©0)50 6 76 (p� 6©-p�/- 6 76©�)5 � ¼(5) = < 6 (p- 6©-)5 6 (p0 6 ©-p- 6©0)50 6 (p� 6©-p0 6©0p- 6©�)5� ¼(5) = < 6 (c-6c�)5 6 (c06c�c-6c#)50 6 (c+6c�c06c#c-6c�)5�
¼(5) = <6c� 5 6c/8.� 50 6c+ 5� = < 6c� 5 6 5�
Se emplea el algoritmo de Forney, dada las posiciones de los errores, para el
cálculo de la magnitud de estos (diferencia entre símbolo correcto y recibido) por
medio de la siguiente expresión:
T� =¼(c�/-)
Ä (< 6c8 F c�/-)8Å�************(�F �¡)
Donde:
c+=c+c�=c�c-�=c-�
T+ =<6c� Æ <c+Ç 6c/8.� Æ
<c+Ç
06c+ Æ <c+Ç
�
Æ< 6c�F <c+Ç Æ< 6c-� F<c+Ç
54
T+ =< 6c�6<
(< 6c�)(< 6c-�)
T+ =<6c�6 <c�c-+
T+ =c�c
T+ =c0 ********Â ******:P�%9;�A*T^^I^*dIY9'9ó%*X
T� =<6c� Æ <c�Ç 6c+ Æ
<c�Ç
�
Æ< 6c+F <c�ÇÆ< 6c-�F <c�Ç
T� =<6c�c-+6 <
(< 6c-+)(< 6c�)
T� =c-�c�c0
T� =c-�c�
T� =c� ********Â ******:P�%9;�A*T^^I^*dIY9'9ó%*�
T-� =< 6c� Æ <
c-�Ç 6c+ Æ<c-�Ç
�
Æ< 6c+F <c-�Ç Æ< 6c�F <c-�Ç
T-� =<6c�6c+c�(< 6c0)(< 6c�)
T-� =c-+ 6c�c�6c�
T-� =c�c0
T-� =c�********Â ******:P�%9;�A*T^^I^*dIY9'9ó%*<�
Una vez calculada la magnitud del error se calcula el polinomio
T(5) = T+ 6 T�5� 6 T-�5-� T(5) =c06c� 5� 6c� 5-�
55
Como paso final de la decodificación y para obtener la palabra código transmitida
se realizará la diferencia entre la palabra recibida ^(5) y el error T(5).
r(5) = ¥(5) 6 T(5)************(�F�¢)
r(5) =c�6c-0 5 6c� 50 6c0 5� 6c# 5# 6c- 5� 6c-0 5� 6c# 5�6c� 5-� 6 5-#6c06c� 5� 6c� 5-�
r(5) =c--6c-0 5 6c� 50 6c0 5� 6c# 5# 6c-- 5� 6c-0 5� 6c# 5� 6 5-#
La palabra de información serán los últimos nueve símbolos de la palabra
codificada retirando los seis símbolos del inicio pertenecientes a la paridad y
desplazándolos las seis ubicaciones hacia atrás que se aumentaron al iniciar el
proceso.
9(5) = v-0 6 X5- 6X50 6 v#5� 6 X5# 6X5� 6 X5� 6 X5� 6<5�
9(5) = v-0 6v#5� 6 5�
1.3.3.5 Parámetros iniciales para el cálculo del código RS abreviado (204,188)
La codificación abreviada se debe generar agregando 51 bytes en el comienzo de
la entrada de los datos obteniendo un código RS(255,239).
Para este codificador se debe utilizar el campo de Galios:
!"(2�)************(�F�¨)
Polinomio primitivo d(5):
d(5) = 5� 6 5# 6 5� 6 50 6 <************(�F�±)
56
Polinomio generador �(5):
�(5) = (56c)(56c0)(56c�)� F F (5 6c-�)****** ****(�F�²)
Al final de la decodificación se deberá remover los 51 bytes agregados al inicio del
codificador.
1.4 MODULACIÓN
Para la transmisión de la señal codificada se podrá utilizar varios tipos de
modulación como son QPSK, 16QAM y 64QAM seguido de OFDM en modo 1,
modo 2 o modo 3 según se detalla en la norma de televisión digital utilizada como
base para el presente estudio. El objetivo del proyecto es analizar a detalle la
codificación por lo cual se escogerá la modulación QPSK seguido de OFDM para
simular un la transmisión de la señal por un canal. [1]
1.4.1 QPSK [15][16][17]
QPSK (Quadrature Phase-Shift Keying) o modulación por desplazamiento de fase
cuadrafásica, conocido también como 4QAM se encuentra representada en el
diagrama de constelación por cuatro puntos equidistantes del origen de
coordenadas como se observa en la figura 1.5.
Figura 1.7 Diagrama de constelaciones modulación QPSK.
57
Este tipo de modulación permite variar la fase de una onda portadora, de frecuencia
y amplitud fija, por medio de la aplicación de una señal digital. Posee cuatro fases
lo que le permite cambiar la fase de la onda portadora entre cuatro estados
correspondientes a 0, 90, 180 y 270 grados de la posición dentro de la forma de
onda.
QPSK toma los datos de la señal en pares de bits consecutivos tomando a cada bit
como un cambio de fase con respecto al elemento de la señal anterior.
Las ventajas de este tipo de modulación son:
· Alta inmunidad al ruido,
· Procesamiento sencillo y
· Alta seguridad de los datos.
1.4.2 OFDM [18][19][20]
OFDM (Orthogonal Frecuency Division Multiplexing) denominado también
modulación por multitono discreto (DMT), se basa en enviar la información
modulando en QAM (Quadrature Amplitude Modulation) o en PSK (Phase Shift
Keying) un conjunto de portadoras de frecuencias diferentes.
Esta modulación se la realiza después de que la señal haya pasado por un
codificador, a esto se denomina COFDM (Coded OFDM). En el presente estudio el
codificador a ser estudiado es el Reed-Solomon previamente explicado. Con esto,
se transporta la información protegida de errores.
La modulación OFDM presenta problemas por su gran número de subportadoras,
debido a que su generación y detección en tiempo continuo resultan difíciles de
realizarlas, por tal razón los procesos de modulación y demodulación se las realiza
en tiempo discreto mediante la Transformada Inversa de Fourier Discreta (IDFT) y
la Transformada de Fourier Discreta (DFT) respectivamente.
58
Una señal en tiempo discreto es la función de una variable independiente entera en
valores discretos y no se encuentra definida para instantes entre dos muestras
sucesivas. Para valores no enteros la señal simplemente no se encuentra definida.
Este tipo de modulación, OFDM, posee características favorables para que las
distintas señales que presentan retardos y amplitudes diferentes en el transmisor,
lleguen al receptor contribuyendo positivamente. Un ejemplo claro de esto son la
creación de redes de radiofrecuencia sin tener interferencias entre cada una de
ellas.
La modulación OFDM permite corregir y superar problemas de la propagación
multitrayectoria, este tipo de propagación detalla que entre el receptor y transmisor
existen varias trayectorias, esto se resume expresando que al receptor llegan varias
réplicas de la misma señal con diferentes retardos entre ellas. Principalmente las
tres o cuatro señales que llegan poseen potencia significativa, las restantes poseen
baja potencia y se las puede despreciar.
OFDM envía la información sobre un multiplexor de varias portadoras separadas
entre sí adecuadamente en frecuencia, repartiendo en cada una de ellas la
información. El espaciamiento adecuado más conocido como ortogonalidad es la
característica que diferencia a éste método de otros, este espaciamiento será
siempre el mismo y corresponde al inverso del período de símbolo. Una señal
OFDM se expresa como:
Y(;) = � A8 *T5d Èw*2É ÊËM 69ªÌÍ
Î0/-
8�/Î0
************(�F��)
Donde:
T5dÏw*2É ÆËM 6 8ÐÇÑ es la representación exponencial de una señal sinusoidal
59
s número de portadoras
ËM frecuencia central
ª período de símbolo
A8 símbolo con información
Y(;) señal OFDM en el tiempo 8Ð espaciamiento entre portadoras
La ortogonalidad usada en este tipo de modulación genera un ahorro de espectro
como se muestra en la figura 1.6:
Figura 1.8 Multiportadora convencional frente a portadoras ortogonales [19].
OFDM presenta aparte del ahorro de espectro, una menor distorsión multitrayecto
esto lo logra agregando un intervalo de guarda en cada símbolo OFDM para
suprimir la interferencia intersímbolo (ISI). Actualmente no solo se usa en difusión
de señales de televisión digital terrestre como ISDB-Tb sino también en telefonía
móvil.
En la siguiente figura se muestra la forma del espectro de una señal OFDM y el
espectro de una señal FDM.
60
Figura 1.9 Espectro de una señal OFDM vs FDM.
1.4.3 DIAGRAMA MODULACIÓN A UTILIZARSE EN LA SIMULACIÓN [21]
En el siguiente capítulo en la simulación del codificador y decodificador del código
Reed-Solomon (204,188), se emulará un canal por el cual se transmitirá la señal
codificada hasta el codificador. Dentro del canal se insertará ruido el cual producirá
errores en la palabra. Para que la transmisión se acerque a realidad se
implementará un modulador OFDM+QPSK.
En la figura 1.8 se presenta el diagrama de bloques del transmisor a implementarse.
Figura 1.10 Transmisor con modulación OFDM.
61
En la figura 1.9 se presenta el diagrama del receptor a implementarse.
Figura 1.11 Receptor con modulación ODFM.
1.5 RUIDO GAUSSIANO Y DESVANECIMIENTO [22][23][24]
1.5.1 RUIDO GAUSSIANO
Ruido Gaussiano o ruido blanco hace referencia a un proceso estocástico con
media22 nula, varianza23 constante y covarianza24 nula, es decir que corresponde a
una señal aleatoria caracterizada debido a que no existe correlación estadística
entre valores de señal en dos tiempos diferentes. Su densidad espectral de
potencia (PSD) es una constante. La señal contiene todas las frecuencias y todas
ellas muestran la misma potencia.
Este tipo de ruido en el eje del tiempo adquiere diferentes valores sin relación entre
ellos. Si la distribución es normal, se denomina Ruido Blanco Gaussiano.
En la siguiente figura se muestra el efecto que este tipo de ruido presenta en una
imagen.
22 Media: Proporciona información sobre la tendencia de los datos. 23 Varianza: Muestra la variación de un grupo de datos tomados. 24 Covarianza: medida de asociación que mide la relación lineal entre variables.
62
Figura 1.12 Ruido Gaussiano [23].
1.5.2 DESVANECIMIENTO DE UNA SEÑAL
El desvanecimiento de una señal se refiere a la atenuación de la señal debido a las
pérdidas en el espacio, obstáculos y resistencia con la que se encuentra durante
toda su trayectoria hasta llegar a su destino. El desvanecimiento presenta un
carácter probabilístico y se refleja en el destino o receptor como baja potencia o
mala potencia.
En la siguiente imagen se presenta el efecto del desvanecimiento de una señal,
Figura 1.13 Desvanecimiento de una Señal [22].
63
CAPÍTULO 2
SIMULACIÓN Y ANÁLISIS DEL DESEMPEÑO DEL
CODIFICADOR REED-SOLOMON UTILIZANDO MATLAB
2.1 PROCEDIMIENTO Y SOLUCIÓN
El objetivo del presente proyecto es desarrollar, analizar y simular el algoritmo del
codificador RS(204,188) en MATLAB. Con el propósito de generar una herramienta
sobre la cual se puedan analizar los resultados de manera rápida y eficiente. Para
dar solución a lo propuesto se ha optado como punto de partida, desarrollar el
algoritmo para un código más pequeño, que cumple con el mismo procedimiento
que el código a ser analizado. El algoritmo RS(15,9) posee dimensiones factibles
para el análisis matemático previo, debido a que al realizar manualmente los
cálculos correspondientes en papel, se observa que la dificultad aumenta
linealmente con la capacidad del código RS.
Previamente los cálculos del RS(15,9) se presentaron en el capítulo 1, tomados
como base para desarrollar los algoritmos y posterior adecuación al código
RS(204,188), desarrollados en su totalidad en el software Matlab con sus
respectivas herramientas de simulación, que a continuación se presentan.
En la siguiente figura se presenta el modelo simplificado del sistema de transmisión
que se utiliza para el análisis.
Figura 2.1 Sistema de Transmisión.
64
2.1.1 DIAGRAMAS DE FLUJO DE LOS PARÁMETROS INICIALES
Para el desarrollo del algoritmo se deben tomar en cuenta ciertos parámetros
necesarios para los cálculos, los cuales son: “polinomio primitivo”, “campos de
Galois”, “polinomio generador”, “suma de campos de Galois” y “tabla XOR”. Se
presentará para cada uno de los parámetros su diagrama de flujo correspondiente
a los scripts creados en MATLAB y cuyos códigos se encuentran en los anexos.
2.1.1.1 Generación del Polinomio Primitivo
Para la obtención del polinomio irreducible a utilizarse en el Codificador Reed-
Solomon, se debe tomar en cuenta que el tamaño del polinomio depende de la
longitud del símbolo a ser transmitido (m). En la herramienta se desarrolla el
algoritmo para generar el polinomio primitivo de grado 2 a 8, según sea el
requerimiento y se lo presentará en modo vectorial correspondiente a cada
polinomio presentado en la Tabla 1.2. La figura 2.2 presenta los pasos del algoritmo
para generar el polinomio primitivo, el cual se estudió en el capítulo 1 (numeral
1.3.3.1). El algoritmo se encuentra detallado en el Anexo A.
m=2 Poli=[1 1 1]
Poli=[1 1 0 1]
Poli=[1 1 0 0 1]
Poli=[1 0 1 0 0 1]
Poli=[1 1 0 0 0 0 1]
Poli=[1 0 0 1 0 0 0 1]
Poli=[1 0 1 1 1 0 0 0 1]
m=3
m=4
m=5
m=6
m=7
FIN
No
Si
Si
Si
Si
Si
Si
No
No
No
No
No
Polinomio_Primitivo (m) m: longitud de símboloPoli: polinomio primitivo
Figura 2.2 Algoritmo para la generación del Polinomio Primitivo.
65
2.1.1.2 Campo de Galois
Se presenta el procedimiento para la generación del conjunto de elementos del
campo de Galois en forma vectorial (Figura 2.3), con el cual se realizarán los
cálculos posteriores para la generación de la tabla 2.1 ingresando las variables m
y el polinomio primitivo.
Tabla 2.1 Elementos del campo de Galois.
Campo FINk≤q
Campo (m, poli_prim)
Campo=[0]qxmalfa_m=poli_prim(m)
q=2^mk=m+2
vec_k=[0 Campo(k-1,:)]
SiNo
Campo(k,:)=vec_k(1:m)k=k+1
vec_l=vec_k(1:m)+alfa_mvec_k(1:m)=mod(vec_1,2)
vec_k(m+1>0
Si
No
m: longitud de símbolopoli_prim: polinomio primitivoalfa_m: raices de polinomio primitivoq:símbolos de paridadk: contadorvec_k :vector de elementos de la matriz de campovec_l: raices del polinomio sumado al vector vec_kCampo: campo de galois GF(2^m)
Figura 2.3 Campo de Galois.
66
En el capítulo 1 se calculan manualmente los elementos del campo de Galois para
el ejemplo de codificador Reed-Solomon (15,9) en el numeral 1.3.3.3.1 los cuales
corresponden a los elementos calculados por el algoritmo y detallados en la tabla
2.1. El algoritmo se encuentra detallado en el Anexo B.
2.1.1.3 Operación de Suma GF
Se crea una matriz del campo de Galois, que posee 2? elementos, donde : es un
número entero entre 2 y 8 correspondiente al tamaño del símbolo a transmitir.
Cuando se manipula la operación Suma_GF al utilizar el operador suma XOR, se
trabaja en el campo de Galois que se ha especificado, considerando que se utiliza
el polinomio primitivo para definir el campo.
d
FIN
k<len_a
Suma_GF (a,b,c)
a=aT
b=bT
n_c=size(c,1)len_a=length(a)
tempo=mod(c(a+2,:)+c(b+2,:),2)K=1
f_1mod(c+2-ones(n_c,1)xtempo(k,:),2)f_2=sum(f_1T)
indi=find(f_2==0)d(k)=indi-2
n=k+1len_a=length(a)
tempo=mod(c(a+2,:)+c(b+2,:),2)k=1
indi=find(d<0)d(indi)=indi-infe=length(ind)
d=reshape(d,e,e)
Si
No
a: matriz de elementos [0 – (2 ̂m-1)]
b: tomará el valor de m (longitud de símbolo)c: tomará el valor de Poli (polinomio primitivo)n_c: tamaño de campolen_a: tamaño tabla_1Tempo: auxilair temporal de módulo a,b,ck: indicadorf_1mod: modulador operadorf_2: vector sumaindi: buscadorn: auxiliard: forma vectorial GFe: longitud de buscador
Figura 2.4 Suma GF.
67
En la figura 2.4 podemos observar los pasos de la función Suma GF la cual permitirá
calcular en forma vectorial el campo de Galois para diferentes códigos a
desarrollarse ya sea para la codificación RS (15,9) o RS (204,188), sino que podrá
ser utilizado para un sin número de algoritmos. En este proyecto esta función es
necesaria para el cálculo del algoritmo descrito en el figura 2.3. El algoritmo se
encuentra detallado en el Anexo B.
2.1.1.4 Operación XOR
Para facilitar el procedimiento matemático de la suma módulo 2 se genera la tabla
XOR. Este algoritmo permite obtener tablas de diferente tamaño según sea la
necesidad de cálculos en módulo 2.
tabla_xor
FIN
tabla_xor=Suma_GF(tabla_1,tabla_1T,campo)
Tabla_xor (m,campo)
vec=-1:2^(m-2)tabla_1=ones(2^m,1) x vec
m: longitud de símbolocampo: forma vectorial GFvec: [1x2^(m-2)]tabla_1: tabla de unos multiplicado por el vectabla_1T: transpuestatabla_xor: tabla suma XOR
Figura 2.5 Tabla XOR.
Como se explicó en el capítulo 1, los cálculos utilizados para el desarrollo del
codificador Reed-Solomon se utilizará matemática lógica. En el cálculo del ejemplo
desarrollado en dicho capítulo se elaboró la tabla 1.3 la cual permite elaborar de
forma sencilla y rápida suma módulo 2 para RS (15,9). Este algoritmo genera tablas
XOR, según sea el requerimiento del usuario, por ejemplo para el código RS (15,9)
se requerirá una tabla con 16 elementos mientras que para el RS (204,188) se
requerirá una tabla de 255 elementos. El algoritmo se encuentra detallado en el
Anexo B.
68
2.1.1.5 Establecimiento del Polinomio Generador
La figura 2.6 presenta el algoritmo que permitirá generar el polinomio generador de
grado 2 a 8, este polinomio es clave para la codificación de la información. El
resultado que genera este algoritmo será el polinomio generador en forma vectorial
correspondiente al cálculo realizado en el capítulo 1 (numeral 1.3.3.3.4). El
algoritmo se encuentra detallado en el Anexo B.
m=2 Polgen=[1 0]
Polgen=[3 1 0 3 0]
Polgen=[6 9 6 4 14 10 0]
Polgen=[1 30 9 1 19 23 22 3 0]
Polgen=[15 62 1 20 32 10 28 60 6 44 12 60 0]
Polgen=[10 5 66 82 91 117 62 83 66 68 32 72 31 7 108 0]
Polgen=[136 240 208 195 181 158 201 100 11 83 167 107 113 110 106 121 0]
m=3
m=4
m=5
m=6
m=7
FIN
No
Si
Si
Si
Si
Si
Si
No
No
No
No
No
Polinomio_Generador (m) m: longitud de símboloPolgen:Polnomio generador
Figura 2.6 Procedimiento para el establecimiento del Polinomio Generador.
2.1.1.6 Suma XOR
La representación de los elementos del campo de Galois se la puede realizar de
distintas formas, como se presenta en la tabla 2.1, cada una de estas
representaciones se utiliza en los cálculos. Para el cálculo del decodificador en
69
Matlab se usan los exponentes de la forma potencial (FP), los cuales están
detallados en la columna “FP Decodificador” en la Tabla 2.2. Para facilitar los
cálculos en el codificador, se usó la representación de la columna “FP+1
Codificador” en la Tabla 2.1. La representación vectorial binaria se la puede traducir
a una representación vectorial decimal (FV), como se indica en la columna “FV
Matlab” la cual se usa para los futuros cálculos dentro de la matemática de matlab.
En la figura 2.7 se presenta el procedimeinto para el cálculo de Suma XOR. Este
algoritmo utiliza la tabla XOR previamente generado y realiza la sumatoria de forma
automática según sea el requerimiento del usuario. El algoritmo se encuentra
detallado en el Anexo B.
Retornar s
FIN
Suma_XOR
aux1=FV(n1+1)aux2=FV(n2+1)
aux3=aux1+ aux2s=FP(aux3+1)
leer n1leer n2
n1: número 1n2: número 2
aux1: auxiliar 1aux2: auxiliar 2aux3: auxiliar 3
FV: Forma vectorial GF FP: forma potencial GFS: resultado de suma
Figura 2.7 Suma XOR.
70
Tabla 2.2 Campo de Galois – Matlab.
FP+1
CODIFICADOR
FP
DECODIFICADOR
FORMA
POTENCIAL FORMA POLINOMIAL
FORMA
VECTORIAL
FV
MATLAB
0 -1 a^-Inf 0 0 0 0 0
1 0 a^0 a^0 1 0 0 0 8
2 1 a^1 a^1 0 1 0 0 4
3 2 a^2 a^2 0 0 1 0 2
4 3 a^3 a^3 0 0 0 1 1
5 4 a^4 a^0 a^1 1 1 0 0 12
6 5 a^5 a^1 a^2 0 1 1 0 6
7 6 a^6 a^2 a^3 0 0 1 1 3
8 7 a^7 a^0 a^1 a^3 1 1 0 1 13
9 8 a^8 a^0 a^2 1 0 1 0 10
10 9 a^9 a^1 a^3 0 1 0 1 5
11 10 a^10 a^0 a^1 a^2 1 1 1 0 14
12 11 a^11 a^1 a^2 a^3 0 1 1 1 7
13 12 a^12 a^0 a^1 a^2 a^3 1 1 1 1 15
14 13 a^13 a^0 a^2 a^3 1 0 1 1 11
15 14 a^14 a^0 a^3 1 0 0 1 9
2.1.1.7 Operación de Redondeo
Esta función se creó para que los cálculos a realizarse den como resultados valores
dentro del campo de Galois ya que los campos son finitos, propiedad de GF, como
se detalla en el capítulo 1. El algoritmo se encuentra detallado en el Anexo C.
Retornar x FINx>n
Redondear (x)
x=x-n
Si
No
x: valor de entrada n: tamaó de la palabra codificada
Figura 2.8 Procedimiento de la operación de Redondeo.
71
2.1.2 DIAGRAMAS DE FLUJO DE LA CODIFICACIÓN
En esta sección se presentará los diagramas de flujo de los algoritmos
desarrollados para el funcionamiento de la codificación.
2.1.2.1 Codificador
Las figuras 2.9 y 2.10 presentan paso a paso el algoritmo utilizado para la
codificación, en el capítulo 1 se presentaron dos procedimientos para encontrar la
palabra codificada, el primero por medio de la división entre la información y el
polinomio generador y el segundo el circuito de registro de desplazamiento con
realimentación lineal (numeral 1.3.3.3.5). El algoritmo se basa en el circuito de
registro de desplazamiento y se encuentra detallado en los Anexos C y K.
u(nu)x>n
CodRS (u, polgen)
desp=polgen+u(nu)
No
Si
nu=length(u)
desp=[0]
desp=Redondear(desp)i=1
u: Entrada datospolgen: Polinomio Generadornu: Cantidad datosFV: Forma vectorial GFFP: Forma potencial GFPcod: Palabra codificadadesp: [1xpolgen]despx: [1xnpolgen]despla: [1xnpolgen-1]npolgen: Tanaño polgenL,i: Contadoressw: variable auxiliar 1x1
1
Figura 2.9 Codificador RS – parte 1.
72
FINi<nu-1 Pcod=[desp u]
sw=Suma_xor(desp(npolgen),u(nu-i))
sw=0
No
Sidespx=[o]
despx=polgen+sw
despx=Redondear(despx)L=1
L<npolgen-1desp=[despx(1) despla]
i=i+1
despla(L)=Suma_XOR(desx(i+1),desp(1))L=L+1
Si
No
Si
No
1
Figura 2.10 Codificador RS – parte 2.
2.1.3 DIAGRAMAS DE FLUJO DE TRANSMISIÓN
Como parte de la simulación se requiere emular un canal cercano a la realidad,
por tal razón se generará un grupo de algoritmos los cuales cumplirán la función
de modular, generar ruido y demodular con el fin de tener una señal en el receptor
lista para ser decodificada. A continuación se presentarán los diagramas de flujo
correspondientes a cada algoritmo.
2.1.3.1 Modulador
En la figura 2.11 se pueden observar los pasos correspondientes a la modulación
de la señal, se utilizará una modulación OFDM con QPSK permitida dentro de la
norma de televisión digital. El algoritmo toma la señal y la modula en QPSK como
primer paso, luego genera las subportadoras necesarias para transportar la señal
y modularla con OFDM, posteriormente con la ayuda de un conversor
73
digital/analógico se transforma la señal, como últimos pasos se utiliza un filtro pasa
bajos y se envía la señal ya modulada al canal. El algoritmo se encuentra detallado
en el Anexo L.
Modular(data) data: palabra codificadainfo: palabra modulada en QPSKcarriers: generador de subportadoras,IFFTu: conversor D/ALPF: filtro pasa bajossmod: señal modulada en OFDM +QPSK
smod
FIN
info=QPSKModulador(data)
u=ConversorDigitalAnalógico(carriers)
LPF=filtrar(u)
carriers=GenerarSubportadoras(info)
smod=Upconverter(u)
Figura 2.11 Modulador.
2.1.3.2 Generador de Ruido
Con la señal ya modulada y enviada hacia el canal se genera un algoritmo que
inserte ruido a la señal generando errores en la palabra. El ruido debe ser
controlado a través de parámetros como la potencia del ruido para que la señal
recibida posea un número de errores aceptables por el decodificador. El algoritmo
se encuentra detallado en el Anexo M.
Generar_Ruido(smod)smod: señal moduladasr: señal con ruido
sr
FIN
sr=AWGChannel(smod)
Figura 2.12 Generador de Ruido.
74
2.1.3.3 Demodulador
Finalmente se tiene el demodulador, el cual recupera la señal para que pueda ser
decodificada. En la figura 2.13 se observan los pasos del algoritmo generado, los
cuales corresponden al proceso contrario a la modulación. El algoritmo se
encuentra detallado en el Anexo N.
Demodular(sr)sr: señal con ruidor: señal modulada en QPSKr_info: filtro pasa bajosinfo2N: transformada de Furiera: palabra demodulada
a
FIN
r=DownConverter(S)
info2N=FFT(r_info)
a=QPSKDemodulator(info2N)
r_info=filtrar(^r)
Figura 2.13 Demodulador.
2.1.4 DIAGRAMAS DE FLUJO DE LA DECODIFICACIÓN
En esta sección se presentarán los diagramas de flujo de los algoritmos
desarrollados para el funcionamiento de la decodificación.
75
2.1.4.1 Cálculo de los Síndromes
Las figuras 2.14 y 2.15 presentan la estructura del algoritmo del cálculo de
síndromes, el cual en el capítulo 1 (numeral 1.3.3.4.1) es un paso fundamental para
la decodificación de la palabra. El algoritmo se encuentra detallado en los Anexos
E y O.
i≤ nr
Sindromes (R)
Si
No
r=R-1
i=2
No
R: Palabra erradaq: paridad n: longitud de palabra codificadanpolgen: Tamaño Polinomio GeneradorS: SindromesSind: Sindromes-1 [1xq]r: Entrada-1y: [1xnr]z: [1xnr]j,i: ContadoresPcod: palabra codificada
qn
nr=length(r)y=[0...nr]
z=[0]Sind=[0]
i=1
r(i)=-1
z(i)=-1
Sind(1)=Suma_XOR(Sind(1),z(i))i=i+1
z(i)=r(i)+y(i)z(i)=Redondear(z(i))
Si
1
Figura 2.14 Cálculo de los Síndromes - parte 1.
FINi≤q Pcod=[desp u]
j≤ nr
j=1
z(j)=-1
1No
Si
SiSi
No
z(i)=z(i)+y(j)z(j)=Redondear(z(j))
Sind(i)=Suma_XOR(Sind(i),z(j))j=j+1
No
76
Figura 2.15 Cálculo de los Síndromes - parte 2.
2.1.4.2 Algoritmo de Berlekamp-Massey
En las figuras 2.16 a 2.18 se puede observar la estructura del algoritmo de
Berlekamp-Massey utilizado para encontrar el polinomio localizador de error, en el
capítulo 1 se realizó el cálculo sobre el ejemplo presentado (numeral 1.3.3.4.2). El
algoritmo se presenta en los Anexos F y P.
k≤ q
Berlekamp (S)
Si
No
Sind=S-1
No
Sind: Síndromeslamb: polinomio localizadorT: auxiliar de cálculo propio del algoritmod: discrepanciaF: auxiliar de límites de lazok, i: ContadoresN1, N2: Límetes lazos
F=0N1=1N2=2
qLam=[0 sind(1) -1 -1]T=[-1 n-sind(1) -1 -1]
aux3=[-1 -1]k=2
i≤ N1
d=Suma_XOR(d,aux1)i=i+1
aux1=lam(i+1)+sind(k-i)aux1=Redondear(aux1)
Si
Plerror=lam+1 FIN
d=sind(k)i=1
lam(i+1)=-1Ó
Sind(k-i)=-1
aux1=-1
Si
No
4
1
77
Figura 2.16 Berlekamp-Massey - parte 1.
2
d=-1Si
No
Noi≤ N2
aux2=[1]1
aux=d+T
i=1
T(i)=-1
aux2=Redondear(aux2)i=i+1
aux2(i)=-1
Si
Si
No
F=1No
Si
T=[-1 T(1:end-1)]2
i=1
i≤ N1
No
aux3(i)=lam(i)+n-daux3(i)=Redondeo(aux3(i))
i=i+1
T=[-1 n-d aux3]i=1
Si
i≤ N2
lam(i)=Suma_XOR(lam(i),aux(i))
Si
No3
Figura 2.17 Berlekamp-Massey - parte 2.
78
F=1No
Si
N2=N2+1F=1
3
N1=N1+1F=0
4
Figura 2.18 Berlekamp-Massey - parte 3.
2.1.4.3 Polinomio localizador de error
El algoritmo Berlekamp-Massey entrega el polinomio localizador del error, con este
polinomio se procede a localizar la posición del error, para esto se procede a
elaborar el siguiente algoritmo presentado en las figuras 2.19 y 2.20. Se evalúa el
polinomio para encontrar las raíces que corresponderán al recíproco de la posición.
El algoritmo se encuentra detallado en los Anexos G y Q.
LOCALIZADOR (Plerror)
Z=[0] 1x4PosError=[0] 1x3poer=[-1] 1x15lerror=[-1] 1x15
i=1 m=1
i≤nlambda
No
Si
lambda=Plerror-1
Si
lambda(i)=-1
i=3
z(i)=lambda(i)+y(i)z(i)=redondear (z(i))
No
Si
z(i)=-1
lerror(1)=Suma_xor(lerror(1),lambda(i))lerror(2)=Suma_xor(lerror(2),z(i))
i=i+1
i≤npoer(1)=lerror(1)
i=2
j=1
j≤nlambda
z(j)!=-1
z(j)=z(j)+y(j)z(j)=redondear(z(j))
lerror(i)=Suma_xor(lerror(i),z(j))j=j+1
i=i+1
2
Si
Si
Si
No
No
No
lambda: polinomio localizadorPlerror: polinomio localizador errorz:polinomio evaluador de erroresi,j: contadoresn: longitud de la palabra codificadapoer: posición errorPosError: vector posición error
79
Figura 2.19 Polinomio localizador - parte 1.
FINPosError2 i≤(n+1)/2 i=1
poer(i)=lerror(n+2-1)poer(i+(n-1)/2)=lerror(((n+1)/2)+2-i)
i=i+1
i<n
PosError(m)=IM=m+1
poer(i)=-1
i=i+1
Si
No
Si
No
Si
No
Figura 2.20 Polinomio localizador - parte 2.
2.1.4.4 Polinomio evaluador del error
Posterior a encontrar las posiciones de los errores se requiere calcular el polinomio
evaluador, el algoritmo (figura 2.21) toma los síndromes y el polinomio localizador
del error y los multiplica para encontrar el nuevo polinomio.
Zeta (Sind, Lam)
Si
pol=[0]ne=0i=1
Sind: síndromesLam: polinomio localizadorpol=longitud(Polz-1)i, j: contadoresq: paridadPolz: polinomio Zaux1 , aux2: auxiliares
Sind=Sind-1Lam=Lam-1
i≤ q/2
pol(i)=Suma_XOR(Sind(i), Lam(i+1))aux2=-1
j=1
No Polz=[0 pol]+1 FIN
j≤ i-1
Sind(i-j)=-1ó
Lam(j+1)=-1
aux1=sind(i-j)+Lam(j+1)aux1=Redondear(aux1)
aux1=-1
aux2=Suma_XOR(aux2,aux1)a=j+1
Si
Si
pol(i)=Suma_XOR(pol(i),aux2)i=i+1
No
No
80
Figura 2.21 Polinomio evaluador del error.
El algoritmo se presenta detallado en los Anexos H y R.
2.1.4.5 Magnitud del error
PosError(i)=-1
Magnitud (Polz, PosError, Perrada)
No
ne=0nq
i=1magni=[0]
Polz:Poserror:ne: Número de errorn: longitud de palabra codificadaq: paridadPerrada: Palabra erradaPalabra a decodificari,j: contadoreserror: errormagni: M-1M: Magnitud errornume: numeradordeno: denominadorPcorreg: palabra corregidaaux1, aux2, aux3: auxiliares
Polz=Polz-1PosError=PosError-1Perrada=Perrada-1
i≤ q/2
ne=ne+1
i=i+1No
Si
j≤ ne
j=1
Si
error=[-1]i=1
i≤ q/2
i=1
PosError(i)!=-1
5
i=i+1
aux1=0nume=0
i=1
i≤ ne
aux4=0den=n
i=2
aux1=aux1+n-PosError(j)aux1=redondear(aux1)
No
Si
No
Error(PosError(i)+1)=magni(i)
Si
No
Polz(i+1)=-1
aux2=-1
aux2=aux1+Polz(i+1)aux2=redondear(aux2)
No
Si
3
Si
Si
No
1
4
2
81
Figura 2.22 Magnitud del error - parte 1.
PosError(j)=-1
i≤ ne
Si
No
nume=-1
magni(j)=nume+n-denomagni(j)=redondear(magni(j))
J=j+1
i=j
1 nume=Suma_XOR(nume, aux2) 2
aux3=PosError (i)+n-PosError(j)
aux3=PosError(1)+n-PosError(j)
aux3=redondear(aux3)aux3=Suma_XOR(aux3,0)
aux4=aux4+aux3aux4=redondear(aux4)
PosError(j)=-1 deno=aux4
deno=n
i≤ n
Pcorreg(i)=Suma_XOR(Perrada(i), error(i))i=i+1
Pdecod=Pcorreg+1M=magni+1
FIN
i=i+1 3
5
4
i=i+1
3
Si
No
Si
No
No
Si
No
Si
82
Figura 2.23 Magnitud del error - parte 2.
En las figuras 2.22 y 2.23 se puede observar los pasos del algoritmo para calcular
la magnitud del error, el algoritmo de Forney se utiliza para el cálculo. El algoritmo
se encuentra detallado en los Anexos I y S.
2.1.4.6 Decodificador
La figura 2.24 presenta paso a paso el algoritmo utilizado para la decodificación, el
cual llama a los algoritmos previamente elaborados de esta sección para encontrar
la palabra de información inicial. En el capítulo 1 se realiza este cálculo para el
ejemplo en el numeral 1.3.3.4. El algoritmo se encuentra detallado en los Anexos J
y T.
Pdec
FIN
[Pdec, M]=Magnitud(Z, S, Perrada)
Decodificador (Perrada)
L=Localizador(B)
B=Berlekamp(S)
S=Sindromes(Perrada)
Z=Zeta(S,B)
Perrada: Palabra erradaS:vector de síndromesB: vector resultante de cálculo de algoritmo de BerlekampL: vector localizadorZ: polinomio ZM: magnitud del errorPdec: palabra decodificada
Figura 2.24 Decodificación.
83
2.1.5 DIAGRAMA DE FLUJO RUTINA PRINCIPAL REED-SOLOMON
En la figura 2.25 se presenta un resumen de todo el proceso de la codificación y
decodificación Reed-Solomon generada para este proyecto.
REED SOLOMON Palabra: datos de entradaPcod: palabra codificadaS: señal moduladaSR: inserción de señalPerror: palabra erradaPdec: palabra decodificada
Palabra
FIN
Pcod=Codificar(Palabra)
SR=GenerarRuido(S)
Perror=Demodular(SR)
S=Modular(Pcod)
Pdec=Decodificar(Perror)
Pdec
Figura 2.25 Rutina Principal REED-SOLOMON.
2.1.6 RESULTADOS DE LA SIMULACIÓN DE LOS ALGORITMOS DEL
CODIFICADOR REED-SOLOMON
A continuación se presentan los resultados de la simulación de los algoritmos
desarrollados en Matlab, y para una mejor comprensión del manejo de la aplicación
generada se realiza el siguiente manual de usuario.
84
En el Anexo Z se presenta la interfaz gráfica principal, para abrirla es necesario
colocar en el directorio de Matlab la dirección de la carpeta del anexo y en el
workspace digitar el comando “main”.
2.1.6.1 Ejemplo y resultados de la codificación RS (15,9)
En esta sección se simulan los algoritmos del codificador RS (15,9) presentando
imágenes de las interfaces, en la cuales el usuario puede navegar y obtener con
detalle cada dato de la matemática calculada para la generación del codificador RS.
En la Figura 2.26 se pueden apreciar 3 botones del simulador, los cuales despliegan
diferentes interfaces:
· Botón 15-9: Inicio de la interfaz codificación RS (15,9).
· Botón FPGA: Inicio de la interfaz comunicación Matlab – Tarjeta FPGA (su
explicación se desarrollará en el CAPÏTULO 3).
· Botón 204-188: Inicio de la interfaz codificación RS (204,188).
85
Figura 2.26 Menú principal del simulador de Matlab.
A continuación se presentarán los pasos a seguir para la utilización de la aplicación:
1) Luego de hacer click en el botón 15-9, se presentan los parámetros iniciales de
la codificación RS(15,9), como se muestra en la Figura 2.27.
Figura 2.27 Interfaz Codificación RS (15,9).
2) La palabra de información es un vector de 9 símbolos (cada símbolo está
conformado por 8 bits), al que se le puede cambiar los datos según el usuario
requiera o también pueden ser aleatorios haciendo click en el botón GENERAR.
Figura 2.28 Entrada de datos.
86
Para la demostración se usa el ejemplo presentado en el capítulo 1. Cabe recalcar
que en la aplicación de los algoritmos, los símbolos de información expresados
cambian de acuerdo a la Tabla 2.1, usando la Forma Potencial (FP+1
CODIFICADOR).
3) El primer parámetro que se puede desplegar es el Campo de Galois (Figura
2.29). Al hacer click en botón ABRIR se despliega un archivo .xlsx, en donde
se encuentra la Tabla Galois (Tabla 2.1) y la Tabla XOR (Figura 2.30), archivos
importantes para el entendimiento del código RS. En la tabla XOR se tiene tanto
en el la primera fila como en la primera columna los posibles valores decimales
de los símbolos.
Figura 2.29 Parámetro Campo Galois.
Figura 2.30 Tabla XOR de las operaciones entre los elementos del campo de
Galois para un codificador RS(15,9).
4) El segundo parámetro que se puede observar es el Polinomio Primitivo, el cual
es constante para el código RS(15,9). Valor obtenido de la Tabla 1.2
87
Figura 2.31 Polinomio Primitivo para el codificador RS(15,9).
5) El último parámetro que se puede observar en la ventana principal es el
Polinomio Generador, expresado en valores de forma potencial, es constante
para el código RS(15,9).
Figura 2.32 Polinomio Generador para el codificador RS(15,9).
6) En el recuadro de Simular se procede a realizar el cálculo de la palabra
codificada, haciendo click en el botón CODIFICAR.
Figura 2.33 Opción para la codificación RS(15,9) en el simulador de Matlab.
7) Se despliega entonces la Palabra Codificada, obtenida de la aplicación del
algoritmo antes mencionado en el Diagrama de Flujo 2.9. Como se presentó en
la Figura 2.34 se tiene la palabra información [13 0 0 5 0 0 0 0 1] por lo tanto la
paridad corresponde a [12 13 10 3 5 12].
Figura 2.34 Ejemplo de una palabra codificada con RS (15,9).
8) Posteriormente al hacer click en el botón de SIMULINK se despliega su
respectiva simulación (Figura 2.35). Se visualiza de manera rápida la relación
entre la palabra de información y palabra codificada.
88
Figura 2.35 Simulación de la Codificación RS(15,9) en Simulinlk.
9) En el cuadro de navegación se tienen dos opciones, la cuales son: primero
regresar al menú principal o segundo empezar el proceso de decodificación:
10) Seleccionando el botón DECODIFICACIÓN se inicia la interfaz del proceso de
la decodificación que se muestra en la figura 2.36.
89
Figura 2.36 Interfaz de decodificación Reed-Solomon (15,9).
11) Es posible insertar errores en la Palabra Codificada de dos maneras: digitando
los valores dados por el usuario en el campo Palabra Errada con una tolerancia
de hasta 3 errores, o generándolos aleatoriamente por medio del botón
GENERAR, como se muestra en la figura 2.37.
Figura 2.37 Ingreso de errores para la decodificación RS(15,9).
12) En el recuadro de Simular se puede seleccionar el botón DECODIFICAR para
desplegar los resultados de la decodificación.
13) Los cálculos matemáticos generados en la Decodificación se despliegan como
se muestra en la Figura 2.38, los cuales son: Síndromes, Berlekamp-Massey,
Polinomio Localizador (P. Loc.), Polinomio Evaluador del error (Pol. Z.) y
Magnitud de errores respectivamente.
Figura 2.38 Parámetros generados en la Decodificación RS (15,9).
14) En la herramienta de simulación se puede observar y comparar la palabra
codificada, errada y el resultado decodificado con los errores corregidos.
90
Figura 2.39 Resultados de la Decodificación RS(15,9).
15) De la misma manera al hacer click en el botón de SIMULINK se despliega su
respectiva simulación (Figura 2.40). Se visualiza de manera rápida la relación
de palabra de información y palabra codificada.
Figura 2.40 Simulación de la Decodificación en Simulink.
16) En la Figura 2.36 al dar click en el cuadro DECODIFICADOR se visualiza el
arreglo de bloques internos, donde constan los algoritmos de los parámetros
previamente indicados.
91
Figura 2.41 Bloques internos del algoritmo de Decodificación.
17) Finalmente se presentan las opciones de navegación, las cuales permiten
trasladarse al menú principal y de regreso al cuadro de la codificación.
2.1.6.2 Ejemplo y resultados de la codificación RS (204,188)
A continuación se presenta la simulación del método de detección y corrección de
errores Reed-Solomon (204,188) desarrollado en Matlab y con la herramienta
Simulink. En este caso se incluirá un bloque de transmisión de señal OFDM con
esquema de modulación de las portadoras QPSK, con el fin de poder ingresar el
flujo de bits provenientes del codificador RS al canal de prueba. El programa
permite emular diferentes niveles de ruido en el canal, desvanecimientos rápidos y
también los intervalos de guarda 1/4, 1/8, 1/16, 1/32 de la duración del símbolo
activo para el modo 1 de la transmisión de una señal de TV digital ISDBT-b.
A continuación se presentan los pasos para el uso de la interfaz que permite
observar con el detalle el codificador RS(204,188).
1) Al hacer click en el botón del decodificador 204-188, se despliega la interfaz de
la codificación RS(204,188) (Figura 2.42).
92
Figura 2.42 Interfaz de la Codificación RS(204,188).
2) La palabra de información es editable u obtenida aleatoriamente por medio del
botón GENERAR. Para el presente ejemplo se generó una palabra aleatoria. Se
recuerda que el código RS(204,188) es abreviado y se deben añadir
obligatoriamente 51 bytes, formando un código RS(255,239) y éste es el usado
para el proceso de codificación y decodificación. Los 51 bytes serán removidos
posteriormente en la recepción.
A continuación se presenta un ejemplo de la palabra de información generada
con los bytes añadidos:
[203 79 135 42 154 67 167 176 191 115 21 58 233 39 211 137 255 20 113 27 246
1 198 209 222 21 102 66 204 110 233 46 67 37 34 222 148 140 37 218 159 89
131 102 19 61 31 47 61 106 12 231 241 125 125 86 230 94 28 199 99 61 103
24 33 241 244 147 15 60 90 210 3 11 43 166 187 165 115 140 75 190 48 175
46 94 160 199 20 237 198 124 111 114 78 130 130 209 203 164 96 207 136 89 240
224 140 159 150 53 77 120 59 216 49 57 43 58 111 79 236 110 47 231 250 112
28 66 104 152 67 154 182 56 30 75 81 108 130 21 67 205 7 237 186 125 148
60 117 246 139 133 59 125 159 173 101 94 252 9 226 233 203 25 67 85 174 34
93
184 27 167 126 199 183 231 228 85 178 50 7 190 128 122 231 156 158 220 206 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
3) Cabe resaltar que en la palabra de información cada X = [*X*X*X*X*X*X*X*X*] y cada
número tiene su respectiva representación en el Campo de Galois (2�). Dichos
valores se pueden observar en la Figura 2.43 haciendo click en el botón ABRIR.
También en la figura 2.43 se nuestra el Polinomio Primitivo a usarse, que fue
obtenido de la Tabla 1.2.
Figura 2.43 Parámetros de Inicio del codificador RS (204,188).
El Polinomio Generador de grado 16 no es fijo y se pueden observar todos sus
coeficientes en forma de vector.
�(5) =c-��6c0#+ 5 6c0+� 50 6c-�� 5�6c-�- 5#6c-�� 5� 6c0+- 5� 6c-++ 5� 6c-- 5� 6c�� 5� 6c-�� 5-+6c-+� 5-- 6c--� 5-0 6c--+ 5-�6c-+� 5-# 6c-0- 5-� 65-�
�(5) = [<��*2�X*2X¤*<��*<¤<*<�¤*2X<*<XX*<<*¤�*<�£*<X£*<<�*<<X*<X�*<2<]
4) Al hacer click en el botón CODIFICAR (Figura 2.44) se obtiene la Palabra
Codificada (Figura 2.45).
Figura 2.44 Simulación.
94
Figura 2.45 Palabra Codificada.
A continuación se indican todos los términos de la palabra codificada, donde se
puede identificar claramente la paridad, 16 bytes añadidos al inicio de la palabra:
[58 161 149 64 195 41 122 237 131 196 234 213 129 25 226 103 203 79 135 42 154
67 167 176 191 115 21 58 233 39 211 137 255 20 113 27 246 1 198 209 222 21
102 66 204 110 233 46 67 37 34 222 148 140 37 218 159 89 131 102 19 61 31
47 61 106 12 231 241 125 125 86 230 94 28 199 99 61 103 24 33 241 244 147
15 60 90 210 3 11 43 166 187 165 115 140 75 190 48 175 46 94 160 199 20
237 198 124 111 114 78 130 130 209 203 164 96 207 136 89 240 224 140 159 150
53 77 120 59 216 49 57 43 58 111 79 236 110 47 231 250 112 28 66 104 152
67 154 182 56 30 75 81 108 130 21 67 205 7 237 186 125 148 60 117 246 139
133 59 125 159 173 101 94 252 9 226 233 203 25 67 85 174 34 184 27 167 126
199 183 231 228 85 178 50 7 190 128 122 231 156 158 220 206 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
5) EL botón SIMULINK (Figura 2.44) permite observar la simulación de la
codificación, debido a las limitaciones del display solo se pueden observar los
200 primeros términos (Figura 2.45).
6) En la Figura 2.46 se aprecian las formas de navegación que se pueden utilizar
en en la interfaz. Con el botón PRINCIPAL se despliega la interfaz del menú,
con el botón MODULACIÓN se inicia el proceso de la transmisión de la señal
por el canal. Para realizar la Decodificación se hace click en el botón
DECODIFICACIÓN.
Figura 2.46 Opciones del codificador RS (204,188).
95
Figura 2.47 Simulación de la Codificación RS (204,188) en Simulink.
A continuación se describe la Interfaz de la Modulación que se muestra en la figura
2.48.
96
Figura 2.48 Interfaz de la modulación en el codificador RS(204,188).
En la Figura 2.49 se aprecian los datos de la palabra codificada en forma discreta.
Figura 2.49 Representación discreta de la Palabra Codificada.
En la Figura 2.50 se aprecian las componentes I y Q de la palabra mapeada en
QPSK.
97
Figura 2.50 Diagrama de constelación del modulador antes de la
transmisión.
En la Figura 2.51 se muestran los datos después de pasar por el filtro pasa bajos y
la transformada inversa rápida de Fourier (IFFT), listos para la modulación sobre
las subportadoras generadas.
Figura 2.51 Transformada Inversa de Fourier de la palabra codificada.
En la figura 2.52 se observa la señal ya analógica después de pasar por el
conversor digital a analógico.
98
Figura 2.52 Señal después de pasar por DAC.
En la Figura 2.53 se aprecia la señal modulada a transmitirse.
Figura 2.53 Señal modulada a transmitirse.
7) Posteriormente, se puede seleccionar el valor de intervalo de guarda (figura
2.54) que previamente se explicó en el CAPÍTULO 1.
99
Figura 2.54 Opciones de intervalo de guarda en la simulación.
8) Por medio del botón MODULAR se pueden cambiar los intervalos de guarda.En
las figuras 2.55 a 2.58 se muestra la modulación de la señal con diferentes
valores de intervalo de guarda, -#,
-�,
--� y
-�0 respectivamente.
Figura 2.55 Señal Modulada a 1/4 de intervalo de guarda.
Figura 2.56 Señal Modulada a 1/8 de intervalo de guarda.
100
Figura 2.57 Señal Modulada a 1/16 de intervalo de guarda.
Figura 2.58 Señal Modulada a 1/32 de intervalo de guarda.
La interfaz gráfica en la pantalla “MODULACIÓN OFDM QPSK” presenta los
campos editables correspondientes a Ps y SNR, propiedades del bloque AWGN de
SImulink para generación de ruido, como se indica en la Figura 2.59.
Figura 2.59 SNR y Ps.
101
SNR hace referencia a la relación Señal a Ruido, mientras que Ps es el valor de
potencia del ruido en referencia a 1 ohm.
9) Ingresados los valores de ruidos se procede con la demodulación mediante el
botón DEMODULAR, el cual despliega las respectivas gráficas del proceso de
la demodulación (figura 2.60).
Figura 2.60 Resultados del proceso de Demodulación.
En la Figura 2.61 se aprecia en color rojo la señal original y en color azul la señal
que se recepta con ruido.
Figura 2.61 Señal Recibida con ruido.
102
En la Figura 2.62 se aprecia en color rojo la señal en cuadratura y en color azul la
señal en fase después de pasar por el filtro pasa bajos de la demodulación.
Figura 2.62 Señal en fase y cuadratura en el proceso de demodulación.
En la Figura 2.63 se aprecia la señal después del conversor analógico a digital, las
señales se encuentran separadas por fase y cuadratura.
Figura 2.63 Señal recibida después del conversor analógico a digital.
En la Figura 2.64 se aprecian los valores recuperados después del mapeo QPSK.
Se presenta la palabra codificada con errores en forma discreta.
103
Figura 2.64 Señal recuperada con errores en el receptor.
El diseño realizado en Simulink permite apreciar en general los bloques utilizados
para la transmisión de la señal OFDM por un canal con ruido (Figura 2.65). Se
presenta la gráfica de constelación recuperada (Figura 2.66).
Figura 2.65 Diagrama de bloques del canal simulado en Simulink.
104
Figura 2.66 Diagrama de constelación del Demodulador en el receptor.
10) Por medio de la interfaz de navegación (figura 2.67) se ingresa al proceso de
la decodificación por medio del botón DECODIFICACIÓN.
Figura 2.67 Interfaz para la decodificación de la señal.
En la Figura 2.68 se aprecia la interfaz completa de la Decodificación RS(204,188).
11) En la Figura 2.69 se despliegan los valores de la palabra codificada, palabra
errada, valores modulados y demodulados previamente, indicando la cantidad
de errores generados. También se pueden generar errores aleatorios haciendo
click en el botón GENERAR o ingresando los valores que el usuario desee, ya
que el campo es editable. El contador de errores funciona en todos los casos.
105
Figura 2.68 Interfaz completa del proceso de Decodificación.
Figura 2.69 Datos de entrada.
Se han desplegado los valores de la palabra codificada y palabra errada del ejemplo
para poder apreciar en color amarillo la cantidad de errores generados y su
posición.
Palabra codificada:
[58 161 149 64 195 41 122 237 131 196 234 213 129 25 226 103 203
79 135 42 154 67 167 176 191 115 21 58 233 39 211 137 255 20 113
27 246 1 198 209 222 21 102 66 204 110 233 46 67 37 34 222 148
106
140 37 218 159 89 131 102 19 61 31 47 61 106 12 231 241 125 125
86 230 94 28 199 99 61 103 24 33 241 244 147 15 60 90 210 3
11 43 166 187 165 115 140 75 190 48 175 46 94 160 199 20 237 198
124 111 114 78 130 130 209 203 164 96 207 136 89 240 224 140 159
150 53 77 120 59 216 49 57 43 58 111 79 236 110 47 231 250 112
28 66 104 152 67 154 182 56 30 75 81 108 130 21 67 205 7 237
186 125 148 60 117 246 139 133 59 125 159 173 101 94 252 9 226
233 203 25 67 85 174 34 184 27 167 126 199 183 231 228 85 178
50 7 190 128 122 231 156 158 220 206 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Palabra errada:
[58 161 149 64 195 41 122 237 131 196 35 213 129 25 226 103 203
79 135 42 154 67 167 176 191 115 21 58 233 39 211 112 255 20 113
27 246 1 198 209 71 21 102 66 204 110 233 46 67 37 34 222 148
140 37 218 159 89 131 102 19 61 31 47 61 106 12 231 241 125 125
86 230 94 28 199 99 61 103 24 33 241 244 147 15 60 90 210 3
11 43 166 187 165 115 140 75 190 48 175 46 94 160 199 20 237 198
124 111 114 78 130 130 209 203 164 96 207 136 89 240 224 140 159
150 53 77 120 59 216 49 57 43 58 111 244 236 110 47 231 250 112
28 66 104 152 67 154 213 56 30 75 81 108 130 21 67 205 7 237
186 125 148 206 117 246 139 133 59 125 159 173 101 94 252 9 226
233 203 36 67 85 174 34 184 27 167 126 199 183 232 228 85 178
50 7 190 128 122 231 156 158 220 206 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
En los ocho bytes errados se encontraron 24 bits con error (tabla 2.3), el algoritmo
tiene como capacidad de corregir 64 bits siempre y cuando sean dentro de los
mismos 8 bytes.
107
Tabla 2.3 Bits errados en el ejemplo de codificación RS(204,188).
234 1 1 0 0 1 1 1 1 SIMBOLO ORIGINAL
35 0 1 1 1 0 0 1 0 SÍMBOLO ERRADO
137 1 1 1 1 0 0 1 0
112 0 1 1 1 0 0 1 1
222 1 0 1 0 0 0 1 0
71 0 1 1 1 1 0 1 0
79 0 0 0 1 1 1 1 0
244 1 0 1 1 1 1 1 0
182 1 0 0 0 1 1 0 0
213 1 0 0 1 1 1 1 0
60 0 1 0 0 1 0 1 1
206 1 1 1 0 0 1 0 1
25 1 1 1 1 0 0 0 1
36 0 0 1 1 1 0 0 1
231 0 0 1 0 1 1 1 1
232 1 0 1 0 1 1 1 1
En la Figura 2.70 se despliegan los valores de cada proceso matemático necesario
para obtener la solución:
Figura 2.70 Parámetros del Proceso de Decodificación RS (204,188).
108
El parámetro de Síndromes del ejemplo se presenta en forma vectorial a
continuación:
[127 135 251 238 207 179 210 43 22 244 119 122 36 7 75 244]
En la Figura 2.71 se aprecia la palabra Decodificada (corregida los errores), que se
la presenta en el recuadro de Datos Entrada para su comparación con la palabra
codificada.
Figura 2.71 Palabra Decodificada RS (204,188).
La Palabra Decodificada completa es la siguiente:
[58 161 149 64 195 41 122 237 131 196 234 213 129 25 226 103 203
79 135 42 154 67 167 176 191 115 21 58 233 39 211 137 255 20 113
27 246 1 198 209 222 21 102 66 204 110 233 46 67 37 34 222 148
140 37 218 159 89 131 102 19 61 31 47 61 106 12 231 241 125 125
86 230 94 28 199 99 61 103 24 33 241 244 147 15 60 90 210 3
11 43 166 187 165 115 140 75 190 48 175 46 94 160 199 20 237 198
124 111 114 78 130 130 209 203 164 96 207 136 89 240 224 140 159
150 53 77 120 59 216 49 57 43 58 111 79 236 110 47 231 250 112
28 66 104 152 67 154 182 56 30 75 81 108 130 21 67 205 7 237
186 125 148 60 117 246 139 133 59 125 159 173 101 94 252 9 226
233 203 25 67 85 174 34 184 27 167 126 199 183 231 228 85 178
50 7 190 128 122 231 156 158 220 206 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Los valores recuperados son exactamente los mismos a los valores de la Palabra
Codificada. Si se retiran los 51 bytes añadidos y los 16 bytes primeros de paridad
se recupera la información.
109
Por medio del botón SIMULINK se despliegan los valores obtenidos en la
simulación, con un límite del display de 200 valores (figura 2.72).
Figura 2.72 Simulación de la Decodificación.
110
En la figura 2.73 se presenta la interfaz gráfica con el proceso completo de la
decodificación RS (204,188).
Figura 2.73 Interfaz gráfica con los valores completos de la decodificación.
2.2 EFICIENCIA DEL ALGORITMO FRENTE AL NIVEL DE ERROR
El codificador REED-SOLOMON (204,188) posee el limitante de corregir 8 errores
producidos por la transmisión de la información por el canal. En un canal ideal no
se presentaría ruido y por lo tanto no existirían errores de transmisión.
Para poder simular un canal real se realiza un generador de ruido aleatorio con
amplitud e intensidad variable dependiendo del valor de relación señal a ruido
(SNR) y el valor de poder de la señal de ruido a ingresarse (Ps), referenciada a 1
ohm (watts).
111
Los valores por defecto que se establecieron son: SNR=10 y Ps=0.0012, con los
cuales el ruido generará un número de errores aleatorios dentro del valor permitido.
Para el análisis de eficiencia del algoritmo ante la presencia del ruido se realizarán
variaciones del valor de Ps para determinar el número de errores que se presentan
en un número de transmisiones realizadas. Se partirá desde un Ps de cero y se
comenzará a subir el valor hasta que se presenten errores en la palabra
demodulada, de esta manera se podrá verificar, primero hasta que valor de ruido el
canal no se ve afectado y posteriormente el número de errores generados por cada
uno de los valores hasta llegar al límite de errores que son ocho.
En la Tabla 2.4 se presentan los resultados de los análisis de diez transmisiones
con diferentes niveles de ruido.
Tabla 2.4 Resultados estadísticos de números de errores
producidos por ruido.
#TRANSMISIÓN 1 2 3 4 5 6 7 8 9 10 MAXIMO % PRESENCIA ERROR
Ps 0 0
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0001 0.0001
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0002 0.0002
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0003 0.0003
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0004 0.0004
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0005 0.0005
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0006 0.0006
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0007 0.0007
ERRORES 0 0 0 0 0 0 0 0 0 0 0 0%
Ps 0.0008 0.0008
ERRORES 0 0 0 0 1 0 1 0 1 0 1 30%
Ps 0.0009 0.0009
ERRORES 3 1 0 1 1 2 4 0 0 0 4 60%
Ps 0.0010 0.0010
ERRORES 2 1 2 4 2 1 4 5 2 0 5 90%
Ps 0.0011 0.0011
112
ERRORES 2 1 3 0 5 3 4 1 3 6 6 90%
Ps 0.0012 0.0012
ERRORES 3 7 4 3 4 4 5 3 7 5 7 100%
Ps 0.0013 0.0013
ERRORES 7 3 7 4 3 6 6 7 8 8 8 100%
Ps 0.0014 0.0014
ERRORES 10 8 2 9 4 9 6 5 9 3 10 100%
Ps 0.0015 0.0015
ERRORES 7 13 13 9 4 11 14 12 9 6 14 100%
Ps 0.0020 0.0020
ERRORES 30 26 29 24 28 23 29 31 18 27 31 100%
Se puede concluir que mientras sube el nivel de ruido manteniendo la relación señal
a ruido, aumenta el número de errores como se puede observar en la Figura 2.74.
Figura 2.74 Errores vs Potencia de Ruido.
El nivel crítico de potencia es Ps=0.0013, debido a que con este nivel se generarán
número de errores desde 3 hasta 8 errores como se observa en la Tabla 2.4. Con
valores más altos el número de errores pasarán el límite corregible, por lo cual no
todas las palabras serán corregidas. A continuación en las Figuras 2.75 a 2.83 se
presenta el número de errores producidos en cada transmisión con diferentes
valores de potencia de ruido. Se presentarán las gráficas de número de errores
para valores de Ps desde 0.0008 debido a que para valores menores no se generan
errores.
0 0 0 0 0 0 0 14 5 6 7 8
1014
31
0
5
10
15
20
25
30
35
ERR
OR
ES
Ps=POTENCIA DE RUIDO (WATT)
NÚMERO ERRORES POR POTENCIA DE RUIDO
113
Figura 2.75 Número de errores vs número de transmisiones para Ps (0.0008).
Figura 2.76 Número de errores vs número de transmisiones para Ps (0.0009).
Figura 2.77 Número de errores vs número de transmisiones para Ps (0.0010).
0
0,5
1
1,5
1 2 3 4 5 6 7 8 9 10
ERR
OR
ES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0008)
0
1
2
3
4
5
1 2 3 4 5 6 7 8 9 10NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0009)
0
2
4
6
1 2 3 4 5 6 7 8 9 10NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0010)
114
Figura 2.78 Número de errores vs número de transmisiones para Ps (0.0011).
Figura 2.79 Número de errores vs número de transmisiones para Ps (0.0012).
Figura 2.80 Número de errores vs número de transmisiones para Ps (0.0013).
0
2
4
6
8
1 2 3 4 5 6 7 8 9 10NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0011)
0
2
4
6
8
1 2 3 4 5 6 7 8 9 10NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0012)
0
2
4
6
8
10
1 2 3 4 5 6 7 8 9 10
NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0013)
115
Figura 2.81 Número de errores vs número de transmisiones para Ps (0.0014.)
Figura 2.82 Número de errores vs número de transmisiones para Ps (0.0015).
Figura 2.83 Número de errores vs número de transmisiones para Ps (0.0020).
0
2
4
6
8
10
12
1 2 3 4 5 6 7 8 9 10NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0014)
0
2
4
6
8
10
12
14
16
1 2 3 4 5 6 7 8 9 10
NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0015)
0
10
20
30
40
1 2 3 4 5 6 7 8 9 10
NÚ
MER
O D
E ER
RO
RES
NÚMERO DE TRANSMISIONES
NÚMERO DE ERRORES POR TRANSMISIÓN Ps (0.0020)
116
Se debe tomar en cuenta que el algoritmo puede corregir hasta ocho errores, por
lo tanto hay niveles de ruido que aunque su máximo número de errores sobrepasa
este límite, producen aleatoriamente errores que entran en el intervalo permitido,
como se puede observar en las figuras 2.81 y 2.82, y pueden ser corregidos. Para
valores mayores de potencia de ruido no será posible corregir los errores y la
transmisión llegará con problemas.
Se puede también realizar el análisis con las gráficas desplegadas por la interfaz al
demodular. Se presentará un ejemplo con cero errores y uno con un nivel de
potencia tan alto que generará un gran número de errores.
Para una potencia de ruido que no afecta a la señal se tiene un número de cero
errores, por lo cual se posee una señal recibida sin alteraciones, como se puede
observar en la Figura 2.84 y 2.85.
Figura 2.84 Modulación con potencia de ruido de Ps (0.00002).
117
Figura 2.85 Señal recibida sin ruido.
De la misma manera en el diagrama de constelaciones se puede observar que los
datos recibidos aparecen muy cercanos a los puntos de cuadratura sin generar
conflicto. La Figura 2.86 presenta el diagrama de constelaciones.
Figura 2.86 Diagrama de constelaciones señal sin errores.
Cuando se demodula con un nivel de ruido significativo se tiene una generación de
varios errores como se puede observar en la Figura 2.87.
118
Figura 2.87 Modulación con potencia de ruido de Ps (0.02).
En la Figura 2.88, la señal recibida con ruido (señal en azul) es más grande que la
señal original (señal en rojo) por lo que se presenta al momento de demodular una
palabra con 212 errores, los cuales será imposible corregirlos con el codificador RS
(204,188).
Figura 2.88 Señal recibida con ruido.
De la misma manera en el diagrama de constelaciones se puede observar que los
datos recibidos se encuentran distribuidos por toda la constelación sin un indicio de
exactitud entre los datos pertenecientes a cada punto de cuadratura. La Figura 2.89
presenta el diagrama de constelaciones.
119
Figura 2.89 Diagrama de constelaciones señal con errores
120
CAPÍTULO 3
IMPLEMENTACIÓN DEL CODIFICADOR Y DECODIFICADOR RS
3.1 CARACTERÍSTICAS DE LA TARJETA FPGA SPARTAN 3E [25]
[26] [27][28] La tarjeta FPGA (Field Programmable Gate Array) es un dispositivo lógico,
conformado por una serie de compuertas lógicas programables a través de un
lenguaje de programación específico. La manera en la cual se encuentra constituida
una FPGA da al usuario un sin número de posibilidades creativas.
Existen varios tipos de tarjetas, las cuales poseen diferentes capacidades lo que
limita la creación de diferentes tipos de dispositivos. Cada fabricante de tarjetas
posee su propio software propietario con el cual se debe programar a la tarjeta. Con
el avance del tiempo aumenta también la variedad de tarjetas cada vez con
capacidades superiores, ampliando los campos de aplicación desde la más básica
que comprende una pequeña serie de compuertas, hasta áreas muy complejas
como radioastronomía, emulación de hardware, bioinformática y criptografía. En el
presente proyecto se utilizará la tarjeta SPARTAN 3E para aplicación en Televisión
Digital Terrestre. A continuación se describen las cualidades y propiedades de la
tarjeta a ser utilizada para desarrollar este proyecto.
Figura 3.1 Tarjeta FPGA Spartan-3E utilizada en el proyecto.
121
Las características de la tarjeta FPGA Spartan 3E son las siguientes:
· FPGA XC3S500E, familia Spartan-3E de Xilinx.
· Memoria Flash de 4 Mbit para configuración.
· CPLD XC2C64A, familia CoolRunner.
· DDR SDRAM de 64 MByte (512 Mbit), interfaz x16, 100+ MHz.
· Memoria Flash 16 MByte (128 Mbit) para aplicaciones.
· Memoria Flash 16 Mbits acceso serial, via SPI.
· Pantalla LCD de 16 caracteres por 2-líneas.
· Puerto PS/2 y Puerto VGA.
· Capa física Ethernet 10/100.
· Dos puertos RS-232 de 9 terminales.
· Interfaz USB para descarga y depuración
· Oscilador de 50 MHz.
· Convertidor Digital a Analógico SPI de cuatro salidas, con resolución de 12 bits.
· Convertidor Analógico a Digital SPI de dos entradas con resolución de 14 bits y
pre - amplificador con ganancia programable.
· Botón rotatorio.
En la Figura 3.2 se presenta la estructura de una tarjeta FPGA con sus módulos
principales.
Figura 3.2 Módulos de una tarjeta FPGA.
La interfaz SPI permite que el usuario pueda manipular el Conversor Digital a
Análogo (DAC), el Conversor Análogo a Digital (ADC) y el pre-amplificador con
ganancia variable.
122
La interfaz SPI posee componentes SPI maestro y SPI esclavo, los cuales son
manejados por señales MOSI (Master Output, Slave Input), MISO (Master Input,
Slave Output) y SCK (reloj del sistema). La tarjeta FPGA corresponde al
componente Maestro, mientras los conversores DAC, ADC y el preamplificador
corresponden a los componentes esclavos. En la tarjeta Spartan 3E se tiene el DAC
de tipo LTC264, el ADC de tipo LTC1407a-1 y un preamplificador LTC6912-1.
En una estructura SPI los esclavos comparten un bus SPI común, por lo cual no
solo existen las tres señales antes mencionadas, es decir MISO, MOSI y SCK, sino
que también se presentan señales propias para su puesta en marcha, de esta
manera no existirán conflictos al funcionar un dispositivo mientras otro se está
usando.
En la Figura 3.3 se presentan las conexiones entre el Maestro y los Esclavos,
Figura 3.3 Componentes de la Interfaz SPI.
La interfaz SPI posee una sola entrada y una sola salida para la señal analógica,
las cuales son, D_IN y D_OUT respectivamente.
El módulo Interfaz_usuario permite al usuario manipular de manera directa la
tarjeta FPGA por medio de los interruptores y control rotatorio, mediante los cuales
se define la referencia y se manipulan los LEDs para mostrar resultados según sea
123
la necesidad. También se puede interactuar con la pantalla LCD para mostrar la
referencia, el valor actual y el posible error.
El módulo Algoritmo_Control recibe como entrada la señal a utilizarse en el
algoritmo programado en la interfaz SPI y el módulo Interfaz_usuario para de esta
manera tener una salida con el resultado esperado.
Lo que se busca al trabajar con tarjetas FPGA es transformar en físico un proceso
o algoritmo desarrollado como script en lenguaje de comandos. Una ventaja de la
tarjeta FPGA SPARTAN 3E es la compatibilidad que presenta con MATLAB,
software en el cual se desarrolló el algoritmo del codificador RS. Esta compatibilidad
se refleja en la capacidad de transformar los bloques de Simulink, herramienta de
Matlab, a VHDL lenguaje de programación de la tarjeta.
A continuación se describirán los tres módulos previamente definidos.
3.1.1 MÓDULO INTERFAZ_SPI
Este módulo opera a través de registros de desplazamiento, es decir que el maestro
indica la velocidad y marca el inicio de la transferencia, mientras que el esclavo
recibe los datos y los retorna para verificación. En la Figura 3.4 se puede observar
la comunicación de la interfaz.
Figura 3.4 Comunicación SPI.
124
En la figura se puede observar una señal SS la cual sirve para seleccionar un
esclavo en particular, debido a que pueden existir varios esclavos compartiendo la
interfaz.
En la figura 3.5 se presenta el diagrama de bloques de la interfaz SPI con las
respectivas conexiones entre los elementos a ser programados.
Figura 3.5 Diagrama de bloques del módulo Interfaz SPI.
Para el control de los desplazamientos requeridos por cada dispositivo se tiene el
bloque contador. El bloque control genera las tramas SPI y activa a cada uno de
los dispositivos para que no se encuentren activados en simultáneo.
El control se basa en cuatro estados jerárquicos, los cuales corresponden a estado
inicio, estado AMP, estado DAC y finalmente estado ADC. Estos estados se pueden
observar en la Figura 3.6.
125
Figura 3.6 Estados de control del módulo SPI.
El estado inicio corresponde a señales colocadas por el control, en espera de la
estabilización de los dispositivos después de reinicios en la alimentación. En el
estado AMP se tiene el procedimiento de configuración del pre-amplificador con
ganancia unitaria. Finalmente se tiene una secuencia infinita entre el DAC y el ADC.
3.1.2 MÓDULO INTERFAZ_USUARIO
El módulo basa su funcionamiento en un procesador de 8 bits, el cual posee una
memoria ROM de un bloque RAM con capacidad para almacenar un programa de
hasta 1024 instrucciones y posee un desempeño de entre 43 y 66 MIPS (millones
de instrucciones por segundo) en la tarjeta Spartan 3E.
Este módulo se encuentra compuesto de 42 instrucciones y comandos para
procesar datos de ocho bits, estas instrucciones están comprendidas entre lógicas,
aritméticas y de transferencia. Además de las instrucciones también comprende
memoria de datos, 16 registros de propósito general, banderas, ALU (unidad
aritmética lógica), 1 interrupción externa, 256 puertos de entrada y 256 puertos de
salida.
El LCD, botón rotatorio, interruptores y botones, así como el reconocimiento del
estado de la planta y la inserción de los datos, se los maneja por medio de la
configuración de los respectivos puertos.
126
En las diferentes configuraciones para la activación de puertos se tiene un lenguaje
de programación denominado VHDL (VHSIC25 Hardware Description Language), el
cual será explicado brevemente más adelante.
En la Tabla 3.1 se presenta los puertos requeridos para la configuración de los
distintos elementos de la interfaz_usuario en una tarjeta Spartan 3E.
Tabla 3.1 Puertos de la Interfaz_Usuario.
Puerto Uso switch_port 4 botones y 4 interrupciones rotary_port Codificador Rotatorio
LCD_input_port Datos del módulo LCD Act_port_LOW Estado actual (byte bajo) Act_port_HIGH Estado actual (byte alto)
LCD_output_port Datos y Control del LCD Err_port_LOW Error (byte bajo) Err_port_HIGH Error (byte alto)
LED_port Manejo de los LEDs
En las figuras 3.7 y 3.8 se presentan los diagramas de bloques con sus respectivas
señales, tanto de los puertos de entrada como de los puertos de salida
respectivamente.
Figura 3.7 Diagrama de bloques del puerto de entrada.
25 VHSIC: Very High Speed Integrated Circuit
127
Figura 3.8 Diagrama de bloques del puerto de salida.
3.1.3 MÓDULO ALGORITMO_CONTROL
En el módulo Algoritmo_Control se configura el procedimiento que unirá los dos
módulos previamente explicados, y de esta manera identificará las señales de
entrada que ingresarán al algoritmo programado para que se genere una señal de
salida con el resultado esperado.
3.1.4 COMUNICACIÓN UART
El módulo receptor y transmisor asíncrono universal (Universal Asynchronous
Receiver-Transmitter) es el dispositivo que ayuda en la transmisión de información
en un sistema serial de comunicaciones. Entre las aplicaciones básicas de la UART
se puede mencionar la comunicación entre un PC y una tarjeta PFGA. Su función
principal es convertir los datos de información paralelo a serie para transmisión
(datos de salida) y convierte datos de serie a paralelo cuando se trata de datos
recibidos (datos de entrada).
Las funciones principales del módulo UART son:
128
· Conversión de datos de paralelo a serie y viceversa,
· Genera bit de inicio,
· Inserta bit de parada,
· Sincronismo entre receptor y transmisor,
· Codificación de datos (paridad),
· Envío de señales de handshaking26,
· Envío de señales eléctricas de valores lógicos,
· Controla número de bits por carácter,
· Controla la velocidad de transmisión y recepción,
Figura 3.9 Diagrama de Bloques del sistema de transmisión y recepción
digital.
UART es el mecanismo más importante en un subsistema serial de comunicaciones
de computadora, toma bytes de datos y transmite los bits individuales de forma
secuencial. En la recepción se re-ensamblan los bits en bytes completos. Las
señales externas pueden ser de varias índoles. En este proyecto el estándar a
usarse es el RS-232, señalización por voltaje.
26 Handshaking: Un procesador y sus periféricos intercambian señales de control que les permiten sincronizar
sus acciones y "colaborar" conjuntamente en la transferencia de información.
129
La comunicación UART en el actual proyecto se utiliza para la comunicación serial
entre el computador que actúa como generador de información y posteriormente
presenta en Simulink los resultados obtenidos después de pasar por la tarjeta
FPGA.
Matlab por defecto no posee habilitado la comunicación serial, por lo cual es
necesario la instalación del paquete de comunicación adjunto el Anexo Y. Para su
instalación, en el workspace de Matlab se ejecuta la función “install_waijung”.
3.2 LENGUAJE VHDL [29] [30] [31]
Las siglas de VHDL, significan Very high speed integrated circuit (VHSIC) Hardware
Description Language. VHDL es la manera por la cual, las máquinas y personas
entienden la funcionalidad y ordenamiento de los sistemas digitales de hardware.
VHDL fue definido por el IEEE27 y usado para implementar circuitos digitales. Fue
desarrollado en los Estados Unidos a inicios de los años 80`s con la finalidad de
realizar simulaciones de circuitos digitales. Después se desarrollaron herramientas
que permitieron la implementación en hardware.
VHDL permite programar algoritmos por software y modelar sistemas digitales y
hardware. A partir de estos modelos se puede:
· Simular para comprobar que se tiene la funcionalidad deseada.
· Sintetizar para crear un circuito que funciona como el modelo.
3.2.1 VENTAJAS DEL LENGUAJE VHDL
Las ventajas son:
· Disponibilidad pública.
· Reutilización.
27 IEEE: Instituto de Ingeniería Eléctrica y Electrónica
130
· Diseño jerárquico.
· Independencia de dispositivos y fabricantes.
3.2.2 CARACTERÍSTICAS DEL LENGUAJE VHDL
Las características del lenguaje VHDL son:
3.2.2.1 Descripción textual normalizada
El lenguaje especifica los circuitos en un formato adecuado para ser interpretado
tanto por personas como por máquinas. Se trata además de un lenguaje formal, no
ambiguo. Su utilización está abierta garantizando su compatibilidad siempre que se
mantengan sus especificaciones de acuerdo a la norma. Su lenguaje es ejecutable
y la descripción textual del hardware se materializa en una representación del
mismo, utilizable por herramientas como simuladores y sintetizadores lógicos.
3.2.2.2 Extenso rango de capacidad descriptiva
El lenguaje hace factible la descripción del hardware en varias formas de
abstracción, con esto se logra la adaptabilidad para distintos propósitos y la
actualización de los diseños a los avances de la tecnología en el futuro. Es flexible
a distintas metodologías de diseño y es independiente de la tecnología.
3.2.3 MODELADO VHDL
El modelo de hardware de un dispositivo en VHDL consiste en la obtención de dos
unidades de código VHDL.
3.2.3.1 Declaración de Entidad
Es la unidad de diseño VHDL que se aprovecha para indicar la interfaz del
dispositivo. Aquí se define el nombre del dispositivo y sus puertos.
131
3.2.3.2 Cuerpo de Arquitectura
El cuerpo de arquitectura es la unidad de diseño VHDL que permite indicar el
funcionamiento de un dispositivo identificado por una determinada declaración de
entidad, equivalente a las tablas de verdad.
El modelo se dará como concluido el momento en el cual las unidades que lo
describen son almacenadas en una librería VHDL. Para comprobar que el modelo
fue desarrollado siguiendo una serie de reglas sintácticas y semánticas se utiliza el
compilador. Un proyecto de VHDL puede contener muchos ficheros. El código
VHDL usualmente se encuentra en los ficheros con extensión *.vhd.
3.2.4 TIPO DE DESCRIPCIÓN
VHDL permite una gran cantidad de arquitecturas posibles para describir un mismo
circuito electrónico, el lenguaje no se halla orientado hacia ningún método en
especial y el mismo circuito puede ser descrito de varias formas, las más usadas
son las que se indican a continuación:
3.2.4.1 Descripción de comportamiento
Indica la manera en que se comporta el circuito digital, se tiene en cuenta el
comportamiento de las entradas y las salidas. De esta forma la descripción puede
ser secuencial, además estas sentencias se encuentran dentro de los llamados
procesos en VHDL, los procesos pueden ser ejecutados en paralelo entre sí.
3.2.4.2 Descripción de flujo de datos
En esta descripción hay varias instrucciones concurrentes, como consecuencia no
se seguirá el orden en que están escritas las instrucciones a la hora de ejecutar el
código. Si hay dos o más instrucciones, estas se ejecutan al mismo tiempo.
132
3.2.4.3 Descripción estructural
Describe el circuito como instancias que permiten la realización de diseños
jerárquicos. Si el diseño es complejo, esta descripción es la recomendada a
utilizarse.
3.2.4.4 Descripción mixta
Combinación de las descripciones antes mencionadas.
3.3 TRANSFORMACIÓN DEL ALGORITMO DESARROLLADO EN
MATLAB A LENGUAJE VHDL [32]
Se han establecido varios métodos y herramientas para la creación e
implementación del código VHDL a partir de otros lenguajes de programación. En
este proyecto para la elaboración del código VHDL se ha partido del entorno de
Matlab, que consiste en una herramienta técnica de altas prestaciones para el
cálculo numérico y su respectiva visualización.
Para la transformación de Matlab a VHDL se usa la herramienta Math Works y el
generador HDL Code. La función del generador HDL coder es generar
automáticamente un código HDL desde MATLAB, es decir que permite diseños
sobre FPGAs y ASICs mediante el lenguaje de Matlab. Ya que el objetivo de la
creación del lenguaje fue principalmente lograr el diseño, modelado y
documentación del Método de Detección y Corrección de errores Reed-Solomon
se ha procedido a realizar la transformación de los algoritmos desde Matlab,
facilitando la realización de scripts de los circuitos complejos desarrollados.
A continuación se describen los pasos a seguir para obtener el código VHDL a partir
de MATLAB:
HDL CODER es una aplicación propia de Matlab versión R2014a.
133
Se inicia el HDL CODER herramienta de transformación de código entre el modelo
de Matlab y el código VHDL, que además permite la verificación de código para
aplicaciones de alta integridad.
Figura 3.10 Ícono de la herramienta Matlab HDL Coder.
1. Se procede a dar un nombre al archivo VHDL, de acuerdo a la ventana de la
figura 3.11, la extensión que tendrá este archivo es *.prj
Figura 3.11 Selección del nombre del archivo VHDL.
2. Se escoge la función que se requiere convertir a VHDL. Se añade sólo el archivo
a convertir directamente de Matlab, no se añaden archivos que son llamados
por la función. Se hace click en el botón Workflow Advisor.
134
Figura 3.12 Selección de la función de Matlab para la transformación.
3. Se define la carpeta de proyecto y el modo conversión de punto fijo, el cual
genera el código utilizando los datos especificados en el algoritmo de Matlab.
Se presiona el botón RUN y empieza el proceso automático de cambio a código
VHDL con la respectiva generación y verificación del código HDL.
Figura 3.13 Parámetros para la generación del archivo VHDL.
Si el proceso se ejecutó con éxito se despliega la pantalla mostrada en la figura
3.14.
135
Figura 3.14 Ventana de generación de código VHDL exitosa.
4. Se genera el código de Matlab en lenguaje VHDL, como se muestra en la figura
3.15.
Figura 3.15 Script VHDL generado en Matlab.
5. Se abre el código en ISE Desing Suite versión 13.1.
6. Se compila el código para verificar que funciona y es posible verificar también
que entradas y salidas se especificaron.
136
7. Se configuran las entradas y salidas a usar en la tarjeta FPGA y se procede a
grabar el programa en la misma.
3.4 SIMULACIÓN DEL CODIFICADOR RS(15,9) EN ISIM
SIMULATOR DE XILINX
Al tener el código en lenguaje VHDL se verifica el funcionamiento del algoritmo, por
medio del simulador de XILINX. Al momento de cargar el código en el simulador se
genera un diagrama, donde se encuentran especificadas las entradas y los puertos
de salida, como se indica en la Figura 3.16.
Figura 3.16 Esquema de circuito Codificador RS(15,9).
Para comprobar el comportamiento del modelo se pueden editar los datos
ingresados como variables en el script de la siguiente manera:
9 EN
TRA
DA
S 15 SALID
AS
137
Palabra_0 <= X"0D";
Palabra_1 <= X"00";
Palabra_2 <= X"00";
Palabra_3 <= X"05";
Palabra_4 <= X"00";
Palabra_5 <= X"00";
Palabra_6 <= X"00";
Palabra_7 <= X"00";
Palabra_8 <= X"01";
Se han tomado los datos del ejemplo del capítulo anterior. Los valores a ingresar
deben estar en Hexadecimal.
Figura 3.17 Simulación del codificador RS(15,9).
9 EN
TRA
DA
S 15
SA
LID
AS
138
Se despliegan los resultados en la interfaz de simulación, como se indica en la
figura 3.17, los campos se encuentran identificados como palabra y pcod, los cuales
representan a la palabra de ingreso y la palabra codificada respectivamente. Los
valores de la palabra codificada son los mismos que se generaron en el
procedimiento del ejemplo en el capítulo anterior. Ya verificado el correcto
funcionamiento del algoritmo, se procederá a probar físicamente en la tarjeta.
Para la decodificación el simulador ISIM Simulator de Xilinx no procesa el algoritmo
creado, debido al nivel de procesamiento matemático requerido. Sin embargo al
momento de programar el algoritmo en la tarjeta, la FPGA funciona de forma
correcta.
3.5 IMPLEMENTACIÓN FÍSICA DEL CODIFICADOR Y
DECODIFICADOR RS (15,9)
Para la implementación física se utiliza la tarjeta FPGA SPARTAN 3E, donde se
cargará la configuración del algoritmo en VHDL. Para realizar las pruebas de
funcionamiento se han configurado la entrada y salida de los datos a través del
puerto serial. De esta manera el computador generará los datos, los cuales a través
del puerto serial se envían hacia la tarjeta, en donde se aplicará el algoritmo de
codificación cuando el usuario procede a ejecutarlo a través del botón EJECUTAR
presente en la interfaz gráfica como se explicará posteriormente. La palabra
codificada saldrá de la tarjeta por el mismo puerto serial hacia el computador donde
se presentará por medio de un display en SIMULINK. De la misma manera se
procederá la decodificación. En la Figura 3.18 se presenta el diagrama físico.
Figura 3.18 Sistema de comunicación entre PC y tarjeta FPGA.
139
3.5.1 GUIA DE USO DEL PANEL DE CONTROL DE ALGORITMOS
PROGRAMADOS EN TARJETA FPGA
Se implementará físicamente el circuito presentado, en la Figura 3.19 se muestra
la conexión física entre la tarjeta y el computador.
Figura 3.19 Prueba del codificador y decodificador RS en la tarjeta FPGA.
A continuación se presentarán los pasos a seguir para la utilización de la aplicación
y la ejecución del codificador y decodificador en la tarjeta FPGA:
1) En la Figura 3.20 se presenta la interfaz gráfica del menú principal, como se
explicó en el Capítulo 2, se tiene el botón FPGA, el cual al presionarlo se
desplegará la interfaz perteneciente a la tarjeta FPGA, como se indica en la
Figura 3.21.
140
Figura 3.20 Menú principal de la interfaz del codificador.
Figura 3.21 Interfaz para la ejecución en la tarjeta FPGA
141
2) En el campo perteneciente a la palabra de información se puede generar la
palabra de forma automática y aleatoria haciendo click en el botón GENERAR
o digitando manualmente la palabra de acuerdo al criterio del usuario, como se
muestra en la siguiente figura.
Figura 3.22 Ingreso de la palabra de información
3) Para poder ejecutar la codificación, se debe verificar en el circuito que los
puertos seriales a utilizarse en la comunicación entre el computador y la tarjeta
se encuentre bien seleccionado. Como se indica en la figura 3.23, el puerto de
comunicación por defecto es el puerto COM3, el cual debemos modificarlo para
escoger el puerto correcto.
Figura 3.23 Circuito de comunicación entre FPGA y PC.
4) Para conocer que puerto COM se encuentra activado al reconocer el cable de
conexión serial entre el computador y la tarjeta FPGA, se debe ir a “panel de
control” del computador como se indica en las figuras 3.24 y 3.25.
142
Figura 3.24 Menú de inicio de Windows
Figura 3.25 Pantalla de panel de control
143
En el panel de control seleccionamos “Administrador de dispositivos” (Device
Manager) y se desplegará la pantalla que se indica en la figura 3.26.
Figura 3.26 Pantalla de Administración de dispositivos.
Se despliega la pestaña “Puertos (COM & LPT)” donde se presentan los puertos
COM activos como se muestra en la figura 3.27.
Figura 3.27 Puertos serial activados en el computador.
5) Para modificar el puerto se debe hacer doble click en los bloques “Host serial
setup”, “Host serial TX” y “Host serial RX”, en los cuales se especifica un puerto
serial COM, de esta manera se abre la configuración del bloque, en su
configuración se observa una pestaña donde se puede modificar el puerto, como
se indica en la Figura 3.28.
144
Figura 3.28 Configuración del bloque de comunicación.
Al realizar este cambio pertinente, se podrá observar que en los bloques se
actualiza automáticamente el número de puerto a ser utilizado, como se indica en
la Figura 3.29.
Figura 3.29 Bloques de comunicación serial.
145
6) Posteriormente se debe configurar el puerto en el bloque controlador de la
comunicación, en donde también se especifica la velocidad de transmisión. En
la Figura 3.30 se presenta la pantalla de configuración del bloque con sus
respectivos parámetros.
Figura 3.30 Parámetros de configuración del bloque de control de
comunicación serial.
De esta manera, en la Figura 3.31 se presenta el diagrama de bloques configurado
con el puerto de comunicación serial que se utilizará en la comunicación entre el
PC y la FPGA.
Si no se configura de manera correcta el puerto serial en los bloques de
comunicación, el algoritmo no funcionará y se presentarán errores.
146
Figura 3.31 Diagrama de bloques de comunicación serial con sus
parámetros.
7) Posterior a la configuración se podrá ejecutar el codificador. Para esto, se debe
hacer click en el botón EJECUTAR y se desplegará un DISPLAY en SIMULINK,
donde se tendrá la palabra que se generó en el computador y salió a través del
puerto COM8 hacia la tarjeta FPGA. En la tarjeta FPGA se codifica y se
transmite nuevamente hacia el computador por el mismo puerto. En la figura
3.32 se muestra el DISPLAY y en la Figura 3.33 se presenta la interfaz de la
FPGA con la palabra codificada.
147
Figura 3.32 Display de Codificación en Simulink.
Figura 3.33 Interfaz FPGA con la palabra codificada recibida en PC.
INFO
RM
AC
IÓN
INFO
RM
AC
IÓN
P
AR
IDA
D
148
8) El Display presenta opciones de despliegue de información, se podrá cambiar
el formato del símbolo presentado, en la Figura 3.34 se observa la información
en binario, datos que ayudan a verificar los resultados de la simulación.
Figura 3.34 Display de codificación con los datos binarios.
9) Es posible insertar errores en la palabra codificada de dos maneras: digitando
los valores dados por el usuario en el campo palabra errada con una tolerancia
de hasta 3 errores, o generándolos aleatoriamente por medio del botón ERROR.
Figura 3.35 Ingreso de errores en el proceso de decodificación.
10) Al tener la palabra errada se procederá a decodificar, para esto se deberá hacer
click en el botón EJECUTAR como se presenta en la Figura 3.36.
Figura 3.36 Inicio de la Decodificación de una palabra errada.
149
11) Al hacer click en el botón EJECUTAR se desplegará un DISPLAY en
SIMULINK, donde se tendrá la palabra errada y la palabra decodificada después
de pasar por la tarjeta FPGA y regresar al computador. En la figura 3.37 se
presenta el DISPLAY, en la figura 3.38 se presenta el DISPLAY con datos
binarios y en la Figura 3.39 se presenta la interfaz de la FPGA con la palabra
decodificada.
Figura 3.37 Display de decodificación en Simulink.
Figura 3.38 Display de decodificación con los datos binarios.
INFO
RM
AC
IÓN
DEC
OD
IFICA
DA
PA
LAB
RA
ER
RA
DA
150
Figura 3.39 Interfaz FPGA con la palabra decodificada.
3.5.2 RECURSOS UTILIZADOS EN LA TARJETA FPGA SPARTAN 3E PARA EL
CODIFICADOR Y DECODIFICADOR RS (15,9)
La figura 3.40 presenta el resumen detallado en porcentaje del nivel de uso de la
tarjeta FPGA. En el campo “Number of Slices” se indica que se ha utilizado el 101%
de la tarjeta, esto se debe a que la Spartan 3E tiene un 5 % de reserva del cual se
ha utilizado el 1%.
Figura 3.40 Recursos utilizados en la tarjeta FPGA Spartan 3E para el
codificador y decodificador RS (15,9)
Al momento de sintetizar el algoritmo para el RS(204,188), este proceso no
culmina, por esta razón no será posible programar este algoritmo en la tarjeta
FPGA.
151
CAPÍTULO 4
CONCLUSIONES Y RECOMENDACIONES
En este capítulo se presentan las conclusiones y recomendaciones que se
obtuvieron a lo largo de la realización del proyecto de titulación.
4.1 CONCLUSIONES
· La complejidad de un algoritmo se define por medio del número de
operaciones elementales necesarias en la resolución de un problema y a su
vez las operaciones dependen del número de datos de entrada y de salida.
De esta manera la complejidad aumenta linealmente según sea el tamaño
de la información de entrada. Por esta razón se partió de un algoritmo
pequeño con 15 bytes de entrada, Reed-Solomon (15,9), y posteriormente
se replicó el algoritmo para el desarrollo del Reed-Solomon (204,188) con
255 bytes de entrada. El estudio, comprensión y visualización del código
Reed-Solomon es más fácil con un código de dimensiones pequeñas.
· La decodificación Reed-Solomon utiliza varios algoritmos para su resolución,
entre los cuales se encuentra Berlekamp-Massey, estos algoritmos limitan al
decodificador la corrección de errores cuando la palabra de información que
ingresa al receptor sobrepasa el número de errores permitidos por el
algoritmo. Al intentar decodificar una palabra que sobrepase el número
máximo de errores no se logra decodificar, llegando la información con
errores.
· El algoritmo Reed-Solomon (204,188) puede corregir 8 bytes de los 255
bytes que ingresan, cada byte posee 8 bits, por lo tanto tiene la capacidad
de corregir 64 bits siempre y cuando sean dentro de los mismos 8 bytes.
152
· El ruido ingresado en la señal durante su transmisión por el canal, con un
factor señal a ruido SNR=10, no debe superar un valor de potencia de ruido
de 0,13 watts en referencia a 1 ohm, para que la palabra que ingresa al
decodificador tenga un número de errores permitidos para su corrección.
· La herramienta de programación Matlab permite realizar funciones y
algoritmos que dependen de entradas variables o constantes según sea la
necesidad del usuario, por tal razón el algoritmo realizado es un genérico
para cualquier Reed-Solomon a implementarse. El lenguaje de Matlab es
flexible para realizar cálculos avanzados como los utilizados en el codificador
y decodificador Reed-Solomon.
· La tarjeta utilizada es la Spartan 3E, ya que es una tarjeta con múltiples
aplicaciones, fácil de conseguir en el mercado y su valor es accesible para
estudiantes. Tarjetas de mayor capacidad tiene costo alto.
· La tarjeta FPGA Spartan 3E es compatible con Matlab, por lo cual es factible
realizar la transformación de funciones generadas en Matlab a programas
en lenguaje VHDL.
· La tarjeta FPGA Spartan 3E posee una memoria limitada lo que permite un
número limitado de comandos. En la implementación el código Reed-
Solomon (15,9) se puede cargar en la tarjeta con un nivel de procesamiento
del 100% y su funcionamiento es el correcto. Para el código Reed-Solomon
(204,188) se satura la memoria de la tarjeta, por lo cual no es posible realizar
la implementación en la tarjeta propuesta, es necesario utilizar una tarjeta de
mayor capacidad para poder implementarlo físicamente.
· Para la decodificación el simulador ISIM Simulator de Xilinx no procesa el
algoritmo creado, debido al nivel de procesamiento matemático requerido.
Sin embargo al momento de programar el algoritmo en la tarjeta, la FPGA
funciona de forma correcta.
153
· Los cálculos matemáticos avanzados como la división en el proceso de
codificación de la palabra de información, presenta un cálculo muy extenso
y minucioso, por lo cual su uso es factible para algoritmos de pequeño
tamaño como el RS(15,9). Para algoritmos de mayor tamaño como el
RS(204,188) se procedió a usar el circuito de registro de desplazamiento con
retroalimentación lineal, el cual facilita el cálculo y posterior implementación
en lenguaje de programación.
4.2 RECOMENDACIONES
· Se recomienda en un proyecto futuro utilizar una tarjeta FPGA de alta
capacidad, para que su memoria soporte el algoritmo Reed-Solomon
(204,188) diseñado y desarrollado en el presente proyecto, ya que la tarjeta
FPGA Spartan 3E soporta algoritmos de baja capacidad.
· El cable para programar el algoritmo en la tarjeta FPGA no es reconocido
por Windows 8 y Windows 10, por lo tanto es recomendable utilizar Windows
7, en cambio para la comunicación serial entre el computador y la tarjeta
para envío de información funciona con cualquier versión de Windows.
· En la simulación del codificador desarrollado en este proyecto los resultados
se presentan en displays de Simulink, al terminar la presentación se requiere
cerrar estas ventanas, es recomendable que no se guarde ningún cambio en
los archivos debido a que puede generar fallos en futuros cálculos.
· En un futuro proyecto es recomendable elaborar la programación de este
tipo de algoritmos directamente en lenguaje VHDL y no la transformación de
un algoritmo del Matlab a VHDL para tratar de optimizar los recursos
utilizados en la tarjeta FPGA.
154
· Matlab por defecto no presenta paquete de comunicación serial compatible
con tarjetas programables como la FPGA, por lo que se recomienda instalar
el paquete de comunicación serial adjunto en el CD en el Anexo Y.
155
BIBLIOGRAFÍA
[1] ARCOTEL, Adopción del estándar para Televisión Digital Terrestre,
http://www.arcotel.gob.ec/wp-content/uploads/2015/07/Proyecto-
resoluci%C3%B3n-norma-tecnica-tdt.pdf
[2] Asociación Brasilera de Normas Técnicas, “ABNT NBR 15601:2007
Televisión digital terrestre – Sistema de transmisión ISDB-Tb”, 2007.
[3] Abramson Norman, “Teoría de la Información y Codificación”, Editorial
Paraninfo, quinta edición, Madrid, 1981.
[4] Haykin Simon, “Sistemas de Comunicación”, Editorial Limusa Wiley, cuarta
edición, New York, 2001.
[5] Artés Antonio, Pérez Fernando, “Comunicaciones Digitales”, Editorial
Limusa, primera edición, México, 2001.
[6] Benalcázar Hernán, “Fundamentos de Matemática”, segunda edición,
Impresión Hernán Benalcázar, Quito, 2014.
[7] Herstein I. N., “Álgebra moderna”, Editorial F. Trillas, S. A., primera edición,
México, 1970.
[8] Hall H. S. y Knight S. R., “Algebra Superior”, Editorial Hispano-América,
México, 1956.
[9] Gentile Enzo, “Estructuras Algebraicas I”, Editorial Eva V. Chesneau,
segunda edición, Buenos Aires, 1973.
[10] Gentile Enzo, “Estructuras Algebraicas II”, Editorial Eva V. Chesneau,
Buenos Aires, 1971.
[11] Espitia Jesus, Codificador Reed-Solomon en Software
http://tesis.ipn.mx/bitstream/handle/123456789/11486/44.pdf?sequence=1
[12] Perez Constantini, Transmisión de televisión
http://personales.unican.es/perezvr/pdf/Codificacion%20de%20Canal.pdf
[13] Casey Erin, Berlekamp-Massey Algorithm
http://www.math.umn.edu/~garrett/students/reu/MB_algorithm.pdf
[14] C.K.P. Clarke, Reed-Solomon error correction
http://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031.pdf
[15] Rao Farhat Masood, Adaptive Modulation (QPSK,QAM)
https://arxiv.org/ftp/arxiv/papers/1302/1302.7145.pdf
156
[16] Kundu Sudakshina (2010). Analog and Digital Communications. Pearson Education India. pp. 163–184. ISBN 978-81-317-3187-1
[17] STREMLER, Ferrel G., Introduction to Communications Systems, Second
Edition, Reading, Mass., Addison-Wesley, 1982.ISBN 0-201-07251-3
[18] D. Matie, "OFDM as possible modulation technique for multimedia
applications in the range of mm waves", Introduction to OFDM, II edition,
TUD-TVS. October 1998.
[19] Leonardo Jimenez, Joaquin Parrado, Carlos Quiza y Carlos Suarez,
Modulación Multiportadora OFDM
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&c
ad=rja&uact=8&ved=0ahUKEwja7tar1ZPKAhUKXB4KHdz6C5UQFggcMA
A&url=http%3A%2F%2Fdialnet.unirioja.es%2Fdescarga%2Farticulo%2F4
797263.pdf&usg=AFQjCNEVMBNhq0jUdoXpiZWKae2-
AEWc3g&bvm=bv.110151844,d.dmo
[20] Margarita Cabrera, Modulaciones Avanzadas: Parte 2 OFDM
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&c
ad=rja&uact=8&ved=0ahUKEwja7tar1ZPKAhUKXB4KHdz6C5UQFggqMA
I&url=http%3A%2F%2Focw.upc.edu%2Fdownload.php%3Ffi le%3D15011
931%2Fcom2_tema_5_teoria_2-
2777.pdf&usg=AFQjCNH_cPCMfAKfoa1f2c-
9nk3I7oDPEQ&bvm=bv.110151844,d.dmo
[21] Comparación de sistemas CP-OFDM con ZP-OFDM
http://bibing.us.es/proyectos/abreproy/11254/fichero/5_CAPITULO+1.pdf
[22] Fernández Marcos, Señales aleatorias y ruido
http://lmi.bwh.harvard.edu/papers/pdfs/1996/martin-
fernandezCOURSE96b.pdf
[23] Rodríguez Francisco, Distribuciones de Probabilidad Gaussiana
http://delta.cs.cinvestav.mx/~francisco/prope/Normal.pdf
[24] http://personales.unican.es/perezvr/pdf/CH8ST_Web.pdf
[25] Etter Delores, “Solución de problemas de ingeniería con Matlab”, Editorial
Prentice Hall, segunda edición, México, 1998.
[26] Simpsons P, “FPGA Design: Best Practices for Teambased Design”,
Editorial Springer, New York, 2010.
[27] Universidad de Málaga, Comunicaciones asíncronas (UARTS)
157
http://www.el.uma.es/marin/Practica4_UART.pdf
[28] Universidad Autónoma de San Luis de Potosí, Sistema de comunicación
serial.
http://galia.fc.uaslp.mx/~cantocar/microprocesadores/EL_Z80_PDF_S/22_
UART_2.PDF
[29] Kubler Academic Publishers, VHDL: Hardware Description and Design,
Boston.
[30] Kevin Skahill (Cypress Semiconductor), VHDL for PROGRAMMABLE
LOGIC, Massachusetts - Menlo Park, California - New York - Harlow,
England, etc.
[31] Neil H. E. Weste - Kamran Eshraghian, Principles of CMOS VLSI design. A
systems Perspective, massachusetts/California/New York/Ontario/Etc.
[32] Department of Electronic and Computer Engineering, University of Limerick,
Ireland, A Matlab conversion toolbox for digital control
http://alumni.cs.ucr.edu/~kstephen/ventilator/Grout_2000.pdf
ANEXOS
ANEXO A: Código fuente generación Polinomio Primitivo
ANEXO B: Código fuente generación Campo de Galois y tabla XOR
ANEXO C: Código fuente del Codificador Reed-Solomon (15,9)
ANEXO D: Código fuente del Generador De Error, RS(15,9)
ANEXO E: Código fuente del Algoritmo Síndromes, RS(15,9)
ANEXO F: Código fuente del Algoritmo BERLEKAMP-MASSEY, RS(15,9)
ANEXO G: Código fuente del Algoritmo Polinomio Localizador, RS(15,9)
ANEXO H: Código fuente del Algoritmo Polinomio Evaluador del Error, RS(15,9)
ANEXO I: Código fuente del Algoritmo Magnitud del Error, RS(15,9)
ANEXO J: Código fuente del Decodificador Reed-Solomon (15,9)
ANEXO K: Código fuente del Codificador Reed-Solomon (204,188)
ANEXO L: Código fuente del Modulador OFDM
ANEXO M: Código fuente del Generador de Ruido, RS(204,188)
ANEXO N: Código fuente del Demodulador OFDM
ANEXO O: Código fuente del Algoritmo Síndromes, RS(204,188)
ANEXO P: Código fuente del Algoritmo BERLEKAMP-MASSEY, RS(204,188)
ANEXO Q: Código fuente del Algoritmo Polinomio Localizador, RS(204,188)
ANEXO R: Código fuente del Algoritmo Polinomio Evaluador del Error,
RS(204,188)
ANEXO S: Código fuente del Algoritmo Magnitud del Error, RS(204,188)
ANEXO T: Código fuente del Decodificador Reed-Solomon RS(204,188)
ANEXO U: Código Fuente del Codificador y Decodificador Reed-Solomon (15,9)
en FPGA
ANEXO V: Código Fuente De La Simulación Del Codificador Reed-Solomon
(15,9) En FPGA
ANEXO W: Código Fuente Del Codificador Reed-Solomon (204,188) En FPGA
ANEXO X: Código Fuente Del Decodificador Reed-Solomon (204,188) En FPGA.
ANEXO Y: Instalación Paquetes De Comunicación Matlab
ANEXO Z: Interfaz Gráfica Principal (MAIN)
Los Anexos se encuentran en el CD adjunto.