Universidad Autónoma Gabriel René Moreno

Facultad de Ingeniería en Ciencias de la Computación y Telecomunicaciones

Redes AdHoc

INTEGRANTES
 Cristian Blas Mojica Céspedes…….……………………………...…214135713
 Alex Ocaña Peña………….…………………………………………..214018253
 Danny Cruz Saucedo………………………………………………….210056118
 Carlos Alberto Lizondo Melgar……………………………………….213093472

DOCENTE
 Ing. Junior Villagomez Melgar

TEMA
 Codificación De Canal

FECHA
 20/08/2018

Santa Cruz – Bolivia

1
 Contenido

1.Introducción……………………………………………………………………………3
2. Tipos De Codigos De Control De Error(ARQ,FEC)…………………………….4
2.1.1 El ARQ-stop-and-wait………………………………………………………….5
2.1.2. El ARQ-continuos……………………………………………………………...9
2.1.2.1 Go-back-N-ARQ……………………………………………………………9
2.1.2.2 Selective-repeat-ARQ……………………………………………………..9
2.2 FEC (Forward Error Correction)………………………………………………...11
3. Reglas de decisión…………………………………………………………………12
4. Probabilidades De Error de Bit y Bloque………………………………………...14
5. Teorema Fundamental De Shannon……………………………………………..17
6. Códigos Binarios lineales………………………………………………………….24
6.1 Definición y parámetros………………………………………………………….24
7. Códigos de Hamming……………………………………………………………25
8. códigos cíclicos, CRC……………………………………………………………30
8.1. Técnicas de detección de errores………………………………………………31
8.2. CRC………………………………………………………………………………..33
9. Codigos Convolucionales, Algoritmo De Viterbi………………………………39
10. Bibliografía………………………………………………………………………...43

2
 CODIFICACIÓN DEL CANAL

1. Introducción.
Las redes deben ser capaces de transferir datos de un dispositivo a otro con total
exactitud, si los datos recibidos no son idénticos a los emitidos, el sistema de
comunicación es inútil. Sin embargo, siempre que se transmiten de un origen a un
destino, se pueden corromper por el camino. Los sistemas de comunicación deben
tener mecanismos para detectar y corregir errores que alteren los datos recibidos
debido a múltiples factores de la transmisión.
La finalidad de la codificación de canal es la detección y corrección de errores
producidos en el canal de comunicación o en medios de grabación, como
consecuencia el ruido y distorsión son introducidos, tanto por el medio de
propagación, como propio sistema de transmisión.

En los sistemas digitales de comunicaciones hay dos causas principales que influyen en
el deterioro de la señal recibida. La primera es el ruido introducido por el propio canal
de comunicaciones, en que los mecanismos de propagación juegan un papel muy
importante. La segunda es el ruido de cuantificación, consecuencia del proceso de
codificación, que se introduce inevitablemente en el transmisor y que se transporta
por todo el sistema hasta la salida del receptor. El ruido del canal produce errores de
transmisión, que hacen que la señal reconstruida por el receptor no sea la misma que
la señal transmitida. La fidelidad de la transmisión de información se mide en términos
de la tasa de errores o probabilidad de error es decir, la probabilidad de que el
símbolo a la salida del receptor o reproductor sea diferente al símbolo transmitido o
grabado. Tanto los sistemas de transmisión como de grabación y reproducción están
sujetos a errores.

En la transmisión y grabación de señales digitales de audio, vídeo o datos en general,

igual que en cualquier sistema digital de comunicaciones, el caudal binario recibido o
reproducido debe ser, en la medida posible, igual que el transmitido o grabado, por lo

3
que la información debe protegerse al máximo contra las degradaciones que
inevitablemente introduce el medio de transmisión o los circuitos de procesado de la
señal. Los sistemas de comunicaciones por cable y satélite son menos hostiles que los
de radiodifusión terrestre, ya que los primeros utilizan un medio de transmisión muy
estable: cable o fibra óptica, en que el principal problema es la atenuación, fácilmente
predecible y cuyos efectos pueden compensarse con relativa facilidad. En el caso de
comunicaciones por satélite también el comportamiento del medio de propagación,
aunque sujeto a variaciones por meteoros atmosféricos en ciertas bandas, es bastante
predecible y por consecuencia, sus efectos también pueden compensarse.
Existen muchas técnicas de corrección de errores nos enfocaremos específicamente
las siguientes dos:

 Corrección hacia atrás ARQ

 Corrección hacia delante FEC

2. Tipos De Codigos De Control De Error (ARQ,FEC)

2.1 ARQ (Automatic Repeat Request)

ARQ (del inglés Automatic Repeat-reQuest) son protocolos utilizados para

el control de errores en la transmisión de datos, garantizando la integridad de los
mismos. Estos suelen utilizarse en sistemas que no actúan en tiempo real, ya que el
tiempo que se pierde en el reenvío puede ser considerable y suele ser más útil
emitir mal en el momento, que hacerlo correctamente un tiempo después. Esto se
puede ver muy claro con una aplicación de videoconferencia donde no resulta de
utilidad emitir el pixel correcto de la imagen 2 segundos después de haber visto la
imagen.

4
Esta técnica de control de errores se basa en el reenvío de los paquetes de
información que se detecten como erróneos (Esto quiere decir que no todos los
paquetes de información se detectan como erróneos).
Para controlar la correcta recepción de un paquete se utilizan ACK's (acknowledge)
y NACK's de forma que cuando el receptor recibe un paquete correctamente el
receptor asiente con un ACK y si no es correcto responde con un NACK. Durante el
protocolo que controla recepción de paquetes pueden surgir múltiples problemas
(pérdida de ACK, recibir un ACK incorrecto, etc.) complicándose así el contenido
del ACK y surgiendo nuevos conceptos como el de timeout.
Si el emisor no recibe información sobre la recepción del paquete durante un
tiempo fijado (timeout) éste se reenvía automáticamente.
Esencialmente existen tres tipos de ARQ aunque en la práctica se combinen
buscando el sistema óptimo para cada canal o estado de tráfico concreto.

Detección de errores o corrección hacia atrás o ARQ (Petición automática de

retransmisión): Cuando el receptor detecta un error solicita al emisor la repetición
del bloque de datos transmitido. El emisor retransmitirá los datos tantas veces
como sea necesario hasta que los datos se reciban sin errores.

Existen dos tipos de sistemas de ARQ en general:

 ARD-stop-and-wait
 ARQ-continuous.

2.1.1 El ARQ-stop-and-wait

El método de Parada y espera (Stop-and-wait) es un tipo de protocolo ARQ para

el control de errores en la comunicación entre dos hosts basado en el envío de
tramas o paquetes, de modo que una vez se envía un paquete no se envía el
siguiente paquete hasta que no se recibe el correspondiente ACK (confirmación de
la recepción) y en caso de recibir un NACK (rechazo de la recepción) se reenvía el
paquete anterior.

5
Este protocolo asegura que la información no se pierde y que las tramas o
paquetes se reciben en el orden correcto. Es el más simple de los métodos ARQ. En
este, el emisor, después de enviar una sola trama, no envía las demás hasta que
reciba una señal ACK (un acuse de recibo de que se recibió la trama) por parte del
receptor. Por otro lado, el receptor, cuando recibe una trama válida (sin errores),
envía la señal ACK.
Si el ACK no logra llegar al emisor antes de un cierto tiempo, llamado tiempo de
espera (time out), entonces el emisor, reenvía la trama otra vez. En caso de que el
emisor sí reciba el ACK, entonces envía la siguiente trama.
El comportamiento anterior es la implementación más simple del método Parada-
y-Espera. Sin embargo, en la implementación práctica de la vida real existen
problemas que deben solucionarse.
Normalmente el emisor agrega un bit de redundancia al final de cada trama. El
receptor utiliza dicho bit de redundancia para la búsqueda de posibles errores. Si el
receptor encuentra que la trama es válida (no contiene errores), entonces envía el
ACK. Si el receptor encuentra que la trama está dañada, entonces el receptor la
deshecha y no envía el ACK -- pretendiendo que la trama se perdió por completo,
no que fue solamente dañada.
Un problema surge cuando un ACK enviado por el receptor se daña o se pierde por
completo en la red. En este caso, el emisor de la trama no recibe el ACK, se acaba

