Detección de errores, parte 1: el comprobador de Hamming

Cuando te envían un mensaje expresado como una larga secuencia de 0s y 1s, uno o más de sus bits podrían invertirse durante el trayecto. En ese caso, puede ser útil contar con una forma de determinar si ocurrió un "cambio de bit" y dónde, para invertirlo de nuevo. Una solución consiste en incluir en el mensaje algún tipo de metainformación sobre el propio mensaje que pueda ayudarte a decidir si está corrupto o no.

Código de Hamming es un bloque de código que incluye bits redundantes. Estos bits no deben considerarse parte del mensaje en sí, sino que se utilizan para indicar si los bits no redundantes están bien o si alguno se ha invertido. Como ilustración, considera un mensaje de 16 bits:

0111
0010
1110
0100

En este bloque, 4 bits son redundantes y 11 transportan el mensaje (el bit en la posición 0 no se utilizará en este desafío). Los bits redundantes siempre tienen potencias de dos como índices, por lo que aquí ocupan las posiciones 1, 2, 4 y 8. La forma en que codifican información sobre el mensaje es:

• Cada bit redundante se encarga de comprobar una región determinada del código.
• Se cuentan los 1s dentro de cada región. Si el número de 1s es impar, el bit redundante de esa región es 1 para que el total sea par. Si ya es par, el bit redundante es 0.
• Cada región divide el bloque de la siguiente manera:

Los rectángulos rojos representan una región, y el bit redundante encargado de ella aparece subrayado en cada una. Este bloque probablemente no está corrupto, ya que el número de 1s es par en todas las regiones.

Tu tarea es escribir una función que tome un bloque de Hamming y compruebe si hay bits corruptos. Si el método de Hamming no encuentra bits corruptos, devuelve el mismo bloque que recibió como entrada. Si encuentra un bit corrupto, devuelve el código corregido. Para este desafío, no habrá más de un error por bloque.

Pista: los bloques de Hamming están diseñados de modo que el (número de 1s) mod 2 de todas las regiones "indique" el índice invertido del bit corrupto en binario. Por ejemplo:

0110    region 1: 3 mod 2 = 1    corrupted bit: index 0011 (decimal 3)
0010    region 2: 3 mod 2 = 1
1110    region 3: 2 mod 2 = 0
0100    region 4: 4 mod 2 = 0

En general, piensa en todos los índices en binario y quizá encuentres algunos patrones interesantes.

Ejemplos

hamming_checker("0100100100010010") ➞ "0100100000010010"
# The corrupted bit is in position 7.

hamming_checker("0011011010100110") ➞ "0010011010100110"
# The corrupted bit is in position 3.

hamming_checker("0010101011111111")  ➞ "0010101011111111"
# There are no corrupted bits.

Notas

• Todos los bloques tendrán un tamaño de 16.
• Habrá como máximo un cambio de bit por bloque.
• Para ver una explicación visual de este desafío y una posible solución, consulta los videos de la pestaña Resource.
• Para obtener más información, consulta la parte 2.