Rendimiento y redundancia de un código y Longitud media de un código y Códigos compactos

Que representa la longitud media de un código?

La longitud media de un codigo se define como la sumatoria de los productos entre las probabilidades y longitudes de cada simbolo.

La longitud media de un código cómo se la alcanza?

Sea C un código que asocia a cada i x E X , una palabra código C (x i) . Sea l (xi) la longitud de cada una de esas palabras código y p (x i) la probabilidad del símbolo xi . Se define la longitud media del código, L, mediante la ecuación: 

Los códigos compactos son 

Se denomina código compacto a aquel en el que cada carácter puede tener longitud diferente, buscando en general que cada mensaje, pueda transmitirse en el menor número posible de símbolos. 

La codificación de códigos compactos consiste en?

Un código se dice compacto u óptimo si es unívocamente decodificable y es de longitud media mínima (respecto a todos los demás códigos univocos sobre los mismos alfabetos fuente y codigo).

Que inconveniente presentan estos códigos?

Los códigos de bloque suelen tener limitada capacidad de corrección de errores alrededor de 1 o 2 bits erróneos por palabra de código. Son códigos de bajo rendimiento debido a que tienen una gran redundancia (una palabra de código de Hamming tiene más bits de paridad que de información). Se podría pensar que si el número de bits de paridad es incrementado esto debería posibilitar la corrección de más y más errores. Sin embargo, agregando más y más bits de paridad, el ancho de banda aumenta igualmente

Dentro de la codificación de códigos compactos cómo se define la tasa de información?

La tasa de información R se define como 

R=rH(s)$$$$

 donde r son símbolos por segundo. R se mide en bits (de información) por segundo.

La Capacidad se define como?

La capacidad se define como 

C=IT=log(n)τ$$$$

, con una señal discreta de n niveles, periodo T y cada símbolo con duración tau. Por lo tanto, hay 

nTτ$$$$

 estados posibles, donde la probabilidad de cada uno es la inversa de dicha cantidad.

Mediante un análisis corto explique Cómo funciona El código morse?

el Código Morse, que se ha construido sobre la base de idioma inglés. Este código permite que un texto redactado en ese idioma sea transmitido con la menor cantidad de símbolos posible. Por lo tanto, los símbolos más frecuente tienen menor cantidad de caracteres que los menos habituales. 
Para determinar la codificación más conveniente, su constructor estudió la frecuencia de aparición de cada letra a codificar en lo textos en idioma inglés y le asignó una menor cantidad de símbolos a la letras cuya frecuencia se utilización es mayor. 

Utilizando recursos de la web, traduzca el siguiente texto a morse
"Código no Singular 
Se denomina código no singular a aquel código bloque en el cual a cada símbolo codificado le corresponde una única codificación. 
El código ASCII es un ejemplo de este tipo de código. "

-.-. -.. .. --. --- / -. --- / ... .. -. --. ..- .-.. .- .-. / ... . / -.. . -. --- -- .. -. .- / -.-. -.. .. --. --- / -. --- / ... .. -. --. ..- .-.. .- .-. / .- / .- --.- ..- . .-.. / -.-. -.. .. --. --- / -... .-.. --- --.- ..- . / . -. / . .-.. / -.-. ..- .- .-.. / .- / -.-. .- -.. .- / ... -- -... --- .-.. --- / -.-. --- -.. .. ..-. .. -.-. .- -.. --- / .-.. . / -.-. --- .-. .-. . ... .--. --- -. -.. . / ..- -. .- / -. .. -.-. .- / -.-. --- -.. .. ..-. .. -.-. .- -.-. .. -. .-.-.- / . .-.. / -.-. -.. .. --. --- / .- ... -.-. .. .. / . ... / ..- -. / . .--- . -- .--. .-.. --- / -.. . / . ... - . / - .. .--. --- / -.. . / -.-. -.. .. --. --- .-.-.- .-.-.

Rendimiento y redundancia de un código

Cuál es el objetivo de la codificación?

La codificación es la operación que permite pasar del alfabeto fuente al alfabeto código. 

Los códigos que deben tener propiedades?

Se tendrá en cuenta sólo aquellos códigos que posean ciertas propiedades suplementarias

Qué constituye la primera propiedad de código?

La primera de estas propiedades es que el código constituya un bloque. Esto es un código que asigna cada uno de los símbolos del alfabeto fuente S a una secuencia fija del alfabeto código x.

