Make your own free website on Tripod.com
SELEC CABLE-UTT soft

Home

FIBRA OPTICA | CABLE COAXIAL | PAR TRENZADO | CALCULADORA | CODIGO HAMMING Y CODIGO CICLICO O CRC | CONVERTIDOR DE MONEDAS | MULTIPLEXAJE Y MODELO CLIENTE SERVIDOR | VIRUS INFORMÁTICOS
CODIGO HAMMING Y CODIGO CICLICO O CRC

INTRODUCCION

   

    La codificación del canal consiste en 'mapear' (añadir redundancia) la secuencia de datos entrante en una secuencia de entrada al canal y realizar el 'mapeo' inverso a la salida del canal en una secuencia de datos tal que los efectos del ruido estén minimizados.
    La introducción de redundancia en la codificación del canal tiene como finalidad mejorar la fiabilidad de la transmisión.

    Antes de comenzar con la descripción de algunos de estos códigos es conveniente dar unas definiciones:

  • tasa de error: Se define como la relación entre el número de bits erróneos recibidos respecto al número total de bits transmitidos. Una tasa de error aceptable para una transmisión es 10 elevado a la -6.

  • tasa residual de error: Se define como la relación entre el número de bits erróneos no detectados sobre el total de bits emitidos. Mide la capacidad de detectar errores.

  • peso de Hamming: El peso de Hamming W(c) de una palabra de código c se define como el número de bits de esa palabra diferentes de cero.

  • distancia de Hamming: Es la distancia entre dos palabras de código de igual longitud y se define como el número de bits (posición a posición) en los que se diferencian las dos palabras.

 

Codigos Convolucionales

    Se diferecian de los códigos de bloque en su forma estructural y las propiedades para corregir errores.
    Los códigos de bloque suelen tener limitada la capacidad de corrección de errores alrededor de 1 o 2 símbolos erróneos por palabra de código. Estos códigos son buenos para utilizar en canales con baja probabilidad de error.
    Los códigos convolucionales son adecuados para usar sobre canales con mucho ruido (alta probabilidad de error).
    Los códigos convolucionales son códigos lineales, donde la suma de dos palabras de código cualesquiera también es una palabra de código. Y al contrario que con los códigos lineales, se prefieren los códigos no sistemáticos.
    El sistema tiene memoria: la codificación actual depende de los datos que se envían ahora y que se enviaron en el pasado.
    Un código convolucional queda especificado por tres parámetros (n,k,m):

n es el número de bits de la palabra codificada
k es el número de bits de la palabra de datos
m es la memoria del código o longitud restringida

 

Ejemplos

- Código (2,1,3)

- la palabra codificada tiene 2 bits de longitud
- la entrada son bloques de 1 bit
- la salida depende de los dos bloques anteriores y del actual

- Código (4,2,3)

- la palabra codificada tiene 4 bits de longitud
- la entrada son bloques de 2 bit
- la salida depende de los dos bloques anteriores y del actual

 

Proceso de codificación

    El proceso de codificación de estos códigos se realiza utilizando un dispositivo lógico en el codificador.
    Ejemplo: Codificador convolucional (4,3,5) 

    La palabra codificada se obtendría como el resultado de realizar una serie de operaciones lógicas entre determinados bits que están almacenados en los registros intermedios.
    Ejemplo: Codificador convolucional (2,1,3)

  • El conmutador con las dos entradas hace el papel de un registro de desplazamiento de dos estados.

  • El código convolucional es generado introduciendo un bit de datos y dando una revolución completa al conmutador.

  • Inicialmente se supone que los registros intermedios contienen ceros.

    En este ejemplo la palabra codificada se obtiene como resultado de sumas módulo-2 entre los bits indicados que están almacenados en los registros intermedios.
    Las secuencias de salida para el código anteriormente descripto:

Entrada (S3,S2,S1) Salida (O1,O2)
000 00
001 11
010 01
011 10
100 10
101 01
110 11
111 00

    Como ejemplo del funcionamiento de este codificador, supongamos que se quiere enviar la secuencia de bits 0101 (donde los bits más a la derecha son los más antiguos). El proceso de codficación es el siguiente:

  • Se introduce el primer bit de la secuencia en el codificador:

  • Se introduce el segundo bit de la secuencia en el codificador:

  • Se introduce el tercer bit de la secuencia en el codificador:

  • Se introduce el cuarto bit de la secuencia en el codificador:

    Al final del proceso de codificación obtenemos que la secuencia codificada es 01 01 01 11.

    Sigamos con la exposición del proceso de codificación.

    Debido a la memoria del código es necesario de disponer de medios adecuados para determinar la salida asociada a una determinada entrada.

    Hay tres métodos gráficos:

  • Diagrama árbol o árbol del código: representación mediante un árbol binario de las distintas posibilidades.

  • Diagrama de estados: es la forma menos utilizada.

  • Diagrama de Trellis o enrejado: es la forma más utilizada porque es la que permite realizar
    la decodificación de la forma más sencilla.

    Para el ejemplo del codificador (2,1,3) anteriormente especificado tenemos el siguiente Arbol del código:

    La profundidad del árbol es 2· (m-1), y el número de estados es 2 (m-1) . k

    La interpretación del árbol del código es la siguiente:

  • Hay dos ramas en cada nodo.   

  • La rama superior corresponde a una entrada de un 0.

  • La rama inferior corresponde a la entrada de un 1.

  • En la parte exterior de cada rama se muestra el valor de salida.

  • El número de ramas se va multiplicando por dos con cada nueva entrada.

  • A partir del segundo nivel el árbol se vuelve repetitivo. En realidad, solo hay cuatro tipos de nodos: A,B,C,D. Estos tipos de nodos en realidad son estados del codificador. A partir de estos nodos, se producen los mismos bits de salida y el mismo estado. Por ejemplo, de cualquier nodo etiquetado como C se producen el mismo par de ramas de salida: Salida 10 y estado A Y Salida 01 y estado B

    A partir de la identificación de los estados del codificador se puede incorporar esta información en el DIAGRAMA DE TRELLIS.

    El diagrama de Trellis es un diagrama en forma de red. Cada línea horizontal se corresponde con uno de los estados del codificador. Cada línea vertical se correspondería con uno de los niveles del árbol del código.

    Partimos del estado inicial del codificador en el primer nivel del árbol. A partir de aquí se trazan dos líneas desde este estado. Una para el caso de que la siguiente entrada fuera un 0 y otra para el caso de que fuera un 1. Estas líneas irán hasta el siguiente nivel del árbol al estado en el que queda el codificador después de haber codificado las correspondientes entradas. Encima de cada una de estas líneas escribiremos la salida del codificador para esa codificación.   

    Para cada nivel del árbol hacemos lo mismo desde todos los estados en los que el codificador se puede encontrar.

    Según todo esto, el diagrama de Trellis para el codificador (2,1,3) de nuestro ejemplo será:

    Vamos a seguir en el diagrama de Trellis que acabamos de construir la codificación de la secuencia de bits 0101.

Proceso de decodificación

    El proceso de decodificación consiste en buscar un camino en el diagrama de Trellis (o en el árbol del código) que nos dé la secuencia de bits más probable (si no hay errores obtendremos la secuencia exacta).
    El codificador convolucional añade una estructura a la secuencia de bits. Incluso aunque la entrada sea totalmente aleatoria, se fuerza a que la salida siga unas determinadas secuencias. Esta restricción es la que da la capacidad correctora a los códigos convolucionales.
    El procedimiento de decodificación es equivalente a comparar la secuencia recibida con todas las posibles secuencias que pueden obtenerse con el correspondiente codificador y seleccionando la secuencia que está más próxima a la secuencia recibida.
    Para realizar la decodificación se utiliza un algoritmo denominado Algoritmo de Viterbi.
    El fundamento de este algoritmo está en que no se almacenan todas las secuencias a las que da lugar el codificador.
    Se basa en el principio de optimalidad: el mejor camino (menor distancia de Hamming) a través del diagrama de Trellis que pasa por un determinado nodo, necesariamente incluye el mejor camino desde el principio del diagrama de Trellis hasta este nodo.
    El principio anterior implica que para cada uno de los nodos del diagrama de Trellis sólo es necesario guardar el mejor camino (secuencia) hasta ese nodo. De esta forma, como mucho se tendrán tantos caminos como estados diferentes (el número de estados es 2(m-1)*k).
    Descripción del algoritmo de Viterbi:

  • Paso 1: en el nivel j, calcular la distancia de Hamming de cada camino entrante en cada nodo (estado) desde el nodo del nivel j-1 hasta el nodo del nivel j a través del camino superviviente.

  • Paso 2: para cada nodo (estado) del diagrama de Trellis en el nivel j, descartar todos los caminos que entran en el nodo, excepto el de distancia mínima.
    Cuando a un nodo llegan dos caminos con la misma distancia se toma el superior.

  • Paso 3: pasar al nivel j+1 y repetir los pasos 1 y 2.

    Estos pasos se aplican para j mayor o igual que 2. Hasta ese valor se expanden los caminos.

Codigos Cíclicos

    Los códigos cíclicos son un subconjunto de los códigos lineales, los cuales poseen dos características muy importantes:   

  • Son fáciles de implementar usando una circuitería basada en registros de desplazamiento.

  • Tienen una estructura algebraica bien definida.

Descripción de los Códigos Cíclicos

 

Rotación Cíclica

 

    Sea la n-tupla v=(v0, v1, ... , vn-1). Si los componentes de esa n-tupla son desplazados cíclicamente un lugar a la derecha obtenemos la n-tupla: v(1) =(vn-1, v0, ... , vn-2), denominada rotación cíclica de un elemento de v. De una forma más general si los componentes de v son rotados cíclicamente i veces obtenemos: v(i) =(vn-i, vn-i+1 , ... , vn-1, v0, v1, ..., vn-i-1)

 

Definición de Código Cíclico

 

    El código C(n,k) es cíclico si y solo si cualquier rotación cíclica de un vector v perteneciente a C es también un vector del código C.

 

Notación Polinimial


    Para representar los vectores pertenecientes a los códigos cíclicos usaremos la notación polinomial. Cada una de las componentes de un vector código v =(v0, v1, ... , vn-1) serán los coeficientes del polinomio: v(x)=v0+ v1x+v2x2+ ... + vn-1xn-1. A este polinomio se le denomina polinomio código. Por lo tanto a todo vector v le corresponde un polinomio código v(x) de grado (n-1) o menor. v(i) , en representación polinomial, sería v(i)(x) =(vn-i, vn-i+1x, ... , vn-1xi-1, v0xi, v1xi+1, ... , vn-i-1xn-1).

    Si multiplicamos xiv(x)=v0xi+ v1xi+1+ ... + vn-1xn+i-1. Este producto lo podemos expresar como: xiv(x)=vn-i+vn-i+1x+ ... + vn-ixi-1+ ... +vn-i-1xn-1+ vn-i(xn+1)+vn-1+1x(xn+1)+ ... + vn-i1xi-1(xn+1)= xiv(x)=(vn-i+vn-i1+1x+ ... + vn-1xi-1)(xn+1) + (vn-i +vn-i+1x+ ... +v0xi+ ... + vnxn-1).
xiv(x)=q(x)(xn+1)+v(i)(x)

    De aquí se observa que v(i)(x) es el resto de dividir xiv(x) entre (xn+1).

 

Polinomio de Grado Mínimo

 

Teorema:
   
El polinomio código distinto de 0 de grado mínimo en C(n,k) cíclico es único.

 

Teoremas

 

Teorema:

    Sea g(x)=g0+g1x+g2x2+ ... + gr-1xr-1+xr el polinomio de grado mínimo => g0=1.

    Hemos visto que el polinomio de grado mínimo siempre tendrá la forma: g(x)=1+g1x+g2x2+ ... + gr-1xr-1+xr. Consideremos ahora el conjunto de polinomios g(x), x(g)x, x2g(x), ..., xn-r-1g(x) de grado r, r+1, r+2, ..., n-1 respectivamente. Vamos a demostrar que ese conjunto pertenece al código. Sabemos que: xiv(x) =q(x)(xn+1)+v(i)(x). Si sustituimos v(x) por g(x) quedaría : xig(x)=q(x)(xn+1)+g(i)(x). Sin embargo q(x)(xn+1) tendría grado mayor o igual que n => q(x) debe ser 0. Por tanto queda: xig(x)=gi(x) para todo i que pertenezca al intervalo [0, n-r-1]. Luego el conjunto {g(x), xg(x), ... , xn-r-1g(x)} son rotaciones de g(x), por lo que pertenecen al código y además son linealmente independientes (todos tienen distinto grado).

    Por lo tanto ese conjunto puede constituir una base del código. v(x)=u0g(x)+u1g(x)+u2x2g(x)+ ... +un-r-1xn-r-1g(x) perteneciendo v(x) a C(n,k). v(x)=u(x)g(x), u(x)=u0g(x)+u1g(x)+ ... + un-r-1xn-r-1g(x).

 

Teorema:

    Sea g(x)=1+g1x+g2x2+ ... + gr-1xr-1+xrel polinomio de grado mínimo, para todo v(x) de grado menor o igual que n-1 v(x) pertenecerá al código si y solo si v(x) es múltiplo de g(x).

    El número de múltiplos que habrá será:

    Si añadimos el 0, el número de palabras del código (todos los múltiplos posibles de g(x))=2n-r=2k. Por tanto r=n-k será el grado mínimo de un polinomio cíclico (grado de g(x)) => g(x)=1+g1x+ ... +gn-k-1xn-k-1+xn-k. Por tanto una posible codificación de u(x) será: v(x)=u(x)*g(x)=(u0+ ... +uk-1xk-1)g(x). El grado de g(x) será el número de bits de redundancia que se añaden.

 

Teorema:

    Sea g(x) polinomio generador de C(n,k) => g(x) es factor de (xn+1).

 

Teorema:

    Si g(x) tiene grado (n-k) y es factor de xn+1 => g(x) genera siempre un código cíclico C(n,k).

 

Codificación Sistemática

 

    Sea u=(u0, ... , uk-1), u(x)=u0+ ... +uk-1xk-1. xn-ku(x)=u0xn-k+ ... +uk-1xn-1. xn-ku(x)=a(x)g(x)+b(x). b(x) es un polinomio de grado menor o igual que (n-k-1). b(x)=b0+ ... +bn-k-1xn-k-1. b(x)+xn-ku(x)=a(x)g(x) pertenecerá a C(n,k). Por lo tanto: (b0+b1x+ ... +bn-k-1xn-k-1+u0xn-k+ ... +uk-1xn-1) pertenecerá al código C(n, k). Por lo tanto tenemos:

    Pasos para la codificación sistemática de u:

        1. Multiplicar xn-k por u(x).

        2. Calcular b(x), que es el resto de dividir xn-ku(x) entre g(x).

        3. Concatenar b(x) y u(x).

 

Matrices Generadora y de Comprobación de Paridad De los Códigos Cíclicos

 

Matriz Generadora (MATRIZ G)

 

   Sea C(n,k) un código cíclico y g(x)=g0+g1x+ ... +gn-kxn-k. Se ha demostrado anteriormente que el conjunto de k polinomios {g(x), xg(x), ... , xk-1g(x)} forman una base del código C. Si ponemos como filas de una matriz k*n, las k n-tuplas correspondientes a esos k polinomios código obtendríamos la matriz generadora siguiente:

El problema de usar esta matriz generadora es que, en general, produce una codificación no sistemática. Para sistematizar G se verán dos modos de hacerlo más adelante.

 

Matriz Comprobadora de Paridad (MATRIZ H)

 

    Como g(x) es factor de (xn+1) => (xn+1)=g(x)h(x), siendo h(x)=h0+h1x+ ... +hkxk, con h0=hk=1. Sea una palabra código v=(v0, v1, ... , vn-1), por lo tanto v(x), polinomio asociado a v, debe ser múltiplo del polinomio generador v(x): v(x)=a(x)g(x). v(x)h(x)=a(x)g(x)h(x)=a(x)(xn+1)=a(x)xn+a(x). El grado de a(x) es menor o igual que (k-1), las potencias xk, xk+1, ... , xn-1 no aparecen en a(x)+xna(x). Si expandimos el producto v(x)h(x), los coeficientes de xk+1, ... , xn-1 deben ser iguales a cero. Por lo tanto, obtenemos (n-k) ecuaciones, denominadas ecuaciones de diferencia:

    El polinomio recíproco de h(x) es xkh(x-1)=hk+hk-1x+hk-2x2+... +h0xk. xkh(x-1) es también factor de (xn+1), por lo tanto generará un código cíclico C(n, n-k).

    La matriz generadora de ese código será:

De las ecuaciones de diferencias obtenemos que cualquier palabra del código es ortogonal a cualquiera de las filas de la matriz H => H es la MATRIZ DE PARIDAD de C. H genera el código dual de C, h(x)=polinomio de paridad de C.

 

Teorema:

 

Sea C(n,k) un código cíclico con polinomio generador g(x) => el código dual de C es cíclico y se genera por xkh(x-1), con h(x)=(xn+1)/g(x)

 

Sistematización de la matriz G

 

Tenemos dos formas para sistematizar la matriz G :

    1) Combinando filas de la matriz G. Por ejemplo : Sea g(x)=1+x+x3. La sistematización de la matriz G se muestra en la figura siguiente :

 

 

    2) Sea C(n, k) nuestro código cíclico y g(x) su polinomio generador. Si dividimos xn-k+i por g(x) obtenemos : xn-k+i=a(x)ig(x)+bi(x), con i=0, 1, ..., k-1.bi(x)=bi, 0+bi, 1x+bi, 2x2+ ... +bi, n-k-1xn-k-1. bi(x)+xn-l+i=ai(x)g(x), es decir, bi(x)+xn-l+i es un múltiplo de g(x) por lo que pertenecerá al código. Podemos usar esos k polinomios código como las filas de la matriz G, obteniendo la matriz generadora de forma sistemática :

 

    Podemos calcular H a partir de esta matriz G en forma sistemática como : H=(In-k | Pt) según se vio en el tema de códigos lineales. La matriz quedaría de la forma :

Codificación de los códigos cíclicos

Codificación basada en g(x)

    Para codificar seguiremos los tres pasos vistos en la codificación sistemática :

        1. Multiplicar xn-k por u(x).

        2. Calcular b(x), que es el resto de dividir xn-ku(x) entre g(x).

        3. Concatenar b(x) y u(x).  La implementación se hace con el circuito:

    Los pasos de la codificación serían :

        1.  La puerta está cerrada, por lo que se introducen los dígitos de xn-ku(x) al canal y al circuito. (gi => conexión, gi => no conexión).

        2.  Se abre la puerta (se elimina la realimentación). En este paso ya están calculados todos los bi, por lo que se van desplazando hacia el canal.

Codificación basada en h(x)

   

    h(x)=h0+h1x+ ... +hkxk. Sea el vector código v=(v0, v1, ... , vn-1). Las ecuaciones en diferencias son : 

    Como hk=1 y h0=1, esas ecuaciones se pueden expresar de la forma :

    Usando esta última ecuación el circuito que realizaría la codificación sería:

    Los pasos de la codificación serían :

        1. La puerta 1 está conectada y la puerta 2 está desconectada. Se va introduciendo el mensaje original en los registros de desplazamiento.

        2. La puerta 1 está desconectada y la puerta 2 está conectada. Se van caulculando y sacando los bits de paridad.
    Por lo tanto hemos visto que tenemos dos métdodos de codificación :

  • Método basado en g(x) : tiene (n-k) etapas.

  • Método basado en h(x) : tiene k etapas.

    Usaremos el que tenga menor número de etapas según cada caso; por ejemplo, para un código C(7, 4) usaríamos el método basado en g(x).


Procesamiento del Síndrome y Detección de Errores

Procesamiento del Síndrome

    Recordemos que el síndrome era, por ser también código lineal, s = r·HT

    Por lo tanto, si s(x)0, se ha producido un error.

    El primer paso será procesar el síndrome. Para calcular el síndrome vamos a ver que se puede usar el mismo esquema del codificador:

Decodificación

Teorema:

Demostración:

Tabla Estándar

  
    Utilizaremos la tabla estándar (o matriz típica) de la misma forma que lo hacíamos con los códigos lineales.

    La tabla estándar me da los vectores de corrección que debo sumar a los vectores recibidos.

 

Propiedades de la Detección de Errores

 

    1. Si g(x)distinto del polinomio 1 => Detecto todos los errores simples
    2. Si g(x) múltiplo de (1 + x) => Detecto todos los errores impares

   Demostración:

     Un error e(x) de peso impar cumple la propiedad de que e(x=1) = 1 lógicamente.
    Por tanto e(x) no puede ser múltiplo de (1+x) ya que de lo contrario e(1)=0 cosa que es imposible.
    Como sólo no detectamos los errores que pertenecen al código, no detectaríamos los errores tales que e(x) fuera múltiplo de g(x) en este caso de (1+x).
    Por tanto, como si e(x) es de peso impar hemos visto que no es múltiplo de (1+x), podemos decir que si e(x) es de peso impar detectamos siempre el error si se cumple que g(x) es múltiplo de (1+x).

    3. Si g(x) tiene como factor a un polinomio primitivo detecta todos los errores dobles, siendo un polinomio primitivo aquel que:

Detección de Errores Ráfaga

    A veces se producen muchísimos errores en pocas milésimas de segundo. A esto se le denomina ráfaga.
Un error de tipo ráfaga tiene un esquema o forma como ésta:

    Sabemos que no podemos detectar los errores que pertenezcan al código y que una palabra que pertenezca al código es múltiplo de g(x), v(x)=a(x)g(x)

    1. Todo código cíclico C(n,k) detecta ráfagas de longitud menor o igual que n-k

    Demostración:
   
Sabemos que los errores indetectables son aquellos que pertenecen al código. Supongamos que tenemos un vector de error que tiene una longitud menor o igual que n-k. Si perteneciera al código, tendríamos que el polinomio de grado mínimo sería él mismo o una rotación de él, lo cual es imposible ya que por definición el polinomio de grado mínimo tiene una longitud entre el primer "1" y el último de n-k+1, por tanto ninguna ráfaga de error con longitud menor o igual a n-k pertenece al código y por tanto es detectable.
    Matemáticamente debemos demostrar que:

    2. Si la longitud de la ráfaga de error es igual a n-k+1 entonces detectamos todas menos la que coincide con el polinomio g(x).
    Definimos:

    3. Además si la longitud de la ráfaga de error es mayor que n-k+1 entonces detectaremos todas las ráfagas que no coincidan con palabras del código, es decir todas las ráfagas que no sean múltiplos de g(x). Para ver cual es aquí la fracción de ráfagas indetectables decimos:

    Longitud de la ráfaga = L > n-k+1

    Palabra del código: v(x)=a(x)g(x)
    Veamos cuales son los grados de los términos de la ecuación anterior:

  • grado (v(x))= L-1, siendo L='longitud de v(x)'
  • grado (g(x))= n-k

    Por tanto: grado(a(x))= L-(n-k)-1 (que se corresponde con una longitud de L-(n-k).

 

Códigos Cíclicos de Hamming

 

Definición

 

    Un código de C(n,k) se considera de Hamming si tiene una longitud L=m-1, con m mayor o igual a 3, y es generado por un p(x) primitivo de grado m.

 

Teorema

 

    La matriz H de un Código Hamming, lineal o cíclico, es tal que todas sus columnas son distintas de cero, como por ejemplo:

    Por otro lado sabemos que la matriz H de un código cíclico tiene la siguiente forma cuando está en forma sistemática:

 

Demostración

  • No hay ninguna columna igual a cero

  • Cada columna tiene al menos dos unos

  • Todas las columnas son distintas

    Al cumplirse las tres condiciones, la matriz H de un código cíclico sistemático tiene sus m-tuplas distintas de cero.

 

Códigos Recortados

 

    Estos códigos nos sirven para implementar unas características pedidas. Los pasos para conseguir estos códigos son:

  • Partimos de un código C(n,k) cíclico y consideramos el conjunto de vectores de este código que tengan sus "L" bits más significativos igual a cero ("L" arbitrario). Tendremos 2k-L vectores que cumplan esta condición.

  • Ahora formamos un código C´ tal que a todas las palabras del código les quito esos "L" bits y lo que obtengo es un código recortado que cumple las siguientes características.

  • Si partimos de C(n,k) obtenemos C´(n-L,k-L). Por ejemplo, si tengo C(10,7) y L=3, obtengo C´(7,4).

  • Es un código lineal pero no cíclico.

  • Tiene al menos las mismas propiedades detectoras y correctoras que C(n,k).

  • Los circuitos de codificación/decodificación son los mismos que teníamos pero incluyendo un número mayor de desplazamientos.

  Codigos Lineales

Código lineal   

 

    A un código bloque de longitud n y 2k palabras código se le llama código lineal (n,k) si y sólo si sus 2k palabras código forman un subespacio k-dimensional del espacio vectorial de las n-tuplas sobre el cuerpo finito correspondiente.

    De hecho, un código es lineal si y sólo si la suma de módulo 2 de dos palabras código es también una palabra código.

    Dado que un código lineal (n,k) C es un subespacio k-dimensional del espacio de vectores Vn de las n-tuplas binarias, es posible encontrar k palabras código linealmente independientes, g0, g1,..., gk-1 en C, de tal forma que cada palabra código v en C es una combinación lineal de esas k palabras código: v = u0 g0 + u1 g1 + ... + uk-1 gk-1 donde ui es un elemento del cuerpo base para i mayor igual que cero y menor que k. Ahora vamos a colocar estas k palabras código linealmente independientes como las filas de una matriz k x n:

donde g = (gi0 , gi1 , ..., gi,n-1). Si u = (u0 , u1 , ..., uk-1) es el mensaje que va a ser codificado. La palabra código correspondiente puede ser dada de la siguiente manera:

v = u G = u0 g0 + u1 g1 + ... + uk-1 gk-1

    Evidentemente la filas de G generan el código lineal (n,k) C. Por esta razón a la matriz G se la llama matriz generadora de C. Nótese que cualquier conjunto de k palabras código linealmente independientes pueden ser usadas para formar una matriz generadora del código. Por lo tanto, un código lineal (n,k) esta completamente definido por las k filas de la matriz generadora G. Como consecuencia de esto, el codificador solo tiene que almacenar las k filas de G y formar una combinación lineal de estas k filas basada en el mensaje de entrada u.

Forma sistemática

 

    Una propiedad deseable en un código lineal es una estructura sistemática de las palabras código como la mostrada en la siguiente figura, donde una palabra código se divide en dos partes: la parte del mensaje y la parte de redundancia. La parte del mensaje consiste de k bits de información inalterada ( o mensaje) y la parte de redundancia consiste de de n - k bits de comprobación, los cuales son una suma lineal de los bits de información. A un código lineal de bloque con esta estructura se le llama código lineal sistemático de bloque .

    Forma sistemática de una palabra código:

    Un código lineal (n,k) sistemático queda completamente definido por una matriz G kxn de la siguiente forma:

donde pij son del cuerpo base.

      Con Ik denotamos a la matriz identidad de dimensión k. Con lo que G = [P Ik].

    Hay otra matriz útil asociada con cada código lineal de bloque. Para cada matriz G de dimensiones k x n con k filas linealmente independientes, existe una matriz H de dimensiones ( n - k ) x n con n - k filas linealmente independientes de tal manera que cada vector en el espacio de las filas de G es ortogonal a las filas de H y cada vector que es ortogonal a las filas de H esta en el espacio de las filas de G . Como consecuencia de esto, podemos describir el código lineal (n,k) generado por G de esta forma alternativa:

    Una n-tupla v es una palabra código en el código generado por G si y sólo si v HT = 0. Esta matriz H es la matriz de control del código.

    Si la matriz generadora de un código lineal (n,k) está en la forma sistemática, la matriz de control tiene la siguiente forma: H = [ In-k (-PT)] =

    Donde PT es la transpuesta de la matriz P.

 

Síndrome y detección de errores

    

    Consideramos un código lineal (n,k) con su matriz generadora G y su matriz de comprobación de paridad H. Sea v una palabra código que se transmite en un canal ruidoso, y r es el vector recibido a la salida del canal. Debido a que el canal es ruidoso, r puede ser distinto de v.

 

    El vector suma de r y v es e; e es una n-tupla tal que ei=1 si ri es distinto de vi y ei=0 si ri=vi. A esta n-tupla se le llama vector de error. Los 1's que aparecen en e son errores de transmisión producidos porque el canal es ruidoso.

    El receptor recibe r que es la suma de la palabra código transmitida y el vector de error.

    Cuando recibe r, el decodificador debe determinar si contiene errores de transmisión. Si se detectan errores, el decodificador intentará corregirlos (FEC) o pedirá una retransmisión (ARQ)

    Cuando se recibe r, el decodificador calcula la siguiente (n-k)-tupla: s= r HT = ( s0, s1,..., sn-k-1 ), esta n-tupla es el sindrome de r.

    s = 0 si y sólo si r es una palabra código ( el receptor acepta r como la palabra código transmitida), y s es distinto de 0 si y sólo si r no es una palabra código ( el receptor detecta la presencia de un error ). Pero, es posible que los errores no sean detectables (i.e., r contiene errores pero s = 0 ). Esto sucede cuando el vector de error es idéntico a una palabra código no nula. En este caso, r es la suma de dos palabras código y por lo tanto el síndrome es igual a cero. Estos errores son errores indetectables. Como hay 2k - 1 palabras código no nulas, hay 2k - 1 errores indetectables.

 

Distancia mínima de un código.

 

    Tomamos una n-tupla v = ( v0, v1, ..., vn-1). El peso Hamming ( o simplemente peso ) de v, que se denota como w(v), se define como el número de componentes distintas de cero de v. Por ejemplo, el peso de v = ( 1 0 0 1 0 1 1 ) es 4.

    Sean v y w dos n-tuplas, la distancia Hamming ( o simplemente distancia ) entre v y w, que se denota como d(v,w), se define como el número de dígitos en el mismo sitio que tienen diferentes. Por ejemplo, la distancia Hamming entre v = ( 1 0 0 1 0 1 1 ) y w = ( 0 1 0 0 0 1 1 ) es 3; tienen diferentes las posiciones cero, uno y tres.

    La distancia Hamming es una función métrica que satisface la desigualdad triangular. Sean v,w y x tres n-tuplas, entonces:

    d(u,w) + d(w,x) >= d(v,x).

    La demostración de esta desigualdad se deja como ejercicio.

    De todo esto se deduce que la distancia Hamming entre dos n-tuplas, v y w, es igual a el peso Hamming de la suma de v y w, esto es,

d(v,w) = w( v + w )

    Dado un código bloque C, se puede calcular la distancia Hamming entre cualquiera dos palabras código distintas.     

    La distancia mínima de C ( dmin) se define como:

            dmin = min { d(v,w) : v,w pertenecen a C, v distinto de w }.

    Sea C un código lineal, la suma de dos vectores es también un vector código. Por lo tanto, la distancia Hamming entre dos vectores código en C es igual al peso Hamming de un tercer vector código en C. De esto obtenemos que: dmin = min { d(v,w) : v,w pertenecen a C, v distinto de w }=
= min { w(x) : x pertenece a C, x distinto de 0 } = wmin.

wmin es el peso mínimo del código lineal C. De lo cual obtenemos el siguiente teorema:

Teorema

    

    La distancia mínima de un código lineal de bloque es igual al mínimo peso de sus palabras distintas de cero.

 

Teorema

    

    Sea C un código lineal (n,k) con su matriz de comprobación de paridad H . Para cada vector código de peso Hamming l, existen l columnas de H tales que el vector suma de esas columnas es igual al vector cero. Reciprocamente, si existen l columnas de H cuyo vector suma es el vector cero, existe un vector código con peso Hamming l en C.

demostración.

    Corolario 1. Sea C es un código bloque lineal cuya matriz de comprobación de paridad es H . Si no d - 1 o menos columnas de H suman 0, el código tiene un peso mínimo de por lo menos d.

    Corolario 2. Sea C un código lineal cuya matriz de comprobación de paridad es H . El peso mínimo ( o la mínima distancia ) de C es igual al menor número de columnas de H que suman 0.

 

Propiedades de detección y corrección de errores de un código bloque

 

Propiedades detectoras

 

    Cuando se transmite un vector código v por un canal ruidoso, un vector de error con l errores provoca que el vector recibido r sea diferente del vector v en l posiciones [ i.e., d(v,r) = l ]. Si la distancia mínima del código C es dmin, cada pareja de dos vectores de C tienen al menos dmin posiciones distintas. Por lo tanto, cualquier vector de error con dmin - 1 o menos errores da un vector r que no es una palabra código de C. Cuando el receptor detecta que el vector recibido no es una palabra código de C, el error ha sido detectado.

    Por lo tanto, un código bloque con distancia mínima dmin es capaz de detectar todos los patrones de error de dmin - 1 o menos errores

    Un código bloque detecta todos los patrones de error de dmin - 1 o menos errores, pero también detecta una gran fracción de los patrones de error con dmin o más errores. En realidad, un código lineal (n,k) es capaz de detectar 2n - 2k patrones de error de longitud n.

    De entre los 2n - 1 patrones de error distintos de cero, hay 2k - 1 patrones de error que son idéticos a a las 2k - 1 palabras código. Si sucede cualquiera de esos 2k - 1 patrones de error, la palabras código transmitida, v se transforma en otra palabras código, w. Por lo tanto, se recibe w y su sídrome es cero. En este caso, el decodificador acepta w como la palabra transmitida y realiza una decodificación incorrecta. De todo esto concluimos que hay 2k - 1 patrones de error que son indetectables

    Hay 2n - 2k patrones de error detectables. Para n suficientemente grande, 2k - 1 es en general mucho mas pequeño que 2n. Por lo tanto, sólo una pequeña fracción de errores pasa por el decodificador sin ser detectados.

 

Probabilidad de no detectar un error

    Sea C un código lineal (n,k). Sea Ai el número de vectores del código de peso i. A los números A0, A1, ..., An se les llama distribución del peso de C. Si C se usa sólo para detección de errores en un BSC, la probabilidad de que el decodificador falle al detectar errores se puede calcular como la distribución del peso de C.

Propiedades correctoras

    

    Si un código bloque C con distancia mínima dmin se usa para corregir errores aleatorios, es conveniente saber cuantos errores es capaz de corregir dicho código.

    La distancia mínima es par o impar. Por lo tanto, podemos elegir un entero t tal que: 2t + 1 <= dmin <= 2t + 2

Probabilidad de decodificar de forma incorrecta

    Si usamos un código bloque, que es capaz de corregir t errores, únicamente para corregir en un canal BSC con probabilidad de error p, la probabilidad de que el decodificador realice una decodificación incorrecta es:

 

Matriz Típica y decodificación de síndrome

 

Partición como método de decodificación

 

    Sea C(n,k) un código lineal y v1,v2,..., v2k los vectores código que componen C. Si enviamos un vector código cualquiera a través de un canal ruidoso, el vector símbolo recibido estará dentro de las n-tuplas (U1,...,Un).

Todo sistema de decodificación divide el total de vectores en 2ksubconjuntos disjuntos D1,D2,...,D2k. En el método que veremos cada palabra código vj se encuentra en un y sólo un subconjunto Dj.Si el vector recibido rj se encuentra en ese subconjunto Dj, se decodificará como vj.

 

Construcción de la Matriz Típica

 

    Empezamos colocando en la primera fila los 2k vectores del código conel vector nulo v1=(0,0...,0) como primer elemento. De las 2n-2k n-tuplas restantes se toma una e2 como vector de error y se sitúa debajo del v1, obteniendo el resto de elementos de la fila como suma de e2 con los vectores código de la fila primera poniendo e2+vj bajo el vector vj. Para la tercera fila se toma otro que no se encuentre en las dos primeras y se le llamae3.

    El resto de la fila lo forman las palabras e3+vj que se sitúa bajo vj. Así continuaremos el proceso hasta que todas las n-tuplas seanusadas quedando la matriz:

 

Teorema

 

    En una fila de una matriz típica no existen dos n-tuplas iguales. Cada n-tupla aparece en una y sólo una fila.

 

Demostración

 

    Se deduce pues que hay 2n-k filas distintas cada una con 2k elementos distintos. Estas filas son denominadas coconjuntos del código C y la primera n-tupla de cada coconjunto se denomina líder del coconjunto. Cualquier elemento del coconjunto puede ser líder del mismo, permutándose los elementos, pero sin cambiar el coconjunto.

 

Teorema

    

    Todo código lineal de bloque es capaz de corregir 2n-k patrones de error.

 

Demostración

 

    Para minimizar la probabilidad de error hemos de tomar como líderes de los coconjuntos los patrones de error más probables, que en un BSC son los de menos peso. Por consiguiente, al formar la matriz típica, deben elegirse los líderes de los coconjuntos como un vector del menor peso entre los que aún no han sido incluidos. Así el líder tiene mínimo peso en su coconjunto, siendo la decodificación basada en la matriz típica una decodificación de mínima distancia.

Demostración

    es el número de vectores líderes de coconjunto de peso i. Podemos halla probabilidad de error a partir de esta distribución de peso mediante la fórmula siguiente:

Teorema

 

Para un código lineal C(n,k) con distancia mínima dmin, todas las n-tuplas de peso t=[(dmin-1)/2] o menor pueden ser usadas como líderes de coconjuntos de una matriz típica de C. Si todas las n-tuplas de peso t o menor son usadas, hay al menos una n-tupla de peso t+1 que no puede ser usada como líder de coconjunto.

 

Demostración

 

    Este teorema nos confirma que un código lineal C(n,k) con distancia mínima dmin, es capaz de corregir todos los patrones de error de [(dmin-1)/2 o menos errores, pero no es capaz de corregir todos los patrones de error de peso t+1.

 

Teorema

 

    Todas las 2k n-tuplas de un coconjunto tienen el mismo síndrome. Los síndromes para diferentes coconjuntos son distintos.

 

Demostración

 

    Sabemos que el síndrome de una n-tupla es una (n-k)-tupla y hay 2(n-k) (n-k)-tuplas.

    Usando la correspondencia uno a uno que existe entre un líder de coconjunto y un síndrome podemos formar una tabla de decodificación, que es un método mucho más simple que usar la matriz típica. La tabla contiene los 2(n-k) líderes de coconjuntos y sus correspondiente síndromes. La decodificación consta de tres pasos:

        1. Calcular el síndrome del vector recibido r, multiplicándolo por la matriz H traspuesta.

        2. Localizar el líder del coconjunto cuyo síndrome es igual al hallado. Entonces dicho líder ( ei ) se considera el patrón de error causado por el canal.

        3. Decodificar el vector recibido r en el vector código v = r + ei.

    A este esquema de decodificación se le denomina decodificación de síndrome. El resultado de aplicar este método a un código lineal C(n,k) es un retraso en decodificación mínimo y una probabilidad de error mínima.

No obstante para n-k grandes, el esquema se vuelve poco práctico.

 

Probabilidad de error no detectado para códigos lineales sobre un BSC

   

    Si un código lineal C(n,k) se usa solamente para detección de errores sobre un BSC, la probabilidad de error sin detectar, Pu(E), puede ser calculado mediante la fórmula ya estudiada:

siempre que se conozca la distribución de pesos del código. Existe una relación interesante entre la distribución de peso de un código lineal y la de su código dual, que hace a menudo mucho más fácil el cálculo de Pu(E). Sea {A0, A1, ... , An} la distribución de pesos de un código lineal C(n,k) y sea {B0, B1, ... , Bn} la distribución de peso de su código dual Cd. Representando esas dos distribuciones de peso en forma polinomial:

        A(z) = A0 + A1z + ... + Anzn

        B(z) = B0+ B1z + ... + Bnzn

    Entonces A(z) y B(z) están relacionados por la siguiente identidad:

        A(z)= 2-(n-k)(1+z)nB((1-z)/(1+z))

    Esta identidad se conoce como identidad de MacWilliams. Los Polinomios A(z) y B(z) se denominan polinomios enumeradores de peso para el código lineal C y su dual Cd. De la identidad de MacWilliams vemos que si conocemos la distribución de peso del dual de un código lineal, podemos determinar la distribución de pesos de este código lineal, lo que nos da más flexibilidad en los cálculos.

    Utilizando la identidad de MacWilliams, podemos calcular la probabilidad de un error no detectado para un código lineal (n,k) a partir de la distribución de peso de su dual. Primero hacemos una transformación en la fórmula:

    Sustituyendo z = p/(1-p) en A(z) y usando el hecho de que A0 = 1, obtenemos la siguiente identidad:

    Combinando expresiones obtenemos: 1

    Y finalmente: 2

    Donde

   Aqui encontramos dos modos de calcular la probabilidad de error no detectado para un código lineal. Si n-k es menor que k, es mucho más fácil calcular Pu(E) en la fórmula anterior (2); de otro modo habremos de usar (1).

 

Códigos Hamming

 

    Los códigos Hamming fueron la primera clase de códigos ideados para corrección de errores. Estos códigos y sus variaciones han sido ampliamente usados para control de errores en comunicacion digital y en sistemas de almacenaje de información.

    Para cualquier entero positivo m>=3, existe un código Hamming con los siguientes parámetros:

Longitud del Código:

n=2m-1

Número de símbolos de información:

k=2m-m-1

Número de símbolos de comprobación de paridad:

n-k=m

Capacidad de corrección de errores:

t=1(dmin=3)

 

    La matriz de comprobación de paridad H de este código consta de todas las m-tuplas no nulas como columnas. En forma sistemática, las columnas de H están ordenadas de la siguiente forma: H=[ImQ], donde Im es una matriz identidad m x m y la submatriz Q consta de 2m-m-1 columnas, las cuales son las m-tuplas de peso 2 o más. Estas columnas pueden ser colocadas en cualquier orden sin afectar a la propiedad de distancia y distribución de peso del código. En forma sistemática, la matriz generadora del código es G=[QT I2m-m-1] , donde QT es la traspuesta de Q y I2m-m-1 es una matriz identidad de orden 2m-m-1.

    Como las columnas de H son no nulas y distintas, dos columnas no pueden sumar cero. Se sigue que la mínima distancia de un código Hamming es al menos 3. Como H consta de todas las m-tuplas no nulas como columnas, el vector suma de dos columnas cualesquiera, hi y hj, debe ser también una columna de H, hl. Así

hi+ hj+ hl= 0.

    De aquí se sigue que la mínima distancia de un código Hamming es exactamente 3. Así, el código es capaz de corregir todos los patrones de error con un error simple o de detectar todos los patrones de error de dos errores o menos.

    Si formamos una matriz típica para el código Hamming de longitud 2m-1, se pueden usar todas las (2m-1)-tuplas de peso 1 como líderes de coconjunto. El número de (2m-1)-tuplas de peso 1 es 2m-1. Como n-k=m, el c&oacyte;digo tiene 2m coconjuntos. Así, el vector 0 y las (2m-1)-tuplas de peso 1 forman todos los líderes de los coconjuntos de la matriz típica. Esto nos dice que un código Hamming corrige solamente los patrones de error simple y ningún otro. Esta es una construcción muy interesante. Un código corrector de errores de peso t se llama código perfecto si su matriz típica tiene todos los patrones de error de peso t o menor y ningún otro como líderes de coconjunto. Así, los códigos Hamming forman una clase de códigos perfectos de corrección de errores simples.

    Podemos borrar cualesquiera l comunas de la matriz de comprobación de paridad H de un código Hamming. Esto da como resultado una matriz H' de orden m x (2m-l-1). Usando H' como matriz de comprobación de paridad, obtenemos un código Hamming recortado con los siguientes parámetros:

Longitud del Código:

n=2m-l-1

Número de símbolos de información:

k=2m-m-l-1

Número de símbolos de comprobación de paridad:

n-k=m

Distancia mínima:

dmin=3

 

    Si borramos las columnas apropiadas de H, obtenemos un código Hamming recortado de distancia mínima 4. Por ejemplo, si borramos de la submatriz Q todas las columnas de peso impar, obtenemos una matriz de peso m x 2m-1: H'=[Im Q'] ,donde Q' consta de 2m-1-m columnas de peso par. Como todas las columnas de H' tiene peso par, no hay tres columnas que sumen cero. No obstante, para una columna hi de peso 3 en Q', existen tres columnas hj, hl, hs en Im tal que hi + hl + hj + hs = 0. Así, el código Hamming recortado con H' como matriz de comprobación de paridad tiene distancia mínima exactamente 4.

    El código Hamming recortado de distancia 4 puede ser usado para corregir todos los patrones de error simple y simultáneamente detectar todos los patrones de error doble. Cuando un error simple ocurre durante la transmisión de un vector código, el síndrome resultante es distinto de cero y contiene un número par de unos. No obstante, cuando ocurre un error doble, el síndrome es también distinto de cero, pero consta de un número impar de unos.

    Basándonos en estos hechos, la decodificación puede ser realizada de la siguiente manera:

    1. Si el síndrome s es cero, asumimos que el error no existió.

    2. Si s es distinto de cero y consata de un número par de unos, asumimos que el error ocurrido fue un error simple. El patrón de error del error simple que corresponde a s se suma al vector recibido para la correccín de errores.

    3. Si s es distinto de cero y contiene un número impar de unos, se ha detectado un patrón de error no corregible.

    La distribución de peso de un código Hamming de longitud n=2m-1 es conocida. El número de vectores código de peso i, Ai, es simplemente el coeficiente de zi en la expansión del polinomio siguiente:

    Este polinomio es el enumerador de peso para los códigos Hamming.