Download - TemaII-3.ppt
-
7/24/2019 TemaII-3.ppt
1/62
Tcnicas de Deteccin y Correccin de
Errores
Profesora Mara Elena Villapol
-
7/24/2019 TemaII-3.ppt
2/62
Tcnicas de Deteccin y Correccin deErrores
!os canales inal"m#ricos proporcionan los ndicesde error $ue suelenen torno a %&'(.
Estas altas tasas de error son el multipath fading$ue caracteri)an a los canales de radio mvil.
Existen dos aproximaciones para poder tratar estepro#lema*
+ Correccin de Error ,acia -delante /or0ard ErrorCorrection1 /EC2.
+ 3e$uerimiento de 3epeticin -utom"tica -utomatic3epeat 3e$uest1 -342.
-
7/24/2019 TemaII-3.ppt
3/62
Deteccion vs Correccion
Existen tecnicas para detectar errores yotras para corre5ir errores.
-
7/24/2019 TemaII-3.ppt
4/62
-
7/24/2019 TemaII-3.ppt
5/62
3edundancia
Para detectar o corre5ir errores senecesita a5re5ar cierta redundancia a los#its de informacin.
-
7/24/2019 TemaII-3.ppt
6/62
/EC
Cdi5os de #lo$ues.+ !ineales
cclicos
Cdi5os convolucionales.
-
7/24/2019 TemaII-3.ppt
7/62
Cada #lo$ue de k #its es codificado con un #lo$ue de(k+r)#its denominado pala#ra cdi5o codeword2.
!a pala#ra cdi5o es la $ue se transmite. En el receptor varias cosas pueden pasar*
+ 6i no 7ay errores1 la salida de decodificador es i5ual al cdi5oori5inal.
+ Para ciertos errores1 el decodificador puede detectar y corre5irlos mismos.
+ Para ciertos patrones de errores1 el decodificador puede
detectar el error pero no corre5irlo.+ Para ciertos errores el decodificador no puede detectar el error y
produce una se8al de salida $ue difiere de la ori5inal.
Cdi5os para la deteccin de errores
-
7/24/2019 TemaII-3.ppt
8/62
Codificacin por 9lo$ues
-
7/24/2019 TemaII-3.ppt
9/62
Cdi5os por 9lo$ues !ineales
Casi todos los cdi5os de #lo$ue utili)ado7oy en da pertenecen a un su#5rupollamado #lo$ue de cdi5os lineales.
:n cdi5o de #lo$ue lineal es un cdi5oen el $ue el ;3 exclusivo adicinmdulo'(2 de dos pala#ras de cdi5o
v"lidas crea otra pala#ra de cdi5o v"lida
-
7/24/2019 TemaII-3.ppt
10/62
Deteccin de Errores
-
7/24/2019 TemaII-3.ppt
11/62
Principios de la deteccin de errores
El al5oritmo suma r#its al #lo$ue de datos de m #its. !osk#its en la se8al ori5inal se transmiten en la pala#ra cdi5o de
(k+r)#its. !a distancia de Hamming1 dv%1v(2 se define como el n (n.dmin = minij [d(wi,wj)]
Por e?emplo1 si v% > &%%&%% y v( > %%&&&% dv%1v(2 >
!a funcin de la forma vc > fvd2 donde vd es un vector de data dem #its y vc la pala#ra cdi5o. El radio de redundanciaie redundancia2 es rAB. !a tasa del cdigoes BABr2 y mide la cantidad adicional de anc7o
de #anda $ue se necesita.
-
7/24/2019 TemaII-3.ppt
12/62
!as si5uientes consideraciones se de#en tener en eldise8o de un cdi5o*+ Dado B y r1 nos 5ustara el valor m"s 5rande de dmin.
+ El codificador de#era ser sencillo re$uiriendo un mnimo de
memoria y tiempo de procesamiento.+ os 5ustara un pe$ue8o n
-
7/24/2019 TemaII-3.ppt
13/62
Principios de la deteccin de errores
Para detectar d errores se re$uiere unadistancia de d+1. Por e?emplo1 #it deparidad.
Para corre5ir derrores1 se re$uiere unadistancia de d+1.
-
7/24/2019 TemaII-3.ppt
14/62
9it de Paridad
6umar un #it al finalde un #lo$ue de data.
De forma tal $ue1 el
car"cter tiene*+ :n n %%%&&%&%+ Calculo en el receptor 92 >
%%%&&%&&+ Distancia -'9 > (
-
7/24/2019 TemaII-3.ppt
15/62
C7e$ueo Cclico 3edundante C3C2
Para un #lo$ue de k#its1el transmisor 5enera unasecuencia de r#its.
El transmisor transmite
una secuencia de k+r#its1la cual es exactamentedivisi#le por un n trama de (r+k)
#its1 r FB
+ M> mensa?e de k#its.+ / > secuencia /C6
de r#its.+ P > divisor con un
patrnpredeterminado.
+ Tienen r+1#its.
-
7/24/2019 TemaII-3.ppt
16/62
El o#?etivo es $ue TAP no ten5a resto.
Es claro $ue*
! = r" + #
+ r" despla)a el mensa?e a la i)$uierda y lo rellena de ceros &2.
Dividir r
" entre P*r"$%= & + '$%
:semos 3 como el /C6
! = r" + ' !$% = r" $%+ '$% = & + ('$% + '$%) = &
-s $ue no 7ay resto.
Esto es por la suma modulo ( #asada en la operacin ;3'exclusivo* = 1 = 1 1 = 1 1 1 = *
Entonces1 dividir (rM entre P y usar el resto como el /C6.
C7e$ueo Cclico 3edundante C3C2
-
7/24/2019 TemaII-3.ppt
17/62
C7e$ueo Cclico 3edundante C3C2
6e puede demostrar $ue los si5uientes erroresson detecta#les*+ Errores de un #it
+ Errores de dos #its siempre $ue P tiene tres trminosen %.+ Cual$uier n
-
7/24/2019 TemaII-3.ppt
18/62
C3C* 3epresentacin PolinomialAE?emplo
M > %&%&&&%%&% %& #its2 F'GHIHJH@H(%
P > %%&%&% K #its2 F'G H
L
HM
H(
% /C6 > N
O > %&
n > K + % > L
enere el mensa?e a ser transmitido.
-
7/24/2019 TemaII-3.ppt
19/62
!5ica Di5ital
C3C puede ser representado usando un circuitocon compuertas H;3 y un re5istro dedespla)amiento.
El circuito es implementado*+ El re5istro contiene r#its la lon5 del /C62.
+ ,ay 7asta rcompuertas H;3.
+ !a presencia o ausencia de una compuertacorresponde con la presencia o ausencia de untermino en el divisor polinomial1 PH21 excluyendo eltrmino % y Hr.
-
7/24/2019 TemaII-3.ppt
20/62
3epresentacin Di5ital
P(X)= X5+X4+X2+1
-
7/24/2019 TemaII-3.ppt
21/62
Correccin de Errores
-
7/24/2019 TemaII-3.ppt
22/62
/EC* Principios
El al5oritmo /EC suma n'B2 #its al #lo$ue de datos de B #its. !os B #its en la se8al ori5inal se transmiten en la pala#ra cdi5o de
n #its. !a distancia de Hamming1 dv%1v(2 se define como el n &%%&%% y v( > %%&&&% dv%1v(2 > !a funcin de la forma vc > fvd2 donde vd es un vector de data de B
#its y vc la pala#ra cdi5o. Dentro de un #lo$ue de cdi5o n1B2 7ay (O cdi5os v"lidos de (n
cdi5os posi#les.
El radio de redundanciaie redundancia2 es n'B2AB. !a tasa del cdigoes BAn y mide la cantidad adicional de anc7o de
#anda $ue se necesita.
-
7/24/2019 TemaII-3.ppt
23/62
-
7/24/2019 TemaII-3.ppt
24/62
!a distancia mnima para una pala#ra cdi5o $ue consiste de0%10(1 =0s donde s > (n.dmin = minij [d(wi,wj)]
as siguientes condiciones se cumplen+ dmin-= t+1, el cdigo puede corregir hasta e incluendo t .its*
+ dmin-= t puede corregir todos los errores /= t01 .its loserrores de t .its pueden ser detectados*
tra forma de e2presar esta relacin es+ 3l m42imo n5mero de errores corregi.les es
t=[(dmin01)$] [2] el m4s grande de los enteros 6ue no e2cede 2*
+ 3l m42imo n5mero de errores 6ue pueden ser detectados es t=dmin01
/EC* Principios
-
7/24/2019 TemaII-3.ppt
25/62
/EC* E?emplo
B>( y n>L
6upon5a $ue sereci#e &&%&&.
El cual es un cdi5oinv"lido.
!a distancia de
,ammin5 a cadacdi5o v"lido es*
Bloque dedatos
Palabra Cdigo
&& &&&&&
&% &&%%%
%& %%&&%%% %%%%&
Distancia mnima
-
7/24/2019 TemaII-3.ppt
26/62
/EC* E?emplo
Obsrvese que si ocurren dos errores no se pueden corregir.
-
7/24/2019 TemaII-3.ppt
27/62
/EC* Principios
!as si5uientes consideraciones se de#en teneren el dise8o de un cdi5o de #lo$ue*+ Dado n y B1 nos 5ustara el valor m"s 5rande de dmin.+ El codificador de#era ser sencillo re$uiriendo un
mnimo de memoria y tiempo de procesamiento.+ os 5ustara un pe$ue8o n
-
7/24/2019 TemaII-3.ppt
28/62
/EC* Cdi5o de ,ammin5
Dise8ado para corre5ir errores de #it simples.
/amilia de #lo$ues de correccin de error (n,k)con los si5uientespar"metros*
+ !on5itud del #lo$ue* n > (m+ %
+ (m+ m + %+ m
+ Distancia mnima* dmin>
El proceso de codificacinAdescodificacin tiene la misma estructuradel /EC.
En el receptor el resultado de la comparacin H;3 de la se8alreci#ida y otra de la calculada2 es reali)ada.
El resultado se conoce como pala#ra sndrome.
-
7/24/2019 TemaII-3.ppt
29/62
/EC* Cdi5o de ,ammin5
!a pala#ra sndrome tiene un ran5o de (.n'B2+ %.
indica no error entonces no se cuenta.
Como un error puede ocurrir en los B #itsde data o n'B2 #it de c7e$ueo*
(.n'B2' % G> Bn'B2 > n
Esto nos permite calcular el n
-
7/24/2019 TemaII-3.ppt
30/62
/EC* Cdi5o de ,ammin5
Codificacin* k #its de datos (n 0k)#its de c7e$ueo. Decodificacin* compara los (n0k)#its reci#ido con los (n 0k)#its
calculados #its usando H;3. !os (n0k)#its resultantes se llamanpala.ra s7ndrome. El ran5o del sndrome esta entre & y (n'B2'%. El sndrome indica*
+ 6i contiene solo &s1 no se 7an detectados errores.+ 6i el sndrome contiene un solo #it en % entonces un error 7a ocurrido
en uno de los #its de c7e$ueo. Por lo tanto1 no se re$uiere correccin.+ 6i el sndrome contiene m"s de un #it en %1 entonces el valor numrico
del sndrome indica la posicin de un #it de data en error. El #it en errores invertido para su correccin.
-
7/24/2019 TemaII-3.ppt
31/62
/EC* Cdi5o de ,ammin5'E?emploBloque de datos = 00111001
-
7/24/2019 TemaII-3.ppt
32/62
/EC* Cdi5o de ,ammin5'E?emplo
Bit con error
-
7/24/2019 TemaII-3.ppt
33/62
Cdi5os Cclicos
Pueden ser codificados y decodificados usandore5istros !/63s2.
Para un cdi5o cclico1 un cdi5o v"lido c&1 c%1
=1 cn'%21 despla)ado 7acia la i)$uierda un #itcn'%1 c&1 =1 cn'(21 es tam#in un cdi5o v"lido.
!a entrada de lon5itud fi?a B2 toma y produce uncdi5o n'B2.
-
7/24/2019 TemaII-3.ppt
34/62
Codificacin* los B #its de data son usados como entrada paraproducir un cdi5o de c7e$ueo de n'B2 #its.
Decodificacin* la entrada reci#e un streamde #its de lon5itud n ieB #its de data se5uidos de n'B2 #its de c7e$ueo2.+ 6e procesan los #its reci#idos para calcular el cdi5o sndrome en la
misma manera $ue se calcularon los #its de c7e$ueo2.
+ 6i todos los #its del sndrome son cero1 no se 7a detectado error.
+ En caso contrario1 se e?ecuta procesamiento adicional del sndromepara corre5ir el error.
Cdi5os Cclicos
-
7/24/2019 TemaII-3.ppt
35/62
Par"metros*+ T > trama de n #its $ue se transmite.+ D > data de B #its de lon5itud los primeros B #its de
T2.
+ P > patrn de n+B%2 #its predeterminados.+ 4 > Cociente.+ C > 3esto.
3epresentacin polinomial* los coeficientescorresponden a los #its en el n
-
7/24/2019 TemaII-3.ppt
36/62
Para $ue TAP no ten5a resto entoncescomen)ar por*
!(8) = 8n0k;(8) +
-
7/24/2019 TemaII-3.ppt
37/62
6i uno o m"s errores ocurren el #lo$ue reci#idotendr" la forma*(8) = !(8) + 3(8)
EH2 es el polinomio de n #its con un % en cadaposicin de #it $ue es un error en QH2. 6i se pasa QH2 por el mismo !/63 se tiene*
(8)$%(8)= >(8) + ?(8)$(%(8)
6H2 es el sndrome de lon5itud n'B2 #its.
Cdi5os Cclicos
-
7/24/2019 TemaII-3.ppt
38/62
Cdi5os Cclicos
6e puede demostrar $ue EH2APH2 produce el mismoresto $ue QH2APH2 es decir 6H2APH2.(8)$%(8) = >(8)+?(8)$%(8)
(!(8)+3(8))$%(8) = >(8) + ?(8)$%(8)
&(8)+3(8)$%(8) = >(8) + ?(8)$%(8)3(8)$%(8)=[&(8)+>(8)]+ ?(8)$%(8)
Entonces 6H2 depende solo de los #its de error. -s $ue los #its de error se pueden corre5ir usando un
suma simple*(8) + 3(8) = !(8) + 3(8) + 3(8) = !(8)
-
7/24/2019 TemaII-3.ppt
39/62
Cdi5os Cclicos* E?emplo
Cdi5o J121 es decir1 n>J1 B>1 n'B >. PH2 > H@H(% %%&%. Para $ue un cdi5o se capa) de corre5ir errores
simples* nF> (n'B'%2 Ra $ue n>J > (@'%>J este cdi5o es capa) de
corre5ir un error.
Ver ta#la a2 a continuacin1 note $ue ladistancia mnima es 1 entonces se confirma loanterior de acuerdo lo $ue se muestroanteriormente.
-
7/24/2019 TemaII-3.ppt
40/62
Cdi5os Cclicos* E?emplo
-
7/24/2019 TemaII-3.ppt
41/62
Cdi5os Cclicos* E?emplo
Para cada patrn de error EH2 calcular el sndrome6H2.
Proceder como se muestra a continuacin para cadapatrn de error.
-s se o#tiene la ta#la #2 en la l"mina anterior.
110E(X)=X6
Cdi5o 9C,
-
7/24/2019 TemaII-3.ppt
42/62
Cdi5o 9C,
Para un par de enteros positivos m y t un cdi5o9C, n1B2 tiene los si5uientes par"metros*+ !on5itud del #lo$ue* n > (m+ %+ (t %
Corri5e com#inaciones de t o menos errores. Permite 5ran flexi#ilidad en la eleccin de los
si5uientes par"metros !on5itud del #lo$ue y tasa del cdi5o
-
7/24/2019 TemaII-3.ppt
43/62
Cdi5o 3eed'6olomon
6u# clase de lo cdi5os 9C,. !a data es procesada en tro)os de m #its1
llamados sm#olos.
:n cdi5o 36 n1B2 tiene los si5uientes par"metros*+ !on5itud del sm#olo* m #its por sm#olo+ !on5itud del #lo$ue* n > (m+ % sm#olos > m(m+ %2 #its+ !on5itud de la data* B sm#olos+ Tama8o del cdi5o de c7e$ueo* n + B > (t sm#olos >
m(t2 #its+ Distancia mnima* dmin > (t % sm#olos
-
7/24/2019 TemaII-3.ppt
44/62
Cdi5o 3eed'6olomon*3jemplo
?ea t=1 m=* ;enotemos los s7m.olos,1,,@ 6ue se pueden escri.ir en forma.inaria como =, 1=1, =1 @=11* 3l
cdigo tiene los siguientes par4metros+ n= 01 = @ s7m.olos = A .its+ (n0k) = s7m.olos = B .its
3ste cdigo puede corregir una r4faga deerrores 6ue se e2pande en un s7m.olo de .its
-
7/24/2019 TemaII-3.ppt
45/62
Sntercalamiento de #lo$ues
!a data es escrita y leda de la memoria en ordenes diferentes. :na tcnica muy com
-
7/24/2019 TemaII-3.ppt
46/62
-
7/24/2019 TemaII-3.ppt
47/62
Cdi5os Convolucionales
eneran #it redundantes continuamente. C7e$ueo y correccin de errores reali)ados continuamente.
Cdi5o representado como (n, k, C)*
El proceso de entrada procesa k#its en un determinado tiempo.
!a salida produce n#its por cada k #its de entrada. K> factor de restriccin
ky n5eneralmente muy pe$ue8os.
!a salida de n#its del cdi5o (n,k,C)depende de*
+9lo$ue en curso de k#its de entrada.+ !os K01 #lo$ues previos de k#its de entrada.
!a tasa de un cdi5o convolucional es BAn.
-
7/24/2019 TemaII-3.ppt
48/62
un-1,un-2
Codificacin
-
7/24/2019 TemaII-3.ppt
49/62
Cdi5os Convolucionales* Codificacin
Existen varias maneras de representar5r"ficamente un codificador convencional*+r#ol de cdi5o.
+ Enramado trellis2.+ Dia5rama de Estado.
-
7/24/2019 TemaII-3.ppt
50/62
Cdi5os Convolucionales *Descodificacin
El cdi5o de Viter#i es uno de los m"s importantesal5oritmos de correccin para los cdi5osconvolucionales.
Cdi5o de Viter#i + al5oritmo de correccin*
+ Compara la secuencia reci#ida con todas las posi#lessecuencias transmitidas.+ El al5oritmo eli5e el camino a travs del dia5rama de enramado
cuya posi#le secuencia transmitida difiere en el menor n
-
7/24/2019 TemaII-3.ppt
51/62
Dia5rama de Enramado del Codificador en la/i5ura Previa
-
7/24/2019 TemaII-3.ppt
52/62
Cdi5os Convolucionales * Descodificacin
Existen diversa variaciones del al5oritmode Viter#i.
Ellas dependen de la mtrica usada paramedir las deferencias entre lassecuencias reci#idas y las secuenciasvalidas.
:na de las mas comunes es usar ladistancia de ,ammin5.
-
7/24/2019 TemaII-3.ppt
53/62
Cdi5os Convolucionales * Descodificacin
El al5oritmo opera de la si5uiente manera* El al5oritmo procede en pasos o niveles1 ?. MF>?F>!1 M> K'% memoria del codificador1 ! es la lon5
de la secuencia del mensa?e entrante.
En cada nodo del enramado se comparan las dostrayectorias path2 $ue entran al nodo.
6e retiene la trayectoria con menor mtrica. Estas trayectorias se llaman so.reDiDienteso actiDas.
-
7/24/2019 TemaII-3.ppt
54/62
Cdi5os convolucionales * Descodificacin
Paso por paso el al5oritmo opera de la si5uientemanera*
Paso (nivel) 0:
+ 6e marca como & el estado m"s a la i)$uierda delenramado.
+ Pues en este punto no 7ay discrepancia.
+ 6e identifican todas las trayectorias so#revivientes.
+ 6e almacenan las trayectorias so#revivientes y sumtrica para cada estado del enramado.
-
7/24/2019 TemaII-3.ppt
55/62
Cdi5os Convolucionales * Descodificacin
Paso (nivel) j+1:+ 6e calcula la mtrica para todas las trayectorias $ue
entran en cada estado del enramado.+ Esto consiste en la suma del la mtrica de las
ramas entrantesa las mtrica de la traectoriasobreviviente conectora desde el !aso j.+ 6e identifican todas las trayectorias so#revivientes la
trayectoria con la mtrica m"s #a?a2.+ 6e almacenan las trayectorias so#revivientes y su
mtrica para cada estado del enramado.
-
7/24/2019 TemaII-3.ppt
56/62
Cdi5os Convolucionales * Descodificacin
Paso "inal:+ Continua el calculo 7asta $ue el al5oritmo completa su
#
-
7/24/2019 TemaII-3.ppt
57/62
;
-
7/24/2019 TemaII-3.ppt
58/62
;troE?emplo
-
7/24/2019 TemaII-3.ppt
59/62
n = 2, =1, !="#asa del c$digo 1%2
&ecuencia enviada0000000'
&ecuencia recibida0100010000'
Dmin &&1&%2 > %Dmin %%1&%2 > %
%%
&&
%&
&%
Dmin &&1&&2 > &2% >%Dmin %%1&&2 > (2%>dmin%&1&&2>%2%>(
dmin&%1&&2>%2%>(
-
7/24/2019 TemaII-3.ppt
60/62
-
7/24/2019 TemaII-3.ppt
61/62
Decodificacinincorrecta de la
secuencia depuros ceros
recibidas
&ecuencia enviada0000000'&ecuencia recibida1100010000'
-
7/24/2019 TemaII-3.ppt
62/62
3evisar este !inB
7ttp*AA000.#rian?osep7.comAviter#iA0orBs7op.7tm