codificacion canal

TEMA 5

TECNICAS DE PROTECCION FRENTE A ERRORES(CODIFICACION DE CANAL)

MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 1 / 99

Indice

Introduccion y definicionesCodigos bloque linealesCodigos convolucionalesCodigos de rejillaCodigos BCH y codigos RSProteccion frente a ruido impulsivo: intercalado yconcatenacion de codigosEsquemas avanzados de codificacion

Turbo codificacionCodigos LDPC


Introduccion

Los sistemas de comunicaciones comenten erroresObjetivo de un sistema de comunicaciones

BER < CalidadAlternativas para reduccion de los errores

Aumentar la energa de la senalLimitaciones: Econonicas, fsicas, legales, interferencias, ...

Teorema de codificacion de canales con ruido (Shannon)Introduccion de bits de redundanciaTasa de codificacion: R (bits de datos/bits transmitidos)Capacidad del canal: C (bits/uso)Posibilidad de reduccion de la BER de forma arbitraria

R < C


Capacidad de canal - Canales digitales

Modelo de canal discreto sin memoria (DMC)Entrada y salida: variables aleatorias X e YProbabilidades de transicion pY|X(yj|xi)

Capacidad de canal

C = maxpX(xi)

I(X,Y) bits/uso

Ejemplo: Canal binario simetrico (BER=)

-

-

*

HHHHHHHHHHHH

HHHHHHHHHj

s

s

s

sx0

x1

y0

y11

1

C = 1 Hb() bits/usoMMC (UC3M) Comunicaciones Digitales Codificacion de Canal 4 / 99

Entropa binaria Hb(p)

Entropa de una v.a. binaria con pX(x0) = p y pX(x1) = 1 p

Hb(p) = p log2(p) (1 p) log2(1 p)

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.10.20.30.40.50.60.70.80.91

.

...................................................................................................

.

..................................................................

.

.....................................................

..............................................

....................................

................................

...........................

. .......................... ......................... . ....................... . ....................... . ........................ . .......................... .

...........................

......................

..........

.....................................

......................................

.......

....................................

.................

.

..................................................................

.

...................................................................................................

Probabilidad p

Ent

ropi

abi

naria

Hb(p)


Capacidad de canal - Canal gausiano

Capacidad sobre canal gausiano en las siguientescondiciones:

Potencia transmitida: P watt.Potencia de ruido: PN watt.Ancho de banda: B Hz

C =1n

logM =12

log(

1 +PPN

)PN =

BB

No2df = NoB

C =12 log

(1 +

PNoB

)bits/uso

C = B log (1 + SNR) bits/s


Cotas

Capacidad en funcion de B

lmB

C =PNo

log2(e) = 1,44 PNo

Sistema de comunicaciones practico

Rb < B log (1 + SNR) bits/sTasa binaria (eficiencia) espectral: = RbB bits/s/Hz

Energa media por bit - Eb = PRb

Relacion Eb/N0 = SNR

< log (1 + SNR) , < log(

1 + EbNo

)SNR > 2 1, Eb

No>

2 1

Cuando 0 EbNo = ln2 = 0,693 1,6 dBMMC (UC3M) Comunicaciones Digitales Codificacion de Canal 7 / 99

Tasa binaria (eficiencia) espectral frente a Eb/N0

-

6

........................................................................................................................................................

.......... ............................

........ .................... ............. ........

.......... ........... ........................ .............. ............... ............

.............. ................ ............. .............. ............................. ............... ................ .............. ............... ................

............................................101

101

1

0 5 10 15 20 EbNo dB

= RbB

1,592

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

..........

.....


Relacion senal a ruido normalizada

Cota inferior para SNR

SNR > 2 1

Definicion de SNR normalizada

SNRnorm =SNR

2 1Cota inferior sobre SNRnorm

SNRnorm > 1 (0 dB)


Tipos de codigos

Capacidad del codigoCodigos de deteccion de erroresCodigos de correccion de errores

Mecanismo de introduccion de la redundanciaCodigos bloque

Bloques de k bits se codifican de forma independienteConcepto clave: distancia entre palabras codigo

Codigos convolucionalesCodificacion continua mediante filtrado digital

Estadstico para la decisionSalida dura: decodificacion a partir de los bits decididos B[`]Salida blanda: decodificacion a partir de la salida deldemodulador q[n]

Mejores prestaciones pero mayor complejidad

Borrado de bits: se marcan los bits/smbolos dudosos


Ganancia de codificacion

Definicion: diferencia en decibelios entre las relacionesEb/N0 necesarias para alcanzar una determinada BER sincodificar y utilizando la codificacionPermite comparar las prestaciones de distintos codigosDepende de la BER (o de Eb/N0)Puede ser positiva a partir de un cierto valor de Eb/N0


Codigos bloque - Definiciones

Codificacion independiente de bloques de k bitsConversion en bloques de n bits Tasa R = k/n

Definiciones para los bloques de bitsInformacion: bi = [bi[0], bi[1], , bi[k 1]], i = 0, 1, , 2k 1Codificados: ci = [ci[0], ci[1], , ci[n 1]], i = 0, 1, , 2k 1Codificacion: bi ciDiccionario del codigo: mensaje palabra codigo

Peso de una palabra codigo w(ci)Numero de unos de la palabra

Distancia de Hamming entre dos palabras codigo dH(ci, cj)Numero de bits diferentes entre ambas palabras

Distancia mnima del codigo: dminMnima distancia de Hamming entre dos palabras codigodistintas


Estimador optimo - Salida dura

Observacion condicionada a la transmision de ci

r = ci + e, e = [e[0], e[1], , e[n 1]]Modelo probabilstico del patron de error (BER = )

pE(e[j]) = e[j] (1 )1e[j] ={, e[j] = 11 , e[j] = 0

Verosimilitud

pr|c(r|ci) =n1j=0

r[j]ci[j] (1 )1(r[j]ci[j])

Estimador de maxima verosimilitud (ML)

ci = arg mnci

dH(r, ci)


Capacidades de deteccion y correccion con salida dura

Distancia mnima del codigo: dminCapacidad de deteccion: d = dmin 1 erroresCapacidad de correccion:

t =dmin 1

2

errores


Estimador optimo - Salida blanda

Constelacion: M smbolos (m = log2(M) bits/smboloSecuencia de smbolos para una palabra codigo

ci Ai = [Ai[0],Ai[1], ,Ai[n 1]], n = nmModelo de la observacion condicionada a ci

q = Ai + e, e = [e[0], e[1], , e[n 1]]

Modelo probabilstico del error: fE(e[j]) = N(0, 2z )Verosimilitud: fq|A(q|Ai) = N(Ai, 2z )Estimador de maxima verosimilitud

c = arg mnide(q,Ai)


Codigos bloque lineales

Codigo C(k, n)Base del codigo: k palabras codigo linealmenteindependientes

{g0, g1, , gk1}gi = [gi[0], gi[1], , gi[n 1]]

Palabra codigo: combinacion lineal de las k bases

ci = bi[0] g0 + bi[1] g1 + + bi[k 1] gk1Propiedades

c0 = 0 = [0, 0, , 0] pertenece al codigoTodos los elementos de la base pertenencen al codigoToda combinacion lineal de palabras codigo C(k, n)Todas las palabra tienen a otra palabra a distancia dmindmin = mn

ci 6=c0w(ci)


Matriz generadora del codigo

Agrupacion de la base en una matriz k n

G =

g0g1...

gk1

=

g0[0] g0[1] g0[n 1]g1[0] g1[1] g1[n 1]

...... . . .

...gk1[0] gk1[1] gk1[n 1]

Obtencion de las palabras codigo

ci = bi GCodigos sistematicos: el mensaje bi forma parte de ci

ci = [bi|pi] G = [Ik|P]ci = [pi|bi] G = [P|Ik]


Matriz generadora del codigo - Ejemplo

Codigo C(2, 5)

G =[

0 1 1 1 01 0 1 0 1

]Palabras codigo

bi ci0 0 0 0 0 0 00 1 1 0 1 0 11 0 0 1 1 1 01 1 1 1 0 1 1

Codigo sistematicoDistancia mnima del codigo: dmin = 3

Detecta 2 erroresCorrige 1 error


Matriz de chequeo de paridad

Matriz (n k) n: complemento ortogonal de GG HT = 0 matriz de k (n k) ceros

Codigos sistematicos

G = [Ik|P] H = [PT |Ink]G = [P|Ik] H = [Ink|PT ]

Identificacion de palabras codigo

ci HT = bi G HT = 0 vector de n k cerosDecodificacion mediante sndrome

Modelo de transmision: r = ci + e (e: patron de error)Sndrome

s = r HT = (ci + e) HT = e HT

Decodificacion: Tabla de sndromesMMC (UC3M) Comunicaciones Digitales Codificacion de Canal 19 / 99

Matriz de chequeo de paridad - Ejemplo

G =[

0 1 11 0 1

1 00 1] H =

1 0 00 1 00 0 1

0 11 01 1

Tabla de sndromes

e s0 0 0 0 0 0 0 01 0 0 0 0 1 0 00 1 0 0 0 0 1 00 0 1 0 0 0 0 10 0 0 1 0 0 1 10 0 0 0 1 1 0 1

? 1 1 0? 1 1 1

110 e1 = 11000, e2 = 00011, e3 = 10110, e4 = 01101Posibilidad: elegir uno de los dos patrones de dos errores


Ventaja de trabajar con G y H

Numero de palabras del codigo: 2k

k = 2, n = 5: 4 palabrask = 247, n = 255: 2247 2,26 1074 palabras

Numero de sndromes posiblesk = 2, n = 5 (t = 1): 8 sndromesk = 247, n = 255 (t = 1): 256 sndromes


Metodo de eliminacion - Ejemplo

Sustitucion de filas por combinaciones lineales de otras1a fila: 1a+2a filas2a fila: 1a fila

Codigo C(2, 5)

G =[

1 1 0 1 10 1 1 1 0

]Palabras codigo

bi ci0 0 0 0 0 0 00 1 0 1 1 1 01 0 1 1 0 1 11 1 1 0 1 0 1

Mismas palabras codigos / distintas asignacionesLa misma matriz H es valida para generar la tabla desndromes


Lmite de Hamming

Numero de sndromes con redundancia r = n k:2nk = 2r

Lmite de Hamming para corregir t errores

r log2 V(n, t), V(n, t) =t

j=0

(nj

)

V(n, t): Esfera de Hamming de radio tInterpretacion con numero de sndromes disponibles(

00

)+

(n1

)+ +

(nt

) 2r

Igualdad: Codigos perfectos


Codigos perfectos

Codigos de repeticion (decision por mayora)n impar, k = 1, t = (n 1)/2

Codigos de Hammingn = 2m 1, k = 2m m 1, t = 1Matriz de chequeo: en las columnas aparecen todas lasposibles combinaciones binarias de (n k) bits, excepto latodo ceros

Ejemplo: Codigo Hamming (4,7)

H =

1 0 0 0 1 1 10 1 0 1 0 1 10 0 1 1 1 0 1

Codigo de Golay

n = 23, k = 11, t = 3


Prestaciones - Decodificacion dura

Probabilidad de error de bit (BER): Se comenten errores cuando se excede la capacidad decorreccion del codigoCodigo de correccion de t errores

Pe =n

j=t+1

(nj

) j (1 )nj

Codigos que corrigen todos los patrones de t errores y apatrones de t + 1 errores

Pe =[(

nt + 1

) a]t+1 (1)nt1 +

nj=t+2

(nj

)j (1)nj

Codificacion tipo Gray o pseudo-Gray

BER 1kPe


Prestaciones - Decodificacion blanda

Probabilidad de error

Pe c Q(

demin2N0/2

)demin: mnima distancia eucldea entre las secuencias desmbolos correspondientes a dos palabras codigodiferentesc: maximo numero de palabras de distancia mnima de unadada

Modulaciones binarias

de(ci, cj) = d(a0, a1)dH(ci, cj)

Pe c Q(d(a0, a1)2N0/2

dmin

)MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 26 / 99

Codigos cclicos

Codigos bloque linealesDefinicion: si ci = [ci[0], ci[1], , ci[n 1]] C(k, n),entonces ci = [ci[1], , ci[n 1], ci[0]] C(k, n)Caracterizacion mediante un polinomio generador g(x)

Codificacion: multiplicacion por el polinomioDecodificacion: division por el polinomioImplementacion mediante registros de desplazamiento


Codificacion/Decodificacion

Representaciones polinonicasPolinomio generador: g(x), grado n kPolinomio de chequeo: h(x), tal que g(x) h(x) = xn 1Palabras mensaje: b(x), grado k 1Palabras codigo y recibida: c(x), r(x), grado n 1Sndrome: s(x), grado n k 1

Codificacion

c(x) = b(x) g(x) mod xn 1Decodificacion

s(x) = r(x) h(x) mod xn 1r(x) = a(x) g(x) + s(x)

Division por g(x) y quedarse con el resto


Ejemplo: codigo C(4, 7)

Polinomio generador: g(x) = x3 + x + 1Mensaje: b = [0 1 0 1] b(x) = x2 + 1Palabra codigo

c(x) = (x2 + 1) (x3 + x + 1) = x5 + x2 + x + 1

c = [0 1 0 0 1 1 1]


Codificacion mediante registros de desplazamiento

n registrosRamas con sumadores: indicadas por el polinomioSe introduce el mensaje bit a bitLa palabra codificada corresponde a los bits en losregistros al final del proceso

- - n?- - - n?- - - -


Ejemplo b = [0101]

[0 1 0 1]

- 0 - k?- 0 - 0 - k?- 0 - 0 - 0 - 0[0 1 0 1]

- 1 - k?- 1 - 0 - k?- 1 - 0 - 0 - 0[0 1 0 1]

- 0 - k?- 1 - 1 - k?- 0 - 1 - 0 - 0[0 1 0 1]

- 1 - k?- 1 - 1 - k?- 0 - 0 - 1 - 0MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 31 / 99

Codigos de Hamming

Existen implementaciones cclicasAlgunos ejemplos:

m = 3 (n = 7, k = 4): g(x) = x3 + x + 1m = 4 (n = 15, k = 11): g(x) = x4 + x + 1m = 5 (n = 31, k = 26): g(x) = x5 + x2 + 1m = 6 (n = 63, k = 57): g(x) = x6 + x + 1m = 7 (n = 127, k = 120): g(x) = x7 + x3 + 1m = 8 (n = 255, k = 247): g(x) = x8 + x4 + x3 + x2 + 1m = 9 (n = 511, k = 502): g(x) = x9 + x4 + 1m = 10 (n = 1023, k = 1013): g(x) = x10 + x3 + 1


Codigos Golay

k = 12, n = 23, t = 3 (dmin = 7)Codigo cclico

g1(x) = x11 + x10 + x6 + x5 + x4 + x2 + 1g2(x) = x11 + x9 + x7 + x4 + x3 + x2 + x + 1

Polinomios de chequeo de paridadh1(x) = x12 + x11 + x10 + x9 + x8 + x5 + x2 + 1h2(x) = x12 + x10 + x7 + x4 + x3 + x2 + x + 1

Codigo de Golay extendidoAnade un bit de paridadTasa 1/2 (facilidad de implementacion)Capacidad de corregir el 19 % de patrones de 4 errores


Codigos cclicos sistematicos

Definicion de la palabra codigo

c(x) = b(x) xnk + d(x)

d(x) = resto de(b(x) xnk

g(x)

)Ejemplo: b(x) x3 = x5 + x3

x5 + x3 = x2 (x3 + x + 1) + x2 d(x) = x2

c(x) = x5 + x3 + x2 c = [0 1 0 1 1 0 0]


Division con registros de desplazamiento

n k registrosRamas con sumadores: indicadas por g(x)Se introduce bit a bit b(x) xnkEl resto es el contenido final de los registros

-?- -?- - -


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?0 - 0 -?- 0 - 0 -0


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?1 - 1 -?- 0 - 0 -0


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?0 - 0 -?- 1 - 0 -0


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?1 - 1 -?- 0 - 1 -0


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?0 - 1 -?- 0 - 0 -1


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?0 - 0 -?- 1 - 0 -0


Ejemplo b = [0101]

[0 1 0 1 0 0 0]

-?0 - 0 -?- 0 - 1 -0Resto: d(x) = x2 (igual que antes)Reduccion de iteraciones: colocar en los registros los datoscorrespondientes a las k primeras iteraciones


Decodificador codigos sistematicos

Tomar la parte sistematica y volverla a codificar: d(x)Definicion del sndrome

s(x) = d(x) d(x)

Generacion de tabla de sndromes para decodificacion


Limitaciones de los codigos bloque

Tamano de la tabla de sndromes - Crecimientoexponencial

Ejemplo: n = 23, t = 1: 23 entradasEjemplo: n = 23, t = 2: 276 entradasEjemplo: n = 23, t = 3: 2047 entradas

Prestaciones relacionadas con la distancia mnimaSu calculo requiere conocer las palabras del codigoNo hay aproximaciones constructivas para obtener una dmin


TEMA 5

TECNICAS DE PROTECCION FRENTE A ERRORES(CODIGOS CONVOLUCIONALES)


Codigos convolucionales

Introduccion de la redundancia mediante filtradoIntroduccion de memoria

Tasa R = k/n: Banco de filtros conk entradasn salidas

-B(0)[`]