La segunda propiedad a que se refiere exactamente, cuál es su tabla de descripción?

 Se denomina código no singular aquel bloque de código en el cual a cada símbolo codificado le corresponde una única codificación.

La tercera propiedad que objetivo debe cumplir, que tabla debe ordenarse para cumplir en esta tercera propiedad?

 Para poder definir esta propiedad, se necesita conocer una nueva definición. La extensión de orden n de un bloque de código que hace corresponder los símbolos si con las palabras de código Xi , es el bloque de código que hace corresponder las secuencias de símbolos de la fuente (si1, si2,......., sin) con las secuencias de las palabras de código (Xi1, Xi2, ......, Xin).

A través de un ordenador gráfico, indique los distintas clases de códigos que se utilizan.

Cuál es el propósito de la decodificación?

El decodificador de fuente trataría de devolver la redundancia eliminada, haciendo los datos legibles.

Cuál es la probabilidad de error y sus reglas de dicisión?

La posibilidad de error de un canal será mínima con la regla de decisión que asigna a cada símbolo de salida el símbolo de entrada de mayor probabilidad.

Esta regla de decisión recibe el nombre de máxima posibilidad condicional y depende de las probabilidades a priori. La regla de decisión que se conoce como de máxima posibilidad, es independiente de las probabilidades a priori. 

Cuál es el primer teorema de Shannon?

El primer teorema de Shannon demuestra la existencia de una unidad común con la que puede medirse cualquier fuente de información. El valor de símbolo de una fuente S puede definirse en términos del número equivalente de dígitos binarios necesario para representarlo. El teorema establece que el valor medio de un símbolo S es H(S), llamado entropía de la fuente. 

Qué objetivo persigue el rendimiento y redundancia de un código?

La introducción de redundancia en la codificación tiene como finalidad mejorar la fiabilidad de la transmisión. 

A que se refiere la longitud media de un código de la fuente?

 L es la longitud media de un código de la fuente S, L no puede ser inferior a H(S).

La longitud media de un código se define como la longitud en promedio de una palabra

Con que formula se refiere el rendimiento de un código?

Según esto, se define el rendimiento de un código como:

Compresion RLE

Cómo se realiza el proceso de compresión de imágenes RLE.

La compresión de una imagen mediante RLE, se basa en la observación de que, al seleccionar un píxel de la imagen al azar, existe una probabilidad muy alta de encontrar otros adyacentes a él —sus vecinos— con el mismo color (véanse también, las Secciones 4.30 y 4.32). El compresor, por lo tanto, explora el mapa de bits fila por fila, en busca de secuencias de píxeles con el mismo color. Si el bitmap comienza, e.g., con 17 píxeles blancos, seguidos de 1 píxel negro, 55 blancos, etc, entonces sólo es necesario escribir, como datos de salida, los números: 17, 1, 55,. . . . El compresor asume que el bitmap comienza con píxeles blancos. Si esto no es cierto, se considera entonces que el mapa de bits empieza con cero píxeles blancos, y se indica en la secuencia de salida, escribiendo un 0 como primer run length. La resolución del bitmap también debería guardarse al principio de dicha secuencia.

Ejercicio 1.3

6, 8, 0, 1, 3, 1, 4, 1, 3, 1, 4, 1, 3, 1, 4, 1, 3, 1, 2, 2, 2, 2, 6, 1, 1. Los dos primeros, son la resolución del bitmap (6 × 8). El siguiente, indica que el primer píxel es negro. Si se almacenan usando un byte por número, el tamaño es de 25 bytes —en comparación con el del mapa de bits de tan sólo 6 × 8 bits = 6 bytes—. El método no funciona con imágenes pequeñas

Cómo se ejemplifica el proceso para la compresión de imágenes en escala de gris

RLE también puede utilizarse para comprimir imágenes en escala de grises. Cada bloque (run) de píxeles con la misma intensidad (nivel de gris) se codifica como un par (run length, valor del píxel). El run length, ocupa normalmente un byte, lo que permite secuencias de hasta 255 píxeles. El valor del píxel ocupa varios bits, dependiendo del número de niveles de gris (típicamente, entre 4 y 8 bits).

Cómo son las formas de muestreo en RLE.

Ejercicio 1.4

El método RLE para imágenes se basa en la idea de que los píxeles adyacentes tienden a ser idénticos. No es común que el último píxel de una fila sea idéntico al primer píxel de la fila siguiente

Explique el algoritmo RLE como trabaja para su funcionamiento.

El código es muy sencillo. Comienza por la conversión de la matriz —M— en un vector unidimensional —x—; para ello, guarda en f y c el número de filas y de columnas, respectivamente —[f, c] = size (M)—, y con el bucle for van introduciendo en x las filas de la matriz —M (k, :)—, una tras otra. Cada run length, continúa de una línea a la siguiente y se calculan todos a partir de x, mediante las siguientes operaciones: N = f ∗ c, calcula el número de elementos de la matriz, N. La suma de los elementos —de 2 a N— de x (x (2 : N)), con los elementos —de 1 a N − 1— de x (x (1 : N − 1)), proporciona el vector z, que contendrá unos en los lugares clave14 . Con la búsqueda de los unos en z, obtenemos una matriz unidimensional z1 (z1 = find(z == 1)), con la que se construyen dos vectores: el primero —i1—, formado por todos los elementos de z1 con N al final (i1 = [z1 N]); el segundo —i2—, formado por todos los elementos de z1 precedidos por 0 (i2 = [0 z1]). La resta i1 − i2 genera todos los run lengths de la matriz M. La desventaja del algoritmo RLE para imágenes consiste en que cuando se modifica la imagen, normalmente los run lengths tienen que ser reconstruidos por completo. La salida proporcionada por el método RLE en imágenes complejas, a veces puede ser más grande que el almacenamiento de la imagen sin comprimir (i.e., una imagen sin comprimir —un volcado píxel a píxel del bitmap original—).

Codificar el algoritmo de compresión RLE

Codigo Java

Visual

Sistemas de codificación de la fuente

Código Braille:

Describa su funcionalidad para optimizar códigos.

Este conocido código, que permite a los ciegos a leer, fue desarrollado por Louis Braille en 1820, y después de haber sido modificado varias veces, todavía se sigue utilizando hoy en día. Hay disponibles muchos libros en Braille en el National Braille Press.

Como se representan las 26 letras del alfabeto en esta codificación

resolver el ejercicio 1.1

Encuéntrense frases redundantes que formen parte de la vida cotidiana.

(1) hacer una pregunta, (2) es absolutamente necesario, (3) con previo aviso, (4) punto de ebullición caliente, (5) subir, (6) un examen riguroso, (7) exactamente lo mismo, (8) obsequio, (9) calentador de agua, (10) mi opinión personal, (11) recién nacido, (12) aplazado hasta más tarde, (13) sorpresa inesperada, (14) misterios sin resolver.2

Comprensión irreversible de texto
Cuál es la funcionalidad mas destacada de este sistema de compresión.

Esto se conoce como compresión irreversible de texto o compactación. El texto descomprimido no es idéntico al original, por lo que estos métodos no son de propósito general; sólo pueden utilizarse en casos especiales.

En casos extremos, todos los caracteres, excepto letras y espacios, pueden ser despreciados, y se puede convertir todo el texto, a mayúsculas o minúsculas1 , reduciendo así el número de signos a codificar. De esta manera, un texto en inglés estará compuesto por combinaciones de exactamente 27 símbolos, cada uno de los cuales puede ser codificado con 5 bis, en lugar de los 8 usuales.

resolver el ejercicio 1.2

Una forma razonable de utilizarlos es codificar las cinco cadenas más frecuentes en el texto. Debido a que la compresión irreversible de texto es un método de propósito particular, el usuario puede saber qué cadenas son las más comunes en el flujo de datos a comprimir; tiene que proporcionárselas al codificador y además debe escribirlas al principio de la secuencia de salida (para el uso del decodificador)

Compresión del texto Ad hoc
Cuál es la funcionalidad mas destacada de este sistema de compresión de texto ad hoc.

Si el texto contiene muchos espacios, pero no están agrupados, se pueden eliminar; sus posiciones, se indican entonces mediante una cadena de bits, que contiene un 0 por cada carácter del texto que no es un espacio y un 1 por cada espacio. Por lo tanto, el texto (Aquí hay algunas ideas), se codifica en la cadena de bits “0000100010000000100000” seguida de (Aquíhayalgunasideas).

A que se refiere el código Baudot. 

Era un código de 5 bits desarrollado por J.M.E. Baudot en torno al año 1880 para la comunicación telegráfica. Se hizo popular, y en 1950 fue designado el Código Internacional de Telégrafos Nº 1. Se utilizaba en muchos equipos de primera y de segunda generación.

Utilce un organizador o tabla para conocer el código

Codificación run-lenght
Cuál es la funcionalidad mas destacada de este sistema de compresión ruc.

La idea básica de este método es la siguiente: Si un dato d aparece n veces consecutivas en el flujo de entrada, se cambian las n ocurrencias con el par único nd. Las n apariciones consecutivas de un elemento de datos se llama run length9 de n, y este enfoque para la compresión de datos se llama codificación run-length o RLE. Aplicamos esta primera idea a la compresión de texto y luego a la compresión de imágenes.

Utilce un organizador o tabla para conocer la codificación run-length

Compresión de texto RLE.

Cuál es la funcionalidad mas destacada de este sistema de compresión de texto RLE

El reemplazo exacto de 2.⊔all⊔is⊔too⊔well con 2.⊔a2⊔is⊔t2⊔we2, es ambiguo y no funciona . Claramente, el descompresor debería tener una manera de expresar que el primer 2 es parte del texto, mientras que los demás indican el número de repeticiones de las letras o y l. Incluso la cadena 2.⊔a2l⊔is⊔t2o⊔we2l, sigue sin resolver este problema (y además no proporciona compresión alguna). Un camino para resolver este problema es preceder cada repetición con un carácter especial de cambio de código (o código de escape). Si usamos @ como carácter de cambio de código, entonces la cadena 2.⊔a@2l⊔is⊔t@2o⊔we@2l, puede ser descomprimida sin ambigüedad

Busque los algoritmos para Compresión y Descompresión

Compresión

Descompresión

Codificación relativa
Cuál es la funcionalidad mas destacada de este sistema de codificación relativa.

Esta es otra variante, a veces llamada diferenciación ([Gottlieb et al. 75]). Se utiliza cuando los datos a comprimir, están formados por una serie de números que no difieren en mucho entre sí (e.g., en la telemetría); o bien cuando se componen de cadenas similares. El último caso, se utiliza en la compresión de datos para envío por fax descrita en la Sección 2.13 y también en la compresión LZW

Codificación de la fuente

Para que se realiza la codificación de la fuente?

Para transmitir fiablemente (o con la mínima distorsión) un proceso aleatorio (la información)-
- Reducir (sin/con pérdidas) la cantidad de información [codificación de fuente]
- Diseñar sistemas transmisión con la menor probabilidad de error de bit [teoría de la comunicación]
- Diseñar códigos/sistemas de protección (detección/corrección) frente a errores [codificación de canal]

Cómo se hace esta conversión de la fuente de información.

 Mapeo del rango de una fuente a un conjunto finito de símbolos de un alfabeto D-ario
- Binario: {0,1}, {punto, raya}, …
- Ternario: {A, B, C} …
- Ejemplo: fuente:{Red, Blue}, alfabeto={0,1}, código={00,11}. 

No es óptimo pero es código Códigos:
- Palabras código de longitud fija (asignación “ciega”)
- Palabras código de longitud variable (basados en estadísticos)
- Palabras código de longitud fija 

Cómo es el esquema de compresión.

Compresión (límite H): Codificación sin pérdidas vs con pérdidas.

Compresión de texto irreversible
- En general texto se basa en código ASCII (8bits/símbolo): caracteres imprimibles 32-255 o Código Unicode (16bits/símbolo): caracteres imprimibles 0x0020-0xFFFC (32- 65.532).
- Quitar caracteres de formato, acentos, puntuación, pasar todo a mayúsculas/minúsculas (26 + ñ = 27) => 5 bits (25=32) y quedan 5 para blanco, puntuación, palabras comunes, …
- Ciertas pérdidas.

Compresión ad-hoc (reversible) de texto
- Quitar blancos y sustituir por cadena binaria de 100000100001… o 1: indica blanco, 0: carácter
- Quitar blancos de formato y sustituir por digito de número de blancos (extensión de fuente-codificación por carreras…) o Hace falta código de escape …
- Usar 7 bits para los caracteres textuales ASCII (compresión 7/8) o Más el bit anterior, lo que hace es reducir los blancos de 8 a 1.
- 403=64.000 < 216=65.536 o 40 = 26 letras, 10 dígitos, 4 símbolos de puntuación (. , ! ?) –esto es para inglés  : ni ñ, ni ¿, ni ¡, …- o Si agrupo caracteres de 3 en 3 (extensión de fuente-codificación vectorial) tengo una nueva fuente que tiene 403 símbolos y que se puede codificar con 16 bits (teniendo incluso adicionalmente símbolos adicionales): compresión 2/3 

Investigar 3 algoritmos de cifrado, explicar cuál es su fundamento.

DES (Data Encryption Standard)

Su arquitectura está basada en un sistema monoalfabético, donde un algoritmo de cifrado aplica sucesivas permutaciones y sustituciones al texto en claro. En un primer momento la información de 64bits se somete a una permutación inicial, y a continuación se somete a una permutación con entrada de 8 bits, y otra de sustitución de entrada de 5 bits, todo ello constituido a través de un proceso con 16 etapas de cifrado.

El algoritmo DES usa una clave simétrica de 64bits, los 56 primeros bits son empleados para el cifrado, y los 8 bits restantes se usan para comprobación de errores durante el proceso. La clave efectiva es de 56 bits, por tanto, tenemos 2⁵⁶ combinaciones posibles, por lo que la fuerza bruta se hace casi imposible.

3DES (Triple Data Encryption Standard)

Se basa en aplicar el algoritmo DES tres veces, la clave tiene una longitud de 128 bits. Si se cifra el mismo bloque de datos dos veces con dos llaves diferentes (de 64 bits), aumenta el tamaño de la clave.

El 3DES parte de una llave de 128 bits, que es divida en dos llaves, A y B.

Al recibir los datos, aplicamos el algoritmo DES con la llave A, a continuación se repite con la llave B y luego otra vez con la llave A (de nuevo).

3DES aumenta de forma significativa la seguridad del sistema de DES, pero requiere más recursos del ordenador.

Existe una variante del 3DES, conocida como DES-EDE3, con tres claves diferentes y una longitud de 192bits, consiguiendo un sistema mucho más robusto.

RC5

Se aplican operaciones XOR sobre los datos, pudiendo ser de 32, 64 o 128 bits. Permite diferentes longitudes de clave, y un número variable de iteraciones (la seguridad del cifrado aumenta exponencialmente cuanto mayor número de iteraciones), también funciona como un generador de número aleatorios, sumándoles a los bloques de texto rotados mediante la XOR.

Desigualdad de Kraft

Definición
Nombrada así debido a Leon Kraft. Limita la longitud de las palabras en un código prefijo: si se toma la exponencial de la longitud de cada palabra válida, el grupo resultante de valores debe seguir una función de probabilidad, es decir, su medida total debe ser menor o igual a uno (1). La desigualdad de Kraft puede ser entendida en términos de un presupuesto limitado de palabras a ser empleado, siendo las palabras más cortas, las más caras.

Dada una fuente de  n  símbolos a codificar con un alfabeto de r símbolos utilizando un conjunto de  n  palabras de longitudes l1 a ln , la desigualdad de Kraft corresponde a:







- Las longitudes de las palabras no pueden ser todas “cortas”, si hay una muy corta
debe haber otras más largas.
- No especifica cómo asignar los largos

Fundamento Matemático

Video de ejemplo de Desigualdad de Kraff

Taller N° 15

¿Qué tipos de códigos se conocen?

¿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.

Como aplicación, un resultado muy útil a la hora de hacer cálculos.

A que se refiere un código lineal.

Como hemos comentado antes, la idea subyacente de los códigos correctores de errores es la redundancia en la información. En este capítulo comentaremos la manera algebraica de controlar dicha redundancia, y de hecho, la codificación y decodificación.

Que son los códigos duales u ortogonales

 Equivalentemente, H es una matriz cuyo espacio nulo es C. Si C es un código con una matriz de generación G en forma estándar, G = (I_k | A), entonces H = (−A^t | I_n − k) es una matriz de comprobación para C. El código generado por H es llamado código dual de C.

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

Ya hemos comentado que para hacer la codificación en códigos lineales usamos una aplicación lineal que tiene que ser inyectiva (1.1.1); 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 fórmula. 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 Ya hemos visto algunos resultados generales en (2.3.2). En el caso de los códigos lineales podemos mejorarlo. Vamos al caso cuando d = 1. La demostración es trivial.

- Extendido También hemos visto ya los resultados generales en (2.3.7 y 2.3.8). Es muy fácil comprobar cualquiera de los siguientes hechos.

- La construcción de Plotkin Recordemos la definición de la construcción de Plotkin en (2.3.10). Es inmediato comprobar que cuando C1 y C2 son códigos lineales también C1 ⊕ C2 es lineal. Aún más.

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

- Cota de Hamming.- Esta cota viene a completar el estudio de los códigos perfectos. Lo que hemos visto en (2.1.20 y 2.1.21) nos indica fácilmente la demostración del siguiente resultado, que se conoce como cota de Hamming o del empaquetado esférico.

- 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.

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

- Códigos de Hamming La construcción de los códigos de Haming y algunas de sus propiedades en el caso binario las hemos visto en capítulos anteriores. Vamos a extender la definición. Sea Fq un cuerpo finito cualquiera y consideremos F r q con r ≥ 2. Llamamos código de Hamming y denotamos Hq,r a todo aquel código cuya matriz de control se construye de la siguiente manera. La denotamos con Hq,r.

- Códigos simplex Los códigos simplex son aquellos que se realizan como duales de los códigos de Hamming.

- Códigos de Golay Los códigos de Golay fueron propuestos por M. J. E. Golay en 1949. Hay binarios y ternarios. Los binarios se denotan G24, un [24, 12, 8]-lineal y G23, un [23, 12, 7] código. El segundo se obtiene pinchando el primero. Los ternarios se denotan G12 y el G11.

- Códigos de Golay binarios Se construye la matriz G24 = (I12|A12×12) donde la matriz A tiene una la caja inferior derecha de 11 × 11 y se escribe en la primera fila, en la posición i un 1 si i es cuadrado modulo 11 y un 0 en caso contrario. Después se hace un recorrido (shift) en dirección (←). Así que el bloque tiene forma cíclica

- Códigos de Golay ternarios El código de Golay ternario G12 es el [12, 6]-código sobre F3 con matriz G12 = (I6|A), donde

Se puede comprobar directamente cada una de las siguientes propiedades.

- Códigos de Reed-Muller (binarios) Los propusieron por separado (en trabajos independientes) I. S. Redd y D. E. Muller en 1954. Existe también la definición de código de Reed-Muller sobre cuerpos con otra característica. Su distancia mínima es muy pequeña pero se decodifican muy fácilmente. Hay muchas maneras de construirlos. Una de ellas se basa en la construcción de Plotkin (2.3.10).

Investigar los siguientes códigos cíclicos:

Códigos cíclicos y anillos de polinomios

Los códigos cíclicos también se llaman CRC (Códigos de Redundancia Cíclica) o códigos polinómicos. Su uso está muy extendido porque pueden implementarse en hardware con mucha facilidad.
Estos códigos se basan en el uso de un polinomio generador G(X) de grado r, y en el principio de que n bits de datos binarios se pueden considerar como los coeficientes de un polinomio de orden n-1.

Por ejemplo, los datos 10111 pueden tratarse como el polinomio x4 + x2 + x1 + x0

A estos bits de datos se le añaden r bits de redundancia de forma que el polinomio resultante sea divisible por el polinomio generador, sin generar resto.

El receptor verificará si el polinomio recibido es divisible por G(X). Si no lo es, habrá un error en la transmisión.

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

Sea C un código cíclico de orden n sobre Fq, con mcd(n, q) = 1, sea ξ una raíz n-ésima primitiva de 1, y sea S un juego completo de representantes de las clases q-ciclotómicas modulo n. Sea g(X) el generador de C (Observación 6.5.6). Como sabemos del Teorema 6.5.5 si g(X) | Xn − 1 entonces

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

Como hipótesis general, supongamos que tenemos un código cíclico C ≤ Rn tal que C = hgi, con g el polinomio generador, con gr(g) = r, así que la dimensión dim C = n − r. Comenzamos con la codificación. Vamos a ver una decodificación sistemática. Supongamos que queremos codificar la palabra a0 · · · an−r−1. 1. Hacemos a(X) = Pn−r−1 i=0 aiXn−i−1 2. Luego operamos a(X) = pg + s, con gr(s) < r. 3. Finalmente hacemos c = a − s = pg. Para decodificar, se puede proceder de la siguiente manera. 1. Se recibe un vector p ∈ Rn. 2. Se divide p = gs + t, con gr(t) < r. Es claro que si p = c + e, entonces existe s 0 ∈ Rn tal que p = c 0 g +e. La unicidad del algoritmo de la división nos dice que c = c 0 ; luego p − t es la palabra buscada. Esta decodificación es en realidad una decodificación por síndrome. Vamos a comprobar que existe una matriz de control cuyos síndromes son precisamente los restos obtenidos