6
el tiempo de espera y reenvía la trama de nuevo. Ahora el receptor tiene 2 copias
de la misma trama y no sabe si la segunda es una trama duplicada o si es la
siguiente trama de la secuencia que se enviará, que en realidad contiene datos
idénticos a la primera.
Otro problema surge cuando el medio de transmisión tiene una latencia tan grande
que el tiempo de espera del emisor se termina incluso antes de que la trama llegue
al receptor. En este caso, el emisor reenvía la trama. Eventualmente el receptor
obtiene 2 copias de la misma trama y envía un ACK por cada una de ellas.
Entonces, el emisor, que está a la espera de un sólo ACK, recibe dos ACK's que
pueden causar problemas si el emisor asume que el segundo ACK es para la
siguiente trama en la secuencia.
Para evitar estos problemas, la solución más común es definir un número de
secuencia de 1 bit en la cabecera de la trama. Este número de secuencia es
alternado (de 0 a 1) en las tramas posteriores. Así, cuando el receptor envía un
ACK, incluye el número de secuencia de la siguiente trama que espera recibir. De
esta forma, el receptor puede identificar tramas duplicadas al checar si el número
de secuencia de la trama fue alternado. Si dos tramas subsiguientes tienen el
mismo número de secuencia, significa que son duplicados, y la segunda trama es
desechada. De igual forma, si dos ACK's subsiguientes hacen referencia al mismo
número de secuencia, entonces significa que están acusando de recibo a la misma
trama.

7
Como comentario, recordar que todo esto puede ser aplicado tanto a tramas,
como a paquetes, ya que estos protocolos pueden ser implementados tanto en la
capa de Enlace de Datos, como en la capa de Transporte del modelo OSI.
El método ARQ de Parada-y-Espera es ineficiente comparada con otros métodos
ARQ porque el tiempo entre paquetes, en caso de que los ACK's y los datos sean
recibidos satisfactoriamente, es el doble del tiempo de transmisión (suponiendo
que el tiempo que tardan los hosts en procesar la información y responder es
cero). El rendimiento en el canal es una fracción de lo que realmente podría ser.
Para solucionar este problema, se puede enviar más de un paquete a la vez con un
número de secuencia más grande y usar un sólo ACK para dicho conjunto de

8
paquetes. Esto es lo que se realiza con los métodos ARQ de Rechazo simple (Go-
Back-N) y de Repetición Selectiva (Selective Repeat).
Pueden ocurrir dos tipos de error. El primero consiste en que el código que llega al
destino puede estar dañado. El receptor detecta este hecho mediante la utilización
de técnicas de detección de errores y, simplemente, descartará la trama. Para dar
respuesta a esta situación, la estación fuente utiliza un temporizador. De este
modo, tras el envío de una trama, la estación espera la recepción de una
confirmación; si no se recibe ninguna confirmación antes de que el temporizador
expire, se procederá a reenviar el mismo código.

Obsérvese que este método exige que el emisor conserve una copia del código
transmitido hasta que se reciba la confirmación correspondiente.

El segundo tipo de error se refiere a una confirmación deteriorada. Considérese la

siguiente situación. Una estación A envía un código, que se recibe correctamente
en una estación B, la cual responde con una confirmación (ACK). La trama ACK se
deteriora en el camino, de modo que no es identificable por A, por lo que se
producirá una expiración del temporizador y se reenviará la misma trama de datos.
Esta trama duplicada llega y se acepta por B. Así pues, B ha aceptado dos copias
del mismo código como si fueran distintas. Para evitar este problema, los códigos
se pueden etiquetar de forma alternada con 0 o 1, siendo las confirmaciones
positivas de la forma ACK0 y ACK1.

La principal ventaja del esquema ARQ con parada y espera es su sencillez. Su

desventaja más importante no es otra que el procedimiento parada y espera es
ineficiente. Para conseguir una utilización más eficiente de la línea se puede hacer
uso de las técnicas de control de flujo mediante ventana deslizante, a las cuales se
les suele referir como ARQ-continuous.

2.1.2 El ARQ-continuos (Ventana deslizante)

En ARQ-continuous el transmisor envía palabras de código al receptor de manera

constante y recibe respuestas de este último de la misma manera. Cuando un NAK
es recibido el transmisor debe iniciar una retransmisión, según uno de los dos
siguientes patrones: Go-back-N-ARQ y selective-repeat-ARQ.

2.1.2.1 Go-back-N-ARQ (Rechazo simple)

El rechazo es un tipo de respuesta usado en control de errores.

9
Si se utiliza un protocolo basado en ventana deslizante lo que se reenvía es
todo lo que no haya sido confirmado.
Go-back-N-ARQ: El primer patrón de retransmisión consiste en reenviar las
palabras de código desde que fue detectada errónea.

El transmisor envía continuamente paquetes de información, con un

número de identificación, y el receptor envía los correspondientes ACK o
NAK con la identificación del paquete. Cuando se recibe un NAK el
transmisor vuelve a retransmitir desde el bloque erróneo en adelante.

Es un mecanismo fácil de implementar, pero con el inconveniente de que

puede darse el caso de reenvíos de tramas que habían llegado bien, con el
empeoramiento en el rendimiento del sistema que esto supone (por ejemplo, si
de 20 tramas falla la última, el receptor envía un REJ 20 y el emisor envía 20
tramas) Una ventaja de este sistema en escenarios con pocos errores es que
no limita tanto el tamaño de la ventana (número de paquetes que se pueden
enviar sin esperar confirmación por medio de un ACK) como la estrategia de
ventana deslizante. Esto perjudica tanto para el que lo recibe como para el que
lo da.

2.1.2.2 Selective-repeat-ARQ

La repetición selectiva (del inglés Selective Repeat) es un tipo de respuesta

usado en control de errores.
Selective-repeat-ARQ. Consiste en retransmitir únicamente la palabra del
código que pertenece el NAK recibido este último tipo de retransmisión es
más complejo en su implementación que el primero pero es más eficiente.
El esquema ARQ-continuous está diseñado para utilizarse en canales full –
dúplex

En este tipo de respuesta ARQ se envían paquetes hasta que se recibe

un NACK o hasta que se completa la ventana de transmisión definida; en
ese momento se termina de enviar el paquete que estábamos
transmitiendo y se reenvía el paquete que tenía errores; inmediatamente
después se sigue enviando la información a partir del último paquete que
se había enviado.
Este tipo de ARQ exige una memoria en el transmisor que sea capaz de
almacenar tantos datos como los que puedan enviarse en un timeout
(ventana de transmisión), ya que será el tiempo máximo de espera y esos
datos deben reenviarse tras detectar un error.

10
 Otra de las exigencias de este tipo de ARQ es la numeración de los ACK's
para poder distinguir a qué paquete de información están asintiendo.
Quizá el más molesto de todos los inconvenientes sea la recepción
desordenada de la información, lo que obliga a mantener otra ventana en
recepción para poder pasar los datos de manera ordenada a la capa
superior en caso de recibir un paquete con errores.

FEC (Forward Error Correction) (Corrección de Errores Hacia Adelante).

La corrección de errores hacia adelante (en inglés, Forward Error Correction o FEC)
es un tipo de mecanismo de corrección de errores que permite su corrección en el
receptor sin retransmisión de la información original. Se utiliza en sistemas sin
retorno o sistemas en tiempo real donde no se puede esperar a la retransmisión
para mostrar los datos. Este mecanismo de corrección de errores se utiliza por
ejemplo, en las comunicaciones vía satélite, en las grabadoras de DVD y CD o en las
emisiones de TDT para terminales móviles (estándar DVB-H).
Necesita sólo un enlace de ida, Los bits de paridad se diseñan tanto para detectar la
presencia de errores como para corregirlos. No es posible corregir todos los
posibles errores.

