Clasificación de códigos de canal

1. Códigos detectores de error

Es una serie de códigos cuya principal característica es que permiten detectar si se ha
producido o no error en la transmisión de la palabra de código. Aunque en caso de
producirse no son capaces de su corrección inmediata, su detección evita el uso de
información incorrecta. El error se soluciona repitiendo la transmisión hasta que éste
desaparezca. La ventaja de esta metodología es inmediata: el mensaje sólo se repite en caso
de error.
Por ejemplo:
Queremos transmitir dígitos decimales para lo que usamos el código BCD natural. En este
no se emplean más que 10 de las 16 combinaciones posibles con 4 dígitos binarios.
Supongamos que se emite la combinación 0011 y tras producirse error en un dígito binario
durante la transmisión se recibe la 1011; como no pertenece al código utilizado es inmediato
deducir que nunca ha podido ser transmitida, por lo que el error será detectado
Sin embargo, esta condición es necesaria pero no suficiente. Veámoslo con un
contraejemplo:
Retomemos el ejemplo anterior y supongamos ahora que al transmitir la combinación 0011
se produce el error en el primer dígito, recibiendo la 0010. Como también pertenece al
código el centro receptor la considerará correcta, identificando, erróneamente, al dígito
decimal 2 como el mensaje emitido.
De lo expuesto es fácil de deducir intuitivamente que la condición necesaria y suficiente
para poder detectar error en un dígito binario es que toda combinación del código se
transforme, al variar uno cualquiera de sus dígitos, en una combinación que no pertenezca
al código.
En la Figura 1 se puede observar gráficamente la condición expuesta.

Figura 1. Los círculos sombreados representan combinaciones pertenecientes

al código y los blancos combinaciones no pertenecientes al código. Las flechas
negras indican transmisiones libres de error, mientras que con las grises se
señalan las transmisiones con error en un dígito.
Los códigos que cumplen esta condición son aquellos cuya distancia mínima es mayor o
igual a 2. Relacionando ambas afirmaciones se puede concluir que la condición necesaria y
suficiente para que un código sea detector de error en un dígito binario es que su distancia
mínima sea, como mínimo, dos.
Generalizando el razonamiento anterior se puede afirmar que la condición necesaria y
suficiente para que un código permita detectar el error producido por la variación de un
número de dígitos igual o menor que k durante la transmisión de la palabra de código, es
que su distancia mínima sea, al menos, k+1. Gráficamente se puede ver en la Figura 2.

Figura 2. La simbología es la misma que en la figura anterior, sólo se añade, en las

flechas grises, el número de dígitos que varían en la transmisión. Se puede ver como
el código detector de k errores lo será también de un número de errores inferior a k.

De los múltiples códigos detectores de error cabe destacar, de entre los detectores de un
solo error, a los de paridad y a los de peso constante.
1.1.- Códigos de paridad
Concepto de paridad: Se dice que una combinación binaria tiene paridad par si el número
de unos de esa combinación es par. De igual forma se dice que una combinación tiene
paridad impar si su número de unos es impar.
Síntesis del código
Un código de paridad se obtiene añadiendo a las palabras de un código de distancia mínima
uno, un dígito que se denomina de paridad. Si el código que se desea obtener es de paridad
par, este dígito debe adquirir un valor tal que la paridad de cada combinación sea par. Igual
criterio se aplica si el código deseado es de paridad impar.
Ejemplo
Vamos a crear un código de paridad para los dígitos decimales a partir del código BCD
natural
Para verificar que los códigos de paridad son detectores de error en un dígito binario basta
con probar que su distancia mínima es dos, para lo que se demostrarán las siguientes dos
proposiciones:
a) Un código de paridad par posee una distancia mínima estrictamente mayor que uno.
Razonamos por reducción al absurdo. Supóngase que existen dos combinaciones b k
bk-1 ... b1 b0 y ak ak-1 ... a1 a0, con una distancia entre ellas de uno. Esto implica que existe
un bit, por ejemplo, el j-ésimo, que hace que:

bi = ai ∀ i ∈ [0, k] /i ≠ j
𝑏̅𝑗 = aj

De aquí se infiere que si la primera combinación posee m 1´s, la segunda tiene m+1 ó
m-1. En cualquier caso, si m es par m+1 ó m-1 son números impares, con los cual la
segunda combinación no pertenecería al código. Este razonamiento lleva a un absurdo,
con lo que queda demostrada la proposición.

b) En un código de paridad par existen siempre dos combinaciones que distan dos
unidades. Como el código de partida es de distancia mínima uno, existirán al menos dos
subcombinaciones bk-1 ... b1 b0 y ak-1 ... a1 a0, en las que solamente un índice j hace que:

bi = ai ∀ i ∈ [0, k] / i ≠ j
𝑏̅𝑗 = aj

Si la primera combinación posee m 1´s, la segunda tendrá m+1 ó m-1. Supóngase que
m es par. Entonces los respectivos bits de paridad serán b k=0 y ak=1. Si m fuera impar
los bits de paridad serían bk=1 y ak=0. En cualquier caso, se cumple que 𝑏̅𝑘 = ak. Por lo
tanto, la distancia de estas dos combinaciones resultante es dos ( 𝑏̅𝑘 = ak y 𝑏̅𝑗 =aj). En
esta demostración se ha trabajado con códigos de paridad par. El razonamiento es el
mismo si fuese de paridad impar.
 Análisis del código

Para detectar si existe o no error en la palabra de código recibida, se comprueba si ésta

cumple el criterio de paridad preestablecido, si es así se supondrá que no ha existido
error en la transmisión, si no es así es que algún dígito ha variado de valor, no podemos
saber cuál es, pero sí que ha existido error.
Ejemplo
Supongamos que el criterio de paridad del código usado es par. Entonces si se recibe:

10001 su paridad es par ⇒ será correcta.

10000 su paridad es impar ⇒ será incorrecta.
01110 su paridad es impar ⇒ será incorrecta.
01100 su paridad es par ⇒ será correcta.

Como comentario final se puede añadir que, por la forma de operar de estos códigos,
permitirán la detección de error siempre que el número de dígitos binarios que varíen
sea impar.

1.2.- Códigos de peso constante

Se denomina peso de una combinación binaria al número de unos que posee. Entonces, los
códigos de peso constante serán aquellos cuyas combinaciones tienen siempre la misma
cantidad de unos.
Entre estos códigos de peso constante se encuentran los BCD 2 entre 5 y biquinario o 2
entre 7, que es, además ponderado:

Se puede comprobar que estos códigos poseen una distancia mínima de dos. El error se
detecta cuando la combinación recibida tenga un número de unos distintos al peso del
código usado.
Se puede añadir el mismo comentario que a los de paridad.
1.3.- Códigos de redundancia cíclica

Los CRC (Códigos de Redundancia Cíclica), también llamados códigos polinómicos,

constituyen el método de detección de errores más empleado en comunicaciones. Su uso
está muy extendido porque pueden implementarse en hardware con mucha facilidad. Estos
códigos se basan en el uso de un polinomio generador G(X) de grado r, y en el principio de
que n bits de datos binarios se pueden considerar como los coeficientes de un polinomio
de orden n-1. Por ejemplo, los datos 10111 pueden tratarse como el polinomio x4 + x2 + x1
+ x0.

A estos bits de datos se añaden r bits de redundancia de forma que el polinomio resultante
sea divisible por el polinomio generador, sin generar resto. El receptor verificará si el
polinomio recibido es divisible por G(X). Si no lo es, habrá un error en la transmisión.

Ejemplo
El emisor quiere enviar la trama 110101 siendo r = 3 y G = 1001. Entonces, M 2r = 110101000
que dividido (división de módulo 2) entre G produciría R = 011

En el receptor se recibirá T' y procederá a dividirlo entre G

Utilizando CRCs no es posible saber, en caso de error, cuántos errores se han cometido ni
qué bits contienen errores

2. Códigos correctores de error

Estos códigos permiten, además de detectar el error, corregirle sin necesidad de repetir la
transmisión. De forma general, se puede decir que la técnica empleada para la corrección
consiste en identificar como combinación correcta, a la perteneciente al código que sea más
cercana a la errónea recibida, o sea, aquella cuya distancia de la combinación incorrecta sea
menor. Veamos, al igual que antes, las propiedades de estos códigos partiendo del caso más
sencillo:

Figura 3. Se utiliza la misma simbología que en figuras anteriores.

Conviene fijarse como un código corrector de orden 1 sólo corrige
correctamente si hay un error en la transmisión. Esta afirmación es
extrapolable a códigos correctores de cualquier orden.

códigos capaces de corregir el error cometido al variar un dígito binario. Puesto que se ha
de detectar el error, no deben de usarse todas las combinaciones posibles (como se vio en
la pregunta anterior), pero, además, como el proceso de corrección ha de ser no ambiguo,
sólo debe de haber una posible combinación del código que diste una unidad de cada
combinación no usada. En la Figura 3 se puede observar esquemáticamente el proceso de
corrección. Se puede concluir, que la condición necesaria y suficiente para que un código
sea corrector de orden uno (corrija correctamente errores producidos al variar un dígito en
la transmisión) es que su distancia mínima sea tres. Veamos un ejemplo que ilustra lo
expuesto:
Ejemplo
Queremos transmitir dos mensajes A y B. Si la distancia mínima del código usado es menos
que tres, es imposible una corrección no ambigua:
código I:
A.........00
B.........11
Supongamos que usando este código se recibe la combinación 01, evidentemente ha
existido un error, y suponiendo que ha sido en un solo dígito es imposible discernir si la
combinación enviada ha sido la 00 o la 11 ya que ambas distan una unidad de la recibida.
Creemos ahora un código de distancia mínima tres:
código II:
A..........000
B..........111
Las entradas y salidas del canal serían (suponiendo que no puede haber más de un error en
la transmisión de cada combinación):

Es inmediato ver como en el proceso de corrección no existe ninguna ambigüedad:

Aunque la restricción de que no existe más de un error en la transmisión de cada
combinación es aplicable en numerosos canales reales, es conveniente generalizar el
proceso de corrección a un orden k: Si durante la transmisión de una combinación varían
un número de dígitos igual o inferior a k, se recibirá una combinación no perteneciente al
código; para que este error pueda ser corregido, debe de cumplirse que la combinación
emitida sea la única perteneciente al código cuya distancia de la recibida sea igual o inferior
a k. Generalizando el razonamiento a cualquier combinación transmitida se puede concluir
que la condición necesaria y suficiente para que un código sea corrector de orden k es que
su distancia mínima sea de 2k+1; sólo en este caso el proceso de corrección será no
ambiguo. En la Figura 4 se puede observar una esquematización gráfica del proceso de
corrección de orden k que puede ayudar a la comprensión de lo anteriormente expuesto.

Figura 4. Representación simbólica de un proceso de corrección de k errores

De los posibles códigos correctores de errores vamos a ver únicamente los denominados
códigos de Hamming.
2.1.- Código de Hamming
Con este nombre se conoce a un conjunto de códigos correctores en k dígitos binarios. En
esta lección solamente se tratará el de orden uno: k=1.
A la hora de trabajar con este tipo de códigos podemos distinguir dos operaciones:
a) Construcción, que se realizará en el centro emisor.
b) Interpretación, que se realizará en el centro receptor.
a) Construcción. Se parte de un código de n dígitos de distancia mínima uno. Estos n dígitos
son conocidos dentro del código de Hamming como "dígitos de datos". A continuación, se
le añaden p (cp-1, ..., c2, c1, c0) dígitos denominados de control o paridad. Así pues, el nuevo
código tendrá una longitud de palabra de l=n+p. La numeración de los dígitos es la habitual
(de derecha a izquierda) pero comenzando por uno: dn+p dn+p-1 ... d2 d1.
Cada uno de estos p dígitos que añadimos al código original va a afectar a unas
determinadas posiciones de la nueva palabra de código de n+p dígitos, de forma que
tomaran el valor adecuado para que se cumpla el criterio de paridad (par o impar)
preestablecido en las subcombinaciones afectadas por cada uno. Se tiene, entonces, que
en la construcción del código los p dígitos añadidos actúan como dígitos de paridad.
b) Interpretación. Recibida una combinación de un código de Hamming hay que comprobar
si es correcta, y de no ser así habrá que detectar el dígito que varió en la transmisión.
Ahora los p dígitos añadidos actúan como dígitos de control y con ellos formamos una
palabra binaria. Cada uno de los dígitos de esta palabra toma el valor 0 ó 1 dependiendo
de si el número de unos de las posiciones de la palabra de código por el afectadas cumplen
o no el criterio de paridad establecido. Interpretando la combinación resultante en binario
natural, tendremos dos posibilidades:
- Que se corresponda con el 0. Entonces quiere decir que la transmisión ha sido correcta.
- Que se corresponda a un número distinto del 0. Entonces en la transmisión ha variado el
dígito situado en la posición indicada por ese número.
Quedan varias cuestiones por resolver:
I.- Cómo calcular p.
II.- A que posiciones afecta cada uno de los p dígitos de control o paridad.
III.- Dónde se colocan estos dígitos dentro de la palabra de código.
I.- Dada la forma de calcular la posición errónea, con p dígitos binarios se tiene que poder
detectar el error en todas y cada una de la n+p posiciones de la palabra de código. Como la
combinación formada por los p dígitos de control se interpreta en binario natural, se debe
cumplir que:
2p - 1 ≥ n + p
Donde 2p -1 es el mayor número que se puede representar en binario natural con p dígitos.
II.- Construyamos todas las combinaciones posibles con p dígitos de control, e
interpretemos cada una en binario natural:

