´ Matematica ´ Ampliacion Discreta ´ Justo Peralta Lopez U  A´ı ´ D  A  A´ M´

´ Codigos

1

´ Codigo Bloque y Distancia M´ınima

2

´ Codigos c´ıclicos

3

´ Codificacion

4

´ Codigos BCH

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigo Bloque y Distancia M´ınima

´ Definicion Si A es un alfabeto, una palabra de longitud n es una secuencia de s´ımbolos de dicho alfabeto. Al conjunto de todas las palabras de longitud n sobre ese alfabeto lo denotamos por A n . ´ Definicion ´ Un (n, M )-codigo bloque C sobre un alfabeto A , es un subconjunto C de A n , con |C | = M. ˜ o el numero ´ Normalmente, hablaremos de n como la longitud de C y de M como el tamano ´ de palabras codigo de C. ´ Definicion ´ El peso Hamming de una palabra del codigo, x = (x1 , x2 , . . . , xn ), al cual denotaremos por ´ w (x ),es el numero de componentes distintos de cero. ´ Definicion ´ La distancia Hamming entre dos palabras del codigo, x e y, a la cual denotaremos por ´ d (x , y ), es el numero de posiciones en que dichas palabras difieren. Es decir d (x , y ) = w (x − y ) = w (y − x ) ´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigo Bloque y Distancia M´ınima

´ Definicion ´ La distancia m´ınima, dmin , de un codigo C es la m´ınima de las distancias entre todos los ´ pares de las palabras del codigo. Teorema ´ Es necesario y suficiente que la distancia m´ınima de un codigo sea mayor o igual que d, para poder detectar d − 1 errores o menos. Teorema ´ Un codigo C puede corregir t errores o menos si y solo si dmin ≥ 2t + 1.

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigos c´ıclicos

Sea ahora f (x ) = x n − 1 y consideremos el anillo de polinomios Fq [x ]/(x n − 1). Entonces ´ x n ≡ 1 (mod x n − 1). Luego podemos reducir cualquier polinomio modulo xn − 1 reemplazando x n por 1, x n+1 por x, etc. Ahora identifiquemos un vector a0 , a1 , ..., an−1 ∈ V (n, q) con el polinomio a (x ) = a0 + a1 x + a2 x 2 + · · · + an−1 x n−1 en F [x ]/(x n − 1) Entonces V (n, q)  F [x ]/(x n − 1) Ahora, si multiplicamos a (x ) por x, obtenemos xa (x ) = a0 x + a1 x 2 + a2 x 3 + · · · + an−1 x n = an−1 + a0 x + a1 x 2 + a2 x 3 + · · · + an−2 x n−2 . Es ´ decir, si consideramos a (x ) como una palabra de un codigo c´ıclico, multiplicar por x i es equivalente a ciclar dicha palabra i veces.

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigos c´ıclicos

Teorema ´ Un codigo C en F [x ]/(x n − 1) es c´ıclico si y solo si verifica i) a (x ), b (x ) ∈ C ⇒ a (x ) + b (x ) ∈ C ii) a (x ) ∈ C y r (x ) ∈ F [x ]/(x n − 1) ⇒ r (x )a (x ) ∈ C Corolario ´ Todo ideal en F [x ]/(x n − 1) es un codigo c´ıclico. Teorema ´ Sea C un codigo c´ıclico. Entonces ´ ´ i) Existe un unico polinomio monico g (x ) de menor grado in C ii) C =< g (x ) > iii) g (x ) es un factor de x n − 1

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigos c´ıclicos

Ejemplo ´ Codigos c´ıclicos de longitud 3 en GF(2) x 3 − 1 = (x + 1)(x 2 + x + 1) Polinomio Generador 1 x +1 x2 + x + 1 x3 − 1

´ Codigo en F [x ]/(x 3 − 1) Todo F [x ]/(x 3 − 1) {0, 1 + x , x + x 2 , 1 + x 2 } {0, 1 + x + x 2 } 0

´ Matematica ´ Ampliacion Discreta

´ Codigo en V (3, 2) Todo V (3, 2) {000, 110, 011, 101} {000, 111} {000}

´ Codigos

´ Codigos ´ Codificacion

En F [x ]/(x n − 1) basta con multiplicar por el polinomio de datos por el polinomio generador ´ modulo (x n − 1) generador. Teorema ´ Si C es un codigo c´ıclico con polinomio generador g (x ), y gr (g (x )) = r, entonces C tiene ´ n − r. Es decir, dimension C =< g (x ) >= {f (x )g (x )|deg (f (x )) < n − r }

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigos BCH

´ Definicion ´ ˜ El codigo BCH definido sobre el cuerpo GF (q). de longitud n y distancia m´ınima de diseno ´ δ es el mayor codigo c´ıclico entre cuyos ceros hay δ − 1 potencias consecutivas de la forma

αb , αb +1 , . . . , αb +δ−2 , b ≥ 0, δ ≥ 1 ´ con α una n-esima ra´ız primitiva en GF (qm ) de la unidad (siendo m el orden multiplicativo ´ ´ de q modulo n). El polinomio generador de este codigo es: g (x ) = mcm{Mαb (x ), Mαb +1 (x ), . . . , Mαb +δ−2 (x )} ´ O lo que es lo mismo, el polinomio monico de menor grado que admite como ra´ıces a las ´ n-esimas ra´ıces primitivas anteriormente descritas Teorema ´ ´ Sea ω una n-esima ra´ız de la unidad sobre Fq = GF (q). Sea C un codigo c´ıclico en ´ de menor grado Fq [x ]/(x n − 1) cuyo polinomio generador g (x ) es el polinomio monico sobre Fq que como ra´ıces a

ωb , ωb +1 , . . . , ωb +γ−2

con b ≥ 0. Entonces C tiene distancia m´ınima al menos γ.

´ Matematica ´ Ampliacion Discreta

´ Codigos

´ Codigos ´ Codigos BCH

Ejemplo ´ ´ Los conjuntos 2-ciclotomicos modulo 31 son A0 = {0} A1 = {1, 2, 4, 8, 16} A3 = {3, 6, 12, 24, 17} A5 = {5, 10, 20, 9, 18} A7 = {7, 14, 28, 25, 19} A1 1 = {11, 22, 13, 26, 21} A15 = {15, 30, 29, 27, 23}

x +1 x5 + x2 + 1 x5 + x4 + x3 + x2 + 1 x5 + x4 + x2 + x + 1 x5 + x3 + x2 + x + 1 x5 + x4 + x3 + x + 1 x5 + x3 + 1

´ El polinomio binario Mα (x )Mα3 (x ), con ceros {αi , i ∈ A1 ∪ A3 } genera un codigo binario ˜ δ = 5. Si el polinomio generador es BCH[31,21], con distancia de diseno ´ Mα (x )Mα3 (x )Mα5 (x ), con ceros en {αi , i ∈ A1 ∪ A3 ∪ A5 }, entonces genera un codigo BCH[31,16], con δ = 7. Y si el polinomio generador es Mα (x )Mα3 (x )Mα5 (x )Mα7 (x ) con ´ ceros {αi , i ∈ A1 ∪ A3 ∪ A5 ∪ A7 }, entonces genera un codigo BCH[31,11] y distancia de ˜ δ = 11. Como n es de la forma 25 − 1, todos los codigos ´ diseno descritos son primitivos.

´ Matematica ´ Ampliacion Discreta

´ Codigos