Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » 10. Codificación de Canal: Código Hamming y Código Convolucional

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

10. Codificación de Canal: Código Hamming y Código Convolucional

Module by: Mariangela Mezoa. E-mail the authorEdited By: Mariangela MezoaTranslated By: Mariangela Mezoa

Summary: Este módulo contiene información acerca del bloque de codificación de canal de un sistema de comunicaciones digitales, específicamente la codificación por bloque (Código Hamming) y la codificación convolucional para la detección y corrección de errores.

CODIFICACIÓN DE CANAL: CÓDIGO HAMMING Y CÓDIGO CONVOLUCIONAL

González C. Y. Venuska

Mezoa R. Mariangela

Resumen

Este módulo contiene información acerca del bloque de codificación de canal de un sistema de comunicaciones digitales, específicamente la codificación por bloque (Código Hamming) y la codificación convolucional para la detección y corrección de errores.

Cuando transmitimos información, uno de los objetivos principales es el de minimizar la cantidad de errores que pudieran producirse en el proceso. Esta transmisión depende del factor Señal a Ruido (S/N), potencia y velocidad de transmisión. Si optimizando estas variables se necesita aún mejorar la calidad de la transmisión, entonces se deben buscar ciertos métodos que aseguren y mejoren la fiabilidad. Es a partir de aquí que surge el concepto de la codificación para control de errores.

La codificación de canal para el control de errores se encarga, básicamente, de la adición de dígitos extra al mensaje a transmitir. Ellos no poseen información como tal, pero hacen posible la detección y corrección de errores en el bloque de recepción del mensaje.

Detección y Corrección de Errores:

En un sistema de comunicaciones, detectar un error es más sencillo que corregirlo. Si existen irregularidades, el receptor puede pedir una retransmisión del mensaje que contiene el error (ARQ: Automatic Repeat Request). Sin embargo, cuando el sistema no implementa esta técnica por no ser práctico o simplemente porque no es posible, debe aplicar redundancia en el código a través del método FEC (Forward Error Correction).

El método más sencillo de redundancia en el código consiste en repetir n veces el símbolo de mensaje. Cuando los símbolos son 1 y 0, cualquier error de transmisión en una palabra código recibida alterará el patrón de repetición cambiando un 1 a 0 (o viceversa). Si los errores de transmisión ocurren de forma aleatoria (e independiente) con probabilidad Pe, entonces se pudiera definir la probabilidad de que ocurran i errores en una palabra código de n bits como:

Figura 1
Figura 1 (graphics1.jpg)

Por ejemplo, si se considera un código de repetición triple (3, 1) (1 bit de mensaje, dos bits de repetición, palabra código de tres bits), las palabras código serían 000 y 111. Cualquier mensaje recibido que no coincida con estas palabras código evidencian la presencia de errores. Pero, si los tres bits están errados (Se transmite 000 pero se recibe 111) entonces será imposible detectar el error:

Figura 2
Figura 2 (graphics2.jpg)

Si se quiere corregir el error, asumimos que al menos dos de los tres bits son correctos. Entonces, 001 se decodifica como 000 y 101 se decodifica como 111. Esto corrige palabras con un solo error, pero para dos o tres errores la probabilidad de que una palabra esté errada resulta como:

Figura 3
Figura 3 (graphics3.jpg)

Distancia Hamming

Una palabra código de n bits puede ser representarse como un vector en un espacio de n dimensiones. Por ejemplo, el código 010 puede representarse como X=( 0 1 0 ). Tomemos el caso anterior de código de repetición (3, 1):

Figura 4: Vectores que representan palabras código de tres bits.
Figura 4 (graphics4.jpg)

En total se grafican las 8 posibles combinaciones de palabras código y los puntos azules representan el código de repetición. La distancia que separa dos puntos cualesquiera se reconoce como la distancia Hamming, que está relacionada con el poder de control de errores del código (Fortaleza del código) y se define como el número de elementos diferentes entre dos puntos. Por ejemplo:

Figura 5
Figura 5 (graphics5.jpg)

La distancia mínima de un código en particular es la distancia Hamming más pequeña entre dos vectores de código válidos. De esta forma, la detección de errores es posible siempre que se cumpla que el número de errores de transmisión en una palabra código sea menor a dmín, por lo que la palabra errada no es un vector válido. Si es mayor o igual, la palabra errada puede corresponder a un vector válido y el error no podría ser detectado.

La capacidad de corrección y detección de un código se define como:

Figura 6
Figura 6 (graphics6.jpg)

Para el ejemplo desarrollado, dmín= 3, por lo que el código de repetición es capaz de corregir hasta 1 error por palabra y detectar hasta 2 errores. Evidentemente, la fortaleza del código depende del número de bits que se le agregan al mensaje original. La distancia mínima de una codificación por bloque (repetición) se define como:

Figura 7
Figura 7 (graphics7.jpg)

