Codificacion De Linea

CODIFICACION DE CANAL Si uno quiere disminuir la probabilidad de error en un sistema de transmisión digital, puede hacer varias cosas: a) aumentar la potencia de transmisión aunque si es un sistema con baterías esta solución podía no aplicar b) Emplear un esquema sencillo de detección de errores y aplicar un ARQ(Automatic Repeat Request); esto se usa, por ejemplo, en transmisión de fax, pero en una aplicación como transmisión vía satélite, esto sería poco práctico c) Emplear redundancia en la transmisión a través de las llamadas técnicas FECC (Forward Error Correction Coding). Dentro de esta última solución están inscritas las técnicas de Codificación de Canal que veremos a continuación. El problema del control de errores puede verse desde varios aspectos: a) Tipo de control de errores: detección o corrección b) Tipo de errores: aleatorios, por ráfagas, etc. c) Tipo de codificación: por bloques o convolucional d) Tipo de decodificador: algebraico vs. probabilístico Por ejemplo el chequeo de paridad permite detectar errores mientras que FECC permite “estimar” los datos recibidos. Corregir es más complicado que detectar. Entre las aplicaciones que usan técnicas de control de errores están: Pruebas planetarias, Redes de datos (Ethernet, Bluetooth, WAN,etc.), Modems, subsistemas de memoria (SIMMs para detección y Dims para correción), buses de computadoras, Discos magnéticos, CDs, DVD, minidisks, etc. Se ha demostrado que el uso de técnicas de codificación de canal mejora la probabilidad de error acercándola al límite de Shannon.

La forma mas sencilla de insertar bits redundantes para detección de errores es repitiendo cada símbolo n veces; por ejemplo si solo se tienen los símbolos 1 y 0, entonces los códigos posibles son (111..11, 00...0). Puede detectar hasta (n-1) errores y de correción hasta (n-1)/2

Otro tipo de codificación muy sencilla es la de chequeo de paridad donde a que el EX_OR de los datos resulte 1 o 0 de manera predefinida; en este caso se puede detectar cualquier error de 1 bit o de un número impar de bits. Un sistema mas sofisticado sería el de códigos de producto. Se colocan los datos binarios en un arreglo bidimensional y se agregan bits de paridad al final de cada fila y cada columna. Si hay un error en un bit se afectará una fila y una columna y así se podrá determinar en donde ocurrió exactamente el error. Estos últimos códigos son buenos pero ineficientes; por esto surgen los códigos de bloques. CODIFICACION POR BLOQUES La forma de generar un código de bloques es la siguiente: Se toman k bits de datos, se le agregan r bits redundantes de manera de crear nuevos bloques de datos de longitud n (n=k+r). Suponga k=2 y n=3. Esto implica que pueden haber 4 mensajes distintos 00,01,10,11. Al agregarle un bit redundante las posibles palabras codificadas serían 000

011

100 111

Si se transmite 100 y el bit menos significativo se equivoca, recibiremos 101. Al compararlo con las 4 palabras codificadas posibles o válidas se observa que con respecto a las dos primeras tiene 2 diferencias y con respecto a las dos últimas tiene tan solo 1 diferencia. No puede decir cual e}de las dos es la correcta (no puede corregir el error) pero si lo puede detectar. Suponga ahora k=1 n=3. Se tienen 2 posibles mensajes ( 1 y 0) y dos posibles palabras codificadas que podrían ser 000 y 111. Si al transmitir 000 se comete un error en el bit menos significativo, se recibirá 001. El receptor compara con las posibles palabras válidas y la que mas se acerca es 000. Aquí si se estaría detectando y corrigiendo el error. En definitiva se debe tratar de agregar la menor cantidad de redundancia que permita mejorar la probabilidad de error con un sistema sencillo.

Suponga k=3, r=3. A este código se le llamaría (n,k)=(6,3) Llamemos los datos originales m1 m2 m3 Los bits redundantes se construyen usando relaciones entre los bits de mensaje. Por ej.

m1 +m3

m1 +m2

m2 +m3

m1

m2

m3

0

0

0

0

0

0

1 0 1

0

1

0

0

1

1

1

0

1

0

1

0

0

1

1

1 0 1 0

1

0

1

0

0

1

1

1

0

1

0

1

1

1

0

0

0

1

1

1

Donde la suma es módulo 2. Observe que se tienen 2k (8) combinaciones de las 2n (64) posibles. Cuando el mensaje forma parte de la palabra código, se dice que éste es sistemático. Se quiere que las combinaciones enviadas estén lo mas alejadas posible para disminuir la probabilidad de error, por otra parte hay que agregar pocos bits adicionales para que no crezca indefinidamente el ancho de banda. Una forma de modelar este tipo de codificación es pensando en una matriz generadora G, a partir de la cual pueda generarse el mensaje codificado C multiplicando el mensaje m por la matriz G. [m][G]=[C] donde la matriz [G] =

p11

p12

.

p1r

|

1

0

0

.

.

0

p21

p22

.

p2r

|

0

1

0

.

.

0

.

.

.

.

.

.

.

.

.

.

.

pk1

pk2

.

pkr

|

0

0

0

.

.

1

------------------- P----------| ----------------- I ----------------| La primera parte de la matriz [G] la llamaremos porción de paridad del arreglo, y la ultima parte es la matriz identidad. Para el ejemplo que venimos desarrollando 110100 [G] =

011010 101001

Observe que para generar los códigos solo hay que almacenar la porción de paridad (P), de la matriz [G]. En el receptor se tendría una matriz llamada [H] (matriz de chequeo de paridad) que permitiría decodificar los vectores recibidos, y cuya transpuesta sería:

[HT] =

1

0

.

0

0

1

.

0

.

.

.

.

0

0

.

1

p11

p12

.

p1r

p22

.

p2r

.

.

.

.

pk2

pkr

Si uno multiplica el mensaje codificado (sin errores) por esta matriz, el resultado será nulo. [C] [HT]= [m][G] [HT]= 0 Si esto ocurre uno tiene la garantía que el código que llegó es válido. Si, en cambio, el vector [C] se corrompe con un vector [e], la señal recibida será: [r]= [C]+ [e] Por lo tanto, si en el receptor multiplicamos por la matriz [HT] obtendremos: [S] =[r] [HT]= ( [C]+ [e] ) [HT]= [C] [HT]+ [e] [HT]= [e] [HT] A [S] se le llama el síndrome. Si [r] pertenece al conjunto de palabras válidas, [S]=0. Si [r] tiene un error, [S] dará una pista sobre donde está dicho error. El síndrome sobre [r]es igual al síndrome sobre[e]. Tiene que haber una correspondencia uno a uno entre los patrones de error y el síndrome. Ejemplo: Suponga [C]=[1 0 1 1 1 0] y [e]=[0 0 1 1 1 0]

Es posible hacer corresponder este resultado al error que se cometió. Para esto la matriz [H] debe cumplir que: a) Ninguna columna debe ser nula ya que el error en esa columna no seria detectado; b) Todas las columnas deben ser diferentes. Como asociar un síndrome a un error determinado? Construyamos un arreglo así: . En la primera fila se colocan todos las palabras de código validas que son 2k . En la primera columna se colocan todos los errores detectables, comenzando por error 0 es decir (00..0) Generalmente se trata primero de detectar los errores de 1 bit, luego de 2 bits y asi sucesivamente. Estos son llamados los COSET LEADER. Luego cada columna se rellena con la suma de las palabras válidas con el COSET LEADER correspondiente.

Ejemplo COSET LEADER

000000 110100 011010 101110 101001 011101 110011 000111 Palabras validas ________________________________________________________ 000001 110101 011011 101111 101000 011100 110010 000110 000010 110110 011000 101100 101011 011111 110001 000101 000100 110000 011110 101010 101101 011001 110111 000011 001000 111100 010010 100110 100001 010101 111011 001111 010000 100100 001010 111110 111001 001101 100011 010111 100000 010100 111010 001110 001001 111101 010011 100111 010001 100101 001011 111111 111000 001100 100010 010110 Un esquema de decodificación sería el siguiente: Se calcula el síndrome y se busca dentro de la tabla de COSET LEADER cual fue el error que ocurrió. Se le suma este valor al código recibido y se tendrá el valor transmitido. FORTALEZA DEL CODIGO

Definiciones: Peso Hamming de un vector U = w(U) =Numero de elementos no nulos de U Distancia Hamming entre dos vectores U y V = d(U,V)= Numero de elementos en los cuales difieren w(U+V)= d(U,V) w(V)=d(V,0) La mínima distancia (Hamming) de un código define su fortaleza frente al ruido. Como la suma de dos vectores de un subespacio dará otro elemento del subespacio d( U,V)= w(U+V)= w(Z) Solo necesitamos ver el peso de cada vector y se elige el menor. Esto será dmin. Que hace el receptor? U. r1. . . . .V (Aquí se decide por U) U. . r2. . . .V (Aquí también se decide por U) Sin embargo, si transmito V y se producen 3 errores, se convierte en U La distancia mínima define la capacidad de detectar y corregir errores. En general un código (n,k) es capaz de corregir 2r patrones de error o t errores t= capacidad de corrección de un código