Funcionamiento
La posibilidad de corregir errores se consigue añadiendo al mensaje original unos
bits de redundancia. La fuente digital envía la secuencia de datos al codificador,
encargado de añadir dichos bits de redundancia. A la salida del codificador
obtenemos la denominada palabra código. Esta palabra código es enviada al
receptor y éste, mediante el decodificador adecuado y aplicando los algoritmos de
corrección de errores, obtendrá la secuencia de datos original. Los dos principales
tipos de codificación usados son:

 Códigos bloque. La paridad en el codificador se introduce mediante un algoritmo

algebraico aplicado a un bloque de bits. El decodificador aplica el algoritmo inverso
para poder identificar y, posteriormente corregir los errores introducidos en la
transmisión.
 Códigos convolucionales. Los bits se van codificando tal y como van llegando al
codificador. Cabe destacar que la codificación de uno de los bits está enormemente
influenciada por la de sus predecesores. La decodificación para este tipo de código
es compleja ya que en principio, es necesaria una gran cantidad de memoria para
estimar la secuencia de datos más probable para los bits recibidos. En la actualidad
se utiliza para decodificar este tipo de códigos el algoritmo de Viterbi, por su gran
eficiencia en el consumo de recursos.

11
 Podemos definir algunas ventajas y desventajas de ambas técnicas de
codificación

 Con errores a ráfagas: ARQ funciona mejor que los FEC simples
 Con errores independientes: FEC funciona mejor que ARQ
 FEC es muy sensible a la degradación del canal (interferencia, ruido impulsivo,
atenuación)
La ventaja del ARQ sobre el FEC es que el equipo de detección de errores es mucho
más simple y se requiere el uso de menos redundancia en los códigos.

3. Reglas de decisión
Para poder seleccionar la alternativa adecuada también existen una serie de modelos
de ayuda a la toma de decisiones que se conocen con el nombre genérico de “criterios
de decisión”. Estos criterios son los siguientes:

 Criterio de Laplace o de “igual verosimilitud”

 Criterio de Wald o del pesimismo absoluto.
 Criterio de Hurwicz o del pesimismo optimismo parcial
 Criterio del Maximax o del absoluto
 Criterio de Savage o de los pesares.
3.1. Criterio de Laplace o de “igual verosimilitud”

El modelo de Laplace o de la razón insuficiente. Se basa en la asignación de

probabilidades iguales para todos los estados debido a que en la ausencia de otra
evidencia, se considera que todas las situaciones del futuro tengan las mismas
probabilidades de ocurrir.

3.2. Criterio de Wald o del pesimismo absoluto

Este criterio se debe a Abraham Wald y se conoce también bajo los nombres de
“Maximin” y de criterio pesimista. Supone situación de esperar lo peor por lo que
se deberá seguir la estrategia que maximice el resultado mínimo. Es el criterio a
usar en decisiones de alto riesgo

3.3. Criterio de Hurwicz o del pesimismo optimismo parcial.

El criterio de Leonidas Hurwicz consiste en la creencia de un optimismo parcial o

atenuado. Sugiere la consideración de un coeficiente de optimismo que se
establece mediante un  que puede adoptar cualquier valor comprendido entre 0

12
y 1. En base a este coeficiente lo que hace es establecer una media ponderada
entre el mejor y el peor resultado de cada estrategia

3.4. Criterio del Maximax o del optimismo absoluto

El criterio Maximax consiste en elegir aquella alternativa que proporcione el mayor

nivel de optimismo posible.

Este criterrio corresponde a un pensamiento optimista, el decisor supone que las

probabilidades siempre estara de su parte, por lo que siempre se presentara el
estado o situacion mas favorable.

3.5. Criterio de Savage o de los pesares.

L. J. Savage propone otro criterio decisorio, también conocido con el nombre de la

“matriz de pesares” o regla del “Minimax”. Consiste este criterio en la búsqueda
de la diferencia existente entre cada resultado posible y lo que se hubiera podido
ganar, caso de haber elegido la alternativa mejor para ese estado de la naturaleza.
A esa diferencia se la denomina “coste condicional de oportunidad”.

13
4. PROBABILIDADES DE ERROR DE BITS

P (e) es una expectativa teórica de la tasa de error de bit (BER) para un sistema determinado.

BER es un registro empírico del verdadero rendimiento de error de bit de un sistema.

EJEMPLO

Para un P (e) de

Se puede esperar que ocurra un error de bit en cada millón de bits transmitidos.

Una tasa de error de bit:

Se mide, se compara con la P (e) esperada y se evalua el rendimiento de un sistema.

INTRODUCCION

Probabilidad de Error, P (e) es una función de la relación de potencia de la portadora, C, a Ruido.

C/N

Promedio de la relación de densidad de potencia de energía por bit de ruido con relación al
número de posibles condiciones de codificación utilizadas M-ario.

La relación de la potencia promedio de la portadora ( la potencia combinada de la portadora y sus

bandas laterales asociadas) a la potencia de ruido térmico.

POTENCIA DE PORTADORA

En dBm:

14
Dónde: C = Potencia de la portadora

POTENCIA DE RUIDO TERMICO

N = KTB (Watts)

Indicado en dBm:

N= Potencia de Ruido Termico(w)

K=Cte. De proporcionalidad de Boltzman

T= Temperatura (en ºk) (0º k= -273 ºc)

B = Ancho de banda(Hz)

RELACION DE POTENCIA DE LA PORTADORA RUIDO

Relacion sin unidades :

Indicado en dbm:

C= Potencia de la portadora (w)

N = Potencia de ruido (w)

ENERGIA POR BIT

15
Es la energía de un solo bit de información

Indicado en dBJ:

Eb= Energia de un solo bit(J/bit)

Tb= tiempo de un solo bit(s)

C= Potencia de la portadora (w)

DENSIDAD DE POTENCIA DE RUIDO

Es la potencia de ruido térmico normalizada a un ancho de banda de 1 Hz o potencia de ruido

presente en un ancho de banda de 1 Hz.

No= Densidad de potencia de ruido (W /Hz)

N= potencia de ruido térmico (w)

B= Ancho de banda (Hz)

16
5. TEOREMA DE SHANNON

El primer teorema de Shannon muestra que (en el límite en el que una cadena
de variables aleatorias independientes e idénticamente distribuidas de datos tiende a
infinito) es imposible comprimir la información de forma que el ratio de codificación
(número medio de bits por símbolo) es menor que la entropía de Shannon de la fuente, si
se garantiza que no haya pérdida de información. Sin embargo, sí es posible conseguir un
ratio de codificación arbitrariamente cerca del valor de la entropía de Shannon.
El primer teorema de Shannon establece una cota inferior y superior de la longitud
mínima posible de bits de información
Shannon estudia el caso general de un sistema de comunicación, compuesto por un
emisor, un receptor, un canal de transmisión y una fuente de ruido, que en todo sistema
real de transmisión existe en mayor o menor medida. En la siguiente imagen se muestra la
representación del propio Shannon de dicho sistema general de comunicaciones.

A partir del
esquema anterior y a lo largo de más de cincuenta páginas, Claude E. Shannon demuestra
mediante complejos cálculos matemáticos su famoso teorema de las comunicaciones.
Todo el artículo está lleno de límites, derivadas, integrales, cálculos de estadística y
probabilidades y otros procedimientos matemáticos. En la siguiente imagen se muestra
un ejemplo de dichos cálculos
el resultado final del teorema de las comunicaciones de Shannon es una pequeña fórmula,
fácil de aplicar y de recordar, y de consecuencias fundamentales para todos los sistemas

de comunicaciones modernas: En la fórmula de

Shannon, C es la velocidad máxima en bits por segundo, B es el ancho de banda en Hz
y S/N es la relación señal a ruido (signal/noise), sin unidades. Para cualquier sistema de
transmisión con un determinado ancho de banda y con una relación dada de señal a ruido,

17
el teorema de Shannon limita la velocidad máxima en bps que se puede obtener, sea cual
sea la técnica de transmisión empleada. El límite de velocidad que impone el teorema de
Shannon a cualquier sistema real de transmisión hay que entenderlo de la misma manera
que existe una temperatura de cero absoluto y por debajo de la cual no se puede bajar o
el límite de la velocidad de la luz, por encima de la cual no se puede subir. Y esto es
válido para cualquier sistema de transmisión (fibra óptica, radio, cable de pares, cable
coaxial, etc). Ni se puede sobrepasar hoy en día ese límite ni tampoco se podrá sobrepasar
en el futuro.

