Hermit И просьба Википедией и поисковыми системами не пользоваться!

ну да, вроде об этом договорились еще в начале викторины.

В общем, посмотрела я, что тут предлагали и предлагаю вообще не передавать исходное сообщение. Точнее так.
Пусть исходное сообщение состоит из 4х бит: i1, i2, i3, i4
Тогда передаем следующее:
bit1: i1
bit2: i1
bit3: i2
bit4: xor(i1, i2)
bit5: xor(bit4,i3)
bit6: xor(bit5,i4)
bit7: xor(i3,i4)

Все случаи не проверяла, но навскидку везде двойная проверка и можно восстановить, какой бит битый и его реальное значение.

Вот только совсем не легкий пример получился. Возможно, кто-то найдет решение попроще.

Добавлено через 7 минут
xor (0,0) = 0
xor (0,1) = 1
xor (1,0) = 1
xor (1,1) = 0

т.е. это проверка одинаковые операнды или разные.

Пример.
Необходимо передать 1 1 1 1
Передаем 1 1 1 0 1 0 0