“Año del Bicentenario del Perú: 200 años de Independencia”
UNIVERSIDAD NACIONAL DE SAN AGUSTÍN
FACULTAD DE INGENIERÍA
DE PRODUCCIÓN Y
SERVICIOS
ESCUELA PROFESIONAL DE
ING. ELECTRÓNICA
TEMA: Control de errores
CURSO:
REDES INDUSTRIALES, SCADAs
Y DCS
DOCENTE:
Ing. Manuel Augusto Jordan Palma
ALUMNOS:
Cano Linare Jose Raul
Gonzales Cordova Jymmy Alexander
Lima Chalco Karol Madeleine
Mamani Huisa Carlos Esteban
SEMESTRE: IX
Arequipa-2021
ÍNDICE
Introducción 3
Marco teórico 3
Fiabilidad-Control de errores 4
Retransmisión. 6
ARQ(Automatic Repeat-reQuest) 6
Parada y espera (Stop&Wait ARQ): 6
Retroceso N (Go-Back-N ARQ): 7
Repetición selectiva (selective-repeat ARQ): 7
Corrección de errores hacia delante. 8
Códigos de bloque: 8
Códigos convolucionales: 9
Esquemas hıbridos (FEC/ARQ) 9
Errores de carácter. 10
Errores de rafaga 10
Errores de sincronización 11
Framing 11
Overrun 12
Errores a nivel de mensaje 12
Bits de Paridad 12
Verificación de redundancia vertical (VRC) 14
Verificación de Redundancia Cíclica (CRC) 15
Roles del Algoritmo 16
2
Introducción
En los sistemas de comunicación se considera que un bit es erróneo cuando llega a su destino
con un valor distinto del que tenía al ser transmitido. Esto se expresa con el parámetro BER
(Bit Error Rate) como el ratio entre los bits erróneos y los bits transmitidos en un espacio de
tiempo representativo y se considera el parámetro más importante para caracterizar las
imperfecciones en los sistemas de comunicación digitales.[1]
Por ello, las técnicas más frecuentes es añadir a la información binaria ciertos bits o bytes para
detectar y si es posible corregir los errores que surgen en las comunicaciones digitales.En
general, cualquier fallo detectado por el receptor dará origen a un mensaje de error , y se
requerirá la repetición del mensaje.Podemos distinguir tres grandes tipos de errores [2]:
Marco teórico
En los últimos 10 años, la industria de las comunicaciones ópticas ha migrado hacia esquemas
de receptores coherentes utilizando conversores de señal analógica a digital (ADC, del inglés
Analog-to-Digital Converter) de alta velocidad. Esto ha permitido la incorporación de códigos
correctores de errores con decodificación por decisiones blandas con el objetivo de extender el
alcance y la eficiencia espectral de los enlaces disponibles. Los códigos correctores de errores
3
con decodificación por decisiones blandas tales como los turbo códigos y los de chequeo de
paridad de baja densidad (LDPC, del inglés Low Density Parity Check), y en especial estos
últimos, se han expandido por las más diversas áreas y constituyen en la actualidad el estándar
en varias normas, tales como 10GBase-T, DVB-S2, y Mobile WiMax (802.16e). Sin embargo,
en comunicaciones ópticas generalmente se los trata como algo ajeno al sistema y por lo tanto
en la mayoría de la bibliografía relacionada no se han tenido en cuenta todos los efectos
residuales del canal a la entrada del decodificador para evaluar su desempeño.
Fiabilidad-Control de errores
Un sistema telemático está conformado por :
Emisor Codificador Canal AWGN
BER Receptor Decodificador
Fig 1.Sistema Telemático.
El emisor se encarga de enviar las fuentes de datos
los receptores reconstruyen el mensaje emitido por la fuente eliminando o mitigando las
imperfecciones del canal (ruido y distorsiones) que se suman a la señal recibida.
Estas imperfecciones ocurridas en el canal producen errores en la señal reconstruida que tienen
que ser detectados y ser corregidos.El conjunto de técnicas que permiten la deteccion y
correccion de errores son denominados códigos detectores y códigos correctores de errores.
En los sistemas clásicos las tecnicas de deteccion clasicas de errores se basan en adjuntar al
mensaje original una información adicional o redundante, que permita al receptor detectar la
existencia de errores.
4
Datos R
Fuente de datos
m bits R n bits
f(datos)
Fig 2.Esquema de un codificador de canal de tipo bloque (n,m)
La información de redundante R, se obtiene procesando la fuente de datos por un algoritmo
f(datos).Esta función f(datos) se puede aplicar en forma periódica es decir la información se
divide en bloques de igual tamaño, calculando la R para cada uno de estos bloques, a este tipo
de códigos se le denomina códigos bloque.
Mientras que el decodificador del canal sería de la forma :
Datos R
Se compara R y
n bits R’ si ambos son
iguales es
R’
correcto
f(datos)
Redundancia
Fig 3.Esquema de un decodificador de canal de tipo bloque
Como podemos observar se tiene que la información está constantemente con la información
redundante R. En este caso se conoce como codificación convolucional.
Para reconstruir el mensaje original los decodificadores pueden emplear dos mecanismos: el
FEC (Forward Error Control) y el ARQ (Automatic Repeat reQuest). En las técnicas FEC la
información redundante es suficiente para detectar y corregir los errores y reconstruir el
mensaje original.Las técnicas ARQ detectan la existencia de errores en la información
reconstruida, de modo que en el caso de detectar un bloque erróneo solicitan al emisor su
reenvío.
Los mecanismos ARQ emplean códigos bloque y necesitan un canal de retorno que
interconecte el receptor con el emisor que sirve para comunicar el reenvío del bloque erróneo.
Los mecanismos ARQ se utilizan en los sistemas de transmisión de datos convencionales que
disponen de canales de retorno como son, las redes de área local, Internet, etc.
5
Los mecanismos FEC requieren procesos de cálculo complejos y no necesitan canales de
retorno. Se aplican en los nuevos sistemas de transmisión de datos como son la emisión de
canales de TV digital terrestre (Digital Video Broadcasting) basados en el estándar MPEG
(Grupo de Expertos en Películas) . La aplicación de estas técnicas se ha iniciado en la década
de los 90 gracias a la disponibilidad de dispositivos microelectrónicos y procesadores de
comunicaciones que permiten el procesado de la información en tiempo real.
Retransmisión.
Este sistema es útil cuando no se está operando en tiempo real, puede ser útil pedir el reenvío
íntegro de las partes con errores o dañadas.Es el método más seguro de corrección de errores
pero raramente el más eficiente.
Por ejemplo el sistema ARQ(Automatic Repeat-reQuest) donde el receptor al detectar un error
solicita la repetición automática de todo el mensaje.
ARQ(Automatic Repeat-reQuest)
En el caso de aplicaciones de tiempo no real la transmisión de información incorrecta o pérdida
se puede confiar a técnicas ARQ que se han demostrado como poco apropiadas para servicios
de tiempo real o con requerimientos de baja latencia por el elevado retardo que introducen las
retransmisiones. ARQ ofrece dos variantes y ambas requieren que emisor y receptor
intercambian algún tipo de información de estado por lo que incurren en retardos para el nodo
receptor, implosión ( efecto negativo que experimentan las fuentes emisoras de tráfico cuando
deben ´ atender las solicitudes de retransmisión de paquetes perdidos o erróneos.) en el nodo
emisor y excesivo overhead en la red.
● En la primera variante de ARQ el receptor devuelve mensajes de confirmación´ positiva
(ACK) incluso cuando ha recibido correctamente los datos.
● En la segunda variante de ARQ el receptor devuelve mensajes de acuse de recibo
negativos (NAK) solo cuando se han producido errores o pérdidas de datos.
Existen tres sistemas comunes de ARQ:
1. Parada y espera (Stop&Wait ARQ):
El sistema stop-and-wait ARQ, el transmisor envía una palabra de código al receptor y
espera una respuesta positiva (ACK) o negativa (NAK) de este último. Un ACK
recibido por el transmisor significa que no se detectaron errores en la transmisión y por
lo tanto se envía la siguiente palabra de código. Por el contrario, un NAK recibido por
el transmisor implica que hubo errores en la transmisión y por lo tanto debe enviarse
la palabra de código que fue transmitida. Este sistema es simple y se utiliza en muchos
sistemas de comunicación de datos, sin embargo, este esquema es inherentemente
6
ineficiente a causa del tiempo de inactividad de espera de un acuse de recibo de cada
palabra de código transmitida. A menos que la longitud del código no sea
extremadamente larga, la fracción de tiempo de inactividad puede ser grande, sin
embargo, utilizando una longitud de bloque muy largo no proporciona una solución, ya
que la probabilidad de que un bloque contiene errores aumenta rápidamente con la
longitud del bloque.
Figura 4.Protocol Stop&Wait ARQ.
2. Retroceso N (Go-Back-N ARQ):
En un sistema go-back-N ARQ, las palabras de código se transmiten continuamente. El
transmisor no espera un acuse después de enviar una palabra de código; tan pronto
como se haya completado el envío de una, comienza el envío de la palabra de código
siguiente. El acuse de recibo de una palabra de código llega después de una demora de
ida y vuelta, que se define como el intervalo de tiempo entre la transmisión de palabra
de código y la recepción de un acuse de recibo de la palabra de código. Durante este
intervalo, N-1 palabras de código también han sido transmitidos. Cuando se recibe un
NAK, el emisor retransmite las palabras de código desde la que fue detectada errónea,
es decir, vuelve a enviar la palabra de código y N-1 siguientes palabras en clave que se
transmitieron durante el tiempo de ida y vuelta (es decir, el emisor retrocede y vuelve
a enviar N palabras de código).
3. Repetición selectiva (selective-repeat ARQ):
En un sistema selectivo de repetición ARQ, las palabras en clave también se transmiten
de forma continua, sin embargo, el transmisor reenvıa (o repite) solo las palabras de
código que tienen un acuse negativo (correspondiente NAK). Debido a que las palabras
de código normalmente debe ser entregado al usuario en el orden correcto, un buffer
debe ser proporcionado al receptor para almacenar los vectores sin errores recibidos
después de un vector detectado con errores. Cuando la primera palabra con acuse
negativo reconocido se recibe correctamente, el receptor libera los vectores libres de
errores recibidos en orden consecutivo hasta que se encuentre el siguiente vector
7
erróneamente recibido. El buffer de recepción debe proporcionar suficiente espacio: de
lo contrario, el buffer puede desbordarse, y se pueden perder datos. El selective-repeat
ARQ es la más eficiente entre los tres esquemas básicos de ARQ, sin embargo, esta es
la más compleja de implementar.
Corrección de errores hacia delante.
Conocido también como Forward Error Correction (FEC), es el único esquema de corrección
de errores que detecta y corrige los errores de transmisión en la recepción, sin pedir la
retransmisión del mensaje enviado. Este tipo de sistema codifica la información agregando
redundancia y ası conseguir, bajo algún algoritmo, la información original a pesar que existan
pérdidas de determinado número de paquetes.
Los sistemas basados en ARQ son de utilidad en situaciones donde el número de usuarios
compartiendo información es pequeño, en aplicaciones no interactivas, cuando predominan las
pérdidas en enlaces compartidos de los árboles multicast, o cuando la probabilidad de pérdidas
no es homogénea. Los sistemas FEC, en cambio, son interesantes cuando existen grupos
grandes, predominan las pérdidas individuales, la probabilidad de pérdidas es homogénea o los
buffers de recepción son limitados.
Existen dos categorías principales de códigos FEC : los códigos de bloque y los códigos
convolucionales.
1. Códigos de bloque:
trabajan en bloques de tamaño fijo (paquetes) de bits o sımbolos de un tamaño predeterminado.
Los códigos de bloques pueden ser decodificados en tiempo polinomial dependiendo de su
longitud de bloque.
Los códigos de bloque pueden ser lineales o no lineales. Un código lineal es un código de
corrección tal que cualquier combinación lineal de palabras de código es también una palabra
de código, y puede representarse como un producto de matrices. Los códigos lineales se
denominan también códigos de comprobación de paridad, pues la palabra de código se obtiene
a partir de sumas módulo dos (o el espacio donde se esté trabajando) de las palabras de código.
Un código de este tipo queda completamente caracterizado por una matriz generadora G (ver
capítulo 4). Ejemplos de códigos de bloque son códigos Reed-Solomon, códigos Hamming,
códigos de Hadamard, códigos de expansión, códigos de Golay y códigos Reed- Muller,
códigos LDPC. Estos ejemplos también pertenecen a la clase de códigos lineales, y por lo tanto
son llamados códigos de bloque lineales.
8
2. Códigos convolucionales:
trabajan en flujos de bits o con símbolos de longitud arbitraria. Con mayor frecuencia se
decodifica con el algoritmo de Viterbi, aunque a veces otros algoritmos son utilizados. Los
códigos convolucionales se utilizan ampliamente en numerosas aplicaciones con el fin de
lograr la transferencia fiable de datos, incluyendo vídeo digital, la radio, la comunicación
móvil, y la comunicación por satélite. Estos códigos se aplican a menudo en una vinculación
con un código hard-decisión, sobre todo Reed Solomon. Antes de los turbo códigos, tales
construcciones fueron las más eficientes, más próximas a los límites de Shannon.
Esquemas hıbridos (FEC/ARQ)
La mayor ventaja que tiene ARQ sobre FEC es que la detección de errores requiere un equipo
de decodificación mucho menos complejo que el que se requiere para la corrección de errores.
Otra desventaja que presenta FEC con respecto a ARQ es que con FEC puede darse el caso de
que en la secuencia decodificada binaria aún contenga algunos errores que serían ya
incorregibles. Sin embargo, en canales donde la probabilidad de error es alta, emplear un
sistema ARQ implicaría la necesidad de retransmitir muchas veces una palabra de código, lo
que limitaría de manera considerable la rapidez del sistema.
Comparando los sistemas para el control de errores FEC y ARQ, observamos que ARQ es
simple y provee sistemas de alta fiabilidad; Además, los sistemas ARQ tienen un severo
retroceso . Los rendimientos disminuyen rápidamente con la creciente tasa de error del canal.
Los sistemas que utilizan FEC mantienen el rendimiento constante (igual a la tasa de código ´
R = k/n) independientemente de la tasa de error de canal, sin embargo, los sistemas de FEC
tienen dos inconvenientes; en primer lugar, cuando un vector recibido se detecta un error, este
debe ser decodificado y el mensaje decodificado debe ser entregado al usuario,
independientemente de si es correcto o incorrecto. Porque la probabilidad de un error de
decodificación es mucho más grande que la probabilidad de un error no detectado, esto es
difícil para lograr un sistema FEC con alta fiabilidad. En segundo lugar, para obtener un sistema
de alta fiabilidad y capaz de corregir una gran colección de patrones de error, se debe usar un
código potente. Esto hace que la decodificación sea difícil de implementar y costoso. Por estas
razones ARQ frecuentemente es preferible por encima de FEC para el control de error en los
datos de sistemas de comunicación, como en redes de packet-switching de datos y en redes
informáticas de comunicación, sin embargo, en los sistemas de comunicación (o de
almacenamiento de datos) donde los canales de retorno no están disponibles o la retransmisión
no es posible por alguna razón, FEC es la única opción.
9
Los inconvenientes en ambos sistemas de ARQ y FEC pueden ser superados si dos esquemas
de control de error se combinan adecuadamente, este tipo de combinación se conoce como
hıbrido ARQ (hybrid-ARQ) y a pesar de que no se ha implementado en muchos sistemas,
podrıa considerarse como la estrategia de control de errores más eficiente.
Un sistema hıbrido ARQ consta de un subsistema de FEC contenida en un sistema ARQ. La
función del subsistema FEC es reducir la frecuencia de la retransmisión por la corrección de
los patrones de error que se producen con mayor frecuencia. Esto aumenta el rendimiento del
sistema. Cuando un patrón de error de menor frecuencia se produce y se detecta, el receptor
realiza una solicitud de retransmisión en lugar de pasar el mensaje decodificado al usuario.
Esto aumenta la fiabilidad del sistema como de un sistema FEC solo y un alto rendimiento
como en un sistema con solo ARQ. Además, dado que el decodificador está diseñado para
corregir una pequeña colección de patrones de error, que puede ser simple. El esquema FEC se
puede incorporar en cualquiera de los tres esquemas ARQ básicos.
Tipos de Errores
Errores de carácter.
Los errores de carácter consiste en el cambio de algún bit dentro del carácter. Para detectar esta
eventualidad se suele añadir un bit adicional de paridad, que permite conocer si el número de
unos en el carácter es par o impar. La paridad se fija por convenio al configurar la comunicación
entre dos terminales, por ejemplo se puede escoger una paridad PAR también llamada EVEN
,IMPAR llamada ODD o anular la comprobación NONE.
Errores de rafaga
Significa que dos o más bits de la unidad de datos han sido alterados.Es importante notar que
los errores de rafaga no implican que se afecten bits consecutivos. La longitud de la rafaga se
mide desde el primer hasta el último bit incorrecto, tomando en cuenta que algunos bits
intermedios pueden no estar afectados, como se observa en la figura
10
Errores de sincronización
Los errores básicos de sincronización son dos:
Framing
En comunicaciones asíncronas en código ASCII, indica sim-plemente que el receptor no ha
reci-bido el bit o los bits de stop al final del carácter más bit de paridad. En otros códigos que
no admiten más que un determinado número de ceros o unos seguidos pueden implementarse
otro tipo de comprobaciones.
11
Overrun
Indica que se ha enviado un carácter antes de que el receptor haya tenido suficiente tiempo
para leer el an-terior.
Errores a nivel de mensaje
Puede suceder que exista una correcta sincronización y que todos los bits de paridad hayan
dado correctos, pero aun así no puede descartarse la posibilidad de que haya existido un cambio
de dos unos en un carácter, por ejemplo. Para asegurar que el mensaje está libre de errores
puede emplearse varios métodos, de distinta complejidad, dependiendo del grado de fiabilidad
que se desee obtener. A continuación, se citan alguno de los más simples:
Detección de errores
Bits de Paridad
Los errores de carácter consiste en el cambio de algún bit dentro del carácter. Para detectar esta
eventualidad se suele añadir un bit adicional de paridad, que permite conocer si el número de
unos en el carácter es par o impar. La paridad se fija por convenio al configurar la comunicación
entre dos terminales, por ejemplo se puede escoger una paridad PAR también llamada EVEN
,IMPAR llamada ODD o anular la comprobación NONE.
Al escoger un paridad , el transmisor añade automáticamente un 1 o 0 al final del caracter
(CARÁCTER+BIT DE PARIDAD) de forma que el números de 1 resulte siempre impar o par.
Este concepto se aplica al código ASCII de 7 bits como al de 8 bits.
12
Datos R
Se compara R y
n bits R’ si ambos son
iguales es
R’
correcto
f(datos)
Redundancia
Por ejemplo si queremos transmitir 11001010, con paridad par se añadirá un 0 , ya que el
número de unos ya es par, por otro lado, si queremos transmitir 10101011 debemos añadir un
1 para que el número de unos sea par.
Fig. Paridad Par[3]
En caso de que queramos una paridad impar, si queremos transmitir un 11001010 , añadiremos
un 1 para que el número de unos sea impar, y en caso si queremos transmitir 10101011
añadiremos un 0 , ya que el número de unos ya es impar.
Fig.Paridad Impar[3]
13
Fig.Paridad Vertical y Horizontal
Verificación de redundancia vertical (VRC)
El código VRC (Vertical Redundancy Check) añade un bit de paridad a cada unidad de datos
de manera que la cantidad de bits en 1 sea par o impar (en función a la paridad adoptada).
También se le conoce como código TRC (Transverse Redundancy Check).
La idea es que se use un bit de paridad para cada unidad de datos, en vez de usar un único bit
para la totalidad del mensaje.
14
Al igual que la paridad, detecta la totalidad de los errores simples a nivel de unidad de datos.
Verificación de Redundancia Cíclica (CRC)
La verificación de redundancia cíclica (abreviado, CRC ) es un método de control de integridad
de datos de fácil implementación. Es el principal método de detección de errores utilizado en
las telecomunicaciones.
La verificación de redundancia cíclica consiste en la protección de los datos en bloques,
denominados tramas. El código CRC contiene datos redundantes con la trama, de manera que
los errores no sólo se pueden detectar sino que además se pueden solucionar.
● El código CRC (Cyclic Redundancy Check) se basa en ciertas propiedades matemáticas
que satisface el cociente entre polinomios.
- Mecanismo: Agregar al patrón de bits que compone el mensaje a ser enviado un
conjunto de bits adicionales, de manera que el patrón resultante (al ser
considerado como un polinomio binario), resulte divisible de manera exacta por
un cierto polinomio denominado polinomio generador.
● Para poder llevar adelante el cociente entre polinomios, se debe interpretar el mensaje
original como si se tratara de un polinomio.
- La clave está en pensar los n bits que componen al patrón original de bits como
los coeficientes binarios de las primeras n - 1 potencias de x.
- Nótese que el polinomio resultante es de grado) a lo sumo n - 1.
- Por caso, el patrón 010011 denota el polinomio x4 + x + 1, mientras que el patrón
110110 al polinomio x5 +x4 + x2 +x .
15
Sea M(x) el polinomio binario representado el mensaje original, sea G(x) el polinomio
generador que se esté usando y sea r su grado. J'En este contexto, el mensaje a ser transmitido
T(x) es xrM(x) + R(x), donde R(x) es el resto de dividir xrM(x) por G(x).
T(x) resulta divisible de manera exacta por G(x) puesto que al tratarse de polinomios binarios,
se puede demostrar que xrM(x) + R(x) equivale a xrM(x) - R(x).
● Pasos para calcular los bits que deben ser agregados a un cierto mensaje M(x):
- Primero se añaden r bits en 0 a la derecha de M(x) (esto es, se añaden tantos ceros como
grado tenga el polinomio generador).
- Luego se divide el polinomio obtenido por el polinomio generador. Esta división se
realiza en el módulo dos, que es igual que la división binaria, con dos excepciones: no
hay carries ni borrows.
- Finalmente, para obtener T(x) se suma el resto R(x) al polinomio original M(x)
(desplazado en r bits).
● Supongamos que el mensaje que se desea transmitir es M(x) = 11010110111 y que el
polinomio generador que se está usando es G(x) = 10011.
● Verifiquemos que el mensaje a ser transmitido T(x) = xrM(x) + R(x) es divisible de
manera exacta por G(x):
Roles del Algoritmo
● El algoritmo CRC cumple dos roles:
16
- Por un lado permite determinar los bits que se deben agregar al mensaje original.
- A su vez, también permiten verificar si el mensaje recibido contiene o no errores.
● Nótese que el receptor puede ir dividiendo el mensaje a medida que va recibiendo los
bits.
- Es decir, no hace falta recibirlo en su totalidad para recién ahí comenzar a verificar el
CRC.
- Este código es muy simple de implementar en HW.
Corrección de Errores
Códigos BCH
los códigos BCH son una subclase de códigos cíclicos que permiten corregir un número
arbitrario de errores t. los códigos fueron propuestos por Bose, Chaudhuri y Hocquenghem, a
los que deben su nombre. Estos códigos tienen una gran versatilidad para el diseño, ya que
existe un gran número de polinomios generadores previamente tabulados. De esta forma, el
usuario sólo debe determinar unos parámetros de diseño, que depende del número de errores
que desee corregir y la longitud de los bloques y, posteriormente, con estos parámetros, buscar
el polinomio generador en una tabla.
17
los parámetros de diseño se determinan a partir de las ecuaciones:
𝑛 = 2𝑚 − 1
𝑛 − 𝑘 = 𝑚𝑡
𝑑𝑚𝑖𝑛 = 2𝑡 + 1
De acuerdo con estos parámetros, si queremos utilizar un tamaño de bloque de 31 bits (n=31)
y corregir un total de tres errores (t=3), encontraríamos un único polinomio en las tablas cuyo
valor de k es 16. Así, el código BCH con un tamaño de bloque 31 que permite corregir 3 errores
contienen un total de 16 bits de información y 15 de redundancia. La tasa del código es R = 16/
31. El polinomio que obtenemos en las tablas está expresado generalmente en octal. En un caso
concreto es 𝐺 = 107657𝑜𝑐𝑡 .
Podemos pasar ese polinomio a forma binario directamente: G= 1000111110101111, o
expresarlo directamente como un polinomio convencional:
𝐺(𝑝) = 𝑝15 + 𝑝11 + 𝑝10 +𝑝9 + 𝑝8 + 𝑝7 + 𝑝5 + 𝑝3 + 𝑝2 + 𝑝 + 1
Reed Solomon
El código fue inventado por Irving S. Reed y Gustave Solomon (de ahí su nombre) en el año
1960. Este código encuentra actualmente aplicación en áreas como los CDs, telefonía móvil y
sondas espaciales (la sonda Galileo a Júpiter en 1989, la sonda Magallanes a Venus ese mismo
año o la sonda Ulises al Sol en 1990). También es de destacar el empleo del código Reed-
Solomon en las comunicaciones por satélite Digital Video Broadcasting (DVB), así como en
los sistemas xDSL de comunicación por cable.
18
Irving S. Reed y Gustave Solomon
El código Reed-Solomon es un subconjunto de los códigos BCH (Bose Chaudhuri
Hocquenqhem), códigos cíclicos que presentan entre sus parámetros (n,k,t) una relación entre
los símbolos de datos (k), del código total (n) y del número máximo de errores por ser
corregidos (t), y son de bloques lineales. Un código Reed-Solomon se especifica como RS(n,k)
con símbolos de s bits. Lo anterior significa que el codificador toma k símbolos de los s bits y
añade símbolos de paridad para hacer una palabra de código de n símbolos. Existen n-k
símbolos de paridad de s bits cada uno. Un decodificador puede corregir hasta t símbolos que
contienen errores en una palabra de código, donde 2t = (n-k).
Ejemplo:
Un código popular Reed-Solomon es RS(255,223) con símbolos de 8 bits. Cada palabra de
código contiene 255 bytes de palabra de código, de los cuales 223 bytes son datos y 32 bytes
son paridad. Para este código se tiene:
● N=255, k=223, s=8
● 2t=32, t=16
El decodificador puede corregir cualquier error de 16 símbolos en la palabra de código, es
decir, errores de hasta 16 bytes en cualquier lugar de la palabra pueden ser automáticamente
corregidos.
Dado un tamaño de símbolo s, la máxima longitud de la palabra de código (n) para un código
Reed-Solomon es n=2𝑠 − 1
Por ejemplo, la máxima longitud de un código con símbolos de 8 bits (s=8) es de 255 bytes.
Los códigos Reed-Solomon pueden ser acortados haciendo un número de símbolos de datos
igual a cero en el codificador, no transmitiendo estos, y reinsertando éstos en el decodificador.
19
Ejemplo aplicativo de Reed Solomon:
CODIFICADOR Y DECODIFICADOR DIGITAL REED-SOLOMON
PROGRAMADOS PARA HARDWARE RECONFIGURABLE
Por Cecilia E. Sandoval Ruiz y Antonio Fedón
se presenta una recopilación de las bases teóricas empleadas para diseñar bloques funcionales
del codificador/decodificador Reed-Solomon y una metodología de diseño orientada a
tecnología FPGA. Inicialmente se presenta el diseño del algoritmo del codificador, luego se
concibe la arquitectura y se captura el diseño de hardware mediante el empleo de VHDL y la
herramienta de sintaxis Xilinx ISE 6.1. Finalmente se lleva a cabo la validación del
comportamiento del codificador con ModelSim 5.7 mediante simulaciones de los módulos. Las
operaciones en los campos finitos de Galois, GF(2m), son la base de varios algoritmos en el
área de corrección de errores y procesamiento digital de señales. Sin embargo, los cálculos
requeridos demandan gran cantidad de tiempo al ser implementados a través de software; por
razones de desempeño y seguridad es preferible implementar los algoritmos en hardware.
El código Reed-Solomon es un subconjunto de los códigos BCH (Bose Chaudhuri
Hocquenqhem), códigos cíclicos que presentan entre sus parámetros (n,k,t) una relación entre
los símbolos de datos (k), del código total (n) y del número máximo de errores por ser
corregidos (t), y son de bloques lineales. Un código Reed-Solomon se especifica como RS(n,k)
con símbolos de s bits. Lo anterior significa que el codificador toma k símbolos de los s bits y
añade símbolos de paridad para hacer una palabra de código de n símbolos. Existen n-k
símbolos de paridad de s bits cada uno. Un decodificador puede corregir hasta t símbolos que
contienen errores en una palabra de código, donde 2t = (n-k).
Para codificar la trama con esta estructura se debe procesar a través de un circuito digital que
opere bajo los fundamentos de campo finito de Galois. Este presenta una arquitectura en el
codificador compuesta por los bloques funcionales mostrados en la Figura
20
CAMPOS DE GALOIS APLICADOS A LA CODIFICACIÓN REED-SOLOMON
Los códigos Reed-Solomon se basan en un área especializada de la matemática llamada campos
de Galois o campos finitos. Un campo finito tiene la propiedad de que las operaciones
aritméticas sobre elementos del campo siempre tienen un resultado en el campo. Un codificador
o decodificador Reed-Solomon debe ser capaz de realizar estas operaciones aritméticas.
21
HAMMING
En el año de 1950, el profesor Richard W. Hamming (1915-1988) matemático Estadounidense
publicó un artículo sobre detección de errores. Esta publicación supuso el comienzo de una
nueva área de investigación dentro de la teoría de la información ya que actualmente el código
de Hamming tiene un papel importante en la vida cotidiana y son usados en muchos sistemas
electrónicos.
Antes de comenzar a analizar sobre este algoritmo es necesario tener en cuenta los siguientes
conceptos:
● Código Binario: Es una representación unívoca de las cantidades, de tal forma que a
cada una de éstas se le asigna una combinación de símbolos binarios.
● Distancia entre dos combinaciones binarias: Viene dada por el número de bits que hay
que cambiar en una de ellas para obtener la otra.
● Distancia mínima de un código: Es la menor de las distancias entre dos combinaciones
binarias cualesquiera pertenecientes a dicho código.
En un proceso de transmisión de datos digitales existe la posibilidad de pérdida de información
debido a circunstancias como disipación de niveles de energía, efectos magnéticos externos
sobre el canal de datos, deficiencias de acoplamiento entre terminales de los canales de datos,
entre otros. En el caso de que un receptor reciba información incorrecta, debe realizarse un
proceso de retransmisión de la información. Este proceso de retransmisión, generalmente, no
es muy apropiado debido a que genera uso adicional del canal de datos, lo cual conlleva otros
inconvenientes.
22
En la figura 2 podemos visualizar que cuando se transmite una información binaria desde un
emisor hacia un receptor a través de un medio susceptible a perturbaciones o ruidos externos,
aparece el problema de que alguno de los bits de la palabra original pueda modificar su valor
y den lugar a una nueva combinación que evidentemente será errónea
Códigos correctores de errores
La idea básica de los códigos correctores de errores es enviar dos veces la información de cada
bit y comparar en la recepción que los bits recibidos por cada uno de los dos caminos es la
misma. En caso de ser diferente, se puede afirmar que se ha producido un error en esa línea de
datos.
Código Hamming
El código de Hamming sirve es un código de distancia 3. El propósito del algoritmo de
Hamming es realizar una tabla detectora del bit erróneo a partir de los bits detectores de paridad
par generados por el receptor, es decir, poder identificar la línea donde se ha producido el error
y así proceder a su corrección. El número de combinaciones que se pueden formar con los K
bits tiene que ser mayor o igual que el número de líneas del código original (M) más el número
de líneas de paridad añadidas (K) más uno, este último para contemplar el caso de no error.
23
Por medio del código de corrección de errores de Hamming es posible no solo detectar, sino
también enmendar los errores ocurridos sobre la cadena de información en el receptor. La
detección y corrección de errores en un sistema de transmisión de información depende de la
inclusión de redundancia sobre la cadena de transmisión, es decir, a los datos se les añade
información que permite dar una pequeña descripción de los mismos datos. La cantidad de
errores a detectar o corregir en un sistema con código de Hamming depende de la distancia de
Hamming “d”.
Consideraciones
● Este corrector de errores supone que sólo un bit de información puede llegar invertido
durante la transmisión, con lo cual con este código sólo es posible corregir un sólo error.
● Esta técnica requiere incorporar metainformación a los datos para poder identificar los
errores. Sin embargo, el tamaño de la metainformación no es proporcional al tamaño
del mensaje, lo que indica que un mensaje muy grande tiene una metainformación
relativamente pequeña.
Ejemplos
Codificación: Si por ejemplo se quiere transmitir “1010’’, como se puede observar es una
palabra de cuatro bits, entonces M = 4.
24
Como , se puede hacer el cálculo y se concluye que K = 3; por lo tanto, se
necesitarán 3 bits de paridad para la codificación de HAMMING. Al momento de codificar,
los bits de paridad (P) junto con los bits de información (I) se ordenan de manera que los bits
de paridad deben ubicarse de forma tal que su posición sea potencia de 2.
Luego se los vuelve a renombrar con el subíndice en código binario, quedando en la siguiente
manera:
Luego lo primero que se hace para averiguar el valor lógico de cada uno de los bits de
paridad es ordenarlos de la siguiente forma:
Se concluye que: . Entonces codificado en Hamming queda:
Es decir, para obtener los valores lógicos de los bits de paridad lo que se hizo fue razonar de la
siguiente manera, por ejemplo, para la fila uno, se bajaron todos los bits de información (I)
cuyos subíndices tienen un “1” a la derecha, como es en el caso del subíndice primer bit de
paridad, luego, debajo del bit de paridad se pone “1” ” si y solo si la cantidad de “unos” en la
fila de los bits de información que se bajaron fue impar, sino resulta así como en el caso de la
fila 2 se pone “0” (en este caso se bajó : “1 0 0”, entonces debajo de P001 se pone “0”)
25
Decodificación: para decodificar se hace lo mismo que en la codificación, pero en este orden
los bits de paridad se ordenan de menor a mayor. Entonces lo que se recibe es:
Se ordena:
Como se observa en las flechas: los valores lógicos a los que se llegan son “cero”, eso quiere
decir la información llegó “correctamente”. Ahora bien, si por ejemplo en vez de haberse
recibido “1 0 1 1 0 1 0” se hubiera recibido lo siguiente: “1 0 0 1 0 1 0” como “a priori” lo
que se sabe es que la información viene codificada en HAMMING, entonces lo que se hace
es decodificar:
Como se ve, se llega a que los valores lógicos que se obtienen indicados con las flechas es el
“011” (3), (se deben leer siempre de derecha a izquierda), por lo tanto, está indicando que se
produjo un error, y que dicho error se produjo en el bit “3” (011), entonces lo que se hace es
invertir el bit 3 de cero a uno. Por lo tanto, al invertir el bit 3 queda lo siguiente:
Ejemplos de aplicación de los códigos correctores de errores
En el año 1987 Intel introdujo el circuito integrado 8206 cuya misión era detectar y corregir
errores en palabras de 8 o de 16 bits. Inicialmente su campo de aplicación era corregir los
26
posibles errores generados al leer datos desde una memoria. Recientemente, los códigos de
Hamming han visto una aplicación similar al corregir errores en bits almacenados en
memorias RAM dinámicas insertadas dentro de circuitos integrados de aplicación específica
ASICs.
En el año 1996, la firma CML introdujo el circuito integrado FX909A. Se trata de un modem
para comunicaciones inalámbricas vía radio que incorpora la modulación GMSK. En la
figura 7 se muestra cómo genera una trama de 20 bytes para ser transmitida en serie. Es
importante destacar que para aprovechar al máximo las posibilidades de los códigos
correctores de un error, el registro de desplazamiento que incorpora ordena los bits
transversalmente, es decir, si durante la transmisión hay un ruido de unos milisegundos, se
estropearon varios bits, pero todos de palabras distintas y por lo tanto todas estas palabras
podrán ser reconstruidas (figura 8). En cambio, si los bits se hubieran enviado palabra tras
palabra, la modificación de varios bits consecutivos impediría la reconstrucción de la
información de dicha palabra.
27
