- 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.
|
Blog personal: El hilo del laberinto
