Códigos de detección y corrección de errores
Sabemos que los bits 0 y 1 corresponden a dos rangos diferentes de voltajes analógicos. Por lo tanto, durante la transmisión de datos binarios de un sistema a otro, el ruido también puede agregarse. Debido a esto, puede haber errores en los datos recibidos en otro sistema.
Eso significa que un bit 0 puede cambiar a 1 o un bit 1 puede cambiar a 0. No podemos evitar la interferencia del ruido. Pero, primero podemos recuperar los datos originales detectando si hay algún error y luego corrigiéndolos. Para ello, podemos utilizar los siguientes códigos.
- Códigos de detección de errores
- Códigos de corrección de errores
Error detection codes- se utilizan para detectar los errores presentes en los datos recibidos (flujo de bits). Estos códigos contienen algunos bits, que se incluyen (se añaden) al flujo de bits original. Estos códigos detectan el error, si se produce durante la transmisión de los datos originales (flujo de bits).Example - Código de paridad, código de Hamming.
Error correction codes- se utilizan para corregir los errores presentes en los datos recibidos (flujo de bits) de modo que obtengamos los datos originales. Los códigos de corrección de errores también utilizan la estrategia similar de los códigos de detección de errores.Example - Código Hamming.
Por lo tanto, para detectar y corregir los errores, se añaden bit (s) adicionales a los bits de datos en el momento de la transmisión.
Código de paridad
Es fácil incluir (añadir) un bit de paridad a la izquierda de MSB o a la derecha de LSB del flujo de bits original. Hay dos tipos de códigos de paridad, a saber, código de paridad par y código de paridad impar según el tipo de paridad que se elija.
Código de paridad uniforme
El valor del bit de paridad par debe ser cero, si hay un número par de unos presentes en el código binario. De lo contrario, debería ser uno. Así que, incluso el número de los presentes eneven parity code. Incluso el código de paridad contiene los bits de datos e incluso el bit de paridad.
La siguiente tabla muestra la even parity codescorrespondiente a cada código binario de 3 bits. Aquí, el bit de paridad par se incluye a la derecha del LSB del código binario.
| Código binario | Incluso un poco de paridad | Código de paridad uniforme |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Aquí, el número de bits presentes en los códigos de paridad par es 4. Entonces, el número par posible de unos en estos códigos de paridad par es 0, 2 y 4.
Si el otro sistema recibe uno de estos códigos de paridad par, entonces no hay error en los datos recibidos. Los bits distintos del bit de paridad par son los mismos que los del código binario.
Si el otro sistema recibe códigos distintos a los de paridad par, habrá un error (s) en los datos recibidos. En este caso, no podemos predecir el código binario original porque no conocemos las posiciones de los bits del error.
Por lo tanto, el bit de paridad par es útil solo para la detección de errores en el código de paridad recibido. Pero no es suficiente para corregir el error.
Código de paridad impar
El valor del bit de paridad impar debe ser cero, si hay un número impar de unos presentes en el código binario. De lo contrario, debería ser uno. De modo que, un número impar de los presentes enodd parity code. El código de paridad impar contiene los bits de datos y el bit de paridad impar.
La siguiente tabla muestra la odd parity codescorrespondiente a cada código binario de 3 bits. Aquí, el bit de paridad impar se incluye a la derecha del LSB del código binario.
| Código binario | Bit de paridad impar | Código de paridad impar |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Aquí, el número de bits presentes en los códigos de paridad impares es 4. Entonces, el posible número impar de unos en estos códigos de paridad impares es 1 y 3.
Si el otro sistema recibe uno de estos códigos de paridad impares, entonces no hay error en los datos recibidos. Los bits distintos del bit de paridad impar son los mismos que los del código binario.
Si el otro sistema recibe códigos de paridad distintos de los impares, entonces hay un error (s) en los datos recibidos. En este caso, no podemos predecir el código binario original porque no conocemos las posiciones de los bits del error.
Por lo tanto, el bit de paridad impar es útil solo para la detección de errores en el código de paridad recibido. Pero no es suficiente para corregir el error.
Código Hamming
El código Hamming es útil tanto para la detección como para la corrección de errores presentes en los datos recibidos. Este código usa múltiples bits de paridad y tenemos que colocar estos bits de paridad en las posiciones de potencias de 2.
los minimum value of 'k' para lo cual la siguiente relación es correcta (válida) no es más que el número requerido de bits de paridad.
$$ 2 ^ k \ geq n + k + 1 $$
Dónde,
'n' es el número de bits en el código binario (información)
'k' es el número de bits de paridad
Por lo tanto, el número de bits en el código de Hamming es igual an + k.
Deja el Hamming codees $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & bits de paridad $ p_ {k}, p_ {k-1}, .... p_ {1} $. Podemos colocar los bits de paridad 'k' en potencias de 2 posiciones solamente. En las posiciones de bit restantes, podemos colocar los 'n' bits de código binario.
Según los requisitos, podemos usar paridad par o paridad impar al formar un código de Hamming. Pero, se debe utilizar la misma técnica de paridad para encontrar si existe algún error en los datos recibidos.
Siga este procedimiento para encontrar parity bits.
Encuentra el valor de p1, basado en el número de unos presentes en las posiciones de bit b 3 , b 5 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 0 .
Encuentra el valor de p2, basado en el número de unos presentes en las posiciones de bit b 3 , b 6 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 1 .
Encuentra el valor de p3, basado en el número de unos presentes en las posiciones de bit b 5 , b 6 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 2 .
De manera similar, encuentre otros valores de bits de paridad.
Siga este procedimiento para encontrar check bits.
Encuentre el valor de c 1 , basado en el número de unidades presentes en las posiciones de bit b 1 , b 3 , b 5 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 0 .
Encuentre el valor de c 2 , basado en el número de unidades presentes en las posiciones de bit b 2 , b 3 , b 6 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 1 .
Encuentre el valor de c 3 , basado en el número de unidades presentes en las posiciones de bit b 4 , b 5 , b 6 , b 7 y así sucesivamente. Todas estas posiciones de bit (sufijos) en su binario equivalente tienen '1' en el valor posicional de 2 2 .
De manera similar, encuentre otros valores de bits de control.
El equivalente decimal de los bits de verificación en los datos recibidos da el valor de la posición del bit, donde el error está presente. Simplemente complemente el valor presente en esa posición de bit. Por lo tanto, obtendremos el código binario original después de eliminar los bits de paridad.
Ejemplo 1
Encontremos el código de Hamming para el código binario, d 4 d 3 d 2 d 1 = 1000. Considere los bits de paridad pares.
El número de bits en el código binario dado es n = 4.
Podemos encontrar el número requerido de bits de paridad usando la siguiente relación matemática.
$$ 2 ^ k \ geq n + k + 1 $$
Sustituya, n = 4 en la relación matemática anterior.
$$ \ Flecha derecha 2 ^ k \ geq 4 + k + 1 $$
$$ \ Flecha derecha 2 ^ k \ geq 5 + k $$
El valor mínimo de k que satisface la relación anterior es 3. Por lo tanto, requerimos 3 bits de paridad p 1 , p 2 y p 3 . Por lo tanto, el número de bits en el código Hamming será 7, ya que hay 4 bits en el código binario y 3 bits de paridad. Tenemos que colocar los bits de paridad y los bits de código binario en el código Hamming como se muestra a continuación.
los 7-bit Hamming code es $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
Sustituyendo los bits del código binario, el código de Hamming será $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Ahora, busquemos los bits de paridad.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Sustituyendo estos bits de paridad, el Hamming code será $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Ejemplo 2
En el ejemplo anterior, obtuvimos el código de Hamming como $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Ahora, busquemos la posición del error cuando el código recibido es $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Ahora, busquemos los bits de control.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
El valor decimal de los bits de verificación da la posición del error en el código Hamming recibido.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Por lo tanto, el error está presente en el tercer bit (b 3 ) del código Hamming. Simplemente complemente el valor presente en ese bit y elimine los bits de paridad para obtener el código binario original.