Taller N° 17 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 código se define como la sumatoria de los productos entre las probabilidades y longitudes de cada símbolo. 

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

Los códigos compactos son.............................................

Son códigos de longitud variable que minimiza la longitud promedio (entropía), se los llama código de alto rendimiento. Son códigos instantáneos, por lo que ninguna palabra de código puede aparecer como prefijo de una de mayor longitud.

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

La codificación consiste en asignar las palabras de menor cantidad de símbolos a aquel mensaje de mayor probabilidad, así sucesivamente:

P(1) ≥ P(2) ≥ ... ≥ P(n-1) ≥ P(n)

L(1) ≤ L(2) ≤ … ≤ L(n-1) ≤ L(n)

Que inconveniente presentan estos códigos?

Estos códigos presentan el inconveniente de que la distribución de la fuente puede no ser conocida cuando se diseña el código.

Dentro de lo 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)R=rH(s) donde r son símbolos por segundo. R se mide en bits (de información) por segundo.

El teorema de Shannon indica que para transmitir sin errores debe valer que la tasa de información sea menor o igual a la capacidad del enlace, o sea, R≤CR≤C.

La Capacidad se define como?

La capacidad se define como C=I/T=log(n)/τ, con una señal discreta de n niveles, periodo T y cada símbolo con duración tau. Por lo tanto, hay n^ T / τ 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?

Cada letra contiene una sucesión de elementos. El punto equivale a la unidad de tiempo más baja (un segundo). La raya en cambio, tiene una duración aproximada de tres segundos, es decir tres puntos.

Para separar una letra de otra, se deja un espacio de silencio equivalente a tres puntos. En cuanto a las palabras, la distancia es de aproximadamente cinco a nueve segundos.

Para facilitar el aprendizaje de este sistema, se suele usar la regla mnemotécnica (técnica que ayuda a relacionar palabras o información con datos que ya están en nuestra memoria). En este sentido, se asocia el código de una letra con una palabra clave:

-La inicial de la palabra clave es la letra correspondiente, por ejemplo: Carro (C)

-El número de vocales que contiene la palabra clave indica la longitud de la codificación en morse de dicha letra.

-Si la vocal es una O se sustituye por una raya (-)

-Si se trata de cualquier otra vocal se sustituye por un punto (·)

-Al sustituir, solo se tendrá en cuenta los puntos y rayas obtenidos hasta la totalidad de la longitud en morse.

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

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

Taller N° 16 Rendimiento y redundancia de un código y Longitud media 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?

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. Esas secuencias fijas (secuencias de xj) reciben el nombre de palabras código. Se denominará Xi a la palabra de código que corresponde al símbolo si. Hay que notar que Xi constituye una secuencia de xj ‘s.1

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

La segunda propiedad es que todas las palabras Xi sean distintas, lo que se denomina no singular. 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?

La tercera de las propiedades es que el código sea unívocamente decodificable. 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?

Un canal de información viene determinado por un alfabeto de entrada A = {a1, a2, ......., ar}; un alfabeto de salida B = {b1,b2, ......., bs}; y un conjunto de probabilidades condicionales P(bj/ai). P(bj/ai) es la probabilidad de recibir a la salida el símbolo bj cuando se envía el símbolo de entrada ai.

Cuál es la probabilidad de error y sus reglas de decisió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 P11 P12 ...... P1s P21 P22 ...... P2s................................ Pr1 Pr2 ...... Prs P = Estrategias de Decodificación Gabriela Sanromán - 11 - 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 redundancia es la información superflua o innecesaria para interpretar el significado de los datos originales. 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?

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

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

η= H(S)/L

Codificación RLE

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

