En telecomunicaciones , un código Berger es un código de detección de errores unidireccional , que lleva el nombre de su inventor, JM Berger. Los códigos de Berger pueden detectar todos los errores unidireccionales. Los errores unidireccionales son errores que solo convierten unos en ceros o solo unos ceros en unos, como en los canales asimétricos. Los bits de verificación de los códigos de Berger se calculan contando todos los ceros en la palabra de información y expresando ese número en binario natural. Si la palabra de información consta de bits, entonces el código Berger necesita "comprobar bits", dando un código Berger de longitud k + n. (En otras palabras, el Los bits de verificación son suficientes para verificar bits de información). Los códigos de Berger pueden detectar cualquier número de errores de cambio de bit de uno a cero, siempre que no ocurran errores de cero a uno en la misma palabra de código. De manera similar, los códigos de Berger pueden detectar cualquier número de errores de cambio de bit de cero a uno, siempre que no se produzcan errores de cambio de bit de uno a cero en la misma palabra de código. Los códigos de Berger no pueden corregir ningún error.
Como todos los códigos de detección de errores unidireccionales, los códigos de Berger también se pueden usar en circuitos insensibles al retardo .
Detección de errores unidireccionales
Como se indicó anteriormente, los códigos de Berger detectan cualquier número de errores unidireccionales. Para una palabra de código dada , si los únicos errores que han ocurrido son que algunos (o todos) los bits con valor 1 han cambiado al valor 0, entonces esta transformación será detectada por la implementación del código Berger. Para entender por qué, considere que hay tres casos de este tipo:
- Algunos bits de 1 en la parte de información de la palabra de código han cambiado a 0.
- Algunos bits de 1 en la parte de verificación (o redundante ) de la palabra de código han cambiado a 0.
- Algunos bits de unos en las porciones de información y de verificación han cambiado a ceros.
Para el caso 1, el número de bits con valor 0 en la sección de información aumentará, por definición del error. Por lo tanto, nuestro código de verificación Berger será menor que el recuento real de 0 bits para los datos, por lo que la verificación fallará.
Para el caso 2, el número de bits con valor 0 en la sección de información ha permanecido igual, pero el valor de los datos de verificación ha cambiado. Como sabemos que algunos 1 se convirtieron en 0, pero ningún 0 se convirtió en 1 (así es como definimos el modelo de error en este caso), el valor binario codificado de los datos de verificación bajará (por ejemplo, de binario 1011 a 1010, o a 1001 o 0011). Dado que los datos de información se han mantenido igual, tienen el mismo número de ceros que tenían antes, y eso ya no coincidirá con el valor de verificación mutado.
Para el caso 3, donde los bits han cambiado tanto en la sección de información como en la de verificación, observe que el número de ceros en la sección de información ha aumentado , como se describe para el caso 1, y el valor binario almacenado en la parte de verificación ha disminuido . como se describe para el caso 2. Por lo tanto, no hay posibilidad de que los dos terminen mutando de tal manera que se conviertan en una palabra de código válida diferente.
Se puede realizar un análisis similar, y es perfectamente válido, en el caso en que los únicos errores que ocurren son que algunos bits con valor 0 cambian a 1. Por lo tanto, si todos los errores que ocurren en una palabra de código específica ocurren todos en la misma dirección , estos errores serán detectados. Para la siguiente palabra de código que se transmite (por ejemplo), los errores pueden ir en la dirección opuesta y aún se detectarán, siempre que todos vayan en la misma dirección que los demás.
Los errores unidireccionales son comunes en determinadas situaciones. Por ejemplo, en la memoria flash , los bits se pueden programar más fácilmente en un 0 que en un 1.
Referencias
- JM Berger (marzo de 1961). "Una nota sobre un código de detección de errores para canales asimétricos" . Información y control . 4 (1): 68–73. doi : 10.1016 / S0019-9958 (61) 80037-5 .
- Subhasish Mitra y Edward J. McCluskey, " ¿Qué esquema de detección de errores concurrentes elegir? ", Centro de Computación Confiable, Universidad de Stanford, 2000. CiteSeer x : 10.1.1.9.2021
- Tom Verhoeff (marzo de 1988). "Códigos insensibles al retraso: una descripción general] por" (PDF) . Computación distribuida . 3 (1): 1–8. doi : 10.1007 / BF01788562 .