• Author / Uploaded
• Manuel Castañeda Mayora

Citation preview

FEC (Corrección de error en sentido directo). Es el único esquema de corrección de errores que realmente detecta y corrige errores de transmisión en la recepción, sin pedir retransmisión. En FEC, un receptor puede usar un código de corrección de errores, la cual automáticamente corrige ciertos errores. En teoría, es posible corregir cualquier error automáticamente. Los códigos de corrección de errores, sin embargo, son más sofisticados que los códigos de detección de errores y requieren más bits de redundancia. Como bien sabemos, los errores de un solo bit pueden ser detectados por la adición de un bit de redundancia (paridad). Un bit adicional puede detectar errores de un solo bit en cualquier secuencia de bits porque debe distinguirse solamente entre dos condiciones: error o no error. Un bit tiene dos estados (0 y 1). Esos dos estados son suficientes para estos niveles de detección. Pero si queremos corregir así como detectar error de un solo bit, Dos estados son suficientes para detectar un error pero no para corregirlo. Un error ocurre cuando el receptor lee un bit 1 como un 0 y viceversa. Para corregir el error, el receptor simplemente restaura el valor del bit alterado. Para hacer eso, se debe conocer que bit esta erróneo. El secreto de la corrección de errores, es localizar el bit o bits invalidos. Por ejemplo, para corregir un solo bit de error en un carácter ASCII, el código de corrección de errores debe determinar cuál de los 7 bits ha cambiado. En este caso, tenemos que distinguir entre ocho diferentes estados, no error, error en posición 1, error en posición 2, y así continuamente, hasta la posición 7. Para realizar esto se requiere suficiente redundancia de bits para mostrar todos los 8 estados. En primera instancia, parece ser que un código de 3 bits de redundancia deben ser adecuados porque 3 bits pueden mostrar 8 diferentes estados (000 a 111) y pueden por lo tanto indicar la localización de ocho diferentes posibilidades. Pero, ¿Qué pasaría si un error ocurre en los bits de redundancia? Siete bits de datos (el carácter ASCII) mas tres bits de redundancia es igual a 10 bits. Tres bits, sin embargo, pueden identificar solamente 8 posibilidades. Bits adicionales son necesarios para cubrir toda la posible localización de errores. Para calcular el número de bits de redundancia r requeridos para corregir un dado numero de bits de datos m debemos encontrar una relación entre m y r. Con m bits de datos y r bits de redundancia agregados a ellos, la longitud de un código resultante es m + r. Si el número total de bits en una unidad transmitirle es m + r, entonces r debe ser capaz de indicar al menos m + r + 1 estados diferentes. Uno estado significa que no hay error, y m + r estados indican la localización de un error en cada uno de los m + r posiciones. Así que los estados m + r + 1 deben ser descubiertos por r bits; y r bits pueden indicar 2r estados diferentes. Por lo tanto, 2r debe ser igual a o mayor que m + r + 1: 2r >=m + r + 1 Código Hamming Consiste en introducir más de un bit de paridad por cada palabra, de forma que, si el número de bits de paridad es el adecuado, se puede detectar en que digito se ha producido el error (y por tanto, corregirlo). A diferencia de los códigos de paridad simple, donde el digito de paridad se genera a partir de todos los de información, en este caso cada bit de paridad se genera a partir

de un grupo de dígitos de información (no de todos ellos), incluyéndose a el mismo. Dadas dos palabras código cualesquiera, digamos 10001001 y 10110001, es posible determinar cuántos bits correspondientes difieren, en este caso difieren 3 bits. Para determinar la cantidad de bits diferentes basta aplicar una operación OR exclusivo a las dos palabras código y contar la cantidad de bits 1 en el resultado. La cantidad de posiciones de bit en la que difieren dos palabras código se llama distancia Hamming, su significado es que, si dos palabras código están separadas una distancia Hamming d, se requerirá d errores de un bit para convertir una en la otra. Los bits de corrección de errores son conocidos como bits Hamming, el número que se requiere para ser agregados al carácter es determinado por la expresión: 2n >=m + n + 1 Donde m es igual al número de bits en el dato, y n es el número de bits haming. Típicamente, los bits Hamming son agregados en posiciones de potencia de 2, el 1ro, 2do, 4to, 8vo, 16vo, y así sucesivamente, comenzando de derecha a izquierda. Los Bits Hamming deben ser insertados en el 1ro, 2do, 4to, y 8vo bit. 1 1 9 8 7 6 5 4 3 2 1 1 0 H H H H D D D D D D D 8 4 2 1 En el código Hamming, cada H bit es el bit de paridad para una combinación de bits de datos: H1: bits 1, 3, 5, 7, 9, 11 H2: bits 2, 4, 6, 7, 10, 11 H4 bits 4, 5, 6, 7 H8 bits 8, 9, 10, 11 Ejemplo: El carácter es 011001 Los bits Hamming son HHHH (4) = 24 >= 6 + 4 + 1 1 9 8 7 6 5 4 3 2 1 0 0 1 H 1 0 0 H 1 H H La posición debe ser representada como un valor binario donde haya un 1 representado. Cada valor de la posición es XOR con la otra. El resultado es el código Hamming, ejemplo: Posici Código ón 9 1001 7 0111 3 0011 XOR 1101 (Código Hamming) Así que el código Haming será 1101 y el mensaje transmitido será 0111001101 10 9 8 7 6 5 4 3 2 1 0 1 1 1 0 0 1 1 0 1

Para identificar donde hay un error simplemente se debe aplicar XOR a las posiciones de los datos reales con valor ‘1’ conjuntamente con el código Hamming. Supongamos que ocurre un error en el bit 4 Posici Código ón 9 1001 7 0111 4 0100 3 0011 XOR 0100 (4 Binario) Con este resultado, indica en qué posición se encuentra el bit erróneo