Introdução
Trilhões e trilhões de mensagens cruzam o espaço entre a Terra e as galáxias vizinhas a cada milissegundo.
Mas transmitir por distâncias tão longas é complicado.
Explosões solares incômodas, distorções temporais, forças errantes e até o bater das asas de uma borboleta espacial podem fazer um bit aleatório mudar durante a transmissão.
Agora imagine as consequências:
- Derrubar o Mercado de Ações Intergaláctico quando "buy low" vira "sell now".
- Perder contato com o sistema Kepler Whirl quando "save new worm hole" se transforma em "cave new worm hole".
- Ou mergulhar o universo em um horror existencial trocando um emoji de cowboy 🤠 por um emoji de palhaço 🤡.
Detectar mensagens corrompidas não é só importante: é essencial.
O receptor precisa saber quando algo deu errado antes que o desastre aconteça.
Mas como?
Cientistas e engenheiros de todo o universo vêm enfrentando esse problema há eras.
Superaglomerados cósmicos inteiros de IA processam os dados sem parar.
E então, um dia, uma lenda ressurge: um método antigo e poderoso, sussurrado em fóruns de depuração, murmurado por engenheiros que já viram demais...
O Bit de Paridade!
Um método tão simples, tão poderoso, que pode muito bem salvar a comunicação interestelar.
Instruções
Sua tarefa é ajudar a implementar
- o transmissor, que calcula a sequência de transmissão, e
- o receptor, que a decodifica.
Um bit de paridade é uma forma simples de detectar erros de transmissão.
O transmissor e o receptor só conseguem transmitir e receber exatamente oito bits por vez (incluindo o bit de paridade).
O bit de paridade é definido de modo que haja um número par de bits 1 em cada transmissão, e o bit de paridade é sempre o primeiro bit da direita.
Então, se o receptor recebe 11000001, 01110101 ou 01000000 (ou seja, uma transmissão com um número ímpar de bits 1), ele sabe que há um erro.
No entanto, mensagens raramente são tão curtas e, quando são mais longas, precisam ser transmitidas em uma sequência.
Por exemplo, considere a mensagem 11000000 00000001 11000000 11011110 (ou C0 01 C0 DE em hexadecimal).
Como cada transmissão contém exatamente oito bits, ela só pode conter sete bits de dados e o bit de paridade.
Um bit de paridade deve então ser inserido após cada sete bits de dados:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
A sequência de transmissão dessa mensagem fica assim:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Os dados da primeira transmissão da sequência (1100000) têm dois bits 1 (um número par), então o bit de paridade é 0.
A primeira transmissão passa a ser 11000000 (ou C0 em hexadecimal).
Os dados da próxima transmissão (0000000) têm zero bits 1 (um número par de novo), então o bit de paridade é 0 outra vez.
A segunda transmissão fica então 00000000 (ou 00 em hexadecimal).
Os dados das duas transmissões seguintes (0111000 e 0001101) têm três bits 1.
Seus bits de paridade são definidos como 1 para que elas tenham um número par de bits 1 na transmissão.
Elas são transmitidas como 01110001 e 00011011 (ou 71 e 1B em hexadecimal).
A última transmissão (1110) tem apenas quatro bits de dados.
Como exatamente oito bits são transmitidos por vez e o bit de paridade é o bit mais à direita, três bits 0 e depois o bit de paridade são adicionados para completar oito bits.
Agora ela fica assim (em que _ é o bit de paridade):
1110 000_
↑↑↑ (added 0 bits)
Há um número ímpar de bits 1 de novo, então o bit de paridade é 1.
A última transmissão da sequência passa a ser 11100001 (ou E1 em hexadecimal).
A sequência de transmissão completa dessa mensagem é 11000000 00000000 01110001 00011011 11100001 (ou C0 00 71 1B E1 em hexadecimal).