Codificación FEC

Un sistema FEC puede expresarse gráficamente como:

Figura 8
Figura 8 (graphics8.jpg)

Los bits de entrada llegan con una tasa de rb. El codificador toma bloques de k bits del mensaje y construye un código de bloques (n, k) con tasa Rc=k/n<1. La tasa de bits del canal será r= rb/ Rc> rb. La probabilidad de error tomará un valor de Pe<<1, que evidentemente dependerá de la energía de la señal y la densidad de potencia del ruido en el receptor (0). Si Eb representa la energía promedio por bit de mensaje, entonces la energía promedio por bit de código es Rc.Eb. Entonces:

Figura 9
Figura 9 (graphics9.jpg)

Codificación por Bloques Lineal

Como ya se mencionó antes, un código por bloques(n,k) consiste en vectores de n bits, con cada vector correspondiente a un bloque único de k bits de mensaje. Dado que existen 2k bloques de mensaje y 2n vectores de n bits, la meta está en seleccionar los 2k vectores de código que cumplan con la condición de que la distancia mínima Hamming sea lo más grande posible.

Supongamos un vector de código arbitrario tal que:

Figura 10
Figura 10 (graphics10.jpg)

Se cumple que esta codificación por bloques es lineal si al sumar, en módulo 2, dos palabras código se genera una tercera palabra código válida, incluyendo el código de puros ceros. Esta suma se define como:

Figura 11
Figura 11 (graphics11.jpg)

Ahora bien, una codificación por bloques sistemática consiste en vectores cuyos primeros (o últimos) k elementos son idénticos a los bits de mensaje, tomando el resto de los elementos (n-k) como bits de chequeo. Por lo tanto, un vector de código se expresa como:

Figura 12
Figura 12 (graphics12.jpg)

El vector de código X puede obtenerse a través de una multiplicación de matrices:

Figura 13
Figura 13 (graphics13.jpg)

La matriz identidad en G reproduce el vector de mensaje para los primeros k elementos de X, mientras que la sub-matriz P genera el vector C a través de C=MP. Al igual que con la suma de vectores explicada inicialmente, esta multiplicación de matrices sigue el procedimiento de la suma módulo 2.

Para la recepción, tomaremos el vector Y. Cualquier error de transmisión resultará en Y≠X. Uno de los métodos más fáciles es haciendo uso de una matriz de chequeo de paridad H derivada de la sub-matriz P. Se define como:

Figura 14
Figura 14 (graphics14.jpg)

Si esta última condición no se cumple, el código recibido contiene errores. La detección de errores puede basarse a partir del vector síndrome S:

Figura 15
Figura 15 (graphics15.jpg)

Si todos los elementos de S son iguales a CERO, entonces hay dos posibilidades:

  • Y es igual a X o Y;
  • Y es igual a otro vector código y el error de transmisión no se detecta.

De igual forma, los errores se indican con la presencia de elementos distintos a cero en S.

Ahora bien, si el vector X se corrompe con un vector de error E, el vector Y resultará en:

Figura 16
Figura 16 (graphics16.jpg)

Por lo que S será:

Figura 17
Figura 17 (graphics17.jpg)

Esto evidencia que el Síndrome dependerá completamente del patrón de error, no del vector transmitido. Al existir errores en la codificación, S indicará en dónde se encuentra el mismo.

Si un código debe corregir hasta t errores por palabra, entonces q y n deben cumplir con la desigualdad o relación de Hamming, definida como:

Figura 18
Figura 18 (graphics18.jpg)

Código Hamming

Es un código de bloques lineal (n,k) con 3 ó más bits de chequeo/redundancia (q) que cumple con estas ecuaciones:

Figura 19
Figura 19 (graphics19.jpg)

Dado que su distancia mínima siempre es 3 (sin importar el valor de q), este tipo de código es capaz de corregir hasta un error y detectar dos, por lo que:

Figura 20
Figura 20 (graphics20.jpg)

Supongamos el caso Hamming (7,4) (n=7, q=3, k=4). Para construir dicho código, tomamos la sub-matriz P de la matriz generadora G y la llenamos con todas las palabras de q bits que tengan dos o más 1’s, sin ningún orden en particular. Como son k=4 bits de mensaje original, entonces la matriz G tendrá cuatro filas. Entonces:

Figura 21
Figura 21 (graphics21.jpg)

Dado un bloque de bits de mensaje M = (m1 m2 m3 m4), los bits de chequeo se calculan sustituyendo los elementos de la sub-matriz P en la ecuación C=MP, por lo que:

Figura 22
Figura 22 (graphics22.jpg)

Para este ejemplo se pudiera construir un codificador Hamming de la siguiente forma:

Figura 23
Figura 23 (graphics23.jpg)

Las palabras código correspondientes a este código Hamming (7,4) se observan en la tabla (Todas generadas a partir de C=MP):

Tabla 1
Mensaje Bits Redundantes
0 0 0 0 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 1
0 0 1 1 0 1 0
0 1 0 0 0 1 1
0 1 0 1 1 1 0
0 1 1 0 1 0 0
0 1 1 1 0 0 1
1 0 0 0 1 1 0
1 0 0 1 0 1 1
1 0 1 0 0 0 1
1 0 1 1 1 0 0
1 1 0 0 1 0 1
1 1 0 1 0 0 0
1 1 1 0 0 1 0
1 1 1 1 1 1 1

Códigos Convolucionales

A diferencia de la codificación por bloque, los códigos convolucionales trabajan bit por bit. Su estructura pudiera generalizarse de la siguiente forma:

Figura 24
Figura 24 (graphics24.jpg)

Esta estructura genera V símbolos a la salida por cada símbolo de entrada. Su tasa de símbolos de salida será entonces Rc=1/V. Existen 4 métodos de representación de los códigos convolucionales:

  • Por Conexión.
  • Diagrama de estados.
  • Árbol de código.
  • Diagrama Trellis

Representación por Conexión:

Supongamos que se tiene el siguiente codificador convolucional:

Figura 25
Figura 25 (graphics25.jpg)

Para que el código funcione correctamente, antes de que llegue el primer bit del mensaje el registro de desplazamiento está ‘limpio’ (Sólo contiene 0’s). Esto implica que la primera salida será U1=0 y U2=0. Supongamos que el mensaje de entrada es 101. Entonces, el codificador hará los siguientes pasos:

Figura 26: Diagrama de conexión con salidas U1 y U2 cuando se tiene como mensaje de entrada la secuencia 101. Se asume que inicialmente los registros están vacíos.
Figura 26 (graphics26.jpg)

La secuencia de salida será:

Tabla 2
U1 U2
1 1
1 0
0 0
1 0
1 1

Representación por Diagrama de Estados:

El estado del codificador convolucional se define como los contenidos de los registros de desplazamiento de las k-1 etapas más a la derecha del codificador. Para el ejemplo actual:

Figura 27: Diagrama de estados.
Figura 27 (graphics27.jpg)

Representación por Árbol de código:

La raíz representa el estado inicial (U1U2=00). Si el próximo bit es un 0, se toma la ramificación superior. Dado que la longitud del registro es igual a 3 (L=3), entonces el árbol será:

Figura 28
Figura 28 (graphics28.jpg)

Diagrama Trellis

A través de él se puede observar la evolución del codificador por cada T que pase. El diagrama deberá tener 2k-1 nodos que representen los posibles estados (a,b,c y d). Entonces:

Figura 29
Figura 29 (graphics29.jpg)

Para la decodificación implementamos la máxima verosimilitud (maximum-likelihood), que busca maximizar P(Z/Um), siendo Um las posibles secuencias recibidas.

Figura 30
Figura 30 (graphics30.jpg)

Esto puede verse a través del Algoritmo de Viterbi: Se basa en el Diagrama de Trellis. Asigna a cada rama una métrica que es igual a la distancia Hamming correspondiente a la rama recibida y todas las ramas de Trellis que intervienen en ese instante de tiempo. Supongamos el siguiente ejemplo:

Figura 31
Figura 31 (graphics31.jpg)

Como se observa, se debe esperar hasta el instante T4 (que es cuando empiezan a cerrarse los lazos) para tomar una decisión sobre el camino más corto. Allí, se tendrán dos caminos para llegar a ese instante:

Figura 32
Figura 32 (graphics32.jpg)

Partiendo del estado a, en el estado 4 convergen dos trayectorias dos métricas: la primera con un total de 4(la de arriba) y la segunda con un total de 3(la que va por debajo). Luego se analizan situaciones similares en T4. Por ejemplo, al estado b en T4 se llega por dos trayectorias: la de arriba con métrica 4 y la de abajo con métrica 3. Para T4 pero al estado c también se llega por dos caminos: el de arriba con métrica 5 y el de abajo con métrica 0. Para T4 pero al estado d los dos caminos tienen métricas 3 y 2 respectivamente. Al eliminar todas las trayectorias de métrica mayor, en este ejemplo se logra ya despejar el bit transmitido entre la transición T1-T2 y decidir que es un “1”.

Figura 33
Figura 33 (graphics33.jpg)

Se repite el mismo procedimiento para el nodo T5 y luego para los demás nodos hasta que se vayan obteniendo cada uno de los bits transmitidos.

Se descartan entonces todos los caminos no viables. Este proceso debe repetirse hasta que se logre obtener la secuencia original.

Figura 34
Figura 34 (graphics34.jpg)

Simulación en LabVIEW

Las pruebas para las codificaciones Hamming(7,4), Hamming(15,11) y Convolucional pueden realizarse descargando el VI del siguiente enlace: Media File: canal.rar

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks