Embed Size (px)
Citation preview
I
INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA
“Aplicaciones de los campos de Galois en el contexto de la corrección y detección de errores en comunicaciones basadas en los códigos BCH, con un enfoque didáctico”.
TESIS
QUE PARA OBTENER EL GRADO DE :
MAESTRO EN CIENCIAS EN INGENIERÍA DE TELECOMUNICACIONES
P R E S E N T A :
JORGE ROJAS BELTRÁN
DIRECTORES DE TESIS
M. EN C. MIGUEL SÁNCHEZ MERÁZ
Y
DRA. PATRICIA CAMARENA GALLARDO
MEXICO, D. F. 2008
SECCIÓN DE ESTUDIOS DE POSGRADO E INVESTIGACIÓN
II
III
IV
Resumen
Cada vez es más necesario en los currículos de cursos de ingeniería de telecomunicaciones profundizar en tópicos como la teoría de la información y la teoría de códigos, principalmente para entender el potencial de los sistemas de comunicaciones totalmente digitales. El propósito de este trabajo es confirmar la vinculación del álgebra de campos finitos de Galois con los codificadores de canal, donde estos últimos tienen utilidad en los sistemas de telecomunicaciones. Ello mediante simulaciones en matlab, programación de dispositivos CPLD’s con VHDL y gráficas de desempeño teórico para cada uno de los codificadores de canal más representativos. El resultado del documento es mostrar el desempeño en gráficas (Pe vs. SNR) de tres modelos: teórico, simulink y en hardware por implemntación en VHDL.
Abstract
Every time it is more necessary in the curriculum of telecommunications engineering courses to deep in topics how information theory an error control coding, principally to understand the potential of digital communications systems. The purpose of this thesis work is to confirm the link between Galois fields and coding channel, where coders of error control have utility en telecommunication system. It using simulations in matlab, programming devices how CPLD and graphics of theoretical performance by some BCH codes. The final result is to show graphics of Pe (error probability) vs. SNR of 3 models: theoretical, software simulation in simulink and hardware implementation in VHDL.
V
Objetivo
Establecer con elementos de simulación los principios matemáticos y de electrónica que caracterizan a los codificadores de canal, principalmente a los de tipo BCH, para comprender de manera didáctica la funcionalidad de codificadores más robustos.
Objetivos particulares
� Integrar un documento lo suficientemente accesible y detallado en el área de aplicación de los campos Galois en técnicas de codificación de canal, para que éste sea empleado en asignaturas de ingeniería y posiblemente de maestría en telecomunicaciones y telemática, como un recurso para elevar el potencial cognitivo de los estudiantes en dichos niveles.
� Analizar el desempeño teórico y práctico de los códigos BCH, mediante simulaciones en hardware y software.
� Comparar los resultados obtenidos con el modelo teórico y la simulación en Matlab y VHDL para
verificar su grado de concordancia. � Resaltar la vinculación que existe entre la teoría de los sistemas de telecomunicaciones y el álgebra
moderna, en especial la conexión entre la codificación de canal y los campos de Galois.
VI
Justificación
En diversas ocasiones durante los curso de ingeniería, las contenidos de algunas asignaturas, por ejemplo de teoría en comunicaciones y electrónica, se pierde por momentos los antecedentes de las estructuras o bases matemáticas que dan origen a alguna aplicación en los sistemas de comunicaciones; así como en los cursos de licenciatura en matemáticas no se aborda detalladamente la utilidad que alcanzan a tener los modelos matemáticos (campos de Galois) en algunas áreas de la ingeniería. También se puede mencionar que los estudiantes que cursan asignaturas como teoría de la información y teoría de códigos, tiene que recurrir a diversas referencias bibliográficas para tener un panorama, si no completo, de manera introductoria, que en ocasiones no es tan accesible de comprender ya que se cuenta con escasos ejemplo y muy pocas herramientas de simulación para verificar de manera didáctica, por ejemplo, el comportamiento de algún codificadores fuente o de canal. Por lo tanto, cada vez es más necesario en los currículos de cursos de ingeniería de telecomunicaciones profundizar en tópicos como la teoría de la información y la teoría de códigos, principalmente para entender el potencial de los sistemas de comunicaciones totalmente digitales. Asimismo, es fundamental que en los currículos de los cursos de ingeniería se establezca la vinculación entre disciplinas, en particular con la matemática, como lo establece la teoría educativa de la Matemática en el Contexto de las Ciencias.
VII
Introducción
Un primer propósito de este trabajo es el de comparar el desempeño teórico y práctico de los algunos codificadores BCH mediante simulaciones en Matlab, programación de dispositivos CPLD’s en VHDL y modelos matemáticos, el cual se verá reflejado en gráficos característico donde intervengan la relación señal a ruido y la probabilidad de error. Otro de los propósitos que se tiene la presente tesis es el de establecer la vinculación del álgebra de campos finitos de Galois con los codificadores de canal, donde estos últimos tienen utilidad en los sistemas de telecomunicaciones. Y el tercer propósito establece el enfoque didáctico tratado en el desarrollo del trabajo, el cual incluye dos perspectivas educativas. La primera es referente a la Matemática en Contexto (Camarena, 1984), en donde los campos de Galois se encuentran en el contexto de la corrección y detección de errores en comunicaciones. La segunda toma en cuenta la teoría de la elementarización, a través de la cual el lenguaje y las explicaciones se tornan claras y accesibles para el estudiante y se alude a los ejemplos. El documento aquí desarrollado pretende plasmar en tres grandes ejes temáticos otra visión en el estudio de los codificadores de canal, particularizando en la evaluación y caracterización de los códigos de tipo BCH. Esos tres ejes son: la teoría de las comunicaciones, los campos de Galois, y el aspecto didáctico, como se muestran en el mapa conceptual de la presente tesis.
Lógica digital
Codificación de canal
Códigos BCH
Campos d
e Galo
isComunicaciones
D i d á
c t i c a
S i m u l a c i o n e s
Hw y SwM
odelo
Mate
máticoRecursos de Program
ación Compe
ndio
did
áctic
o de
codi
ficac
ión
para
el co
ntro
l
de er
rore
s
Mapa conceptual de tesis
Lógica digital
Codificación de canal
Códigos BCH
Campos d
e Galo
isComunicaciones
D i d á
c t i c a
S i m u l a c i o n e s
Hw y SwM
odelo
Mate
máticoRecursos de Program
ación Compe
ndio
did
áctic
o de
codi
ficac
ión
para
el co
ntro
l
de er
rore
s
Mapa conceptual de tesis
VIII
La estructura de los capítulos está basada en este mapa conceptual, donde el capítulo I aborda de manera ilustrativa y concreta los objetivos y elementos de la teoría de la información, así como la diferencia entre la codificación fuente y de canal. Por su parte el capítulo II, describe mediante modelos teóricos y de simulación el comportamiento de un sistema de transmisión en banda base digital sin el uso de codificación de canal. El capítulo III está integrado por dos temas, el primero referente a las bases del álgebra moderna que se van a utilizar para fundamentar los códigos BCH, y el segundo propiamente sobre la caracterización de los códigos BCH. Fue necesario unificar estos dos temas ya que son los protagonistas de la dupla “fundamento-teórico y aplicación-tecnológica”. En este capítulo se prepararon ejemplos muy detallados para entender el porqué usar un polinomio generador en específico con base en la capacidad de corrección, así como también casos desglosados de los procesos de codificación y decodificación. El capítulo IV está dedicado a todo el conjunto de pruebas que fueron realizadas para evaluar el desempeño de los códigos BCH, principalmente con el parámetro de la BER y WER. Se especifican tres modelados durante el desarrollo del mismo, y que son el modelo teórico, el modelo en software (matlab-simulink) y el modelo en VHDL o de hardware (sacando provecho de la lógica digital que presentan los campos de Galois). El capítulo V trata de la obtención de conclusiones a partir de los resultados gráficos que brindó el capítulo IV mediante una inferencia comparativa de éstas. La parte de los anexos conjunta algunas tablas que se hacen referencia durante el trabajo, y en especial se presenta una breve biografía y cronograma del Evariste Galois, la cual refleja el breve e intempestivo vivir de un matemático, que junto con Claude E. Shannon, se debe en gran parte el presente trabajo.
IX
Índice
Capítulo ICapítulo ICapítulo ICapítulo I
Introducción a la codificación para el control de errores 1.1 Antecedentes, Teoría de la información 1. 1.2 Breve reseña del pensamiento de Claude Elwood Shannon (1916 - 2001) 2. 1.3 ¿Qué es la teoría de la información? 3. 1.4 Entropía máxima 6. 1.5 Antecedentes, Codificación de canal 8. 1.6 Tipos de errores 9. 1.7 Principales técnicas para la recuperación y corrección de errores 10. 1.8 Codificación FEC 10.
Capítulo IICapítulo IICapítulo IICapítulo II
simulación en software para el desempeño de sistemas de transmisión en banda base digital sin codificación de canal 2.1 Descripción de la prueba 12. 2.2 Comentarios sobre la simulación tipo Monte Carlo para la Pe vs. SNR 13. 2.3 Conclusiones sobre la simulación Monte Carlo para la Pe vs. SNR 17.
Capítulo IIICapítulo IIICapítulo IIICapítulo III
Códigos BCH 3.1 Bases del álgebra moderna para la codificación de canal 18. 3.2 Introducción a la Teoría de Grupos, Anillos y Campos 18. 3.2 Aritmética modular 21. 3.3 Protagonismo de los números primos 22. 3.4 Campo 25. 3.5 Introducción a la extensión de un campo 29. 3.6 Polinomio primitivo 30. 3.7 Construcción de la extensión de campo GF (2m) a partir de GF(2) 31. 3.8 Propiedades básicas de un campo GF (2m) 33. 3.9 Introducción a los códigos BCH 39. 3.10 Descripción general del caso binario 39. 3.11 Lineamientos de diseño para los codificadores BCH 40. 3.12 Lineamientos generales para el proceso de decodificación BCH 45. 3.13 Cálculo del síndrome 47. 3.14 Búsqueda del polinomio localizador de error 50. 3.15 Relación entre el polinomio localizador de error y el síndrome 52. 3.16 Introducción al caso del algoritmo de Berlekamp-Massey 53. 3.17 Estructuración del algoritmo de Berlekamp-Massey (BM) 56. 3.18 Determinación de las raíces del polinomio localizador del error (búsqueda de Chien) 58. 3.19 Determinación del polinomio patrón de error 60.
X
3.20 Caso para ejemplificar el proceso de decodificación BCH 60. 3.21 Implementación en hardware de los campos de Galois 67.
Capítulo IVCapítulo IVCapítulo IVCapítulo IV
Desarrollo de simulaciones para medir el desempeño de codificadores BCH 4.1 Descripción de las pruebas 73. 4.2 Modelo teórico 73. 4.3 Simulaciones del modelo teórico 81. 4.4 Resultados gráficos del modelo teórico 83. 4.5 Simulaciones por bloques de software en simulink 86. 4.6 Descripción y configuración de los bloques en simulink 86. 4.7 Resultados gráficos del modelo de simulación por bloques “simulink” 89. 4.8 Estructura de la simulación con elementos de hardware 92. 4.9 El codificador (coder) 93. 4.10 El decodificador (decoder) 96. 4.11 Resultados gráficos del modelo en hardware 99.
CAP VCAP VCAP VCAP V
Inferencia Comparativa
5.1 Desempeño comparativo 102. 5.2 Conclusiones 113. 5.3 Trabajos a futuro 113. Referencias 114.
CAP VICAP VICAP VICAP VI
Anexos
A1 Biografía de E. Galois A1. A2 Cronograma de E. Galois A7. A3 Tabla de SNR vs. Pe A9. A4 Listado del programa en VHDL para el codificador (15,7) A11.
1
Capítulo ICapítulo ICapítulo ICapítulo I
Introducción a la codificación para el control de errores 1.1 Antecedentes, Teoría de la información El objetivo del ingeniero en comunicaciones y electrónica es el de diseñar sistemas de modo que la información se transmita efectivamente al mismo tiempo y que satisfaga las siguientes limitantes de diseño:
energía de transmisión, ancho de banda de la señal y los costos permitidos. El objetivo de los sistemas de comunicación es el de transmitir información desde una fuente hasta un receptor pasando por su canal respectivo. Se puede citar que la información es: “inteligencia o conocimiento capaz de ser representado en formas adecuadas para comunicación, almacenamiento o procesamiento.” La teoría de la información se propone estudiar la eficiencia y fiabilidad de la información permitiendo evaluar matemáticamente el rendimiento de los diferentes sistemas de comunicaciones. En esta teoría, el término "información" no es el significado que cierto conjunto de signos o símbolos puede poseer para quién envía o recibe un mensaje, sino una cantidad específica de información del mensaje en cuestión, cualquiera que sea la forma en que ha sido emitido, el modo en que se ha transmitido y el sistema mediante el cual se recibe. En esencia, la cantidad especifica de información queda determinada por la “posibilidad de selección” contenida en los elementos que integran el mensaje (sorpresa, incertidumbre, interés).
La teoría de la información responde dos cuestiones fundamentales:
1.- ¿Cuál es la tasa final de compresión? Respuesta: Entropía (H) 2.- ¿Cuál es la tasa final de transmisión de la comunicación Respuesta: Capacidad del canal (C)
Esto tiene contribuciones fundamentales en:
� Física (Termodinámica)
� Ciencias de la computación (Complejidad de Kolmogorov o algoritmo de complejidad)
� Inferencia estadística (Occam’s razor: “La explicación más simple es la mejor”)
� Probabilidad y estadística (Información de Fisher)
� Economía (Teoría del portafolio, riesgo de Kelly).
2
Límite de compresión y de transmisión de los datos En la fig. 1.1 podemos observar cuáles son los límites tanto de compresión como de transmisión de datos en la teoría de las comunicaciones. Donde la tasa final de compresión es H y la tasa final de transmisión que es la información mutua máxima, C = máx I(A;B).
Fig. 1.1. Extremos teóricos de información en la teoría de las comunicaciones.1
1.2 Breve reseña del pensamiento de Claude Elwood Shannon (1916 - 2001)
En su trabajo de 1948 denominado “Una teoría matemática de la comunicación” (se concentra más en la información que en las señales en sí), Shannon se preguntó: ¿Cómo se representarán los mensajes para que la información sea conducida de la mejor manera?, con sus limitaciones físicas inherentes.
Fue uno de los primeros investigadores que relaciona las herramientas de probabilidad y estadística con la información transmitida en los sistemas de comunicación.
Antes del trabajo de Shannon, el trabajo de los matemáticos e ingenieros que trabajaban en la teoría de comunicaciones, era el de hallar formas en las cuales podía mantenerse la integridad de las señales analógicas que viajan en un cable, como una corriente eléctrica fluctuante, o a través del aire como una onda de radio modulada. Shannon tomó un enfoque muy diferente. El vio la "información" codificada completamente de manera digital, como una serie de 1's y 0's a los cuales se refiere como bits (binary information unit). Además de proveer a los ingenieros de comunicaciones con una metodología diferente de diseño de circuitos de transmisión, este cambio de enfoque también condujo al concepto "información" como un producto objetivo, desincorporado de "remitentes" ó "receptores" humanos. Después de Shannon la cuestión de importancia era ¿En qué forma se puede enviar, de la mejor manera, una secuencia de pulsos eléctricos ó electromagnéticos de un punto a otro? ________ 1
de la referencia Cover [36], pp 2.
Límite de compresión de los datos
Límite de transmisión de los datos
H máx I(A;B)
3
Una consecuencia particular de este nuevo enfoque, era que mientras aún una pequeña variación en una señal analógica distorsiona y puede, concebiblemente corromper la información transportada por esa señal, la naturaleza del si/no (on/off) de la señal digital significa que la señal transportada digitalmente es mucho menos propensa a corromperse.
En la teoría de Shannon lo que se mide es la cantidad de información que transporta una señal sin importar lo que denota esta señal.
Los tres puntos medulares de la teoría de la información de Shannon: Nueva medida para la velocidad de Información. Medida para la capacidad de transmisión de información del canal. Proceso de codificación para utilizar los canales a máxima capacidad.
1.3 ¿Qué es la teoría de la información?
La teoría de la información trata el problema de la eficiencia y fiabilidad en la transmisión de la información. Los dos principales tópicos relacionados a la TI son:
� Codificación Fuente: el problema de la eficiencia. � Codificación de Canal: el problema de la fiabilidad.
Eficiencia: Teniendo un código con una longitud promedio tan pequeño como sea posible, por ejemplo, códigos para letras que aparecen frecuentemente. Fiabilidad: La habilidad para procesar errores en la transmisión, por ejemplo, el envío de la misma secuencia varias veces, para recuperarla a pesar de los errores.
Codificación fuente y de canal
Codificación Fuente: Su objetivo es extraer la información esencial de la fuente y codificarla a un formato discreto de modo que se pueda guardar o transmitir mediante técnicas digitales. Codificación de Canal: Se agregan datos al tren de bits de la fuente para que el receptor pueda detectar y corregir errores provocados por el ruido presente en el canal.
"En esencia la codificación se emplea para acoplar la fuente al canal"
Es importante mencionar que dicha Teoría se encarga de analizar los símbolos que transmite una fuente, su cantidad y calidad en un sistema de comunicaciones y no el significado que el receptor puede darle a este grupo de símbolos (para el usuario o aplicación final).
4
Codificación fuente y de canal en un sistema de comunicaciones
Fig. 1.2. Sistema de comunicaciones a bloques. El procesador de la señal condiciona a la fuente para una transmisión más eficiente. Es aquí en donde se proporciona una “codificación fuente” de la señal de entrada. Además agrega bits de paridad a la palabra digital con lo que se produce “codificación de canal” con el propósito de que el receptor pueda detectar y corregir errores. Los circuitos portadores convierten la señal de banda base procesándola en una banda de frecuencia apropiada para el medio de transmisión del canal (señal pasa banda). El receptor captura la señal contaminada proveniente del canal, la convierte en banda base, limpia la señal y entrega una estimación de la información general.
La codificación fuente extrae la información más esencial a mandar de una fuente.
Teorema fundamental de la teoría de la información
Dada un fuente de información y un canal de comunicación, existe una técnica de codificación tal que la información se pueda transmitir sobre un canal a cualquier rapidez menor que la capacidad del canal y una frecuencia de errores arbitrariamente pequeña, no obstante la presencia del ruido.
5
Medida de la información Consideremos los siguientes titulares de algún periódico:
1. "El sol sale por el este"
2. "Estados Unidos invade Cuba"
3. "Cuba invade Estados Unidos"
4. "México ganará el próximo mundial"
P(1) = 1 - Apenas lleva información, o nula
P(2) ⇒ Escasa probabilidad pero finita - Trae mayor cantidad de información
P(3) ⇒ Casi imposible - Más información que las anteriores
P(4) ⇒ Imaginario - Sin comentarios
Tabla 1.1. Relación de la probabilidad y cantidad de información. Entre menos probable sea un evento mayor información “I” contendrá. Por lo tanto:
P → 1 P → 0
I → 0 I → ∞
Fórmula para la medida de la información “I”
La cantidad de información “I” enviada desde una fuente, cuando se transmite el mensaje xi, está dada por:
en unidades r-arias donde P(xi) es la probabilidad de xi, , y siendo IA = f(PA)
Los requisitos que debe cumplir tal función son:
� f(PA) ≥ 0 0 ≤ PA ≤ 1
� lim f(PA) = 0 PA→1
� f(PA)>f(PB) para PA<PB
� PC = PAPB donde A y B son estadísticamente independientes
� IC = f(PAPB) ⇒ f(PAPB) = IA + IB ⇒ IC = IA + IB
=
)(
1log)(
iri xP
xI Ec. 1.1
6
Se observa que la cantidad de información depende sólo de la probabilidad de enviar el mensaje y no de la posible interpretación del contenido, respecto a si tiene o no sentido. La base del logaritmo determina las unidades, es decir para r = 2, r = e y r = 10.
una manera rápida de conversión: 1 hartley = 3.32 bits
1 nat = 1.44 bits
[ ] [ ])(ln2ln
1)(log
2log
1)( 10
10iii xPxPxI
−=
−=
log2 υ = 3.32 log10 υ
1.4 Entropía máxima
Para ello hay que encontrar la distribución de probabilidades de los mensajes que produzcan la máxima entropía. Se espera que " H " sea máxima cuando todos los símbolos sean equiprobables. Comprobando el caso binario:
Ec. 1.2
Ec. 1.3
7
Calculando la entropía H de una fuente binaria y sin memoria con la ecuación 1.4:
== ∑∑
== )(
1log)()( 2
2
1
2
1 iii
iii xP
xPIxPH
−−+=
pp
PPH
1
1log)1(
1log 22
Fig. 1.3. Gráfica de la entropía de una fuente binaria.
Además el rango de valores posibles de H está acotado: 0 < H ≤ log2 q, donde “q” es el número de símbolos. Velocidad de entropía
Si se introduce el elemento tiempo en escena, supóngase que dos fuentes tienen igual entropía pero una es más rápida que la otra por lo tanto se producen más símbolos por unidad de tiempo. En estos casos la descripción de la fuente no reside totalmente en su entropía sino en su velocidad de entropía (bits/s).
La velocidad de entropía " R " de una fuente discreta es:
)(s
bitsHR
τ=
donde: τ es la duración promedio del símbolo
iτ → es la duración del símbolo xi
∑=
=q
iiixP
1
)( ττ
Ec. 1.5
Ec. 1.6
Ec. 1.7
Ec. 1.4
H
bits/símbolo
8
1.5 Antecedentes, Codificación de canal El “BER” es habitualmente el parámetro más importante a tener en cuenta, desde el punto de vista de los diseñadores de sistemas de comunicación. La velocidad de transmisión de la información es también decisiva, ya que el diseñador desea transmitir información a cierta tasa de símbolos R (velocidad o tasa de entropía), necesidad que viene determinada por cada aplicación. Otros criterios de diseño incluyen:
* Complejidad * Costo * Peso del equipo
* Disipación de calor * Tolerancia a fallos * Ancho de banda consumido
Esto deja poca flexibilidad al proceso de diseño ya que según nuestro razonamiento simplista parece indicar que: una vez seleccionado el formato de modulación, la velocidad de encapsulamiento de salida y el BER, éstos determinan el nivel de potencia del transmisor, que a su vez determina el peso de la batería, la disipación térmica y otros factores. En algunos casos, este análisis puede indicar que la construcción del sistema deseado es físicamente imposible. Por ejemplo, en el diseño de un satélite de comunicaciones, la ecuación potencia/velocidad/BER puede llegar a dictar un nivel de potencia P mayor del que puede ser proporcionado por los amplificadores de las ondas portadoras o los amplificadores de estado sólido disponibles para las construcciones de satélites. En otro ejemplo, podemos encontrar que las necesidades de potencia para el diseño de un teléfono móvil indican el uso de baterías del tamaño más bien para la espalda de un elefante que para el bolsillo de una camisa. Hubo un tiempo en el que estos obstáculos resultaban insuperables. Sin embargo a finales de los 40 los trabajos de Shannon y Hamming en los Laboratorios Bell sentaron las bases para los códigos de control de error, un campo que hoy nos proporciona un conjunto de técnicas potentes para alcanzar las BER deseados con potencias de transmisión bajas. Estos caballeros atacaron el problema del control de error en canales con ruidos usando técnicas completamente diferentes. Shannon utilizó un enfoque estadístico/existencial mientras que Hamming podría decirse que utilizó un planteamiento combinatorio/constructivo. Consecuentemente, sus resultados fueron también radicalmente distintos: Shannon encontró los límites para el control de errores ideal, mientras que Hamming mostró la manera de construir y analizar los primeros sistemas de control de error prácticos.
Existen tres tipos distintos de codificaciones en las comunicaciones digitales: Códigos Fuentes (eliminan redundancia), Códigos de Confiabilidad y Secretos, por último, Códigos para el Control de Errores los cuales hacen uso de la Matemática discreta como del álgebra moderna.
9
La detección de errores
El decodificador puede reaccionar ante la detección de un error de tres maneras diferentes:
� Pedir una retransmisión de la palabra
� Tomar la palabra como incorrecta e ignorarla
� Tratar de corregir los errores de la palabra recibida.
La petición de retransmisión es utilizada en un conjunto de estrategias de control de errores denominado petición automática de repetición (ARQ = Automatic Repeat Request). Para ello es necesario que exista un enlace bidireccional entre el transmisor y el receptor y que la información inicial todavía esté disponible. La segunda opción se denomina comúnmente como “mutting". Es típica de aplicaciones en las que los retrasos no permiten la retransmisión de la palabra transmitida y parece mejor dejar la palabra recibida como un valor "apagado" que intentar corregir los errores. (p.e. comunicación por voz y audio digital). La opción final se denomina corrección del error (FEC=Forward Error Correction). En los sistemas FEC la estructura aritmética o algebraica del código se utiliza para determinar cuáles de las palabras código válidas han sido enviadas, dada la palabra errónea recibida.
1.6 Tipos de errores
Aleatorios (Random) Canales sin memoria Comunicación satelital
De espacio profundo (deep-space)
Ráfagas (Burst) Canales con memoria Radio / cable
diafonía,
desvanecimiento (fading)
Compuesto Random-Burst Características atmosféricas
extremas, pérdida del enlace
por bastante tiempo (meteor-burst)
Tabla 1.2. Clasificación de los errores en los sistemas de comunicaciones.
10
1.7 Principales técnicas para la recuperación y corrección de errores
Técnica Aplicaciones Tipos
ARQ (Automatic Repeat Request)
Retransmisión de bloque detectado por el receptor
con error.
Modo Duplex
Distancias cortas
LAN’s (ACK)
"Stop and wait" "Go back N"
"Selective reject"
Ventana deslizante
en conjunto con el CRC
FEC (Forward Error Correction)
Corrección de errores anticipada ó adelantada,
donde los datos transmitidos se codifican de modo que el receptor pueda detectar y
corregir los errores.
Modo Simplex
Comunicaciones con largas demoras en la transmisión
Códigos de Bloque
Códigos Cíclicos
RS, BCH, RM
Códigos convolucionales
“Turbo Codes”
Tabla 1.3. Principales técnicas para el control de errores. 1.8 Codificación FEC
Otra motivación pragmática para el uso de dicha codificación radica en la reducción de Eb/No requerida para una tasa de errores en bits fija (BER). Esta reducción en Eb/No puede explotarse para reducir la potencia transmitida necesaria para o reducir los costos en el hardware Existen muchos códigos diferentes para la corrección de errores (con fundamento en varias disciplinas matemáticas) que se pueden utilizar. Desde hace tiempo, estos códigos se han clasificado en códigos de bloque y códigos de convolución. La característica distintiva para dicha división es la presencia o ausencia de memoria en los dos codificadores. El principio de funcionamiento de un codificador de bloque (n,k) consiste en aceptar información en bloques sucesivos de k dígitos, y en cada bloque agrega n - k dígitos redundantes que se relacionan algebraicamente con los k dígitos del mensaje original, produciendo por lo anterior un bloque codificado completo de n dígitos, donde n > k.
11
Este último bloque de n dígitos se denomina palabra de código. Un codificador de canal produce bits a razón de
SRk
nR
=0
donde : RS � (b/s) tasa de bits de la fuente de información
η = k/n � tasa de código ó eficiencia del codificador (0 < η < 1)
R0 � (b/s) tasa de bits a la salida del codificador o “tasa de datos del canal”
En un código convolucional, la operación de codificación puede entenderse como la propia convolución en tiempo discreto de la secuencia de entrada con la respuesta al impulso del codificador. La duración de la respuesta al impulso es igual a la memoria del codificador. Por lo tanto, el codificador de convolución opera sobre la secuencia del mensaje entrante, empleando una “ventana de desplazamiento” igual en duración a su propia memoria.
Segundo teorema de Shannon (teorema de codificación de canal)
El Teorema de codificación de canal establece que si un canal sin memoria discreto tiene capacidad C y una fuente genera información a una tasa menor que C, existe entonces una técnica de codificación tal que la salida de la fuente puede transmitirse por el canal con una probabilidad de error de símbolo arbitrariamente baja. Para el caso especial de un canal simétrico binario, el teorema nos indica que si la tasa de código r es menor que la capacidad C del canal, entonces es posible encontrar un código que logre una transmisión sin errores por el canal. De manera opuesta, no es factible un código de este tipo si la tasa de código r es mayor que la capacidad C del canal. El anterior teorema especifica a la capacidad C del canal como un límite fundamental sobre la tasa a la cual puede llevarse a cabo la transmisión confiable (sin errores) de mensajes por un canal sin memoria y discreto. He aquí el énfasis de la codificación a la entrada del canal sobre el parámetro suficientemente grande de la relación señal a ruido (S/R, o en inglés SNR). La parte menos concreta de dicho teorema es su poca naturaleza de diseño. El teorema asegura la existencia de “buenos códigos” pero no dice cómo determinarlos, aunque la parte loable es el establecimiento de tal límite sin haberse desarrollado un algoritmo de código de canal tal cual. Por “buenos códigos” se refiere a un conjunto de códigos de canal que son capaces de proporcionar transmisión de información confiable (probabilidad de error pequeña) por un canal ruidoso a tasas de bit hasta un valor máximo menor que la capacidad de dicho canal.
Ec. 1.8
12
Capítulo IICapítulo IICapítulo IICapítulo II
simulación en software para el desempeño de sistemas de transmisión en banda base digital sin codificación de canal
2.1 Descripción de la prueba
Las pruebas desarrolladas en el presente capítulo tienen como objetivo evaluar el desempeño de un sistema digital de banda base con transmisión de señales unipolar NRZ y antipodal, sin la utilización de codificador de canal alguno.
(a) (b)
Fig. 2.1. Ejemplos de señal (a) antipodal y de señal (b) unipolar NRZ (on-off).
Para medir tal desempeño, se graficará la probabilidad de error (Pe) vs. la relación señal a ruido SNR, tanto para el caso del modelo matemático (fórmula), como para una simulación de tipo Monte Carlo. Lo anterior permitirá de primera instancia, tener una referencia para comparar el desempeño de los codificadores BCH a desarrollar en los siguientes capítulos. Para llevar a cabo lo anterior, se tuvieron las siguientes consideraciones:
� Se utiliza un canal simétrico binario (BSC) con probabilidad de error en transición (p) en función a la SNR con AWGN.
� Las probabilidades de enviar un “0” y un “1” son las mismas, (probabilidades iniciales o a priori equiprobables P0 = P1)
� El receptor está bajo la detección de un filtro acoplado � No hay problemas de ISI; perfecta sincronía
t
A
s0(t)
Dígito “1”
t
-A
s1(t)
Dígito “0”
Tb t
A
s0(t)
Dígito “1”
t 0
s1(t)
Dígito “0”
Tb Tb Tb
Cíclo reloj Cíclo reloj
13
Se utilizaron las siguientes fórmulas: --para señal unipolar--
=
=
00 22
1
N
Eerfc
N
EQP bb
e
--para señal antipodal--
=
=
00 2
12
N
Eerfc
N
EQP bb
e
Fig. 2.2. Grafica de la Pe vs. SNR en los casos de una señal antipodal y unipolar NRZ.
Ec. 2.2
Ec. 2.1
14
2.2 Comentarios sobre la simulación tipo Monte Carlo para la Pe vs. SNR La simulación de Monte Carlo es una técnica computacional que hace uso de números aleatorios. Los objetivos de esta simulación son los de resolver uno o dos de los siguientes problemas:
- generar muestras provenientes de una distribución de probabilidades p(x) dada - estimar la media de una función bajo la fdp p(x) dada.
Para el rubro que nos ocupa, se implementó dicha técnica para estimar la probabilidad de error de un sistema de comunicación digital, mediante el siguientes diagrama a bloque, del cual sobresalen un módulo generador de datos aleatorios, un detector de nivel según el umbral y un comparador de datos, donde al final se contabilizan los errores que son después presentados en graficas de Pe vs. SNR
Fig. 2.3. Diagrama a bloque de la simulación Monte Carlo implementada para Matlab. Este esquema (fig. 2.3) muestra la generación de una variable aleatoria r, la cual es la entrada a un detector. Se implementa un generador de números aleatorios uniforme para simular la secuencia de información binaria proveniente de una fuente de datos binario. Las secuencias de 0’s y de 1’s es mapeada dentro de una secuencia de ±E , donde E representa la energía de la señal. Para este caso E se normaliza al valor unitario. Además, un generador de ruido gaussiano se utiliza para obtener la secuencia de números aleatorios gaussianos con media cero y varianza σ 2 . El detector compara la variable aleatoria r con umbral de 0 (cero). Si r > 0, la decisión a tomar es de que se transmitió el bit
“0”. Si r < 0, entonces ahora la decisión a tomar es de que se transmitió el bit “1”. La salida del detector es comparada con la secuencia trasmitida en bits, y es entonces cuando el contador de errores actúa.
Generador de números aleatorios
(Uniforme) N= # de datos a
generar
Detector
Generador de números aleatorios
(Gaussiano)
Fuente de datos binarios
Comparador
Contador de errores
+
Salida de datos
±E n
r
15
Para las primeras simulaciones se consideraron la transmisión de un tren de 10,000 bits de información, los cuales se vieron afectados por diferentes valores de SNR. Pero hay algunas de mayor longitud que requirieron mayor tiempo de CPU para poderlas terminar (N=1,000,000).
Fig. 2.4. Gráficas de las simulaciones Monte Carlo implementadas para Matlab, con una corrida de 10,000 dígitos binario.
Como se observa en la fig. 2.4, el desempeño de la Pe para la señal antipodal con base en el modelo de Monte Carlo (en *) se ajusta en sus primeros seis valores (de 0 a 5 dB’s) a la curva de Pe obtenida por la ec. 2.1 (línea continua), mientras que el resto comienza a separarse por la cantidad de datos simulados. En las siguientes pruebas de Monte Carlo se evaluaron más puntos de SNR como de dígitos binarios, como se puede observar en las figuras 2.5, 2.6 y 2.7.
Teórico
* Simulación
16
Fig. 2.5. Gráfica de la segunda prueba para simulación Monte Carlo, con una corrida de 10,000 dígitos binario.
Fig. 2.6. Gráfica de la simulación Monte Carlo implementada para Matlab, con una corrida de 10,000
dígitos binarios, con más puntos de prueba.
Teórico
* Simulación
Teórico
* Simulación
17
Fig. 2.7. Gráficas de la simulaciones Monte Carlo implementadas para Matlab, con una corrida de
1,000,000 de dígitos binario. 2.3 Conclusiones sobre la simulación Monte Carlo para la Pe vs. SNR Se puede observar que la simulación de Monte Carlo se aproxima de manera muy cercana a la curva del desempeño teórico de la gráfica de Pe vs. SNR antipodal, sin embargo, habrá que realizar mayores corridas en los valores de N, para llegar a tasas de errores más bajas y observar que tanto error de aproximación ofrecen las dos modalidades. Es decir, a mayor SNR habrá que incrementar el número de símbolos binarios a transmitir para alcanzar las tasas de error esperadas.
Teórico
* Simulación
Teórico
* Simulación
18
Capítulo IIICapítulo IIICapítulo IIICapítulo III
Códigos BCH
3.1 Bases del álgebra moderna para la codificación de canal
Los sistemas algebraicos son estructuras que satisfacen ciertas reglas o leyes, las cuales casi siempre son las mismas que aplicamos en nuestros sistemas de numeración ordinarios. Dichas estructuras son deseables en los códigos correctores de error por dos razones: facilitan la búsqueda de propiedades de un código, y llevan a cabo la instrumentación de códigos prácticos. En general en toda la teoría de códigos se suelen trabajar en conjuntos cuyo alfabeto es bastante restringido. Es aquí donde el álgebra abstracta y la aritmética modular apoyan las aplicaciones de los sistemas de comunicaciones, tales como almacenamiento y transmisión de datos en redes telemáticas, donde el alfabeto de símbolos posible es el conjunto {0,1}. Con respecto a la aritmética modular se puede mencionar que ésta es una parte de las matemáticas extremadamente útil, tanto en la corrección de errores como en la criptografía dentro de los sistemas de comunicaciones digitales, ya que permite realizar cálculos complejos y plantear problemas interesantes, manteniendo siempre una representación numérica compacta y definida, puesto que sólo maneja un conjunto finito de números enteros. Muchos estudiosos la conocen como la aritmética del reloj, debido a su parecido con la forma en que llevamos la contabilidad del tiempo. Por ejemplo, si son las 19:13:59 y pasa un segundo, se dice que son las 19:14:00, y no las 19:13:60. Como se puede entender, los segundos al igual que los minutos, se expresan utilizando sesenta valores cíclicamente, de forma que tras el 59 viene de nuevo el 0. Desde una perspectiva formal diríamos que los segundos se expresan en módulo 60. A continuación se describirán los bloques de construcción fundamentales del álgebra abstracta, la cual abordaremos con mayor detalle durante este capítulo. 3.2 Introducción a la Teoría de Grupos, Anillos y Campos En el álgebra abstracta o también conocida como álgebra moderna se tienen ciertos sistemas básicos o simplemente conjuntos cuyos elementos podemos operar algebraicamente, es decir que se pueden combinar dos elementos del conjunto, quizá de varias maneras, para obtener un tercer elemento también del conjunto, y además se supone que estas operaciones algebraicas están sujetas a ciertas reglas que se indican explícitamente en lo que se llaman axiomas o postulados definitorios del sistema. En este apartado se expondrán distintos teoremas dentro del marco abstracto que integran estructuras generales como grupos, anillos y campos, con el objetivo de relacionar sus propiedades con aplicaciones específicas dentro del área de los sistemas de comunicaciones. Es imperativo resaltar que los anteriores sistemas algebraicos son sistemas que satisfacen ciertas reglas o leyes, y que en la mayoría de los casos, esas son las mismas leyes que se aplican en nuestros sistemas ordinarios de numeración. Así un grupo es un sistema con una operación y su inversa, tales como la adición y su inversa que es la substracción, o la multiplicación y su inversa que es la división. Un anillo tiene dos operaciones, adición y multiplicación, y la operación inversa de la primera (resta).
19
Un campo tiene las dos operaciones básicas anteriores, ambas con sus operaciones inversas. Por convención, la notación para las dos principales clases de operaciones sobre el conjunto de elementos de las anteriores estructuras, es usualmente la misma notación que se utiliza para representar a las operaciones de adición y multiplicación que estamos acostumbrados a utilizar dentro de los sistemas numéricos ordinarios. No obstante, es importante hacer notar que en álgebra abstracta, no se está limitado a las operaciones aritméticas tradicionales. En el siguiente cuadro sinóptico, se especifican los distintos axiomas y teoremas que dan lugar a las estructuras algebraicas anteriormente citadas.
(A1) Cerradura bajo adición
Si a y b pertenecen a G, entonces a+b está también en G.
(A2) Asociativa de la adición
a+(b+c)=(a+b)+c para todo a, b, c en G.
(A3) Elemento identidad adición
Hay un elemento 0 Є G tal que a+0=0+a=a para todo a en G.
(A4) Inverso aditivo Para cada a en G hay un elemento –a en G tal que a+(-a)=(-a)+a=0.
(A5) Conmutativa de la adición
a+b=b+a para todo a, b en G.
(M1) Cerradura bajo multiplicación
Si a y b pertenecen a R, entonces a • b está también en R.
(M2) Asociativa de la multiplicación
a • (b • c)=(a • b) • c para todo a, b, c en R.
(M3) Leyes distributivas
a • (b+c)=a • b + a • c para todo a, b, c en R.
(a+b) • c=a • c + b • c para todo a, b, c en R.
(M4) Conmutativa de la multiplicación
a • b = b • a para todo a, b, c en R.
(M5) Elemento identidad multiplicación
Hay un elemento 1 en R tal que a • 1 = 1 • a = a para todo a en R.
(M6) No posee divisores cero
Si a y b están en R y a • b = 0, por lo tanto a=0 o b=0.
(M7) Inverso multiplicativo de elementos no cero
Si a pertenece a F y a ≠ 0, hay un elemento a-1 en F tal que a • a-1 = a-1 • a = 1.
Fig. 3.1. Cuadro sinóptico sobre las estructuras del álgebra moderna.
GRUPO
GRUPO
ABELIANO
ANILLO
CONMUTATIVO
ANILLO
DOMINIO
ENTERO
CAMPO
Anillo con elemento unitario
20
En el siguiente cuadro se muestran algunas propiedades resumidas de los grupos, anillos y campos: Grupo Conjunto de elementos que pueden ser operados (+ o •) sin salirse del conjunto.
Anillo Conjunto de elementos donde se definen 2 operaciones tal que los elementos pueden ser sumados, restados y multiplicados sin salirse del conjunto.
Campo Conjunto de elementos con 2 operaciones y sus inversos tal que los elementos pueden ser sumados, restados, multiplicados y divididos sin salirse del conjunto.
Operación módulo-n
Dados cualquier entero n y cualquier entero a, si se divide a entre n, habrá un entero cociente q y un entero residuo r que obedecen la siguiente expresión:
rqna += , nr <≤0 ;
=n
aq
donde x es todo entero mayor que es menor o igual a x.
Fig. 3.2. Valores que intervienen en la descripción del módulo n. La fig. 3.2 muestra en una línea numérica a dos enteros cualesquiera (a, n positivo), en la cual siempre es posible encontrar q y r que satisfagan la relación a = qn + r; y donde a puede caer en algún lugar de dicha recta (para este caso a cae en lado positivo de la recta). Iniciando desde 0, se procede a ubicar n, 2n, hasta qn tal que qn ≤ a y (q + 1)n > a. La distancia desde qn hasta a es r, y por lo tanto se han encontrado los valores únicos de q y r. Por ejemplo: a = 11; n = 7; 11 = (1 × 7) + 4; r = 4 a = -11; n = 7; -11 = [(-2) × 7] + 3; r = 3 Si a es un entero y n es un entero positivo, se definirá al módulo n de a (a mod n) como el residuo de dividir a entre n. Así, para cualquiera entero a, se puede escribir lo siguiente:
)mod( nann
aa +×
=
0 1 2
n 2n 3n qn a (q +1) n
r
n
21
Siguiendo los ejemplos, se tiene que: 11 mod 7 = 4; -11 mod 7 = 3 Congruencia Dos enteros a y b se dicen ser congruentes módulo n, si (a mod n) = (b mod n). Lo anterior se escribe como:
nba mod≡ Siguiendo con ejemplos, se tiene que: 73 ≡ 4 mod 23; 21 ≡ - 9 mod 10 3.2 Aritmética modular Si m es un entero positivo, Zm denota el conjunto de los enteros módulo-m, es decir:
Zm ={0,1, . . . , m-1}.
A partir de este conjunto se podrán definir operaciones tales como la suma y el producto. Definición D3.1. Sean x, y Є Z. La suma de x y y en Zm es el residuo que resulta de dividir x + y Є Z entre m. Análogamente el producto de x y y en Z, es el residuo que resulta de dividir x • y Є Z entre m. Nótese que con esta definición Zm es un conjunto cerrado bajo la suma y producto módulos-m. Ejemplo, para Z5: 2 + 4 = 1 y 2 • 4 = 3 A la terna ⟨ Zm, +, • ⟩ es a lo que se designará como los enteros módulo-m, y que a partir de este momento se simplificará su notación a Zm. Las tablas 3.3 y 3.2 muestran un ejemplo de los enteros módulo-2, el cual es el caso más utilizado en áreas de ingeniería, principalmente en la de electrónica y comunicaciones.
++++ 0 1 × × × × ó • 0 1 0 0 1 0 0 0 1 1 0 1 0 1
Tabla 3.1. Suma módulo-2. Tabla 3.2. Multiplicación módulo-2.
22
3.3 Protagonismo de los números primos En este apartado se pretende resaltar la importancia que tienen los números primos en la aritmética modular, los cuales a se vez, también son protagonistas fundamentales para la estructuración de los campos, que se analizarán más adelante. Primeramente, se puede hacer notar que 4 • 2 = 0 en Z8, pero 4 y 2 son, ambos, distintos de cero. Sería deseable que cuando un producto sea cero al menos uno de los operadores sea cero. Y entonces se hace pregunta: ¿Qué se requiere para que ocurra esto? Supongamos que a • b = 0 Є Zm, es decir:
a • b ≡ 0 (mod-m)
Para que esto suceda se necesita que m(a • b), es decir, “m un divisor de (a • b)”. Por lo tanto, se tiene el siguiente teorema. Teorema T3.1. Sean a, b Є Zp, y a • b = 0 en Zp implica que a = 0 o b = 0 sí y sólo sí p es primo. Suponiendo que a • b = 0 en Zp. Esto significa que (a • b) ≡ 0 mod-p y por lo tanto p(a • b). Dado que p es primo entonces ocurre alguna de las siguientes dos cosas:
� pa, lo que significa que a ≡ 0 mod-p, es decir a = 0 en Zp � pb, lo que análogamente significa que b = 0 en Zp
También se puede demostrar lo anterior, suponiendo que p no es primo y que no es cierto que si el producto de a y b es cero, a o b son cero. Sin embargo, lo que interesa es visualizar la importancia de los números primos para valores de m a utilizar en multiplicación módulos-m. Lo anteriormente analizado, es el preludio de los llamados “divisores cero”, los cuales se hace referencia por primera vez en el cuadro sinóptico 1, y que se definen prácticamente como los elementos a, b Є Zm y que al ser operados en multiplicación mod-m su resultado es cero, donde ninguno de los dos es cero mod-m (a y b son divisores cero), y ello por el simple hecho de que m no es primo. Esta peculiaridad no la deben presentar las estructuras que más adelante se abordarán en la tesis, y que son los denominados campos. A continuación se presentan tablas para la multiplicación módulo-m, con diferentes valores de m (primo y no primo), con el fin de ejemplificar lo aquí expuesto.
23
×××× 0 1 2 ×××× 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 1 0 1 2 1 0 1 2 3 4 2 0 2 1 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1
Tabla 3.3. Multiplicación módulo-3. Tabla 3.4. Multiplicación módulo-5.
×××× 0 1 2 3 ×××× 0 1 2 3 4 5 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 1 0 1 2 3 4 5 2 0 2 0 2 2 0 2 4 0 2 4 3 0 3 2 1 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1
Tabla 3.5. Multiplicación módulo-4. Tabla 3.6. Multiplicación módulo-6. Como se puede observar, la propiedad de divisores cero sólo se presenta en las tablas de multiplicación mod-4 y mod-6 (m no primo), inclusive en estas mismas tablas se pueden detectar (con letra cursiva) productos del mismo valor provenientes de elementos de una misma columna o fila, por ejemplo: (2 x 1) mod 4 = 2 y (2 x 3) mod 4 = 2; o (3 x 1) mod 6 = 3; (3 x 3) mod 6 = 3 y (3 x 5) mod 6 = 3 Los presentes casos, por no provenir de un número primo, propician que los productos entre diferentes elementos se repitan, pero lo más critico es que a la hora de calcular sus inversos multiplicativos, dichos elementos no lo tendrán, por lo que no se podrá realizar la división entre algunos de ellos; por lo anterior se citan los siguientes teoremas. Teorema T3.2. Zm es un campo sí y sólo sí m es primo. Para la demostración de este teorema, primeramente se comprobará uno que hace referencia directamente a los enteros módulo-m, y después en su oportunidad se abordará lo que corresponda en el apartado de campos. Teorema T3.3. En Zm todos los elementos distintos de cero tienen un inverso multiplicativo sí y sólo sí m es primo. Para su demostración se optará por la negación de la hipótesis. Es decir, si m no es primo entonces no todos los elementos de Zm tienen inverso.
24
Si m no es primo significa que es divisible entre algún número distinto de 1 y de m mismo. Significa que m = a • b con a y b enteros distintos de cero y menores a m. Pero entonces a, b Є Zm y como el producto de ellos es m por lo tanto a • b = 0 en Zm. Ahora por otra parte, si a tuviera inverso a-1 entonces se tendría: b = a-1 • (a • b) = a-1 • 0 = 0 Pero se había establecido que b era distinto de cero, así que esto es una contradicción. Por lo tanto a no tiene inverso, con lo cual existe un elemento en Zm sin inverso multiplicativo. Otra manera de demostrar lo anterior, es establecer una hipótesis donde ahora m sea primo, y se deberá deducir que todos los elementos de Zm tienen inverso. Sea a un elemento cualquiera de Zm. Considerando por el momento que todos los productos de la forma a • b donde b Є Zm. Si hubiera un par de elementos b, b’ Є Zm distintos entre sí pero que dieran el mismo producto al multiplicar por a, se tendría que b ≠ b’ y a • b = a • b’, es decir:
(a • b) ≡ c mod-m y (a • b’) ≡ c mod-m Por lo consiguiente, al dividir a • b entre m se tiene el mismo residuo del que resulta de dividir a • b’ entre m, es decir:
ab = km + c
ab’ = k’m + c Si el residuo es el mismo y el divisor también, sólo basta con recordar un momento el algoritmo de la división para implicar que también los cocientes son los mismos. Esto es:
k = k’ Entonces b debe ser también igual a b’ lo que contradice la hipótesis inicial. Así que no pueden haber dos productos iguales (como se pudo observar en los ejemplos anteriores de las tablas de multiplicación con m no primo, los cuales tenían productos iguales), ya que para todo b Є Zm el producto de a • b es un elemento distinto de Zm. Por lo que en total hay m productos distintos, todos ellos en Zm, entonces el conjunto de todos los posibles productos es exactamente todo Zm y debe haber algún producto que sea igual a 1, (esto también se pudo comprobar en las tablas de multiplicación módulo-m con m primo). Finalmente, existe algún b Є Zm tal que a • b = 1, luego a, un elemento cualquiera de Zm tiene inverso. De hecho en un conjunto Zm un elemento a tiene inverso multiplicativo si a es primo relativo de m. Esto es más global de lo que se acaba de demostrar, porque si a es primo entonces cualquier elemento en Zm resultará primo relativo de m, así que todos los elementos de Zm tendrán inverso. Esta generalización se comentará en el siguiente apartado relativo a los campos de Galois.
25
3.4 Campo Un campo es un conjunto de elementos que pueden ser operados de acuerdo a reglas que satisfacen ciertas propiedades, que se han mencionado brevemente al inicio del presente capítulo. Como ejemplo de primera mano podemos mencionar al conjunto ordinario de todas las fracciones formadas a partir de los enteros, junto con las operaciones usuales de suma y multiplicación, es conocido como el campo de los números racionales. Los principios de los campos tienen muchas aplicaciones. La ingeniería eléctrica y la de electrónica y comunicaciones usan el campo de los números complejos para estudiar los circuitos eléctricos, fenómenos eléctricos y magnéticos. A su vez, la teoría de la codificación que es usada en las telecomunicaciones, los campos son herramientas para reducir los errores que surgen de la transmisión de información sobre medios como el par de hilos de cobre (línea telefónica), el cable coaxial, enlaces de fibra óptica y enlaces de radio frecuencia en microondas (satélite y celular). Definición de campo Como preámbulo, se puede decir que un campo es un anillo conmutativo con elemento unitario (identidad multiplicativa) en el cual cada elemento no cero tiene un inverso multiplicativo. Definición:
Un campo F es un conjunto que tiene dos operaciones definidas en este, llamadas adición y multiplicación, tales que satisfacen las siguientes condiciones:
1. F forma un grupo conmutativo bajo la adición. El elemento identidad con respecto a la
adición es llamado elemento cero o la identidad aditiva de F, y se denota por el “0”.
2. El conjunto de elementos no cero en F forman un grupo conmutativo bajo la multiplicación. El elemento identidad con respecto a la multiplicación es llamado elemento unidad o identidad multiplicativa de F, y se denota por el “1”.
3. La multiplicación es distributiva bajo la adición. a • (b + c) = a • b + a • c. A partir de la introducción a estas estructuras básicas del álgebra moderna, es inmediato comprender que cada elemento a de un campo tiene un inverso aditivo –a tal que a + (–a) = (–a) + a = 0. Además se puede observar que cada elemento no cero a de un campo tiene un inverso multiplicativo a-1 tal que a • a-1 = a-1 • a = 1. El número total de elementos en un campo es llamado el orden del campo. Un campo puede contener un infinito o finito número de elementos. Si el orden de un campo es finito, el campo es llamado un campo finito. Y son estos campos los que interesan para el contexto de la teoría de codificación. Los campos finitos también son llamados campos de Galois en honor al matemático Francés E. Galois, para el cual se ha anexado una reseña de su interesante y joven vida al final de la presente tesis.
Un campo de Galois de orden q es denotado por GF(q), o por Fq
26
En ejemplo de lo anterior son las siguientes tablas, que definen el campo de Galois de orden 7 bajo módulo-7 en suma y multiplicación: –a + 0 1 2 3 4 5 6 a-1
×××× 0 1 2 3 4 5 6 0 0 0 1 2 3 4 5 6 - 0 0 0 0 0 0 0 0 6 1 1 2 3 4 5 6 0 1 1 0 1 2 3 4 5 6 5 2 2 3 4 5 6 0 1 4 2 0 2 4 6 1 3 5 4 3 3 4 5 6 0 1 2 5 3 0 3 6 2 5 1 4 3 4 4 5 6 0 1 2 3 2 4 0 4 1 5 2 6 3 2 5 5 6 0 1 2 3 4 3 5 0 5 3 1 6 4 2 1 6 6 0 1 2 3 4 5 6 6 0 6 5 4 3 2 1
Tabla 3.7. Suma Módulo-7 y sus inversos. Tabla 3.8. Multiplicación Módulo-7 y sus inversos. Asumiendo que p = 7, la tablas 3.7 y 3.8 muestra al conjunto de enteros {0, 1, 2, 3, 4, 5, 6} el cual conforma un campo de 7 elementos, denotado por GF(7), bajo las operaciones de adición y multiplicación. Además se puede observar que la tabla 3.7 también se usa para la substracción, ya que se anexan los inversos aditivos de cada elemento a. Por ejemplo, si se desea restar 6 de 3, primeramente se localiza el inverso aditivo de 6 el cual es el 1, posteriormente se suma 1 al 3 para obtener el resultado [3 – 6 = 3 + ( – 6 ) = 3 + 1 = 4]. Para la división podemos proceder de una forma similar pero con la tabla 3.8. Ahora si se desea dividir 3 entre 2, primero se debe encontrar el inverso multiplicativo del 2 que es 4, y entonces se multiplica 3 por 4 para tener el resultado [3 ÷÷÷÷ 2 = 3 • ( 2–1 ) = 3 • 4 = 5]. Con base en el ejemplo anterior, se puede deducir una propiedad inconfundible para asegurar la conformación de un campo, y es que q debe ser un número primo; esto anteriormente se enunció en el teorema T3.2, y que junto con el teorema T3.3 se demostró que en Zm todos los elementos distintos de cero tienen un inverso multiplicativo sí y sólo sí m es primo. Característica de un campo Para continuar con la trascendencia de los números primos en los campos se tiene el siguiente análisis. Considerando un campo finito GF(q) = {0, 1, . . . , q-1}. Ahí existe un λ que es el entero positivo más pequeño tal que
∑=
=λ
1
01i
donde λ es llamado la característica del campo. Teorema T3.4. La característica λ de un campo finito es un entero primo. Para demostrar el anterior teorema, se supondrá que λ no es un primo, entonces existen dos enteros positivos 0 < m, n > λ tales que λ = m • n y
27
∑ ∑ ∑= = =
== •λ
1 1 1
0111i
m
i
n
i
Lo anterior implica también que ∑=
=m
i 1
01 o que ∑=
=n
i 1
01 y λ no es el entero positivo
más pequeño, tal que ∑=
=λ
1
01i
. Esto contradice la definición de la característica de un campo.
Por lo consiguiente λ es primo. Orden de un elemento de campo Considerando un elemento a no cero de un campo finito GF(q). Existe un entero positivo más pequeño n tal que an = 1 y an = a • a . . . (n veces). Donde n es llamado el orden del elemento de campo a. Teorema T4.5. Si a es un elemento no cero de GF(q), aq-1 = 1. Para justificar lo anterior se asume que a1, a2, . . . , aq-1 son elementos no cero de GF(q). El conjunto de todos los elementos no cero de GF(q) forma un grupo conmutativo G = {a1, a2, . . . , aq-1} bajo la multiplicación módulo-q. Se podrá observar claramente que G = {a1, a2, . . . , aq-1} = {a • a1, a • a2, . . . , a • aq-1}, donde a es un elemento no cero de GF(q). También, a1 • a2 . . . • aq-1 = (a • a1) • (a • a2) . . . (a • aq-1) = aq-1 • ( a1 • a2 . . . • aq-1) ≠ 0. Por lo tanto aq-1 = 1. Elemento primitivo de un campo Teorema T3.6. Si n es el orden de un elemento no cero de GF(q), q – 1 es divisible entre n. Demostrando lo anterior, se supondrá que q – 1 es no divisible entre n. Ahora, dividiendo q – 1 entre n, se tiene que q – 1 = q’n + r, donde q’ es el cociente, r es el residuo y 0 < r < n. Además:
rqnrnqq aaaa ⋅== +− ''1 )( A partir de que aq-1 = 1 y an = 1, se deberá tener que ar = 1 y r es el orden del elemento a. Lo anterior es imposible a partir de que 0 < r < n ya que se contradice la definición del orden de un elemento de campo, y donde n es el entero positivo más pequeño tal que an = 1. Por consiguiente n debe dividir a q – 1, (q – 1 es divisible entre n). A partir de lo anterior, se puede analizar una propiedad interesante de un campo finito, (ésta a su vez da lugar a otra característica propia de los polinomios con coeficientes en campos finitos que después se abordarán), la cual se conoce como elemento primitivo.
28
Para un campo finito GF(q), un elemento no cero a es llamado elemento primitivo de GF(q) si el orden de a es q – 1. Por lo tanto, se puede decir que las potencias de un elemento primitivo generarán todos los elementos no cero de GF(q). Además, cada campo finito GF(q) contiene al menos un elemento primitivo. Para efectos de resumir lo anterior, se muestra el siguiente ejemplo. La característica del campo GF(5) = {0, 1, 2, 3, 4} es λ = 5.
� Las potencias del elemento 2 en GF(5) son:
21 = 2; 22 = 4; 23 = 8 ≡ 3 mod-5; 24 = 16 ≡ 1 mod-5. En el último caso se puede observar que el orden del elemento a = 2 es cuatro (n = 4), ya que se cumple con la expresión an = 1 donde n = q – 1 = 5 – 1 = 4, por lo que 24 = 1. Y como se puede comprobar, las potencias del elemento 2 generaron todos los elementos no cero (1, 2, 3 y 4) de GF(5), entonces se puede concluir que 2 es un elemento primitivo de GF(5).
� Las potencia del elemento 3 en GF(5) son:
31 = 3; 32 = 9 ≡ 4 mod-5; 33 = 27 ≡ 2 mod-5; 34 = 81 ≡ 1 mod-5. Se repite el análisis anterior, observando el caso de la última potencia del elemento a = 3, donde n = q – 1 = 5 – 1 = 4, resultando que 34 = 1. Entonces el orden del elemento 3 es cuatro (n = 4). Así que el elemento 3 también es un elemento primitivo de GF(5).
� Las potencia del elemento 4 en GF(5) son: 41 = 4; 42 = 16 ≡ 1 mod-5; 43 = 64 ≡ 4 mod-5; 44 = 256 ≡ 1 mod-5. Para este elemento a = 4 se puede percibir que no se pueden generar todos los elementos no cero de GF(5) con sus propias potencias. Ello se debe a que no cumple con la expresión an = 1 donde n = q – 1. Se puede observar que tanto la potencia 2 como la 4 llegan al valor de 1, sin embargo el orden del elemento 4 es 2 (n = 2), porque n debe ser el entero de valor más bajo, y por consiguiente 5 – 1 ≠ 2 (n ≠ q – 1), lo que lleva a concluir que el elemento 4 de GF(5) no es un elemento primitivo para dicho campo. Lo analizado hasta el momento, brinda las primeras bases matemáticas para entender el rol que juegan las estructuras conocidas como campos de Galois dentro de los propios codificadores y decodificadores (principalmente los cíclicos) de canal. Por lo que a continuación se abordarán los polinomios que estructurarán a la codificación de canal.
29
3.5 Introducción a la extensión de un campo Para cualquier primo p y un entero positivo m > 1, es posible extender el campo GF(p) a un campo de pm elementos el cual es llamado una extensión de campo de GF(p) y se denota como GF(pm). En lo particular para la teoría de codificación de canal, los códigos para control de errores son a menudo estructurados con elementos provenientes de GF(p) o GF(pm). De hecho, en lo concerniente a esta tesis sólo se abordará la construcción de códigos con símbolos o elementos provenientes de los campos GF(2) o de GF(2m). Antes de proceder con la construcción de una extensión de campo GF(2m), será necesario definir y analizar primeramente los polinomios sobre el campo GF(2). Polinomios sobre GF(2) Sea GF(p) un campo de Galois, y
011
1)( fxfxfxfxf mm
mm ++++= −
− K
con grado m en la incógnita x, es denominado como un polinomio de x sobre un campo GF(p), donde los coeficientes f0, f1, . . . , fm ∈∈∈∈ GF(p). Con base en lo anterior se tienen la siguiente definición. Un polinomio f(x) de grado cualesquiera con coeficientes en GF(2) es llamado un polinomio irreducible si f(x) no es divisible por cualquier otro polinomio de grado mayor a cero pero menor al grado de f(x). Un ejemplo de esto es presentar el caso del polinomio x4 + x + 1 sobre GF(2), el cual no es divisible por cualquier polinomio en GF(2) de grado mayor a cero pero menor a 4. La tabla 3.9 muestra todos los casos de dicha divisibilidad.
f(x) g(x) f(x) / g(x) Residuo
x4 + x + 1 x x3 + 1 1 x4 + x + 1 x + 1 x3 + x2 + 1 1 x4 + x + 1 x2 x2 x + 1 x4 + x + 1 x2 + 1 x2 + 1 x x4 + x + 1 x2 + x x2 + x + 1 1 x4 + x + 1 x2 + x + 1 x2 + x 1 x4 + x + 1 x3 x x + 1 x4 + x + 1 x3 + 1 x 1 x4 + x + 1 x3 + x x x2 + x + 1 x4 + x + 1 x3 + x2 x + 1 x2 + x + 1 x4 + x + 1 x3 + x + 1 x x2 + 1 x4 + x + 1 x3 + x2 + 1 x + 1 x2 x4 + x + 1 x3 + x2 + x x + 1 1 x4 + x + 1 x3 + x2 + x + 1 x + 1 x
Tabla 3.9. Cocientes y residuos del polinomio x4 + x + 1 sobre GF(2).
30
Por lo tanto se dice que x4 + x + 1 es un polinomio irreducible sobre GF(2). Para el siguiente caso del polinomio x2 + 1 sobre GF(2), este es divisible por el polinomio x + 1 también sobre GF(2) y que es de grado uno (mayor de grado cero pero menor de grado 2). Entonces se dice que x2 + 1 no es un polinomio irreducible sobre GF(2). 3.6 Polinomio primitivo Para poder relacionar los conceptos de polinomio irreducible y el de polinomio primitivo, se puede mencionar, que cualquier polinomio irreducible sobre GF(2) de grado m siempre divide exactamente a la expresión:
112 +−m
x
Un ejemplos para comprobar lo anterior es el caso del polinomio irreducible x3 + x + 1, que tiene grado m = 3, y donde
1111 7181212 3
+=+=+=+ −−− xxxxm
es divisible entre dicho polinomio x3 + x + 1, como se muestra a continuación:
011
1 243
7
=+++=++
+resxxx
xx
x
Con base en lo anterior, se define que un polinomio irreducible
011
1)( pxpxpxpxp mm
mm ++++= −
− K
de grado m con coeficientes p0, p1, . . . , pm provenientes de GF(2) es llamado polinomio primitivo si el entero positivo más pequeño n por el cual p(x) divide exactamente a xn+1 es de valor igual a 2m-1. Un ejemplo de lo anterior se tiene con el polinomio irreducible x4 + x + 1 sobre GF(2), el cual divide exactamente a x15 + 1, donde 15 = 24 – 1. Por otra parte, el polinomio irreducible x4 + x3 + x2 + x + 1 sobre GF(2) divide exactamente también a x15 + 1 donde 15 = 24 – 1, pero también dicho polinomio divide exactamente a x5 + 1 y ahora 5 ≠ 24 – 1. Por lo que se puede deducir, que el polinomio irreducible x4 + x + 1 es un polinomio primitivo, mientras que el polinomio irreducible x4 + x3 + x2 + x + 1 no es polinomio primitivo sobre GF(2). Lo anterior se resume en la tabla 10.
Polinomio Irreducible m n 2m-1 ¿Es polinomio primitivo?
x4 + x + 1 4 15 15 SI x4 + x3 + x2 + x + 1 4 5 15 NO
Tabla 3.10. Ejemplo de polinomios primitivos sobre GF(2).
31
Se puede observar que un polinomio primitivo sobre GF(2) es siempre irreducible, mientras que un polinomio irreducible no siempre puede ser primitivo. 3.7 Construcción de la extensión de campo GF (2m) a partir de GF(2) La elaboración de una extensión de campo GF(2m) a partir de GF(2) se encuentra basada en las raíces primitivas de un polinomio primitivo p(x) de grado m con coeficientes provenientes de GF(2). Tomando en cuenta un conjunto finito de elementos sobre los cuales una operación de multiplicación “•” está definida, tal que dicho conjunto F = { 0, 1, α, α 2 , . . . , α j , . . . } y tendiendo que α j = α • α • α • . . . • α (j veces), donde la expresión α • α • α • . . . • α es llamada la representación en potencias del elemento α j en el conjunto F. Si el elemento α es una raíz del polinomio primitivo p(x) de grado m sobre GF(2), entonces p(α) = 0.
A partir de que p(x) divide exactamente a 112 +−m
x (como se pudo ejemplificar en el apartado anterior), se tiene que:
)()(112 xpxqxm
=+−
Pero aplicando en función de la raíz α, se tiene que:
0)()()(112 ⋅==+− αααα qpqm
Por consiguiente, 112 ≡−m
α bajo suma módulo-2 y conjunto:
},...,,,1,0{ 222 −=m
F ααα
Se puede demostrar 1 que el conjunto de elementos no cero de F son cerrados (prop. cerradura) bajo la multiplicación “•”, y que F es cerrado bajo la adición “+”. Por lo que se puede concluir que F es un campo de Galois GF(2m) de 2m elementos. Las potencias de α generan todos los elementos no cero de GF(2m) y α es un elemento primitivo. A partir de que la extensión de campo GF(2m) está construida desde GF(2), por lo que GF(2) es llamado el campo base de GF(2m). Este campo base es cerrado bajo la adición y multiplicación de módulo-2. Por lo tanto, el subconjunto {0, 1} forma un sub-campo de GF(2m), [es decir, GF(2) es un sub-campo de GF(2m) ]. Ahora asumiendo que
012
21
1)( pxpxpxpxxp mm
mm
m +++++= −−
−− K
de grado m con coeficientes p0, p1, . . . , pm-1 provenientes de GF(2). Si p(α) = 0, se tiene que ________ 1
Demostración en la referencia Lin [4], pp 44-46.
32
012
21
10 pppp mm
mm
m +++++= −−
−− αααα K
012
21
1 pppp mm
mm
m ++++= −−
−− αααα K
donde α m es expresado como un polinomio con coeficientes p0, p1, . . . , pm-1 provenientes de GF(2) y
012
21
1 pppp mm
mm ++++ −
−−
− ααα K
es llamado representación polinomial de los elementos α m. Todo lo anterior lleva a poder representar los elementos no cero de F como potencias del elemento primitivo α y como una combinación lineal de α 0, α 1, α 2 , . . . , α m-1. La representación polinomial del elemento α i , con i = 0, 1, . . . , 2m – 2 , se expresa como
012
21
1 aaaa mm
mm
i ++++= −−
−− αααα K
con coeficientes binarios. También dichos coeficientes se pueden representar por medio de un vector [ a0 a1 . . . am-1]. Por otra parte, el elemento cero “0” en F puede ser representado por el polinomio cero o un vector fila de puros ceros. Ejemplificando lo anterior, sea α una raíz del polinomio primitivo p(x) = x4 + x + 1 sobre GF(2). La representación en potencias de α4 es α • α • α • α y la representación polinomial es α + 1, ya que aplicando p(x) en función de α se tiene que p(α) = 0, por lo tanto
10)( 4 ++== αααp
14 += αα Con base en esta última igualdad, se pueden desarrollar las siguientes representaciones polinomiales de α5 , α6 y α7 .
ααααααα +=+=⋅= 245 )1(
23256 )( αααααααα +=+=⋅=
1)1()( 33342367 ++=++=+=+=⋅= αααααααααααα Finalmente, la tabla 3.11 muestra las distintas representaciones de los elementos del campo de extensión GF(24) generados por el polinomio primitivo p(x) = x4 + x + 1.
33
Representación en
potencias Representación polinomial Representación
binaria 0 = 0 0 0 0 0 1 = 1 1 0 0 0 α = α 0 1 0 0 α2 = α2 0 0 1 0 α3 = α3 0 0 0 1 α4 = 1 + α 1 1 0 0 α5 = α + α2 0 1 1 0 α6 = α2 + α3 0 0 1 1 α7 = 1 + α + α3 1 1 0 1 α8 = 1 + α2 1 0 1 0 α9 = α + α3 0 1 0 1 α10 = 1 + α + α2 1 1 1 0 α11 = α + α2 + α3 0 1 1 1 α12 = 1 + α + α2 + α3 1 1 1 1 α13 = 1 + α2 + α3 1 0 1 1 α14 = 1 + α3 1 0 0 1
Tabla 3.11. Representación de los elementos de GF(24) generados por p(x) = x4 + x + 1. 3.8 Propiedades básicas de un campo GF (2m) El propósito de este apartado es el de abordar la definición de los polinomios mínimos, por lo que se analizarán primero las raíces de los polinomios y sus conjugados para llegar a tal definición. Como en el caso del algebra tradicional, donde un polinomio con coeficientes reales puede no tener raíces en ese mismo campo pero si raíces provenientes de los complejos, así un polinomio con coeficientes provenientes de GF(2) puede no tener raíces en ese mismo campo GF(2), sin embargo tiene raíces contenidas en una extensión de campo GF(2m). Por ejemplo, el polinomio x4 + x3 + 1 el cual es un polinomio irreducible de GF(2), y que tiene cuatro raíces provenientes de GF(24). Esto se comprueba mediante la substitución de todos los elementos de GF(24), mostrados por la tabla 3.11, dentro de x4 + x3 + 1, y llegando a localizar cuatro raíces que son α7, α11, α13, α14. Verificando para la primera raíz se tiene:
01)()1(11)()( 323221283747 =+++++=++=++ αααααααα Igualmente para las otras tres raíces se comprueba lo anterior, entonces se puede desarrollar la siguiente expresión:
))()()(( 1413117 αααα ++++ XXXX con aplicación de los elementos de la tabla 3.11, se tiene que:
34
))()()(( 1413117 αααα ++++ XXXX ])(][)([ 2714132181172 αααααα ++++++= XXXX finalmente, desarrollando queda:
1))()()(( 341413117 ++=++++ XXXXXX αααα Y que resulta ser el polinomio original. Ahora, lo interesante es saber cuáles son los elementos de una extensión de campo GF(2m) que son otras raíces de un polinomio dado f(x) a partir de uno de sus elemento β que es raíz unidad de f(x). Para responder lo anterior, se enunciará el siguiente teorema 2: T3.7. Sea f(x) un polinomio con coeficientes provenientes de GF(2), y suponiendo que β sea un elemento de una extensión de campo GF(2m). Si β es una raíz de f(x), entonces para cualquier ≥ 0,
l2β es también una raíz de f(x).
El elemento l2β es llamado “un conjugado de β ”; además, el anterior teorema menciona que si β [un
elemento de GF(2m)] es una raíz de un polinomio f(x) proveniente de GF(2), entonces todos los conjugados distintos de β [elementos de GF(2m)] son también raíces de f(x). Por ejemplo, el polinomio f(x) = x6 + x5 + x4 + x3 + 1 tiene a α4 [elemento de GF(24) dado por la tabla 3.11], como una de sus raíces. Comprobando lo anterior y recordando que α15 = 1, se tiene que:
1)()()()()( 344454644 ++++= αααααf
112162024 ++++= αααα
11259 ++++= αααα
1)1()()( 3223 +++++++++= αααααααα
0)( 4 =αf
Y los conjugados de α4, utilizando l2β , son:
424 0
)( αα =
824 1
)( αα = ααα == 1624 2
)( 23224 3
)( ααα ==
Si se desea tener valores para mayores de 3, se comprobará que estos caerán en los anteriores
conjugados, por ejemplo para el caso de = 4, se tiene que:
________ 2
Demostración en la referencia Lin [4], pp 48.
35
46424 4
)( ααα == lo cual resulta ser la propia raíz unidad α4. Continuando con lo definido por el anterior teorema T3.7 y asumiendo que β sea un elemento no cero dentro del campo GF(2m), se puede establecer que:
112 =−m
β si se agrega un “uno” en ambos miembros, se tiene:
0112 =+−m
β
La anterior expresión implica que β es una raíz del polinomio.
112 +−m
x
Por lo tanto, cada elemento no cero de GF(2m) es una raíz de la ec. 3.0. Ahora, debido a que el grado del anterior polinomio es 2m − 1, los 2m − 1 elementos no cero de GF(2m) forman todas las raíces de la expresión de ec. 3.0. Resumiendo lo anterior, se tiene el siguiente teorema:
T3.8. Los 2m − 1 elementos no cero de GF(2m) conforman todas las raíces de 112 +−m
x . Además, a partir de que el elemento “0” de GF(2m) es la raíz de x, el teorema T3.8 tiene el siguiente corolario, que es el preámbulo a los polinomios mínimos.
C3.1. Los elementos de GF(2m) conforman todas las raíces del polinomio xxm
+2.
Para probar brevemente el anterior corolario C3.1, se toma el caso de GF(24) conforme sus elementos mostrados de la tabla 3.11. El polinomio analizado queda:
xxxxxxm
+=+=+ 1622 4
Para x = 0 00016 =+
Para x = 1 01116 =+
Para x = α 016 =+=+ αααα
Para x = α2 0)( 222322162 =+=+=+ αααααα
Para x = α3 0)( 333483163 =+=+=+ αααααα
Ec. 3.0
36
Y así, hasta el último elemento α14 serán raíces del polinomio x16 + x.
Entonces, debido a que cualquier elemento β de GF(2m) es una raíz del polinomio xxm
+2, β puede
ser raíz de un polinomio de GF(2) con grado menor a 2m. Y permitiendo que φ(x) sea el polinomio de grado más pequeño sobre GF(2) tal que φ(β) = 0. Entonces dicho polinomio es llamado el polinomio mínimo de β, Por ejemplo, el polinomio mínimo del elemento “0” del campo GF(2m) es x, mientras que el polinomio mínimo del elemento “1” es x + 1. Ahora, para poder obtener el polinomio mínimo de β, para cada uno de estos elementos β, será necesario mencionar algunos otros teoremas3 relacionados con dichos polinomios. T3.9. El polinomio mínimo φ(x) de un elemento de campo β es un polinomio irreducible. T3.10. Sea f(x) un polinomio sobre GF(2) y φ(x) un polinomio mínimo de β. Si β es una raíz de f(x), entonces f(x) es divisible entre φ(x). Retomando el corolario C3.1 y el teorema T3.10, se tiene el siguiente teorema: T3.11. El polinomio mínimo φ(x) de β proveniente del campo GF(2m) divide exactamente al
polinomio xxm
+2.
Este último teorema conlleva a que todas las raíces de φ(x) provengan del campo GF(2m). T3.12. Sea f(x) un polinomio irreducible sobre GF(2), además sea β un elemento del campo GF(2m). Y asumiendo que φ(x) sea un polinomio mínimo de β. Si f(β) = 0, entonces φ(x) = f(x). En otras palabras, el teorema T3.12 dice que si un polinomio irreducible tiene a β como una raíz, éste será el polinomio mínimo φ(x) de β. Inclusive, recordando lo expuesto por el teorema T3.7, donde β y
sus conjugados l
K2222 ,,,,
321
ββββ son también raíces de φ(x). Y si se asume que e sea el
entero más pequeño tal que ββ =e2
. Entonces 1321 2222 ,,,,
−e
ββββ K son todos los
distintos conjugados de β. Además de que ββ =m2
con e ≤ m , (ya que m es divisible entre e). ________ 3
Demostración en la referencia Lin [4], pp 49-50.
37
T3.13. Sea β un elemento del campo GF(2m) y asumiendo que e sea el entero más pequeño no
negativo tal que ββ =e2
. Entonces:
)()( 21
0
i
xxfe
i
β+= ∏−
=
y será un polinomio irreducible sobre el campo GF(2). Finalmente combinando los teoremas T3.12 y T.3.13, resultará el siguiente teorema: T3.14. Sea φ(x) el polinomio mínimo de un elemento β proveniente del campo GF(2m). Y sea e el
entero más pequeño tal que ββ =e2
. Entonces:
)()( 21
0
i
xxe
i
βφ += ∏−
=
El resultado al que llega el teorema T3.14, es básico para generar el polinomio mínimo de un elemento β proveniente de GF(2m), a partir de él mismo y de sus conjugados. A continuación se ejemplifica todo lo anterior. Considerando la extensión de campo GF(24) que se muestra en la tabla 3.11, y sea el caso de β = α3, entonces sus conjugados son:
aplicando l2β
3231 0
)( ααβ ==
6232 1
)( ααβ == 12232 22
)( ααβ == 924232 33
)( αααβ === si tomamos el caso de = 4,
348232 44
)( αααβ === se puede observar que resulta un elemento repetido, por lo tanto sólo hay 4 raíces: α3, α6, α12, y α9. Por lo tanto el polinomio mínimo de β = α3 es:
))()()(()( 91263 ααααφ ++++= xxxxx
)])()][()([( 91263 αααα ++++= xxxx
])(][)([ 2191229632 αααααα ++++++= xxxx después de simplificar, queda:
38
1)( 234 ++++= xxxxxφ
Sólo habrá que recordar que el polinomio φ(x) obtenido es un polinomio irreducible con coeficientes en el campo GF(2). La tabla 3.12 resume todos los casos de polinomios mínimos correspondientes a su conjunto de raíces conjugadas que conforman los elementos del campo GF(24) generados por el polinomio primitivo p(x) = x4 + x + 1.
Raíces conjugadas Polinomio mínimo 0 x 1 x + 1
α , α2 , α4 , α8 x4 + x + 1 α3 , α6 , α9, α12 x4 + x3 + x2 + x + 1
α5, α10 x2 + x + 1 α7 , α11 , α13, α14 x4 + x3 + 1
Tabla 3.12. Polinomios mínimos de los elementos de GF(24) generados por p(x) = x4 + x + 1. Solamente hay que resaltar de la tabla 3.12, que el grado del polinomio mínimo de cualquier elemento proveniente de GF(2m) divide exactamente a m, (en este caso m = 4). Se presentan a continuación dos tablas más para los casos de m = 3 y m =5, que serán utilizadas más adelante en el presente capítulo.
Raíces conjugadas Polinomio mínimo 0 x 1 x + 1
α , α2 , α4 x3 + x + 1 α3 , α5 , α6 x3 + x2 + 1
Tabla 3.13. Polinomios mínimos de los elementos de GF(23) generados por p(x) = x3 + x + 1.
Raíces conjugadas Polinomio mínimo 0 x 1 x + 1
α , α2 , α4 , α8, α16 x5 + x2 + 1 α3 , α6 , α12, α17, α24 x5 + x4 + x3 + x2 + 1 α5 , α9, α10, α18, α20 x5 + x4 + x2 + x + 1 α7 , α14, α19, α25, α28 x5 + x3 + x2 + x + 1 α11 , α13, α21, α22, α26 x5 + x4 + x3 + x + 1 α15 , α23, α27, α29, α30 x5 + x3 + 1
Tabla 3.14. Polinomios mínimos de los elementos de GF(25) generados por p(x) = x5 + x2 + 1.
39
3.9 Introducción a los códigos BCH Los códigos BCH constituyen una de las clases más importantes y poderosas de los codificadores de bloque, principalmente como códigos cíclicos correctores de errores aleatorios múltiples. Estos códigos fueron desarrollados conjuntamente por Bose y Ray-Chaudhuri en 1960 e independientemente por Hocquenghem en 1959; además de que posteriormente en 1960 Peterson diseñó el primero de los algoritmo para la decodificación BCH. Estos códigos son relativamente sencillos de implementar, tanto para codificar como para decodificar, ya que fundamentalmente esta última hace uso de la decodificación algebraica. La decodificación algebraica es realizable porque existe una considerable estructura matemática en dichos códigos, que hace posible el desarrollo de algoritmos para la resolución de la ecuación del síndrome. Los codificadores BCH son códigos de corrección de t errores en el sentido de que pueden detectar y corregir hasta t errores aleatorios por palabra de código. Además de que es posible describir los códigos Hamming (códigos correctores de un solo error) como códigos BCH, esto hace resaltar lo genérico que pueden ser los códigos BCH. 3.10 Descripción general del caso binario Para cualquier entero positivo m ≥ 3 y con t ≤ 2m-1, existe un código BCH binario con los siguientes parámetros:
Longitud del bloque n = 2m - 1
Número de dígitos de paridad n – k ≤≤≤≤ mt
Distancia mínima dmin ≥≥≥≥ 2t + 1
Se puede observar que dicho código es capaz de corregir cualquier combinación de t o menos errores en un bloque de n = 2m – 1 dígitos binarios. En otras palabras se habla de un “código binario BCH corrector de t errores”. Inclusive como los códigos BCH son códigos cíclicos, estos son también definidos por un polinomio generador g(x), el cual para su caso, se encuentra especificado en términos de sus raíces provenientes del campo GF(2m).
40
Asumiendo que α es un elemento primitivo de GF(2m). El polinomio generador g(x) de estos códigos BCH con longitud del bloque código n = 2m – 1 es el polinomio de más bajo grado sobre el campo GF(2) el cual tiene:
t232 ,..,.,, αααα como sus raíces [ g( α i ) = 0 para 1< i < 2t ]. Retomando algunos teoremas sobre las propiedades de las extensiones de campo GF(2m) y la parte de los polinomios mínimos; se asumirá que Mi(x) sea el polinomio mínimo de α i. Entonces g(x) debe ser el m.c.m. (mínimo común múltiplo) de M1(x), M2(x), . . . , M2t(x), quedando g(x) como:
)}(,...),(),(.{..)( 221 xMxMxMmcmxg t= Lo anterior nos brinda un preámbulo para establecer los términos generales del diseño para un codificador BCH. 3.11 Lineamientos de diseño para los codificadores BCH Un código BCH sobre GF(2) de longitud n capaz de corregir al menos t errores, se encuentra especificado por:
1. Determinado valor de m más pequeño tal que GF(qm) tiene una n-ésima raíz primitiva de unidad β. Lo que designará a n como n = qm − 1 (primitivo)
2. Determinado entero no negativo b. Generalmente seleccionado con b = 1 (sentido estricto).
3. Listado de las 2t potencia consecutivas de β:
121 ,...,, −++ tbbb βββ
Determinando el polinomio mínimo con respecto a GF(q) de cada una de estas potencia de β.
4. El polinomio generador g(x) es el mínimo común múltiplo (m.c.m.) de esos polinomios mínimos.
Por otra parte, se puede denominar a un código BCH como un código cíclico ( n, n − grado [g(x)] ). Debido a que el polinomio generador es construido a partir de polinomios mínimos respecto a GF(q), g(x) tiene coeficientes en GF(q), ello también da lugar a que el código esté en GF(q) (polinomio de las palabras código resultantes).
41
Para profundizar en esto último, se puede mencionar que existen dos campos involucrados en la construcción de los códigos BCH, conocidos como el “campo menor” y el “campo mayor”. El campo menor GF(q) es donde el polinomio generador tiene sus coeficientes y también es el campo donde los elementos de las palabras código se encuentran. Por su parte el campo mayor GF(qm), es el campo donde el polinomio generador tiene sus raíces. Y para efectos de pura codificación es suficiente trabajar sólo con el campo menor, mientras que para la decodificación se requiere del campo mayor. Ejemplificando lo anterior; se toma m = 5, por lo que n = 31 = 25 – 1, además se asumirá que β es una raíz del polinomio primitivo x5 + x2 + 1 en GF(25) (q = 2 ⇒ binario). Lo anterior resultará en la
construcción de un código primitivo (ya que la raíz β tiene su orden n = 31 que cumple con 11 =−mqβ
o β n = β 31 = 1 siendo β primitivo). Se designa b = 1 (sentido estricto), además con la condición de que sea va a construir un código corrector de un error t = 1. Las 2t potencias consecutivas de β ( t = 1; 2•1 = 2 potencias) son β, β 2. El polinomio mínimo de β y β 2 con respecto a GF(2) es el mismo ya que las dos raíces son conjugadas, y dicho polinomio se denota como M1(x). A partir de que β es primitivo, se tiene que M1(x) = x5 + x2 + 1, según la tabla 3.15; y como sólo existe un polinomio mínimo de las dos raíces, se entiende que g(x) = mcm[ M1(x) ], entonces:
1)()( 251 ++== xxxMxg
Y como el grado de g(x) es 5, este código se denomina (31, 26). Además se observar que de hecho se trata de un código Hamming.
Raíces conjugadas Polinomio Mínimo
0 M_(x) = x
1 M0(x) = x + 1
α, α 2, α 4, α 8, α 16 M1(x) = x5 + x2 + 1
α 3, α 6, α 12, α 17, α 24 M3(x) = x5 + x4 + x3 + x2 + 1
α 5, α 9, α 10, α 18, α 20 M5(x) = x5 + x4 + x2 + x + 1
α 7, α 14, α 19, α 25, α 28 M7(x) = x5 + x3 + x2 + x + 1
α 11, α 13, α 21, α 22, α 26 M11(x) = x5 + x4 + x3 + x + 1
α 15, α 23, α 27, α 29, α 30 M15(x) = x5 + x3 + 1
Tabla 3.15. Lista de polinomios mínimos de los elementos en GF(25) generada con respecto a GF(2) del polinomio primitivo p(x) = x5 + x2 + 1.
42
Otros ejemplos para seguir identificando los parámetros claves involucrados en la construcción de un código BCH, son los siguientes: Ejem. 1) Asumiendo que m = 5 resulta que n = 31, pero ahora t = 2 (corregir 2 errores), con b = 1, y β siendo un elemento primitivo y raíz del polinomio x5 + x2 + 1 en GF(25). Las respectivas 2t = 4 potencia consecutivas de β serán { β , β 2, β 3, β 4 }. Estas raíces conjugadas se pueden dividir en dos grupos de acuerdo a la tabla 1 anterior { β , β 2, β 4 } y { β 3 }, siendo sus polinomios mínimos los siguientes:
1)( 251 ++= xxxM 1)( 2345
3 ++++= xxxxxM
por lo tanto g(x) = mcm[ M1(x), M3(x) ] = ( x5 + x2 + 1 ) ( x5 + x4 + x3 + x2 + 1 ), entonces
1)( 3568910 ++++++= xxxxxxxg La denominación del presente código binario sería (31, 31 – 10) = (31, 21). Ejem. 2) Retomando todos los anteriores valores del ejemplo 1, salvo que ahora t = 3 para tener la capacidad de corregir 3 errores en la palabra código. Las respectivas 2t = 6 potencia consecutivas de β serán { β , β 2, β 3, β 4, β 5, β 6 }. Estas raíces conjugadas se puedes dividir en tres grupos { β , β 2, β 4 }, { β 3, β 6 } y { β 5 }, siendo sus polinomios mínimos los siguientes (de acuerdo a la tabla 3.15):
1)( 251 ++= xxxM 1)( 2345
3 ++++= xxxxxM 1)( 2455 ++++= xxxxxM
Y calculando el m.c.m. de estos polinomios mínimos de tales raíces conjugadas, el polinomio generador resulta ser:
)1)(1)(1()()()()( 245234525531 ++++++++++== xxxxxxxxxxxMxMxMxg
1)( 235789101115 ++++++++++= xxxxxxxxxxxg Por su parte, la denominación de este código binario será (31, 31 – 15) = (31, 16). Se podrá observar que al ir aumentando la capacidad de corrección se incrementa la cantidad de dígitos de paridad del código, ya que va aumentando el grado del polinomio generador. Finalmente, lo que resta es obtener las palabras código a partir del polinomio generador y las posibles palabras dato, con base en la siguiente expresión:
)()()( xgxdxc ⋅= Esta última ecuación se utiliza para la codificación de tipo no sistemática, donde d(x) es el polinomio de la palabra dato y c(x) es el polinomio de la palabra código.
43
Sin embargo, la codificación más utilizada es la de tipo sistemático, la cual se caracteriza por contener tal cual la palabra dato d(x) en la propia palabra código c(x), facilitando así el proceso de la decodificación en el receptor, debido a que sólo hay que ubicar el segmento donde inicia la palabra dato dentro de la palabra recibida r(x) previamente ya corregida. Por lo cual, estos codificadores son los que se abordarán en la presente tesis. La siguiente expresión determina el cálculo de la palabra código para un codificador cíclico sistemático
)()()( xbxdxxc kn += −
y donde b(x) se obtiene conforme a la siguiente expresión:
=)(xb Res
−
)(
)(
xg
xdx kn
además donde n y k son las longitudes de las palabras código y dato respectivamente. Para entender esta codificación, se muestra brevemente el siguiente ejemplo para el caso de un codificador (7,4) con g(x) = 1 + x + x3 y con un vector dato d = 1 0 1 0, siendo su palabra código la siguiente:
c(x) = ( x7-4 ) d(x) + b(x) = ( x3 ) d(x) + b(x) d(x) = 1 + x2 b(x) = Res [( x7-4 ) d(x) / g(x) ] = Res [ x3 ( 1 + x2 ) / ( 1 + x + x3 )]
= Res [( x3 + x5 ) / ( 1 + x + x3 )]
c(x) = ( x3 ) (1 + x2 ) + x2 = x3 + x5 + x2
= x5 + x3 + x2 y en formato binario queda: c = 0 0 1 1 0 1 0 Finalmente se podrá observar, que los cuatro dígitos finales de izquierda a derecha corresponden a la palabra binaria del dato d = 1 0 1 0 .
44
Las tablas 3.16 y 3.17 muestran los polinomios mínimos para los casos de m = 3 y m = 4.
Raíces conjugadas Polinomio Mínimo
0 M_(x) = x
1 M0(x) = x + 1
α, α 2, α 4 M1(x) = x3 + x + 1
α 3, α 6, α 5 M3(x) = x3 + x2 + 1
Tabla 3.16. Lista de polinomios mínimos de los elementos en GF(23) generada con respecto a GF(2) del polinomio primitivo p(x) = x3 + x + 1.
Raíces conjugadas Polinomio Mínimo
0 M_(x) = x
1 M0(x) = x + 1
α, α 2, α 4, α 8 M1(x) = x4 + x + 1
α 3, α 6, α 9, α 12 M3(x) = x4 + x3 + x2 + x + 1
α 5, α 10 M5(x) = x2 + x + 1
α 7, α 11, α 13, α 14 M7(x) = x4 + x3 + 1
Tabla 3.17. Lista de polinomios mínimos de los elementos en GF(24) generada con respecto a GF(2) del polinomio primitivo p(x) = x4 + x + 1.
45
3.12 Lineamientos generales para el proceso de decodificación BCH La decodificación BCH algebraica tiene los siguientes pasos: 1. Cálculo del síndrome S = {S1, S2, . . . , S2t}. Por medio del polinomio de la palabra recibida r(x). 2. Determinación de un polinomio localizador de error Λ(x). Ello con el uso de los componentes del síndrome S1, S2, . . . , S2t.
Dicho polinomio es nombrado así, ya que sus raíces proporcionan un indicativo de dónde se encuentran los errores a corregir. Esta etapa tiene varios métodos (tanto para BCH como RS) para encontrar dicho polinomio localizador de error:
� Algoritmo de Peterson para códigos BCH � Algoritmo de Berlekamp-Massey para códigos BCH � Algoritmo Euclidiano, inclusive � Técnica basada en transformada de Fourier para campos de Galois
El algoritmo que se abordará en la presente tesis es el de Berlekamp-Massey.
3. Buscar las raíces del polinomio localizador de error Λ(x). Esto usualmente se realiza utilizando la denominada “búsqueda de Chien”, la cual consiste en una búsqueda exhaustiva de raíces con todos los elementos del campo. 4. Determinar el polinomio patrón del error e(x), el cual está conformado por los denominados localizadores de error {Xi}. Estos últimos son los recíprocos de las raíces de Λ(x). 5. Corregir el error mediante la suma del polinomio patrón del error e(x) con el polinomio de la palabra recibida r(x), y así obtener la palabra de código c(x) enviada originalmente. Es importante aclarar que para efectos de la presente tesis se analizará la construcción de codificadores y decodificadores BCH binarios, primitivos y de sentido estricto (b = 1). Matriz verificadora de paridad Al analizar la etapa de decodificación de un codificador de canal, es básico primero hacer referencia a una matriz que coadyuva al cálculo del síndrome, y que se conoce como la matriz verificadora de paridad, la cual se desarrollará primero en este apartado, para que después se dé lugar al síndrome de un código BCH.
46
Sea α un elemento de GF(qm) y asumiendo el código (n, k) BCH de distancia mínima dmin ≥ 2t + 1 que se construye a partir de un polinomio generador g(x) sobre GF(q). Y ya que los códigos BCH se asumen como códigos cíclicos, se puede retomar la expresión de que c(x) = d(x) • g(x), donde
012
21
1 ...)( cxcxcxcxc nn
nn ++++= −
−−
− es un polinomio código de grado n – 1 sobre GF(q) y
012
21
1 ...)( dxdxdxdxd kk
kk ++++= −
−−
− es un polinomio dato de grado k – 1 sobre GF(q). Se puede observar que el polinomio código c(x) es divisible entre el polinomio generador g(x). A partir de que g(x) tiene
1221 ,...,,, −+++ tbbbb αααα como raíces del código (n, k) BCH, c(x) tiene esas mismas raíces como propias. Por lo que se tendrá:
012
21
1 ...)()()(0 ccccc bnbn
nbn
b ++++== −−
−− αααα
01
121
211
11 ...)()()(0 ccccc bnb
nnb
nb ++++== +−+
−−+
−+ αααα
M
012
1212
2112
112 ...)()()(0 ccccc tbntb
nntb
ntb ++++== −+−−+
−−−+
−−+ αααα
En un formato de matrices, lo anterior resulta:
=
−−+−+−
−++
−++
−
112111
212212
121
110
)()()(
)()()(
111
]...[0
ntbnbnb
tbbb
tbbb
nccc
ααα
αααααα
K
MMM
K
K
K
Y simplificando:
TCH=0
47
Por lo tanto, la matriz verificadora de paridad de un código (n, k) BCH de distancia mínima dmin ≥ 2t + 1 puede expresarse como:
=
−−+−+−+
−+++
−
11221212
11211
12
)()(1
)()(1
)()(1
ntbtbtb
nbbb
nbbb
H
ααα
αααααα
L
MM
L
L
Siendo la dimensión de esta matriz de t × n. 3.13 Cálculo del síndrome El proceso algebraico de la decodificación BCH inicia con el cálculo del síndrome de la palabra recibida. Partiendo nuevamente con b = 1, y t errores a corregir por el código. Sea c(x) el polinomio código, con notación vectorial
=C [ ]110 −nccc K además
012
21
1 ...)( exexexexe nn
nn ++++= −
−−
− como el polinomio patrón de error e(x), con notación vectorial
=E [ ]110 −neee K y un nuevo elemento que es
012
21
1 ...)( rxrxrxrxr nn
nn ++++= −
−−
−
conocido como el polinomio de la palabra recibida r(x), con vector:
=R [ ]110 −nrrr K Así, el polinomio recibido es:
)()()( xexcxr += y
TTT EHCHRH +=
TEH+= 0
TEH=
48
donde, a partir de la matriz H T obtenida del apartado anterior, y con b = 1 se tiene que:
=
−−− 12121
22222
12121
)()()(
)()()(
)()()(
111
ntnn
t
t
TH
ααα
αααααα
K
MMM
K
K
K
El vector del síndrome S está definido como:
TRHS =
TEHS =
=S ],..,.,[ 221 tSSS donde, podemos generalizar que:
)( ii rS α=
012
21
1 )(...)()( rrrr inin
nin ++++= −
−−
− ααα o
)( ii eS α=
012
21
1 )(...)()( eeee inin
nin ++++= −
−−
− ααα para 1 ≤ i ≤ 2t. Y es hasta aquí donde se concluye el procedimiento para calcular los elementos del síndrome S = {S1, S2, . . . , S2t}. Sin embargo, a continuación se demuestra la relación que existe entre dichos elementos y los denominados localizadores de error. Ahora, si se supone que el vector de patrón de error tiene v dígitos no cero localizados en j1, j2, . . . , jv (v es la cantidad de dígitos erróneos), entonces
1
1
2
2
1
1...)( j
jj
jj
jj
j xexexexexe v
v
v
v++++= −
−
donde 0 ≤ j1 < j2 < . . . < jv ≤ n y v ≤ t. La (ec. 3.1) Si = e(α i) se desarrolla como:
Ec. 3.1
49
1
1
2
2
1
1...1
jj
jj
jj
jj eeeeS v
v
v
vαααα ++++= −
−
2222
2 )()(...)()( 1
1
2
2
1
1
jj
jj
jj
jj eeeeS v
v
v
vαααα ++++= −
−
M
tjj
tjj
tjj
tjjt eeeeS v
v
v
v
22222 )()(...)()( 1
1
2
2
1
1αααα ++++= −
−
donde vv jjjj αααα ,,...,, 121 − son desconocidos. El anterior sistema de ecuaciones para el síndrome (ec. 3.2), se puede expresar como:
ijj
v
li
l
leS )(
1
α∑=
=
y donde se recordara que i = 1, 2, . . . , 2t. El conjunto de funciones en la ecuación (ec. 3.2) es conocido como funciones simétricas de sumas de
potencias en vv jjjj αααα ,,...,, 121 − . Para los códigos binarios que se estarán abordando se
tiene que 1...2121
=====−− vv jjjj eeee (es decir, si hay un error no cero, este debe ser
de valor 1), y asumiendo un cambio de variable lj
lX α= , entonces la (ec. 3.3) puede escribirse
como:
il
v
li XS ∑
=
=1
ti 2,...,2,1=
Si se conoce Xl , entonces se sabe la localización del error. Así Xl se le denomina el localizador de error. Ahora la siguiente etapa, es determinar el polinomio localizador del error, el cual contiene los denominados localizadores de error, y ello mediante la solución de la (ec. 3.2) que está en función de los elementos del síndrome previamente calculados por la (ec. 3.1).
Ec. 3.2
Ec. 3.3
Ec. 3.4
50
3.14 Búsqueda del polinomio localizador de error Cualquier algoritmo de decodificación que resuelva el sistema de ecuaciones (ec. 3.2) es un método de decodificación para los códigos BCH, donde j1, j2 . . . jv indican la ubicación de los errores en el polinomio e(x). Es decir, resolviendo este conjunto de funciones no lineales de manera directa, se podrán relacionar los componentes del síndrome con los coeficientes de un polinomio localizador de error y de esa forma encontrar los errores de la palabra recibida. Definiendo al polinomio localizador de error, se tiene:
1...)( 11
1 +Λ++Λ+Λ=Λ −− xxxx
v
v
v
v
)1(...)1()1()( 21 xxxx vjjj ααα −−−=Λ
∏=
−=Λv
l
j xx l
1
)1()( α y recordando que lj
lX α= entonces
∏=
−=Λv
ll xXx
1
)1()(
donde las raíces de Λ(x) son 1)( −ljα (inversos de Xl para 1 ≤ l ≤ v). Es decir, las raíces del
polinomio localizador del error son los recíprocos de los localizadores de error Xl. La primera parte de
las técnicas para encontrar Λ(x) y calcular sus raíces se describe a continuación. A partir de la expansión de la (ec. 3.5) e igualando ésta con la (ec. 3.6), se tiene que:
1...)1()( 11
11
+Λ++Λ+Λ=−=Λ −−
=∏ xxxxXx
v
v
v
v
v
ll
Evaluando (Ec. 3.7) para el caso de v = 3 (recordar que v es número de errores que tiene R en las localidades j1, j2, . . . , jv) se tiene:
Ec. 3.5
Ec. 3.6
Ec. 3.7
51
1)( 12
23
3 +Λ+Λ+Λ=Λ xxxx
1)()()()( 3213231212
3213 +++−+++−=Λ XXXxXXXXXXxXXXxx
Lo anterior es un ejemplo para inducir el caso general, el cual describe, que para cualquier polinomio localizador de error de grado v, se encuentra que:
vv
v
ii XXXXX ++++==Λ− −∑ 1211 ...
vvvvv
v
jiji XXXXXXXXXXXX 12131212 ...... −−
<
++++++==Λ ∑
vvvvvv
v
kjikji XXXXXXXXXXXXXXX 12134213213 ... −−−−
<<
++++==Λ− ∑
M
v
v
iiv
v XXXX ...)1( 211
==Λ− ∏=
Esto es, el coeficiente del polinomio localizador de error Λi es la suma de los productos de todas las combinaciones de los localizadores de error tomados de i a la vez. La forma de la ec. 3.8 es referida como las funciones simétricas elementales de los localizadores de error. Además, desarrollando la ec. 3.4 (funciones simétricas de sumas de potencias):
il
v
li XS ∑
=
=1
ti 2,...,2,1=
vXXXS +++= K211
22
22
12 vXXXS +++= K
M
t
vtt
t XXXS 222
212 +++= K
Ec. 3.8
Ec. 3.9
52
Esta última expresión (ec. 3.9), proporciona una relación no lineal entre el síndrome y los localizadores de error. Y las funciones simétricas elementales de la ec. 3.8, proporcionan una relación también no lineal entre los coeficientes del polinomio localizador de error y los localizadores de error. Pero la clave de todo esto, es que existe una relación lineal entre el síndrome y los coeficientes del polinomio localizador de error. Esta última relación es descrita mediante las identidades de Newton. En el siguiente apartado, se demuestra la anterior relación entre el síndrome y los coeficientes del polinomio localizador de error, mediante la utilización de varias expresiones previamente establecidas. 3.15 Relación entre el polinomio localizador de error y el síndrome A continuación se procede a deducir la ecuación que establece dicha relación. Primeramente, se multiplican los dos miembros de la ec. 3.5 por el término
vljj
l
le +')(α
y se hace evaluar al polinomio localizador de error Λ(x) con 1)( −ljα . Entonces, Λ(x) = 0 (ya que
1)( −ljα es una raíz de tal polinomio), y la ec. 3.5 se transformará en:
]1)(...)()([)(0])([ 11
11
'1 +Λ++Λ+Λ===Λ −+−−
−+− llll
l
l jvjv
vjv
vljj
j ex ααααα
])()(...)()([0 '1'1
1'1
' vljvljljv
ljvj
llll
le +−++
− +Λ++Λ+Λ= αααα
donde l’= j - v, y que es una variable de apoyo para las sumatorias a desarrollar. La ec. 3.10 se mantiene para cada valor de l y l’. Esto es, para cada valor de l’, se sumará la ec. 3.10 sobre l = 1, 2, . . . , v. Quedando la ec. 3.10:
∑∑∑∑=
+
=
−+
=
+−
=
+Λ++Λ+Λ=v
l
vljj
v
l
vljj
v
l
ljjv
v
l
ljjv
l
l
l
l
l
l
l
leeee
1
'
1
1'1
1
1'1
1
' )()(...)()(0 αααα
Aplicando la ec. 3.3, a la anterior expresión, se puede reescribir ésta como:
vlvllvlv SSSS +−++− +Λ++Λ+Λ= '1'11'1' ...0 Recordando que v ≤ t, entonces la ec. 3.11 siempre especificará componentes de síndrome Si ya conocidos, y con 1 ≤ i ≤ 2t, si l’ está en el intervalo 1 ≤ l’ ≤ v. Además, j = l’ + v, se obtiene:
Ec. 3.10
Ec. 3.11
53
jjvjvvjv SSSS +Λ++Λ+Λ= −+−−− 1111 ...0
para v + 1 ≤ j ≤ 2v. Las funciones definidas por la ec. 3.12 son lo que anteriormente se identificó como las identidades de Newton. Ahora realizando un acomodo de los términos, se obtiene:
vjvvjvjjj SSSSS −+−−−− Λ−Λ−−Λ−Λ−= 112211 ...
ljl
v
lj SS −
=
Λ−= ∑1
vvvj 2,...,2,1 ++=
Esta última expresión es la base para resolver el problema de la decodificación y dicha fórmula se le conoce como la ecuación clave. Su formato matricial es el siguiente:
Λ
ΛΛ
−=
−
−+
++
+
1
1
121
132
21
2
2
1
M
L
MM
L
M
v
v
vvv
v
v
v
v
v
SSS
SSS
SSS
S
S
S
Esta última expresión relaciona a los coeficientes de Λ(x) con los componentes del síndrome y que pueden ser determinados por inversión de la matriz cuadrada contenida. 3.16 Introducción al caso del algoritmo de Berlekamp-Massey La mayoría de los cálculos requerido para decodificar códigos BCH usando el algoritmo de Peterson se centra en la solución de la ecuación matricial (ec. 3.14), que también se puede desarrollar de la siguiente forma:
−
−−−
=
Λ
ΛΛΛ
+
+
+
−
−
−++
+
+
v
v
v
v
v
v
v
vvvv
v
v
v
S
S
S
S
SSSS
SSSS
SSSS
SSSS
2
3
2
1
1
2
1
1221
2543
1432
321
MM
L
MM
L
L
L
Ec. 3.13
Ec. 3.12
Ec. 3.14
Ec. 3.15
54
Para valores de v pequeños, el método de solución que aplica el algoritmo de Peterson usando inversión de matriz no es desproporcionado. Es decir, el número de cálculos necesarios para invertir una matriz de orden v x v tiene una complejidad computacional4 de O(v3). Sin embargo existen muchas aplicaciones en la que se requiere utilizar codificadores con una mayor capacidad de corrección de errores. Para tales casos, la implementación se debe inclinar por un método de solución más eficiente. Berlekamp en 1965 analizó un método que descarta el hecho de que la matriz de las ecuaciones ec. 3.14 y ec. 3.15 no son arbitrarias en su forma, más bien, tales matrices tiene un alto grado en su estructura. Y tal estructuración es una ventaja que toma en cuenta tal método para obtener
el vector Λ mediante un procedimiento más complejo que la simple inversión matricial, pero computacionalmente mucho más simple, con una complejidad computacional4 de O(v2). Por su parte Massey en 1972, tuvo un enfoque muy cercano al de Berlekamp, donde este primero desarrolló un algoritmo iterativo que se basó en la síntesis del polinomio localizador del error como el de un registro de corrimientos con retroalimentación lineal (LFSR linear feedback shift register). Estas dos técnicas de decodificación son en ocasiones referidas como un solo procedimiento, el cual es conocido como el algoritmo iterativo de Berlekamp-Massey (BM), y que a continuación se describirá brevemente para después detallar en ejemplos de cálculo manual como también en simulaciones tanto de software como de hardware.
Partiendo de que el vector Λ se desconoce, entonces la primer fila de la ec. 3.15 define Sv+1 en términos de S1, S2, . . . , Sv. La segunda fila define Sv+2 en términos de S1, S2, . . . , Sv+1 y así en adelante. Este proceso secuencial es indicado por la propia ec. 3.13.
ljl
v
lj SS −
=
Λ−= ∑1
vvvj 2,...,2,1 ++=
Si se mantienen fijos los valores de Λ , esto puede dar lugar a una implementación de un LFSR con
sus derivaciones o retroalimentaciones dadas por Λ . Visto de esta forma, el problema se convierte o transforma en uno de diseño para un circuito LFSR, como se muestra en la siguiente figura, el cual generará la secuencia conocida de los propios síndromes previamente calculados. Para tal secuencia pueden existir varios registros de corrimiento, pero se desea encontrar el LFSR de menor longitud, ya que esto último dará el patrón de error con menor peso que los datos recibidos podrán soportar al
momento de la decodificación, esto es, un polinomio localizador de error Λ(x) del grado más bajo. Tal polinomio de grado más bajo tendrá el grado v, y hay sólo un polinomio de grado v debido a que la matriz de orden v x v del problema original es invertible. ________ 4
Basado en las referencias Moon [16] pp 253, y Blahut [17], pp 176.
Ec. 3.13
55
ljl
v
lj SS −
=
Λ−= ∑1
Figura 3.3. Síntesis de un polinomio localizador del error como un circuito de registro de corrimiento con retroalimentación lineal LFSR.
Por otra parte, la ec. 3.13 establece una relación de recurrencia entre los diferentes parámetros que la conforma, y para encontrar la recurrencia adecuada se deberá primero determinar dos cantidades: el polinomio de conexión (polinomio localizador del error) y la longitud L, esto es, un polinomio como lo establece la ec. 3.7.
1...)( 11
1 +Λ++Λ+Λ=Λ −− xxxx
v
v
v
v
cuyos coeficientes son los que aparecen en la recurrencia dada, y donde L está establecida por el grado
de tal polinomio: deg( Λ(x) ) ≤ L. En estos códigos BCH que están sobre los ya analizados campos de Galois, una forma de determinar
los coeficientes Λl es por medio del algoritmo ya mencionado de BM, el cual es un proceso inductivo
que en el µ-ésimo paso se construye una pareja (Lµ , Λ(µ )(x) ) con Λ(µ )(x) que es un polinomio cuyos coeficientes generan los primeros µ síndromes, es decir, satisface la relación de recurrencia de la ec. 3.13. La idea de este algoritmo es que en la iteración µ se calcule la siguiente salida del (µ -1)-ésimo polinomio, esto es
ll
L
l
SS −−
=
Λ−= ∑−
µµ
µ
µ)1(
1
1
ˆ
y posteriormente se reste esta cantidad a la salida deseada para obtener
Sj-1 Sj-2 Sj-v-1
−Λ1
. . .
−Λ2
Sj-v
−Λ v-2 −Λ v-1
. . .
−Λ v
Sj-v-1,
Sj-v-2,
. . .
S3,
S2,
S1
Se inicializan con Sv , Sv-1 , . . . , S1
Ec. 3.7
56
ll
L
l
SSSd −−
=
Λ=−= ∑−
µµ
µµµ
µ)1(
0
1
ˆ
En esta última expresión a dµ se le conoce como la µ-ésima discrepancia. Si dµ = 0, no se modifica el polinomio, pues éste no sólo genera los primeros µ -1 síndromes, sino también el µ-ésimo. Pero si dµ ≠ 0 se modifica el polinomio en la siguiente forma:
)()()( )1(1)1()( xxddxx mmm
−−−− Λ−Λ=Λ µµ
µµ
donde m es la más reciente iteración en la cual fue necesario modificar el polinomio de conexión o sea L m > L m-1, pues hubo un cambio de longitud. Esta elección de dicho polinomio garantiza que la discrepancia actual, dm sea nula. 3.17 Estructuración del algoritmo de Berlekamp-Massey (BM) Este apartado analizará de forma más detallada el algoritmo de BM mediante su diagrama de flujo con el propósito de conocer el conjunto de iteraciones y funciones a las cuales recurre para determinar el polinomio localizador del error. Con base en la figura 3.4, la cual muestra el diagrama de flujo de este algoritmo BM, se tiene la siguiente designación de variables: para el paso de la µ-ésima iteración se asumirá a Lµ como el grado del polinomio localizador del error Λ(µ )(x) , a dµ como la µ-ésima discrepancia, a T(x) como el nuevo polinomio de conexión para el caso de no haber discrepancia ( dµ = 0 ), a B(x) como el antiguo polinomio de conexión, y a j como la ubicación del símbolo más antiguo dentro del LFSR a partir del punto donde el registro de corrimiento falló en la secuencia. Además, hay que tener en mente que los coeficientes de todos los polinomios determinan las derivaciones o conexiones del LFSR; conforme a lo anterior el algoritmo trabaja como sigue. Inicialmente, los coeficientes de las derivaciones y la longitud del registro de corrimiento están habilitados en 1 y 0 respectivamente. Esto implica que el computo o cálculo del polinomio localizador del error Λ(0)(x) y de su propia longitud, estén con valor 1 y 0 respectivamente. El producto xΛ(0)(x) es temporalmente almacenado en el polinomio de conexión B(x). Cada vez que un componente del síndrome es tomado o procesado, un término de la discrepancia dµ es calculado a partir de los coeficientes de las derivaciones y del contenido de los registros de corrimiento propios del LFSR. Si no existe discrepancia, los coeficientes de las derivaciones generan la secuencia del síndrome dado y después el polinomio B(x) es actualizado para la siguiente iteración. Si existe discrepancia ( dµ ≠ 0 ), los coeficientes de las derivaciones no generan la secuencia del síndrome dado, y por lo tanto un nuevo polinomio de conexión T(x) para no discrepancia es calculado a partir de: las derivaciones del conjunto de registros de corrimiento, de la discrepancia dµ y del antiguo polinomio de conexión B(x).
57
La longitud del LFSR es entonces probada. Si la longitud requiere una extensión, el polinomio B(x) es normalizado y actualizado, además las derivaciones de los registros de corrimiento son modificadas por los coeficientes del polinomio T(x), también la longitud de T(x), el valor de j y la longitud del registro de corrimiento Lµ son actualizados; pero si sucede lo contrario las derivaciones del registro de corrimientos es modificado por los coeficientes del polinomio T(x), mientras que el polinomio B(x) es actualizado para la siguiente iteración. El algoritmo se detiene al finalizar la iteración µ = 2t y el resultado de Λ(2t)(x) es finalmente tomado como el polinomio localizador del error Λ(x). El grado de dicho polinomio encontrado por este algoritmo es siempre el mínimo.
)(11
01ll
L
lll
L
l
SSSd −=
−=
Λ=Λ+= ∑∑−−
µµµµ
µµ
)()()( )1( xBdxxT µµ −Λ= −
Fig. 3.4. Diagrama de flujo algoritmo Belekamp-Massey.
Inicializar µ = 0, B(x) = x, Λ(0) (x) = 1, Lµ = 0 y j = 0
µ ← µ + 1
Cómputo del error en el siguiente síndrome
dµ = 0
Cómputo del nuevo polinomio de conexión para el cual dµ = 0
Lµ −1 < µ - j Λ(µ ) (x) ← T (x)
B (x) ← (dµ )-1 Λ(µ −1 ) (x)
Λ(µ ) (x) ← T (x)
Tµ ← µ − j j ← µ − L µ -1
Lµ ← Tµ
Almacenar el antiguo registro de corrimiento después de normalización. Actualizar los registros de corrimiento. Actualizar la longitud.
B (x) ← x B (x)
µ = 2t
Detener
¿El actual diseño del registro de corrimiento da el siguiente síndrome?
Si (derivaciones OK)
No (corregir derivaciones)
¿Debe ser extendido el registro de corrimiento?
Si <
No
≥≥≥≥
No Si
58
3.18 Determinación de las raíces del polinomio localizador del error (búsqueda de Chien) Una vez que se obtiene el polinomio localizador del error Λ(x), se procede a determinar sus raíces, ya que éstas indicarán, de forma casi directa, lo posición de los errores detectados por las etapas anteriores dentro de la palabra de código recibida r(x). Recordando que el campo que más interesa en la etapa de decodificación es el denominado campo mayor GF(qm), y siendo este un campo finito, se puede examinar cada elemento de dicho campo para determinar si tales elementos son una raíz de Λ(x). La forma más común de factorizar los polinomios sobre campos de Galois, es la llamada “búsqueda de Chien”, por lo que este apartado describirá el procedimiento matemático que lo caracteriza y en apartados posteriores se abordará la eficiencia en su etapa de implementación a circuitos lógicos. Tomando como base un ejemplo, el cual supone la existencia previa de un polinomio localizador del error y de que v = 3, entonces se tiene de la ec.3.7:
33
2211)( xxxx Λ+Λ+Λ+=Λ
Ahora, si se evalúa a Λ(x) para cada elemento no cero del campo en forma sucesiva:
22 ,...,,,1 −====mqxxxx ααα
se tendrá lo siguiente:
33
221 )1()1()1(1)1( Λ+Λ+Λ+=Λ
3
32
21 )()()(1)( αααα Λ+Λ+Λ+=Λ
32
322
22
12 )()()(1)( αααα Λ+Λ+Λ+=Λ
M
32
322
22
12 )()()(1)( −−−− Λ+Λ+Λ+=Λ
mmmm qqqq αααα La automatización en el cálculo de la anterior secuencia se puede implementar eficientemente en dispositivos de hardware (circuitos lógicos secuenciales), como se muestra en la fig. 3.5, donde se observa que un conjunto de v registros son cargados inicialmente con los coeficientes del polinomio localizador del error Λ1, Λ2 . . . , Λv , y donde la salida inicial es la suma
11
1)( ==
−Λ=Λ= ∑ xj
v
j
xA
59
Si A = 1, entonces un error ha sido localizado (a partir de que Λ(x) = 0). En el siguiente paso, cada registro es multiplicado por α j, j = 1, 2, . . . , v, así los registros contendrán Λ1α , Λ2α 2, Λ3α 3 , ... , Λvα v . Ahora la salida es la suma
αα ==
−Λ=Λ= ∑ xj
j
v
j
xA 1)(1
Los registros son multiplicados otra vez por potencias sucesivas de α, dando lugar a una evaluación en α 2. Este procedimiento continua hasta que Λ(x) halla sido evaluado para todos los elementos no cero del campo.
Fig. 3.5. Algoritmo general para la búsqueda de Chien. Finalmente, si las raíces son distintas y todas residen en el campo apropiado, entonces éstas se podrán usar para determinar la ubicación de los errores. Por el contrario, si dichas raíces no son distintas o residen en un campo equivocado (no en el campo mayor GF(qm) previamente determinado), entonces la palabra recibida no está dentro de la distancia t de cualquier palabra código válida.
Λ1
α
Λ2
α 2
Λv
α v
. . .
A
60
3.19 Determinación del polinomio patrón de error
Una vez obtenidos los elementos no cero del campo GF(qm) que son las propias raíces del polinomio localizador del error Λ(x), se procede a obtener sus inversos multiplicativos, ya que estos mismos inversos son los conocidos localizadores de error, y que a su vez son los términos que integran al denominado polinomio patrón de error e(x), es decir, este último polinomio indica las posiciones de los errores que tienen que ser corregidos dentro del polinomio recibido r(x). Conociendo a e(x), lo que finalmente restaría es aplicar la siguiente expresión para que se obtenga la palabra código valida c(x) ya corregida, la cual fue obtenida por el propio codificador BCH en la parte del transmisor.
)()()( xexrxc += Para cerrar la explicación de este capítulo, se presenta a continuación un ejemplo numérico detallado, principalmente del proceso de decodificación BCH, que integra los distintos algoritmos aquí desarrollados. 3.20 Caso para ejemplificar el proceso de decodificación BCH
Se partirá de los siguientes parámetros y campos para la presente decodificación BCH: � Codificador BCH: (15,5), t = 3. � Polinomio primitivo: 1)( 4 ++= xxxp
� Polinomio generador: 1)( 245810 ++++++= xxxxxxxg
� Polinomio código: ;0)( =xc 000000000000000→
� Polinomio recibido: 3512)( xxxxr ++= 010000101000000→ Se puede observar que el número de errores que tiene la palabra recibida es de 3, y que la capacidad máxima de corrección del presente decodificador es de t =3 (la obtención de los parámetros y de los tres primeros polinomios se encuentra explicada al principio de este capítulo). Por lo tanto, se deberá tener en cuenta el uso de la tabla 3.11 del apartado 3.7, que aquí se vuelve a mostrar de la siguiente forma:
61
Potencia Polinomial Binaria Potencia Polinomial Binaria
0 = 0 0000 α7 = 1 + α + α3 1101
1 = 1 1000 α8 = 1 + α2 1010
α = α 0100 α9 = α + α3 0101
α2 = α2 0010 α10 = 1 + α + α2 1110
α3 = α3 0001 α11 = α + α2 + α3 0111
α4 = 1 + α 1100 α12 = 1 + α + α2 + α3 1111
α5 = α + α2 0110 α13 = 1 + α2 + α3 1011
α6 = α2 + α3 0011 α14 = 1 + α3 1001
Tabla 3.18. Representación de los elementos de GF(24) generados por p(x) = x4 + x + 1.
1ª etapa) Cálculo del síndrome mediante la evaluación del polinomio recibido r(x), y con base en el número de error máximos a corregir t. El conjunto de elementos del síndrome son
=S ],..,.,[ 221 tSSS y se obtienen mediante )( ii rS α= ; por lo tanto se tendrán 6 síndromes
para este caso.
1)( 35121 =++== ααααrS
1)( 6102422 =++== ααααrS
104153633 )( ααααα =++== rS
1)( 12204844 =++== ααααrS
1015256055 )( ααααα =++== rS
518307266 )( ααααα =++== rS
Habrá que mencionar que la simplificación polinomial de los términos son con base en los elementos del campo GF(24) generados por el polinomio primitivo p(x) = x4 + x + 1 (tabla 3.18), es decir, que a cada potencia de α se tiene que restar 15 (número de elementos no cero del campo) tantas veces hasta llegar a obtener una de las potencia de los elementos contenidos en dicha tabla. Por ejemplo
126072...15157272 αααα === −−−−
62
y detallando el caso completo del S6, se tiene:
)( 66 αrS =
36561266 )()()( ααα ++=S
30121830726 αααααα ++=++=S
23326 11 αααααα +=+++++=S
56 α=S
2ª etapa) Aplicación del algoritmo BM para la obtención de r(x) con base en los distintos síndromes previamente calculados. A continuación se muestran los valores que se obtienen de este algoritmo según sus valores de inicialización y de la propia secuencia de iteración µ.
B(x)=x2
B(x)<-xB(x)
¿d=0? => SI d2= S2+ΣΛlSµ-l = S2 + ΛlS1 =0 µ=µ+1=2
Tenemos: µ=1 ; B(x)=x ; Λ (1)(x)=1+x ; Lµ=1 ; j=1
B(x)= S1-1 =1
Λ(1)(x)= 1+x
L1=1
B(x)<-d1-1Λ(0)
(x)
Λ(1)(x)<-T(x)
T1=1-0=1
J=1-0=1 L1<-T1
B(x)=x B(x)<-xB(x)
¿L0=0<1? => SI T(x)= Λ(0)(x)+d1B(x)=1+x
¿d=0? => NO d1= S1+ΣΛlSµ-l = S1 = 1 µµµµ=µµµµ+1=1
Inicializar: µ =0 ; B(x)=x ; Λ(0)(x)=1 ; Lµ=0 ; j=0
63
B(x)=( α5)-1(1+x)
=α10(1+x)
Λ(3)(x)=1+x+α5
x2
L3=2
B(x)<-d3-1Λ(2)
(x)
Λ(3)(x)<-T(x)
T3=3-1=2
J=3-1=2 L3<-T3
B(x)= α10(x+x
2)
B(x)<-xB(x)
¿L2=1< µ-j=2? => SI T(x)= Λ(2)(x)+d3B(x)
=1+x+α5x2
¿d=0? => NO d3=S3+ΣΛlSµ-l=S3+ΛlS2
=S3+ΛlS2=α10+1=α5
µ=µ+1=3
Tenemos: µ =2 ; B(x)=x2 ; Λ(2)(x)=1+x ; Lµ=1 ; j=1
B(x)= α10(x
2+x
3)
B(x)<-xB(x)
¿d=0? => SI d4=S4+ΣΛlSµ-l=S4+ΛlS3+Λ2S2
=1+α10+α5
=0
µ=µ+1=4
Tenemos: µ=3 ;B(x)=α10(x+x
2); Λ(3)
(x)=1+x+α5x2 ; Lµ=2 ; j=2
64
B(x)=( α10)-1(1+x+α5
x2)
=α5(1+x+α5
x2)
Λ(5)(x)=1+x+α5
x3
L3=3
B(x)<-d5-1Λ(4)
(x)
Λ(5)(x)<-T(x)
T3=5-2=3
J=5-2=3
L3<-T3
B(x)= α10x3+α5
(x2+x)
B(x)<-xB(x)
¿L4=2<µ-j=3? => SI T(x)= Λ(4)(x)+d5B(x)
=1+x+α5x3
¿d=0? => NO d5=S5+ΣΛlSµ-l=S5+ΛlS4+Λ2S3
=α10+1+α5α10
=α10+1+α15
=α10
µ=µ+1=5
Tenemos: µ=4 ;B(x)= α10(x
2+x
3); Λ(4)
(x)=1+x+α5x2 ; Lµ=2 ; j=2
B(x)=
α10x4+α5
(x3+x
2)
B(x)<-xB(x)
¿d=0? => SI d6=S6+ΣΛlSµ-l=S6+ΛlS5+Λ2S4 +Λ3S3
=1+α10+α5
=0
µ=µ+1=6
Tenemos: µ=5; B(x)= α10x3+α5
(x2+x); Λ(5)
(x)=1+x+α5x3 ;Lµ=3;j=3
65
La tabla 3.19 resume los parámetros obtenidos por los distintos cálculos conforme se desarrolló cada iteración µ, con el propósito de observar el desenvolvimiento de tales valores y como se fue deduciendo el valor del polinomio localizador del error Λ(x) .
Iteración µ
Discrepancia dµ
B(x) Λ(µ )(x) j Lµ
0 --- x 1 0 0 1 S1 = 1 x x + 1 1 1 2 0 x2 x + 1 1 1 3 α5 α10 x2 + α10 x α5 x2 + x + 1 2 2 4 0 α10 x3 + α10 x2 α5 x2 + x + 1 2 2 5 α10 α10 x3 + α5 x2 + α5 x α5 x3 + x + 1 3 3 6 0 α10 x4 + α5 x3 + α5 x2 α5 x3 + x + 1 3 3
Tabla 3.19. Pasos del algoritmo iterativo de Berlekamp Massey.
Por lo tanto, el polinomio resultante de toda esta etapa es Λ(x) = α5 x3 + x + 1. 3ª etapa) Determinación de las raíces de Λ(x) por medio de la búsqueda de Chien. Por lo que se procederá a ejemplificar la evaluación de los distintos elementos no cero (α , α2 , α3 , . . . , α15) del campo mayor, simplemente substituyendo éstos directamente en tal polinomio y ubicar aquellos que den Λ = 0. Probando con α se tiene
)()(1)( 35 αααα ++=Λ
28 111)( ααααα +++=++=Λ
0)( 2 ≠+=Λ ααα por lo cual α no es una raíz. A continuación se presentan sólo los elementos no cero que si resultan ser raíces de Λ(x).
66
Como se puede observar, la raíces de Λ(x) son α3 , α10 y, α12. 4ª etapa) Obtención de los recíprocos de las raíces de Λ(x), ya que sus inversos indicarán la posición de los errores dentro de la palabra recibida r(x). Entonces, las ubicaciones de los errores son α12 , α5 y, α3 , por lo tanto el polinomio patrón de error será:
3512)( xxxxe ++= 5ª etapa) Corrección del error, mediante una simple suman de los propios polinomios e(x) y r(x), como se muestra a continuación
)()()( xrxexc += 35123512)( xxxxxxxc +++++=
Y finalmente la palabra que se transmitió fue:
;0)( =xc 000000000000000→
= 0 1+α12+α5α36 Λ(α12
) =
= 0 1+α10+α5α30 Λ(α10
) =
= 0 1+α3+α5α9 Λ(α3
) =
= α+α2 1+α+α5α3 Λ(α) =
α3 1/α12
= α15/α12 Λ(α12
) =
α5 1/α10
= α15/α10 Λ(α10
) =
α12 1/α3
= α15/α3 Λ(α3
) =
67
3.21 Implementación en hardware de los campos de Galois Los códigos BCH pertenecen a una clase de codificadores llamados algebraicos, ya que sus procesos de codificación y decodificación se sustentan en cálculos basados principalmente en la aritmética de los campos de Galois. Dicha característica los hace fáciles de implementar en dispositivos electrónicos conformados fundamentalmente en compuertas lógicas y memorias (registros de corrimiento), como se pudo observar en el análisis del algoritmo BM. Este apartado describe, mediante ejemplos y simulaciones, la forma en que algunas operaciones entre polinomios con coeficientes y raíces provenientes de los campos GF(2) y GF(2m) se pueden ejecutar con el uso de circuitos lógicos. Además, se tomará como base de los ejemplos la tabla 3.18, que contiene a los elementos de la extensión de campo GF(24) generados por p(x) = x4 + x + 1.
Potencia Polinomial Binaria Potencia Polinomial Binaria
0 = 0 0000 α7 = 1 + α + α3 1101
1 = 1 1000 α8 = 1 + α2 1010
α = α 0100 α9 = α + α3 0101
α2 = α2 0010 α10 = 1 + α + α2 1110
α3 = α3 0001 α11 = α + α2 + α3 0111
α4 = 1 + α 1100 α12 = 1 + α + α2 + α3 1111
α5 = α + α2 0110 α13 = 1 + α2 + α3 1011
α6 = α2 + α3 0011 α14 = 1 + α3 1001
Tabla 3.18. Representación de los elementos de GF(24) generados por p(x) = x4 + x + 1.
Para describir el caso de la multiplicación, se muestra primero el producto de un elemento β cualquiera dentro de GF(24) con el elemento α perteneciente a la misma extensión de campo GF(24), β puede quedar expresado como:
33
2210 αααβ bbbb +++=
multiplicando ambos miembros de esta expresión por α, y tomando en cuenta que α4 = 1 + α , se obtiene:
32
21303 )( ααααβ bbbbb ++++=
Ec. 3.16
68
Esta última expresión de la ec. 3.16, puede ejecutarse mediante registros de corrimiento con retroalimentación lineal (LFSR), como se aprecia en la fig. 3.6.
Figura 3.6. Circuito LFSR para la multiplicación de un elementos de GF(24) por α. Como se aprecia en el circuito anterior, b0 es retroalimentado por b3, b1 es el resultado de b3 + b0, b2 es alimentado por b1 y b3 recibe el valor del registro b2, lo anterior conforme a la que establecen los coeficientes de la ec. 3.16. Los dispositivos que se usan para almacenar los coeficientes de b0 a b3 son flip flops tipo J-K. Por ejemplo, inicialmente se almacenan los valores del elemento β = α6 = α2 + α3 (0 0 1 1) en las memorias (SR o FF-JK), posteriormente se realiza el primer corrimiento conforme a un pulso de sincronía y los nuevos valores almacenados en dichos SR serán el producto βα, como se indica a continuación:
b0 = b3 b1 = b3 + b0 b2 = b1 b3 = b2 Valores iniciales 0 0 1 1
Primer corrimiento 1 1 0 1
Tabla 3.20. Contenido de los SR en el circuito de la fig. 3.6 que indican el producto βα. El valor almacenado después del corrimiento en los SR es 1 1 0 1, que conforme a la tabla 3.18 pertenece al valor binario de α7 = 1 + α + α3, y que corresponde al producto βα = ( α2 + α3 ) α, como se detalla a continuación:
7334332 11)( αααααααααααβ =++=++=+=+=
Con lo anterior, se puede comprobar la funcionalidad de los LFSR para ejecutar una operación polinomial con base en los campos de Galois. Este tipo de circuito (fig. 3.6) se utiliza como un generador de secuencias (contador), para la simulación del modelo en VHDL del código BCH (15,7) (cap. V), ya que almacenando inicialmente los valores de 1 0 0 0 en los SR, que representa según la tabla 3.18 al elemento α, y al cabo de ir realizando corrimientos sucesivos, se presentan en tales SR los valores binarios de cada uno de los elementos no cero del campo GF(24). Al final de 15° corrimiento se tendrá el mismo valor inicial de α.
b0 + b1 b2 b3
69
Otro ejemplo es el producto βα3, que se desarrolla analíticamente continuación:
)( 33
2210
33 ααααβα bbbb +++=
63
52
410
33 ααααβα bbbb +++=
)()()1( 323
2210
33 ααααααβα ++++++= bbbb
330
232211
3 )()()( αααβα bbbbbbb ++++++= Como se puede observar en la ec. 3.17, la asignación de los coeficientes de este polinomio determina la conexión que habrá entre los SR para diseñar el LFSR que ejecutará el producto βα3. La fig. 3.7 muestra el circuito resultante de tal asignación entre los coeficientes b.
Figura 3.7. Circuito LFSR para la multiplicación de un elementos de GF(24) por α3. En este caso se almacenan los valores del elemento β = α6 = α2 + α3 (0 0 1 1) en las memorias (SR o FF-JK), posteriormente se realiza el primer corrimiento conforme a un pulso de sincronía y los nuevos valores almacenados en dichos SR serán el producto βα3, como se indica a continuación:
b0 = b1 b1 = b1 + b2 b2 = b2 + b3 b3 = b0 + b3 Valores iniciales 0 0 1 1 Primer corrimiento 0 1 0 1
Tabla 3.21. Contenido de los SR en el circuito de la fig. 3.7 que indican el producto βα3.
Ec. 3.17
b0 b1 b2 b3
b0 + b1 b2 + b3 +
70
El valor almacenado después del corrimiento en los SR es 0 1 0 1, que conforme a la tabla 3.21 pertenece al valor binario de α9 = α + α3, y que corresponde al producto βα3 = ( α2 + α3 ) α3, como se detalla a continuación:
93322653233 )( ααααααααααααβα =+=+++=+=+=
Otro caso más completo es el producto entre dos elementos de la misma extensión de campo GF(24). El circuito que ejecuta tal operación polinomial se muestra en la fig. 3.8.
Figura 3.8. Circuito LFSR para la multiplicación de dos elementos cualesquiera de GF(24). Inicialmente se cargan los valores binarios de los dos elementos a multiplicar en los registros B y C (uno por cada registro), a su vez el registro A debe estar en ceros. Después los tres conjuntos de registros (A, B y C)se desplazan cuatro veces y al final del cuarto corrimiento, el contenido que resulte en los registros de A será el valor del producto de los elementos cargado respectivamente en los registros B y C. En esta ocasión para comprobar la operación completa de este LFSR, se desarrolló una simulación con el ambiente de “simulink”, en el cual se dispuso de registros FF-JK, compuertas AND y XOR que fueron interconectadas según la fig. 3.8. La configuración en bloques de este circuito se puede observar en la fig. 3.9.
b0 + b1 b2 b3
c0 c1 c2 c3
a0
+ +
a1
+
a2
+
a3
71
Figura 3.9. Modelo en simulink para la simulación del circuito LFSR para la multiplicación de dos elementos cualesquiera de GF(24).
Para la ejecución del modelo de la fig. 3.9, primero se cargan los datos del elemento α7 (1 1 0 1) en los registros B, mientras que el elemento α11 (0 1 1 1) se cargan en los registros C, después de 4 corrimientos en los registros A aparecen los valores binarios del elemento α3 (0 0 0 1) que corresponde al producto de α7α11. Por la parte analítica se tiene lo siguiente:
))(1( 323117 ααααααα ++++=
65443232117 ααααααααααα ++++++++=
23265117 αααααααααα ++++=++=
3117 ααα =
TPN= Transición Positivo a Negativo
72
El modelo en simulik arroja 4 gráficas pertenecientes a los mismos cuatro FF-JK de los registros A, que se presentan a continuación en la fig. 3.10.
Se debe observar que los valores son a partir del segundo 8
Figura 3.10. Gráficas del modelo en simulink de los cuatro RS que reflejan los valores del proceso final de la multiplicación α7α11.
Para complementar este apartado, sólo resta incorporar circuitos más especializados para la decodificación BCH, que se abordarán o describirán en el siguiente capítulo para el caso del modelado en VHDL.
0 0 0 1
73
CAP IVCAP IVCAP IVCAP IV
Desarrollo de simulaciones para medir el desempeño de codificadores BCH
4.1Descripción de las pruebas Para tener un panorama completo sobre el desempeño de los codificadores BCH que se están analizando en esta tesis, se ha desarrollado el presente capítulo en tres apartados, el primero concerniente a las pruebas de simulación utilizando el modelo matemático5, el cual determina el cálculo de la probabilidad de error (tanto en bit como en palabra) con base en parámetros básicos (n, k, peso de Hamming de palabras código) de un codificador de bloque. El segundo es una simulación utilizando los recursos de la herramienta Simulink de Matlab, mediante la generación iterativa de palabras dato de manera aleatoria que se hacen procesar por distintos bloques programados como codificadores BCH, canales BSC y decodificadores BCH, arrojando todo lo anterior en un cálculo de tasa de error en bit. Finalmente el tercer apartado es el dedicado a las simulaciones en VHDL para programar dispositivos CPLD como codificadores y decodificadores BCH. Los resultados arrojados por los tres anteriores esquemas de simulación se muestran en gráficas que visualizan la probabilidad de error vs. la SNR. 4.2 Modelo teórico Un criterio simple para medir el desempeño de un codificador de bloque, con un número máximo t de errores corregidos (decodificación de distancia limitada6) son la Pw y Pb, que están definidas como la probabilidad de error en palabra y probabilidad de error en bit respectivamente, también conocidas como el WER y el BER. Durante la revisión bibliográfica en textos sobre codificación de canal (LIN [4], Lathi [9], Haykin [1] y Lee [11]), sólo se pudo encontrar referencia de la primera probabilidad Pw de manera muy concreta y más frecuente, definida por la siguiente expresión:
inin
tiw pp
i
nP −
+=
−
≤ ∑ )1(
1
En esta ec. 4.1, se asume la utilización de un canal BSC (canal binario simétrico), donde p se denota como su probabilidad de error (probabilidad de cruce). Básicamente, la anterior desigualdad describe un límite superior para el desempeño de la probabilidad de error en palabra decodificada para un codificador de bloque (con t errores a corregir como máximo). Por lo tanto, se tuvo que investigar con acuidad artículos que describieran el cómputo más específico de la WER y la BER en codificadores de bloque binarios (principalmente BCH). Dando lugar a fórmulas más especificas para tales cálculos, que a continuación se describen. ________ 5
Fórmula desarrollada en la referencia Desset [18], pp 914-915. 6
“bounded-distance decoding” referencia Torrieri [19], pp 613.
Ec. 4.1
74
Para calcular la probabilidad de error en bit posterior a la decodificación Pb (post-decoding BER), se tiene la siguiente expresión:
ubebb PPP +=
Y para calcular la probabilidad de error en palabra decodificada Pw, se tiene la siguiente expresión:
uweww PPP +=
En las anteriores ecuaciones 4.2 y 4.3, se podrá observar que las probabilidades Pb y Pw se conforman por un par de probabilidades provenientes de dos diferentes tipos de errores propios del proceso de decodificación, siendo las primeras Peb y Pew, mientras que las segundas son Pub y Puw. Donde Peb y Pew son las probabilidades de error (para bit y palabra respectivamente) atribuibles a palabras erróneamente decodificadas (decoding error), mientras que Pub y Puw son las probabilidades de error (para bit y palabra respectivamente) originadas por decodificación fallida (decoding failures) o también conocidas por errores provenientes de palabras “indecodificables” (undecodable word). A continuación se explica el significado que tienen dichos tipos de errores. Para entender la naturaleza de estos tipos de errores, habrá que hacer referencia al concepto de las esferas de Hamming, las cuales son una forma espacial (distancias de Hamming) de explicar la capacidad de corrección que tiene un codificador de bloque mediante circunferencias de radio t (# máximo de errores a corregir) y como su centro una palabra código. La figura 4.1 muestra lo anterior.
Fig. 4.1. Ejemplo de representación de las esferas de Hamming.
Ec. 4.2
Ec. 4.3
palabra código
c1
radio t
radio t
palabra código
c2
radio t
palabra código
cn
palabras recibidas a decodificar
con t - 1 errores
t - 1
t - 1
t - 1
palabras recibidas a decodificar
con t errores
Todas las distancias que se indican son
distancias de Hamming
75
Una vez que se hizo referencia a las esferas de Hamming, se puede entonces mencionar que un código bloque trata de corregir los símbolos erróneos (símbolos binarios para nuestro caso) dentro de una palabra recibida r si ésta yace dentro de una de las esferas de decodificación, esto es, alrededor de una de las palabra código (esferas de Hamming). Si el decodificador siempre corrige t o menos símbolos erróneos, entonces cada esfera de decodificación tiene radio t, y ninguna de las esferas se intersecan (código perfecto). Pero en un primer caso en el que ocurran más de t errores, la palabra recibida r puede yacer en una esfera de Hamming equivocada, es decir, estar alrededor de una palabra código incorrecta; o en un segundo caso, estar ubicada en el perímetro de intersección entre dos o más esferas. Si la palabra recibida se encuentra en el primer caso, el decodificador selecciona una palabra de código incorrecta según sea el centro de tal esfera, y así producirá en su decodificación una palabra dato de salida con los denominados “errores indetectables”, a esto se le conoce como errores provenientes de palabras erróneamente decodificadas. Ahora, si la palabra recibida r presenta el segundo caso, es decir, ésta se ubica en la intersección de tales fronteras, el decodificador no podrá corregir los errores pero si reconoce la existencia de tales eventos. De esta manera, el decodificador falla en su operación y lo que procede a realizar es reproducir la palabra dato d tal cual viene incorporada en la palabra r (codificación sistemática). A este tipo de error se le conoce como decodificación fallida por el arribo de “palabras indecodificables”. Para comprender mejor lo anterior, se ha desarrollado una serie de ejemplos con palabras código válidas, provenientes de un codificador BCH (15, 7) con t = 2. Para este ejemplo, se muestra la palabra dato d y su correspondiente palabra código c, donde ésta última será afectada por un vector de error e, para que con ello se origine la palabra recibida r (r = c + e) y con ésta analizar lo que entregará el decodificador a su salida.
Palabra dato d Palabra código c x0 X1 x2 x3 x4 x5 x6 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1
Palabra de error e x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0
Palabra recibida r x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 Tabla 4.1. Palabras resultado de la codificación BCH (15,7) para ejemplificar errores provenientes de
palabras erróneamente decodificadas (errores indetectables).
76
Como se podrá observar en la tabla 4.1, la palabra código c es afectada por un vector e con PH = 3 (peso de Hamming), es decir que sobrepasa la capacidad de corrección del actual código que es de t = 2. Entonces, el decodificador al tener en su entrada la palabra r que se muestra en la tabla 1, éste procede a calcular sus parámetros importantes para detectar y corregir los errores de tal palabra r (síndrome, polinomio localizador del error), y entrega a su salida la palabra dato de 7 ceros (d = 0000000), esto sucede ya que sólo puede corregir como máximo dos errores y como además su algoritmo entrega síndromes acordes a un doble error, el decodificador determina finalmente que la palabra dato correcta es d = 0000000. El ejemplo anterior corresponde a los casos de “errores indetectables”, ya que la palabra recibida fue erróneamente decodificada por encontrarse dentro de una esfera de Hamming equivocada. Por otra parte, la ejemplificación para el segundo caso requiere más elementos de comparación, para su explicación, que a continuación se muestran en la tabla 4.2.
Palabra dato d1 Palabra código c1 x0 x1 x2 x3 x4 X5 x6 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0
Palabra de error e1 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1
Palabra recibida r x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 Tabla 4.2. Palabras resultado de la codificación BCH (15,7) para ejemplificar errores provenientes por
decodificación fallida (palabras –indecodificables-). Como se puede ver en la tabla 4.2, ahora la palabra c1 es afectada por un vector de error e1 con PH = 4 (hay 4 posiciones con error), sin embargo, el decodificador entregará a la salida la palabra dato d2 = 1000001 (tabla 2), en lugar de la palabra dato original d1 = 1000010, ello debido a que la palabra recibida r se encuentra en las fronteras comunes (intersección) de dos esferas de Hamming con igual número de palabras código como sus centros y con radios iguales a 4 (t = 4), provocando que el decodificador no tenga otra opción que extraer la palabra dato tal cual viene adjuntada a la palabra recibida r (codificación sistemática).
77
La tabla 4.3 muestra la otra palabra código c2 que interviene en el presente proceso de decodificación.
Palabra dato d2 Palabra código c2 x0 x1 x2 x3 x4 x5 x6 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 0 0 1
Palabra de error e2 x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0
Palabra recibida r x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1
Tabla 4.3. Palabras complementarias de la codificación BCH (15,7) para ejemplificar errores provenientes por decodificación fallida (palabras –indecodificables-).
Se puede observar en la tabla 4.3 que la palabra recibida r, resultado de r = c2 + e2, es la misma palabra r que se muestra en la tabla 2, sólo que en este última tabla la palabra de error e2 es diferente a e1, pero con igual número de posiciones con error y que se aplica a la palabra código c2 resultado de codificar a la palabra dato d1 = 1000001, que es la arrojada originalmente por el decodificador de manera fallida.
Fig. 4.2. Esquemas de esferas de Hamming para el caso de decodificación fallida.
palabras recibidas a decodificar con t = 2 errores
palabra código c1
t = 4
palabra código c2
t = 4
t = 2 t = 2
palabra r que está en la intersección de las esferas de c1
y de c2 (con t = 4 errores)
78
La figura 4.2 brinda una esquematización del caso de error por decodificación fallida, donde se muestra la intersección que presentan dos esferas de Hamming con una palabra r recibida que es común a dos palabras código pero con dos vectores de error diferentes. Lo que resta presentar del modelo matemático son el desglose de las ecuaciones 4.2 y 4.3 que a continuación se aborda. Conforme a la referencia Desset [18], se tienen las siguientes expresiones que determinan el cálculo propio de las distintas probabilidades debidas a patrones de error indetectables y palabras “indecodificables”. Retomando primeramente la ec. 4.2 perteneciente a la probabilidad de error en bit Pb:
ubebb PPP +=
se tiene que la probabilidad Peb está determinada por:
n
bpp
i
nP iini
n
tieb η−
+=
−
= ∑ )1(
1
donde: p es la probabilidad de error perteneciente al canal binario simétrico (BSC)
n longitud del código (palabra código)
t número de errores máximos a corregir
η densidad de código
bi peso promedio de palabras r
i
n combinaciones de n elementos tomados en i maneras (coeficientes binomiales)
El parámetro densidad de código η está definido como la relación entre el número de palabras contenidas en esferas de Hamming de radio t alrededor de todas las palabras código válidas sobre el número total de palabras de longitud n, y se determina para el caso binario como:
kn
t
i i
n
−=∑
=2
0η
Ec. 4.2
Ec. 4.4
Ec. 4.5
79
Ahora, el parámetro bi se define como el peso promedio de Hamming de las palabras erróneas de peso i recibidas después de que han sido decodificadas; el cómputo para los valores de bi se realiza mediante el conteo del número de formas para decodificar una palabra recibida r de peso i dentro de palabras de diferentes pesos, para ello se hace uso de la distribución de los pesos de tales palabra y de un factor Ni,j., que posteriormente se detallan. Entonces la expresión para el cálculo de bi es:
∑
∑+
−=
+
−==),(
,
),(
,
ntimin
tijijj
ntimin
tijijj
i
NA
jNA
b
donde: Aj es el número de palabras código con peso de Hamming igual a j
Nj,i factor que denota el número de palabras de peso i pertenecientes a la esfera de Hamming de radio t alrededor de una palabra código de peso j.
Este último factor se calcula por medio de la siguiente expresión:
( ),
,,2/)(
0∑
−−−
=
−
+
initmin
l l
in
l
iδδ
δ 0≥−= jiδ
=jiN ,
( ),
,,2/)(
0∑
−−−
=
+−
δδ
δ
initmin
l l
in
l
i 0≥−= ijδ
Solamente para efectos del orden de los índices i y j que aparecen en la ec. 4.7, se puede reafirmar que el factor Ni,j es el número de palabras de peso de Hamming igual a j pertenecientes a la esfera de Hamming de radio t alrededor de una palabra código válida de peso i. Por su parte, la expresión para calcular la probabilidad Pub es:
n
ipp
i
nP ini
n
tiub )1()1(
1
η−−
= −
+=∑
Finalmente, retomando la ec. 4.3 perteneciente a la probabilidad de error en palabra Pw:
Ec. 4.6
Ec. 4.7
Ec. 4.8
80
uweww PPP +=
donde la probabilidad Pew está determinada por:
ηinin
tiew pp
i
nP −
+=
−
= ∑ )1(
1
y para la probabilidad Puw se tiene:
)1()1(1
η−−
= −
+=∑ ini
n
tiuw pp
i
nP
Con las anteriores ecuaciones se tiene completo ya el modelado matemático7, y con base en éste se ha desarrollado un esquema de simulación para medir el desempeño de cuatro distintos códigos BCH, que a continuación se detalla. ________ 7
Fórmulas desarrollada en la referencia Desset [18], pp 914-915.
Ec. 4.3
Ec. 4.9
Ec. 4.10
81
4.3 Simulaciones del modelo teórico Para tales simulaciones vía software, se dispuso del paquete de programación Matlab, con el cual se obtuvieron una serie de gráficas de desempeño (BER vs SNR, y WER vs. SNR) de algunos codificadores BCH. A continuación se describe el diagrama de flujo general que se desarrolló para determinar los valores de Pb (BER) y Pw (WER), con base en el conjunto de ecuaciones de la 4.2 a la 4.10, expuesta en el apartado anterior.
Fig. 4.3. Diagrama de flujo para el cálculo de Pb.
Inicio
Definir datos básicos del
codificador n, k, t
Definir el valor de p para el presente
cálculo
Obtener la distribución de los pesos de Hamming de
las palabras código Aj
Cálculo del parámetro
η
Cálculo del parámetro
Ν i , j
Cálculo de bi , desde i = t + 1 hasta n
Cálculo de Peb y Pub
Fin
82
Así como se estableció un diagrama para el algoritmo de cálculo para Pb, también se tiene un diagrama de flujo, pero ahora para calcular Pw.
Fig. 4.4. Diagrama de flujo para el cálculo de Pw.
Inicio
Definir datos básicos del
codificador n, k, t
Definir el valor de p para el presente
cálculo
Cálculo del parámetro
η
Cálculo de Pew y Puw
Fin
83
4.4 Resultados gráficos del modelo teórico En este apartado se presentan las gráficas pertenecientes al desempeño de 3 casos de códigos BCH basadas en el modelo teórico. Sólo hay que recalcar que el parámetro de la SNR (Eb/N0) que se presenta en decibeles (dB’s), se obtiene en función de la probabilidad de error p de un BSC, y por ello se muestra en la parte de anexos una lista de equivalencias entre los valores de estas dos cantidades. Caso BCH (15, 7) donde t = 2.
Fig. 4.5. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (15, 7).
84
Caso BCH (15, 5) donde t = 3.
Fig. 4.6. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (15, 5).
85
Caso BCH (7, 4) donde t = 1.
Fig. 4.7. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (7, 4).
86
4.5 Simulaciones por bloques de software en simulink. En este segundo modelado de pruebas se aplicó el concepto de la simulación tipo Monte Carlo, pero ahora en el ambiente de la herramienta “Simulink”, que permite simular sistemas dinámicos mediante la utilización e interconexión de diagramas de bloques. Dichos bloque fueron seleccionados de acuerdo a las distintas etapas básicas de una transmisión digital de banda base con su correspondiente etapa de codificación de canal (códigos BCH), y al final de dicho proceso se calculó la tasa de errores (por bit y por palabra) que presentó todo el esquema, con base en un millón de datos binarios procesados. A continuación se muestra un esquema general de la simulación en “Simulink”, que se configuró para medir también el desempeño de los cuatro tipos de codificacores BCH que se abordaron en el modelo matemático anterior.
Fig. 4.8. Modelo general a bloques para la simulación de códigos BCH en “Simulink”.
4.6 Descripción y configuración de los bloques en simulink. Generador de datos aleatorios.
Es el primer bloque a considerar ya que es tiene como función la de generar el tren de datos binarios aleatorios que se conformarán en palabras de datos d a ser codificadas; y sus parámetros a configurar son: Probabilidad de emitir cero: [0.5] Tiempo de muestro: 0.00001 para 1 millón de datos Semilla inicial: [12345] Muestras por trama: 7 para el caso del (15, 7)
87
Codificador BCH:
Este bloque es el codificador de canal tipo BCH que se desea evaluar. Para el caso de un codificador BCH (15, 7), se tienen los siguientes parámetros: Longitud de la palabra código n: 15 Longitud del mensaje (palabra dato k): 7 Canal simétrico binario (BSC):
Este bloque define el tipo de canal por el cual se transmitirán los dígitos binarios de banda base, los cuales se verán afectados por las características propias de dicho canal. Es importante remarcar que el parámetro a modificar en este bloque es la probabilidad de error de transición p, pero que estará en función del valor de la SNR que se desee evaluar con base en el comportamiento de una señal antipodal (según capítulo II). Por lo anterior, se presenta en los anexos un listado que relaciona los valores de la SNR con su correspondiente valor de probabilidad de error p. Los datos a configurar de este bloque son: Probabilidad de error p: 0.05628 (para una SNR=1dB) Semilla inicial: 2137 Decodificador BCH:
Aquí se debe emparejar el tipo de decodificador según el codificador BCH que se eligió en la etapa de transmisión, y sus parámetros son (caso BCH (15, 7)): Longitud de la palabra código n: 15 Longitud del mensaje (palabra dato k): 7 Capacidad de corrección de errores t: 2
88
Módulo calculador de las tasa de error y su respectivo desplegado de resultados (display): Esta es la última etapa del modelado de simulación dinámica, en el cual se calcula el número de dígitos binarios procesados, el número de datos errados y la probabilidad de error por bit decodificado (BER), el cual corresponde al cálculo de Pb del modelo matemático. Los parámetros de este módulo son: Retardo en recepción: 0 Retardo en el cómputo: 0 Num. Máx. de símbolos: 1e6 (para caso de 1 millón) Modo de cómputo: Trama completa Salida de datos: por puerto (para conectar el display) El modelo de la fig. 4.8, como resultado de su comparación de datos binarios (uno a uno), arroja la tasa de error por dígito binario decodificado, el denominado Pb, pero para obtener el valor de la probabilidad de error por palabra Pw, se tuvieron que almacenar los datos de la palabra dato antes de ser codificada y los datos después de ser decodificados, en dos variables que posteriormente con algoritmos en “Matlab” se compararon palabra a palabra para calcular tal tasa. La fig. 4.9 esquematiza tal adecuación al modelado de “Simulink”
Fig. 4.9. Modelo general a bloques en “Simulink”, para almacenar las palabras d.
# de datos procesados
# de datos erroneos
Probabilidad de error Pb
89
4.7 Resultados gráficos del modelo de simulación por bloques “simulink” En este apartado se presentan las gráficas pertenecientes al desempeño de los 3 casos de códigos BCH abordados anteriormente, pero ahora basadas en el modelo de “Simulink”. Caso BCH (15, 7) donde t = 2.
Fig. 4.10. Gráfica comparativa entre Pb y Pw, para desempeño en “Simulink” del código BCH (15, 7).
90
Caso BCH (15, 5) donde t = 3.
Fig. 4.11. Gráfica comparativa entre Pb y Pw, para desempeño en “Simulink” del código BCH (15, 5).
91
Caso BCH (7, 4) donde t = 1.
Fig. 4.12. Gráfica comparativa entre Pb y Pw, para desempeño en “Simulink” del código BCH (7, 4).
92
4.8 Estructura de la simulación con elementos de hardware En este tercer escenario de pruebas se hizo uso del lenguaje VHDL para configurar dispositivos CPLD’s (familia “Ultra37000” y familia “Delta39K”), tomando como base códigos fuente de la referencia Jamro [20], que fueron adaptados para ejecutar el siguiente esquema general de simulación.
Fig. 4.13. Diagrama a bloques para la simulación en hardware de los códigos BCH. Para la operación de este esquema de simulación, se requirió de una ejecución por subgrupos de los módulos, lo anterior para evitar la complejidad de la sincronía conjunta de todas las partes. Por lo anterior, fue necesario correr la simulación inicialmente con los módulos interconectados al coder, donde primero se cargaron las palabras dato al generador de datos (vía PC) para que éstas fueron incorporadas de manera serial al coder, después éste último entregaba al módulo canal la palabra ya codificada para que finalmente se pudieran leer las palabras código por parte de los procesos en PC. Una vez que se obtienen las palabras código en PC, es aquí donde por programación en Matlab se alteraban dichas palabras para simular el efecto del ruido (AWGN), ello mediante un valor de Pe específico con base en la SNR de una señal antipodal (ver anexo tabla Pe vs. SNR). Después de que se modifican las palabras código en PC, estas palabra ahora denominadas “palabras recibidas”, se introducen en el modulo canal.
Generador
de datos Canal
(BSC)
Coder
BCH
(n,k)
Decoder
BCH
(n,k)
Recolector
de datos
din
Vdin
dout
dout
din
Vdout
Pe
(k)
(k)
Implementación en PIC’s
Implementación en CPLD’s
Carga y lectura de
datos
Proceso en PC
93
Después de todo lo anterior, viene la ejecución del otro subgrupo de módulos interconectados ahora al decoder, donde la palabra recibida es enviada por parte del modulo canal al modulo decoder para su posterior decodificación; una vez que se tiene la palabra dato corregida, ésta se envía de manera serial al modulo recolector de datos, para que después sean leídas por los procesos en PC. Finalmente, ya que se tienen todos las palabras datos antes y después de su paso por todas las etapas del esquema de la fig. 1, con recursos de Matlab y Excel, se procedió a calcular el número de dígitos binarios y palabras completas con error, para que con ello se pudieran determinar sus correspondientes tasas de error. A continuación se describen los módulos desarrollados en VHDL, para entender la configuración de las distintas etapas de la codificación y decodificación BCH a las que esta tesis se está abocando. 4.9 El codificador (coder) El proceso de codificación fue expuesto en el capítulo III, por lo que ahora se abordará la forma en que dicho proceso fue adaptado para el ambiente en VHDL. El módulo coder consiste en dos entidades, una (ering) como registro de corrimiento con retroalimentación lineal (LFSR) y otra (ecount) como sistema de control.
Fig. 4.14. Módulo general coder con sus señales de entrada-salida y sus entidades VHDL para un codificador BCH.
La entidad “ering” se dedica a describir el circuito del codificador cíclico sistemático a simular, siendo un ejemplo de esto el siguiente circuito para el caso del codificador BCH (15, 7), que se muestra en la fig. 4.15.
Coder BCH
(n,k)
din
vdin dout
ering ecount reset
clk
94
Fig. 4.15. Circuito lógico para la implementación del codificador BCH (15,7) sistemático mediante un
registro de corrimiento con retroalimentación lineal (LFSR). Por su parte la entidad “ecount”, tiene como propósito controlar la secuencia de los datos a procesar en todo el codificador, ello mediante el conteo de ciclos de reloj según el tamaño de la palabra de entrada (k) y de salida (n). El contador está conformado por un LFSR según el polinomio primitivo p(x) que genere todos los elementos de la extensión de campo GF(2m). Para el caso del código (15,7), m = 4 y por lo tanto su polinomio p(x) = x4 + x + 1. El siguiente esquema de la fig. 4.16 muestra tal circuito. Fig. 4.16. Circuito lógico secuencial para el conteo de ciclos implementado en la entidad “ecount”, con base en el polinomio x4 + x + 1 para complementar el control de codificador BCH (15,7) sistemático.
R0 R1 R2 R3 + R4
din
R5 + R6 R7 + +
rin
reset
dout
rll
rll � señal de control para el LFSR rin � señal para habilitar la salida con din (codificador sistemático)
C(0) + C(1) C(2)
C(3)
reset
95
La referencia de tiempo (reloj) que tiene este módulo se recibe mediante la señal de entrada “clk” (fig. 4.14) y con la implementación del anterior circuito (fig. 4.16), la entidad “ecount” coordina la secuencia de las demás señales de entrada-salida “din” (terminal de entrada para la palabra dato) y “dout” (terminal de salida para la palabra código), y mediante otro conjunto de flip-flops habilita la señal “vdin” (indicador de control para la recepción de datos en el buffer de entrada) y también controla la funcionalidad dentro de todo el sistema de la señal “reset” (reiniciar la operación del coder). Para corroborar el buen funcionamiento de la etapa del codificador (coder) con el lenguaje VHDL, se ejecutó el software de simulación “Active-HDL Sim”. La fig. 4.17 muestra la interfaz gráfica de dicho software con las formas de onda resultantes.
Fig. 4.17. Ventana de la aplicación “Active-HDL Sim” para simular la codificación de una palabra
dato, correspondiente al codificador BCH (15,7) sistemático.
1 0 0 1 1 1 1 MSB
Palabra dato ( d )
1 0 0 1 1 1 1 1 0 1 1 0 0 0 1
MSB
Palabra código ( c )
96
4.10 El decodificador (decoder) El proceso de la decodificación también fue expuesto en el capítulo III, por lo que ahora se abordará la forma en que dicho proceso fue adaptado para el ambiente en VHDL. El modulo decoder consiste principalmente de tres procesos que se son:
� Cálculo del síndrome � Algoritmo BM � Búsqueda de Chien
Además de otros subprocesos para el control de secuencias, relojes y de corrección de los errores detectados.
Fig. 4.18. Módulo general decoder con sus señales de entrada-salida y sus entidades VHDL para un decodificador BCH.
S1, S2,... S3, S6,... S2t-1
Sn0 Sn1 Sn2 Sn(t) Sn(t+1) Sn(2t-2)
S5, S10,...
BMA
Ch0 Ch1 Ch(t)Sum
buffer
Sn3
din
S3 S2 S1 S2t-1 S5
dout
Calculo del
Síndrome
Búsqueda
de Chien
Rearreglo del
Síndrome
Sistema
de
Control
Fig. 4.19. Diagrama a bloques de las distintas entidades que describen el módulo general decoder.
Decoder BCH
(n,k)
din
vdout
dout
reset
clk
97
Para corroborar el buen funcionamiento de la etapa del decodificador (decoder) con el lenguaje VHDL, se ejecutó el software de simulación “Active-HDL Sim”. La fig. 4.20 muestra la interfaz gráfica de dicho software con las formas de onda resultantes, además se puede observar que la palabra recibida tiene un error, el cual después de ser decodificada éste es detectado y corregido para dar lugar a la palabra dato original.
Fig. 4.20. Módulo general decoder con sus señales de entrada-salida y sus entidades VHDL para un decodificador BCH con un error procesado.
Como se puede observar en la fig. 4.20, el error aleatorio que presenta la palabra recibida r fue detectado y corregido por el decodificador BCH (15, 7). Ahora lo que corresponde es mostrar el mismo proceso pero con dos errores en tal palabra, que se visualiza en la fig. 4.21.
1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 MSB
Palabra recibida ( r )
error
MSB
Palabra dato obtenida
( d ) 1 0 0 1 1 1 1
98
Fig. 4.21. Módulo general decoder con sus señales de entrada-salida y sus entidades VHDL para un decodificador BCH con dos errores procesados.
Cabe mencionar que algunos programas adaptados para esta simulación se presentan en la parte de anexos, pero todos los programas utilizados en la tesis se contemplan grabar en un disco compacto (CD).
1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 MSB
Palabra recibida ( r )
error
Palabra dato obtenida
( d ) 1 0 0 1 1 1 1
MSB
99
4.11 Resultados gráficos del modelo en hardware En este apartado se presentan las gráficas pertenecientes al desempeño de 3 casos de códigos BCH basadas en el modelo de simulación con CPLD’s utilizando el lenguaje de descripción para dichos dispositivos VHDL. Nuevamente hay que recalcar que el parámetro de la SNR (Eb/N0) que se presenta en decibeles, se obtiene en función de la probabilidad de error p de un BSC, y por ello se tiene en el anexo una lista de equivalencias entre los valores de estas dos cantidades. Caso BCH (15, 7) donde t = 2.
Fig. 4.22. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (15, 7).
100
Caso BCH (15, 5) donde t = 3.
Fig. 4.23. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (15, 5). Hay que mencionar que debido a la complejidad para integrar varia etapas en la simulación en VHDL y de la baja capacidad de almacenamiento en algunos elementos, se perdio en cantidad de símbolos a probar y también aumento el tiempo para poder completar un mayor número de corridas, por lo tanto el desempeño de este código en especial sólo se tuvo valores confiables hasta los 2 decibeles.
101
Caso BCH (7, 4) donde t = 1.
Fig. 4.24. Gráfica comparativa entre Pb y Pw, para desempeño del código BCH (7, 4).
102
CAP VCAP VCAP VCAP V
Inferencia Comparativa
5.1 Desempeño comparativo
En este apartado se hace una comparación de las distintas gráficas obtenidas en los escenarios de simulación del capítulo IV, con el objetivo de poder deducir el desempeño individual de cada código y posteriormente inferir éste respecto de los demás. Una vez que se han obtenido las graficas de Pb y Pw en los tres modelos, es pertinente mencionar lo revelador que resultaron dichos desempeños al coincidir en los tres tipos de pruebas, ya que partiendo desde un análisis teórico pasando por un planteamiento de modelos matemáticos y resolución de ejemplo, continuando con simulaciones y finalizando con la implementación en hardware, se pudo demostrar lo provechoso que resulta analizar a los codificadores de canal desde esta perspectiva. Primeramente se muestran las gráficas de los tres escenarios de prueba para cada código BCH, y después se intercalan estas graficas con sus correspondientes modelados (teórico y Simulink) sobre los demás códigos BCH analizados. � Gráficas de Pb para BCH (15,7) Para obtener las curvas de la fig. 5.1, se realizó una corrida de un millón de datos binarios pertenecientes al caso en Simulink, mientras que para el modelo en VHDL se realizó una prueba con un total de 25,500 dígitos binarios por cada valor de SNR. En lo que respecta al caso teórico, se evaluó su fórmula (Pb) desde 0 a 5 dBs con incrementos de 0.25 dBs.
103
Fig. 5.1. Gráficas de Pb vs. SNR para el desempeño del código BCH (15,7).
Con base en la fig. 5.1, se puede inferir que las curvas de desempeño correspondientes a los modelos teórico y de simulink se asemejan bastante, llegando a tener una diferencia de ajuste promedio de 0.00018714; mientras que el modelo en VHDL se comienza a separar de los dos anteriores modelos a partir de los 2 dBs, ello debido al universo limitado datos que se pudieron simular. � Gráficas de Pw para BCH (15,7) En este prueba el total de datos para el modelo en simulink fue de 142,860 palabras dato (k = 7), y para la simulación en VHDL fue de 1700 palabras, además el caso teórico fue evaluado desde 0 dBs hasta 5 dBs en incrementos de 0.25 dBs.
104
Fig. 5.2. Gráficas de Pw vs. SNR para el desempeño del código BCH (15,7).
Ahora en la fig. 5.2 se puede observar que nuevamente el modelo teórico y el de Simulink presentan un desempeño muy similar (error promedio en ajuste de – 9.85614 x 10-6); por su parte el modelo en VHDL discrepa respecto del caso en Matlab con un error promedio de – 0.00248205. � Gráficas de Pb para BCH (15,5) En lo que respecta al comportamiento del código BCH (15,5), el cual se recuerda tiene una capacidad máxima de corrección de tres errores, se dispuso también de una corrida de un millón de datos para el caso en Simulink, mientras que para el modelo en VHDL se probaron un total de 23,325 dígitos binarios por cada valor de SNR; en el caso teórico del cálculo de Pb se evaluó desde 0 dBs hasta 5 dBs con incrementos de 0.25 dBs.
105
Fig. 5.3. Gráficas de Pb vs. SNR para el desempeño del código BCH (15,5).
La fig. 5.3 muestra un comportamiento muy similar entre el modelo teórico y el caso de simulink, salvo que después de los 4 dBs, el último modelado ya no arrojaba datos confiables, es decir su valor de Pb era cero. Lo anterior se puede adecuar ejecutando una corrida de diez millones de dígitos binarios, sólo hay que aclarar que en esta oportunidad no se contaba con la capacidad suficiente en memoria de PC para ello. También sucedió lo mismo para el caso en VHDL, ya que posterior a los 2 dBs el valor en la probabilidad de error en bit se obtenía de cero. � Gráficas de Pw para BCH (15,5) Para las pruebas en el cálculo de Pw pertenecientes al código BCH (15,5), se compararon un total de 200,000 palabras dato (k=5) para el caso de simulink, mientras que para el modelo en VHDL se ejecutaron pruebas a 1,555 palabras. El modelo teórico fue evaluado de 0 dBs a 5 dBs.
106
Fig. 5.4. Gráficas de Pw vs. SNR para el desempeño del código BCH (15,5).
El análisis que se observa de este código a partir de esta fig. 5.4 es el de un desempeño muy regular entre los tres modelos, ello hasta donde la cantidad de las palabras simuladas lo permite, principalmente en caso de VHDL. � Gráficas de Pb para BCH (7,4) Para obtener las curvas de la fig. 5.5, se realizó una corrida de un millón de datos binarios pertenecientes al caso en simulink, mientras que para el modelo en VHDL se realizó una prueba con un total de 25,480 dígitos binarios por cada valor de SNR. En lo que respecta al caso teórico, se evaluó su fórmula (Pb) desde 0 a 5 dBs con incrementos de 0.25 dBs.
107
Fig. 5.5. Gráficas de Pb vs. SNR para el desempeño del código BCH (7,4).
Según se observa en la fig. 5.5, se puede concluir que las curvas de desempeño correspondientes a los modelos teórico y de Simulink se asemejan bastante; mientras que el modelo en VHDL se comienza a separar de los dos anteriores modelos a partir de los 3 dBs, ello debido al universo datos que se pudieron simular. � Gráficas de Pw para BCH (7,4) En este prueba el total de datos para el modelo en simulink fue de 250,000 palabras dato (k = 7) mientras que para la simulación en VHDL fue de 3460 palabras, además el caso teórico fue evaluado desde 0 dBs hasta 5 dBs en incrementos de 0.25 dBs.
108
Fig. 5.6. Gráficas de Pw vs. SNR para el desempeño del código BCH (7,4).
Ahora en la fig. 5.6 se puede observar que nuevamente el modelo teórico y el de Simulink presentan un desempeño muy similar; por su parte el modelo en VHDL comienza a discrepar respecto de los anteriores a partir de los 4 dB’s., ello por el número de palabras que se pudieron simular en VHDL.
109
� Gráficas comparativas de Pb entre los códigos BCH analizados En este sección se presentan las gráficas del desempeño teórico (Pb) pertenecientes a todos los códigos BCH que se simularon. Además, para tomar un comportamiento de referencia sin un proceso de codificación de canal, se incorporó en cada figura la curva de desempeño para una señal antipodal que se analizó en el capítulo II.
Fig. 5.7. Gráficas de Pb para comparar el desempeño teórico entre los código BCH. Observando la fig. 5.7 se puede inferir que hay un mejor desempeño del código BCH (15, 5) respecto al código BCH (15, 7) en el parámetro de Pb (diferencia de 1.3 dB’s a un BER = 0.0032), sin embargo
si se hace referencia al parámetro de eficiencia ( η = k / n ), se podrá advertir que el código BCH (15,7)
es más eficiente (η = 0.466) que el código (15, 5) (η = 0.333), ya que dentro de su palabra código
alberga una palabra dato de mayor longitud (7 > 5) y por lo tanto se tendrá una mayor tasa de información de la fuente. Lo anterior también se aplica para el caso de comparar el código BCH (15, 5) y el código BCH (7, 4), en el que existe una diferencia de 2.4 dB’s.
1.3 dB’s de
diferencia
2.4 dB’s de
diferencia
110
A continuación se conjuntaron las gráficas del desempeño en Simulink (Pb) pertenecientes a todos los códigos BCH que se analizaron.
Fig. 5.8. Gráficas de Pb para comparar el desempeño en Simulink entre los código BCH. Nuevamente en esta fig. 5.8 se identifica el mismo comportamiento que en la fig. 5.7, el cual también presenta una diferencia de 1.3 dB’s en promedio a favor del código BCH (15, 5) respecto al código BCH (15, 7) y de 2.8 dB’s en referencia al código BCH (7, 4).
1.3 dB’s de
diferencia
2.8 dB’s de
diferencia
111
� Gráficas comparativas de Pw entre los códigos BCH analizados Ahora se intercalaron las gráficas del desempeño teórico (Pw) pertenecientes a todos los códigos BCH que se simularon; también se incorporó en cada figura la curva de desempeño para una señal antipodal.
Fig. 5.9. Gráficas de Pw para comparar el desempeño teórico entre los código BCH.
Tanto en la fig. 5.9 como en la fig. 5.10 se puede observar una diferencia promedio de 1.5 dBs a favor del código BCH (15,5), ello cuando se trata de la tasa de error en palabra codificada Pw, esto se puede advertir por dos razones, la primera que hay una mayor capacidad de corrección de errores en el primer código (t = 3) y segundo por el tamaño de la palabra dato (k = 5) que tiene respecto al código (15,7) (k = 7), lo que genera un menor universo de palabra código (32 en el primer caso y 128 en el segundo) y que por consecuencia se tenga una menor incidencia en la decodificación de tipo errónea y en la decodificación fallida (Pew y Puw, cap. IV). Además se observa en la misma fig. 5.9 una diferencia de 2.1 dB’s entre el código BCH (15,5) y el código BCH (7,4), que se debe a las mismas razones anterior mente expuesta.
1.5 dB’s de
diferencia
2.1 dB’s de
diferencia
112
Fig. 5.10. Gráficas de Pw para comparar el desempeño en simulink entre los código BCH.
También en esta comparación (fig. 5.10) entre los distintos codificadores respecto al parámetro Pw, con base en el modelo de simulink, se observan las mismas diferencia en dB’s que al igual existen en el análisis de la fig. 5.9. Lo anterior nuevamente se debe a la capacidad de corrección de errores que tiene el código BCH (15,5) respecto a demás, pero todo tiene un costo, y es que al ganar capacidad de corrección también se gana en complejidad sobre el diseño del algoritmo para el codificador pero sobre todo en el algoritmo del decodificador.
2.1 dB’s de
diferencia
1.5 dB’s de
diferencia
113
5.2 Conclusiones Conforme a lo analizado y desarrollado durante esta tesis, se puede concluir lo siguiente: Lo abstracto del álgebra moderna, en especial los sistemas denominados campos de Galois, tienen en los sistemas de comunicaciones digitales un buen ejemplo para materializar sus aplicaciones. Lo anterior fue el corazón de este trabajo, y donde se demostró la estrecha vinculación que existe entre las matemáticas y la ingeniería. La forma en que se describió la operabilidad de los GF, hace posible su implementación tanto electrónicamente (hardware) como lógicamente (software) de forma muy eficiente cuando se trata de diseñar algoritmos para codificadores de canal, en particular los códigos algebráicos como los BCH. Se confirmó la similitud en el desempeño de los códigos BCH analizados, con base en sus parámetros BER y WER, lo anterior mediante pruebas integrales en hardware y software de tres modelos de simulación: teórico, Matlab y VHDL (electrónico), como se pudo describir en el apartado anterior 5.1. En lo que respecta al modelo teórico, éste se menciona o se aborda de manera somera en los principales libros en materia de codificadores de canal consultados, si acaso se hace referencia a fórmulas para determinar la WER sin tomar en cuenta los 2 tipos de errores y decodificaciones fallidas que se mencionan en el capítulo IV. Además, lo que se expone gráficamente en algunas referencias bibliográficas son desempeños de SNR vs. Pw como fronteras o límites superiores a las que un código BCH está caracterizado (ec. 4.1). Con base en los escenarios de simulación en software y hardware que fueron trabajados, se puede mencionar que para tener una visión amplia y rápida sobre el comportamiento de los códigos cíclicos, al menos en los parámetros Pb y Pw, los modelos teóricos y de Simulink son una buena alternativa. Las herramientas de hardware y software que fueron desarrolladas en la presente tesis, con base en referencias tanto escritas como de internet, junto con casos detallados de codificación, decodificación y las gráficas que muestran el desempeño de los códigos BCH, integran un documento didáctico para incrementar el potencial cognitivo del estudiante en ingeniería respecto a los codificadores de canal. Finalmente, el documento aquí desarrollado se puede considerar como un medio de enseñanza, es decir “software con el necesario hardware en un contexto particular de comunicación instruccional”. 5.3 Trabajos a futuro Para ampliar el rango y mejorar el tiempo de operación del modelado en VHDL, será necesario contar con un esquema de prueba integral el cual opere en tiempo real, el cual cuente con un circuito codificador y decodificador con plena sincronía entre todos los módulos que intervienen en dicha simulación.
114
Referencias
[1] Simon Haykin, Sistemas de Comunicación, (Limusa Wiley, 2002) [2] J. G. Proakis, M. Salehi, Contemporary Communication System Using Matlab, (The PWS BookWare Companion Series, 1998) [3] R. Ziemer, W. Tranter, Principles of Communications, (John Wiley & Sons, Inc., 5th ed., 2002) [4] S. Lin, D. J. Costelo, Error Control Coding, (Prentince Hall, 2nd ed., 2004) [5] W. Wesley, E. J. Weldon, Error-Correcting Codes, (The MIT Press, 2nd ed., 1996) [6] B. Carlson, P. B. Crilly and J. C. Rutledge, Communication System, (Mc Graw Hill, 5th ed., 2002) [7] L. W. Couch II, Sistemas de Comunicación Digitales y Analógicos, (Pearson, 5ª ed., 1998) [8] H. Hsu, Analog and Digital Communications, (Mc Graw Hill, 2nd ed., 2003) [9] B. P. Lathi, Sistemas de Comunicación, (Interamericana Mc Graw Hill, 1986) [10] J. Kurzweil, An Introduction to Digital Communications, (John Wiley & Sons, 2000) [11] L. H. Charles Lee, Error-Control Block Codes for Communications Engineers, (Artech House) [12] I. N. Herstein, Álgebra Modernar, Grupos-Anillos-Campos-Teoría de Galois, (Trillas, Biblioteca de Matemática Superior, 5ª reimpresión, 2006). [13] A. G. Kurosh, Curso de Álgebra Superior, [14] L. H. Charles Lee, Error-Control Block Codes for Communications Engineers, (Artech Hose, 2000). [15] W. W. Peterson, E. J. Weldon, Jr., Error-Correcting Codes, (The MIT Press, 2nd ed., 1996). [16] T. K. Moon, Error Correction Codes, Mathematical Methods and Algorithms, (Wiley-Interscience, 2005). [17] R. E. Blahut, Theory and Practice of Error Control Codes (Reading, MA: Addison-Wesley, 1983).
115
[18] C. Desset, L. Vandendorpe, B. Macq, “Computing the Word-, Symbol-, and Bit Error Rates for Block Error-Correcting Codes”, IEEE Trans. Commun., vol. 52, pp. 910-921, Jun 2004. [19] D. J. Torrieri, “Information-bit, information-symbol, and decoded-symbol error rates for linear block codes”, IEEE Trans. Commun., vol. 36, pp. 613-617, May 1988. [20] Ernest Jamro, The design of a VHDL based synthesis toll for BCH codecs, a thesis submitted to the University of Huddersfield for the degree of master of philosophy, School of Engineering the University of Huddersfield, Sep 1997. [21] S. Brown, Z. Vranesic, Fudamentals of Digital Logic with VHDL Design (McGraw-Hill International edition, 2nd ed., 2005). [22] F. Pardo, J. A. Boluda, VHDL Lenguaje pas síntesis y modelado de circuitos (Alfaomega Ra-Ma, 2000). [23] J. M. García, E. J. Pérez, Dispositivos Lógicos Programables (PLD) Diseño práctico de aplicaciones (Alfaomega Ra-Ma, 2006).
[24] C. Pérez, Matlab
y sus Aplicaciones en las Ciencias y la Ingeniería (Pearson Prentince Hall, 2002). [25] E. R. Berlekamp, Algebraic Coding Theory, (McGraw-Hill, 1984). [26] E. R. Berlekamp, “On Decoding Binary Bose-Chaudhuri-Hocquenghem Codes”, IEEE Transactions on Information Theory, vol. 11, pp. 557-579, Oct 1965. [27] J. L. Massey, “Step-by-step Decoding of the Bose-Chaudhuri-Hocquenghem Codes”, IEEE Transactions on Information Theory, vol. 11, pp. 580-585, Oct 1965. [28] J. L. Massey, “Shift-Register Synthesis and BCH Decoding”, IEEE Transactions on Information Theory, vol. 15 (1), pp. 122-127, Jan 1969. [29] C. L. Chen, “High-Speed Decoding of BCH Codes”, IEEE Transactions on Information Theory, vol. 27(2), pp. 254-259, Mar 1981.
116
[30] F. I. Peralta, G. I. Duchen, R. Vázquez, “Complejidad Lineal y Algoritmo Berlekamp-Massey para la Construcción de Generadores de Secuencias Pseudoaleatorias”, Información Tecnológica, vol. 17 N° 3-2006, pp. 167-178, 2006, versión on-line. [31] L. N. Childs, A concrete Introduction to Higher Algebra, (Springer, 2nd ed., 2000). [32] S-W. Wei, “High-speed hardware decoder for double-error-correcting binary BCH Codes”, IEE Proceedings, vol. 136, N° 3, pp. 227-231, Jun 1989. [33] M. A. Hasan, M. Wang, V. K. Bhargava, “Modular Construction of Low Parallel Multiplier for a Class of Finite Fields GF(2m)”, IEEE Transactions on Computer, vol. 41, N° 8, pp. 962-971, Aug 1992. [34] J. Beltrán Llera, J. A. Bueno, Psicología de la Educación, (Alfaomega Marcombo, 1997). [35] J. A. Vargas Mendoza, Álgebra Abstracta, (Limusa, 1986). [36] Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, (John Wiley & Sons, 1991)
A1
Evariste Galois (1811 - 1832)
JOVEN Y REVOLUCIONARIO: Évariste Galois, nació el 25 de octubre de 1811 en Bourg-la-Reine una pequeña población en los alrededores de París, en el momento del máximo esplendor del Imperio de Napoleón, en una familia republicana, que sufre las dificultades de la caída en 1814 de Napoleón y la vuelta de la monarquía derrocada en la revolución de 1789. Su padre Nicholas Gabriel Galois, director de la escuela de la localidad que llegaría a ser alcalde de la comuna al frente del partido liberal, partidario de Napoleón. Su madre Adelaida Marie Demante, era una persona de indudables cualidades intelectuales hija de una familia de abogados muy influyente de París. Hasta los doce años, Évariste fue educado por su madre, junto con su hermana mayor Nathalie-Theodore, consiguiendo una sólida formación en latín y griego, así como en los clásicos. La educación regular de Galois comenzó en 1823, cuando ingreso en el “Collage Royal de Louis le Grand”, de París. En el Louis le Grand, Galois comenzó en este colegio inmediatamente a sensibilizarse políticamente; sus simpatías liberales y democráticas adquiridas de sus padres, estaban en consonancia con las simpatías de la mayoría de los alumnos. No obstante, durante el primer año de Galois en el Louis le Grand, las relaciones entre el alumnado y el rector recién nombrado fueron ásperas y tirantes. Los alumnos sospechaban que el nuevo rector se proponía devolver el colegio a los jesuitas. Los alumnos hicieron un plan sin excesiva trascendencia: se negaron a cantar en la capilla, a recitar en clase y a brindar por Luís XVIII en un banquete colegial. En represalia, el rector expulso a 40 alumnos sospechosos de haber encabezado la rebelión. Aunque Galois no fue expulsado, la arbitraria acción de tal rector contribuyó sin duda a fomentar los recelos que Galois pudiera sentir hacia la autoridad.
A2
Durante 1824 y 1825, Galois ganó varios premios de griego y latín. Aunque durante el tercer año, su trabajo en retórica fue considerado insuficiente y tuvo que repetir curso. En febrero de 1827 fue decisivo en la vida de Galois. Tomó su primera clase de matemáticas. El curso, impartido por Hippolyte Jean Vernier, despertó el genio matemático de Galois. Tras engullir a toda velocidad los manuales de texto, fue derecho hacia las obras maestras de la época, devorando Los elementos de Geometría de Adrien Marie Legendre, inmediatamente después se enfocó con las memorias originales de Joseph Louis Lagrange: La resolución de ecuaciones algebraicas, La teoría de funciones analíticas y Lecciones sobre cálculo de funciones. Fue sin duda de Lagrange de quien aprendió por primera vez la teoría de ecuaciones. El descubrimiento de las matemáticas provocó un sorprendente cambio en la personalidad de Galois. Empezó a descuidar las otras materias, atrayendo hacia si la hostilidad de los profesores de humanidades. Incluso Vernier, aunque sin pretender enfriar la pasión matemática de Galois, le insistió en la necesidad de trabajar más sistemáticamente. Los informes escolares de Galois lo empezaron a describir como singular, excéntrico, original y hermético. En 1828 a la edad de dieciséis años solicitó su ingreso en la “Ecole Polytechnique”. Esta era la universidad más importante de París y es probable que Galois se haya visto motivado a ingresar a ella por razones académicas. Pero también deseaba entrar a esta institución por los fuertes movimientos políticos que existían entre sus estudiantes dado que Galois al igual que sus padres, era un ferviente republicano. La admisión para la Ecole Polytechnique era mediante examen oral. Sabemos ahora que Galois, a esa edad, era un matemático superior a sus sinodales o examinadores. Galois rehusó contestar las preguntas elementales y respondió a las más elevadas con tal profundidad de conocimientos que sus examinadores no pudieron entender sus respuestas. Está por demás, decir que Galois fue reprobado en el examen de admisión. De vuelta al Louis le Grand, Galois se incorporó a la clase de matemáticas de Louis Richard, quien se percató inmediatamente de las dotes de Galois solicitando que éste fuera admitido sin examen previo en la Ecole Polytechnique. Aunque su recomendación no fue atendida, el estímulo de Richard produjo en Galois resultados sobresalientes. En abril de 1829 Galois logró publicar su primer trabajo, se titulaba Demostración de un teorema sobre fracciones continuas periódicas, y apareció en Annales de mathematiques pures et apliques, de Joseph Díaz Georgonne. Sin embargo, este artículo no fue su objetivo primordial, ya que Galois había dirigido su atención hacia la teoría de ecuaciones, tema que había explorado por primera vez en las obras de Lagrange. A sus diecisiete años estaba atacando uno de los más difíciles problemas de las matemáticas; un problema que había mantenido en jaque a los matemáticos durante más de un siglo. Lo que Galois consiguió fue dar criterios definitivos para determinar si las soluciones de una ecuación polinómica podrían ser o no calculadas por radicales. Sin embargo, lo más notable quizá de los descubrimientos de Galois en teoría de ecuaciones fueron los métodos que ideó para estudiar el problema. Sus investigaciones abrieron las puertas de una teoría cuyas aplicaciones desbordan con mucho los límites de la teoría de ecuaciones: la teoría de grupos.
A3
La tragedia golpeó a Galois el 2 de julio de 1829 fecha en que su padre se suicidó. El reverendo de Bourg-la-Reine incluyó el nombre del alcalde Galois en maliciosos epigramas falsificados dirigidos a los familiares de Galois. El padre de Galois era un hombre bondadoso y el escándalo que se suscitó fue mayor de lo que el pudo soportar. Se colgó en su departamento de París ubicado a unos pasos del Lycee Louis-le-Grand donde estudiaba su hijo. Esta muerte impactó fuertemente a Galois y marcó el resto de su vida. Pocas semanas después de la muerte de su padre Galois nuevamente solicitó su ingreso a la Ecole Polytechnique cuando tenía dieciocho años. Durante el examen, uno de los sinodales inició una controversia matemática. Galois estaba en lo justo y lo sabia. En un acceso de cólera, mezclado con desesperación, arrojó a su sinodal el borrador del pizarrón. Galois no fue admitido en la Ecole Polytechnique. Viéndose obligado a tomar en consideración la escuela menos prestigiosa la “Ecole Normale”, Galois se presentó a los exámenes de bachillerato necesarios para ser admitido, en noviembre de 1829. Esta vez fue aprobado en razón de una excepcional calificación en matemáticas, recibiendo la categoría de universitario aproximadamente al mismo tiempo que sus trabajos sobre teoría de grupos iban a ser presentados a la Academia de Ciencias. Galois envió a Cauchy trabajos posteriores sobre la teoría de las ecuaciones, sin embargo Cauchy lo rechazó porque su trabajo tenía puntos en común con un reciente artículo publicado por Abel. Galois siguió los consejos de Cauchy y presentó un nuevo artículo titulado Condiciones en las que una ecuación pueda ser resuelta con radicales, en febrero de 1830, y en esta ocasión, Cauchy lo remitió a la Academia para ser considerado para el Gran Premio en matemáticas. Por lo que fueron enviados a Jean Baptiste Joseph Fourier, en su calidad de secretario vitalicio de la misma y el encargado de su publicación. Fourier murió en abril de 1830 y el trabajo de investigación de Galois se extravió por lo que no pudo ser nunca nominado para el premio. El premio fue otorgado exequo a Abel y a Jacobi, y Évariste acusó a la Academia de una farsa para desacreditarle. A pesar de la pérdida de la memoria enviada a Fourier, Galois publicó tres artículos aquel mismo año en el Bulletin des sciences mathematiques, astronomiques, physiques et chimiques del Barón de Ferussac. Estos trabajos presentan los fundamentos de la Teoría de Galois y prueban sin lugar a dudas que el joven había llegado más lejos que ningún otro matemático en el campo del álgebra relacionado con la resolución de ecuaciones polinómicas, ya que a sus diecinueve años Galois dominaba totalmente las ecuaciones algebraicas, en las cuales había demostrado que no podía existir una fórmula general para los grados mayores que 4 (esto era el principio de sus grandes desarrollos). Continuó describiendo aquellas ecuaciones que podían resolverse usando la adición, la multiplicación y la extracción de raíces. Por la misma época Abel había iniciado algo en este sentido, sin embargo Galois lo obtuvo todo, no sólo demostró que no hay ninguna fórmula general que sirva para todas las ecuaciones de quinto grado, sino que, aun suponiendo que se deseara establecer un método especial para cada ecuación particular, hay ecuaciones que algebraicamente no tienen solución. Con una perspicacia superior a los de otros, dio renovados enfoques a dichos problemas.
A4
En julio de 1830 estalló la revolución, los republicanos se levantaron en armas y obligaron al rey Carlos X a exiliarse. Hubo desordenes en las calles de París y el director de la Ecole Normale, M. Guigniault, encerró a los estudiantes para que no participaran en las manifestaciones. Indignado Galois intentó sin éxito escalar los muros; al no conseguirlo no tomó parte en la breve revolución. Aunque los republicanos consideraron que la abdicación del Borbón fue una gran victoria, su triunfo fue efímero. Para frustración de Galois y de otros liberales de ideología afín, el trono fue nuevamente ocupado, esta vez por Luís Felipe de Orleáns. En diciembre de 1830 M. Guigniault escribió artículos para el diario atacando a los estudiantes y Galois escribió una respuesta para la Gazette des Ecoles contraatacando a M. Guigniault por haber encerrado a los estudiantes en el colegio y llamándolo traidor por su actitud durante la revolución de julio. Fue expulsado por ello de la Ecole Normale. Tras su expulsión de la Ecole Normale se mudó a la casa de su madre en París; tan difícil resultaba convivir con él, que su propia madre le abandonó. A finales de 1830, 19 oficiales de la Artillería de la “Garde Nationale” fueron arrestados y acusados de conspirar contra el gobierno. Fueron absueltos y el 9 de mayo de 1831, 200 republicanos se reunieron en una cena para celebrar la absolución. Durante la cena Galois alzó la copa y con una daga descubierta en su mano amenazo abiertamente al rey Louis-Phillipe. A causa de esta acción desafiante fue detenido al día siguiente y encarcelado durante más de un mes en la prisión de Sainte-Pelagie. En el juicio, la defensa de Galois sostuvo que el brindis había sido: “¡Por Luís Felipe, si traiciona!” pero la frase “si traiciona” había quedado ahogada por el clamor de los comensales. No se sabe si los jurados creyeron este alegato o si se conmovieron por la juventud de Galois, que contaba entonces con 19 años; lo cierto es que le absolvieron en pocos minutos. Dos trabajos de menor importancia, un abstract en los Annales de Gergonne y una carta sobre la enseñanza de la ciencia en la Gazette des Ecoles el 2 de enero de 1831 fueron las ultimas publicaciones de su vida. Galois trató de volver a las matemáticas en enero de 1831. Organizó algunas clases de álgebra superior que atrajeron a 40 estudiantes a la primera sesión sin embargo, el interés decayó rápidamente. Durante aquel año de 1831 Galois por fin había redondeado las cuestiones pendientes en su trabajo y lo había sometido a la consideración de Poisson quien le recomendó presentar a la Academia una tercera versión de su memoria sobre ecuaciones y así lo hizo el 17 de enero. Era el 14 de julio, día de La Bastilla, y Galois fue arrestado nuevamente. Estaba usando el uniforme de la Artillería de la “Garde Nationale”, lo que era ilegal, y llevaba también consigo un rifle cargado, varias pistolas y una daga. Galois fue enviado de vuelta a la prisión de Sainte-Pelagie. Durante su confinamiento se le notificó que su memoria había sido rechazada. El propio Poisson, a pesar de su enorme prestigio matemático y de sus esfuerzos, no llegó a comprender los resultados que le presentaba aquella memoria. Después Poisson animó a Galois a publicar una más completa relación de su trabajo. Durante su confinamiento en la prisión de Sainte-Pelagie, Galois trató de suicidarse apuñalándose con una daga pero los otros prisioneros lo impidieron (en otros textos se hace referencia a que lo trataron de asesinar).
A5
En marzo de 1832 una epidemia de cólera barrió París, y los prisioneros incluyendo a Galois, fueron transferidos al internado “Sieur Faultrier”. Fue allí donde al parecer se enamoró de Stephanie-Felice du Motel, la hija del médico residente. Tras ser liberado el 29 de abril, Galois intercambio correspondencia con Stephanie sin embargo, ella trató de distanciarse de aquella aventura. El nombre de Stephanie aparece varias veces en los manuscritos de Galois en notas al margen.
Los detalles que condujeron a su duelo no están claros aunque se suponen dos causas, la primera a causa de un lío de faldas y la segunda es que los realistas lo consideraban tan peligroso adversario que arreglaron para que fuera desafiado a un duelo de honor. Lo que queda para la historia es la noche anterior al evento. Évariste Galois estaba tan convencido de lo inmediato de su muerte que pasó toda la noche escribiendo cartas a sus amigos republicanos y componiendo lo que se convertirla en su testamento matemático. Galois escribió a sus amigos:
Pido a los patriotas y a mis amigos no me reprochen
que muera por otra causa que no es la de mi patria.
Muero víctima de una infame coqueta. Mi vida se
extingue en una miserable disputa. ¿Por qué morir por
una cosa tan trivial, tan despreciable?
. . . . Conserven mi recuerdo, ya que el destino
no me ha dado suficiente vida para que mi país
conozca mi nombre.
A6
En estos papeles describió someramente las implicaciones del trabajo que había desarrollado en detalle y anotó una copia del manuscrito que había remitido a la academia junto con otros artículos.
El 30 de mayo de 1832 a primera hora de la mañana, Galois se batió a duelo con Perscheux d’Herbinville, su adversario lo hirió en el abdomen y su padrino abandonó el campo en busca de un médico. Ni el padrino ni el médico regresaron. Un campesino, que pasaba casualmente por el lugar, lo llevó a un hospital. El hermano menor de Galois rompió en llanto al visitarlo en el hospital. Galois trató de consolarlo y de confortarse a si mismo, diciéndole: “No llores; necesito todo mi valor para morir a los veinte años”. Falleció en la mañana del 31 de mayo de 1832. El hermano de Galois y su amigo Chevalier copiaron sus trabajos matemáticos y se los enviaron a Gauss, Jacobi y otros. Había sido el deseo de Galois que Jacobi y Gauss dieran una opinión sobre su obra. No hay evidencia de ningún comentario que éstos hayan hecho. Las contribuciones matemáticas de Galois fueron publicadas finalmente en 1843 cuando Joseph Liouville revisó sus manuscritos y declaró que aquel joven en verdad había resuelto el problema de Abel por otros medios que suponían una verdadera revolución en la teoría de las matemáticas empleadas. El manuscrito fue publicado en el número de octubre de 1846 del “Journal des mathematiques pures et appliquees”. Las obras reunidas de Galois abarcan un total de sesenta páginas. Tales breves páginas de matemáticas, escritas entre los dieciséis y los veinte años, han dado nueva forma desde entonces a la matemática.
A7
Tabla de la SNR vs. Probabilidad de error para una señal antipodal
SNR_dBa Pe SNR_dBa Pe
0 0.0786496 5 0.00595387
0.1 0.07627397 5.1 0.00547975
0.2 0.07392678 5.2 0.00503457
0.3 0.07160898 5.3 0.0046173
0.4 0.06932149 5.4 0.00422687
0.5 0.0670652 5.5 0.00386223
0.6 0.06484099 5.6 0.0035223
0.7 0.06264974 5.7 0.00320601
0.8 0.06049227 5.8 0.00291229
0.9 0.05836941 5.9 0.00264007
1 0.05628195 6 0.00238829
1.1 0.05423065 6.1 0.0021559
1.2 0.05221625 6.2 0.00194187
1.3 0.05023945 6.3 0.00174517
1.4 0.04830091 6.4 0.00156481
1.5 0.04640128 6.5 0.0013998
1.6 0.04454114 6.6 0.0012492
1.7 0.04272106 6.7 0.00111207
1.8 0.04094156 6.8 0.00098751
1.9 0.0392031 6.9 0.00087466
2 0.03750613 7 0.00077267
2.1 0.03585102 7.1 0.00068075
2.2 0.03423812 7.2 0.00059812
2.3 0.03266771 7.3 0.00052404
2.4 0.03114003 7.4 0.00045782
2.5 0.02965529 7.5 0.0003988
2.6 0.0282136 7.6 0.00034634
2.7 0.02681507 7.7 0.00029986
2.8 0.02545972 7.8 0.0002588
2.9 0.02414752 7.9 0.00022264
3 0.02287841 8 0.00019091
3.1 0.02165224 8.1 0.00016315
3.2 0.02046885 8.2 0.00013894
3.3 0.01932797 8.3 0.00011791
3.4 0.01822932 8.4 0.00009971
3.5 0.01717254 8.5 0.000084
3.6 0.01615724 8.6 0.0000705
3.7 0.01518295 8.7 0.00005894
3.8 0.01424916 8.8 0.00004909
3.9 0.01335532 8.9 0.00004071
4 0.01250082 9 0.00003363
4.1 0.011685 9.1 0.00002766
4.2 0.01090715 9.2 0.00002265
4.3 0.01016654 9.3 0.00001847
4.4 0.00946237 9.4 0.00001499
4.5 0.00879381 9.5 0.00001211
4.6 0.00816001 9.6 0.00000974
4.7 0.00756005 9.7 0.00000779
4.8 0.00699302 9.8 0.0000062
4.9 0.00645796 9.9 0.00000491
10 0.00000387
A8
Listado del programa en VHDL para el codificador (15,7) -- Codificador BCH (15,7), t=2 -------------------------------------------------------------------------- -- disposición del LFSR para el codificador library ieee; use ieee.std_logic_1164.all; ENTITY ering IS PORT (clk, rll, din: IN BIT; dout: OUT BIT); --salida de datos serial END ering; ARCHITECTURE eringa OF ering IS SIGNAL rin, rout: BIT_VECTOR(0 TO 7); SIGNAL rin0: BIT; BEGIN dout<= rout(7); rin0 <= (din XOR rout(7)) AND rll; rin(0)<= rin0; rin(1)<= rout(0); rin(2)<= rout(1); rin(3)<= rout(2); rin(4)<= rout(3) XOR rin0; rin(5)<= rout(4); rin(6)<= rout(5) XOR rin0; rin(7)<= rout(6) XOR rin0; -- Polinomio generador --100010111 PROCESS BEGIN WAIT UNTIL clk'EVENT AND clk='1'; rout<= rin; END PROCESS; END eringa; -------------------------------------------------------------------------- -- Contador LFSR para - control de señales library ieee; use ieee.std_logic_1164.all; ENTITY ecount IS PORT (clk, reset: IN BIT; vdin: OUT BIT); END ecount; ARCHITECTURE ecounta OF ecount IS SIGNAL cout: BIT_VECTOR(0 TO 3); SIGNAL vdinR, vdinS, vdin1: BIT; BEGIN vdinR<= NOT cout(0) AND NOT cout(1) AND cout(2) AND cout(3); -- reset vdin if cout==k-1 vdinS<= ( cout(0) AND NOT cout(1) AND NOT cout(2) AND cout(3)) OR reset; -- vdinS=1 if cout==n-1 vdin<= vdin1 AND NOT reset; PROCESS BEGIN
A9
WAIT UNTIL clk'EVENT AND clk='1'; IF vdinR='1' THEN vdin1<= '0'; ELSIF vdinS='1' THEN vdin1<= '1'; END IF; END PROCESS; PROCESS BEGIN -- proceso para incremento o restablecimiento del circuito contador WAIT UNTIL clk'EVENT AND clk='1'; cout(0)<= cout(3) OR reset; cout(1)<= (cout(0) XOR cout(3)) AND NOT reset; cout(2)<= cout(1) AND NOT reset; cout(3)<= cout(2) AND NOT reset; END PROCESS; END ecounta; ----------------------------------------------------------------- -- arquitectura que coordina las entidades ering y ecount library ieee; use ieee.std_logic_1164.all; ENTITY enc IS PORT (clk, reset, din: IN BIT; vdin, dout: OUT BIT); END enc; -- vdin – validación de los datos de entrada ARCHITECTURE enca OF enc IS SIGNAL vdin1, rin, rout, rll: BIT; -- rll-ring loop lock, pe COMPONENT ecount PORT(clk, reset: IN BIT; vdin: OUT BIT); END COMPONENT; FOR ALL: ecount USE ENTITY WORK.ecount (ecounta); COMPONENT ering PORT(clk, rll, din: IN BIT; dout: OUT BIT); END COMPONENT; FOR ALL: ering USE ENTITY WORK.ering (eringa); BEGIN c1: ecount PORT MAP (clk, reset, vdin1); r1: ering PORT MAP (clk, rll, rin, rout); rin<= din AND NOT reset; rll<= vdin1 AND NOT reset; vdin<= vdin1; PROCESS BEGIN WAIT UNTIL clk'EVENT AND clk='1'; dout<= (NOT vdin1 AND rout) OR (vdin1 AND rin); END PROCESS; END enca;
