Detección y correcion de errores - norman-ipn/Errores GitHub Wiki

Detección y corrección de errores

• La verificación respecto a si una palabra ampliada pertenece o no al código se realiza comprobando las paridades parciales y la paridad global de la palabra completa; si la palabra es correcta (si no hay errores detectables), las nuevas paridades deben ser, todas ellas, nulas pues corresponden a conjuntos de bits ampliados con su propia paridad. • La comprobación de la paridad global se calcula sobre todos los bits de la palabra ampliada y su resultado puede ser:

• comprobación de la paridad global = 0 y, en tal caso, o no existe error, o éste afecta a un número par de dígitos y no se puede hacer corrección de error sobre la palabra recibida
• comprobación de la paridad global = 1 y, en tal caso, existe error y, además, afecta a un número impar de dígitos; en principio, puede suponerse que afecta a un solo bit (pues, salvo sistemas de transmisión o almacenamiento muy defectuosos, es mucho más probable que haya error en un bit que en tres o más de ellos) y, consiguientemente, es viable realizar la corrección de dicho error. • Cada comprobación de paridad parcial se calcula sobre los bits cuyo |número| contiene un «uno» en la misma posición; es decir, se toman todos los bits señalados con el mismo grafismo y se halla la paridad del conjunto de ellos.
  La nueva paridad parcial CP1 es la de todos los bits cuyo |número| acaba por «uno», es decir, aquellos cuyo grafismo es &: b11 b10 b8 b6 b4 b3 b1 b0 P1. La comprobación de paridad parcial CP2 es la de los bits cuyo |número| tiene un «uno» en penúltima posición, es decir su grafismo es #: b10 b9 b6 b5 b3 b2 b0P2. La comprobación CP3 corresponde a un «uno» en antepenúltima posición, o sea al grafismo ∆:
  b10 b9 b8 b7 b3 b2 b1 P3; CP4 se refiere al grafismo *: b10 b9 b8 b7 b6 b5 b4 P4 y CP5 a @: b11 P5. • En caso de que la palabra pertenezca al código Hamming todas las comprobaciones de paridad darán resultado 0, tanto las parciales como la global. Tal cosa sucederá cuando no haya habido error en la transferencia de la palabra; nunca podremos estar absolutamente seguros de la ausencia de error, pero si todas las comprobaciones de paridad son nulas, sabemos que, de haber error hay cuatro o más errores (y siempre en número par), lo cual es altamente improbable. • La comprobación de paridades parciales da lugar a un número binario
  …CP5 CP4 CP3 CP2 CP1, con las siguientes posibilidades:
• si dicho número es nulo y la paridad global también lo es, estamos en el caso anterior y, en principio, aceptaremos (con muy alta probabilidad) la ausencia de error;
• si este número no es nulo y la paridad global es 0, hay error y afecta a un número par de dígitos, por lo cual no podemos corregirlo;
• si tal número no es nulo y la paridad global es 1, es razonable suponer que el error afecta a un solo bit y es posible corregirlo: el número …CP5 CP4 CP3 CP2 CP1 señala al dígito erróneo.

deteccion

Se debe corregir el bit cuyo |número| es 0 1 0 0 1, según indica el número que forman las paridades parciales. Código Hamming correcto: 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 Palabra inicial: 1 0 0 1 0 1 1 1 0 1 0 0 La palabra inicial se obtiene a partir de la palabra ampliada, eliminando en ella las paridades, tanto las parciales como la global. [Compruébese que es correcta, es decir, que coincide con la palabra inicial del apartado 6.3.1.] 154 Electrónica Digital Cuando el número …CP5 CP4 CP3 CP2 CP1 no es nulo y la paridad global es 1, sabemos que hay error y que afecta a un número impar de dígitos; podemos suponer que el error afecta a un solo bit y, en tal caso, el número …CP5 CP4 CP3 CP2 CP1 señala al dígito erróneo:

• CP1 = 1 significa que el error se encuentra entre los bits que corresponden a la paridad
  P1 (es decir, entre aquellos cuyo |número| acaba por «uno», grafismo &),
• CP2 = 1 significa que el error se encuentra entre los bits que corresponden a la paridad
  P2 (es decir, su |número| tiene un «uno» en penúltima posición, grafismo #)
• y así sucesivamente …;
  de manera que el número binario que forman …CP5 CP4 CP3 CP2 CP1 corresponde precisamente al |número| del bit erróneo. La siguiente tabla indica el número de bits de paridad necesarios en el código de Hamming de distancia mínima 4 según el número de bits de la palabra inicial:

deteccion2

Una palabra inicial de 4 dígitos duplica su longitud al pasar a código Hamming de distancia mínima 4, si es de 1 byte requiere 5 dígitos adicionales de paridad (pasa a 13 bits, un aumento del 65 %) y para palabras de 16 bits es preciso añadir otros 6 (40%). En cambio, una palabra inicial de 32 bits aumenta solamente en 7 más (22%) y una de 120 bits se amplía a 128 (un 7%). Con este mismo tipo de idea conceptual (la de introducir adecuadamente paridades parciales) pueden construirse códigos más complejos de distancia mínima superior. La detección y corrección de errores, es decir, la fiabilidad de la información es un tema de interés cada vez mayor y constituye una rama especializada dentro del amplio campo de la codificación de la información. 6. Codificación binaria 155 Consideremos otro ejemplo, relativo a una palabra inicial de 10 dígitos: Sea una palabra binaria inicial de 10 bits: 1 1 0 0 1 1 1 0 0 0

que en código de Hamming de distancia mínima 4 será: 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0

(los dígitos subrayados corresponden a los bits de paridad).

a) si en la palabra inicial se modifica el bit b5: 1 1 0 0 0 1 1 0 0 0

su correspondiente palabra codificada será: 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1

que dista 4 bits de la anterior. b) si en la palabra inicial se modifican los bits b5 y b6: 1 1 0 1 0 1 1 0 0 0

su correspondiente será: 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1

que dista 4 bits de la primera y otros 4 bits de la anterior. c) si en la palabra inicial se modifican los bits b5 , b6 y b7: 1 1 1 1 0 1 1 0 0 0

su correspondiente palabra codificada será: 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0

que dista 4 bits de la palabras anterior y 6 bits de las dos primeras. d) si en la transmisión de la primera palabra ampliada se invierte un solo bit, el que hace el número de orden sexto: 1 1 0 0 0 1 1 1 1 0 1 0 0 1 1

la palabra recibida corresponde a una palabra errónea, es decir, que no coincide con la primera palabra inicial: 1 1 0 0 0 1 1 1 0 0

pero la comprobación de la paridad global da 1 (error en número impar de bits) y el número correspondiente a las comprobaciones de paridades parciales valdrá 0110, lo cual indica error en el bit cuyo número de orden es 6. e) invirtiendo dicho bit 6 se recupera la palabra correcta: 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1

y su correspondiente palabra inicial: 1 1 0 0 0 1 1 0 0 0

f) si en la transmisión de la primera palabra se invierten los bits que hacen los números de orden sexto y séptimo: 1 1 0 0 0 1 1 0 1 0 1 0 0 1 1

el número correspondiente a las comprobaciones de paridades parciales valdrá 0001, lo cual indica error en el bit cuyo número de orden es 1 corrigiéndolo se generaría la palabra: 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1

que es errónea pues corresponde a la palabra inicial: 1 1 0 0 0 1 0 1 0 0

distinta de la primera. Ello es debido a que el error afectaba a dos bits: la comprobación de la paridad global da 0 (error en número par de bits).