Introducción
Billones y billones de mensajes viajan entre la Tierra y las galaxias vecinas cada milisegundo.
Pero transmitir a distancias tan enormes es complicado.
Las molestas llamaradas solares, las distorsiones temporales, las fuerzas errantes e incluso el aleteo de las alas de una mariposa espacial pueden hacer que un bit aleatorio cambie durante la transmisión.
Ahora imagina las consecuencias:
- Hundir el mercado de valores intergaláctico cuando «buy low» se convierte en «sell now».
- Perder el contacto con el sistema Kepler Whirl cuando «save new worm hole» se convierte en «cave new worm hole».
- O hundir el universo en un horror existencial al sustituir un emoji de vaquero 🤠 por un emoji de payaso 🤡.
Detectar mensajes corruptos no es solo importante: es fundamental.
El receptor debe saber cuándo algo ha salido mal antes de que ocurra el desastre.
Pero ¿cómo?
Científicos e ingenieros de todo el universo llevan eones peleando con este problema.
Supercúmulos cósmicos enteros de IA procesan los datos sin parar.
Y entonces, un día, resurge una leyenda: un método antiguo y poderoso, susurrado en los foros de debug, murmurrado por ingenieros que ya han visto demasiado...
¡El bit de paridad!
Un método tan simple y tan poderoso que podría salvar la comunicación interestelar.
Instrucciones
Tu trabajo consiste en ayudar a implementar
- el transmisor, que calcula la secuencia de transmisión, y
- el receptor, que la descodifica.
Un bit de paridad es una forma sencilla de detectar errores de transmisión.
Los transmisores y los receptores solo pueden transmitir y recibir exactamente ocho bits a la vez (incluido el bit de paridad).
El bit de paridad se establece de forma que haya un número par de bits a 1 en cada transmisión, y el bit de paridad es siempre el primer bit por la derecha.
Así que si el receptor recibe 11000001, 01110101 o 01000000 (es decir, una transmisión con un número impar de bits a 1), sabe que hay un error.
Sin embargo, los mensajes rara vez son tan cortos, y cuando son más largos hay que transmitirlos en una secuencia.
Por ejemplo, considera el mensaje 11000000 00000001 11000000 11011110 (o C0 01 C0 DE en hexadecimal).
Como cada transmisión contiene exactamente ocho bits, solo puede contener siete bits de datos y el bit de paridad.
Por lo tanto, hay que insertar un bit de paridad después de cada siete bits de datos:
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
La secuencia de transmisión de este mensaje es la siguiente:
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
Los datos de la primera transmisión de la secuencia (1100000) tienen dos bits a 1 (un número par), así que el bit de paridad es 0.
La primera transmisión pasa a ser 11000000 (o C0 en hexadecimal).
Los datos de la siguiente transmisión (0000000) tienen cero bits a 1 (un número par de nuevo), así que el bit de paridad vuelve a ser 0.
La segunda transmisión pasa a ser, por tanto, 00000000 (o 00 en hexadecimal).
Los datos de las dos transmisiones siguientes (0111000 y 0001101) tienen tres bits a 1.
Sus bits de paridad se establecen a 1 para que la transmisión tenga un número par de bits a 1.
Se transmiten como 01110001 y 00011011 (o 71 y 1B en hexadecimal).
La última transmisión (1110) solo tiene cuatro bits de datos.
Como se transmiten exactamente ocho bits a la vez y el bit de paridad es el bit situado más a la derecha, se añaden tres bits a 0 y luego el bit de paridad para completar los ocho bits.
Ahora tiene este aspecto (donde _ es el bit de paridad):
1110 000_
↑↑↑ (added 0 bits)
Vuelve a haber un número impar de bits a 1, así que el bit de paridad es 1.
La última transmisión de la secuencia pasa a ser 11100001 (o E1 en hexadecimal).
La secuencia de transmisión completa de este mensaje es 11000000 00000000 01110001 00011011 11100001 (o C0 00 71 1B E1 en hexadecimal).
Implementación
Aunque estamos trabajando con bytes de datos, las entradas y las salidas son List<Integer> (en lugar de byte[]) para no tener que hacer un cast ni convertir los valores negativos de los bytes 128 a 255.