Si vemos la tabla de los COSETs, podemos ver que, en ese ejemplo, dmin=3; por lo tanto solo se pueden detectar todos los errores de 1 bit. Existe un teorema que establece que en un código lineal (n,k) la distancia mínima tiene el siguiente límite superior

CODIGOS HAMMING Son aquellos códigos de bloque donde se cumple que:

Donde m es mayor o igual a 3.

Estos códigos tienen la propiedad de que la mínima distancia es 3 independiente del valor asignado a m. Esto significa que los códigos Hamming pueden corregir 1 error. EFECTO EN LA PROBABILIDAD DE ERROR FINAL Y EN EL ANCHO DE BANDA En general se puede decir que: Si uno mantiene la potencia promedio de la señal codificada igual a la de la no codificada, la Energía por bit tiene que bajar ya que cada “1” durará menos. La tasa de símbolos del canal (bits ya codificados) aumenta en un factor (n/k) Hay que detectar mas bits durante el mismo intervalo de tiempo. Ejemplo del Sklar: Compare la probabilidad de error por mensaje de un sistema BPSK, que se corrompe con ruido blanco gaussiano tal que S/η =43.776 y donde se transmiten sin codificar 4800 bits/segundo, con un sistema codificado (15,11) que es capaz de corregir 1 error dentro de un bloque de 15 bits. Sin codificación:

Con codificacion:

La probabilidad de error por mensaje ha mejorado por un factor de 58 respecto al caso no codificado. CODIGOS CICLICOS Son un tipo de códigos lineales mas fáciles de implementar. Un código lineal es llamado cíclico si cumple las siguientes propiedades: 1) Linealidad: La suma de 2 palabras códigos es otra palabra código 2) Desplazamiento cíclico: Cualquier desplazamiento cíclico de una palabra codigo es otra palabra código. 3) Las componentes de un vector de código C0, C1, C2, ... Cn-1, pueden ser tratadas

como un polinomio: C(X)= C0 X0+C1 X1+C2 X2+ ... +Cn-1Xn-1 Si Cn-1es no nulo, se dice que el grado de C(X) es n-1. Si C(X) representa una palabra de un código cíclico, el desplazamiento cíclico del mismo i veces C(i) (X), se puede representar como: C(i) (X)= Xi C(X) mod (Xn +1) O lo que es lo mismo, C(i) (X) es el residuo que resulta de dividir Xi C(X) por (Xn +1).

La estructura matemática de un código cíclico permite utilizar códigos de alto orden que pueden ser implementados usando registros de corrimiento Suponga

C(X)= C0 X0+C1 X1+C2 X2+ ... +Cn-1Xn-1 XC(X)= C0 X+C1 X2+C2 X3+ ... +Cn-1Xn Ahora sumamos 2 veces Cn-1(ojo 1+1=0) XC(X)= Cn-1+C0 X+C1 X2+C2 X3+ ... +Cn-2Xn-1 +Cn-1(Xn +1)= XC(X)=C(1)(X)+ Cn-1(Xn +1) C(1)(X)= XC(X)mod(Xn +1) Por extensión se llega a: C(i)(X)= X i C(X)mod(Xn +1) El termino (Xn +1) juega un papel clave en la generación de códigos cíclicos. Para generar un código cíclico se puede usar un polinomio generador en forma parecida a como en códigos lineales por bloques usábamos una matriz generadora. g(X)=Polinomio de grado (n-k) m(X)=Polinomio mensaje de grado (k-1) C(X)=Código resultante C(X)= (b0, b1, b2, ... bn-k-1 ,m0, m1, m2, ... mk-1)=b(X)+ X n-km(X) b(X) es el residuo que queda después de dividir X n-km(X) entre g(X). PROCEDIMIENTO: Multiplique X n-km(X) Divida X n-km(X)/g(X) Tome el residuo b(X) Sume b(X)+ X n-km(X) y este será el código. Ejemplo: Partiendo de

A los polinomios de la derecha se le llaman primitivos de, en este caso, X7+1 Use g(X)=1 + X + X3 para generar un código sistemático (7,4) para el mensaje m=1011

