Skip to Content
CTRL K

Data Transfer

Concentrémonos en la subtarea 2, ya que la solución de la subtarea 1 es esencialmente la misma.

Pista 1

9=log⁡2256+19 = \log_2{256} + 1. Esto significa que podemos añadir 8 bits (para guardar un entero menor que 256) y un bit extra.

Pista 2

XOR es tu aliado en problemas con operaciones bit a bit.

Pista 3

El bit extra no puede guardar información significativa sobre los 255 bits originales. ¿Puede guardar algo significativo sobre los primeros 8 bits que añadimos?

Solución

Sea xx inicialmente 0. Recorremos los 255 bits originales y, si el ii-ésimo bit es 1, hacemos XOR de xx con ii. Luego añadimos los 8 bits de xx a los datos.

Esto es conveniente porque podemos usar xx para determinar si alguno de los primeros 263 bits de datos que enviamos se corrompió, ya que a lo sumo un bit se corrompe.

Si alguno de esos bits se corrompe, ¿cómo distinguimos si se corrompieron los primeros 255 bits o xx?

Consideramos la cantidad de 1s en la representación bit a bit de xx. Si este número es impar, añadimos 1 a los datos como bit extra, y 0 en caso contrario. Luego podemos comparar este bit extra con xx si sabemos que hay una corrupción.

#include "transfer.h"
 
std::vector<int> get_attachment(std::vector<int> source) {
	std::vector<int> v;
	int x = 0;
	for (int i = 0; i < source.size(); i++)
		if (source[i]) x ^= (i + 1);
 
	int last = 0;
	if (source.size() < 64) {
		for (int i = 0; i < 6; i++) {
			v.push_back(x & 1);
			if (x & 1) last = 1 - last;
			x >>= 1;
		}
	} else {
		for (int i = 0; i < 8; i++) {
			v.push_back(x & 1);
			if (x & 1) last = 1 - last;
			x >>= 1;
		}
	}
	v.push_back(last);
	return v;
}
 
std::vector<int> retrieve(std::vector<int> data) {
	int last = data.back();
	data.pop_back();
	int actual_last = 0, x = 0;
	if (data.size() < 71) {
		for (int i = 0; i < 6; i++) {
			x <<= 1;
			x += data.back();
			if (data.back()) actual_last = 1 - actual_last;
			data.pop_back();
		}
	} else {
		for (int i = 0; i < 8; i++) {
			x <<= 1;
			x += data.back();
			if (data.back()) actual_last = 1 - actual_last;
			data.pop_back();
		}
	}
 
	if (actual_last != last) return std::vector<int>(data.begin(), data.end());
 
	int actual_x = 0;
	for (int i = 0; i < data.size(); i++) {
		if (data[i]) actual_x ^= (i + 1);
	}
 
	int error = actual_x ^ x;
	if (error == 0) return data;
 
	data[error - 1] = 1 - data[error - 1];
	return data;
}

Esencialmente estamos creando un código de Hamming .

Fundamentos