Картинка отсюдаПредлагаю в качестве тренировки для мозга следующую задачку:
Общаются между собой две машины. Шлют друг другу цифровые данные, натурально нули и единицы. Только канал между ними не очень: биты регулярно то искажаются, то пропадают вовсе. Допустим, наш канал из 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%.
- + resend requests — несложный вариант, предложенный haldagan, хоть и не обеспечивающий 100% целостности, но уменьшающий оверхед до ~550% и пытающийся корректировать ошибки запросом о переотправке.
Между первой идеей и последней точкой (первой версии) этой статьи пока что еще прошло меньше 12 часов, так что не обессудьте, если что пропустил. Пишите, поправлю как можно оперативней.
UPD: вот и мой вариант подоспел к шапочному разбору:
- Author's proposal отправляет короткие сообщения с кодами обнаружения ошибок, переподает по запросу. Неисправимо искаженных данных примерно 3 бит на 107
Комментарии (55)
nerudo
02.07.2017 23:31+3Под словом «теряет» (в противовес «ломает») вы подразумеваете, что на приемной стороне в среднем будет приходить 19 бит вместо 20 и место потерянного бита неизвестно?
augur
02.07.2017 23:36+1Совершенно верно! Сейчас уточню это в описании.
nerudo
02.07.2017 23:57+6Весьма нетрадиционный канал. Да и по качеству паршивый. Лучше бы выкинуть его в помойку и спать пойти ;)
Не приходилось сталкиваться с подобным, первое что интуитивно хочется — наколхозить что-нибудь, чтобы детектировать пропадание бита и возвращать его обратно на место (любым значением). Типа банального дублирования как у вас или манчестера по 4 отсчета (для лучшего выделения границ), сверху обложить уже стандартным коррекционным кодом. Беда в том, что по условию задачи (неявно) возможно выпадание и двух и трех и более бит подряд с некоторрой ненулевой вероятностью (в зависимости от закона распределения). И как с этим бороться не вполне понятно. Не исключаю, что и действительно все уже придумано до нас, но где и кем — не в курсе…
izzholtik
03.07.2017 00:57+1Любой канал с линией клока. SPI, I?C, например.
Alj
03.07.2017 08:08Если у вас биты в SPI выпадают, то «проводку» (или разводку, при высокой частоте) пора менять или быстродействия контроллера не хватает. Лучше в пример UART, где действительно могут быть потери из-за рассинхронизации.
nerudo
03.07.2017 08:41Могу еще добавить, что в любом канале с линией клока используется по сути два, а то и три канала и весь контроль ведется на уровне транзакции. Да и то, если к примере пропадет один из клоков в I?C, это повесит шину в лучшем случае до таймаута.
domix32
03.07.2017 10:55+1Можно подумать про космические каналы с рандомными отражениями волн от космических камушков и высокоэнергетическими частицами рандомно выбивающие биты.
Labunsky
03.07.2017 02:08+1К какому значению оверхеда нужно стремиться-то хоть?
А за развлечение спасибо)augur
03.07.2017 08:23Напишете с оверхедом 500%,
возьмут в Яндекс без собеседований, будет уже круто :)
Ночью создавал решение, выходило где-то на 600%, но не дооформил до конца, ушел спать.
Jef239
03.07.2017 09:58Оверхед можно уменьшить за счет посылки подтверждений в обратную сторону. К сожалению, неизвестна скорость прохождения по каналу. Но если канал мгновенный, то можно сыграть на этом и уменьшить оверхед.
Ещё один момент — есть ли паузы в канале. В обычном UART — 3 состояния — ноль, 1 и нет сигнала.
DistortNeo
03.07.2017 02:15+3Можно попробовать оценить нижную границу оверхеда.
Первое — задать BER (пусть будет 1e-6), второе — определиться с размером блока и максимальным количеством бит, которые можно потерять или исказить. Логично, что кодовые слова должны быть сильно больше 20 бит. Например, для блока из 200 бит для поддержания указанного BER нужно допустить потерю 25 бит и искажение 25 бит.
Будем бороться с проблемами по очереди и начнём с потери бит. В этом случае исходный блок будет иметь размер 175 бит и до 25 бит могут быть вставлены в произвольные места. Вопрос в том, какой максимальный размер информации при этом можно передать. Число возможных вставок ноликов и единиц огромно и примерно равно 2^131 комбинаций (sum{k = 175}^{k = 200} C^{k}{200} 2^k). То есть на полезную информацию остаётся всего 44 бита. Учитывая, что redundancy для исправления искажения битов надо накладывать не на эти 44 бита, а на исходные 175 бит, всё плохо — в BER не укладываемся. Нужно брать более длинный блок.
Пусть блок — 1000 бит, тогда для достижения указанного BER будет допустима потеря и искажение по ~90 бит. Аналогично получаем около 520 бит избыточности на чистые 910 бит. Накладываем Рида-Соломона (+180 бит), получаем 910 — 520 — 180 = 210 бит полезных данных. Если увеличивать размер блока, можно ещё увеличить долю полезных данных, но считать сложно.
P.S. На самом деле это идеальный случай. Код, допускающий вставку произвольных бит, ещё нужно придумать. Ну и предполагалось, что все события являются независимыми.
augur
03.07.2017 07:58Спасибо за развернутый анализ! По моим прикидкам тоже получается, что оверхед ниже 400-500% при таком канале обеспечить не получится.
В этом случае исходный блок будет иметь размер 175 бит и до 25 бит могут быть вставлены в произвольные места.
Тут можно поподробнее, каким способом это достигается?
mvv
03.07.2017 07:37+2Вспомнились древние времена, когда занимался написанием драйвера загрузки данных с бытового кассетного магнитофона…
avost
03.07.2017 09:05+1А в чём суть статьи? Чтобы задать вопрос, что ли?
Ну, так навскидку, надо скрестить коды Грея с кодами Рида-Соломона. Кодами Грея отлавливаются пропущенные биты, вместо них вставляются произвольные значения, которые при необходимости корректируются ридом-соломоном.augur
03.07.2017 12:44Суть статьи в том, чтобы дать потеоретизировать (и попрактиковаться онлайн) над задачами, обычно лежащими вне области прикладного программирования. Ну соревнуются же люди в написании "змейки" за 50 строк. Разумеется, не всем это будет интересно.
Выслушивать комментаторов тоже интересно. Вам несложно чуть развить мысль, как использовать коды Грея для пропущенных бит?
deniskreshikhin
03.07.2017 09:27Нужно найти компромисс между оверхедом над полезной нагрузкой сети, и временем работы передающей и принимающей машин.
И как этот компромисс должен выглядеть? Можно же сделать время обработки oo и получить пропускную способность в теоретический предел.
Sinatr
03.07.2017 10:55А будет «правильное» решение? Или вы ждете ответа от комментаторов?
В принципе идея верна, если канал ненадежный, протокол должен организовать repetions (повторения). Если же ошибок очень много, то все повторения могут завершиться с ошибкой и тогда что? Можно попробовать уменьшать размер пакета (динамически?), чтобы увеличить вероятность успешной передачи повторения. Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).
Для обнаружения пропущенных битов можно использовать таймаут, если что-то началов приходить, расчитать через сколько времени макс придет последний бит, чтобы завершить передачу. В этом случае необходимо знать длину пакета, либо пакеты всегда фиксированной длины, либо с заголовком. А что если заголовок получен не правильно?
Можно разбить пакет на 2: заголовок и данные. Получатель должен ответить ACK на заголовок, иначе данные не шлются. Если получатель послал ACK, который из-за ошибке не был получен, то опять можно использовать таймаут (после отсылки ACK), чтобы заметить, что данные не шлются и снова ожидать заголовок.
И т.д.augur
03.07.2017 15:56Подскази для "правильных" решений, могут быть например, здесь: https://habrahabr.ru/post/332134/#comment_10295162 Я могу лишь показать "своё", и то, не раньше чем вернусь домой и допишу :)
Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).
Б-же упаси, этот пример здесь только как аналог сортировки пузырьком — показать, что задачу выполняет, но максимально неэффективным способом.
И проблем со считыванием нет —this.readвозвращает весь накопленный буфер, если его длина меньше запрашиваемой. А на стороне передающей машины стоит ограничитель интенсивности отправки, чтобы кадры не слеплялись.
В целом, да, позитивные/негативные подтверждения с таймаутами, это путь к успеху.
Xitsa
03.07.2017 11:28+2Мне кажется, что в данных условиях особенно важно отследить потерю битов.
Для этого можно добавить какой-нибудь легко детектируемый синхросимвол (0xFF, например) через равные интервалы, а после этого оценивать потерю и либо восстанавливать кадры, либо перезапрашивать их.
koldyr
03.07.2017 11:55Задача о двух генералах не имеет решения.
augur
03.07.2017 13:30О двух генералах — в точку. Однако, мы можем решить задачу с некоторой, устраивающей нас степенью надежности. Выше в комментариях DistortNeo говорит об этом.
syrslava
03.07.2017 13:35Про устраивающую степень надежности понравилось… Теоретически возможно даже полное исчезновение сообщения :)
augur
03.07.2017 14:17Теоретически возможно даже полное исчезновение сообщения
Для этого и дан нам двусторонний канал. Подтверждения о получении данных. Подтверждение о получении подтверждения. Подтверждение о получении подтверждения подтверждения, и тд. Плюс есть отсчет таймаутов на получение подтверждений, для последующей переотправки.
haldagan
03.07.2017 13:39+1устраивающей нас степенью надежности.
И какова эта степень?
Ну вот, например, ваша же наивная реализация с оверхедом 500-510%.
Код//sender req=this.read(7); if (req.length > 0){ this.write(this.lastSent); //console.log('resending:' + this.lastSent); return true; } if (this.counter() % 2 !== 0) return true; var single = this.getPayload(1); if (single.length > 0) { var frame = new Array(6); frame.fill(single[0]); this.lastSent=frame; this.write(frame); //console.log('sending:' + frame ); return true; } else { // console.log('nothing to send...'); } //reciever if (!this.lastMessageTime) this.lastMessageTime = 0; var frame = this.read(6); if (frame.length > 0) { this.lastMessageTime = this.counter(); //console.log('recieved:' + frame); if (frame.length<4) { this.write([1,1,1,1,1,1,1]); //console.log('requesting validation'); return true; } var zeros = 0; for (var bit of frame) { zeros = (bit === 0) ? zeros + 1 : zeros; } if (zeros > frame.length / 2) { this.acceptPayload([0]); //console.log('---accepted 0'); } else if (zeros==frame.length / 2) { this.write([1,1,1,1,1,1,1]); //console.log('requesting validation'); return true; } else { this.acceptPayload([1]); //console.log('---accepted 1'); } return true; } else { if (this.lastMessageTime > this.counter() - 10) return true; }haldagan
03.07.2017 14:01UPD: Неправильно посчитал. В моем случае достаточно 4х «сломанных» битов подряд, в вашем — 5-6 (из-за условия ">", в зависимости от того, нули сломали или единицы).
augur
03.07.2017 14:20Ну здорово же, особо не напрягаясь, уменьшили избыточность, использовав запрос о переотправке команды :)
Если вы не против, добавлю этот вариант в примеры кода, с указанием авторства в комментариях.haldagan
03.07.2017 14:24Не против, но я в нем просмотрел одну некритическую ошибку: там где if (frame.length<4) должно быть if (frame.length<5) по задумке, и оверхед выходит уже не ~500-510, а ~530-570%.
augur
03.07.2017 14:54Добавлено, с исправлением.
haldagan
03.07.2017 16:10Про 97%, наверное стоит убрать, цифра названа наобум.
В общем и целом дело обстоит так:
Если верить Бернулли и предположить, что:
а) в каждом посланном 6-битном пакете теряется минимум 1 бит;
б) мы никогда не теряем весь пакет целиком;
то в итоге в среднем выйдет ~11 ошибок на 10000 бит (~99.989% integrity).
Если предположить, что генератор ошибок «мухлюет» (ну или звезды так сошлись) и ломает биты намеренно по три в каждом пакете, но при этом не выходит за рамки 0.05% сломанных от общего числа битов, то, при соблюдениии а) и б), мы получаем минимальную целостность в ~90%.
Однако оба эти пункта у нас не соблюдаются по условию задачи.
Несоблюдение пункта а) в среднем увеличивает целостность, а влияние несоблюдения пункта б) я затрудняюсь оценить: средняя вероятность потерять целый пакет составляет 0.000000015 и потеря пакета ведет к снижению целостности вплоть до 0 в худшем случае — все зависит от последовательности битов в пейлоаде, и номера потерянного пакета (худший случай: пейлоад — «010101010101...», первый пакет потерян; со сдвигом влево на 1 бит имеем 0% попаданий).
syrslava
03.07.2017 12:45А канал действует только в одну сторону? («шлют друг другу»)
(Первое, что приходит в голову при работе с двухсторонней связью — хеш-суммы.)
Тривиальный алгоритмПосле получения блока данных (четкой длины в n бит, с избыточностью или без — заранее оговаривается) получатель шлёт обратно хеш; отправитель сравнивает собственный хеш для этого блока с принятым, и, при несовпадении, повторяет пересылку, чуть-чуть модифицируя исходное сообщение (например, добавляя относительно метку повтора), повторяется сравнение хешей. После удачногог завершения работы с одним блоком переходим к следующему.haldagan
03.07.2017 13:02А как тогда проверять, что хеш пришел именно тот, что послали?
Пересылка в обратную сторону подвержена тем же ошибкам: в хеше может нехватать некоторого количества бит и некоторые биты могут быть «сломаны».syrslava
03.07.2017 13:080) использовать небольшой хеш
1) повторить передачу блока с сигналом о повторе
syrslava
03.07.2017 13:10-1upd: В простейшем случае даже бит четности может оказаться поврежден, приходится запрашивать повторную посылку. (пардон, не освоился с интерфейсом сайта)
louiscyphre
06.07.2017 07:31Может слать его в том же сообщении, повторяющимся более заданного количества раз?
[msg][hash][hash][hash]
4eyes
03.07.2017 20:15Как идея: а почему бы не договориться слать данные пакетами только по X байт?
Если пришло меньше — значит, биты были потеряны. Дополняем до X спереди, спереди и сзади или сзади (по очереди). Результат прогоняем через декодировщик Рида-Соломона, который рассчитан на коррецию (n+m) ошибок, где n — число бит, которые могут быть потеряны, а m — число возможных инверций бита.augur
03.07.2017 21:47Да, сообщения фиксированной длины это верный путь, сам выбирал такой. Несколько напрягает только переотправка, так как запрос о переотправке может потеряться. И тогда, когда приходит еще один пакет, непонятно, переотправленный это пакет, или новый?
augur
03.07.2017 21:37Обновил до версии 0.1.4, добавил свой вариант решения. Не ахти что по оверхеду — в среднем 520% для больших данных. Однако целостность поддерживается надежно, BER примерно 3e-7.
ser-mk
05.07.2017 20:32Добавлю, что в физических каналах, помимо всего прочего могут еще добавляться паразитные биты :)
mwizard
Все уже придумано до нас.
augur
Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.
mwizard
Поправлять не буду, вы правы.
zerg59
Пусть 1 бит сломан и 1 потерян. Берём код, корректирующий искажение 2 бит. А затем в полученный пакет последовательно втыкаем единичку в разные места пока алгоритм коррекции не исправит двойную (или одинарную если потеряна единичка) ошибку. Или вообще не скажет что все хорошо ибо потерянный бит был сломанной единичкой:-)
nerudo
Автор жесток и не зря указал «в среднем». То есть никто не обещает, что на каждые 20 бит будет ровно одна потеря и одно искажение. Ваш подход бы сработал, если бы вероятность потери была не 1/20, а на несколько порядков меньше — тогда синхронизируемся, и потом ловим сбои вашим методом. А так даже начать работать не удасться…
augur
Я забыл упомянуть, как генерируются ошибки, там всё примитивно — два независимых случайных события для каждого бита, 5% потерять, 5% сломать.
Вообще, кажется, это и вправду слишком много. Надо было в исходной задаче сделать 1% и 1%. Хотя можно и самому регулировать эти значения на интерфейсе.
petropavel
Конечно. Раз «в среднем», то нужен код, исправляющий N ошибок и способный обнаруживать гораздо больше. Коды Рида-Соломона исправляют N и обнаруживают, вроде, 2N. Можно еще и контрольную. сумму прилепить для надежности.
Ну и все, если ошибок больше N — пакет посылается заново. N подбирается так, чтобы минимизировать трафик, с учетом вероятностей потерянных и сломанных битов, тут все просто.