Cada dígito de control ha de afectar a aquellas posiciones en las que sea capaz de detectar
error, o sea, va a afectar a las posiciones de la tabla anterior para las que ese dígito valga
1:
III.- Han de colocarse en aquellas posiciones en las que no se vean afectados por otro dígito
de control, así no existirán ambigüedades a la hora de otorgarles valor en la creación del
código. Estas posiciones han de ser entonces:

Veamos un ejemplo de creación e interpretación de un código de Hamming de paridad par:

Ejemplo: Partimos del código binario natural de 4 bits.

a) Creación. Dividimos el proceso en una secuencia lógica de pasos:

1.- Cálculo del número de dígitos de control necesarios:

2p - 1 ≥ n+p
⇒ 2p ≥ 5 + p ⇒ p = 3
n=4
La palabra de código tendrá, entonces, una longitud l=4+3=7 dígitos: d7d6d5...d1. Para
identificar los dígitos de control les denominamos c2, c1 y c0.
2.- Hallamos las posiciones de la palabra de código afectadas por cada dígito de control.

Los controles de paridad se efectúan sobre las siguientes subcombinaciones:

3.- Cada dígito de control estará situado en las siguientes posiciones de la palabra de
código:
co .- d1 c1 .- d2 c2 .- d4
4.- Construcción del código de Hamming:

b) Interpretación. Analicemos todos los casos posibles de error en un bit.

1.- Alteración de un bit de datos:

- Control de paridad de c0 → d7 d5 d3 d1; 3 unos → impar ⇒ c0 = 1.

- Control de paridad de c1 → d7 d6 d3 d2; 3 unos → impar ⇒ c1 = 1.
- Control de paridad de c2 → d7 d6 d5 d4; 3 unos → impar ⇒ c2 = 1.
El bit erróneo es: c2 c1 c0 = 1 1 1(2) = 7
2.- Alteración de un bit de control:

- Control de paridad de c0 → d7 d5 d3 d1; 2 unos → impar ⇒ c0 = 0.

- Control de paridad de c1 → d7 d6 d3 d2; 2 unos → impar ⇒ c1 = 0.
- Control de paridad de c2 → d7 d6 d5 d4; 3 unos → impar ⇒ c2 = 1.
El bit erróneo es: c2 c1 c0 = 1 0 0(2) = 4
3.- No hay alteración:

- Control de paridad de c0 → d7 d5 d3 d1; 2 unos → impar ⇒ c0 = 0.

- Control de paridad de c1 → d7 d6 d3 d2; 2 unos → impar ⇒ c1 = 0.
- Control de paridad de c2 → d7 d6 d5 d4; 2 unos → impar ⇒ c2 = 0.
Como c2 c1 c0 = 0 0 0(2) = 0, entonces no existe error en la combinación recibida.
http://bibing.us.es/proyectos/abreproy/11199/fichero/Volumen+I%252FAPENDICE+B.
pdf
https://www.infor.uva.es/~cevp/FI_I/fichs_pdf_teo/FI_I_Tema8_CodCorr.pdf