Ahora sumamos el residuo mas X 3m(X) y esta es la palabra codificada 1011 lleva a 1+ X 3+ X 5+ X 6 o sea 1001011 Los 3 primeros bits son de paridad los 4 últimos el mensaje mismo. CODIFICACION CICLICA USANDO DIVISORES Dados dos polinomios V(X)= V0 X0+V1 X1+V2 X2+ ... +VmXm g(X)= g0 X0+g1 X1+g2 X2+ ... +grXr El siguiente circuito realiza la división V(X)/g(X)

A este circuito entra V(x) por la izquierda comenzando por el coeficiente Vm. Para el ejemplo que tenemos en mano

Entrada

Shift

Registros

Salida

0001011

0

000

-

000101

1

100

0

00010

2

110

0

0001

3

011

0

000

4

011

1--------X3

00

5

111

1--------X2

0

6

101

1--------X

-

7

100

1--------1

CODIGOS DE REDUNDANCIA CICLICA Son códigos cíclicos usados para detectar errores no para corregirlos. En este tipo de codificación se toma el mensaje m(x) y se modifica de acuerdo a un polinomio g(x); esto se logra 1) multiplicando o desplazando m(x) por el orden de g(x) 2) dividiendo m(x) desplazado entre g(x) 3) agregando el residuo de la división al final de m(x) para conformar el mensaje codificado. En el receptor se divide el mensaje codificado entre g(x); si no hay residuo es porque no hubo errores. La división puede efectuarse fácilmente con registros de desplazamiento y sumadores módulo 2.

Algunos polinomios generadores típicos son los siguientes

Codigo

Polinomio g(X)

n-k

CRC-12

1+ X+ X2+X3+X11+X12

12

CRC-16

1+X2+ X15+X16

16

CRC-CCITT 1+X5+ X12+X16

16

Estos códigos todos contienen como factor primo (1+X). El CRC-12 se usa para caracteres de 6 bits; los otros dos son usados para caracteres de 8 bits. El CRC-CCITT se usa en redes WAN y en MODEMs V.41. Los Códigos CRC binarios pueden detectar los siguientes patrones de error:

Ráfagas de longitud n-k o menores. Una fracción de ráfagas de longitud igual a n-k+1; la fracción igual a 1-2-(n-k-1) Una fracción de ráfagas de longitud mayor que n-k+1; la fracción igual a 1-2-(n-k-1) Todas las combinaciones de dmin-1 ( o menos) errores. Todos los patrones de error con un numero impar de errores si el polinomio g(X) tiene un numero par de coeficientes no nulos. CODIGOS BCH(Bose-Chaudhuri-Hocquenghem) Los mas comunes son los llamados BCH primitivos los cuales tienen: Longitud del bloque: n=2m -1 ( m mayor o igual a 3) Numero de bits del mensaje: k ≥ n-mt Distancia mínima ≥ 2t+1 Cada código BCH es un código corrector de t errores. Los códigos Hamming correctores de un error pueden ser descritos como códigos BCH. CODIGOS REED-SOLOMON Son codigos ciclicos no binarios. Un codigo RS(n,k) expande un bloque de k simbolos a n simbolos agregando n-k simbolos redundantes. Una propiedad importante de los códigos RS es que combaten los errores de ráfaga. Su capacidad de corregir errores es: t=(n-k)/2, donde n y k representan número de símbolos , no de bit. INTERLEAVING: Cuando los errores vienen en ráfagas alterará un grupo de bits seguidos haciendo mas notorio su efecto (ejemplo una raya en un CD). Si en cambio antes de transmitir la señal codificada se divide en bloques más pequeños y se reorganiza entonces una ráfaga de errores se repartirá en el receptor en bits que no son vecinos apreciándose menos su efecto. Esta reorganización se llama Interleaving. Por ejemplo imaginemos que se enviarían los bits en el siguiente orden b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 Sin embargo antes de enviarlos se desordenan de la siguiente manera b7 b3 b6 b2 b10 b9 b5 b3 b8 b4 Si ahora ocurren 3 errores seguidos (digamos en b6 b2 b10) al deshacer el Interleaving quedarán repartidos de manera dispersa en los datos originales notándose menos su efecto.

CODIGOS CONVOLUCIONALES

Difieren de los códigos de bloques en que trabajan en una base de bit por bit (serialmente) reduciendo los problemas de memoria. Tiene en principio la siguiente estructura

El código generado tiene V símbolos de salida por cada símbolo de entrada. La razón del código es 1/V. Hay varios métodos para representar un codificador convolucional: Representación por Conexión, Diagrama de estados, Representación por arbol y Diagrama Trellis. Los veremos a continuacion Suponga que el codificador tiene la siguiente estructura:

Veremos su funcionamiento para una secuencia de entrada ( mensaje)=101. Se asumira que los registros estan descargados(000) y al final habra que alimentar con 3 ceros para volver a limpiar los registros. En cada caso veremos el contenido de los registros y las salidas U1 y U2.

La secuencia de salida será entonces: 11 10 00 10 11. Note que la tasa efectiva es 3/10 ya que por 3 bits de entrada hay 10 bits de salida. (un poco menos de 0.5 que es lo que pareciera ser; sin embargo hay que esperar que el ultimo bit salga del codificador para poder calcular correctamente la tasa. Por supuesto si el mensaje fuera de 300 bits, salen 604 bits y la razón sería 300/604 mucho mas cercana a 0.5. Representación por diagrama de estados: El estado de un codificador se define como los contenidos de los registros de las k-1 etapas mas a la derecha del codificador. En el caso que analizamos tal diagrama seria el mostrado a continuacion, en el cual las lineas solidas indican una transicion debida a un 0 y las lineas punteadas indican una transicion por un 1. El estado a esta representado por 00 en los dos ultimos registros, b=10, c=01, d=11. Entre parentesis se muestran U1 y U2.

Representación por árbol o árbol de códigos: Observe el arbol para el ejemplo que estamos analizando:

Se observa que luego de 3 niveles dentro del árbol ( igual al numero de registros del codificador) la mitad superior del árbol es idéntica a la parte inferior. Se observa que de ese punto en adelante, la salida no depende de en cual de esos se encontraba: el codificador se estabiliza. Esto da pie para presentar la estructura de enrejado o trellis.

Este diagrama permite ver la evolución del codificador por mucho tiempo sin necesidad de escribir un árbol interminable. El diagrama Trellis requiere 2(k-1) nodos para representar los 2(k-1) posibles estados. El decodificador a usar se llamara de máxima verosimilitud ( maximum-likelihood, y debe tratar de maximizar P(Z/Um) donde Um son todas las posibles secuencias recibidas. Si se usan L bits hay que analizar 2L secuencias. Como el ruido afecta cada símbolo en forma independiente, se puede expresar P(Z/Um) de la siguiente forma:

Donde : Zi es la i-esima rama de la secuencia Z, U i m la i-esima rama de una secuencia U m particular zji es el j-esimo simbolo de Zi uji m es el j-esimo simbolo de U i m

El decodificador debe elegir el trayecto a traves del diagrama Trellis donde P(Z/Um) es maximizado. Generalmente se usa el logaritmo para sumar en vez de multiplicar. ALGORITMO DE VITERBI Es un decodificador de máxima verosimilitud, pero usa la estructura Trellis para simplificar la carga computacional. Necesita una medida de similitud o distancia entre la señal recibida en el instante ti y todas las trayectorias Trellis que intervienen a este

tiempo ti. Remueve del diagrama aquellas trayectorias que no son posibles candidatos para una elección de máxima verosimilitud. Cuando 2 trayectos llegan al mismo estado sobrevive el que tenga, por ejemplo, la menor distancia Hamming. Esto se hace para todos los estados. Ejemplo:

Secuencia de entrada 1

1

0

1

Se transmite

11 01 01 00

Se recibe

11 01

01 10

El decodificador sabe el estado inicial del Trellis

Se coloca la distancia entre lo recibido y lo indicado en el diagrama Trellis Si dos trayectorias convergen se elimina la que tiene mayor distancia o trayectoria metrica.

Ya en este punto el decodificador decide que el primer bit fue un 1. Sigue avanzando en el tiempo y puede del mismo modo concluir que el bit 2 tambien fue un 1 y asi sucesivamente. REGLAS DE TRABAJO 1) Dado p bits redundantes, uno puede alcanzar una “undetected error probability” menor o igual a 2-p. Por ejemplo CRC-16 es un código de 16 bits de chequeo de paridad que proporciona una “undetected error probability” menor a 2-16=1,6x10-5 2) Para mensajes de n bits son necesarios y suficientes tlog2n bits de chequeo para detectar t errores. Por ejemplo códigos BCH de longitud 255, requerirían 8 bits para detectar 1 error 3) Se puede intercambiar capacidad de corrección por capacidad de detección a una relación de 1 bit de corrección de errores por 2 bits de detección de errores. Por ejemplo un código que puede corregir 2 errores puede detectar 4 errores