Detecção de erros, parte 2: o codificador de Hamming

Published by MyName in

Este desafio é uma continuação de Detecção de erros, parte 1: o verificador de Hamming . Para relembrar:

  • Cada bit redundante em um bloco de Hamming informa a paridade da quantidade de 1s dentro de sua região: um 0 indica uma quantidade par de 1s, e um 1 indica uma quantidade ímpar de 1s.
  • Os bits redundantes são sempre colocados em potências de dois: índice 1, 2, 4, etc., ou em binário 1, 10, 100, etc.
  • Todos os índices dentro de uma região estão relacionados ao índice do bit redundante dessa região: para o bit redundante na posição 0100 (decimal 4), os índices de sua região são 0101, 0110, 0111, 1100, 1101, 1110 e 1111. Especificamente, todos têm um 1 no terceiro dígito a partir da direita. Esse padrão se aplica a todas as regiões: Índices em binário
  • Um bloco com m bits precisa de n bits redundantes, onde 2^n = m.

Neste desafio, sua tarefa é escrever uma função que receba um bloco de Hamming e preencha todos os bits redundantes com o valor apropriado. Os bits redundantes já estão posicionados, mas todos são 0.

Desta vez, o bit de índice 0 será usado. Esse bit codificará informações sobre todo o bloco, assumindo o valor (0 ou 1) que torne par a quantidade total de 1s. Usar esse bit extra permite que o receptor detecte se ocorreram dois erros, embora não suas posições.

Seu código deve funcionar para blocos de tamanhos diferentes (os tamanhos sempre serão potências de dois).

Exemplos

hamming_coder("0000010100011000") ➞ "0100110100011000"

hamming_coder("0000000001010000") ➞ "1010000001010000"

hamming_coder("00010111010110000111001110001010") ➞ "00110111010110000111001110001010"

hamming_coder("00000110001001000111010100100101") ➞ "10101110101001000111010100100101"

Observações

  • Os bits redundantes sempre têm potências de dois como índices.
  • Cada região divide o bloco em duas partes. Algumas regiões dividem o bloco verticalmente, com colunas que dobram de largura; outras o dividem horizontalmente, com linhas que dobram de altura. Os bits redundantes sempre ficam no canto superior esquerdo de cada região. Aqui há um exemplo de como um bloco de tamanho 32 seria dividido.