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

    Здравствуй, Хабр!

    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%.
    • + resend requests — несложный вариант, предложенный haldagan, хоть и не обеспечивающий 100% целостности, но уменьшающий оверхед до ~550% и пытающийся корректировать ошибки запросом о переотправке.

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

    UPD: вот и мой вариант подоспел к шапочному разбору:
    • Author's proposal отправляет короткие сообщения с кодами обнаружения ошибок, переподает по запросу. Неисправимо искаженных данных примерно 3 бит на 107
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 56

        +2

        Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.

          +1

          Поправлять не буду, вы правы.

            +1
            Пусть 1 бит сломан и 1 потерян. Берём код, корректирующий искажение 2 бит. А затем в полученный пакет последовательно втыкаем единичку в разные места пока алгоритм коррекции не исправит двойную (или одинарную если потеряна единичка) ошибку. Или вообще не скажет что все хорошо ибо потерянный бит был сломанной единичкой:-)
              +2
              Автор жесток и не зря указал «в среднем». То есть никто не обещает, что на каждые 20 бит будет ровно одна потеря и одно искажение. Ваш подход бы сработал, если бы вероятность потери была не 1/20, а на несколько порядков меньше — тогда синхронизируемся, и потом ловим сбои вашим методом. А так даже начать работать не удасться…
                0

                Я забыл упомянуть, как генерируются ошибки, там всё примитивно — два независимых случайных события для каждого бита, 5% потерять, 5% сломать.
                Вообще, кажется, это и вправду слишком много. Надо было в исходной задаче сделать 1% и 1%. Хотя можно и самому регулировать эти значения на интерфейсе.

                  0
                  Конечно. Раз «в среднем», то нужен код, исправляющий N ошибок и способный обнаруживать гораздо больше. Коды Рида-Соломона исправляют N и обнаруживают, вроде, 2N. Можно еще и контрольную. сумму прилепить для надежности.

                  Ну и все, если ошибок больше N — пакет посылается заново. N подбирается так, чтобы минимизировать трафик, с учетом вероятностей потерянных и сломанных битов, тут все просто.
            +3
            Под словом «теряет» (в противовес «ломает») вы подразумеваете, что на приемной стороне в среднем будет приходить 19 бит вместо 20 и место потерянного бита неизвестно?
              +1

              Совершенно верно! Сейчас уточню это в описании.

                +6
                Весьма нетрадиционный канал. Да и по качеству паршивый. Лучше бы выкинуть его в помойку и спать пойти ;)
                Не приходилось сталкиваться с подобным, первое что интуитивно хочется — наколхозить что-нибудь, чтобы детектировать пропадание бита и возвращать его обратно на место (любым значением). Типа банального дублирования как у вас или манчестера по 4 отсчета (для лучшего выделения границ), сверху обложить уже стандартным коррекционным кодом. Беда в том, что по условию задачи (неявно) возможно выпадание и двух и трех и более бит подряд с некоторрой ненулевой вероятностью (в зависимости от закона распределения). И как с этим бороться не вполне понятно. Не исключаю, что и действительно все уже придумано до нас, но где и кем — не в курсе…
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Если у вас биты в SPI выпадают, то «проводку» (или разводку, при высокой частоте) пора менять или быстродействия контроллера не хватает. Лучше в пример UART, где действительно могут быть потери из-за рассинхронизации.
                      0
                      Могу еще добавить, что в любом канале с линией клока используется по сути два, а то и три канала и весь контроль ведется на уровне транзакции. Да и то, если к примере пропадет один из клоков в I²C, это повесит шину в лучшем случае до таймаута.
                      +1

                      Можно подумать про космические каналы с рандомными отражениями волн от космических камушков и высокоэнергетическими частицами рандомно выбивающие биты.

                  +1
                  К какому значению оверхеда нужно стремиться-то хоть?
                  А за развлечение спасибо)
                    0

                    Напишете с оверхедом 500%, возьмут в Яндекс без собеседований, будет уже круто :)
                    Ночью создавал решение, выходило где-то на 600%, но не дооформил до конца, ушел спать.

                      0
                      Оверхед можно уменьшить за счет посылки подтверждений в обратную сторону. К сожалению, неизвестна скорость прохождения по каналу. Но если канал мгновенный, то можно сыграть на этом и уменьшить оверхед.

                      Ещё один момент — есть ли паузы в канале. В обычном UART — 3 состояния — ноль, 1 и нет сигнала.
                    +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. На самом деле это идеальный случай. Код, допускающий вставку произвольных бит, ещё нужно придумать. Ну и предполагалось, что все события являются независимыми.

                      0

                      Спасибо за развернутый анализ! По моим прикидкам тоже получается, что оверхед ниже 400-500% при таком канале обеспечить не получится.


                      В этом случае исходный блок будет иметь размер 175 бит и до 25 бит могут быть вставлены в произвольные места.

                      Тут можно поподробнее, каким способом это достигается?

                      0
                      код манчестера не?
                        +1

                        Манчестерское кодирование решает задачи физического уровня, а у нас тут, скорее, с канальным уровнем вопросы.

                        +2
                        Вспомнились древние времена, когда занимался написанием драйвера загрузки данных с бытового кассетного магнитофона…
                          +1

                          А в чём суть статьи? Чтобы задать вопрос, что ли?
                          Ну, так навскидку, надо скрестить коды Грея с кодами Рида-Соломона. Кодами Грея отлавливаются пропущенные биты, вместо них вставляются произвольные значения, которые при необходимости корректируются ридом-соломоном.

                            0

                            Суть статьи в том, чтобы дать потеоретизировать (и попрактиковаться онлайн) над задачами, обычно лежащими вне области прикладного программирования. Ну соревнуются же люди в написании "змейки" за 50 строк. Разумеется, не всем это будет интересно.
                            Выслушивать комментаторов тоже интересно. Вам несложно чуть развить мысль, как использовать коды Грея для пропущенных бит?

                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              WinRAR умеет делать многотомные архивы с избыточной информацией, которые распаковываются, даже если один том из десяти (любой), например, полностью потеряется. Это не оно?
                                +2
                                Фонтанные коды?
                              0
                              А будет «правильное» решение? Или вы ждете ответа от комментаторов?

                              В принципе идея верна, если канал ненадежный, протокол должен организовать repetions (повторения). Если же ошибок очень много, то все повторения могут завершиться с ошибкой и тогда что? Можно попробовать уменьшать размер пакета (динамически?), чтобы увеличить вероятность успешной передачи повторения. Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).

                              Для обнаружения пропущенных битов можно использовать таймаут, если что-то началов приходить, расчитать через сколько времени макс придет последний бит, чтобы завершить передачу. В этом случае необходимо знать длину пакета, либо пакеты всегда фиксированной длины, либо с заголовком. А что если заголовок получен не правильно?

                              Можно разбить пакет на 2: заголовок и данные. Получатель должен ответить ACK на заголовок, иначе данные не шлются. Если получатель послал ACK, который из-за ошибке не был получен, то опять можно использовать таймаут (после отсылки ACK), чтобы заметить, что данные не шлются и снова ожидать заголовок.

                              И т.д.
                                0

                                Подскази для "правильных" решений, могут быть например, здесь: https://habrahabr.ru/post/332134/#comment_10295162 Я могу лишь показать "своё", и то, не раньше чем вернусь домой и допишу :)


                                Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).

                                Б-же упаси, этот пример здесь только как аналог сортировки пузырьком — показать, что задачу выполняет, но максимально неэффективным способом.
                                И проблем со считыванием нет — this.read возвращает весь накопленный буфер, если его длина меньше запрашиваемой. А на стороне передающей машины стоит ограничитель интенсивности отправки, чтобы кадры не слеплялись.


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

                                +2

                                Мне кажется, что в данных условиях особенно важно отследить потерю битов.
                                Для этого можно добавить какой-нибудь легко детектируемый синхросимвол (0xFF, например) через равные интервалы, а после этого оценивать потерю и либо восстанавливать кадры, либо перезапрашивать их.

                                  +2

                                  Ещё в этом документе можно посмотреть на реализацию Marker Code, который предназначен для борьбы со вставками/удалениями.

                                  0
                                  Задача о двух генералах не имеет решения.
                                    0

                                    О двух генералах — в точку. Однако, мы можем решить задачу с некоторой, устраивающей нас степенью надежности. Выше в комментариях DistortNeo говорит об этом.

                                      0
                                      Про устраивающую степень надежности понравилось… Теоретически возможно даже полное исчезновение сообщения :)
                                        0
                                        Теоретически возможно даже полное исчезновение сообщения

                                        Для этого и дан нам двусторонний канал. Подтверждения о получении данных. Подтверждение о получении подтверждения. Подтверждение о получении подтверждения подтверждения, и тд. Плюс есть отсчет таймаутов на получение подтверждений, для последующей переотправки.

                                        +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;
                                        }
                                        



                                        Обеспечивает в общем-то ~90-100% (в среднем навскидку 97%) целостность, кроме тех случаев, когда «теряются» 6 битов подряд (весь пакет) и вся передача накрывается медным тазом из-за смещения. Можно реализовывать систему «пакет послан-пакет принят полностью», но тогда оверхед снова растет уже в два раза от уже имеющегося (1200+%).

                                        В вашей наивной реализации происходит то же самое, только случаев чуть меньше из-за того, что длина 10 — шанс протерять 10 битов подряд существенно ниже.
                                          0
                                          UPD: Неправильно посчитал. В моем случае достаточно 4х «сломанных» битов подряд, в вашем — 5-6 (из-за условия ">", в зависимости от того, нули сломали или единицы).
                                            0

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

                                              0
                                              Не против, но я в нем просмотрел одну некритическую ошибку: там где if (frame.length<4) должно быть if (frame.length<5) по задумке, и оверхед выходит уже не ~500-510, а ~530-570%.
                                                0

                                                Добавлено, с исправлением.

                                                  0
                                                  Про 97%, наверное стоит убрать, цифра названа наобум.
                                                  В общем и целом дело обстоит так:

                                                  Если верить Бернулли и предположить, что:
                                                  а) в каждом посланном 6-битном пакете теряется минимум 1 бит;
                                                  б) мы никогда не теряем весь пакет целиком;

                                                  то в итоге в среднем выйдет ~11 ошибок на 10000 бит (~99.989% integrity).

                                                  Если предположить, что генератор ошибок «мухлюет» (ну или звезды так сошлись) и ломает биты намеренно по три в каждом пакете, но при этом не выходит за рамки 0.05% сломанных от общего числа битов, то, при соблюдениии а) и б), мы получаем минимальную целостность в ~90%.

                                                  Однако оба эти пункта у нас не соблюдаются по условию задачи.
                                                  Несоблюдение пункта а) в среднем увеличивает целостность, а влияние несоблюдения пункта б) я затрудняюсь оценить: средняя вероятность потерять целый пакет составляет 0.000000015 и потеря пакета ведет к снижению целостности вплоть до 0 в худшем случае — все зависит от последовательности битов в пейлоаде, и номера потерянного пакета (худший случай: пейлоад — «010101010101...», первый пакет потерян; со сдвигом влево на 1 бит имеем 0% попаданий).
                                        0
                                        А канал действует только в одну сторону? («шлют друг другу»)
                                        (Первое, что приходит в голову при работе с двухсторонней связью — хеш-суммы.)

                                        Тривиальный алгоритм
                                        После получения блока данных (четкой длины в n бит, с избыточностью или без — заранее оговаривается) получатель шлёт обратно хеш; отправитель сравнивает собственный хеш для этого блока с принятым, и, при несовпадении, повторяет пересылку, чуть-чуть модифицируя исходное сообщение (например, добавляя относительно метку повтора), повторяется сравнение хешей. После удачногог завершения работы с одним блоком переходим к следующему.
                                          0
                                          А как тогда проверять, что хеш пришел именно тот, что послали?
                                          Пересылка в обратную сторону подвержена тем же ошибкам: в хеше может нехватать некоторого количества бит и некоторые биты могут быть «сломаны».
                                            0
                                            0) использовать небольшой хеш
                                            1) повторить передачу блока с сигналом о повторе
                                              –1
                                              upd: В простейшем случае даже бит четности может оказаться поврежден, приходится запрашивать повторную посылку. (пардон, не освоился с интерфейсом сайта)
                                                0
                                                Может слать его в том же сообщении, повторяющимся более заданного количества раз?
                                                [msg][hash][hash][hash]
                                                
                                              +1
                                              Сразу видно, не держал автор фидоноду на древесно-шаговой АТС, не мечтал о «Русском Курьере» или хотя бы о V32.bis…
                                                +1

                                                Декадно-шаговой

                                                  0
                                                  Конечно, декадно-. Но в узких кругах её называли древесно-. Ввиду её архаичности.
                                                0
                                                Как идея: а почему бы не договориться слать данные пакетами только по X байт?

                                                Если пришло меньше — значит, биты были потеряны. Дополняем до X спереди, спереди и сзади или сзади (по очереди). Результат прогоняем через декодировщик Рида-Соломона, который рассчитан на коррецию (n+m) ошибок, где n — число бит, которые могут быть потеряны, а m — число возможных инверций бита.
                                                  0

                                                  Да, сообщения фиксированной длины это верный путь, сам выбирал такой. Несколько напрягает только переотправка, так как запрос о переотправке может потеряться. И тогда, когда приходит еще один пакет, непонятно, переотправленный это пакет, или новый?

                                                  0

                                                  Я не понял, почему нельзя просто взять и сделать TCP?

                                                    0

                                                    Обновил до версии 0.1.4, добавил свой вариант решения. Не ахти что по оверхеду — в среднем 520% для больших данных. Однако целостность поддерживается надежно, BER примерно 3e-7.

                                                      0
                                                      Добавлю, что в физических каналах, помимо всего прочего могут еще добавляться паразитные биты :)
                                                        0

                                                        Сохраню здесь ещё полезные ссылки:


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

                                                        Самое читаемое