DEPARTAMENTO DE CIENCIA Y TECNOLOGÍA

UNIVERSIDAD NACIONAL DE QUILMES

Roque Sáenz Peña 352 – (B1876BXD) Bernal – Buenos Aires – Argentina

TEORÍA DE LAS TELECOMUNICACIONES - IACI

11 CODIFICACIÓN DE CANAL

La codificación de canal es la transformación intencional que se le hace a una señal de

comunicación a fin de tener un mejor desempeño frente a efectos adversos que produce el
ruido presente en el canal de comunicación. Normalmente la meta que se persigue al hacer
una codificación de canal es reducir la probabilidad de error de bit PB o bien reducir la
exigencia de relación Eb/N0 requerida para alcanzar una cierta probabilidad de error de bit.
Normalmente, esta mejora se hace a expensas de un incremento del ancho de banda utilizado.

La codificación de canal puede dividirse en dos áreas. Una trata con el diseño de una
forma de onda adecuada y la otra con el diseño de una estructura de bits adecuada. La
codificación o diseño de forma de onda consiste en generar la mejor forma de onda posible,
para el canal de comunicación considerado, para que el proceso de detección que se lleva a
cabo en el receptor sea lo menos sensible posible al ruido y de esta manera reducir la
probabilidad de error de bit. Esto lo hemos visto cuando estudiamos modulación en banda base
y modulación pasa banda, y analizamos esquemas de modulación tales como PSK, FSK, QAM o
codificaciones en banda base tales como unipolar, bipolar, Manchester, etc. Encararemos en
este capítulo la codificación de canal mediante la manipulación de estructuras de bits.

El diseño de secuencias estructuradas consiste en la transformación de la secuencia

original de datos en una secuencia “mejor” mediante el agregado de bits redundantes. Estos
bits redundantes se usan para la detección y/o corrección de errores. La probabilidad de error
de bit buscada como objetivo de diseño dependerá de cada aplicación en particular. En algún
caso una probabilidad de error de bit PB = 10-2 podrá ser suficiente, mientras que en otro caso
quizás se requiera una PB de 10-9. Obviamente, como en todo diseño de ingeniería, cuando uno
pretende un mejor desempeño del sistema debe pagarlo con algún costo extra, por lo tanto se
trata de buscar la mejor relación costo-beneficio.

En el tratamiento de la codificación de canal siempre aparece el concepto de distancia

entre símbolos. La distancia entre símbolos (o señales) da una idea de qué tan diferentes son
esas dos señales. Como ya hemos estudiado, cuanto más diferentes, o sea más distantes, son
dos señales, menos probabilidad tienen de confundirse una con otra cuando el ruido las afecta.
Como se verá más adelante, en la codificación estructurada el concepto de distancia también
está presente.

Antes de entrar de lleno al tema de codificación, vamos a ver algunos conceptos

introductorios.

Canal simétrico binario

Un canal simétrico binario (CSB) es un canal de comunicación que presenta dos

símbolos de entrada, x0 = 0, x1 = 1, que ocurren con igual probabilidad, y dos símbolos de
salida, y0 = 0, y1 = 1. Los símbolos de salida yi representan a los símbolos de entrada que han
sido afectados por el ruido del canal. El canal se dice que es simétrico porque la probabilidad
de recibir un 1 habiéndose transmitido un 0 es igual a la probabilidad de recibir un 0
habiéndose transmitido un 1. Esta probabilidad condicional se denota con la letra p y se llama
probabilidad de transición del canal. La Figura 1 muestra un diagrama que representa un

11 Codificación de canal 1
modelo de canal simétrico binario. Nótese que si la probabilidad de recibir erróneamente un bit
es p, entonces obviamente, la probabilidad de recibirlo correctamente es 1 – p.

Figura 1. Canal simétrico binario.

En la Figura 1 se ve que habiéndose transmitido un 0 a la entrada del canal, como

consecuencia del ruido existe una probabilidad p de recibir un 1 a la salida del mismo.
Similarmente ocurre para un 1 binario a la entrada. Si p = 0 entonces los símbolos de entrada
siempre se recibirán correctamente a la salida.

La probabilidad de transición de canal depende de la forma de onda usada para la

transmisión y de la relación Eb/N0 en el receptor.

Capacidad de canal

Sobre esta idea y varias consideraciones teóricas que están fuera de los alcances de la
materia, Shannon desarrolló los temas referentes a capacidad de canal, a través de un trabajo
publicado el año 1948. Esto es, cuánta información es posible transmitir por un canal simétrico
binario cuando a la entrada del mismo se tiene una fuente con una cierta entropía H(S). La
base de los estudios de Shannon estaba en analizar la entropía de la fuente a partir de la
observación de los elementos a la salida del CSB, es decir, del lado del receptor. La capacidad
de canal da cuenta de la cantidad de información que es posible transmitir a través de un
CSB. Sin entrar en detalles teóricos, simplemente definiremos que la capacidad de un canal se
representa por la letra C y se expresa en bits por uso del canal1.

En un canal simétrico binario, las características del mismo quedan determinadas

únicamente por la probabilidad de transición p. Se puede demostrar que para este tipo de
canal la capacidad C viene dada por:

C  1  p  log2 p  (1  p)  log2 (1  p) (1)

La ecuación (1) se muestra graficada en la Figura 2. Allí se puede observar que:

1. Cuando el canal no presenta ruido resulta ser p = 0 y la capacidad es máxima e

igual a 1. Obviamente que es 1, ya que a la entrada del canal se encuentra una fuente discreta
binaria equiprobable, en cuyo caso la entropía H(S) es 1. Por lo tanto, al no haber ruido, esa
es la máxima cantidad de información que puedo transmitir sobre el canal.

2. Cuando el canal comienza a hacerse ruidoso la capacidad del mismo para transmitir
información comienza a disminuir. El caso extremo ocurre cuando p = 0,5 y en tal caso la
capacidad del canal se hace 0. Esto suena lógico ya que siendo p = 0,5 la probabilidad de error
es tal que, a la salida del canal da lo mismo arrojar una moneda al aire y optar por “1” si salió

1
Shannon hizo un estudio más generalizado y no se refirió solamente al canal simétrico binario sino que determinó la
capacidad de canal para un canal de J entradas y K salidas al que denominó canal discreto sin memoria.

2 11 Codificación de canal
cara u optar por “0” si salió ceca. Es decir, no importa la fuente de información que se tenga a
la entrada del canal ante una situación así.

Figura 2. Variación de la capacidad de un canal simétrico binario en función de la probabilidad de

transición.

Teorema de codificación de canal

La presencia inevitable del ruido en un canal de comunicación hace que se produzca

una discrepancia entre la secuencia de datos transmitida y la secuencia recibida. Al usar
codificación de canal se está aumentando la resistencia al ruido del sistema digital de
comunicaciones. La codificación basada en estructuras de bits consiste en un mapeo de la
secuencia de datos que sale de la fuente en otra secuencia que ingresa al canal de
comunicación, realizándose la operación inversa a la salida del canal, de manera que el efecto
total del ruido sobre el canal sea minimizado. Esta operación de mapeo se realiza por medio de
un codificador en el lado del transmisor, mientras que la operación inversa del lado del
receptor se realiza por medio de un decodificador. La Figura 3 describe este proceso en forma
de diagrama de bloques.

Fuente Canal
Codificador Decodificador
discreta sin discreto sin Destino
de canal de canal
memoria memoria

Ruido

Figura 3. Diagrama en bloques simplificado de un sistema de comunicación digital.

Los bits de información van saliendo de la fuente de información y el trabajo del

codificador es agregar bits de redundancia a los bits de información, de una manera
preestablecida, y explotar esta redundancia en el decodificador para reconstruir la señal de la

11 Codificación de canal 3
manera más fiel posible. La codificación de canal pareciera que echa a perder el trabajo
realizado durante la codificación de fuente en la que el objetivo es eliminar bits redundantes.
Sin embargo, las dos operaciones se complementan. Con la codificación de fuente lo que
se busca es aumentar la eficiencia del sistema, mientras que con la codificación de
canal se busca aumentar la confiabilidad del sistema.

Normalmente, y luego lo veremos en detalle, el trabajo del codificador es convertir una

secuencia de k bits de mensaje en una secuencia mayor de n bits, siendo en consecuencia
n > k. Por lo tanto, el número de bits redundantes agregados a la secuencia de bits de
mensaje es n – k. La relación entre k y n se llama tasa de código y se la designa por R:

