Один бит сломал, другой потерял: задачка по передаче данных

в 19:19, , рубрики: Алгоритмы, выходные, задачки, Занимательные задачки, ненормальное программирование, Программирование

Здравствуй!

imageКартинка отсюда

Предлагаю в качестве тренировки для мозга следующую задачку:

Общаются между собой две машины. Шлют друг другу цифровые данные, натурально нули и единицы. Только канал между ними не очень: биты регулярно то искажаются, то пропадают вовсе. Допустим, наш канал из 20 бит в среднем один бит ломает, другой теряет. А теперь пишем алгоритм, наиболее оптимально эти данные передающий.


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

Вы скажете, серьезные ребята из IEEE и смежных организаций уже всё давно придумали, и будете правы. Но когда это мешало переизобретать, just for lulz? И вылезти ненадолго из зоны комфорта надежных и простых сокетов (Не подсматривая какие-нибудь RFC)? Тем более, делать это будем на JavaScript, в браузере, без сторонних библиотек, еще желательно чтобы на один экран влезло:

Вот прямо тут

Понимаю предвзятое отношение многих к JavaScript, однако его единственного можно за 5 минут встроить в браузер и дать возможно редактировать и исполнять. Несложный базовый синтаксис, пишешь будто на псевдкоде.

Весь код исполняется локально. Подключен CodeMirror для редактора кода.
Пишем содержимое двух функций, периодически вызываемых на передающей (Sender Source) и (Receiver Destination) машинах.

В нашем распоряжении контекст this, имеющий аж 5 методов:

var runs = this.counter();

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

var frame = this.getPayload(n);

Доступен на передающей машине. Считывает и возвращает следующие n бит полезной нагрузки.

this.write(frame);

Передает frame, являющийся массивом бит, другой машине. Проходя по каналу передачи, сообщение, возможно, будет искажено.

var frame = this.read(n);

Считывает из входящего сетевого буфера до n бит. Если ничего нет, вернет пустой массив.

this.acceptPayload(frame);

Доступен на принимающей машине. Помещает frame в результирующий массив.

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

Я добавил несколько примеров исходного кода:

  • Tutorial — чуть более подробное описание возможностей передающих и принимающих машин.
  • No Corrections — простейший алгоритм, не следящей за целостностью передаваемых данных. Оверхед отсутствует, но целостность оставляет желать лучшего.
  • Naive 900% Overhead — думаю, понятно из названия. Шлем не торопясь по одному биту, продублированному десять раз. Работает более-менее стабильно (хотя изредка целостность нарушалась), но оверхед по нагрузке сети 900%.

Между первой идеей и последней точкой этой статьи пока что еще прошло меньше 12 часов, так что не обессудьте, если что пропустил. Пишите, поправлю как можно оперативней.

Автор: Денис Кильчичаков

Источник

Поделиться

* - обязательные к заполнению поля