Detección de errores
De Wikipedia, la enciclopedia libre.
En el ordenador, los datos están moviéndose continuamente: teclado-memoria, memoria-pantalla, etc.
Por lo tanto, debemos asegurarnos que dicho movimiento no cause errores en los datos.
El método para detectar y corregir errores es incluir en los bloques de datos transmitidos bits adicionales denominados redundancia.
Se han desarrollado dos estrategias básicas para manejar los errores:
· Incluir suficiente información redundante en cada bloque de datos para que se puedan detectar y corregir los bits erróneos. Se utilizan códigos de corrección de errores.
· Incluir sólo la información redundante necesaria en cada bloque de datos para detectar los errores. En este caso el número de bits de redundancia es menor. Se utilizan códigos de detección de errores.
Si consideramos un bloque de datos formado por m bits de datos y r de redundancia, la longitud final del bloque será n, donde n = m + r.
Bits de redundancia
De Wikipedia, la enciclopedia libre.
A veces se introducen redundancias deliberadamente para detectar posibles errores en la transmisión o grabación de información.
Por ejemplo, si queremos representar cuatro símbolos {1,2,3,4} y hacemos un código sin redundancias, se necesitan dos bits para representarlo.
Si por algún error, obtenemos otro símbolo del alfabeto, no tenemos manera de detectarlo.
Si al código anterior le añadimos un bit al final, se podrán detectar algunos errores determinados.
Si el bit que hemos añadido lo ponemos a cero, y por un error se produce un cambio en el último bit, se detectaría que ese símbolo recibido es un símbolo inválido.
Por ejemplo si recibimos un 001 en vez de un 000, sabríamos que el símbolo recibido es erróneo puesto que no existe en nuestro alfabeto.
Paridad
De Wikipedia, la enciclopedia libre.
Se trata de añadir a los n bits que forman el caracter original, un bit extra, llamado bit de paridad.
Este bit se elige de forma que el número total de bits "1" en el código sea par (código de paridad par) o impar (código de paridad impar).
· Código de paridad par: El bit de paridad será un 0 si el número total de "1" es par, y un 1 si el número total de "1" es impar.
· Código de paridad impar: El bit de paridad será un 1 si el número total de "1" es par y un 0 si el número total de "1" es impar.
· Normalmente el bit de paridad se añade a la izquierda del caracter original.
· Ejemplo: Tenemos el carácter original 0111001. El carácter resultante, añadiendo el bit de paridad a la izquierda, y dependiendo de si usamos paridad par o impar, será:
00111001 paridad par
10111001 paridad impar
Si se envía un dato y ocurre un único error, al comprobar la paridad en el receptor, éste se detectaría.
Este método, aunque resulta satisfactorio en general, sólo es útil si los errores no cambian un número par de bits a la vez, porque un número par de errores no afecta a la paridad de los datos.
Se puede concluir que el método funciona únicamente para un número impar de errores.
Por ejemplo, si transmitimos el caracter 10100000 con paridad par y recibimos 01010000, es imposible saber si los datos recibidos son correctos, porque al haberse producido cuatro errores, la paridad sigue siendo par.
Códigos autochequeo y autocorrectores
De Wikipedia, la enciclopedia libre.
Para garantizar la integridad de los datos, el hecho de añadir un único bit de paridad no siempre resulta suficiente para datos que se mueven constantemente de un lado para otro, especialmente en el caso de transmisión de datos a largas distancias, donde las señales transmitidas están expuestas a interferencias eléctricas (p.e. en una red de ordenadores, donde los datos viajan de un ordenador a otro que puede estar, incluso, en otro país).
Este problema ha conducido al desarrollo de códigos que detectan más de un error e incluso corrigen los errores que encuentran.
Algunas de estas técnicas han sido desarrolladas por el ingeniero americano R.W. Hamming, y se conocen como Códigos de Hamming.
Códigos de bloque
De Wikipedia, la enciclopedia libre.
El principio que se utiliza en los códigos de bloque consiste en estructurar los datos en bloques de longitud fija y añadir a cada bloque un cierto número de bits llamados bits de redundancia.
Sólo ciertas combinaciones de bits son aceptables y forman una colección de palabras de código válidas.
Cuando los datos se transmiten y llegan al receptor hay dos posibilidades:
· Que la palabra que se recibe sea una palabra de código válido
· Que la palabra que se recibe no sea un código válido, en cuyo caso hay dos posibilidades:
·
o El receptor puede recrear el bloque original ( código autocorrector).
·
o El receptor puede pedir que se retransmita el bloque (código de autochequeo).
Distancia Hamming
De Wikipedia, la enciclopedia libre.
La efectividad de los códigos de bloque depende de la diferencia entre una palabra de código válida y otra. Cuanto mayor sea esta diferencia, menor es la posibilidad de que un código válido se transforme en otro código válido por una serie de errores.
A esta diferencia se le llama distancia de Hamming, y se define como el número de bits que tienen que cambiarse para transformar una palabra de código válida en otra palabra de código válida.
Si dos palabras de código difieren en una distancia d, se necesitan d errores para convertir una en la otra.
· Ejemplo: Entre los dos números binarios 01010101 y 0001111 hay una distancia de 4 bits (los bits en que difieren ambos números aparecen en color rojo), es decir, se necesitan cuatro errores para transformar un código en el otro.
Paridad Horizontal Y Vertical
(Redirigido desde Paridad horizontal y vertical)
Algunos códigos de bloque usan una combinación de chequeo de paridad horizontal y vertical (LRC / VRC) para detectar errores.
· LRC: Longitudinal Redundancy Checking
· VRC: Vertical Redundancy Checking
Los caracteres a transmitir se agrupan en bloques. Para el bloque, se calcula el bit de paridad para cada fila y para columna, con lo que el bloque final tendrá una fila y una columna más que el original.
La nueva columna estará formada por los bits de chequeo de paridad horizontal y la nueva fila por los bits de chequeo de paridad vertical.
Adicionalmente, se emplea un bit de paridad cruzada, y que se calcula a partir de la paridad de los bits de paridad vertical y horizontal.
Los chequeos de paridad horizontal y paridad vertical se usan en combinación para detectar los posibles errores que se pueden dar en la transmisión de datos.
Ejemplo: Supongamos que queremos transmitir los caracteres "PAG" en código ASCII (P = 50H; A = 41H; G = 47H).
Colocamos los tres caracteres formando un bloque que consistirá en 3 filas y 8 columnas.
Para cada fila se calcula el bit de chequeo de paridad horizontal (en rojo) y para columna el bit de chequeo de paridad vertical (en verde).
El Bit de paridad cruzada (en azul) sería 0(VRC) + 0(LRC) = 0.
El nuevo bloque a transmitir estará formado por cuatro filas y nueve columnas.
Por tanto, se transmitirían los caracteres 50 41 47 56 (01010110).
La distancia Hamming en este ejemplo es 4: si cambia un bit cambiarían un bit del VRC, un bit del LRC, y el bit de paridad cruzada, es decir cuatro bits en total.
Este código detectaría errores simples, dobles y triples y corregiría los errores simples.
Códigos cíclicos
De Wikipedia, la enciclopedia libre.
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.
Ver también:
· Algoritmo de los Códigos de Redundancia Cíclica
http://es.wikipedia.org/wiki/Teor%EDa_de_la_Informaci%F3n
Teoría de la Información y de la Codificación
Introducción
La Teoría de la Información y de la Codificación es uno de los pilares teóricos sobre los que se construyen las computadoras modernas y los sistemas de transmisión de la información.
Conviene tener en cuenta que una computadora no es más que un sistema de procesamiento de la información, y que antes de poder iniciar ese procesamiento, hay que representar dicha información de alguna manera que la máquina sea capaz de reconocerla y utilizarla.
En el momento actual los elementos con que se construyen las computadoras son dispositivos electrónicos capaces de representar una de dos posibilidades, denominadas de modo arbitrario "1" y "0" (lo que de manera coloquial se denomina tecnología digital), y en consecuencia, es necesaria la existencia de una etapa de traducción entre la representación de la información usada en el mundo real, fácil de entender y manipular por los seres humanos, compuesta por estímulos sonoros, luminosos, olfativos, o de cualquier otro tipo, y la representación adecuada para la computadora, que como ya se ha dicho, consiste únicamente en secuencias de "1" y "0".
Cuando la computadora finaliza el tratamiento de los datos, en la mayoría de las ocasiones será necesario realizar la traducción inversa: desde la secuencia de "1" y "0" usada por la máquina hasta un conjunto de símbolos, colores, sonidos, o estímulos a los que el ser humano (o cualquier otro ente, como puede ser otra máquina) pueda ser sensible.
El problema de la codificación puede aparecer ante el profano como una cuestión "trivial"; nada más lejos de la realidad. Cuando se habla de computadoras como máquinas capaces de tratar automáticamente la información (realmente lo que manipulan son representaciones simbólicas de dicha información), se está haciendo referencia a multitud de posibles procesamientos, entre los que se pueden indicar:
- Adquisición automática de información, lo que implica su traducción o codificación a fin de lograr una representación de dicha información en el "interior" de la computadora.
- Procesamiento automático de la información, que es en principio el objetivo buscado para la construcción de las computadoras.
- Almacenamiento de la información, ya que quizás la información introducida y/o procesada no es requerida en el mismo instante en el que ya se encuentra disponible después de su tratamiento.
- Transferencia automática de la información, permitiendo así la comunicación de dicha información entre distintos sistemas de computación o seres humanos.
- Representación de la información transferida y/o procesada en un formato inteligible o útil para el ser humano u otra máquina.
En esta descripción funcional de una computadora, en todos los puntos aparece la palabra información, y por lo tanto debería existir un paso previo a todo lo indicado anteriormente, en el que se estudiase cuidadosamente todo lo relativo ello. Así, habría que definir lo que se entiende por información, qué propiedades tiene, si es posible medir la cantidad de información... También sería tremendamente interesante poder construir modelos (abstractos en un principio) de sistemas que generen información, y a partir de ellos y mediante las herramientas matemáticas adecuadas, poder deducir propiedades que de alguna manera puedan ser útiles en el mundo real.
Llegado este punto, introducir el concepto de código es inmediato, ya que no es más que el establecimiento de una correspondencia entre la información por representar y el conjunto de símbolos que la representen, idea que coincide con el concepto matemático de correspondencia.
El siguiente paso es unir los conceptos de fuente de información con el de código, con lo que se obtendrá un modelo que proporciona a su salida información ya codificada, es decir, lista para ser transformada y/o transferida por una computadora. En este punto entra en juego un parámetro muy importante en el mundo real: el coste y la eficiencia económica. Así, se pueden indicar las siguientes consideraciones:
- Conviene utilizar códigos que sean eficientes en cuanto al coste de transmisión; para transmitir un mensaje se debería utilizar su representación codificada de la manera más breve, con lo que los gastos en alquiler de equipos de transmisión sean lo más bajos posibles.
- Conviene utilizar códigos que permitan almacenar la información utilizando el menor espacio posible, ahorrándose por lo tanto en equipos como son unidades de disco o cinta.
- También es muy importante la creación de códigos seguros, es decir, que mantengan la información del mensaje original accesible sólo a aquellos usuarios autorizados, mientras que para el resto de los usuarios resulte ininteligible. Este aspecto es tratado por la criptografía.
Como se ha podido observar en los últimos puntos, el estudio de la representación de la información (es decir, los códigos), conlleva una serie de aspectos de elevadísimo interés económico, y cuya aplicación al mundo real es indiscutible.
Otro paso que se va a modelar en la teoría de la información es el hecho de la transmisión de la información entre dos sistemas, el emisor y el receptor. Es bien conocido que durante el transporte las señales que codifican o representan la información pueden sufrir, y de hecho sufren, modificaciones aleatorias que provocan cambios en el mensaje transmitido. Estos errores, tal y como se ha indicado, son de naturaleza aleatoria, y de nuevo las matemáticas permiten establecer modelos para su estudio y, a través de estos modelos, se determinan y descubren las propiedades que les son inherentes. Al modelo que describe las posibles transformaciones en el mensaje codificado durante su transmisión (aunque dichas transformaciones pueden darse también durante el tratamiento o el almacenamiento del mensaje codificado) se le denomina canal de información.
Estudiando los canales de información, al igual que ocurría con las fuentes de información, pueden extraerse una serie de conclusiones muy interesantes y de aplicación inmediatas al mundo real, como son buscar maneras de representar la información (códigos) para ser enviada a través de un sistema de transmisión que posee ruido, de tal manera que la presencia de los errores debidos a ruido afecten lo menos posible al contenido del mensaje enviado. Es decir, se buscan códigos que minimicen el efecto del ruido y permitan reconstruir el mensaje original sin ningún error, a pesar de que el medio de transmisión tenga ruido. http://ponton.dcs.fi.uva.es/web/teoria_informacion/principal.php
PERFIL Y ENTORNO CONCEPTUAL
Wiener en el libro The Human Use of Human Beings escribia "Vivir verdaderamente es vivir con la información adecuada".
En el entorno conceptual , se puede decir que la teoría de la Información tiene por objeto el contenido y la constitución de los mensajes. El pilar básico de la teoría de la Información es proporcionar una medida del contenido de información de un mensaje en términos de su impredictibilidad, que es descrito por los términos de "fuente", "emisor", "canal de comunicación", "receptor", pero que no hace intervenir para nada la naturaleza física que está asignada generalmente a estos vocablos. La teoría de la Información expresa las relaciones que existen entre las configuraciones de los estados de un sistema cualquiera, donde la evolución es aleatoria y el soporte abstracto. Las relaciones son formalmente semejantes a las que se encuentran en la Termodinámica Estadística. Insistiremos que el carácter analógico es solamente formal; sin embargo tiene el mérito de hacer aparecer la teoría de la Información como una disciplina que en materia de comunicaciones juega un papel semejante al de la Energética en el dominio de la Física. En efecto, la Energética es la ciencia de las relaciones generales que preside la evolución de los sistemas físicos. Según [OSWA86], bajo este ángulo sería más coherente llamar "Informática" a la disciplina que lleva el nombre de "Teoría de la Información".
La Teoría de la Información vista un siglo después de la Termodinámica, y aunque las dos disciplinas usan las mismas herramientas matemáticas, la cronología no es más que la separación entre la aparición de las máquinas de vapor y los modernos sistemas de telecomunicación. En efecto las Teorías nacen siempre bajo el influjo de la necesidad, es decir del desarrollo de las ciencias y de la técnica.
El paralelismo entre las dos teorías llega hasta la utilización de la palabra "entropía" para designar a la cantidad de información. Este nombre fue propuesto por el creador de la teoría de la Información, Shanonn , y ha sido adoptado universalmente, habiendo contribuido muy poco a la popularidad de la nueva ciencia debido al carácter de inteligible del término. Desdichadamente también ha contribuido a la difusión de algunas ideas falsas sobre su interpretación y su comprensión. La información no es más que una medida agregada a los estados dicernibles de un sistema y su evolución a lo largo del tiempo: es una magnitud matemática, pero no es una magnitud física caracterizando una propiedad de la materia. La analogía entre la Termodinámica estadística y la teoría de la Información no es más que formal; si ello se traduce por la similitud de muchas de la fórmulas y de los juegos de ecuaciones, nada autoriza a identificar las magnitudes homólogas que se encuentran en las dos disciplinas.
Paradójicamente, si la tentación de una verdadera asimilación no ha sido descartada, la analogía formal no está más lejos que la sugerida del examen de los problemas y que autoriza la escritura matemática para su utilización en teoría de la Información. De todas formas se debería utilizar una terminología propia en Teoría de la Información y no la propia de la Termodinámica. En este sentido [OSWA86] utiliza el término "densidad diacrítica" para denominar a la entropía. El mismo autor sugiere no subestimar la importancia del vocabulario como factor de orden que refleja la claridad de conceptos y que suministra armonía al razonamiento. En este sentido reina una gran anarquía entre los autores de obras sobre la teoría de la Información en lo referente a la definición y nomenclatura de las magnitudes fundamentales.
Aunque la descripción de los códigos correctores de errores no entra dentro de la Teoría de la Información sino de la Codificación, esta relacionada con la misma como vehículo protector de la información las nociones de redundancia y rendimiento no pueden ser presentados sin una vuelta a las propiedades esenciales de los códigos. El problema de la eficacia de los códigos correctores de errores se merece un análisis en profundidad que aclare la Teoría de la distorsión. http://serdis.dis.ulpgc.es/~ii-ti/TI-GUIA-ACADEMICA.html