k
R (2)
n

siendo obviamente R menor que 1.

La pregunta que surge es: ¿se puede construir un esquema de codificación tal que la
probabilidad de error de bit de un mensaje sea todo lo pequeña que uno desee? La respuesta a
esta pregunta es sí, siempre que se cumplan ciertas condiciones. Esta respuesta afirmativa la
dio Shannon.

Supóngase que un canal discreto sin memoria tiene una entropía H(S) bits por símbolo
de fuente. Supongamos que la fuente transmite un símbolo binario cada Ts segundos. Por lo
tanto, la tasa de información es H(S)/Ts bits por segundo. El codificador entrega símbolos
codificados (más grandes, de longitud n) también cada Ts segundos. Por otra parte, el canal al
que van ingresando los paquetes codificados tiene una capacidad de C bits por uso del canal.
Como el codificador ha agregado bits al mensaje original pero la duración del símbolo binario
se debe mantener igual, resulta que cada bit que conforma el paquete codificado es ahora más
pequeño, digamos de duración TC. Por lo tanto, al canal ingresa un bit (físico) cada TC
segundos. Teniendo todo esto en mente podemos enunciar el teorema de Shannon de
codificación del canal, para un canal discreto sin memoria:

1. Sea una fuente discreta sin memoria, S, que tiene una entropía H(S) y produce
símbolos cada TS segundos. Sea un canal discreto sin memoria con capacidad C al que ingresa
un bit cada TC segundos. Entonces, si

H(S) C
 (3)
TS TC

existe un esquema de codificación tal para el cual cada símbolo de la fuente puede ser
transmitido sobre el canal y puede ser reconstruido con una probabilidad de error
arbitrariamente baja.

2. Inversamente, si

H(S) C

TS TC

entonces no es posible transmitir información sobre el canal y reconstruirla con una

probabilidad de error arbitrariamente pequeña.

Este es uno de los resultados más importantes de la teoría de la información. Nótese

que este teorema establece límites, sin embargo no dice nada acerca de cómo debe ser el
esquema de codificación que los haga cumplir. El esquema quizás sea extremadamente
complicado o muy difícil de implementar, pero ese es otro tema. El teorema sólo garantiza la
existencia de ese código.

4 11 Codificación de canal
 Consideremos una fuente discreta sin memoria que emite símbolos binarios igualmente
probables (ceros y unos) una vez cada TS segundos. Ya que la entropía de esta fuente es de 1
bit por símbolo, la tasa de información resulta ser 1/TS bits por segundo. La secuencia de
salida de la fuente ingresa a un codificador de canal con tasa de código R = k/n. El codificador
entrega al canal un bit cada TC segundos. Por lo tanto, la capacidad del canal por unidad de
tiempo es C/TC bits por segundo, donde C queda determinado por la probabilidad de transición
del canal, p. Por lo tanto, de acuerdo a la primera parte del Teorema de Shannon, si se cumple

1 C
 (4)
TS TC

entonces la probabilidad de error puede hacerse arbitrariamente pequeña usando algún

esquema de codificación apropiado. Ya que TC/TS es la tasa de código

TC
R
TS

entonces la (4) se puede rescribir como

RC (5)

Es decir que, si la tasa de código R del esquema de codificación es menor o igual a la

capacidad del canal entonces la probabilidad de error se puede hacer arbitrariamente pequeña.

Ejemplo 1. Consideremos un CSB con una probabilidad de transición p = 10-2. Para

este valor, la capacidad del canal es C = 0,9192, usando la ecuación (1). Por lo tanto, del
teorema de codificación de canal podemos establecer que para cualquier  > 0 y R ≤ 0,9192
existe un código lo suficientemente largo de longitud n y tasa de código R (de valores
adecuados), con un apropiado algoritmo de codificación, de tal manera que cuando dicho
código se envía por este canal la probabilidad de error de decodificación es menor que .

Atención. Tiene que quedar en claro esto de n y k apropiados. Por ejemplo, si R = ½ se

está cumpliendo con la (5) y por lo tanto se puede hacer que la probabilidad de error del
mensaje recibido sea tan pequeña como se desee, digamos 10-50, por ejemplo. Esto NO
necesariamente significa que usando k = 1 y n = 2 (o sea, R = ½) se va a llegar a ese
objetivo. Quizás se deba utilizar k = 4 y n = 8, o quizás k = 1024 y n = 2048, etc. El Teorema
de Shannon de codificación del canal asegura que tal código existe pero no establece cómo es
ese código.

Volviendo al enunciado de este ejemplo, nos planteamos un código llamado código de

repetición que consiste en enviar varias veces el mismo bit de mensaje. Cada bit (1 o 0) se
envía n veces, siendo n = 2m +1, donde m es un entero. Por ejemplo, si n vale 3 entonces
cada símbolo se transmite como 111 o 000. El decodificador decodifica por mayoría de ceros o
de unos. Si la mayoría bits recibidos es 0 supone que el símbolo transmitido fue 0. Caso
contrario supone que fue 1.

Con este esquema, un error, es decir, una detección incorrecta, puede ocurrir siempre
que se reciban m+1 o más bits incorrectos. Para n = 3 la detección será incorrecta cuando se
reciban 2 o 3 bits incorrectos de un mismo bloque. La probabilidad Pe de recibir
incorrectamente un símbolo codificado, es

n
 n
Pe      p i  1  pn  i
i
i  m 1  
(6)

Los resultados de la (6) se agrupan en la tabla siguiente, para distintos valores de n.

11 Codificación de canal 5
 Tasa de código Probabilidad de error
R = 1/n Pe (Para p = 0,01)
1 10-2
1/3 3 x 10-4
1/5 10-6
1/7 4 x 10-7
1/9 10-8
1/11 5 x 10-10

Nótese que a medida que se achica R se hace más pequeña la probabilidad de error de
símbolo. Planteándose, por ejemplo, un objetivo de Pe = 10-8, si bien con R = 1/3 se cumple la
(5), la Pe no queda satisfecha. Esto significa que se deben buscar otros valores de k y n que
den 1/3. Sin embargo, el objetivo sí se cumple para R = 1/9 o más chico.

Es importante aclarar que este resultado es engañoso ya que en verdad la

probabilidad de transición de canal p no se mantiene constante al agregar bits de
redundancia sino que aumenta. Esto es porque la energía de bit disminuye. La idea del
ejemplo es simplemente ver cómo actúan los bits de redundancia para reducir la probabilidad
de error de símbolo.

Tipos de control de error

Antes de entrar en detalle con los códigos redundantes veamos las dos maneras básicas
en la que tal redundancia es usada para el control de errores. Una de estas maneras se llama
detección de error y retransmisión. Como su nombre lo indica, en este caso no hay corrección
de error sino solamente detección. El receptor detecta el error valiéndose de los bits de
redundancia pero no lo corrige, simplemente solicita al transmisor que vuelva a transmitir el
símbolo. Nótese que en este caso se requiere una comunicación de dos vías para que puedan
dialogar el transmisor y el receptor.

El segundo tipo de control de error es el control de error hacia adelante (FEC, forward
error control), o control de error en avance. Requiere comunicación de una sola vía y en este
caso los bits de redundancia se usan para la detección y posterior corrección de errores. Sin
embargo, como veremos más adelante, no es posible corregir todos los patrones de error o
situaciones de error posibles. Si así fuera estaríamos en el caso PB = 0 que nunca se puede
alcanzar en la práctica.

Respecto a la comunicación de una o dos vías que se menciona antes, podemos decir
que la comunicación entre dos terminales se puede clasificar de tres maneras. Supóngase dos
terminales A y B. Se dice que la comunicación entre ambas es simplex cuando sólo puede
realizarse en un sentido (por ejemplo desde A hacia B pero no desde B hacia A). La
comunicación se dice que es half-duplex (o semiduplex) cuando se puede realizar en ambos
sentidos pero no simultáneamente (por ejemplo un par de walkies talkies). Y finalmente la
comunicación es full duplex (o dúplex total) cuando se puede realizar en ambos sentidos y
simultáneamente.

Solicitud de repetición automática (Automatic Repeat Request)

Cuando el control de errores consiste en la detección del error solamente, el sistema de

comunicaciones necesita disponer de un modo de alertar al transmisor de que un error se ha
detectado en el receptor y que se necesita una retransmisión. Este procedimiento se lo conoce
como solicitud de repetición automática (ARQ, Automatic Repeat Request). En la Figura 4 se
ven tres de los mecanismos más conocidos del procedimiento ARQ. En cada diagrama la escala
de tiempos crece de izquierda a derecha. En el primer procedimiento, llamado parada y espera
(stop and wait), el transmisor espera de parte del receptor un mensaje de confirmación (ACK,
acknowledgment) después de cada transmisión, para saber si sigue con la siguiente

6 11 Codificación de canal
transmisión. Si ocurre un error en el receptor, éste envía una confirmación negativa (NAK,
negative acknowledgment) al transmisor y éste retransmite el bloque de datos afectado antes
de seguir transmitiendo con el bloque que correspondía en la secuencia. En este mecanismo es
suficiente una comunicación half duplex ya que la comunicación es en ambos sentidos pero no
simultáneamente.

El segundo mecanismo de ARQ se llama continuo con pullback (retroceso). En este caso
se requiere una comunicación full duplex. Ambas terminales están transmitiendo
simultáneamente. El transmisor envía datos y el receptor envía mensajes de confirmación.
Véase en la Figura 4(b) que se le ha asignado una secuencia de números a los bloques de
datos. Los mensajes ACK y NAK necesitan usar dichos números como referencia para que el
transmisor sepa a qué bloque de datos corresponde el ACK o el NAK que envió el receptor. En
el ejemplo (b) de la Figura 4 se muestra un retardo fijo de 4 bloques entre el mensaje
transmitido y la confirmación recibida simultáneamente. Por ejemplo, cuando se está
transmitiendo el bloque de mensaje 8, simultáneamente se está recibiendo un NAK que
corresponde al mensaje 4. En este tipo de mecanismo ARQ, cuando el transmisor recibe un
NAK vuelve hacia atrás hasta el bloque de datos erróneo y comienza a transmitir la secuencia
de nuevo desde allí.

Figura 4. Esquemas ARQ. (a) Stop and wait (parada y espera). Es half duplex. (b) ARQ continuo con
pullback (retroceso). Es full duplex. (c) ARQ continuo con repetición selectiva (full duplex).

El último tipo de mecanismo ARQ que se muestra en la Figura 4 se llama ARQ continuo
con repetición selectiva. Al igual que en el segundo caso se utiliza un canal full duplex pero
aquí, cuando el transmisor recibe un NAK retransmite solamente el bloque de datos que ha
sido erróneo y luego continúa con la secuencia normalmente (nótese cómo el bloque 4 fue
intercalado entre los bloques 8 y 9).

11 Codificación de canal 7
 La elección de algunos de estos mecanismos ARQ depende de la eficiencia buscada y de
la posibilidad o no de usar un canal full duplex. El canal half duplex del ejemplo (a) es menos
costoso que un canal full duplex, sin embargo, la ineficiencia asociada a este mecanismo se
puede ver en las ranuras de tiempo en blanco que hay entre cada bloque. Como contraparte,
en los ejemplos (b) y (c) se ve una mejor eficiencia en la comunicación (no se desperdician
ranuras de tiempo) pero un canal full duplex es más costoso.

La diferencia fundamental entre ARQ y el FEC es que el primero consiste simplemente

en una detección de error y el hardware asociado es más sencillo y se requiere mucho menos
redundancia que en el caso de un FEC. Sin embargo, el FEC es más conveniente en los
siguientes casos:

1. No se dispone una comunicación desde el receptor hacia el transmisor o bien el

retardo que introduciría un ARQ es muy grande.

2. El número de errores esperados es bastante grande y se requieren excesivas

retransmisiones.

Secuencias estructuradas

Como se dijo anteriormente, una de las áreas pertenecientes a la codificación de canal

consiste en agregar bits de redundancia a los bits de datos de manera tal que puedan ayudar a
detectar y/o corregir errores cuando éstos se producen como consecuencia del ruido que
afecta al canal de comunicación. Estos procedimientos son clasificados como secuencias
estructuradas ya que representan métodos de inserción de redundancia en forma estructurada
en una fuente de datos de manera tal que se pueda detectar o corregir la presencia de errores.
Estas secuencias estructuradas se dividen en dos grupos: códigos de bloque y códigos
convolucionales. Primeramente trataremos con los códigos de bloque y los códigos
convolucionales los estudiaremos en otro capítulo.

En los códigos de bloque, la fuente de datos es segmentada en bloques de k bits de

datos, llamados también bits de información o bits de mensaje. Cada bloque puede
representar un mensaje de un total de 2k mensajes diferentes. El codificador transforma este
grupo de k bits en un grupo o bloque más grande de n bits de longitud, llamados bits de
código o símbolos de canal. A este bloque resultante también se lo llama palabra de código o
codeword en inglés. Los (n – k) bits que el codificador le agrega al bloque inicial de k bits se
llaman bits de redundancia, bits de paridad o bits de verificación. Estos bits de redundancia
no llevan información. Este nuevo bloque que se ha formado mediante el codificador se lo
identifica como código (n, k). El cociente entre la cantidad de bits redundantes y la cantidad de
bits de datos, (n – k)/k, se llama redundancia del código; y la relación entre la cantidad de bits
de datos y la cantidad total de bits k/n se llama tasa de código, como ya se dijo antes.

El agregado de redundancia a los bits de mensaje produce un aumento del ancho de

banda (espectro) requerido para la transmisión. Por ejemplo, una técnica de control de error
que usa una tasa de código R de ½ (es decir, 100% de redundancia) va a necesitar el doble de
ancho de banda que para el caso en que no esté codificado. Esto es intuitivamente claro, ya
que se debe transmitir el doble de bits en el mismo tiempo y por lo tanto el tiempo Tb de cada
bit se reduce a la mitad, duplicándose el ancho de banda. Como otro ejemplo, si se usa un
esquema de codificación cuya tasa de código sea ¾, es decir 33% de redundancia, el ancho de
banda aumenta en un factor de 4/3.

Códigos de verificación de paridad simple

Un código con bit de paridad simple es una construcción que se hace agregando un solo
bit de redundancia, o bit de paridad, a un grupo o bloque de k bits de datos. Este bit de
paridad toma el valor 1 o 0, según sea, para forzar a que la suma de todos los bits de la
palabra de código (incluyendo el bit de paridad) sea par o impar (según la regla que se haya

8 11 Codificación de canal
adoptado). La operación de suma se hace en aritmética de módulo 2 (es decir, es una
operación lógica OR exclusiva). Para verlo de otro modo, decimos que se agrega un bit de
paridad de tal manera que la cantidad de “unos” en el bloque siempre sea par o siempre sea
impar, según la convención que se haya establecido de antemano. Para el primer caso el
método se llama codificación con bit de paridad par y en el segundo caso codificación con bit
de paridad impar. Nótese que si la codificación es según bit de paridad par entonces la suma
en módulo 2 de todos los bits de la palabra de código da 0. Para el caso de bit de paridad
impar la suma da 1. En la Figura 5 se muestra un ejemplo de código de paridad par.

Figura 5. Ejemplo de código de paridad par.

Una vez que el bloque llega al receptor se debe realizar la decodificación y determinar si
se ha producido un error o no. Esta verificación se hace sumando en módulo 2 todos los bits
del bloque recibido y comprobando el resultado. Si se usó paridad par y la suma da 0 entonces
se supone que no hay errores. Por el contrario, si estando codificado con paridad par el
resultado da 1 quiere decir que un error ha ocurrido.

Indudablemente, este código (como todos en realidad) no es perfecto y pueden darse

casos en los que ocurren errores y el sistema no los detecta. Por ejemplo, si ocurren 2 errores
en el bloque transmitido y se está usando paridad par, el resultado de la suma de todos los
bits en el decodificador va a dar 0. En tal caso el decodificador no estaría detectando el error.
Lo mismo pasa si se producen 4, 6, 8, etc. errores. Por el contrario, el sistema será capaz de
detectar 1, 3, 5, etc. errores.

Para este esquema de codificación la tasa de código R es k/k+1. La ventaja que tiene
este esquema es su sencilla implementación. Un conjunto de compuertas XOR permite generar
el bit de paridad, como lo muestra la Figura 6.

Figura 6. Generación de bit de paridad. El bit de polarización es 1

para paridad impar o 0 para paridad par.

