Teoria de codigos S 13

Vista previa del material en texto

TEMA : Teoría de códigos
Universidad Nacional de Ingeniería
Facultad de Ingeniería Industrial y de Sistemas
CODIFICACIÓN 
Un sistema general de comunicación consta de cinco partes. Una fuente o emisor, un codificador,
un canal de comunicación, un descodificador y un destino o receptor.
Una fuente de información: es un proceso que genera símbolos pertenecientes a un alfabeto finito, en
forma discreta, o valores reales, en forma continua. Los símbolos o los valores generados son de
interés para un destino.
Un codificador: es un mecanismo que opera sobre la salida de la fuente para ponerla en una forma
adecuada a la transmisión.
Un canal: es un modelo del medio usado para la transmisión de los mensajes. En particular, puede
modelar un cable eléctrico, una banda de frecuencias de radio, un rayo de luz, una superficie
magnética, etc.
Un decodificador: es un mecanismo que normalmente realiza la operación inversa del codificador,
intentando recuperar en la forma más exacta posible el mensaje originalmente emitido por la fuente.
Definición.-Un código (bloque) C para un alfabeto fuente S y un alfabeto del canal B es una aplicación 
inyectiva, 𝐶: 𝑆 → 𝐵𝑛 . La imagen de la aplicación C se denomina conjunto de palabras código, y sus 
elementos son las palabras código. 
Codificación binaria
En la codificación binaria es necesario conocer, el sistema binario, la teoría del algebra de Boole,
estructuras matemáticas y los teoremas.
El conjunto binario 𝐵 es un grupo bajo la operación ⊕ donde dicha operación se muestra en
la siguiente tabla.
⊕ 0 1
0 0 1
1 1 0
El conjunto 𝐵𝑚 = 𝐵𝑥𝐵𝑥 ……… . 𝑥𝐵 es un grupo bajo la operación ⨁ definida por
𝑥1, 𝑥2…… . . 𝑥𝑛 ⨁ 𝑦1, 𝑦2………𝑦𝑚 = 𝑥1 + 𝑦1, 𝑥2 + 𝑦2…………𝑥𝑛 + 𝑦𝑚
Donde el elemento identidad es 𝑒 = 0,0,0… . . 0 y cada elemento es su propio inverso.
Sea 𝑒: 𝐵𝑚 → 𝐵𝑛 una función, diremos que 𝑓 es una función de codificación si representa cada 
palabra en 𝐵𝑚, como una palabra en 𝐵𝑛. Es decir si 𝑏 ∈ 𝐵𝑚 entonces 𝑒(𝑏) es la palabra 
codificada que representa a 𝑏, y su notación es dado por 𝑒(𝑚. 𝑛).
Función de codificación
Sea la función de codificación 𝑒(3,9), es decir 𝑒: 𝐵3 → 𝐵9, donde la función de
codificación, 𝑒 repite tres veces cada palabra de 𝐵3
Ejemplo
Palabra sin codificar 
000
001
010
011
100
110
111
Palabra codificadas 
𝑒 000 = 000000000
𝑒 001 = 001001001
𝑒 010 = 010010010
𝑒 011 = 011011011
𝑒 100 = 100100100
𝑒 110 = 110110110
𝑒 111 = 111111111
e:
Función de codificación
Definición.- Sea función de codificación 𝑒: 𝐵𝑚 → 𝐵𝑛, si 𝑥 ∈ 𝐵𝑛, entonces el número de 
unos de elemento 𝑥, se le denomina peso de 𝑥, y se denota como 𝑥 .
Ejemplo
Determinar el peso de cada una de las siguientes palabras en 𝐵5
a) 𝑥 = 11100 b) 𝑦 = 00000
Aplicando la definición 𝑥 = 3, 𝑦 = 0
Distancia mínima
La distancia mínima de una función de codificación 𝑒: 𝐵𝑚 → 𝐵𝑛, es la mínima de las
distancias entre todas las distintas parejas de palabras codificadas es decir.
𝑑 𝑥, 𝑦 𝑚𝑖𝑛 = 𝑚𝑖𝑛 𝑑 𝑒 𝑥𝑗 , 𝑒 𝑦𝑗 , 𝑥𝑗 ≠ 𝑦𝑗1 ≤ 𝑗 ≤ 𝑛
Donde las distancias entre parejas de palabras estarán por el peso
Ejemplo
Sea la función de codificación 𝑒(2,5) definida mediante la siguiente codificación
𝑒: 𝑒1 00 = 00000
𝑒2 01 = 01110
𝑒3 10 = 00111
𝑒4 11 = 11111
Hallar la distancia mínima de la función de codificación
Solución
Realizando las operaciones con el operador suma directa y la definición,
obtenemos los siguientes resultados que se muestran a continuación
𝑑(𝑒1, 𝑒2) = 𝑒1⨁𝑒2 = 3
𝑑(𝑒2, 𝑒3) = 𝑒2⨁𝑒3 = 2
𝑑(𝑒3, 𝑒4) = 𝑒3⨁𝑒4 = 2
𝑑(𝑒1, 𝑒3) = 𝑒1⨁𝑒2 = 3
𝑑(𝑒1, 𝑒4) = 𝑒1⨁𝑒2 = 4
𝑑(𝑒2, 𝑒4) = 𝑒1⨁𝑒2 = 2
Donde la distancia mínima será 2.
Teorema
Una función de codificación 𝑒: 𝐵𝑚 → 𝐵𝑛, puede detectar 𝑘 o menos errores si y solo si su
distancia mínima es al menos 𝑘 + 1.
Sea la función de codificación 𝑒(3,8) definida mediante la siguiente codificación
Ejemplo
𝑒: 𝑒1 000 = 00000000
𝑒2 001 = 10111000
𝑒3 010 = 00101101
𝑒4 011 = 10010101
𝑒5 100 = 10100100
𝑒6 101 = 10001001
𝑒7 110 = 00011100
𝑒8 111 = 00110001
Cuantos errores detecta la función de codificación
Solución
i) Hallando la distancia mínima entre las 28 distintas parejas de palabras codificadas
obtenemos que la distancia mínima igual 3.
ii) Por el teorema la función de codificación detecta 𝑘 o menos errores si y solo si su
distancia mínima es al menos 𝑘 + 1, entonces de acuerdo al dato de i) y teorema tenemos.
𝑘 + 1 ≤ 3 → 𝑘 ≤ 2
Así la función detectara dos o menos errores.
Distancia de Hamming
Sean 𝑥, 𝑦 palabras códigos en 𝐵𝑛. La distancia de Hamming denotada por 𝑑(𝑥, 𝑦), entre 𝑥 y 𝑦 es el
peso 𝑥 ⊕ 𝑦 de 𝑥 ⊕ 𝑦. Así la distancia entre 𝑥 = (𝑥1, 𝑥2…… . . 𝑥𝑚) y 𝑦 = (𝑦1, 𝑦 …… . . 𝑦𝑚) es el
número de los valores 𝑖 talque 𝑥𝑗 ≠ 𝑦𝑗, es decir el número de posiciones que difieren 𝑥, y 𝑦.
Ejemplo
Determinar la distancia entre 𝑥, 𝑦 palabras códigos en 𝐵𝑛, dadas a continuación.
a) 𝑥 = (110110), 𝑦 = (000101)
b) 𝑥 = (001100), 𝑦 = (010110)
Solución
a) 𝑥 ⊕ 𝑦 = 110011 → 𝑥 ⊕ 𝑦 = 4
b) 𝑥 ⊕ 𝑦 = 011010 → 𝑥 ⊕ 𝑦 = 3
Propiedades de la función distancia 
Sea 𝑥, 𝑦, 𝑧 elementos de 𝐵𝑛 entonces 
a) 𝑑 𝑥, 𝑦 = 𝑑(𝑦, 𝑥)
b) 𝑑 𝑥, 𝑦 ≥ 0, 𝑥, 𝑦 ∈ 𝐵𝑛
c) 𝑑 𝑥, 𝑦 = 0 ↔ 𝑥 = 𝑦
d) 𝑑 𝑥, 𝑦 ≤ 𝑑 𝑥, 𝑧 + 𝑑(𝑧, 𝑦) (desigualdad triangular)
Grupos de código
Consideremos que 𝐵𝑛,⊕ sea un grupo, luego utilizando la propiedad de 𝐵𝑛
definimos lo siguiente.
Una función de codificación 𝑒: 𝐵𝑚 → 𝐵𝑛es un grupo de código si
𝑒 𝐵𝑚 = 𝑒 𝑏 ∕ 𝑏 ∈ 𝐵𝑚 = 𝑟𝑎𝑛(𝑒), es un subgrupo de 𝐵𝑛
Es decir 𝑒 𝐵𝑚 = 𝑁 ⊆ 𝐵𝑛, es un subgrupo de 𝐵𝑛 si cumple las condiciones 
a) La identidad de 𝐵𝑛 es también de 𝑁
b) si 𝑥 y 𝑦 pertenecen a 𝑁, entonces 𝑥 ⊕ 𝑦 ∈ 𝑁
c) si 𝑥 ∈ 𝑁 entonces su inverso está en 𝑁
Sea la función de codificación 𝑒(3,6) definida mediante la siguiente codificación
𝑒: 𝑒1 000 = 000000
𝑒2 001 = 001100
𝑒3 010 = 010011
𝑒4 011 = 011111
𝑒5 100 = 100101
𝑒6 101 = 101001
𝑒7 110 = 110110
𝑒8 111 = 111010
Ejemplo
Probar que la función de codificación es un grupo de código
Prueba
Por demostrar que conjunto de palabras codificadas
𝑁 = 000000,001100,010011,011111,100101,101001,110110,111010 es un subgrupo de 𝐵6.
a) si 𝐵6,⊕ es un grupo entonces tiene elemento identidad 𝑒 ∈ 𝐵6 dado por 𝑒 = 000000,y
si observamos en conjunto 𝑁 el elemento identidad 𝑒 ∈ 𝑁.
b) si 𝑥, 𝑦 ∈ 𝑁 → 𝑥 ⊕ 𝑦 ∈ 𝑁
En efecto haciendo todas las operaciones de cerradura con el operador ⊕ obtenemos que cumple que 
para todos los elementos 𝑥, 𝑦 ∈ 𝑁,𝑥 ⊕ 𝑦 ∈ 𝑁
c) Cada elemento 𝑥 ∈ 𝑁 tiene inverso en 𝑁, dado que es su propio inverso 
es decir 𝑥 ⊕ 𝑥 = 𝑒 = 000000, por lo tanto 𝑁 es un subgrupo de 𝐵6
Por lo tanto la función de codificación es un grupo de código.