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 0 1
0 1 1 0 1 0
1 1 0 0 1 1
1 1 0 1 0 0
0 1 1 1 0 1
1 0 1 1 1 0
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