Hay que tener en cuenta que este esquema de codificación no puede corregir los
errores sino que sólo puede detectarlos. Teniendo en cuenta que sólo se puede detectar un
número impar de errores, tratemos de cuantificar la eficiencia de este código. Asumiendo que
todos los bits del bloque son igualmente probables y que son independientes entre sí, podemos
escribir la probabilidad de que ocurran j errores en un bloque de n bits de la siguiente manera:

 n
P( j, n)    p j (1  p)n  j (7)
 j

11 Codificación de canal 9
 donde p es la probabilidad de que un bit sea recibido con error, o probabilidad de
transición del canal. El número combinatorio

 n n!
  
j
  j! (n  j)!

representa las diferentes maneras en que j bits pueden ser erróneos dentro de un
bloque de n bits. Por lo tanto, en un código de detección de error con paridad simple, la
probabilidad Pnd de que un bloque erróneo de n bits no sea detectado es:

n / 2 (para n par)
(n-1)/2 (para n impar)
n  2 j
Pnd  
j 1
  p (1  p)n2 j
2 j 
(8)

Ejemplo 2. Configurar un código de detección de error (4, 3) con bit de paridad par, de
tal manera que el bit de paridad aparezca en el extremo izquierdo del código. ¿Cuáles son los
errores que puede detectar? Calcular la probabilidad de que NO se detecte un mensaje
erróneo, asumiendo que todos los bits son independientes entre sí y que la probabilidad de
error de bit o probabilidad de transición del canal es p = 10-3.

Solución.

Mensaje Paridad Código de bits

000 0 0 000
100 1 1 100
010 1 1 010
110 0 0 110
001 1 1 001
101 0 0 101
011 0 0 011
111 1 1 111

El código es capaz de detectar 1 o 3 errores en cada símbolo o palabra de código. La

probabilidad de que no se detecte un error que ha ocurrido en una palabra de código es igual a
la probabilidad de que ocurran 2 o 4 errores en cualquier lugar de la palabra de código:

 4  4
Pnd    p 2 (1  p)2    p 4
2   4
 6 p 2 (1  p)2  p 4
 6 p 2  12p 3  7 p 4
 6(10  3 )2  12(10  3 )3  7(10  3 ) 4  6  10  6

Ganancia de código

La Figura 7 muestra curvas características de probabilidad de error de bit PB en función

de Eb/N0. Se compara una curva característica de modulación bipolar en banda base, sin
codificar, con otras dos curvas del mismo esquema de modulación pero codificadas con ciertos
códigos (n, k). Una lleva un código (24, 12) y la otra un código (127, 92). En el primer caso
(n - k) = 12 y en el segundo caso (n – k) = 35.

Obviamente, es de esperar que el agregado de un código de detección o corrección de

error produzca una mejora en el desempeño de PB. Sin embargo, nótese en la figura que las
tres curvas se cruzan casi en un punto (aproximadamente en 6 dB en este ejemplo) que por
debajo o por encima de él la variación de PB presenta características diferentes.

10 11 Codificación de canal
Concretamente, los códigos de error de este ejemplo comienzan a ser efectivos a partir de
Eb/N0 mayor a esos 6 dB. Para valores menores a este umbral los códigos empeoran el
desempeño (confiabilidad) en lugar de mejorarlo. La explicación de esta característica es la
siguiente: el bloque con redundancia (cualquiera sea ella) se debe transmitir en el mismo
tiempo que el bloque sin redundancia (sin codificar). Al agregar bits de redundancia con la
obligación de no modificar el tiempo de transmisión de símbolos, es necesario que cada bit que
forma la palabra de código de n bits tenga menor duración (menor tiempo de bit Tb), en
comparación con el tiempo de bit original. Pensemos que ahora deben transmitirse n bits en el
mismo tiempo en que antes se transmitían k bits, siendo n > k. Esto produce una menor
energía de bit en cada bit del bloque codificado, ya que la energía de bit es directamente
proporcional a Tb, con lo cual aumenta la probabilidad de transición de canal pues ésta es
dependiente de Eb. Para una tasa de transmisión elevada, o sea Tb pequeño, la relación Eb/N0
tiende a ser pequeña. Si encima se le agregan bits de redundancia entonces Eb tiende a ser
más pequeño aún, con lo cual los bits de redundancia tienen más influencia en la energía de
bit que en la mejora de desempeño que pueden producir por sí mismos como parte de un
código de corrección de errores. Superado un cierto umbral de Eb (una tasa de transmisión
más baja) entonces los bits de redundancia empiezan a tener más contribución por su efecto
de detección o corrección que por su efecto indeseado de disminución de la energía de bit Eb.

Figura 7. Comparación de curvas de probabilidad de error de bit

entre un sistema sin codificar (1, 1) y dos esquemas codificados.

Por lo tanto, los códigos de detección o corrección de error comienzan a ser efectivos
por encima de un cierto umbral de la relación Eb/N0. La ganancia de código es la reducción de
la relación Eb/N0, expresada en decibeles, requerida para un cierto valor de probabilidad

11 Codificación de canal 11
de error de bit, que se obtiene usando un código de control de error. Por ejemplo, en la
figura se ve que para una probabilidad de error de bit PB = 10-5, el código (24, 12) tiene una
ganancia de código de aproximadamente 2 dB respecto del mismo esquema sin codificar. El
código (127, 92) tiene una ganancia de aproximadamente 2,5 dB.

Esta ganancia de código puede interpretarse como energía de bit que “sobra” y que
puede aprovecharse de alguna manera. Supongamos que la ganancia de código de un cierto
código de corrección de error es de 3 dB para una PB de 10-5. Entonces se puede:

1) Mantener la misma probabilidad de error de bit de 10 -5 pero reduciendo la potencia

de transmisión en 3 dB. El beneficio es que ahora se requiere una fuente de
alimentación más pequeña, o menos pilas, o igual cantidad de pilas pero con mayor
autonomía, o si es un radioenlace la antena transmisora puede ser más pequeña,
entre otros ejemplos.

2) Mantener la misma PB y la misma potencia de transmisión y extender la distancia de

transmisión del enlace hasta que la potencia se reduzca 3 dB más que s lo que nos
“sobra” como consecuencia de la ganancia de código.

3) Mantener la PB de 10-5 y reducir la Eb en 3dB reduciendo el tiempo de bit a la mitad

(3 dB). Esto significa duplicar la tasa de bit R sin alterar la probabilidad de error de
bit.

4) Obviamente, dejar fijo Eb y quedarse con el beneficio de la mejora en la probabilidad

de error de bit.

Ejemplo 3. Comparar la probabilidad de error de mensaje, en un enlace de

comunicaciones, con código corrector de error y sin él. Asumir las siguientes características
para el sistema sin codificar: modulación bipolar en banda base, ruido blanco Gaussiano,
S/N0 = 43.776 veces, tasa de bit R = 4.800 bits/s. Para el caso codificado asumir un código
corrector de error (15,11) capaz de corregir un error simple dentro de un bloque de 15 bits.

Solución.

Sea p la probabilidad de error de bit (probabilidad de transición de canal) del sistema

sin codificar:


p  Q 2E b / N 0 
y pc la probabilidad de error de bit (probabilidad de transición de canal) del sistema
codificado:


pc  Q 2E c / N 0 
Eb/N0 es la energía de bit por densidad espectral de potencia de ruido del sistema sin
codificar y Ec/N0 es la energía de bit por densidad espectral de potencia de ruido del sistema
codificado. Q(x) es la función de error.

Con el sistema sin codificar tenemos lo siguiente:

Eb S
  9,12 (9,6 dB)
N0 RN 0

 2E b
p  Q
 N0

 
  Q 18,24  1,02  10 5

(9)
 

12 11 Codificación de canal
 La probabilidad de que el bloque sin codificar sea recibido con al menos un error es:

PM  1  (1  p)k
1 
1
 
p
11
 1,12  10 4
(10)
probabilid ad de que
los 11 bits sin
codificar sean
recibidos correctame nte

Con codificación:

En este caso, la tasa de símbolo es 15/11 veces la tasa de bit.

15
Rc  4800   6545 bps
11

Ec S
  6,688 (8,25 dB)
N0 Rc N 0

Nótese que la relación Ec/N0 para cada bit del código es menor que para los bits sin
codificar ya que se ha aumentado la tasa de bit (pues los bits son “más angostos” debido a su
menor duración) y la potencia se supone constante. Entonces, con el resultado anterior,
tenemos:

 2E c
