Códigos lineales

¿Qué tipos de códigos se conocen?

Las familias más conocidas de estos códigos son:

Códigos lineales: de Hamming, de Hamming extendidos, simplex, de Golay, de Reed- Muller, de Goppa geométricos.

Códigos cíclicos: BCH, de Reed-Solomon, de residuos cuadr´aticos, de Goppa clásicos.

Códigos no-lineales: Hadamard, Kerdock, Justesen, Preparata.

¿A qué se refiere la equivalencia y automorfismo de códigos?

Dos códigos C y D, q-arios decimos que son equivalentes si se puede obtener uno del otro a través de una combinación de operaciones de

los siguientes tipos:

1. Permutación de las posiciones.

2. Permutación de los símbolos de una posición fija.

A que se refiere un código lineal.

Un código lineal q-ario de longitud n y rango k es un subespacio L ⊂ F n q de dimensión k. Así el subespacio L es un [n, k] q-código; Si L tiene distancia d entonces L es un [n, k, d] q-código; Si L ⊂ Z n 2, en general se escribe simplemente [n, k, d]-código

Que son los códigos duales u ortogonales

Un código lineal C se llama auto ortogonal si C <=~C y se llama auto dual si la igualdad se verifica; es decir, C = ~C

Claramente, para ser autodual, es condición necesaria tener dimensión n=2 2

Codificación y decodificación de códigos lineales

Para hacer la codificación en códigos lineales usamos una aplicación lineal que tiene que ser inyectiva; luego el espacio de las palabras de longitud k verifica F^k~= C. Cuando un código es muy grande, se aprecia con claridad la necesidad de codificar y descodificar por formula. El proceso de codificación es en general, mucho más fácil que el de decodificación. La razón es que en la decodificación hemos incluido la corrección de errores, lo más costoso.

Cuáles son los constructores con códigos lineales

Pinchado, Extendido, Plotkin

A que se refiere la Cota de Hamming, Singleton y Códigos MDS

Cota de Hamming:   En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.

Cota de Singleton y Códigos MDS: Esta cota es sencilla pero muy ´útil y da lugar a los códigos de Reed Solomon, que veremos después, y que se usan para la reproducción de los CD. 4.3.1. Teorema. Para d ≤ n se tiene que Aq(n, d) ≤ q n−d+1. Demostración. Trivialmente, Aq(n, n) = q = q n−n+1 y vamos a hacer descenso. Sea d < n. Aq(n, d) ≤ qAq(n − 1, d) ≤ · · · ≤ q n−d Aq (d, d) = q n−d (q) = q n−d+1. 4.3.2. Observación. En particular, para un [n, k, d]-código lineal q-ario, k ≤ n − d + 1. 4.3.3. Definición. Un código que verifica la igualdad en el teorema anterior se conoce como código separable de distancia máxima (maximum distance separable MDS). La primera propiedad es obvia, aunque muy importante.

Investigue sobre los tipos especiales de códigos lineales: Hamming y códigos simples, de Golay y Reed-Muller

Hamming: El código de Hamming agrega tres bits adicionales de comprobación por cada cuatro bits de datos del mensaje. El algoritmo de Hamming (7.4) puede corregir cualquier error de un solo bit, pero cuando hay errores en más de un bit, la palabra transmitida se confunde con otra con error en un sólo bit, siendo corregida, pero de forma incorrecta, es decir que la palabra que se corrige es otra distinta a la original, y el mensaje final será incorrecto sin saberlo. Para poder detectar (aunque sin corregirlos) errores de dos bits, se debe añadir un bit más, y el código se llama Hamming extendido.

Golay: el código binario de Golay es un tipo de código corrector de errores usado en las comunicaciones digitales. El código binario de Golay, junto con el código terciario de Golay tiene una particularidad y conexión interesante con la teoría de los grupos esporádicos finitos en matemáticas. El código lleva el nombre en honor a Marcel J.E Golay.

Reed-Muller: Los códigos Reed-Muller son una familia de códigos lineales de corrección de errores utilizados en las comunicaciones. Los códigos de Reed-Muller pertenecen a las clases de códigos localmente estables y de códigos localmente decodificables, por lo que son útiles en el diseño de pruebas probabilísticamente verificables en la teoría de la complejidad computacional.

Investigar los siguientes códigos cíclicos:
Códigos cíclicos y anillos de polinomios

Ceros de un código cíclico y matriz de control

Codificación y decodificación en códigos cíclicos.

Codificación: La codificación de un código lineal es bien simple, basta con multiplicar la matriz generadora G del código por el bloque a codificar, esto es: Sea m ∈ Kn q el bloque a codificar y sea G una matriz generadora de nuestro código C entonces el bloque codificado será mtG. Observamos que dar un código lineal en realidad no es más que dar una matriz generatriz G y que el proceso de codificación de un bloque exige la realización de nk sumas y productos (k es la dimensión del código). En cuanto a la codificación de un código cíclico el proceso es exactamente el mismo, solo varia la forma de la matriz generatriz G que en este caso es tiene una forma particular.

Decodificación: Varia la forma de corregir el error debido a las particularidades de estos códigos, pues no va a ser necesaria guardar la tabla completa de síndrome/líder, aunque nos vamos a ver forzados a realizar alguna que otra operación más. Aparte de esto la matriz H de control posee la forma particular vista con anterioridad