Задача для программистов

Предыстория

Все мы знаем что представляет из себя проблема обнаружения ошибок, то есть добавление некоторой избыточной информации к сообщению, позволяющей с высокой вероятностью определить, было ли сообщение изменено. Существует также избыточное кодирование, позволяющее не только определить наличие ошибки, но и попытаться ее исправить.

На эту тему и будет задачка — решить задачу об избыточном кодировании, но на микро-условиях, и в жестко заданных рамках. Бывает что мне лезут в голову задачки, это одна из них.

Условие задачи

Дано 11 бит полезной информации. Эту информацию нужно передать по ненадежному каналу. Для этого мы можем дописать в конец 5 (пять) бит избыточной информации. Итого получается 2 байта, которые и передаются.

Задача

Представить алгоритм (точнее, два алгоритма), а именно:

1. Кодировщик: по заданным 11 битам информации, получить 16 бит избыточной информации. Хорошо, если первые 11 бит будут такие же, как и в условии, хотя это необязательно.
2. Декодировщик: По заданым 16 битам, возможно искаженной, информации, получить 11 исходных бит, либо хотя бы обнаружить искажение.

Теперь пара слов об искажении

Назовем ошибкой, когда один любой бит при передаче меняется на противоположный. Так вот, алгоритм должен удовлетворять следующим условиям:

• Если ошибок ноль или одна, необходимо со 100% гарантией вернуть исходную информацию (11 бит)
• Если ошибки две, необходимо со 100% гарантией распознать наличие ошибки
• Ошибки могут быть в любой части передаваемой информации, как в полезных данных, так и в контрольном коде!

P.S.

Если лениво думать над задачей, вот еще одна, на совершенно другую тему:

Можно ли составить любой заполненный прямоугольник на квадратной сетке из фигур, одна из которых — «уголок»:

а все остальные — «прямые»:

Фигуры можно вращать. Прямоугольник должен быть составлен без наложений фигур на себя (в один слой), и не содержать внутри дырок.