pc  Q
 N0

 
  Q 13,38  1,36  10 4

(11)
 

Como consecuencia de la mencionada disminución de la energía de bit, la probabilidad

de error de bit ha empeorado y aún no se ve la supuesta mejoría que debería brindar el
sistema con código de corrección de error. Ahora vamos a calcular la probabilidad de error de
mensaje. Es decir, calculamos la probabilidad de que se produzcan dos bits erróneos o tres, o
cuatro, etc:

n  15
15
PMc    j
j 2
pc  j 1  pc 15  j

(12)

La sumatoria comienza en j = 2 ya que el código corrige todos los errores simples

dentro del bloque de n = 15 bits. Se obtiene una buena aproximación usando sólo el primer
término de la sumatoria:

15
PMc   pc  1  pc   1,94  10 6
2 13
(13)
2 

Ahora se ve, comparando los resultados, que la introducción del código corrector de
error produce una mejora de 58 veces.

Códigos de bloque lineales

Los códigos de bloque lineales son una clase de códigos de verificación de paridad más
general que los códigos con paridad simple y también se caracterizan por la notación (n, k)
descripta anteriormente. Una vez más, el codificador transforma un mensaje de k bits (al que
llamaremos vector de mensaje) en un bloque más grande de n bits (al que llamaremos vector
de código).

11 Codificación de canal 13
 Los k bits del mensaje pueden formar 2k mensajes distintos llamados k-uplas. Los n bits
del bloque pueden formar como máximo 2n diferentes secuencias, llamadas n-uplas. El
procedimiento de codificación asigna a cada uno de los 2 k mensajes de la k-upla uno de los 2n
posibles mensajes de la n-upla. Un código de bloque representa una asignación uno a uno,
mediante la cual los 2k mensajes de la k-upla son mapeados de manera unívoca en un nuevo
conjunto de 2k mensajes pertenecientes a la n-upla.

Espacios vectoriales

El conjunto formado por una n-upla Vn, es llamado espacio vectorial sobre el campo
binario de dos elementos, 0 y 1. El campo binario tiene dos operaciones aritméticas, suma y
multiplicación. El resultado de estas operaciones pertenece también al campo binario. En el
campo binario estas reglas aritméticas se definen de la siguiente manera:

Suma Multiplicación
0 0= 0 00=0
0 1= 1 01=0
1 0= 1 10=0
1 1= 0 11=1

La operación designada por el símbolo  corresponde a una suma en módulo 2.

Un subconjunto S del espacio vectorial Vn se llama subespacio si cumple con las dos
condiciones siguientes:

1. El vector nulo (todos ceros) pertenece a S.

2. La suma de dos vectores en S también pertenece a S.

Estas propiedades son fundamentales para la caracterización algebraica de los códigos

de bloque lineales. Supóngase que Vi y Vj son dos vectores de código pertenecientes a un
código de bloque binario. Se dice que el código es lineal si, y sólo si, (Vi  Vj) es también un
vector de código. Por lo tanto, un código de bloque lineal es aquel cuyos vectores,
pertenecientes al subespacio, no pueden crear vectores fuera dicho subespacio.

Por ejemplo, el espacio vectorial V4 queda completamente definido por las siguientes
24 = 16 4uplas:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

Un ejemplo de un subconjunto de V4 que forma un subespacio es:

0000 0101 1010 1111

Es fácil comprobar que la suma de dos vectores cualesquiera de este subespacio da

como resultado otro vector perteneciente a ese subespacio. Un conjunto de 2 k n-uplas se llama
código lineal de bloque si, y sólo si, es un subespacio del espacio vectorial Vn de todas las n-
uplas (2n). La Figura 8 trata de ilustrar este concepto. Podemos imaginar al espacio vectorial
Vn formado por 2n n-uplas (el total de puntos que se muestra en la figura). Dentro de este
espacio, existe un subconjunto de 2k n-uplas que forman un subespacio. Estos 2k vectores se
muestran como puntos más grandes y los llamamos vectores de código válidos. Un mensaje,
antes de ser transmitido, se codifica previamente en uno de los 2 k vectores de código válidos y
luego finalmente se transmite. Como consecuencia del ruido que hay en el canal de

14 11 Codificación de canal
comunicación, al receptor puede llegar una versión perturbada del código original. Ese vector
que llega al receptor es uno de los 2n vectores de la n-upla que forma el espacio Vn, y que
puede ser un punto grande o un punto chico de los que se muestran en la Figura 8. Si el
vector recibido es un punto chico, el receptor corrige el error eligiendo el punto grande más
cercano. Si el vector recibido está más cerca del punto grande original que de otro punto
grande, la corrección de error es exitosa. Si el vector recibido está más cerca de otro punto
grande distinto al que salió del transmisor, la corrección será fallida, aunque así es como esto
funciona. También será fallida la corrección si el vector recibido es un punto grande distinto al
transmitido. Si el sistema se diseña para detectar errores pero no para corregirlos, un error
será corregible siempre que se reciba un punto chico. No así cuando se reciba un punto
grande. La idea detrás de la elección de un código se puede establecer así:

1. Tratar de buscar un código eficiente extrayendo del espacio Vn la mayor cantidad

posible de vectores de código. Esto es equivalente a decir que se busca agregar la menor
cantidad de redundancia posible. Es decir, la diferencia entre n y k debería ser lo más pequeña
posible para no agregar mucho ancho de banda extra.

2. Buscar que los vectores de código estén lo más apartados posible uno de otro (es
decir, que sean lo menos parecido posible). Esto es para que cuando el código de vector sea
perturbado por el ruido se siga decodificando correctamente.

Figura 8. Estructura de un espacio vectorial.

Ejemplo de código de bloque lineal

Veamos la siguiente asignación de códigos, correspondiente a un esquema de

codificación (6, 3). Hay 2k = 23 = 8 vectores de mensaje y por lo tanto hay 8 vectores de
código. Hay 2n = 26 = 64 6-uplas en el espacio vectorial V6. Los vectores de mensaje y los
vectores de código se muestran ordenados en la tabla siguiente. Es fácil verificar que los ocho
vectores de código forman un subespacio de V6. Esto es, el vector nulo está presente y la
suma de dos vectores de código cualesquiera produce como resultado otro vector de código
que pertenece al subespacio. Por lo tanto, estos vectores de código representan un código de
bloque lineal, conforme a la definición.

11 Codificación de canal 15
 Vector de mensaje Vector de código
000 000000
100 110100
010 011010
110 101110
001 101001
101 011101
011 110011
111 000111

Matriz generadora

Si el valor de k es grande, armar una tabla como la vista en el ejemplo anterior

resultaría realmente muy complicado. Por ejemplo, para un código (127, 92) hay 292 vectores
de código distintos, esto es más o menos 5 x 1027. Si el procedimiento de codificación consiste
en una tabla entonces se necesitaría una cantidad de memoria extremadamente grande para
almacenar a todos los vectores de código. Para evitar esto, se recurre a una forma matemática
matricial para generar los vectores de código y para corregir o detectar los errores.

Dado que el conjunto de vectores de código es un subespacio de dimensión k del

espacio vectorial de dimensión n, siempre es posible encontrar un conjunto de n-uplas, menor
que 2k, que pueda generar todos los 2k vectores miembros del subespacio. El conjunto más
pequeño de vectores linealmente independientes que genera al subespacio se llama base del
subespacio y el número de vectores de esta base es la dimensión del subespacio. Cualquier
base formada por k n-uplas linealmente independientes, V1, V2, ..., Vk puede ser usada para
generar los vectores de código de bloque requeridos. Esto se debe a que cada vector de código
es una combinación lineal de V1, V2, ..., Vk. Esto es, cada vector de código U (de un total de
2k) puede ser escrito como:

U  m1V1  m2 V2    mk Vk (14)

donde mi = 0 o 1, son los dígitos de mensaje, con i desde 1 hasta k.

En general, podemos definir una matriz generadora mediante el siguiente arreglo de

k x n:

 V1  v11 v12  v1n 

V  v v 22  v 2n 

G   2    21 (15)
     
 
Vk  v k1 v k 2  v kn 

Por convención, los vectores de código se designan por vectores fila. Así, el mensaje m,
una secuencia de k bits de mensaje, es una matriz de 1 fila por k columnas:

m  m1 , m2 ,  , mk

La generación del vector de código se puede escribir en forma matricial de la siguiente

manera:

U  mG (16)

Para el ejemplo del código (6, 3) visto anteriormente, una matriz generadora posible
sería:

16 11 Codificación de canal
  V1  1 1 0 1 0 0
    (17)
G  V2   0 1 1 0 1 0
V3  1 0 1 0 0 1

donde V1, V2 y V3 son tres vectores linealmente independientes (un subconjunto de los
ocho vectores de código) que pueden generar todos los vectores de código. La independencia
lineal se comprueba viendo que la suma de dos cualesquiera de ellos no da como resultado a
ninguno de los tres vectores generadores. Para generar el vector de código correspondiente a,
por ejemplo, el vector de mensaje 1 1 0, se aplica entonces la siguiente ecuación:

 V1 
 
U  1 1 0  V2   1  V1  1  V2  0  V3
V3 

U  110100  011010  000000

 101110 (vector de código para el vector de mensaje1 1 0)

Por lo tanto, el vector de código correspondiente a un vector de mensaje es una

combinación lineal de las filas de G. Ya que los códigos quedan completamente definidos por G
el codificador sólo necesita almacenar las k filas de G en lugar todos los 2k vectores de código.
Nótese que, para el ejemplo visto es suficiente un arreglo de 3 x 6 en lugar de uno de 8 x 6.

Códigos de bloque lineales sistemáticos

Un código de bloque lineal sistemático (n, k) es un mapeo desde un vector de mensaje

k-dimensional a un vector de código n-dimensional, de tal manera que parte de la secuencia
generada coincide con los k dígitos del mensaje. Es decir, un código sistemático es aquel en el
que la secuencia de k bits del mensaje aparece explícitamente en el código. Los restantes
(n-k) dígitos son bits de paridad. Un código sistemático tiene una matriz generadora de la
siguiente forma:

G  P I k 
 p11 p12  p1(n  k ) 1 0  0
 
p21 p22  p2(n  k ) 0 1  0 (18)
 
   
 
 pk1 pk 2  pk (n  k ) 0 0  1

donde P se llama matriz de paridad (cada pij vale 0 o 1) e Ik es una matriz identidad de
dimensión k x k (tiene “unos” en su diagonal principal y “ceros” en el resto de las posiciones).
Con esta generación sistemática no es necesario almacenar en memoria la matriz identidad.
Combinando la (16) y la (18) cada vector de código se puede expresar como sigue:

 p11 p12  p1(n  k ) 1 0  0

 
p21 p22  p2(n  k ) 0 1  0
u1 , u2 ,  , un  m1 , m2 ,  , mk   
  
 
 pk1 pk 2  pk(n  k ) 0 0  1

donde

ui  m1 p1i  m2 p2i    mk pki parai  1,..., (n - k)

 mi  n  k parai  (n - k  1),...n

Dada la k-upla de mensaje

11 Codificación de canal 17
 m  m1, m2,, mk

y la n-upla general del vector de código

U  u1 , u2 , , un

entonces el vector de código sistemático puede expresarse como:

U  p1 , p2 ,  , pn  k ,m1 , m2 ,  , mk (19)
    
bits de paridad bits de mensaje

donde

p1  m1p11  m2 p21    mk pk1

p2  m1p12  m2 p22    mk pk 2 (20)
pnk  m1p1(nk )  m2 p2(nk )    mk pk(nk )

Aquí estamos poniendo los bits de paridad del lado izquierdo del vector de código y los
bits de mensajes del lado derecho. Sin embargo puede escribirse al revés y esto no tiene
efecto sobre las propiedades del código de detección o corrección de errores.

Nótese la característica de los códigos sistemáticos. Los bits de paridad se forman

como combinación lineal de los bits de mensaje. Por eso tienen particular interés. La
matriz identidad se puede obviar del codificador ya que los bits de paridad pi se generan
solamente con la matriz de paridad P. Luego, el vector U se forma con los bits de mensaje (en
forma directa, sin ninguna operación matemática), más los bits de paridad generados con P
que se adjuntan a los bits de mensaje.

De acuerdo a lo que acabamos de ver, para el código (6, 3) del ejemplo visto antes, el
vector de código puede escribirse así:

1 1 0 1 0 0
 
U  m1 , m2 , m3   0 1 1 0 1 0 (21)
1 0 1 0 0 1
 
P I3

U  m1  m3,m1  m2,m2  m3,m1,m2 ,m3 (22)

   
u1 u2 u3 u4 u5 u6

Se puede ver que los bits redundantes se forman de diferentes maneras. El primer bit
de paridad es la suma del primer y tercer bit de mensaje; el segundo bit de paridad es la suma
del primero y segundo bit de mensaje y el tercer bit de paridad es la suma del segundo y
tercer bit de mensaje. Una estructura de este tipo, comparada con los esquemas de un solo bit
de paridad, provee mayor capacidad para detectar y corregir errores.

Matriz de verificación de paridad

Para poder realizar el proceso inverso en el receptor, es decir, para poder decodificar el
vector de código recibido, definimos una matriz H a la que llamamos matriz de verificación de
paridad. Por cada matriz generadora G de dimensión (k x n) existe una matriz H de dimensión
(n – k) x n de tal manera que las filas de G son ortogonales a las filas de H. Esto significa que
GHT = 0, donde HT es la matriz transpuesta de H, y 0 es una matriz nula de dimensión
k x (n – k). La matriz transpuesta de H es de dimensión n x (n – k), cuyas filas son las
columnas de H y cuyas columnas son las filas de H. Para cumplir con los requerimientos de
ortogonalidad la matriz H se escribe como:

18 11 Codificación de canal
 
H  In  k PT  (23)

Por lo tanto, la matriz transpuesta de H es

I 
HT   n  k 
 P 
 1 0  0 
 
 0 1  0 
  
  (24)
 0 0  1 

p p12  p1(n  k ) 
 11 
 p21 p22  p2(n  k ) 
  
 
 pk1 pk 2  pk (n  k ) 

Se puede ver que GHT = 0:

I 
GHT  P I k    n  k 
 P  (25)
PP

Como P + P es la suma en módulo 2 de dos matrices resulta P + P = 0.

También se puede verificar que el producto UHT da cero:

UHT  (mG)  HT
 m  (GHT )
 m0
0

Teniendo la matriz H de verificación de paridad se la puede usar para verificar si el

vector de código recibido es un código válido del conjunto de vectores. U es un código de
vector generado por la matriz G (o sea, un código válido) si, y sólo si, UHT = 0.

Test de síndrome

Supongamos que el vector que estamos recibiendo no es igual al vector transmitido ya

que ha sido perturbado por el ruido. Digamos entonces que el vector recibido es r = r1,
r2,...,rn. Por lo tanto, hay 2k vectores U posibles, mientras que hay 2n vectores r posibles.
Podemos escribir:

r Ue (26)

donde e = e1, e2,...,en es el vector de error o patrón de error introducido por el canal.
Hay un total de 2n-1 potenciales patrones de error (el vector e = 0 no produce error) en el
espacio de 2n n-uplas. Se define síndrome de r:

S  rHT (27)

El síndrome es el resultado de una verificación o comprobación de la paridad hecha

sobre el vector r para determinar si r es un miembro del conjunto de vectores de código (o
sea, un vector válido). Si r es miembro entonces el síndrome S tiene valor 0. Si r tiene errores

11 Codificación de canal 19
detectables entonces el síndrome tiene algún cierto valor distinto de cero. Si r tiene errores
corregibles entonces el síndrome tiene algún valor distinto de cero que puede ser asociado al
patrón de error que causó el error. El decodificador tomará acciones para detectar y corregir el
error (en el caso de un FEC) o bien solicitará una retransmisión (en el caso de un ARQ).
Combinando la (26) y la (27) se obtiene:

S  (U  e)  HT
(28)
 UHT  eHT

Y como UHT = 0 entonces resulta

S  eHT (29)

Nótese que el síndrome puede ser calculado tanto con el vector recibido r como con el
patrón de error e. Una propiedad importante de los códigos lineales de bloque, fundamental
para el proceso de decodificación, es que el proceso de mapeo entre los patrones de error
corregibles y el síndrome es uno a uno.

Ejemplo 4. Test de síndrome.

Supóngase que se transmite el vector de código U = 101110 del ejemplo de código (6,
3) visto antes, y se recibe el vector r = 001110, es decir, se produce un error en el bit del
extremo izquierdo. Calcular el valor del síndrome S = rHT y verificar que es igual a eHT.

Solución.

S  rHT
1 0 0
 
0 1 0
0 0 1
 0 0 1 1 1 0   
1 1 0
0 1 1
 
1 0 1
 1, 1  1, 1  1  1 0 0 (sindrome del vector de código perturbado)

Calculando el síndrome por el otro camino resulta:

S  eHT  1 0 0 0 0 0  HT  1 0 0

Las propiedades del síndrome las podemos resumir como sigue:

1. El síndrome depende sólo del patrón de error y no de la palabra de código

transmitida.

2. Dos patrones de error que difieren entre sí por una palabra de código válida tienen
el mismo síndrome.

3. El síndrome S es la suma de aquellas filas de la matriz HT correspondientes a las

ubicaciones del error.

4. Usando decodificación con síndrome, un código lineal de bloque (n, k) puede

corregir hasta t errores por palabra de código, siempre que n y k satisfagan el siguiente límite
de Hamming:

20 11 Codificación de canal
 t
 n
2n  k    i 
i 0
(30)

Si la (30) se cumple con el signo igual, se dice que el código es perfecto.

Corrección de error

En virtud de lo visto hasta acá, está claro que no sólo es posible detectar un error sino
que también es posible corregirlo. Esto se debe a que se tiene la capacidad de conocer el
patrón de error a partir del cálculo del síndrome. Escribamos las 2 n n-uplas que representan
todos los posibles vectores recibidos en un arreglo tal que la primera fila contenga todos los
vectores de código válidos, comenzando por el vector nulo, y la primera columna contenga
todos los esquemas o patrones de error corregibles. Cada fila, llamada coset, consiste en un
patrón de error en la primera columna (llamado coset líder) seguido por los vectores de código
válidos perturbados por ese coset líder. Este arreglo (llamado arreglo estándar), para un
código (n, k) se escribe de la siguiente manera:

U1 U2  Ui  U2 k
e2 U2  e 2  Ui  e2  U2k  e 2
e3 U2  e 3  Ui  e3  U2k  e 3
  (31)
ej U2  e j  Ui  e j  U2k  e j
  
e 2n  k U2  e 2n  k  U i  e 2n  k  U2k  e 2 n  k

El arreglo contiene todas las 2n n-uplas del espacio Vn (cada n-upla aparece sólo una
vez). Cada coset consiste de 2k n-uplas. Por lo tanto hay (2n/2k) = 2n-k cosets. Supóngase que
se transmite el vector Ui sobre un canal con ruido. Si el patrón que causa el error es un coset
líder, el vector recibido será decodificado correctamente. Si el patrón de error que causa la
perturbación no es un coset líder entonces se producirá una decodificación errónea.

Si ej es el coset líder o patrón de error del j-ésimo coset, entonces Ui + ej es una n-upla
que pertenece a este coset o fila del arreglo estándar. El síndrome de esta n-upla es:

S  (U i  e j )  HT  U i HT  e j HT

Ya que Ui es un vector de código válido resulta ser que UiHT = 0, y por lo tanto se
puede escribir:

S  (U i  e j )  HT  e j HT (32)

De esta última ecuación se puede ver que todos los miembros de un coset tienen el
mismo síndrome y por eso el síndrome es usado para estimar el patrón de error. El síndrome
para cada coset es diferente.

El proceso para la corrección de errores es el siguiente:

1. Calcular el síndrome de r usando S = rHT.

2. Localizar el patrón de error, ej, que tiene el mismo síndrome que el calculado en 1,
y cuyo valor es igual a rHT.

3. Este patrón de error se lo toma como el que causa la perturbación en el canal.

11 Codificación de canal 21
 4. El vector recibido corregido se calcula como U = r + ej. La suma es consecuencia de
las reglas de operación en módulo 2 (sumar o restar es lo mismo).

Localización del patrón de error

Volviendo al ejemplo de código (6, 3) visto al comienzo, ubicaremos ahora las 2 6 = 64

6-uplas de acuerdo al arreglo estándar que se muestra en la matriz (31):

000000 110100 011010 101110 101001 011101 110011 000111

000001 110101 011011 101111 101000 011100 110010 000110
000010 110110 011000 101100 101011 011111 110001 000101
000100 110000 011110 101010 101101 011001 110111 000011
001000 111100 010010 100110 100001 010101 111011 001111
010000 100100 001010 111110 111001 001101 100011 010111
100000 010100 111010 001110 001001 111101 010011 100111
010001 100101 001011 111111 111000 001100 100010 010110

Usando la (30) se puede verificar que este código corrige todos los errores simples. Los
vectores de código válidos son los ocho vectores de la primera fila, y los patrones de error
corregibles son los ocho vectores líderes de la primera columna (incluyendo el patrón de error
nulo). Todos los patrones de error de 1 bit son corregibles. Nótese que luego de ubicar todos
los patrones de error de 1 bit queda todavía algún patrón más ya que no se ha completado la
64 6-upla. Es decir, queda un coset libre (con un coset líder asociado) que puede ser
completado y por lo tanto hay un patrón de error más que puede ser corregido. Al respecto,
contamos con flexibilidad para elegir este patrón de manera tal de completar la n-upla en el
último del coset, sin que se repitan las 6uplas. En la tabla anterior, este patrón líder se eligió
como 010001. La decodificación será correcta si, y sólo si, el patrón de error causado por el
canal es uno de los patrones líderes.

Calculamos ahora el síndrome correspondiente a cada una de las secuencias erróneas

corregibles por medio del producto ejHT, para cada patrón líder:

1 0 0
 
0 1 0
0 0 1
S  ej   
1 1 0
0 1 1
 
1 0 1

Los resultados se muestran en la tabla siguiente. Ya que cada síndrome es único, el

decodificador puede identificar el patrón de error e al cual corresponde.

Patrón de error síndrome

000000 000
000001 101
000010 011
000100 110
001000 001
010000 010
100000 100
010001 111

22 11 Codificación de canal
 Como se dijo ya anteriormente, se recibe un vector r y se calcula su síndrome usando
la ecuación S = rHT. Luego se usa ese síndrome en la tabla anterior para encontrar el
correspondiente patrón de error. Este patrón de error es una estimación del error y se denota
como ê. Finalmente, el decodificador suma ê a r para obtener una estimación del vector
transmitido, al que lo identificará por Û.

ˆ re
U ˆ  (U  e)  e
ˆ  U  (e  e
ˆ) (33)

Si el patrón de error estimado es igual al patrón real, o sea, si ê = e entonces Û = U.

Por el contrario, si el error estimado es incorrecto entonces el decodificador estimará un vector
de código que en realidad no fue transmitido y en tal caso se producirá un error indetectable.

Ejemplo 5. Supongamos que se transmite U = 101110 y que el vector recibido es

r = 001110. Mostrar cómo el decodificador, usando la tabla de síndrome anterior, puede
corregir el error.

Solución.

El síndrome r se calcula como:

S  0 0 1 1 1 0  HT  1 0 0

Usando la tabla de la página anterior, el patrón de error estimado corresponde a:

ˆ 1 0 0 0 0 0
e

El vector corregido, estimado, es

ˆ re
U ˆ
 0 0 1 1 1 01 0 0 0 0 0
1 0 1 1 1 0

Ya que el patrón de error estimado es igual al patrón de error verdadero el

procedimiento para este ejemplo conduce a Û = U.

Peso y distancia de vectores binarios

La capacidad de corrección de error de un sistema puede ser analizada investigando su

estructura. El peso de Hamming, w(U), de un vector U queda definido como el número de
elementos distintos de cero en U. Ya que U es un vector con elementos binarios, el peso de
Hamming de U es igual al número de “1” que tiene el vector. Por ejemplo, si U = 100101101,
entonces w(U) = 5. La distancia de Hamming entre dos vectores U y V, d(U, V), queda
definida como el número de elementos diferentes entre ambos vectores. Por ejemplo,

U = 100101101

V = 011110100

d(U, V) = 6

Debido a las propiedades de la suma en módulo 2, si sumamos U y V obtenemos:

U + V = 111011001

Por lo tanto, se puede ver que la distancia de Hamming entre dos vectores es el peso
de Hamming de la suma (o resta) de ambos. Esta propiedad es útil para hallar la distancia