Por ejemplo, en un sistema de comunicaciones como es la

telefonía analógica, que utiliza un ancho de banda de 3100 Hz (300-3400) y tiene una
relación de señal a ruido de unos 35,5 dB (la señal es aproximadamente 3548 veces mayor
que el ruido), la velocidad máxima que se podrá obtener será de:

Este valor es el límite teórico impuesto por el Teorema de Shannon, al cual los modems
sobre linea analógica se han acercado pero nunca lo han igualado. Por eso estos modems
sobre líneas analógicas han tenido como velocidad máxima 33600 bps, y eso a costa de
utilizar complejas codificaciones y modulaciones de la señal, que en ausencia de
condiciones óptimas de la línea, obliga siempre a los modems a negociar una velocidad
aun más baja.

18
Un caso similar lo tenemos en los accesos ADSL, donde frecuentemente los usuarios
demandan velocidades que a determinada distancia de la central no es posible
suministrar, se haga lo que se haga. ¿Por qué no es posible dar, por ejemplo, 20 Mbps a
un usuario que vive a 5 Km de la central y sin embargo si es posible dar dicha velocidad a
uno que vive a 300 metros de la central? La respuesta de nuevo está en el teorema de
Shannon: el usuario que vive a 5 km de la central tiene un bucle de abonado o par de hilos
de cobre con un ancho de banda muy inferior respecto del que vive a 300 metros de la
central y además, también tendrá con seguridad una peor relación señal a ruido.

Otro caso muy claro donde el teorema de Shannon hace acto de presencia es en las
instalaciones de cableado estructurado, donde una instalación de categoría 3 solo
permitirá una velocidad de 10 Mbps mientras que una instalación de categoría 5e
permitirá 1000 Mbps, es decir 1 Gbps y una instalación de categoría 6A permitirá 10 Gbps.
¿En que se diferencian estas instalaciones entre sí? Fundamentalmente en el ancho de

19
banda de las señales que dejan pasar sin dificultad, 16 MHz para la categoría 3, 100 MHz
para la categoría 5e y 500 MHz para la categoría 6A.

Categorías TIA/EIA de cableado estructurado junto con los parámetros a verificar

Para mas detalles sobre velocidades y anchos de banda en instalaciones de cableado
estructurado, se puede consultar la siguiente entrada que está en el blog dedicado a fibra
óptica e instalaciones de redes en general y que también llevamos desde el instituto
Tartanga: Categorías de cableado estructurado y aplicaciones de las mismas.
Y si bien hasta ahora los ejemplos anteriores han sido referidos a cables de cobre, como se
ha dicho al comienzo, el teorema de Shannon es válido para cualquier sistema de
transmisión actual o incluso para cualquier nuevo sistema que se descubra en el futuro.

Y aunque no lo conocieran en su momento, también ha afectado a todas las

comunicaciones en el pasado, por ejemplo a las comunicaciones mediante tambores: en
este caso se ve con claridad que el límite de velocidad vendrá dado por la velocidad con la
que el emisor puede golpear el tambor produciendo sonidos lo suficientemente separados
para que los pueda identificar el receptor. Suponiendo que el tambor se comporta como
una fuente de sonido ideal, el medio, que en este caso es el aire, no se comporta en
absoluto con un sistema de transmisión ideal, ya que los pulsos de sonido se transmiten
sufriendo un cierto retraso y sufriendo también diversas reflexiones y ecos en las propias
capas de aire y en los distintos obstáculos que se encuentran en el camino. Los pulsos de
sonido llegan al receptor por varios caminos diferentes y por tanto con diferentes retardos
entre sí, por lo que el receptor no percibe los diferentes golpes de tambor separados de
forma nítida, sino con una cierta mezcla entre ellos. A medida que aumenta la velocidad
de envío de sonidos el efecto de mezcla en el receptor aumenta, llegando un momento en
el que no es posible diferenciar los golpes individuales en el tambor y por tanto, no es
posible interpretar la información recibida.

20
Parece claro que si además se está en una situación de mucho ruido ambiente -cerca de
una catarata, con ruido de animales, con el ruido producido por una tormenta o con
cualquier otra clase de ruido, la relación señal a ruido del canal de comunicación será
menor, lo que trae como consecuencia una mayor dificultad al receptor para identificar
los sonidos recibidos. Si se quiere mantener la comunicación, el emisor tendrá que
aumentar el nivel de señal enviado o disminuir la velocidad de envío de los sonidos.

Comunicación mediante tambores con buena relación señal a ruido

Comunicación mediante tambores con mala relación señal a ruido

21
Lo mismo se puede decir respecto a las comunicaciones mediante señales de humo, que
todos hemos podido ver en las ya antiguas películas de indios y vaqueros. Este sistema de
comunicación también tiene un ancho de banda determinado, que viene dado, entre otras
circunstancias, por el tiempo que tardan en disiparse en el aire las nubes de humo
producidas por el emisor. Si el transmisor produce nubes de humo “ideales” a mucha
velocidad, se producirá un cierto solapamiento en la atmósfera entre nubes de humo
consecutivas, llegando un momento en que el receptor tendrá una gran dificultad para
observar las nubes individuales producidas. A partir de ese momento, cualquier aumento
en la velocidad de producción de nubes de información provocará que el receptor pase a
observar prácticamente una única nube suspendida en el aire, haciéndose imposible la
transmisión de información. Al igual que en el caso anterior de transmisión de sonido,
también en este caso la relación señal a ruido del medio de transmisión influirá en la
velocidad máxima a la que se puede enviar información. Ahora el ruido se debe a aquellas
condiciones climáticas que dificultan la observación de las nubes de información al
receptor, como la presencia de lluvia o niebla. En estos casos, el transmisor deberá de
disminuir la velocidad a la que produce las nubes de información para permitir al receptor
la identificación de las mismas o, manteniendo la velocidad, deberá de generar nubes de
mayor intensidad, pero en este caso, el mayor tiempo que se necesitará para que se
disipen en el aire, frenará de nuevo la velocidad de transmisión. De nuevo el teorema de
Shannon limitando la velocidad máxima

Y aunque es cierto es que los medios de transmisión continuamente están aumentando

las velocidades máximas disponibles, la forma en que lo consiguen es o bien mejorando el
ancho de banda o bien mejorando la relación señal a ruido, es decir, cumpliendo con lo
establecido en el teorema de Shannon. Cuando en un medio de comunicación mejoramos
el ancho de banda, por ejemplo al pasar del par de cobre del viejo sistema telefónico
analógico a la fibra óptica o los cables coaxiales empleados en las redes FTTH y en HFC,
directamente se pueden enviar señales de más bits por segundo, aun empleando el
mismo sistema de codificación. En cambio, cuando ya no es posible aumentar el ancho de
banda, todavía podemos mejorar la relación señal a ruido, como por ejemplo utilizando
cables apantallados o trenzando los pares para evitar la influencia entre ellos. Con este
sistema podemos utilizar codificaciones multinivel más complejas de tal manera que
aunque la señal transmitida no aumenta los cambios en la línea por segundo (baudios), si
que se aumentan los bits por segundo transmitidos. En la siguiente imagen se observan las
codificaciones MLT-3, PAM 5 y PAM 16 utilizadas respectivamente en los sistemas
Ethernet 100 BASE-TX, 1000 BASE-T y 10GBASE-T

22
Evidentemente, cuantos mas niveles de señal se puedan transmitir, mas bits se podrán
codificar en cada cambio de la señal. Así, con el sistema PAM16 se pueden transmitir
hasta 4 bits en cada cambio de la señal (2^4=16). Por supuesto, para que todo esto pueda
funcionar es necesario que el nivel de ruido en cada uno de los pares del cable del sistema
10GBASE-T debe de ser muy inferior al ruido que puede haber en los pares de un cable
que se utiliza para transmitir señales de 100-BASE-TX o 1000-BASE-T, ya que de otra forma
la señal PAM16 quedaría absolutamente enmascarada por el ruido y sería imposible la
comunicación.

23
6. Códigos Binarios Lineales
En teoría de la codificación, un código lineal es un código de corrección de errores
para los que cualquier combinación lineal de palabras de código es también una
palabra de código. Los códigos lineales son tradicionalmente divididos en bloques de
códigos y códigos convolucionales, aunque los códigos turbos pueden ser vistos como
un híbrido de estos dos tipos. Los códigos lineales permiten la codificación más
eficiente y algoritmos de decodificación que otros códigos (cf. síndrome de
decodificación).

Los códigos lineales se utilizan en la corrección de errores hacia adelante y se aplican

en los métodos de transmisión de símbolos (por ejemplo, los bits) en un canal de
comunicaciones, de manera que, si se producen errores en la comunicación, algunos
errores pueden ser corregidos o detectados por el receptor de un bloque de mensaje.
Las palabras de código en un código de bloque lineal son bloques de símbolos que son
codificados usando más símbolos que el valor original para ser enviadas. Un código
lineal de longitud n transmite bloques que contienen n símbolos. Por ejemplo, la [7,
4,3] código de Hamming es un código binario lineal que representa los mensajes de 4-
bits utilizando palabras de código de 7-bits. Dos palabras de código distintas difieren
en por lo menos tres bits. Como consecuencia de ello, hasta dos errores por palabra
de código pueden ser detectados y un solo error puede ser corregido. Este código
contiene 24=16 palabras de código.

6.1 Definición y parámetros

Un código lineal de longitud n y rango k es un sub espacio lineal C con dimensión k

del espacio vectorial donde es el campo finito con q elementos. Tal código se
denomina un código q-ario. Si q = 2 o q = 3, el código se describe como un código
binario, o un código ternario respectivamente. Los vectores en C se llaman
palabras de código. El tamaño de un código es el número de palabras de código y
es igual a qk.

El peso de una palabra de código es el número de sus elementos que son distintos
de cero y la distancia entre dos palabras de código es la distancia de Hamming
entre ellos, es decir, el número de elementos en los que difieren. La distancia d de
un código lineal es el peso mínimo de sus palabras de código distintas de cero, o de
forma equivalente, la distancia mínima entre palabras de código diferentes. Un
código lineal de longitud n, la dimensión k, y la distancia d se denomina [n,k,d]
código.

Observación: Queremos dar a la base estándar habitual, ya que cada

coordenada representa un "bit", que se transmite a través de un " canal con ruido
", con alguna pequeña probabilidad de transmisión de errores (un canal binario

24
 simétrico). Si se utiliza alguna otra base, este modelo no puede ser utilizada y la
métrica de Hamming no mide el número de errores en la transmisión, que es lo que
se quiere.

7. Códigos de Hamming.
Es un método general propuesto por R. W Hamming usando una distancia mínima m.
Con este método, por cada entero m existe un código de Hamming de 2m-1 bits que
contiene m bits de paridad y 2m-1-m bits de información. En este código, los bits de
paridad y los bits de paridad se encuentran entremezclados de la siguiente forma: Si se
numeran las posiciones de los bits desde 1 hasta 2m-1, los bits en la posición 2k,
donde , son los bits de paridad y los bits restantes son bits de
información.

El valor de cada bit de paridad se escoge de modo que el total de unos en un número
específico de bits sea par, y estos grupos se escogen de tal forma que ningún bit de
información se cubra con la misma combinación de bits de paridad. Es lo anterior lo
que proporciona al código su capacidad de corrección.
Para cada bit de paridad en la posición 2k, su grupo de bits de información
correspondiente incluye todos esos bits de información correspondiente cuya
representación binaria tenga un uno en la posición 2k. La siguiente tabla muestra los
grupos de paridad para un código de Hamming de 7 bits o sea de la forma 2m-1 con m
= 3. En este ejemplo, los bits de información son 4 y los bits de paridad son 3. Los bits
de información están en las posiciones 7, 6, 5 ,3. Los bits de paridad están en las
posiciones 1, 2, 4.

En la tabla anterior, el grupo de paridad del bit de paridad situado en la posición 4 son
los bits de información situados en las posiciones 7, 6, 5 que contienen unos en la
posición 2k o sea 4 cuando k = 2.

25
El grupo de paridad del bit de paridad situado en la posición 2 son los bits de
información situados en las posiciones 7, 6, 3 que contienen unos en la posición 2k o
sea 2 cuando k = 1.
El grupo de paridad del bit de paridad situado en la posición 1 son los bits de
información situados en las posiciones 7, 5, 3 que contienen unos en la posición 2k o
sea 1 cuando K = 0. Como 111 es la representación binaria de 7, el bit de información
en la posición 7 se usa para calcular el valor de los tres bits de paridad. Similarmente,
el bit de información en la posición 6 se usa para calcular el valor de los bits de paridad
en las posiciones 4 y 2; el bit de información en la posición 5 se usa se usa para
calcular el valor de los bits de paridad en las posiciones 4 y 1. Finalmente, el bit de
información en la posición 3 se usa para calcular el valor de los bits de paridad en las
posiciones 2 y 1.
De acuerdo con estos grupos de paridad, el valor del bit de paridad de la posición 1
tiene que elegirse de modo que el número de unos en las posiciones 7, 5, 3, 1 sea par,
mientras el bit de paridad en la posición 2 hace el número de unos par 7, 6, 3, 2 y el
valor del bit de paridad en la posición cuatro hace el número de unos par en las
posiciones 7, 6, 5, 4.

Es fácil observar que, en estas condiciones, la distancia mínima es 3, o sea que tienen
que haber al menos tres cambios de un bit para convertir una palabra de código en
otra.

Para probar que un cambio de un bit siempre genera una palabra que no pertenece al
código, hay que observar que un cambio de un bit en una palabra del código afecta al
menos un bit de paridad.

Por otra parte, un cambio de dos bits en una palabra del código no cambia el valor del
bit de paridad si ambos bits pertenecen al mismo grupo de paridad. Sin embargo ello
no es posible ya que para dos posiciones cualquiera de una palabra del código siempre
hay un grupo de paridad que no incluye ambas posiciones. En otras palabras, como
dos bits cualquiera deben estar en distintas posiciones, sus números binarios deben
diferir al menos en un bit, así que siempre hay al menos un grupo de paridad con un
solo bit cambiado, lo cual da lugar a una palabra que no pertenece al código con al
menos un valor de paridad incorrecto.

Ejemplo.
Supóngase que se transmite una palabra de código y se recibe una palabra que no
pertenece al código y que es 1110101. ¿Cuál fue la palabra correcta transmitida?

26
En la tabla anterior se puede observar lo siguiente:
Cuando se cuenta el número de unos que hay en los bits, 7, 6, 5, 4 de la palabra del
código recibida, se encuentra que este número es impar. De forma similar, se
encuentra que los bits 7, 6, 3, 2 contienen un número0 impar de unos. Por tanto hay
un error en los bits de paridad 4 y 2. Como la suma de los números en esas posiciones
es 6, se sabe que el error se ha producido en el bit de posición 6 y por tanto la palabra
transmitida fue 1010101.
Ejemplo

Consideremos la palabra de datos de 7 bits "0110101". Para ver cómo se generan y

utilizan los códigos Hamming para detectar un error, observe las tablas siguientes. Se
utiliza la d para indicar los bits de datos y la p para los de paridad.

En primer lugar los bits de datos se insertan en las posiciones apropiadas y los bits de
paridad calculados en cada caso usando la paridad par.

p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7

Palabra de datos (sin paridad): 0 1 1 0 1 0 1

p1 1 0 1 0 1 1

p2 0 0 1 0 0 1

p3 0 1 1 0

p4 0 1 0 1

Palabra de datos (con paridad): 1 0 0 0 1 1 0 0 1 0 1

Cálculo de los bits de paridad en el código Hamming

P1 = D1 exor D2 exor D4 exor D5 exor D7

P2 = D1 exor D3 exor D4 exor D6 exor D7

27
 P3 = D2 exor D3 exor D4
P4 = D5 exor D6 exor D7

La nueva palabra de datos (con los bits de paridad) es ahora "10001100101".

Consideremos ahora que el bit de la derecha, por error, cambia de 1 a 0. La nueva
palabra de datos será ahora "10001100100".

Sin errores

p1 p2 d 1 p3 d2 d3 d4 p4 d5 d6 d7 Prueba de Bit de
paridad comprobación

Palabra de 1 0 0 0 1 1 0 0 1 0 1 1
datos
recibida:

p1 1 0 1 0 1 1 Correcto 0

p2 0 0 1 0 0 1 Correcto 0

p3 0 1 1 0 Correcto 0

p4 0 1 0 1 Correcto 0

Comprobación de los bits de paridad (con primer bit de la derecha sin cambiar)

Con errores

p1 p 2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Prueba de Bit de
paridad comprobación

Palabra de 1 0 0 0 1 1 0 0 1 0 0 1
datos
recibida:

p1 0 0 1 0 1 0 Error 1

p2 1 0 1 0 0 0 Error 1

p3 0 1 1 0 Correcto 0

p4 1 1 0 0 Error 1

28
 Comprobación de los bits de paridad (con primer bit de la derecha cambiado)

Si se analiza en la tabla anterior la paridad que se debe obtener a la derecha tras la

llegada del mensaje sin errores debe ser siempre 0 (por cada fila), pero en el momento
en que ocurre un error esta paridad cambia a 1, de allí el nombre de la columna
"prueba de paridad 1". Se observa que en la fila en que el cambio no afectó la paridad
es cero y llega sin errores.

El paso final es evaluar los bits de paridad (recuerde que el fallo se encuentra en d7). El
valor entero que representan los bits de paridad es 11 (si no hubieran ocurrido errores
este valor seria 0), lo que significa que el bit décimo primero de la palabra de datos
(bits de paridad incluidos) es el erróneo y necesita ser cambiado.

p4 p3 p2 p 1

Binario 1 0 1 1

Decimal 8 2 1 Σ = 11

Cambiando el bit décimo primero 10001100100 se obtiene de nuevo 10001100101.

Eliminando los bits de patrón de la paridad no se tienen en cuenta los bits de paridad.
Si el error se produjera en uno de ellos, en la comprobación sólo se detectaría un
error, justo el correspondiente al bit de paridad causante del mismo.

29
8. Códigos Cíclicos

Un código cíclico es aquel que dado un vector codificado C  (C1 , C2 ,..., Cn ) los otros vectores son
desplazamientos cíclicos de este como: (C2 , C3 ,..., Cn , C1 ) , (C4 , C5 ,..., Cn , C1 , C2 , C3 ) ,etc., a
excepción de los vectores formados únicamente por 0’s o 1’s. La matriz generadora G se obtiene a
partir de un polinomio llamado también generador.

g ( x)  x nk  ...  1

De coeficientes 1’ s o 0’ s.

Para obtener la matriz G a partir de polinomio generador se procede de la siguiente manera:

1. Se escribe en el renglón k-ésimo los coeficientes de g (x) .

2. al renglón k-1, corresponden los coeficientes de g 2 ( x) donde g 2 ( x)  x  g ( x) si el
coeficiente de x nk 1 de g (x) es cero, y g 2 ( x)  x  g ( x)  g ( x) si el coeficiente de x nk 1
de g (x) es uno.
3. Al renglón k-2, corresponden los coeficientes de g 3 ( x) donde g 3 ( x)  x  g 2 ( x) si el
coeficiente de x nk 1 de g 2 ( x) es cero, y g 3 ( x)  x  g 2 ( x)  g ( x) si el coeficiente de x nk 1
de g 2 ( x) es uno.
4. Así sucesivamente.

Ejemplo.

Consideremos al código (7, 3) de polinomio generador g ( x)  x 4  x 2  x  1 , obténgase G.

Solución.

3er renglón: g ( x)  x 4  x 2  x  1
2do renglón: x nk 1 = x 3 , coeficiente en g (x)  0 

g ( x)  x  g ( x)  x( x 4  x 2  x  1)

30
  x5  x3  x 2  x
1er renglón: x nk 1 = x 3 , coeficiente en g 2 ( x) 1

g ( x)  x  g 2 ( x)  x( x 5  x 3  x 2  x)
 x6  x 4  x3  x 2
Entonces:

1 0 0 1 0 1 1
G  0 1 0 1 1 1 0
0 0 1 0 1 1 1

Para un código (7, k) los posibles polinomios generadores son factores de x 7  1 (para un código
(n, k) lo serán x n  1 ). Como:

x 7  1  ( x  1)(x 3  x  1)(x 3  x 2  1) Sumas mod 2

Dos polinomios generadores de un código (7, 3) son:

g1 ( x)  ( x  1)( x 3  x  1)  x 4  x 3  x 2  x
g 2 ( x)  ( x  1)( x 3  x 2  1)  x 4  x 2  x  1

Considerando el valor de d de datos como un polinomio de grado k-1 o menor:

d ( x)  d k x k 1  ...  d 2 x  d1 Donde: d  (d k , d k 1 ,..., d1 )

Se establece la operación:

x n k d ( x)
r ( x)  rem
g ( x)

Donde rem indica remanente o residuo, r(x) representa el vector de bits de paridad.

La operación anterior establece un procedimiento para obtener la palabra codificada sin usar la
matriz generadora. Se construye con registros de corrimiento y opera más rápidamente que
utilizando la matriz generadora.

D D D
Salida de n-k
bits de paridad
Salida de k bits de datos

El polinomio generador es:

31
 g ( x)  x nk  h11x nk 1  ...hnk x  1

Por ejemplo, para el código analizado:

g ( x)  x 4  x 2  x  1; ; sea d = (0, 1, 1) entonces:

x 4 ( x  1)
r ( x)  rem
x  x2  x 1
4

x 1
x 4  x 2  x  1 x5  x 4
x5  0  x3  x 2  x
0  x 4  x3  x 2  x
0  x4  0  x2  x 1
0  0  x3  0  0  1
 r ( x)  x 3  1
 Los bits de paridad son: (1, 0, 0, 1) y
el vector codificado es: (0, 1, 1, 1, 0, 0, 1)

Ejemplo.

Para un código (6, 2) y el polinomio generador g ( x)  x 4  x 3  1

a) Obtener su matriz generadora.

b) Usando el método de remanentes, determinar las palabras codificadas de 01 y 11.

Solución.

a) g ( x)  x 4  x 3  1 2° renglón

x nk 1 = x 3 , coeficiente en g 2 ( x) 1

g 2 ( x)  x  g ( x)  x( x 4  x 3  1)
 x5  x3  x  1

1 0 1 0 1 1
G (x)   
0 1 1 0 0 1

x 4 (1)
b) d  (0,1) d ( x)  1 ; r ( x)  rem
x4  x2 1

32
 1
x  x 1 x
4 3 4

x 4  x3  1
0  x3  1
 r ( x)  x 3  1  r  (1,0,0,1)
 c  (0,1,1,0,0,1)

x 3 ( x  1)
d  (0,1) d ( x)  x  1 ; r ( x)  rem
x4  x2 1
x
x  x 1 x  x
4 3 5 4

x5  x4  x
0 0  x
 r ( x)  x  r  (0,0,1,0)
 c  (0,1,1,0,0,1,0)

8. Código CRC

Comprobación de redundancia cíclica o control de redundancia cíclica (en informática, CRC).

Hace referencia a cyclic redundancy check, también llamado polynomial code checksum. El CRC
es una función diseñada para detectar cambios accidentales en datos de computadora y es
comúnmente usada en redes digitales y dispositivos de almacenamiento (como discos duros).

El CRC fue creado por W. Wesley Peterson en 1961; el polinomio de 32 bits usado en funciones
CRC de Ethernet (y otros estándares) fue publicado en 1975. Es muy popular por su simpleza de
implementación, fácil de analizar matemáticamente y es muy bueno detectando errores causados
por ruidos en los canales de transmisión.

Verificación de Redundancia Cíclica

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.

Descripción del Algoritmo

La comprobación de redundancia cíclica consiste en la protección de los datos en bloques,

denominados tramas. A cada trama se le asigna un segmento de datos denominado código de
control (al que se denomina a veces FCS, secuencia de verificación de trama, en el caso de una
secuencia de 32 bits, y que en ocasiones se identifica erróneamente como CRC). El código CRC

33
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 término suele ser usado para designar tanto a la función como a su resultado. Pueden ser
usadas como suma de verificación para detectar la alteración de datos durante su transmisión o
almacenamiento. Las CRC son populares porque su implementación en hardware binario es
simple, son fáciles de analizar matemáticamente y son particularmente efectivas para detectar
errores ocasionados por ruido en los canales de transmisión.

El concepto de CRC consiste en tratar a las secuencias binarias como polinomios binarios,
denotando polinomios cuyos coeficientes se correspondan con la secuencia binaria. Por ejemplo,
la secuencia binaria 0110101001 se puede representar mediante un polinomio, como se muestra a
continuación:

0*X9 + 1*X8 + 1*X7 + 0*X6 + 1*X5 + 0*X4 + 1*X3 + 0*X2 + 0*X1 + 1*X0
siendo
X8 + X7 + X5 + X3 + X0
o
X8 + X7 + X5 + X3 + 1

De esta manera, la secuencia de bits con menos peso (aquella que se encuentra más a la derecha)
representa el grado 0 del polinomio (X0 = 1), (X0 = 1), (X0 = 1), el 4º bit de la derecha representa el
grado 3 del polinomio (X3), y así sucesivamente. Luego, una secuencia de n- bits forma un
polinomio de grado máximo n-1. Todas las expresiones de polinomios se manipulan
posteriormente utilizando un módulo 2.

En este proceso de detección de errores, un polinomio predeterminado (denominado polinomio

34
generador y abreviado G(X)) es conocido tanto por el remitente como por el destinatario. El
remitente, para comenzar el mecanismo de detección de errores, ejecuta un algoritmo en los bits
de la trama, de forma que se genere un CRC, y luego transmite estos dos elementos al
destinatario. El destinatario realiza el mismo cálculo a fin de verificar la validez del CRC.

Funcionamiento del CRC

A cada bloque de datos le corresponde una secuencia fija de números binarios conocida como
código CRC (esto se calcula con una misma función para cada bloque). Ambos se envían o
almacenan juntos. Cuando un bloque de datos es leído o recibido, dicha función es aplicada
nuevamente al bloque, si el código CRC generado no coincide con el código CRC original, entonces
significa que el bloque contiene un error. Eso hará que el dispositivo intente solucionar el error
releyendo el bloque o requiriendo que sea enviado nuevamente.

Si coinciden ambos códigos CRC, entonces se asume que el bloque no contiene errores (existe una
remota posibilidad de que haya un error sin detectar). El nombre "control/comprobación de
redundancia cíclica" se debe a que se "controla" (verificación de datos) un código redundante (no
agrega nueva información, el código CRC representa el mismo bloque de datos) y el algoritmo está
basado en códigos cíclicos. Es importante destacar que el número de caracteres de entrada a la
función CRC puede tener cualquier longitud, pero siempre producirá un código CRC de igual
longitud.

Polinomios generadores

Los polinomios generadores más comunes son:

 CRC-12: X12 + X11 + X3 + X2 + X + 1

 CRC-16: X16 + X15 + X2 + 1
 CRC CCITT V41: X16 + X12 + X5 + 1(este código se utiliza en el procedimiento HDLC)
 CRC-32 (Ethernet): = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 +
X+1
 CRC ARPA: X24 + X23+ X17 + X16 + X15 + X13 + X11 + X10 + X9 + X8 + X5 + X3 + 1

Aplicaciones Prácticas

Digamos que M es el mensaje que corresponde a los bits de la trama que se enviará, y que M(X) es
el polinomio relacionado. Supongamos que M' es el mensaje transmitido, por ejemplo, el mensaje
inicial al que se concatena un CRC de n bits. El CRC es el siguiente: M'(X)/G(X)=0. Por lo tanto, el
código CRC es igual al remanente de la división polinomial de M(X) (X) (al que se le ha anexado
los n bits nulos que corresponden a la longitud del CRC) entre G(X).

35
Por ejemplo, tomemos el mensaje M con los siguientes 16 bits: 1011 0001 0010
1010 (denominado B1 en hexadecimal). Tomemos G(X) = X3 + 1 (representado en el sistema
binario por 1001). Siendo que G(X) tiene un grado 3, el resultado es añadirle a M 4 bits
nulos: 10110001001010100000. El CRC es igual al remanente de M dividido por G:

10110001001010100000
1001...,..,.,.,.....
----...,..,.,.,.....
0100..,..,.,.,.....
0000..,..,.,.,.....
----..,..,.,.,.....
1000.,..,.,.,.....
0000.,..,.,.,.....
----.,..,.,.,.....
1000.,..,.,.,.....
1001,..,.,.,.....
----,..,.,.,.....
1111..,.,.,.....
1001..,.,.,.....
----..,.,.,.....
1100.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
1101,.,.,.....
1001,.,.,.....
----,.,.,.....
1000.,.,.....
0000.,.,.....
----.,.,.....
10001......
1001,.,.....
----,.,.....
10000.,.....
1001.,.....
----
1111,.....
1001,.....
----,.....
1100.....
1001.....

36
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----..
1100.
1001.
----.
1010
1001
----
0011

Para crear M' se debe concatenar el CRC resultante con los bits de la trama que se va a transmitir:

M' = 1011000100101010 + 0011

M' = 10110001001010100011

Por lo tanto, si el destinatario del mensaje divide M' por G, obtendrá un remanente de cero si la
transmisión ocurrió sin errores.

10110001001010100011
1001...,..,.,.,...,,
----...,..,.,.,...,,
0100..,..,.,.,...,,
0000..,..,.,.,...,,
----..,..,.,.,...,,
1000.,..,.,.,.....
1001.,..,.,.,.....
----.,..,.,.,.....
0010,..,.,.,.....
0000,..,.,.,.....
----,..,.,.,.....
0101..,.,.,.....
0000..,.,.,.....

37
----..,.,.,.....
1010.,.,.,.....
1001.,.,.,.....
----.,.,.,.....
0110,.,.,.....
0000,.,.,.....
----,.,.,.....
1101.,.,.....
1001.,.,.....

----.,.,.....
1010,.,.....
1001,.,.....
----,.,.....
0111.,.....
0000.,.....
----
1110,.....
1001,.....
----,.....
1111.....
1001.....
----.....
1100....
1001....
----....
1010...
1001...
----...
0110..
0000..
----,,
1101,
1001,
----,
1001
1001
----
0

38
9. Códigos Convolcionales

Los códigos convolucionales son un tipo de códigos para la detección de errores en canales de
comunicaciones. Este tipo de código genera símbolos codificados pasando los bits de información
por registros de desplazamiento lineales.

Funcionamiento
El codificador convolucional está formado por k registros de desplazamiento de una entrada y
normalmente inicializados a 0. La salida de estos registros se conectan a n sumadores binarios
(puertas XOR) siguiendo los polinomios generadores característicos de la codificación
convolucional concreta utilizada. Finalmente, los resultados de estas sumas generalmente se
serializan mediante un multiplexor. Estas operaciones generan una palabra código de longitud n

por cada k bits de la secuencia de entrada. La tasa binaria de este tipo de código es de
Las operaciones realizadas para la codificación producen que al estudiar el codificador desde el
punto de vista de la respuesta al impulso se observe que responde a una operación de convolución
de los bits de entrada, hecho que le da el nombre a este tipo de codificación.
Representación con Maquinas de Estado
Dado que estos codificadores tienen memoria finita, una forma común de representación de los
mismos es el diagrama de transición de estados. En él, los estados corresponden al valor de los
registros de cierto instante y las transiciones marcan la nueva entrada y la salida dada esa entrada.
Un ejemplo de representación en "máquina de estados" sería el siguiente:

39
Este código convolucional tiene una tasa de codificación de 1/2, y utiliza los polinomios
generadores g1= [1 0 1] y g2=[(1 1 1] .
La máquina de estados parte de la inicialización a nulos de todos los registros. En el interior de
cada estado se observan los posibles valores de los registros 1 y 2, ya que el registro 0 vendrá
determinado por la nueva entrada del sistema. Esto es, si el estado de los registros comienza en [0
0 0] y la siguiente entrada es un 1, se elegirá la rama 1/11 (entrada 1, salida 11). Tras producir esta
salida e introducir la siguiente entrada, los registros desplazan los valores por lo que quedarán [x 0
1] , siendo x la nueva entrada.

Los códigos convolucionales se describen a partir de ciertos elementos como son la tasa del
código, la longitud del código, la memoria del codificador y los polinomios generadores. La tasa del
código, k/n, es la relación entre el número de bits que entran al codificador (k) y el número de bits
que se obtienen a la salida del codificador (n). En cuanto a la longitud del código, K, denota en
cuántos ciclos de codificación tiene influencia un bit que tengamos a la entrada del mismo a partir
de un instante dado, ya que recordemos que este bit que tenemos a la entrada del codificador en
un instante dado irá recorriendo la cadena de flip-flops que forman el registro de desplazamiento.
Así, un parámetro muy relacionado con K es la memoria del codificador, m, que precisamente es el
número de flip-flops que contiene el codificador. Por último, los polinomios generadores son
también muy importantes a la hora de definir el funcionamiento de un codificador convolucional,
y veremos mejor su significado mediante un ejemplo.

La codificación convolucional se realiza básicamente mediante el uso de un registro de

desplazamiento y una lógica combinacional encargada de la realización de la suma en módulo 2. El
registro de desplazamiento está implementado mediante la concatenación de una serie de flips-
flops, de manera que cada vez que llega un ciclo de reloj, el dato que tenemos a la entrada de un
flip-flop pasa a su salida y se sitúa por tanto en la entrada del siguiente flip-flop, que ha hecho lo
propio con el dato que tenía en su entrada cuando llegó el ciclo de reloj. En cuanto a la lógica
combinacional que realiza la suma en módulo 2, basta con utilizar puertas XOR.

40
En la siguiente figura podemos apreciar un ejemplo de codificador convolucional, en el que la tasa
del código es 1/2, K=3 y m=2. En este codificador, los bits de entrada llegan con una tasa de k bits
por segundo y obtenemos una tasa a la salida del codificador de n=2k bits por segundo. El bit de
entrada se mantiene estable durante el ciclo de codificación, el cual comienza cada vez que llega
un ciclo de reloj. Cuando llega el ciclo de reloj, la salida del flip-flop izquierdo se introduce en el
flip-flop derecho, es decir, pasa a la salida de éste, y el bit que teníamos a la entrada del
codificador previamente pasa a la salida del primer flip-flop. Es entonces cuando el nuevo bit está
disponible en la entrada. En cuanto al multiplexor que tenemos a la salida, conmuta durante el
ciclo de reloj entre las dos posiciones, de manera que primero selecciona la salida del sumador
superior y posteriormente selecciona la salida del sumador inferior, formando así el símbolo de
dos bits. En cuanto a los polinomios generadores, en este caso se trata de un codificador (7,5).
Estos dos números representan los polinomios generadores, ya que las representaciones binarias
de estos números (111 y 101) se corresponden con las conexiones del registro de desplazamiento
y los sumadores superior e inferior respectivamente. En este caso los polinomios generadores
serían 1 + x + x2 y 1 + x2 respectivamente.

Veamos ahora el funcionamiento de la codificación convolucional mediante un ejemplo.

Supongamos la secuencia de entrada 010111001010001. Supongamos también que las salidas de
ambos flip-flops están inicialmente a 0. El primer ciclo de reloj hace que el primer bit a la entrada,
0, esté disponible a la entrada del codificador. Las salidas de los flip-flops son ceros y por tanto
todas las entradas a ambos sumadores son también ceros, por los que la salida de ambos
sumadores es 0, de manera que el símbolo de salida sería el 00.

El segundo ciclo de reloj hace que el segundo bit de entrada esté disponible para el codificador.
Ambos flip-flops leen los bits que tenían en sus entradas previamente, que en ambos caso eran 0.
Así, las entradas al sumador superior son 100, de manera que su salida es 1. Análogamente las
entradas al sumador inferior son 10, por lo que su salida también es un 1. Por tanto, el símbolo
codificado esta vez sería el 11.

El tercer ciclo de reloj hace que el tercer bit de entrada, un cero, esté disponible para el
codificador. El primer flip-flop lee su entrada anterior, que era un 1, y el segundo flip-flop hace lo
mismo leyendo el cero que tiene en este caso en su entrada, por lo que ahora las entradas a los
sumadores son 010 y 00, lo que hace que el símbolo obtenido en esta ocasión sea el 10. Después
de que todos los bits de entrada hayan pasado por el codificador, la secuencia de salida sería:

00 11 10 00 01 10 01 11 11 10 00 10 11 00 11.

En este ejemplo se puede ver claramente como cada bit de entrada tiene efecto en los 3 símbolos
de salida siguientes, ya que se trata de un codificador con K=3. De hecho este es un punto
extremadamente importante y es lo que le da a la codificación convolucional la potencia para
corregir errores.

Por este motivo, si queremos que el último bit afecte a tres símbolos de salida se necesitan dos
símbolos de salida adicionales. Esto se consigue introduciendo dos bits a cero en el codificador en

41
los dos siguientes ciclos de reloj. Con esto conseguimos los dos símbolos adicionales que
necesitamos y además "limpiamos" el registro de desplazamiento, de manera que para la próxima
secuencia a codificar tendremos a las entradas de los flip-flops un 0, como supusimos inicialmente.
En general, el número de ceros que tenemos que introducir es igual al número de flip-flops que
contiene nuestro codificador.

De esta explicación se pueden extraer algunas conclusiones, y es que podemos ver el algoritmo de
codificación convolucional como una máquina de estados. El codificador del ejemplo tiene dos bits
de memoria, lo que significa que tenemos cuatro estados posibles. Podemos decir que el estado lo
definen las entradas que tienen los flip-flops en un instante dado. Por ejemplo, si en ambas
entradas tenemos un cero, estaremos en el estado 00, si la primera entrada es un cero y la
segunda es un uno, estaremos en el estado 01 y así sucesivamente. Asimismo, si estando en el
estado 00 (ambas entradas a cero) el bit que tenemos a la entrada cuando llega el siguiente ciclo
de reloj es un cero, entonces permaneceremos en el estado 00. Sin embargo, si el siguiente bit a la
entrada es un uno en lugar de un cero, pasaremos al estado 10. Análogamente, si estando en el
estado 10 el siguiente bit a la entrada es un cero, pasaremos al estado 01 mientras que si el bit de
entrada es un 1, pasaríamos al estado 11. Por tanto podemos completar la tabla 1 que nos indica
cuál es el siguiente estado dependiendo del estado en el que estamos y del bit que nos llega a la
entrada y la tabla 2, que nos indica cuál es el símbolo de salida en función de nuevo del estado en
el que nos encontramos y del bit de entrada que nos llega.

Estado siguiente si...

Estado Actual
Entrada = 0 Entrada = 1

00 00 10

01 00 10

10 01 11

11 01 11

Símbolo de salida si...

Estado Actual
Entrada = 0 Entrada = 1

00 00 11

01 11 00

10 10 01

11 01 10

42
 Bibliografía

1.- El teorema de Shannon

http://www.tsc.urjc.es/Master/RETEPAD/sites/default/files/Curso0_Ficha2.pdf
2.-Redes de Computadoras - 4ta Edición - Andrew S.Tanenbaum
3.-http://huitoto.udea.edu.co/SistemasDiscretos/contenido/cod_hamming.html
4.-http://es.wikipedia.org/wiki/Codigo_Hamming

5.-http://es.wikipedia.org/wiki/Codigos_lineales

6.- http://ma.alvarez0005.eresmas.net/trabajos/ccvsatelite/teoria.html

43