Diagrama de Trellis PDF

Preview

Summary

El diagrama de Trellis es una representación basada en nodos de los posibles estados que tomara el codificador convolucional. Un codificador convolucional pasa de un estado a otro, dependiendo del bit actual y de los bits de entrada anteriores, esta transición de estados puede ser representada de ...

Description

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

Diagrama de Trellis El diagrama de Trellis es una representación basada en nodos de los posibles estados que tomara el codificador convolucional. Un codificador convolucional pasa de un estado a otro, dependiendo del bit actual y de los bits de entrada anteriores, esta transición de estados puede ser representada de forma lineal a partir de un diagrama de Trellis. Características del diagrama Se representa la trayectoria de un estado hacia otro mediante una línea continua si su entrada es cero (0), y con línea entrecortada cuando la entrada es uno (1). El eje vertical indica todos los posibles estados del codificador mientras el horizontal determina las transiciones de tiempo de todos los posibles estados. Una transición de tiempo indica que un bit va a codificarse, existirá una transición para cada bit que ingrese. Considerando el codificador convolucional básico planteado anteriormente (una entrada, 3 registros de memoria y tres salidas), se obtiene el diagrama de Trellis de la figura 1.

Fig.1 Diagrama de Trellis del codificador planteado.

 -_

Salida codificada. Transición de estado para entrada 1. Transición de estado para entrada 0.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

De donde a, b, c y d son los 4 estados posibles del codificador. Análisis y determinación de diagrama de Trellis Se considera estado inicial R1=0, R2=0, R3=0 (R1, R2, R3: Registros de desplazamiento). Por tanto el codificador se encuentra en el estado a=00 (R1=0 y R2=0) . Para determinar el estado del codificador son solo necesarios los registros R1 y R2.

Fig.2. Codificador Convolucional. La entrada puede ser un 1L o un 0L. Si la entrada es un 1L, el codificador pasa del estado a=00 (R1=0, R2=0, R3=0 Estado inicial) a el estado c=10 (R1=1, R2=0, R3=0) ya que el valor de entrada es almacenado en el registro R1, siendo desplazados el valor de R1 y R2 hacia la derecha ocupando ahora los registros R2 y R3 respectivamente , obteniendo como salida 111 (S1=1, S2=1, S3=1). En caso de que la entrada sea un 0L, el codificador pasa del estado a=00 a el estado a=00, es decir mantiene su estado y su salida codificada es 000. Esta transición es representada en el diagrama de Trellis en el intervalo t1 (nodo t1) como se indica a continuación. 

Salida codificada.

--- Transición de estado para entrada 1.

_ Transición de estado para entrada 0.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

En el intervalo consecuente t2, la entrada puede ser un 0L o un 1L, puesto que en t1 se posee 2 posibles estados, debe analizarse cada uno de estos posibles casos: a) Analizando el estado c=10, si la entrada es un 0L el codificador pasa a el estado b=01 (R1=0, R2=1, R3=0) obteniendo una salida 001 (S1=0, S2=0, S3=1). Si la entrada es un 1L el codificador pasa a el estado d=11 (R1=1, R2=1, R3=0) con una salida codificada 110 (S1=1, S2=1, S3=0). b) Analizando el estado a=00, si la entrada es un 0L el codificador se mantiene en el mismo estado con una salida 000. Si la entrada es un 1L, el codificador pasa a el estado c=10 obteniendo una salida 111 (S1=1, S2=1, S3=1). Como se indica a continuación.



Salida codificada.

--- Transición de estado para entrada 1.

_ Transición de estado para entrada 0.

Para obtener el diagrama de Trellis del codificador, se realiza el mismo proceso para el resto de nodos, en donde cada transición indica un nuevo bit que ingresa al codificador. Las salidas del codificador se presenta a continuación en una tabla de verdad, obteniendo como resultado el diagrama de la figura 4. R1

R2

R3

S1

S2

S3

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 0 0 0 1 1 1 1

0 1 0 1 1 0 1 0

0 1 1 0 1 0 0 1

Tabla 1. Salidas del codificador.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

Fig. 3. Diagrama de Trellis del codificador planteado. Se puede observar que a partir del tiempo de transición t3, el diagrama de Trellis se estabiliza, presentando las mismas trayectorias en los siguientes nodos. Ejemplo: Para el codificador planteado, se analiza la salida del codificador de la siguiente secuencia de datos de entrada: 101011. La secuencia de datos de entrada se codificara de derecha a izquierda, es decir el primer bit que ingresara al codificador es el 1L del extremo derecho. El estado inicial del codificador es el a=00, haciendo uso del Diagrama de Trellis de la figura 3 se inicia con el proceso de codificación eligiendo a partir de cada nodo el camino según el bit de entrada. En la primera transición de tiempo t1, la entrada de 1L cambia el estado inicial a el estado c=10 y da como resultado la salida codificada 111.

