Teoria De La Informacion Y Comunicacion

TEORIA DE LA INFORMACIO Y LA COMUNICACION


ALGORITMO DE VITERBI
DEFINICION
Un método de fuerza bruta de decodificar una secuencia utilizando el principio de máxima verosimilitud es calcular la distancia entre la secuencia recibida y todas las posibles secuencias transmitidas, seleccionado entonces la de mínima distancia. Es decir, si se reciben palabras codificadas de N bits de longitud,entonces habrá que hacer 2N cálculos de distancia. Esto implica que a medida que N aumenta se hace impráctica la carga computacional de tal método.
El algoritmo de Viterbi esencialmente lleva a cabo el proceso de decodificación según el principio de máxima verosimilitud; sin embargo reduce la carga de código, pero tomando ventaja del árbol de código.

Se basa en el principio de calcular ladistancia entre la señal recibida en el tiempo t y todas las trayectorias o caminos del esquema del enrejado de Trellis en cada tiempo ti, desechando aquellos caminos que no son candidatos posibles para escoger los de máxima probabilidad. Cuando 2 caminos entran al mismo estado, se escoge el que tenga mayor métrica, el cual se llama camino superviviente. La selección de caminos supervivientes se efectúapor todos los estados. El decodificador continua de esta forma avanzando en profundidad en el enrejado ejecutando decisiones que eliminan los caminos menos probables.

EJEMPLO:
La codificación convolucional se decodifica con ayuda del algoritmo de Viterbi. En la siguiente figura mostramos el algoritmo para la codificación del ejemplo.

El algoritmo de Viterbi también se puede simular enoctave, aunque sólo disponemos de la función para codificadores que realizan un desplazamiento por ciclo (k=1). El comando correspondiente es,
* Algoritmo de Viterbi, y=viterbi(G,2*c-1). En esta función, G es la matriz generadora del codificador convolucional, c es la secuencia de entrada, e y es la secuencia decodificada. La entrada tiene que tener los valores +/-1, por lo que hemos puesto2*c-1.
Para el ejemplo que tenemos,
>> G= [ 1 0 0 ; 1 0 1 ; 1 1 1 ]; % matrix generadora
>> c= encode_conv(G,[0 1 1 0],1); % codificamos [0 1 1 0]
>> % ahora empieza la decodificación
>> y=viterbi(G,2*c-1) % recuperamos la secuencia
Código de Trellis
El código Trellis genera símbolos para la transmisión utilizando una máquina secuencial de estados finitos utilizandolongitudes de palabras arbitrarias. Este proceso de codificación inserta las propiedades claves de memoria y de redundancia dentro de un flujo de datos, como en el caso de los códigos de bloque. El proceso de codificación busca cantidades secuenciales para ser relacionadas. Desde una perspectiva formal, no hay necesidad de bloques de mensajes en segmentos de una misma longitud.

Una descripcióngenérica de un codificador Trellis es representada en la Fig. 2.1. Cada cambio de tiempo, es notado como j, un vector de k entradas de símbolos (usualmente bits) es designada por , símbolos que pueden haber sido extraídos desde una serie de símbolos originales escritos en la forma de  . El codificador produce un vector de n símbolos de código, usualmente del mismo alfabeto, con n > k,introduciendo redundancia. Se define la memoria (también llamada el orden de la memoria m) del codificador como el número de vectores de entrada, que junto con el vector uj, condiciona la salida activa de xj. Así como lo muestra la Figura 2.1, el codificador posee m (vectores) celdas de memoria o retraso.
El símbolo de código producido cada cambio de tiempo puede ser conectado a un modulador en variasformas. Las aplicaciones más sencillas involucran codificación binaria, en la cual n símbolos binarios son serializados y cargados en un modulador binario, como el caso del PSK. Se puede alternativamente igualar la salida de los símbolos con un carácter dentro de un campo más grande y producir un simple M-aria de un conjunto más grande para cada intervalo de reloj. El método preferido depende del...