D - D - D

-C

(0)[`]

-C(1)[`]

.

.......................................................................................................................................................................................................................................................................................................................................

.

........................................................................................................................................................................................................................................

................................................................................................

........................................................................................

........................................................................................

...............................

.

...................................................................................................

......................

......................

......................

......................

..........

Notacion:Entradas: B(i)[`], con i = 0, 1, , k 1Salidas: C(j)[`], con j = 0, 1, , n 1


Representaciones

Esquematica

-B(0)[`] D - D - D

ii-C(0)[`]

-C(1)[`]

.....................................................................................................................................................................................................

.....................................................................................................................

.................................................................................

........................................................................................

....................................

.

............................................................

......................

......................

...............

Relacion entrada salidas

C(0)[`] = B(0)[`] + B(0)[` 1] + B(0)[` 3]C(1)[`] = B(0)[`] + B(0)[` 1] + B(0)[` 2] + B(0)[` 3]

Notacion mediante polinomios en D

B(i)(D) =`

B(i)[`] D`

PropiedadB(i)[` d] B(i)(D) Dd


Representaciones (II)

Notacion mediante polinomios en D

C(0)(D) = B(0)(D){

1 + D + D3}

C(1)(D) = B(0)(D){

1 + D + D2 + D3}

Notacion matricial (polinomios):