El segundo bit a codificar es un 1L que produce una transición t2, el cual cambia el estado del codificador a el estado d=11 generando una salida 110, y una secuencia codificada 111110.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

El tercer bit de entrada es un 0L, el cual produce una transición t3 cambiando del estado d a el estado b=01 con una salida 010. Produciendo una secuencia codificada 111110010.

Se aplica el mismo procedimiento para los 3 bits restantes, según el estado del bit a codificar se obtiene la trayectoria a seguir y por ende la salida codificada. A continuación se presenta la respuesta del codificador a la secuencia de bits de entrada.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

Obteniendo la secuencia codi ficada : 111110010100001100.

Algoritmo de Viterbi El algoritmo de Viterbi permite encontrar la secuencia de estados más probable en un modelo estocástico, por tanto se emplee en la decodificación de códigos convolucionales. Distancia de Hamming Esta distancia se define como la cantidad de bits que cambian de una palabra código válida a otra. Es decir si dos palabras código tienen una distancia de Hamming de valor d, serán necesarios d errores para convertir una palabra código en la otra. Ejemplo: a) Palabra código 1: 1 1 0 0 1 1 0 Palabra código 2: 1 1 0 0 1 0 0 La distancia de Hamming entre PC1 y PC2 es d=1. Palabra código 2: 1 1 1 1 1 0 0 b) Palabra código 1: 0 0 0 1 1 0 0 La distancia de Hamming entre PC1 y PC2 es d=3. Decodificación de Viterbi El decodificador es al igual que el codificador convolucional una maquina de estados con los mismos estados posibles y transiciones de tiempo. Es decir, se basa en el diagrama de Trellis del codificador. Haciendo uso de la distancia de Hamming, se compara el código convolucional con todas las posibles trayectorias presentes en el diagrama de Trellis del codificador, de tal forma que la trayectoria con menor sumatoria total de distancias de Hamming es la información correcta, corrigiendo posibles errores introducidos al transmitir la información. Haciendo uso de la decodificación de Viterbi es posible corregir múltiples errores simultáneamente, siendo esto una de sus principales ventajas. A continuación se detalla el proceso de decodificación.

Ejemplo:

Considerando el dato codificado anteriormente: 111110010100001100.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

Suponiendo que en el proceso de transmisión se produce 3 bits errados. A la entrada del decodificador llega la siguiente secuencia de bits, en donde los bits errados son notados con rojo para el análisis del proceso de decodificación.

Dato original: Salida del codificador:

1

0

1

0

1

1

111 110 010 100 001 100

Entrada del decodificador: 111 101 010 100 000 100

Haciendo uso del diagrama de Trellis del codificador, iniciamos el análisis del decodificador con el primer símbolo codificado es decir la secuencia 111 en la entrada del decodificador y calculamos la distancia de Hamming entre esta secuencia y las posibles trayectorias en la transición t1 como se indica en la figura. En t1 hay dos posibles trayectorias que generan 2 posibles códigos, el primero 000 y el segundo 111, obteniendo una distancia de Hamming d=3 y d=0 (Notado en verde en la figura) respectivamente en esta transición.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

La segunda transición t2, posee 4 posibles trayectorias que generan los códigos 000, 111, 001, 110. Se calcula la distancia de Hamming entre la secuencia codificada 101 y los posibles códigos obteniendo distancias d=2, d=1, d=1, d=2 respectivamente. Para el tercer intervalo t3, se poseen 8 posibles trayectorias por lo que se calcula la distancia de Hamming entres estos posibles códigos y la secuencia codificada 010, como se indica en la figura. Se realiza el mismo procedimiento para las siguientes transiciones, obteniendo las distancias de Hamming de todas las posibles trayectorias. A continuación se realiza la sumatoria de todas las distancia de Hamming en todas las posibles rutas. La ruta con menor sumatoria total es la información con menor cantidad de errores posibles y por ende es la información que el decodificador entrega. En la gráfica inferior se resaltan las 2 rutas con menor sumatoria de distancias de Hamming, sin embargo se debe realizar el análisis de todas.

Transiciones detiempo:t=t 1+t 2+ t 3+t 4+ t 5+t 6 Ruta café : ∑ d=0+1+ 1+1 + 0+ 1=4 Ruta celeste:∑ d=0+ 2+0+0 + 1 + 0=3 La ruta con menor sumatoria de distancias de Hamming, es la ruta celeste, la cual contiene la información que entrega el decodificador, esta coincide con la información correcta que fue transmitida. Corrigiendo los 3 bits errados introducidos en el proceso de comunicación.

INGENIERÍA EN ELECTRÓNICA Y TELECOMUNICACIONES COMUNICACIÓN DIGITAL

El decodificador entrega como primer bit el bit del extremo derecho, es decir de derecha a izquierda. Siendo el primer bit el 1L y a continuación el 0L y así sucesivamente. Obteniendo a su salida la información original.

Salida del decodificador :1 0 1 01 1 Entrada del codificador : 1 0 10 1 1...