Помехоустойчивое кодирование с иcпользованием различных кодов

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

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

    Когда мы передаем сообщение от источника к приемнику, при передаче данных может произойти ошибка (помехи, неисправность оборудования и пр.). Чтобы обнаружить и исправить ошибку, применяют помехоустойчивое кодирование, т.е. кодируют сообщение таким образом, чтобы принимающая сторона знала, произошла ошибка или нет, и при могла исправить ошибки в случае их возникновения.

    По сути, кодирование — это добавление к исходной информации дополнительной, проверочной, информации. Для кодирования на передающей стороне используются кодер, а на принимающей стороне — используют декодер для получения исходного сообщения.
    Избыточность кода — это количество проверочной информации в сообщении. Рассчитывается она по формуле:
    k/(i+k), где
    k — количество проверочных бит,
    i — количество информационных бит.
    Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит — избыточность составит 1/(3+1) = 1/4 (25%).

    Код с проверкой на четность


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

    В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно . Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.
    Ниже показана структурная схемы кодера для данного кода

    и и декодера


    Пример:
    Начальные данные: 1111
    Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
    Принятые данные: 10110 (изменился второй бит)
    Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка.

    Как говорилось ранее, этот метод служит только для определения одиночной ошибки. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным. В этом случае система не определит ошибку, а это не есть хорошо. К примеру:
    Начальные данные: 1111
    Данные после кодирования: 11110 ( 1 + 1 + 1 + 1 = 0 (mod 2) )
    Принятые данные: 10010 (изменились 2 и 3 биты)
    В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку.

    Так как около 90% всех нерегулярных ошибок происходит именно с одиночным разрядом, проверки четности бывает достаточно для большинства ситуаций.

    Код Хэмминга


    Как говорилось в предыдущей части, очень много для помехоустойчивого кодирования сделал Ричард Хэмминг. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит. Для каждого числа проверочных символов используется специальная маркировка вида (k, i), где k — количество символов в сообщении, i — количество информационных символов в сообщении. Например, существуют коды (7, 4), (15, 11), (31, 26). Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 — это код (7,4), количество проверочных символов равно 3. Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания:
    первый проверочный бит на 20 = 1;
    второй проверочный бит на 21 = 2;
    третий проверочный бит на 22 = 4;

    но можно и разместить их в конце передаваемого блока данных (но тогда формула для их расчета будет другая).
    Теперь рассчитаем эти проверочные символы:
    r1 = i1 + i2 + i4
    r2 = i1 + i3 + i4
    r3 = i2 + i3 + i4

    Итак, в закодированном сообщении у нас получится следующее:
    r1 r2 i1 r3 i2 i3 i4

    В принципе, работа этого алгоритма разобрана очень детально в статье Код Хэмминга. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла. Вместо этого приведу структурную схему кодера:

    и декодера

    (может быть, довольно запутано, но лучше начертить не получилось)

    e0,e1,e2 опрделяются как функции, зависящие от принятых декодером бит k1 — k7:
    e0 = k1 + k3 + k5 + k7 mod 2
    e1 = k2 + k3 + k6 + k7 mod 2
    e2 = k4 + k5 + k6 + k7 mod 2

    Набор этих значений e2e1e0 есть двоичная запись позиции, где произошла ошибка при передаче данных. Декодер эти значения вычисляет, и если они все не равны 0 (то есть не получится 000), то исправляет ошибку.

    Коды-произведения


    В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями (при цифровой видеозаписи). При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой. Для возможности борьбы с такими ошибками используются коды-произведения. Принцип действия такого кода изображён на рисунке:

    Передаваемая информация кодируется дважды: во внешнем и внутреннем кодерах. Между ними устанавливается буфер, работа которого показана на рисунке:

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

    При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда-нибудь. Условимся, что и внутренний, и внешний коды – коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове (количество «кубиков» на рисунке не критично — это просто схема). На приемном конце расположен точно такой же массив памяти (буфер), в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки (крестики на рисунке в третьей и четвертой строках), она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена.

    Назначение внешнего кода понятно – исправление пакетных ошибок. Зачем же нужен внутренний код? На рисунке, кроме пакетной, показана одиночная ошибка (четвертый столбец, верхняя строка). В кодовом слове, расположенном в четвертом столбце — две ошибки, и они не могут быть исправлены, т.к. внешний код рассчитан на исправление одной ошибки. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки.

    Использование кодов-произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности.

    P.S.: Плотно занимался этой темой 3 года назад, когда писал дипломный проект, возможно что-то упустил. Все исправления, замечания, пожелания — пожалуйста через личные сообщения
    Поделиться публикацией

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

      +3
      Прочитал сначала «Похмелеустойчивое кодирование...». Извините.
        0
        Это была бы таки бесценная информация
        0
        сие уже нигде не используется, продолжая тему напишите пожалуйста о БЧХ, сверточных кодах, турбо-кодах, ну или хотя бы о LDPC
          0
          На самом деле, об этом я сейчас и не вспомню в подробностях. Будет время — постараюсь написать, хотя в той же википедии довольно много информации.
          Да, на самом деле сейчас все гораздо сложнее, исплозуются другие коды, но с этими проще разобраться не подготовленному человеку.
            0
            Разве коды Хемминга не используются в Ethernet?
            А Ethernet он не то чтоб «не нигде», он везде.
              0
              в старых стандартах да, в новых — нет
                0
                Можно подробнее?
                0
                Как пишут в википедии, код Хэмминга используют часто при работе с памятью. Вроде бы раньше исполльзовали еще в пейджинговой связи. Коды Рида-Соломона и коды-перемежения использовали в спутниковой связи (что используют сейчас не в курсе, к сожалению, но не думаю, что поменялось очень сильно).
                В Ethernet вроде бы используют немного другой принцип кодирования, основанный на проверке четности — вычисляются паритетные биты, блок передается, если данные не верны, блок передается еще раз. И так пока все данные не передадутся
                  0
                  В Ethernet использовался код Хемминга, это, как говорится, «инфа 100%».

                  Здесь выше мне отписали по поводу новых стандартов, (и через Л.С. указали подробности — «в новых стандартах 10Г, 40Г, 100Г перешли к более сложному кодированию, где декодирвоание итеративное — eehpc.csee.umbc.edu/docs/Poster1.pdf ), но я таки буду настаивать что коды Хэмминга пока-еще много где, ибо за гигабитный Эзернет еще далеко не все шагнули.
                    0
                    Ок, тогда я что-то путаю, скорее всего. Просто на олимпиаде в 2008 году было задание реализовать такой алгоритм (передача данных блоками, с проверкой четности, вроде). Как потом сказал преподаватель, это используется в сети Ethernet. Но, опять же, скорее всего я перепутал, возможно, он и не Ethernet говорил :) Надо бы уточнить
                      0
                      Так одно другому не мешает — там может быть CRC а потом и parity flag добавлятся.
                        0
                        P.S. Плюс не известно о какой версии Ethernet речь — может в самых первых версиях CRC не было а была только проверка чётности.
                          0
                          Да, вполне возможно, что это было реализовано лишь в первых версиях стандарта, а потом было выпилено / заменено
                            0
                            Нашёл подтверждение первой версии — биты чётности и CRC используются вместе в Gigabit Ethernet:
                            www.knowledgetransfer.net/dictionary/Storage/en/8b10b_encoding.htm
                            «8b/10b encoding is used in transmitting data on Fibre Channel, ESCON, and Gigabit Ethernet»
                            «The Cyclic Redundancy Check (CRC) or checksum, further assists error detection. As a result, there are fewer retransmissions than would be the case if relying on CRC or parity alone.»
                    0
                    нету кодов-перемежения. В DVB-S использовали Рида-Соломона, после которого стоял перемежитель (interleaver), потом шел сверточный кодер с перфорацией. В DVB-S2 от этого отказались
                      0
                      И в DVB-S, и в DVB-S2 используется внутреннее и внешнее кодирование, только коды разные. В DVB-S код Хэмминга + сверточное кодирование, в DVB-S2 — код Боуза-Чоудхури-Хоквингема и LDPC.
                        0
                        это не противоречит тому, что я писал) В жигулях есть передние и задние сидения, в бентли есть передние и задние сидения, только это две большие разницы.
                          0
                          Да, это я просто уточнял, может быть кто-то мог не так понять, что в DVB-S2 вообще все по-другому )
                0
                Коды Баркера еще интереснее.
                За счет своей структуры и избыточности позволяют передавать с боЛьшей скоростью при бОльшей надежности приема.

                Применяются много где, у меня, в частности, в автосигнализации такое.
                Очень было интересно, когда глушилка рядом работала — народ на стоянке ничего с машиной сделать не может, а у меня и снимаентся и ставится (правда, противоразбойная карточка все же заглючила — там обычное кодирование).
                0
                Вообще, тема кодирования, на самом деле, очень интересная. На этих выходных в Питере были лекции по кодированию информации, на которые любой мог сходить абсолютно бесплатно (было в разделе «События»). К сожалению, не смог сходить, но очень интересно, о чем там рассказывали. Кто-нибудь был из пользователей Хабра на них?
                  0
                  Я, пользуясь случаем, спрошу у ТСа. Какие коды вы считаете наиболее оптимальными для кодирования информации, передаваемой по последовательному каналу с размером слова в 16 бит с частотой порядка 10МГц.
                    0
                    Честно говоря, даже не знаю… Кодированием информации, как уже говорил, занимался 3 года назад, поэтому знаний особых не осталось. Практически, все что хорошо помню — написал в статье. Но в ближайшее время хочу плотно заняться данной темой, так что в будущем постараюсь рассмотреть уже на практике различные коды — что, где и когда использовать.
                      0
                      Термин «оптимальный» вообще не применимо к теории кодирования и связи, лучше этим словом не пользоваться. Кодирование может быть «лучше» по какому-то критерию, относительно других способов, но однозначно так говорить нельзя. Если говорить о «лучших» кодах с точки зрения минимальной вероятности битовой ошибки при заданном отношении энергии бита к спектральной плотности мощности, то тут лучше проявляют себя турбо-коды и LDPC с мягким декодированием. Это коды из серии «легко закодировать, фиг декодируешь», т.е. с большими вычислительными затратами и, главное, итеративные. Если нужно что-нибудь простенькое и канал хороший, то тут циклические коды хороши. Сверточные коды тоже достаточно сложно декодировать, но благодаря им можно получить относительно малую избыточность кода, при этом они хорошо подходят под модуляцию nPSK модуляцию. Тут же можно вспомнить и о каскадных кодах. Да можно много чего вспомнить.
                      Но повторюсь: все зависит от вероятности ошибки и отношения Eb/N0. Отталкиваясь от него, не забывая про модуляцию, Вы можете сами прикинуть «взлетит» такое кодирование или все испортит. В Матлабе есть тулбокс bertool, поиграйте с ним
                        0
                        Вы не могли бы посоветовать почитать что-нибудь по поводу кодирования для новичков?) Просто я из вашего объяснения не понял почти ничего, поэтому хоть как-то адекватно ответить то не могу. Меня интересуют коды для последовательного канала, для проверки целостности данных(даже самокоррекция не нужна по-большому счету). Просто реализация этого кода будет осуществляться на уровне триггеров и комб. логики, что накладывает существенные ограничения на сложность кодирования.
                          0
                          Ну основы основ:
                          Морелос-Сарагоса «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение»
                          Прокис Дж. «Цифровая связь»
                          Вернер «Основы кодирования»

                          Начните с последнего. Там даже схемки на уровне триггеров есть
                            0
                            Благодарю!

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

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