Código Berger

En telecomunicaciones , un código Berger es un código unidireccional de detección de errores . Recibe su nombre de J.M. Berger, su inventor.

Los códigos Berger pueden detectar todos los errores unidireccionales. Los errores unidireccionales son errores que solo convierten unos en ceros o solo ceros en unos, como en los canales asimétricos. Los bits de verificación de los códigos 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${\displaystyle n}$bits, entonces el código Berger necesita${\displaystyle k=\lceil \log _ {2}(n+1)\rceil}$"bits de verificación", dando un código Berger de longitud k+n. (En otras palabras, el${\displaystyle k}$Los bits de control son suficientes para comprobar hasta${\displaystyle n=2^{k}-1}$bits de información). Los códigos Berger pueden detectar cualquier número de errores de inversión de bits de uno a cero, siempre que no se produzcan errores de inversión de bits de cero a uno en la misma palabra de código. De manera similar, los códigos Berger pueden detectar cualquier número de errores de inversión de bits de cero a uno, siempre que no se produzcan errores de inversión de bits de uno a cero en la misma palabra de código. Los códigos Berger no pueden corregir ningún error.

Al igual que todos los códigos de detección de errores unidireccionales, los códigos de Berger también se pueden utilizar en circuitos insensibles al retardo .

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 a valor 0, entonces esta transformación será detectada por la implementación del código de Berger. Para entender por qué, consideremos que existen tres casos de este tipo:

1. Algunos bits 1 en la parte de información de la palabra clave han cambiado a 0.
2. Algunos bits de 1 en la parte de verificación (o redundante ) de la palabra clave han cambiado a 0.
3. Algunos bits que eran 1 tanto en la sección de información como en la de verificación han cambiado a 0.

En el caso 1, el número de bits con valor cero en la sección de información aumentará, por definición del error. Por lo tanto, nuestro código de verificación de Berger será inferior al número real de bits cero en los datos, y la verificación fallará.

En el caso 2, la cantidad de bits con valor 0 en la sección de información se ha mantenido igual, pero el valor de los datos de verificación ha cambiado. Dado que sabemos que algunos 1 se convirtieron en 0, pero ningún 0 se convirtió en 1 (así definimos el modelo de error en este caso), el valor binario codificado de los datos de verificación disminuirá (por ejemplo, de binario 1011 a 1010, o a 1001, o 0011). Como los datos de información se han mantenido iguales, tienen la misma cantidad de ceros que antes, y eso ya no coincidirá con el valor de verificación modificado.

En 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 describió para el caso 1, y el valor binario almacenado en la sección de verificación ha disminuido , como se describió para el caso 2. Por lo tanto, no hay posibilidad de que ambos terminen mutando de tal manera que se conviertan en una palabra clave válida diferente.

Se puede realizar un análisis similar, perfectamente válido, en el caso de que los únicos errores sean el cambio de bits con valor 0 a 1. Por lo tanto, si todos los errores que se producen en una palabra clave específica ocurren en la misma dirección, se detectarán. Para la siguiente palabra clave que se transmita (por ejemplo), los errores pueden ir en la dirección opuesta y aun así se detectarán, siempre que todos vayan en la misma dirección.

Los errores unidireccionales son comunes en ciertas situaciones. Por ejemplo, en la memoria flash , es más fácil programar bits a 0 que restablecerlos a 1.

• JM Berger (marzo de 1961). "Una nota sobre un código de detección de errores para canales asimétricos" . Information and 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 concurrente elegir? ", Centro de Computación Confiable, Universidad de Stanford, 2000.
• Tom Verhoeff (marzo de 1988). "Códigos insensibles al retardo: una visión general " ( PDF) . Computación distribuida . 3 (1): 1–8 . doi : 10.1007/BF01788562 . S2CID 8568354 .