Detecção de erros, parte 1: o verificador de Hamming

Quando uma mensagem, expressa como uma longa sequência de 0s e 1s, é enviada para você, um ou mais de seus bits podem ser invertidos durante o trajeto. Nesse caso, pode ser útil ter uma forma de descobrir se ocorreu uma "inversão de bit" e onde, para então invertê-lo de volta. Uma solução é incluir na mensagem algum tipo de metainformação sobre a própria mensagem que possa ajudar você a decidir se ela foi corrompida ou não.

O código de Hamming é um bloco de código que inclui bits redundantes. Esses bits não devem ser considerados parte da mensagem em si, mas são usados para indicar se os bits não redundantes estão corretos ou se algum foi invertido. Como ilustração, considere uma mensagem de 16 bits:

0111
0010
1110
0100

Neste bloco, 4 bits são redundantes e 11 carregam a mensagem (o bit na posição 0 não será usado neste desafio). Os bits redundantes sempre têm potências de dois como índices, por isso ocupam as posições 1, 2, 4 e 8 aqui. A forma como eles codificam informações sobre a mensagem é:

• Cada bit redundante é responsável por verificar uma determinada região do código.
• Os 1s dentro de cada região são contados. Se o número de 1s for ímpar, o bit redundante daquela região será 1 para tornar a contagem par. Se ela já for par, o bit redundante será 0.
• Cada região divide o bloco da seguinte maneira:

Os retângulos vermelhos representam uma região, e o bit redundante responsável por ela aparece sublinhado em cada uma. Este bloco provavelmente não está corrompido, pois o número de 1s é par em todas as regiões.

Sua tarefa é escrever uma função que receba um bloco de Hamming e verifique se há bits corrompidos. Se o método de Hamming não encontrar bits corrompidos, retorne o mesmo bloco fornecido como entrada. Se um bit corrompido for encontrado, retorne o código corrigido. Para este desafio, não haverá mais de um erro por bloco.

Dica: os blocos de Hamming são projetados de modo que o (número de 1s) mod 2 de todas as regiões "revele" o índice invertido do bit corrompido em binário. Por exemplo:

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

Em geral, pense em todos os índices em binário e talvez encontre alguns padrões interessantes.

Exemplos

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.

Observações

• Todos os blocos terão tamanho 16.
• Haverá no máximo uma inversão de bit por bloco.
• Para ver uma explicação visual deste desafio e uma possível solução, confira os vídeos na aba Resource.
• Para saber mais, confira a parte 2.