C(D)1n = B(D)1k G(D)knMatriz generadora de tamano k n

Elemento fila i columna j: contribucion a la salida j-esima dela entrada i-esimaEjemplos

Ejemplo anterior (A): k = 1, n = 2

G(D) =[1 + D + D3, 1 + D + D2 + D3

]12

Otro ejemplo (B): k = 2,

G(D) =[

1 + D D DD 1 D

]23


Paso a representacion esqumatica - Ejemplo B

G(D) =[

1 + D D DD 1 D

]23

Numero de entradas: k = 2Numero de salidas: n = 3

-B(0)[`]

D

-B(1)[`]

D

-C(0)[`]

-C(1)[`]

-C(2)[`]

.

.................................................................................................................

........................

........................

........................

........................

.................

.......................................................................................................................................................................................................................................................................................

.

........................................................................................................................................................................................................................................................................................

........................

........................

........................

........................

................


Parametros de interes

Memoria total del codigo: MtNumero total de unidades de retardo (memorias)

Mt =k1i=0

M(i)

Memoria de la entrada i-esima: M(i) = maxj

grado(gi,j(D))

Longitud de restriccion: KMaxima longitud de la respuesta al impulso del codificador(maximo numero de instantes de tiempo en los que un bitafecta a la salida del codificador)

K = 1 + maxi,j

grado(gi,j(D))

En general las prestaciones aumentan con K


Codigos sistematicos

Matriz de generacion

G(D) = [Ik P(D)]

Las entradas se copian en algunas de las salidasEjemplo (C)

G(D) =[1, 1 + D + D2

]

-B(0)[`]

