Introdução
Biliões e biliões de mensagens cruzam-se entre a Terra e as galáxias vizinhas a cada milissegundo.
Mas transmitir a distâncias tão grandes é complicado.
Erupções solares maçadoras, distorções temporais, forças desgarradas e até o bater de asas de uma borboleta espacial podem fazer com que um bit aleatório mude durante a transmissão.
Agora imagina as consequências:
- Fazer colapsar o Mercado de Ações Intergaláctico quando "buy low" se transforma em "sell now".
- Perder o contacto com o sistema Kepler Whirl quando "save new worm hole" passa a "cave new worm hole".
- Ou mergulhar o universo num horror existencial ao trocar um emoji de cowboy 🤠 por um emoji de palhaço 🤡.
Detetar mensagens corrompidas não é apenas importante: é crucial.
O recetor tem de saber quando algo correu mal, antes que o desastre aconteça.
Mas como?
Cientistas e engenheiros de todo o universo debatem-se com este problema há eões.
Superaglomerados cósmicos inteiros de IA andam a processar os dados.
E então, um dia, ressurge uma lenda: um método antigo e poderoso, sussurrado em fóruns de depuração, resmungado por engenheiros que já viram demasiado...
O Bit de Paridade!
Um método tão simples e tão poderoso que pode muito bem salvar a comunicação interestelar.
Instruções
A tua tarefa é ajudar a implementar
- o transmissor, que calcula a sequência de transmissão, e
- o recetor, que a descodifica.
Um bit de paridade é uma forma simples de detetar erros de transmissão.
Os transmissores e os recetores só podem transmitir e receber exatamente oito bits de cada vez (incluindo o bit de paridade).
O bit de paridade é definido de modo a que haja um número par de bits 1 em cada transmissão, e o bit de paridade é sempre o primeiro bit a contar da direita.
Por isso, se o recetor receber 11000001, 01110101 ou 01000000 (ou seja, uma transmissão com um número ímpar de bits 1), sabe que há um erro.
No entanto, as mensagens raramente são tão curtas e, quando são mais longas, têm de ser transmitidas numa sequência.
Por exemplo, considera a mensagem 11000000 00000001 11000000 11011110 (ou C0 01 C0 DE em hexadecimal).
Como cada transmissão contém exatamente oito bits, só pode conter sete bits de dados e o bit de paridade.
É então necessário inserir um bit de paridade após cada sete bits de dados:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
A sequência de transmissão desta mensagem é 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), por isso o bit de paridade é 0.
A primeira transmissão passa a ser 11000000 (ou C0 em hexadecimal).
Os dados da transmissão seguinte (0000000) têm zero bits 1 (outra vez um número par), por isso o bit de paridade volta a ser 0.
A segunda transmissão passa assim a ser 00000000 (ou 00 em hexadecimal).
Os dados das duas transmissões seguintes (0111000 e 0001101) têm três bits 1.
Os respetivos bits de paridade são definidos como 1 para que a transmissão tenha um número par de bits 1.
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 se transmitem exatamente oito bits de cada vez e o bit de paridade é o bit mais à direita, são acrescentados três bits 0 e depois o bit de paridade para completar os oito bits.
Agora tem este aspeto (em que _ é o bit de paridade):
1110 000_
↑↑↑ (added 0 bits)
Há novamente um número ímpar de bits 1, por isso 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 desta mensagem é 11000000 00000000 01110001 00011011 11100001 (ou C0 00 71 1B E1 em hexadecimal).
