Comments 56
Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.
Поправлять не буду, вы правы.
Я забыл упомянуть, как генерируются ошибки, там всё примитивно — два независимых случайных события для каждого бита, 5% потерять, 5% сломать.
Вообще, кажется, это и вправду слишком много. Надо было в исходной задаче сделать 1% и 1%. Хотя можно и самому регулировать эти значения на интерфейсе.
Ну и все, если ошибок больше N — пакет посылается заново. N подбирается так, чтобы минимизировать трафик, с учетом вероятностей потерянных и сломанных битов, тут все просто.
Совершенно верно! Сейчас уточню это в описании.
Не приходилось сталкиваться с подобным, первое что интуитивно хочется — наколхозить что-нибудь, чтобы детектировать пропадание бита и возвращать его обратно на место (любым значением). Типа банального дублирования как у вас или манчестера по 4 отсчета (для лучшего выделения границ), сверху обложить уже стандартным коррекционным кодом. Беда в том, что по условию задачи (неявно) возможно выпадание и двух и трех и более бит подряд с некоторрой ненулевой вероятностью (в зависимости от закона распределения). И как с этим бороться не вполне понятно. Не исключаю, что и действительно все уже придумано до нас, но где и кем — не в курсе…
Можно подумать про космические каналы с рандомными отражениями волн от космических камушков и высокоэнергетическими частицами рандомно выбивающие биты.
А за развлечение спасибо)
Можно попробовать оценить нижную границу оверхеда.
Первое — задать 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. На самом деле это идеальный случай. Код, допускающий вставку произвольных бит, ещё нужно придумать. Ну и предполагалось, что все события являются независимыми.
А в чём суть статьи? Чтобы задать вопрос, что ли?
Ну, так навскидку, надо скрестить коды Грея с кодами Рида-Соломона. Кодами Грея отлавливаются пропущенные биты, вместо них вставляются произвольные значения, которые при необходимости корректируются ридом-соломоном.
Суть статьи в том, чтобы дать потеоретизировать (и попрактиковаться онлайн) над задачами, обычно лежащими вне области прикладного программирования. Ну соревнуются же люди в написании "змейки" за 50 строк. Разумеется, не всем это будет интересно.
Выслушивать комментаторов тоже интересно. Вам несложно чуть развить мысль, как использовать коды Грея для пропущенных бит?
В принципе идея верна, если канал ненадежный, протокол должен организовать repetions (повторения). Если же ошибок очень много, то все повторения могут завершиться с ошибкой и тогда что? Можно попробовать уменьшать размер пакета (динамически?), чтобы увеличить вероятность успешной передачи повторения. Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).
Для обнаружения пропущенных битов можно использовать таймаут, если что-то началов приходить, расчитать через сколько времени макс придет последний бит, чтобы завершить передачу. В этом случае необходимо знать длину пакета, либо пакеты всегда фиксированной длины, либо с заголовком. А что если заголовок получен не правильно?
Можно разбить пакет на 2: заголовок и данные. Получатель должен ответить ACK на заголовок, иначе данные не шлются. Если получатель послал ACK, который из-за ошибке не был получен, то опять можно использовать таймаут (после отсылки ACK), чтобы заметить, что данные не шлются и снова ожидать заголовок.
И т.д.
Подскази для "правильных" решений, могут быть например, здесь: https://habrahabr.ru/post/332134/#comment_10295162 Я могу лишь показать "своё", и то, не раньше чем вернусь домой и допишу :)
Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).
Б-же упаси, этот пример здесь только как аналог сортировки пузырьком — показать, что задачу выполняет, но максимально неэффективным способом.
И проблем со считыванием нет — this.read возвращает весь накопленный буфер, если его длина меньше запрашиваемой. А на стороне передающей машины стоит ограничитель интенсивности отправки, чтобы кадры не слеплялись.
В целом, да, позитивные/негативные подтверждения с таймаутами, это путь к успеху.
Мне кажется, что в данных условиях особенно важно отследить потерю битов.
Для этого можно добавить какой-нибудь легко детектируемый синхросимвол (0xFF, например) через равные интервалы, а после этого оценивать потерю и либо восстанавливать кадры, либо перезапрашивать их.
Ещё в этом документе можно посмотреть на реализацию Marker Code, который предназначен для борьбы со вставками/удалениями.
О двух генералах — в точку. Однако, мы можем решить задачу с некоторой, устраивающей нас степенью надежности. Выше в комментариях DistortNeo говорит об этом.
Теоретически возможно даже полное исчезновение сообщения
Для этого и дан нам двусторонний канал. Подтверждения о получении данных. Подтверждение о получении подтверждения. Подтверждение о получении подтверждения подтверждения, и тд. Плюс есть отсчет таймаутов на получение подтверждений, для последующей переотправки.
устраивающей нас степенью надежности.
И какова эта степень?
Ну вот, например, ваша же наивная реализация с оверхедом 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;
}
Обеспечивает в общем-то ~90-100% (в среднем навскидку 97%) целостность, кроме тех случаев, когда «теряются» 6 битов подряд (весь пакет) и вся передача накрывается медным тазом из-за смещения. Можно реализовывать систему «пакет послан-пакет принят полностью», но тогда оверхед снова растет уже в два раза от уже имеющегося (1200+%).
В вашей наивной реализации происходит то же самое, только случаев чуть меньше из-за того, что длина 10 — шанс протерять 10 битов подряд существенно ниже.
Ну здорово же, особо не напрягаясь, уменьшили избыточность, использовав запрос о переотправке команды :)
Если вы не против, добавлю этот вариант в примеры кода, с указанием авторства в комментариях.
Добавлено, с исправлением.
В общем и целом дело обстоит так:
Если верить Бернулли и предположить, что:
а) в каждом посланном 6-битном пакете теряется минимум 1 бит;
б) мы никогда не теряем весь пакет целиком;
то в итоге в среднем выйдет ~11 ошибок на 10000 бит (~99.989% integrity).
Если предположить, что генератор ошибок «мухлюет» (ну или звезды так сошлись) и ломает биты намеренно по три в каждом пакете, но при этом не выходит за рамки 0.05% сломанных от общего числа битов, то, при соблюдениии а) и б), мы получаем минимальную целостность в ~90%.
Однако оба эти пункта у нас не соблюдаются по условию задачи.
Несоблюдение пункта а) в среднем увеличивает целостность, а влияние несоблюдения пункта б) я затрудняюсь оценить: средняя вероятность потерять целый пакет составляет 0.000000015 и потеря пакета ведет к снижению целостности вплоть до 0 в худшем случае — все зависит от последовательности битов в пейлоаде, и номера потерянного пакета (худший случай: пейлоад — «010101010101...», первый пакет потерян; со сдвигом влево на 1 бит имеем 0% попаданий).
Если пришло меньше — значит, биты были потеряны. Дополняем до X спереди, спереди и сзади или сзади (по очереди). Результат прогоняем через декодировщик Рида-Соломона, который рассчитан на коррецию (n+m) ошибок, где n — число бит, которые могут быть потеряны, а m — число возможных инверций бита.
Я не понял, почему нельзя просто взять и сделать TCP?
Обновил до версии 0.1.4, добавил свой вариант решения. Не ахти что по оверхеду — в среднем 520% для больших данных. Однако целостность поддерживается надежно, BER примерно 3e-7.
Сохраню здесь ещё полезные ссылки:
- Восстановление потерянных битов в канале с потерями — но без ошибок интерпретации, т. е. когда бит или принят, или утерян, но факт этого неизвестен
- Feng Wang — Coding for Insertion/Deletion Channels — работа, в которой разрабатывается комбинация варианта LDPC кодирования с маркерным кодом.
Один бит сломал, другой потерял: задачка по передаче данных