Codificación

Para la simulación de los sistemas de codificación usaremos el programa octave y el toolbox de comunicaciones.

En las transmisiones digitales actuales la codificación es un proceso muy elaborado, con un diagrama de bloques general que mostramos en la siguiente figura.

Este sistema contiene dos codificadores propiamente dichos: uno exterior de bloques, y uno interior convolucional. Estos dos codificadores introducen redundancia en los datos con objeto de poder detectar o corregir errores de transmisión. El sistema contiene además dos entrelazados cuyo objetivo es hacer que bloques correlativos de bits no se transmitan juntos. Este es el esquema de codificación empleado en la televisión digital DVB (Digital Video Bradcasting). El esquema de codificación utilizado en la telefonía móvil GSM es similar, pues usa un codificador de bloques, un codificador convolucional y un entrelazado.

Por ejemplo, la función octave que realiza en entrelazado es:

Entrelazado, y=interleave(x,n,m). Realiza un entrelazado n*m. La entrada x es introducida en la matriz columna por columna y leída fila por fila en la salida y. Por ejemplo:

y = interleave([1 1 1 1 0 0 0 0 ],4,2) % salida: [1 0 1 0 1 0 1 0]

Codificación de bloques

En este tipo de codificación, la secuencia de datos a transmitir se divide en bloques de bits que se introducen juntos en el codificador. La salida es otro bloque de bits que ya contiene redundancia. La operación realizada suele ser una operación lineal, la cual entonces puede expresarse de forma matricial. Sea x es un bloque de datos, sea G la matriz generadora de la codificación, entonces la salida de la codificación, c, que se denomina palabra código, se obtiene por el producto matricial c=x*G. Si las palabras código tienen longitud n y los bloques de datos de partida tienen de longitud k, la codificación se denomina (n,k) y la tasa de cofificación es R=k/n. Las funciones octave de las que disponemos son:

Codificación, c=mult_mod2(x,G). Esta función realiza el producto c = x*G, es decir codifica el bloque de bits de entrada x usando la matriz generadora G y obteniendo la palabra código c.
Forma sistemática, GS=syst_matrix(G). Esta función convierte la matriz generadora G en una matriz de forma sistemática.
Matriz chequeo de paridad, H=check_matrix(G). Esta función obtiene la matriz chequeo de paridad H, a partir de la matriz generadora G (se asume que G tiene forma sistemática).
Detección de errores, s=mult_mod2(c,(H')). Esta expresión realiza el producto c*H^t (H traspuesta) y, por lo tanto, en caso de que la palabra c se haya transmitido correctamente se obtendrá cero.

Por ejemplo:

>> G= [ 1 0 0 0 1 0 1 ; 0 1 0 0 1 1 1 ; 0 0 1 0 1 1 0 ; 0 0 0 1 0 1 1]; >> x= [ 0 1 1 0 ]; % bloque da datos a codificar >> c= mult_mod2(x,G) % realizamos la codificacion >> H= check_matrix(G) % obtenemos la matriz de chequeo de paridad >> mult_mod2(c,(H')) % comprobamos que no hay errores >> mult_mod2([ 0 1 1 0 0 0 0],(H')) % un ejemplo con error

Codificación cíclica

Son los códigos más utilizados, pues tienen importantes características matemáticas que los hacen muy adecuados para la detección de errores. Las dos características más importantes son:

Son las codificaciones para las que dado (n,k) proporcionan la mejor distancia Hamming.
La generación y la decodificación de las palabras código puede realizarse con circuitos relativamente sencillos.

Se denominan cíclicos porque tienen la propiedad de que el desplazamiento cíclico de una palabra código genera una nueva palabra del código es decir, que si c=(c_{n-1},c_{n-2},...,c_1,c_0) es una palabra código también lo es (c_{n-2},...,c_1,c_0,c_{n-1}). Un código cíclico (n,k) posee un polinomio generador G(D) de grado n-k, tal que cualquier mensaje de entrada X(D) (de longitud k) se convierte en una palabra código (de longitud n) multiplicándolo por el polinomio generador G(D), es decir C_i(D)=X(D)*G(D). Las funciones octave de las que disponemos son:

Matriz generadora, G=cyclic_matrix(g,length(x)). Esta función obtiene la matriz generadora G a partir de los coeficientes del polinomio generador g. Tenemos que darle como argumente el número de filas que va a tener la matrix y que coincide con la longitud del bloque de bits a codificar x.
Forma sistemática, GS=syst_matrix(G). Esta función convierte la matriz generadora G a su forma sistemática.

Por ejemplo:

>> g= [ 1 1 0 1 ]; % polinomio generador >> G= cyclic_matrix(g,4) % matriz generadora >> GS= syst_matrix(G) % forma sistematica

Circuitos generadores del código cíclico. La codificación cíclica es fácilmente implementable en términos de registros de desplazamiento y puertas EXOR. En la siguiente figura se muestra la forma directa de hacerlo a través del polinomio generador G(D),

Códigos cíclicos de desplazamiento máximo (binarios)

Todas las palabras código, excepto la de todo 0, son desplazamientos de una única palabra (en el caso de código cíclico general hay varias palabras de partida). Contienen 2^{m-1} unos y 2^{m-1}-1 ceros. Se utilizan como generadores de seudorruido y tienen importancia en aplicaciones militares y de telefonía móvil. En la siguiente figura se muestra un pequeño ejemplo para m=3. A la derecha se muestra la secuencia de longitud máxima (7) es capaz de generar, dependiendo del valor incial introducido en el registro.

Durante los 3 primeros ciclos el interruptor está en la posición mostrada en la figura para que los 3 primeros bits entre en el registro. En los siguientes ciclos el interruptor pasa a la posición indicada por la línea rayada. La siguiente tabla muestra como generar códigos cíclicos de distancia máxima

m	conex.	`m`	conex.	`m`	conex.
2	1,2	13	1,3,4,13	24	1,2,7,24
3	1,3	14	1,6,10,14	25	3,25
4	1,4	15	1,15	26	1,2,6,26
5	2,5	16	1,3,12,16	27	1,2,5,27
6	1,6	17	3,17	28	3,28
7	1,7	18	7,18	29	2,29
8	2,3,4,8	19	1,2,5,19	30	1,2,23,30
9	4,9	20	3,20	31	3,31
10	3,10	21	2,21	32	1,2,22,32
11	2,11	22	1,22	33	13,33
12	1,4,6,12	23	5,23	34	1,2,27,34

En la siguiente figura se muestra un ejemplo de como hacer las conexiones,

El funcionamiento del registro se puede similar en octave utilizando la siguiente función:

Registro de desplazamiento,[secuencia, nuevo_estado]= shift_reg (conexiones, estado,N). El array conexiones contiene las posiciones de las líneas de conexión del registro, estado es el estado inicial de registro y N es el número de bits que va a proporcionar el registro, la cual se almacena en secuencia; por último el array nuevo_estado proporciona en contenido del registro una vez que haya acabado su operación.

Por ejemplo,

>> sec= shift_reg([1,3],[1 0 0],7) % registro figura anterior

Códigos Reed-Solomon

Son una generalización de los codigos cíclicos binarios. Los códigos Reed-Solomon en vez de en base 2 (elementos 0 y 1) operan sobre un Campo de Galois de base q, GF(q). Es decir, que las operaciones de suma y de multiplicación se hacen módulo q. Los campos de Galois con q=2^M tienen propiedades matemáticas muy interesantes que los hacen muy útiles en la codificación. Disponemos de las funciones octave que nos permiten simular la codificación Reed-Solomon. Las funciones operan en general en el cuerpo de Galois GF(2^M) y generan la codificación GF(n=2^{M}-1,k=n-2t-1,t). En concreto, son las siguientes:

Codificación Reed-Solomon, c=rs_encode(M,t,x). Realiza la codificación en GF(2^M) con una capacidad de corrección de t errores partiendo de la palabra de entrada x y resultado la palabra código c. Los elementos de estas dos palabras deben estár comprendidos entre 0 y 2^M-1 pues se opera en base 2^M. La longitud máxima de la palabra de entrada x es de 2^M-2t-1 elementos. Si la longitud de la palabra es menor de este valor, el programa automáticamente la amplía añadiendo 0s al final.
Decodificación Reed-Solomon, y=rs_decode(M,t,c). Decodifica la palabra código c recuperando la palabla original y. Puede corregir hasta errores y opera en el Campo de Galois GF(2^M)

Por ejemplo,

>> M=4 % Campo de Galois GF(16) >> t=3 % Puede corregir 3 errores >> x=[8, 6, 8, 1, 2, 4, 15, 9, 9] % valores entre 0 y 15 >> c=rs_encode(4,3,x) % codificacion Reed-Solomon >> y=rs_decode(4,3,c) % decodificacion Reed-Solomon

Codificación convolucional

Pasamos a ver ahora el segundo tipo de codificación. La codificación convolucional es una codificación continua en la que la secuencia de bits codificada depende de los bits previos. El codificador consta de un registro de desplazamiento de K segmentos de longitud k (en total kK) que se desplaza k posiciones por ciclo y genera n funciones EXOR también por ciclo. La tasa de codificación es, entonces, R=k/n.

En el siguiente ejemplo mostramos un registro que se desplaza una posición por ciclo (k=1), que consta de Kk=3 celdas y que genera N=3 funciones EXOR por ciclo.

Codificador convolucional, c=conv_encode(G,x,k). G es la matriz generadora del codificador convolucional, puesta como una matriz de conexiones en binario, x es la secuencia de entrada, c es la secuencia codificada, y k es el número de posiciones que se desplaza el registro en cada ciclo. Esta función proporciona secuencia de salida hasta que el registro queda completamente vacío y vuelto al estado 0.

Simulamos el codificador convolucional del ejemplo 1 de la siguiente forma:

>> G= [ 1 0 0 ; 1 0 1 ; 1 1 1 ]; % matriz generadora >> k=1; % se desplaza 1 posicion por ciclo >> c= conv_encode(G,[0 1 1 0],k) % codificamos la secuencia [0 1 1 0]

Algoritmo de Viterbi

La codificación convolucional se decodifica con ayuda del algoritmo de Viterbi. En la siguiente figura mostramos el algoritmo para la codificación del ejemplo.

El algoritmo de Viterbi también se puede simular en octave, aunque sólo disponemos de la función para codificadores que realizan un desplazamiento por ciclo (k=1). El comando correspondiente es,

Algoritmo de Viterbi, y=viterbi(G,2*c-1). En esta función, G es la matriz generadora del codificador convolucional, c es la secuencia de entrada, e y es la secuencia decodificada. La entrada tiene que tener los valores +/-1, por lo que hemos puesto 2*c-1.

Para el ejemplo que tenemos,

>> G= [ 1 0 0 ; 1 0 1 ; 1 1 1 ]; % matrix generadora >> c= encode_conv(G,[0 1 1 0],1); % codificamos [0 1 1 0] >> % ahora empieza la decodificacion >> y=viterbi(G,2*c-1) % recuperamos la secuencia

Página libre del software de micro$oft
Este material puede usarse libremente según los términos de la GPL
Copyright (C) 2001 Francisco Argüello