D - D

-C

(0)[`]

-C(1)[`].

..........................................................................................................................................................

................................................................

.

......................

......................

......................

......................

..........


Diagrama de rejilla

Definicion del estadoContenido de las memorias del codificador

[`] = [B(0)[`1], ,B(0)[`M(0)], ,B(k1)[`1], ,B(k1)[lM(k1)]]Etiquetado de la rejilla

Bits a la entrada del codificadorBits a la salida del codificador

B(0)[`],B(1)[`], B(k1)[`] C(0)[`],C(1)[`], C(n1)[`]


Ejemplo - Convolucional D

Estado: [`] =[B(0)[` 1],B(0)[` 2]]

Estados: 0 = [0, 0], 1 = [1, 0], 2 = [0, 1], 3 = [1, 1]

- D - D

- k- k

-

?

-

B(0)[`]

C(0)[`]

C(1)[`]

rrrr

rrrr

. ......................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................

.

...............................................................................................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................................................................................................................................................

.

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

...................................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

...........

.

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

................................... .....................................................................................................................................................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

[n] [n + 1]0

1

2

3


Ejemplo - Convolucional E

Estado: [`] =[B(0)[` 1],B(0)[` 2]]

Estados: 0 = [0, 0], 1 = [1, 0], 2 = [0, 1], 3 = [1, 1]

-B(0)[`]

D - D

- k-

-C(0)[`]

C(1)[`]

rrrr

rrrr

. ......................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................

.

...............................................................................................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................................................................................................................................................

.

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

...................................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

............................

...........

.

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

................................... .....................................................................................................................................................................................................................................................................................................

0|00

1|010|10

1|110|01

1|000|11

1|10

[n] [n + 1]0

1

2

3


Secuencia de bits - Camino a traves de la rejilla

Secuencia de datos: B(0)[`] = [11010]Estado inicial: 0 (Se fija con el envo de una cabecera debits)

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

[0] [1] [2] [3] [4] [5]

0

1

2

3

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

Secuencia codificada: C[k] = [11 10 10 00 01]


Decodificacion - Algoritmo de Viterbi

Recuperacion de la secuencia mas verosmilEstados inicial/final

Cabecera de referencia (habitualmente ceros bit flushing)Salida dura: observacion de bits decididos

Secuencia con el menor numero de bits codificados distintosa la observacionMetrica de rama: distancia de Hamming con la observacion

Salida dura: observacion de q[n]Secuencia cuyos smbolos asociados estan a la menordistancia eucldea de la observacionMetrica de rama: |q[n] A[n]|2

Hay que tener en cuenta la constelacion que se utiliza parahacer la conversion de las etiquetas de la rejilla basica asmbolos de la constelacion (A[n])

Mejores prestaciones que con salida blanda


Metricas de rama - Salida dura

Secuencia recibida: R[k] = [11 10 10 00 01]

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

[0] [1] [2] [3] [4] [5]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

2

01

10

21

1

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

1

12

01

10

2

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

1

12

01

10

2

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0

21

12

01

1

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

1

10

21

12

0







Metricas acumuladas en cada estado (Viterbi)

[1] [2] [3] [4] [5]3 0 2/3 3/4 3/22 2 0/5 3/4 0/01 0 3 3/4 0/5 4/30 2 3 3/4 2/3 4/3

Si no hay errores: camino con metrica acumulada nula


Metricas de rama - Salida blanda

Secuencia recibida: q[n] =[

1,10,9

] [1,10,8

] [0,750,6

] [1,21,1

] [0,71,2

]

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

s

s

s

s+11

+1

100

01

10

11

[0] [1] [2] [3] [4] [5]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

8,02

0,024,42

3,620,02

8,023,62

4,42

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

4,45

3,257,65

0,053,25

4,450,05

7,65

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

3,22

2,625,62

0,222,62

3,220,22

5,62

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

0,05

9,254,45

4,859,25

0,054,85

4,45

ssss

ssss

. .........................................................................................................................................................................

....................................................................................................................................................................................................

.

.....................................................................................................................................................................................................

................................................................................................................................................................................................................................

.

..........................................

..........................................

..........................................

..........................................

.............................

........................

........................

........................

........................

........................

........................

........................

........................

........................

........

.

..........................................

..........................................

..........................................

..........................................

............................. ........................................................................................................................................................................

4,93

2,930,13

7,732,93

4,937,73

0,13







Metricas acumuladas en cada estado (Viterbi)

[1] [2] [3] [4] [5]3 0,07 5,69/11,49 10,14/15,74 10,27/8,072 7,67 0,29/16,89 10,54/15,34 17,87/0,471 0,02 11,27 10,89/15,09 0,34/19,54 15,47/12,470 8,02 12,47 10,29/15,69 9,54/10,34 13,47/14,47


Prestaciones

Salida dura

Pe c nzi=t

(n zi

) i (1 )nzi

DHmin: mnima distancia de Hamming entre salidas parasecuencias distintasz: longitud del evento erroneo de distancia mnimat =

DHmin1

2

(capacidad de correccion sobre n z bits)

: probabilidad de error de bit del sistema (BER)Salida blanda

Pe c Q(

Demin2N0/2

)Demin: mnima distancia eucldea entre salidas parasecuencias distintas


Calculo de DHmin

Comparacion con la secuencia de todo ceros

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

0

1

2

3

rrrr

rrrr

.

..........................................................................................................................................................

2

2

rrrr

.

...........................................................................................................................................................

..................................................................................................................................................................................................................

1

1

3

3

rrrr. ................................................................................................................................................

..................................

..................................

..................................

..................................

.

.

..................................

..................................

..................................

..................................

...................

........................

........................

........................

........................

........................

........................

........................

........................

..................

1

1

0

2

4

4

3

5

DHmin = 5

z = 3


TEMA 5

TECNICAS DE PROTECCION FRENTE A ERRORES(CODIGOS DE REJILLA (TCM))


Codigos de rejilla

Conocidos tambien como codigos TCMTrellis Coded Modulation

Diseno conjunto de codigos convolucionales y delcodificador del transmisorUso eficiente del ancho de banda de un canal

La redundancia se introduce aumentando el orden de laconstelacion

Orden de la constelacion acorde al tamano de la salidacodificada

Posibilidad de tasas relativamente altas mediante lastransiciones paralelo


Codigos de rejilla - Definiciones

Convolucionalknp, nnp

...knp ... nnp

...kp npConstelacionn = np + nnpbits/smbolo

k entradaskp transiciones paralelo (sin proteger)knp transiciones no paralelo (protegidas)

n salidasnp = kp transiciones paralelo (sin proteger)nnp transiciones no paralelo (protegidas)

Constelacion: 2n smbolos (n = np + nnp bits/smbolo)MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 59 / 99

Codigos de rejilla - Asignacion de bits

Reglas de diseno: reglas de UngerboeckAsignacion para minimizar la probabilidad de errorDivision de la constelacion + asignacion de bits

Division de la constelacion en subconstelacionesDivision sucesiva aumentando la distancia mnimaSmbolos por subconstelacion: 2npNumero de subconstelaciones: 2nnp

Asignacion de bitsTransiciones paralelo: seleccion de un smbolo dentro de lasubconstelacion

Proteccion fsica sobre la constelacion (Gray)Transiciones no paralelo: seleccion de una subconstelacion

Proteccion mediante codigo convolucionalMaxima distancia: ramas que salen de o llegan a un mismoestadoEquiprobabilidad en la asignacion de smbolos


Ejemplo: kp = 1, knp = 1, nnp = 2, 8-PSK

Codigo de tasa 2/3Una transicion en paraleloConvolucional de tasa 1/2 (Convolucional Ejemplo D)

Convolucional1/2

Constelacion3 bits/smbolo

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

Constelacion con 3 bits por smbolo: 8 smbolos8-PSK


Ejemplo: Division de la constelacion

s s sssss s

s c scscs cB0 c s cscs

c sB1

s c ccscc c

C0 c c scccs c

C1 c s cccsc c

C2 c c csccc s

C3


Ejemplo: Asignacion de las transiciones no paralelo

[n] [n + 1]

0

1

2

3

xxxx

xxxx

. ................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................................................................

.

.......................................................................................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..........................................................

..........................................................

..........................................................

...........................

................................

................................

................................

................................

................................

................................

................................

................................

................................

................................

................................

................................

.............................

.

..........................................................

..........................................................

..........................................................

..........................................................

..........................................................

..........................................................

........................... ...............................................................................................................................................................................................................................................................................................................................................

C0

C1C2

C3C1

C0C3

C2


Asignacion (convolucional D)

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

0|00

1|110|01

1|100|11

1|000|10

1|01

[n] [n + 1]

0

1

2

3

ssss

ssss

. .........................................................................................................................................................................

...........................................................................................................................................................................................

.

............................................................................................................................................................................................

...............................................................................................................................................................................................................

.

..........................................................

..........................................................

..........................................................

..............

................................

................................

................................

................................

................................

................................

...............

.

..........................................................

..........................................................

..........................................................

.............. ........................................................................................................................................................................

C0

C1C2

C3C1

C0C3

C2

s sssss

ss 0|00 1|01

0|10

0|111|10

0|11

1|000|01


Prestaciones

Distancia mnima del codigo - La mnima de:Distancia mnima paraleloEjemplo anterior (constelacion normalizada): dp = 2

Mnima distancia entre puntos de las subconstelacionesDistancia mnima no paralelo

Distancia del convolucional medida sobre lassubconstelacionesEjemplo anterior

dnp =d2(C0,C1) + d2(C0,C2) + d2(C0,C1) = 2,14

Ganancia de codificacionComparacion con la constelacion equivalente sin codificar(misma velocidad de transmision efectiva)Ejemplo anterior: 4-PSK

G =ESCbETCMb

(dTCMmin

)2(dSCmin

)2 = 2 (3 dB)MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 65 / 99

TEMA 5

TECNICAS DE PROTECCION FRENTE A ERRORES(CODIGOS BCH)


Campos finitos (Campos de Galois)

Definicion de campoConjunto de elementos sobre el que es posible definir dosoperaciones, suma (resta) y producto (division, excepto porel elemento nulo), y dos elementos distinguidos, elementonulo (0), elemento unidad (1), que cumplen las siguientespropiedades:

AsociativaConmutativaDistributiva

Campo finitoNumero finito, q, de elementos del campo: Orden q, GF(q)Orden primo: pn con p primo y n enteroConstruccion:

Polinomio irreducible de grado n y coeficientes en GF(p)


Campos finitos GF(2m)

Modelo para grupos de m bits (m-tuplas)Representaciones de los miembros del campo

Polinomios en de grado m 1Tupla Polinomio000 0001 1010 011 + 1

Tupla Polinomio100 2

101 2 + 1110 2 + 111 2 + + 1

Potencia de (j, para j = , 0, 1, ,m 2)Restriccion sobre m para el producto (consistencia)

Polinomio generadorCoeficientes binarios (p = 2)Ejemplo: p(x) = x3 + x + 1Restriccion: 3 = + 1


Definiciones

Polinomio irreduciblePolinomio que no se puede factorizar

Polinomio primitivop(x) de grado m es primitivo si el menor entero n para el quep(x) divide a xn 1 es n = 2m 1

Polinomio minimal de i

Polinomio de menor grado con i como raz (polinomio concoeficientes binarios)


Polinomio generador

Polinomio irreduciblePolinomio primitivoPolinomio de grado m es una raz del polinomio restriccion sobre m

p() = 3 + + 1 = 0 3 = + 1Polinomio primitivo restriccion de periodicidad

p(x) divide a xn 1 (con n = 2m 1)n = 1 = 0

Periodicidad exponencial de perodo nElementos del campo

Resto del cociente con p() (polinomio)Ejemplo: 3 + 2 + + 1 = (+ 1) + 2 + + 1 = 2

3 + 2 + + 1 = (3 + + 1) 1 + 2MMC (UC3M) Comunicaciones Digitales Codificacion de Canal 70 / 99

Adjudicacion de j a una tupla

Utilizacion de la restriccion del polinomio generador

j Polinomio Tupla = 0 0 0000 = 1 1 0011 0102 2 1003 + 1 0114 (3) = 2 + 1105 3 + 2 = 2 + + 1 1116 3 + 2 + = + 1 + 2 + = 2 + 1 1017 3 + = + 1 + = 1

Periodicidad de perodo n = 2m 1:n = 0 (k = k%n)


Polinomios minimales - Cosets ciclotomicos

Coset ciclotomicoConjunto que agrupa a las raices que comparten lospolinomios minimalesExponentes de las raices agrupadas en el coset Ci

{i, 2i, 22i, , 2zi1i}zi: mnimo valor que cumple 2

zi i = i

Races Polinomio minimal0 x

C0 = 1 x + 1C1 = {, 2, 4} x3 + x + 1C3 = {3, 6, 5} x3 + x2 + 1

Races de xn 1: 0 (1),, 2, , n1x7 1 = (x 1) (x ) (x 6)

Producto de los polinomios minimales de los cosetsx7 1 = (x + 1) (x3 + x + 1) (x3 + x2 + 1)


Formacion de los cosets (ejemplo)

Coset C0C0 = {1}, 12 = 1

Coset C1C1 =

{, 2, 4

}, 8 =

Coset C2: 2 ya esta incluido en C1Coset C3

C3 ={3, 6, 12 = 5

}, 24 = 3


Formacion de los polinomios binarios

Agrupamiento de races distintas a todas las de un coset

p(x) = (x ) (x 2) = x2 ( + 2) x + 3

Polinomio con coeficientes no binariosPolinomio minimal de C1

p1(x) =(x ) (x 2) (x 4)=(x2 ( + 2) x + 3) (x 4)=x3 ( + 2 + 4) x2 + (3 + 5 + 6) x 7=x3 + ( + 2 + 2 + ) x2

+ ( + 1 + 2 + + 1 + 2 + 1) x 1=x3 + x + 1


Codigos BCH

Acronimo de Bose, Chaudhuri y HocquenghemCodigos versatiles y constructivos

Cualquier distancia mnimaCualquier longitud de codigo impar (n impar)Permite el diseno de codigos no binariosCasos particulares interesantes

HammingGolayReed Solomon (no binario)

Algoritmo eficiente de decodificacionPrincipio basico para su diseno

Teorema BCH


Teorema BCH (simplificado) - Diseno de codigos BCH

Un codigo cclico C(k, n) con un polinimio generador g(x)que tiene 1 races consecutivas en un campo GF(2m),con el menor m tal que 2m 1 sea multiplo de n, es uncodigo cclico que garantiza un distancia mnima

dmin Codigo con capacidad de correccion de t errores

Distancia mnima dmin 2 t + 1Buscar un entero m tal que n = 2m 1 (o n divisor de 2m 1)Agrupar dmin 1 races consecutivas en GF(2m)

Obtencion del polinomio generador g(x)Utilizacion de los polinomios minimales coeficientes binariosTamano del codigo: grado(g(x))=n k


Ejemplo: n = 63

m = 6Polinomio generador p(x) = x6 + x + 1Cosets y polinomios minimales

Elementos del coset Polinomio minimal

C0 ={0 = 1

}p0(x) = x + 1

C1 ={1, 2, 4, 8, 16, 32

}p1(x) = x

6 + x + 1

C3 ={3, 6, 12, 24, 33, 48

}p3(x) = x

6 + x4 + x2 + x + 1

C5 ={5, 10, 17, 20, 34, 40

}p5(x) = x

6 + x5 + x2 + x + 1

C7 ={7, 14, 28, 35, 49, 56

}p7(x) = x

6 + x3 + 1

C9 ={9, 18, 36

}p9(x) = x

3 + x21

C11 ={11, 22, 25, 37, 44, 50

}p11(x) = x

6 + x5 + x3 + x2 + 1

C13 ={13, 19, 26, 38, 41, 52

}p13(x) = x

6 + x4 + x3 + x + 1

C15 ={15, 30, 39, 51, 57, 60

}p15(x) = x

6 + x5 + x4 +

codificacion canal

Documents