Member of The Internet Defense League Últimos cambios
Últimos Cambios
Blog personal: El hilo del laberinto Geocaching

Definiciones de códigos

Última Actualización: 13 de Mayo de 2004 - Jueves

Código
Conjunto de todas las posibles palabras código.

Palabra código
Cada vector legal de un código.

Código lineal
Un código es lineal si y solo si para cualquier par de palabras código del mismo, la combinación lineal de las mismas produce otra palabra código.

Como corolario, para cualquier código lineal, la palabra código CERO (000.....00) es siempre una palabra código válida.

Código bloque
Un código bloque (n,k) toma "k" bits de la fuente y produce un bloque de tamaño "n". Cada bloque se codifica de forma independiente, sin memoria.

Un código bloque lineal se puede representar siempre como la siguiente operación matricial:

c = b*G

Donde "c" es la palabra código generada, "b" es el bloque de datos inicial y "G" es la matriz generadora del código.

Código convolucional

Código sistemático
Código bloque en el que los primeros "k" bits son idénticos a los de la fuente.

Para un código bloque lineal, su matriz generadora "G" se puede dividir en dos componentes G=(I|P): una matriz identidad "I" y una matriz adicional "P", que representa el código en sí.

Cualquier código lineal se puede transformar en un código sistemático equivalente.

Distancia Hamming
La distancia Hamming entre dos palabras código se define como el número de bits que cambian entre una palabra código y la otra.

La distancia Hamming de un código es la mínima distancia Hamming entre cualesquiera palabras código del mismo. Si el código es lineal, basta con calcular la distancia de todas las palabras código respecto a la palabra código CERO (000...00).

Código perfecto
Aquel para el que toda posible palabra recibida está a distancia "t" o menos de una y solo una palabra código. t = truncar((Distancia Hamming mínima-1)/2).

Matriz de comprobación de paridad
Sea un código bloque lineal. Sabemos que c = b * G, con G = (Ik|P). La matriz de comprobación de paridad "H" es (Pt|In-k)

Síndrome
Suponiendo una transmisión ruidosa, c' = b * G + e. El síndrome es S = c' * Ht = b * G * Ht + e * Ht. Operando en módulo 2 (binario), obtenemos S = e * Ht.

Si no hay errores, el síndrome es el vector CERO. Teniendo una tabla de errores más probables para cada síndrome posible, obtenemos un mecanismo de corrección de errores.

Se utiliza para la decodificación "dura". En general, si se puede usar decodificación "blanda", es muy preferible.

Capacidad detectora
Un código lineal binario de distancia Hamming "d" es capaz de detectar "d-1" errores.

Esta métrica se usa en la decodificación "dura".

Capacidad correctora
Un código lineal binario de distancia Hamming "d" es capaz de corregir "t" errores, con t = truncar((Distancia Hamming mínima-1)/2).

Esta métrica se usa en la decodificación "dura".

Borrado
A veces se pueden identificar datos "borrados" (no presentes, por ejemplo, o con incertidumbre alta). Si somos capaces de identificar borrados, un código puede corregirlos de forma equivalente a su capacidad detectora, que puede ser muy superior a su capacidad correctora.

Código prefijo
Se trata de un código que no tiene un tamaño en bits determinado, sino en el que cada palabra código puede tener un tamaño variable, y en el que es posible determinar la palabra código recibida en cuanto se recibe su último símbolo.

En otras palabras, ninguna palabra código es prefijo de otra.

Ejemplos de códigos prefijos son Huffman y Shannon-Fano.

También se denominan "códigos instantaneos".

Entropía de una fuente
Es la cantidad de información generada por una fuente. Trabajando en base 2 (binario), la entropía nos indica el número de bits, en media (en momentos puntuales podemos estar por encima o por debajo de ese valor "medio"), que necesitamos para transmitir fielmente los datos generados por una fuente.

Matemáticamente, la entropía de una fuente que genera mensajes X[i] con una probabilidad P[i] independiente y sin memoria, se calcula como:

entropia = -suma(P[i]*log(P[i]))

La base del logaritmo empleado depende de las unidades que nos interese. Si trabajamos en binarios, usaremos logaritmos en base dos.

Decodificación "dura"
La decodificación se realiza bit a bit, de forma independiente.

Decodificación "blanda"
La decodificación se realiza a nivel de toda la palabra código de forma simultanea. Esta decodificación proporciona resultados muy superiores, pero no siempre es factible.

Ganancia de codificación
Este valor, típicamente en decibelios (dB), nos indica el margen que hemos ganado con la codificación, para una tasa de error determinada. Es decir, nos indica los decibelios adicionales de ruido que podemos tolerar para obtener la misma tasa de error o, alternativamente, cuánto podemos reducir la potencia de la señal para obtener la misma tasa de error.

Para decodificación "blanda" y tasas de error bajas, la ganancia de codificación viene determinada por

dB= 10 * log10(distancia Hamming mínima * k/n)

Un código de paridad simple tiene una distancia de Hamming de 2, y n=k+1. A medida que crece el tamaño del bloque, la ganancia de codificación tiende a 3dB (suponiendo ruido gausiano, etc). Para el caso (7,6), la ganancia es de

Un código Hamming (7,4) tiene una distancia Hamming de 3 y una ganancia de codificación de 2'34dB, si se usa decodificación "blanda". Si usamos decodificación "dura", y la probabilidad de error es 10-5, la ganancia es de solo 0'63dB.


Historia

  • 13/May/04: Corrijo una errata menor.

  • 30/Ago/03: Primera versión de este documento.



Python Zope ©2003-2004 jcea@jcea.es

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS