Aplicaciones de campos de Galois en corrección de errores

Vista previa del material en texto

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
Ca
mp
os
 de
 G
alo
isComunicaciones
D
 i d á
c t i c a
S i m u l a c i o n e s
Hw y Sw
M
od
elo
 M
ate
má
tic
oRecursos de Program
ación C
om
pe
nd
io
 d
id
ác
tic
o 
de
 
co
di
fic
ac
ió
n 
pa
ra
 el
 co
nt
ro
l 
de
 er
ro
re
s
Mapa conceptual de tesis
Lógica digital
Codificación de canal
Códigos 
BCH
Ca
mp
os
 de
 G
alo
isComunicaciones
D
 i d á
c t i c a
S i m u l a c i o n e s
Hw y Sw
M
od
elo
 M
ate
má
tic
oRecursos de Program
ación C
om
pe
nd
io
 d
id
ác
tic
o 
de
 
co
di
fic
ac
ió
n 
pa
ra
 el
 co
nt
ro
l 
de
 er
ro
re
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, describemediante 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 “Unateorí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 
 






=
)(
1
log)(
i
ri 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 
 
[ ] [ ])(ln
2ln
1
)(log
2log
1
)( 10
10
iii 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: 






== ∑∑
== )(
1
log)()( 2
2
1
2
1 ii
i
i
ii xP
xPIxPH
 






−
−+=
p
p
P
PH
1
1
log)1(
1
log 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úmerode 
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
bitsH
R
τ
=
 
 
donde: τ es la duración promedio del símbolo 
 
 
 
iτ → es la duración del símbolo xi 
 
∑
=
=
q
i
iixP
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
n
R 




=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
E
erfc
N
E
QP bbe 
 
 
 --para señal antipodal-- 
 








=







=
00 2
12
N
E
erfc
N
E
QP bbe 
 
 
 
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 SNRhabrá 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. 
G
R
U
P
O 
G
R
U
P
O 
 
A
B
E
L
I
A
N
O 
A
N
I
L
L
O 
 
C
O
N
M
U
T
A
T
I
V
O 
 
A
N
I
L
L
O 
D
O
M
I
N
I
O 
 
E
N
T
E
R
O 
C
A
M
P
O 
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
a
q 
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( nan
n
a
a +×


= 
 
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éticamodular 
 
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: 
 
� pa, lo que significa que a ≡ 0 mod-p, es decir a = 0 en Zp 
� pb, 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 mencionadobrevemente 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
01
i
 
 
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
0111
i
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
01
i
. 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) = a
q-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 delelemento 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 
 
01
1
1)( fxfxfxfxf
m
m
m
m ++++=
−
− 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
+=+=+=+ −−− xxxx
m
 
 
es divisible entre dicho polinomio x3 + x + 1, como se muestra a continuación: 
 
01
1
1 24
3
7
=+++=
++
+
resxxx
xx
x
 
 
Con base en lo anterior, se define que un polinomio irreducible 
 
01
1
1)( pxpxpxpxp
m
m
m
m ++++=
−
− 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 xpxqx
m
=+− 
 
Pero aplicando en función de la raíz α, se tiene que: 
 
0)()()(112 ⋅==+− αααα qpq
m
 
 
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 
 
01
2
2
1
1)( pxpxpxpxxp
m
m
m
m
m +++++= −−
−
− Kde 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 
 
01
2
2
1
10 pppp
m
m
m
m
m +++++= −−
−
− αααα K 
 
01
2
2
1
1 pppp
m
m
m
m
m ++++= −−
−
− αααα K 
 
donde α m es expresado como un polinomio con coeficientes p0, p1, . . . , pm-1 provenientes de GF(2) y 
 
01
2
2
1
1 pppp
m
m
m
m ++++
−
−
−
− ααα 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 
 
01
2
2
1
1 aaaa
m
m
m
m
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 xx
m
+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: 
xxxxxx
m
+=+=+ 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 xx
m
+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