11 Codificación de canal 23
mínima entre dos vectores del conjunto de palabras de código válidas. Como la suma de dos
vectores de código da como resultado otro vector de código perteneciente al subespacio, la
distancia mínima viene dada por aquel vector de código del subespacio que tiene la menor
cantidad de “1” (sin considerar el vector nulo). Esto nos libera de calcular la distancia entre
cada uno de los pares posibles de vectores de código. La distancia entre vectores de código
nos da una pauta de qué tan separados están entre sí. En particular, la distancia mínima dmin
nos da el peor caso o “peor separación”. Con esto podemos determinar la capacidad de
corrección o detección de errores que tiene el código.

Una vez que se recibe el vector r, la tarea del decodificador es estimar cuál fue el
vector U transmitido. La estrategia es entonces buscar aquel vector U que presente la menor
distancia respecto del vector r recibido.

En la Figura 9 se muestra la distancia de Hamming entre dos vectores, U y V. Los

puntos negros entre ambos representan casos posibles de vectores recibidos r. En la
Figura 9(a) se muestra un vector recibido r1 que tiene distancia 1 respecto del vector U y
distancia 4 respecto del vector V. Si el detector está diseñado para corregir errores entonces
optará por el vector U que es el más cercano a r1. Si r1 fue el resultado de haber recibido
realmente el vector de código U con un bit erróneo, entonces la decodificación es correcta.
Pero, si r1 fue el resultado de haber recibido el vector de código V con cuatro bits erróneos
entonces la decodificación es incorrecta. Una interpretación similar puede hacerse para el
ejemplo (b) de la Figura 9, en donde un doble error en la transmisión de U permite una
decodificación correcta, pero si se trata de un triple error en la transmisión de V entonces la
decodificación es incorrecta ya que el detector toma una decisión errónea. Finalmente, en el
ejemplo (c), si el vector transmitido fue U y se producen tres errores, entonces el detector se
equivocará en la detección, ya que optará por estimar V que es el vector más cercano. Si r3
fue la consecuencia de haber recibido el vector de código V con dos errores entonces la
detección será correcta.

Figura 9. Corrección y detección de errores en función de la distancia

de Hamming.

24 11 Codificación de canal
 Si la tarea del receptor es detectar errores y no corregirlos, se puede ver en la
Figura 9 que cualquier vector recibido afectado por el ruido, representado por un punto negro
y que implica 1, 2, 3 o 4 bits erróneos, puede ser detectado. Sin embargo, si se producen 5
errores en la transmisión y el vector transmitido fue U, el detector recibirá V, con lo cual no
podrá detectar los errores (similarmente ocurre si se transmitió V y se producen 5 errores).

Del análisis hecho anteriormente podemos ver que la capacidad que tiene un
determinado código para detectar y/o corregir errores está relacionada con la distancia mínima
entre dos vectores de código. La tarea del detector, para el caso de corrección de errores, es
determinar en qué región está el vector recibido para tomar una decisión, como se muestra en
la Figura 9(a). Si el vector recibido “cae” en la región 1 el criterio es decidir por U. Si “cae” en
la región 2 el criterio es optar por el vector V. Con tal criterio, y con una distancia dmin = 5
como se muestra en el ejemplo, el detector puede corregir hasta 2 errores. En general el
máximo número garantizado de errores corregibles por palabra de código, t, viene dado por
la expresión:

d  1
t   min  (34)
 2 

donde x representa la parte entera de x. Tiene que quedar claro que la (34) nos dice
que el código puede corregir hasta t errores inclusive. Sin embargo, muchas veces un código
que corrige todas las secuencias posibles de hasta t errores puede también corregir ciertas
secuencias de t + 1 errores. Cuando vimos el ejemplo de código (6, 3) comprobamos que
quedaba una fila sin completar en el arreglo estándar, luego de haber puesto todos los
patrones de 1 error. En general, un código lineal de bloque (n, k) que con seguridad puede
corregir hasta t errores, es capaz de corregir un total de 2n-k patrones de error.

Un código de bloque que con seguridad corrige hasta t errores, tiene una probabilidad
de hacer una detección errónea Pe de la palabra de código, que viene dada por la siguiente
desigualdad:

n
 n
Pe      p j  1  pn  j
j
j  t 1  
(35)

donde p es la probabilidad de transición del CSB. La igualdad en la (35) se produce

cuando el código es perfecto, es decir cuando el código corrige solamente hasta t errores y ni
uno más.

Un código también puede usarse para detectar errores solamente. En la Figura 9 vemos
que cualquier vector recibido caracterizado por un punto negro puede ser identificado como un
error. La capacidad de detectar e errores, viene dada por la distancia mínima de la siguiente
manera:

e  dmin  1 (36)

Un código de bloque con distancia mínima dmin garantiza que todos los patrones con
(dmin – 1) errores, o menos, pueden ser detectados, lo cual no significa que no puedan
detectarse algunos patrones de error más. Del arreglo estándar puede verse que un código (n,
k) puede detectar un total de (2n – 2k) patrones de error diferentes.

Designemos con Aj al número de vectores de código con peso j. Los números A0, A1,
A2,...An forman la distribución de pesos del código. Si el código se usa sólo para detección de
errores sobre un CSB, entonces la probabilidad de que el código no detecte un error en un
vector de código viene dada por la expresión:

11 Codificación de canal 25
 n
Pnd  A p
j 1
j
j
1  pn  j (37)

donde, una vez más, p es la probabilidad de transición del canal. Ya que el código tiene
una distancia mínima dmin, resulta que los valores de A1 hasta Admin – 1 son todos cero. Por lo
tanto, la (37) se puede rescribir como:

n
Pnd  A p
j  d min
j
j
1  pn  j (38)

Este resultado surge de considerar que para que un error no sea detectado, el patrón
de error debe ser igual a un vector de código válido, puesto que generará otro vector de
código válido y consecuentemente el detector lo considerará como un vector de código sin
error. Lo que hace la (37) o (38) es considerar de cuántas maneras pueden generarse vectores
de código válidos.

Resumen

La codificación de canal es un proceso cuyo objetivo es reducir la probabilidad de error

de bit en sistema de comunicación digital. Puede hacerse sobre la señalización utilizada para
transmitir la señal (NRZ, RZ, FSK, PSK, etc.), en donde cada una presenta una probabilidad de
error de bit para un cierto valor de energía de bit. La otra manera de hacerlo, como se estudió
en el presente capítulo, es manipulando bloques de bits. Esto se logra agregando bits de
redundancia a los bits de mensaje que salen de la fuente de información, de tal manera que
sean usados en el receptor para corregir errores de bit o detectar errores de bit. Estos errores
son consecuencia de una detección errónea de la señal a causa del ruido presente en el canal.
En el caso de la detección de errores, el receptor debe informar al transmisor que el mensaje
debe ser retransmitido.

Shannon determinó los límites que determinan si la probabilidad de error de bit se

puede hacer tan pequeña como se desee, en función de la tasa de información de la fuente y
de la capacidad de canal. Si la tasa de información es menor o igual que la rapidez con la que
se usa el canal, entonces es posible obtener un código de corrección de error que dé como
resultado una probabilidad de error de bit tan pequeña como se desee. Sin embargo, este
teorema de Shannon, llamado de codificación de canal, no dice cómo obtener tal resultado.

El agregado de bits de redundancia obliga a achicar los tiempos de bit, por lo que el
costo para obtener el beneficio de corrección o detección de error es un aumento del ancho de
banda ocupado. Incluso puede ocurrir que el perjuicio causado por la reducción de la energía
de bit al agregar bits de redundancia (es decir, el aumento de la probabilidad de transición de
canal), sea mayor que el beneficio aportado por el corrector o detector de errores, por lo que
en ciertas condiciones de bajo valor de Eb/N0 la PB puede empeorar en vez de mejorar.

La generación de los bits de redundancia se hace a través de una operación matemática

matricial, entre un vector de mensaje y una matriz generadora. Si el vector generado es
diseñado de tal manera que los bits de mensaje aparezcan explícitamente en él, se dice que el
código es sistemático. En el receptor también se hace una operación matricial, obteniéndose
como resultado un vector de síndrome mediante el cual se detectan o corrigen los errores. La
capacidad de detectar o corregir errores que tiene un determinado código depende de la
distancia entre los vectores de código generados, llamada distancia de Hamming. A mayor
distancia, mayor capacidad tiene el código.

26 11 Codificación de canal