Codificacion

Codificación
Programación en Tiempo Real

Índice

Pág.

3.1 Grupos 3.1.1 Homeomorfismos 3.1.2 Isomorfismos. 3.1.3 Cíclicos. 3.1.4 Cosets 3.1.5 Teorema de Lagrange 3.1.6 Métrica de Hamming 3.1.7 Matrices Generadoras y de paridad. 3.2 Anillos. 3.2.1 Grupos de códigos. 3.2.2 Cosets líderes. 3.2.3 Matrices de Hamming. 3.2.4 Campos finitos. 3.2.5 Anillos de polinomios. 3.2.6 Polinomiosirreducibles 3.2.7 Cuadrados latinos 3.2.8 Criptografía.

3 4 4 6 7 9 10 10 15 16 20 21 23 24 25 26 27

2

Unidad 3 Codificación
3.1 Grupos
Un grupo es un par (G; _) formado por un conjunto y una operación binaria que cumple: G0 La operación es cerrada, es decir, a * b  G, para todo a,;b G. G1 La operación es asociativa, es decir, (a * b)* c = a * (b * c)) , para todo a,;b  G._ G2 El conjuntoG tiene elemento neutro, que se denotará por e, respecto de la operación. G3 Cada elemento de G tiene inverso respecto de la operación. El inverso del elemento a € G se denotará por a -1. Grupo fundamental: dado un espacio topológico X, se puede formar el conjunto de todos los lazos en X que salen de un cierto punto, considerando como equivalentes a dos lazos que se puedan superponer mediante unahomotopía (es decir, tales que se pueda deformar a uno de ellos en forma continua hasta obtener el otro). A dicho conjunto se le asigna una estructura (algebraica) de grupo, lo que determina el llamado grupo fundamental de X. Se trata de un invariante topológico muy útil. Por ejemplo, el grupo fundamental de una circunferencia es Z, el conjunto de los números enteros (Z = {..., - 3, - 2, - 1, 0,1, 2, 3, ...}), hecho que resulta claro pues todo lazo cerrado sobre la circunferencia está determinado unívocamente por la cantidad de vueltas, y el sentido en que se las recorre. El grupo fundamental de un toro es Z ´ Z, pues en este caso deben tenerse en cuenta las vueltas dadas "alrededor" del agujero, y también "a través" del mismo. Este resultado es, claro está, coherente con el hecho de queel toro puede pensarse como el producto cartesiano de dos circunferencias Estas son algunas de las propiedades que tienen los grupos: • El neutro es único. El inverso de cada elemento también es único. • El inverso del inverso de un elemento es el propio elemento: (x−1)−1 = x. • El inverso de un producto es el producto de los inversos, pero cambiado de orden:(xy) −1 = y−1x−1. • En un grupo laecuación ax = b siempre tiene solución, que es única: x = a−1b. Análogamente, x = ba−1 es la única solución de xa = b.

3

3.1.1 Homeomorfismos
Se llama homeomorfismo entre dos espacios topológicos X e Y a una función f: X® Y que resulte biunívoca y bicontinua, es decir: f es "uno a uno" (biunívoca), lo que significa que para cada elemento x Î X existe un único y Î Y tal que f(x) = y yviceversa. Esto permite definir la función inversa, f-1:Y® X f y f-1 son continuas (f es bicontinua) La noción de homeomorfismo responde a la idea intuitiva de "deformación", y determina cierta clase de equivalencia: dos espacios homeomorfos tienen las mismas propiedades topológicas.

3.1.2 Isomorfismos.
Podríamos definir el significada de un isomorfismo que 2 semigrupos simplemente parezcan iguales, oque es cuando el dominio y la imagen de un isomorfismo propio pueden ser o son idénticos. Con relación a este concepto podemos mencionar diversos teoremas, alguna de cuyas demostraciones veremos a continuación.

4

a) Teorema: La relación G es isomorfo con G’ es una relación de equivalencia entre grupos. b) Teorema: En todo isomorfismo entre dos grupos, los elementos idénticos secorresponden y los inversos de elementos correspondientes también se corresponden. c) Teorema: Todo grupo abstracto G es isomorfo con un grupo de transformaciones del grupo sobre sí mismo. Demostración: Para comprender esta demostración el lector puede tener presente la tabla indicada más arriba para n = 6. Asociemos a cada elemento a  G la transformación ta : G  G tal que ta(x) = xa. El lector puede...