viterbi.pdf
TRANSCRIPT
![Page 1: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/1.jpg)
Códigos para Control deErrores. Algoritmo de Viterbi
Dr. Ing. Nestor Ruben Barraza
Departamento de Electronica
Facultad de Ingenierıa
Codigos para Control de Errores. Algoritmo de Viterbi– p. 1
![Page 2: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/2.jpg)
Contenido
Concepto de canal ruidoso
Codigos para Control de Errores. Algoritmo de Viterbi– p. 2
![Page 3: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/3.jpg)
Contenido
Concepto de canal ruidoso
Objetivos de la codificación
Codigos para Control de Errores. Algoritmo de Viterbi– p. 2
![Page 4: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/4.jpg)
Contenido
Concepto de canal ruidoso
Objetivos de la codificación
Códigos Convolucionales
Codigos para Control de Errores. Algoritmo de Viterbi– p. 2
![Page 5: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/5.jpg)
Contenido
Concepto de canal ruidoso
Objetivos de la codificación
Códigos Convolucionales
Decodificador de Viterbi
Codigos para Control de Errores. Algoritmo de Viterbi– p. 2
![Page 6: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/6.jpg)
Contenido
Concepto de canal ruidoso
Objetivos de la codificación
Códigos Convolucionales
Decodificador de Viterbi
Conclusiones
Codigos para Control de Errores. Algoritmo de Viterbi– p. 2
![Page 7: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/7.jpg)
Canal Ruidoso
Codigos para Control de Errores. Algoritmo de Viterbi– p. 3
![Page 8: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/8.jpg)
Canal Ruidoso
Teorema de la Codificación del Canal. Shannon (1948)
Codigos para Control de Errores. Algoritmo de Viterbi– p. 3
![Page 9: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/9.jpg)
Canal Ruidoso
Teorema de la Codificación del Canal. Shannon (1948)
Codigos para Control de Errores. Algoritmo de Viterbi– p. 3
![Page 10: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/10.jpg)
Tipos de Codificación
Códigos de Bloque
Códigos Convolucionales
Codigos para Control de Errores. Algoritmo de Viterbi– p. 4
![Page 11: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/11.jpg)
Convolucionales
Elias (1955)
Corrección de Errores en tiempo real
Codigos para Control de Errores. Algoritmo de Viterbi– p. 5
![Page 12: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/12.jpg)
Convolucionales
Elias (1955)
Corrección de Errores en tiempo real
Convierte toda la cadena de bits en unasimple palabra de código
Codigos para Control de Errores. Algoritmo de Viterbi– p. 5
![Page 13: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/13.jpg)
Convolucionales
Elias (1955)
Corrección de Errores en tiempo real
Convierte toda la cadena de bits en unasimple palabra de código
El bit codificado depende tambien de bits deentrada pasados
Codigos para Control de Errores. Algoritmo de Viterbi– p. 5
![Page 14: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/14.jpg)
Convolucionales
Elias (1955)
Corrección de Errores en tiempo real
Convierte toda la cadena de bits en unasimple palabra de código
El bit codificado depende tambien de bits deentrada pasados
Ampliamente difundido en Comunicaciones.TDMA/GSM, Wireless
Codigos para Control de Errores. Algoritmo de Viterbi– p. 5
![Page 15: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/15.jpg)
Convolucionales
Elias (1955)
Corrección de Errores en tiempo real
Convierte toda la cadena de bits en unasimple palabra de código
El bit codificado depende tambien de bits deentrada pasados
Ampliamente difundido en Comunicaciones.TDMA/GSM, Wireless
Codigos para Control de Errores. Algoritmo de Viterbi– p. 5
![Page 16: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/16.jpg)
Implementación
Registros de Desplazamiento. Feedforward
Tasa k
n, k bits de entrada, n bits de salida
Codigos para Control de Errores. Algoritmo de Viterbi– p. 6
![Page 17: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/17.jpg)
Ecuaciones
c(1)i = mi−2 + mi−1 + mi
c(2)i = mi−2 + mi
i m S1 S2 c1 c2
0 1 0 0 1 11 0 1 0 1 02 0 0 1 1 13 0 0 0 0 0
Codigos para Control de Errores. Algoritmo de Viterbi– p. 7
![Page 18: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/18.jpg)
Respuesta al impulso
g(1) = (1 1 1)
g(2) = (1 0 1)
c(l)i =
K∑
k=0
mi−k g(l)
M(D) = m0 + m1 D + m2D2 + · · ·
Codigos para Control de Errores. Algoritmo de Viterbi– p. 8
![Page 19: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/19.jpg)
Función Transferencia
G(D)(j) = g(j)0 + g
(j)1 D + g
(j)2 D2 + · · ·
C(D) = M(D) G(D)
Codigos para Control de Errores. Algoritmo de Viterbi– p. 9
![Page 20: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/20.jpg)
Implementación
Registros de Desplazamiento. Feedback
Codigos para Control de Errores. Algoritmo de Viterbi– p. 10
![Page 21: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/21.jpg)
Decodificación
Secuencial. 1957
Viterbi. 1967
Máximo a Posteriori. Algoritmo BCJR, 1974
Codigos para Control de Errores. Algoritmo de Viterbi– p. 11
![Page 22: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/22.jpg)
Algoritmo de Viterbi
Algoritmo Óptimo de decodificación de MáximaVerosimilitud. s = MAXs(ln p(y/s)
Usado para códigos convolucionales o de Trellis
Determina el sendero mas probable de acuerdo a lossaltos ponderados
Codigos para Control de Errores. Algoritmo de Viterbi– p. 12
![Page 23: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/23.jpg)
Hard-Soft decision
1. Hard decision. Distancia de Hamming
2. Soft Decision. Distancia euclidiana con elvalor analógico recibido.
Ver ”Essentials of Error-Correcting Codes”,Castiñeira and Farrel. par. 6.15 y ejemplo 6.9.
Codigos para Control de Errores. Algoritmo de Viterbi– p. 13
![Page 24: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/24.jpg)
Esquemas
Codigos para Control de Errores. Algoritmo de Viterbi– p. 14
![Page 25: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/25.jpg)
Hard decision
Métrica de ramas: δ(cod,out)
δ(11, 11) = 0, δ(01, 10) = 2, δ(00, 01) = 1
Se queda con el lazo con menor métrica
Codigos para Control de Errores. Algoritmo de Viterbi– p. 15
![Page 26: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/26.jpg)
Soft decision
Ver ”Essentials of Error-Correcting Codes”,Castiñeira and Farrel. Fig. 6.28.
Métrica de ramas: δ(cod,out)
δ(1,35 − 0,15,−1 − 1) = 6,245
Se queda con el lazo con menor métrica
Codigos para Control de Errores. Algoritmo de Viterbi– p. 16
![Page 27: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/27.jpg)
Eficiencia. Simulación
Codigos para Control de Errores. Algoritmo de Viterbi– p. 17
![Page 28: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/28.jpg)
Eficiencia. Experimental
Codigos para Control de Errores. Algoritmo de Viterbi– p. 18
![Page 29: viterbi.pdf](https://reader034.vdocumento.com/reader034/viewer/2022051516/55cf9918550346d0339b8932/html5/thumbnails/29.jpg)
Conclusiones
Baja tasa de BER (Bit Error Rate)
Sencillez en la Implementación
Decodificación Óptima. ML
Codigos para Control de Errores. Algoritmo de Viterbi– p. 19