6.2 Error-Detection and -Correction Techniques Flashcards
En qué consiste la detención de errores?
El desafío del receptor es determinar si D es igual a D’, dado que recibió D’ y EDC’.
Aunque se utilicen técnicas de detección de errores puede que queden errores sin detectar, sucede que en general las técnicas más sofisticadas introducen mucho
overhead.
Parity Checks
Es la forma más simple. Suponiendo que la data que se va a enviar, D, tiene d bits.
En un esquema par, el enviador incluye un bit adicional donde elige el valor tal que el número total de 1s en los d+1 bits sea par. En un esquema impar, se elegirá tal que d+1 sea impar.
El receptor tiene que contar la cantidad de 1s recibidos en los d+1 bits, si encuentra un número impar (estando en el esquema par), entonces va a saber que hay un número impar de bits erroneos. Qué pasa si encuentra un número par? no es garantía de nada, podría pasar que sea un caso donde haya errores no detectados y en esta técnica la probabilidad de ocurran errores es muy alta, asi que no es la mejor.
Suponiendo que hay un error en los d bits originales, siguiendo esta técnica, el receptor puede identificar cuál es el bit que está mal y así corregirlo. Esta habilidad del receptor de poder detectar y corregir un error se llama forward error correction (FEC). Esta técnica se utiliza mucho en dispositivos de audio.
Checksumming methods
Los d bits de datos, se toman como una secuencia de k-bits enteros. Un método simple de checksumming es el de sumar esos k-bits y usar el resultado como el bit de detección de error. El receptor verifica ese checksum calculando el complemento a 1 de la suma de lo que recibió (incluyendo el checksum) y viendo si el resultado son todos bits de 1. Si hay algún 0, es porque hay un error. Por qué se utilizan checksums tanto en la capa de transporte como en la de enlace? porque los checksums de la capa de transporte están implementados en software, en cambio en la capa de enlace se implementan en hardware que rápidamente pueden resolver operaciones más complejas como CRC (cyclic redundancy checks).
0x0A + 0x2B + 0x3C = 0x77
Complemento a uno de 0x77 = 0x88
Por ejemplo, si tenemos 8 bits y la suma de verificación es 01010101, entonces el complemento a uno sería 10101010. Si la suma de verificación y los datos son correctos, entonces deberíamos obtener una suma total de 11111111, que es el complemento a uno de todos los bits en 0.
- Cyclic redundancy checks (CRC)
También conocidos como polynomial codes porque se puede pensar en el string de bits como un polinomio con coeficientes 0 y 1. La idea es la siguiente: el enviador y el receptor tienen que ponerse de acuerdo en un patrón de r+1 bits, G, llamado generator. El bit más significante de G tiene que ser 1. Para una data D, el enviador va a elegir r bits adicionales que va a concatenar a D tal que el patrón resultante d+r sea exactamente divisible por G usando aritmética de módulo 2.
El receptor va a dividir los d+r bits recibidos por G. Si el resto no es cero, entonces el receptor va a saber que hay un error, sino considerará que la información es correcta.