Se basa en la repetición de elementos consecutivos. El principio fundamental consiste en codificar un primer elemento al dar el número de repeticiones de un valor y después el valor que va a repetirse. Por lo tanto, según este principio, la cadena “AAAAAHHHHHHHHHHHHHH” cuando está comprimida da como resultado "5A14H". La ganancia de compresión es (19-5) / 19, es decir, aproximadamente 73,7%. Por otro lado, para la cadena "CORRECTLY", donde hay poca repetición de caracteres, el resultado de la compresión es “1C1O2R1E1C1T1L1Y”. Por lo tanto, la compresión genera un costo muy elevado y una ganancia de compresión negativa de (9-16) / 9, es decir, ¡-78%!

Ejercicio 1.3

¿Cuál sería el archivo comprimido para el siguiente bitmap de 6 × 8?

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 pixel 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 solo 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

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). Ejemplo: Un mapa de bits, en escala de grises de 8 bit de profundidad, que comienza con 12, 12, 12, 12, 12, 12, 12, 12, 12, 35, 76, 112, 67, 87, 87, 87, 5, 5, 5, 5, 5, 5, 1, . . .  se comprime como 9 ,12, 35, 76, 112, 67, 3 ,87, 6 ,5, 1,. . . , donde los números en las cajas son contadores que indican la cantidad de veces que se repite el siguiente elemento.

Cómo son las formas de muestreo en RLE.

´

Ejercicio 1.4

Hay otra razón obvia, por la que cada fila de un bitmap debería ser codificada individualmente. ¿Cuál es?

El método RLE para imágenes se basa en la idea de que los pixeles adyacentes tienden a ser Idénticos. No es común que el último pixel de una fila sea idéntico al primer pixel 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 clave .

·         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

Codificación de la fuente, Tecnicas Importantes

Código Braille:
Describa su funcionalidad para optimizar códigos.

