Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

codificación y decodificaión convolucional

No description
by

Nattan Morales Parra

on 13 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of codificación y decodificaión convolucional

CODIFICACIÓN CONVOLUCIONAL SISTEMAS DE COMUNICACIONES II
Presentado a: Lic. Jimmy Ramirez
Elaborado por: Freddy Cardenas
Jhonattan Morales
Codigos Respectivamente:
2007203017
2006203041
Bogotá
Diciembre 12 de 2012 Compuerta XOR Para realizar este proceso se debe tener en cuenta la tabla de la verdad de la compuerta XOR, el proceso comienza con una palabra de entrada compuesta por k numero de bits y para realizar la codificación esta palabra se ingresa bit a bit al sistema de codificación el cual compara la los bits internos del sistema y los va codificando uno a uno.
A continuación observamos el sistema de codificación el cual se compone por 3 celdas S1, S2 y S3, en este sistema el primer estado encontramos que S2 y S3 estarán los bits en cero y S1 sera el primer bit de entrada de la palabra a codificar. CODIFICADOR CONVOLUCIONAL Paso 1 Paso a paso Del anterior estado se obtuvo la primera parte de la codificacion y como resultado se genero 11.
A continuacion se ingresa el siguiente bit, antes de esto recordemos que el sistema se encuentra en el estado 100 y al ingresar el siguiente bit el estado actual es 010 del cual se obtiene despues de operar que:
bit 01 = 0
bit 02 = 1
ya se tiene como palabra codificada de estos primeros pasos 01 11 Paso 2 CODIFICACIÓN Y DECODIFICACIÓN CONVOLUCIONAL Para poder realizar la codificación y decodificación convolucional se debe tener en cuenta la forma de operar de la compuerta XOR, para ello a continuación se ilustra su funcionamiento El código convolucional busca por medio de redundancias detectar y corregir errores de transmisión en el sistema, este tipo de códigos son adecuados para ser usados sobre canales con mucho ruido.
Estos sistemas tienen memoria y dicha memoria depende de los datos que se envían en un ahora y los datos que están por entrar para ser posteriormente enviados
Los códigos convolucionales están especificados por los siguiente parámetros:
n = al numero de bits de la palabra codificada es decir palabra de salida
k = es el numero de bits de la palabra de datos o palabra de entrada
m = es a memoria del codigo o longitud restringida Para realizar este ejemplo se enviara la secuencia de bits 0101, el proceso de codificación es un proceso de desplazamiento bit a bit, es decir:
-Se introduce el primer bit de la secuencia en el codificador y se opera según XOR, donde 01 es el bit de la posición derecha o mas significativo y 02 el bit de la posición izquierda o menos significativo, para este caso de observa que el primer estado del sistema es _00 y el estado actual es 100: Paso 3 Se tiene en cuenta que el estado anterior a este paso es 010 y al ingresar el siguiente bit el estado actual sera 101 al operar:
bit 01 = 0
bit 02 = 1
para recordar la palabra codificada hasta el momento es 01 01 11 Paso 4 Se introduce el cuarto bit de la secuencia en el codificador, teniendo en cuenta que el estado anterior era 101 y el estado actual sera 010
bit 01 = 0
bit 02 = 1
ya como salida final se obtiene 01 01 01 11 Al final del proceso de codificación obtenemos que la secuencia codifificada es 01 01 01 11.
Debido a la memoria del codigo es necesario disponer de medios adecuados para determinar la salida de una determinada entrada, para esto existen tres metodos graficos:

-Diagrama de arbol
-Diagrama de estado
-Diagrama de enrejado -Es la representacion sistematica de todas las posibles salidas de un codificador
-La profundidad del diagrama de arbol esta definida por 2(m-1) para nuestro caso m = 3 el numero de celdas de nuestro codificador o la longitud del mismo
-las ramas terminales del arbol crenen de gorma exponencial a medida que la secuencia de informacio va creciendo, a partir del segundo nivel se vueleve repetitivo, en realidad, solo hay cuatro tipos de nodos:
A,B,C,D. Por ejemplo, de cualquier nodo etiquetado como C se producen el mismo par de ramas de salida: Salida 10 y estado A Y Salida 01 y estado B .
A continuación se obserba el diagrama de arbol de nuestro codigo y la secuencia a seguir para la codificación:
Sec. Entrada: 0101
Sec. Salida: 01 01 01 11
para el diagrama de estado se deben tener encuenta los estados del codificador con el fin de tener la secuencia DIAGRAMA DE ARBOL Para continuar se desplazan los bits a la derecha y quedaría el estado actual en 00 se ingresa el bit 1 y a continuación tendremos la salida 111 y obtenemos como estado final 10 teniendo en cuenta que se desplazara para permitir en ingreso del siguiente bit la secuencia a seguir continua en linea azul Paso 3 Ya como paso final se ingresa el bit 1 teniendo en cuanta que el estado inicial sera 10 y la salida del sistema sera 110. Diagrama de malla La con la ultima secuencia se muestra el grafico total de malla DIAGRAMA DE MALLA O ENREJADO Para este proceso de utilizara otro método de codificador convolucional, se muestra a continuacion el proceso de desarrrollo de este metodo y la graficación del diagrama en malla basado en el siguiente estructura la cual es una estructura general para este tipo de diagrama Se observa a continuacion el codificador convoluciional y como estado inicial tiene 00 y entra un bit 0 y se obtiene como salida 000 Paso 1 Ubicación en diagrama de malla A continuación comenzamos a generar la secuencia y para esto se comienza del estado a=00 el cual al ingresar el primer bit tenemos como salida 000 el camino se muestra con una linea azul Paso 2 Diagrama de estado Este es el menos utilizado y no se va a tomar en cuenta en la actual presentación. DECODIFICACIÓN Consiste básicamente en comparar alguna de las secuencias que llega (bit de entrada) con cualquier secuencia que se haya podido emitir (bit de salida o palabra codificada).
Debido a lo anterior se observa que dicha comparación tiene un costo computacional muy alto y de ahí nace el algoritmo de Viterbi con el fin de reducir el costo computacional anteriormente mencionado ALGORITMO DE VITERBI -Basado en el diagrama de rejilla el algoritmo de Viterbi, asocia a cada rama de la rejilla una etiqueta con las distancias entre los bits recibidos por en canal y los bits de salida generados a esta rama
-Para calcular el camino solo hay que sumar la etiqueta rama a rama Funcionamiento -Este funcionamiento es de tipo secuencial,y recorre el diagrama de izquierda a derecha
-Parta cada estado se calcula la distancia acumulada por todos los caminos posibles
-posteriormente se selecciona el camino con la distancia mínima, si dado el caso se general uno o mas caminos con la misma distancia mínima se escoge el camino de forma aleatoria
-Ya cuando se llega al ultimo estado es cuando se decide que camino se debe tomar dado el caso que existan uno o mas caminos de la misma distancia siempre esta decisión se toma al final del proceso Ejemplo Para este ejercicio se tiene un mensaje de ingreso igual a 10100 y del cual al realizar la codificación se obtiene la palabra, 111 001 100 001 011, generando la siguiente secuencia de malla, este mensaje es lo que transmite el emisor: paso 1 Paso 2 Comenzaremos comparando la primera salida codificada es decir, 110, con las ramas adyacentes, rama A y rama B (aclaramos los nombres de las ramas se ponen aleatoriamente para cumplir con la explicación de la presentación) esto se ilustra en la Figura 1 Como vemos al comparar la salida con cada una de las ramas:
Rama A = 000 Rama B =111, ahora vamos a identificar el numero de bits de diferencia entre cada rama con respecto a la entrada:
- Rama A bits de diferencia entre 000 y 110 son 2 bits
-Rama B bits de diferencia entre 111 y 110 es 1 bit
posteriormente etiquetamos cada rama con el numero de bits de diferencia (figura 2) teniendo esto en cuenta ya sabemos que existen dos caminos iniciales para llegar al punto fina . Fig. 1 Fig. 2 Ahora continuaremos con la siguiente entrada 101 partiendo de los caminos que nos genero la primer entrada buscaremos los nuevos posibles caminos, para este segundo caso se generan cuatro caminos a seguir simultáneamente compararemos el numero de bits de la entrada con los bits de cada una de las nuevas ramas posibles, esto se ilustra a continuación. Paso 3 Para realizar este paso se desarrolla de la misma manera como los pasos anteriores es decir teniendo en cuenta los posibles caminos ya delimitados por el paso dos buscamos los nuevos caminos y las respectivas diferencias de bits con respecto a la entrada 100 esto se ilustra a continuación. Paso 4 Para realizar este paso se desarrolla de la misma manera como los pasos anteriores es decir teniendo en cuenta los posibles caminos ya delimitados por el paso dos buscamos los nuevos caminos y las respectivas diferencias de bits con respecto a la entrada 101 esto se ilustra a continuación. Paso 5 Teniendo en cuenta el funcionamiento de Viterbi nos indica que lo que tenemos que hacer es comparar cada una de las salidas codificadas de cada bit original con las ramas adyacentes a esta codificación generada y para este caso comenzaremos tomando en cuenta la malla original De la misma forma como se ah venido explicando se realizara este mismo paso teniendo en cuenta el que la entrada sera 011 a continuación se ilustra el diagrama Fase 1 final fase 1 Ya como paso final tenemos el siguiente diagrama con la totalidad de las salidas comparadas de cada bit ilustradas en la siguiente figura Paso 1 Paso 2 fase 2 Para comenzar esta segunda fase de la decodificación convolucional usando el algoritmo de Viterbi se debe tener en cuenta el diagrama final de la fase 1 ilustrada a continuación, para luego desarrollar los pasos finales a la decodificación Ya para esta fase lo que debemos hacer es buscar todos los caminos posible para llegar al final esto se desarrolla también por ramas y se etiquetan sumando el numero de bits que se necesitan para llegar a cada camino, dicha etiqueta siempre debe ser la de la mínima distancia para comprender mejor en la siguiente figura se ilustra dicho proceso De la figura anterior el dos aparece de la suma de los bits que necesita para llegar a la otro punto de inicio del siguiente estado y como el único bit que aparece en la rama A es 2 vamos a etiquetar la el punto como dos y el uno de la misma manera aparece ya que para pasar de un punto a otro de la rama B el único bit que aparece el 1 la etiquetamos como 1 A continuación basándonos en el paso anterior vamos a recorrer en camino que se genera de cada rama y sumar los bits que existen para llegar al siguiente paso es decir:
-Desde rama A hasta rama C
-Desde rama A hasta rama F
-Desde rama B hasta rama F
-Desde rama B hasta rama G Como observamos existen 2 caminos para llegar a la rama F pero solo se toma el que va de la rama B hasta la F ya que la suma de los bit de este camino nos genera como etiqueta 2 en cambio si tomamos el camino de la rama A a la rama F la suma de estos bits no genera 3 y por principio de Viterbi nos dice que debemos tomar el camino que menos distancia tenga Paso 3 Teniendo en cuenta el paso 3 se continua la gráfica hasta recorrer todos los caminos a continuación se presenta otro posible problema a la hora de hallar los caminos Como podemos ver la variante de este ejercicio es que hayan varios caminos para llegar a una sola rama por ejemplo el recorrido que pasa de las ramas A, E y K la suma es 5 de igual manera si se recorre el camino de las ramas B, G y H la suma de los bits da 5, en casos como estos se puede escoger cualquiera de los caminos surgen. En este orden de ideas se buscan todos los caminos posibles para llegar al punto final y se genera el diagrama total de caminos ilustrado en la siguiente figura: Paso 4 Ahora ya con todos los caminos creados se puede observar que el camino con la suma menor desde el principio hasta el final es el camino que recorre las ramas B, D, F, K, Ñ y P, y los otros caminos se procede a eliminarlos (Figura 1). De los caminos anteriormente eliminados solo queda uno y si cogemos desde el final y nos devolvemos encontramos la secuencia decodificada (Figura 2) Fig. 1 Fig. 2 En esto consiste la secuencia de decodificación de Viterbi y por medio de esta conseguimos llegar al camino original y recuperar el mensaje detectando y los errores en el sistema BIBLIOGRAFÍA -http://ma.alvarez0005.eresmas.net/trabajos/ccvsatelite/teoria.html
-http://200.69.103.48/comunidad/profesores/jruiz/jairocd/texto/uit/codigconvolucionales.pdf
-http://es.wikipedia.org/wiki/Puerta_XOR
-http://es.wikipedia.org/wiki/Algoritmo_de_Viterbi CONCLUSIONES -El código de Viterbi permite realizar el proceso de decodificación de una manera mas rápida detectando los errores por medio de las distancias que existen entre los posibles caminos
-Una de las desventajas es que necesita mucha capacidad de almacenamiento
-El costo computacional es mucho mas bajo que otro métodos de decodificación
Full transcript