Para optimizar códigos: Una letra es mayúscula, si va precedida del signo Mayúscula; los números tienen la misma representación que las 10 primeras letras (1–2–3–4–5–6–7–8–9–0 se corresponden, respectivamente, con a–b–c–d–e–f–g–h–i–j), y deben ir precedidos del signo Número. Puesto que en las primeras letras, la última fila del código es siempre “◦◦”, se aprovecha esta circunstancia para representar las fracciones (las dos primeras filas del código del numerador de la fracción son desplazadas.

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.

Hacer una pregunta, es absolutamente necesario, con previo aviso,  punto de ebullición caliente, subir, un examen riguroso, exactamente lo mismo, obsequio, calentador de agua, mi opinión personal, recién nacido, aplazado hasta más tarde, sorpresa inesperada, misterios sin resolver.

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

Algunas veces, es aceptable “comprimir” texto, simplemente desechando alguna informació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.

Resolver el ejercicio 1.2

Ejercicio 1.2: Un conjunto de caracteres que incluya las 26 letras en mayúsculas y el espacio, puede ser codificado con códigos de 5 bits, pero dejaría cinco códigos sin usar. Sugiérase una forma de utilizarlos.

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 más 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 se codifica en la cadena de bits “0000100010000000100000”.

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.

Utilice un organizador o tabla para conocer el código

Codificación run-lenght
Cuál es la funcionalidad más 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.

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

Compresión de texto RLE.

Cuál es la funcionalidad más 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. Sin embargo, esta cadena es más larga que la original, ya que sustituye dos letras consecutivas, con tres caracteres. Tenemos que adoptar la convención de que sólo se reemplacen por un factor de repetición, aquellos grupos compuestos por tres o más repeticiones de un mismo carácter.

Busque los algoritmos para Compresión y Descompresión

Codificación relativa

Cuál es la funcionalidad más destacada de este sistema de codificación relativa.

Esta es otra variante, a veces llamada diferenciación. 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 y también en la compresión LZW.

Codificación de la Fuente

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

Se realiza para asignar códigos binarios a información cuyo origen es textual, requiere de un proceso de conversión análogo-digital antes de ser codificada.

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

Cómo es el esquema de compresión.

Según el teorema de codificación de fuente se pueden diseñar algoritmos de codificación (y decodificación) sin pérdidas con Ī≤log N siempre que H≤log N, siendo H el límite de Ī. Los mecanismos son variados:

 l Codificación de longitud variable versus fija o Cadenas de símbolos de X (longitud fija) se mapean a cadenas de tamaño variable de símbolos del alfabeto D-ario (cuanto más frecuentes menos símbolos de D). Problemas de sincronización para saber cuándo termina la cadena de tamaño variable

o Codificación Shannon: li=ceil(-log pi ). Solamente funcionan bien bajo ciertas condiciones Analizar {a1, a2} con p1=0.0001 y p2=0.9999 [14, 1] !!!!!

o Codificación Huffman

o Codificación Shannon-Fano-Elias: se basa en F(x)=Σa≤xp(a) [Función de probabilidad acumulada] y logra códigos con li=ceil(-log pi )+1

o Codificación aritmética: se basa en la anterior y codifica bloques de n símbolos en lugar de símbolos aislados. Más eficiente pero con cierta complejidad de implementación: tamaño de buffer, precisión de cálculo,… Patente de IBM

 l Extensión de fuente

 o Previamente a la codificación se modifica (adapta) la fuente para aprovechar el codificador posterior (modificar estadísticos, orden, …)

l Códigos universales

o No es necesario conocer la fdp a priori

 o Codificación aritmética adaptativa

o Codificación Lempel-Ziv y variantes 

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

– DES: Estándar de cifrado de flujo de 52 bits usado en 1976. La cadena de 56 bits es muy corta, por lo que es capaz de comprometerse en menos de 24 horas.

     Longitud de clave: 52 bits.

     Tamaño de bloque: No

– TDES: Conocido también como 3DES o TripleDES, no es más que el estándar DES aplicado 3 veces. En realidad se dobla la longitud efectiva, siendo de 112 bits, aunque es preciso triplicar el número de operaciones de cifrado, haciendo este método de cifrado muchísimo más seguro que el DES. La longitud de la clave es de 192 bits, aunque como se ha dicho su eficacia solo sea de 112 bits.

     Longitud de clave: 192 bits (eficaces 112 bits).

     Tamaño de bloque: No

– ElGamal: Sistema de cifrado asimétrico libre de patentes y utilizado tanto para generar firmas digitales como para cifrar/descifrar. Su funcionamiento se basa en cálculos sobre “logaritmos discretos”, factorizando números muy grandes, de 150 dígitos o más. Usa para ello un número primo y dos enteros. La velocidad de cifrado y autenticación es inferior a la obtenida con RSA, las firmas producidas son más largas y los mensajes cifrados ocupan el doble que el mensaje plano.

     Longitud de clave: Sin límite. El límite lo marca el protocolo usado.

– RSA: Sistema de cifrado asimétrico, que a diferencia de los anteriores sistemas, trabaja con dos claves diferentes: una clave “pública”, y otra “privada”. Ambas son complementarias entre sí, así que un mensaje cifrado con una de ellas sólo puede ser descifrado por su contraparte. La longitud de clave va desde los 128 bits a los 4096.

     Longitud de clave: Variable: 128, 256, 1024, 2048 y 4096 bits.

Desigualdad de Karft

¿En qué consiste la desigualdad de Kraft?

Expresa las condiciones suficientes para la existencia de un prefijo y, las condiciones necesarias para la existencia de un código unívocamente decodificable para un grupo dado de longitudes de palabra. Sus aplicaciones a los códigos y arboles prefijos son usualmente empleadas en ciencias de la computación y teoría de la información.

¿Cuál es el fundamento matemático de la desigualdad de Kraft? y operación matemática importante para definir capacidad de información necesaria al momento de trabajar con volúmenes de información.

Mediante la presentación de un video y un ejercicio resuelto explique de forma clara el proceso de planteamiento y la forma de resolución más óptima.

Por favor haga click para ver su explicacion en el siguiente video: Click aqui para ver el Video

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