Пороговый декодер

    Друзья, всем привет!

    Пару месяцев назад, я уже начал рассказывать про методы помехоустойчивого кодирования. Первая статья была посвящена алгоритму Чейза. Она вот тут. Многих заинтересовало данное направление, поэтому я решил продолжить. На очереди весьма любопытный, перспективный, и что важно простой для понимания пороговый декодер. Давайте начнём!

    Как работает


    Пороговый декодер предоставляет чрезвычайно простое декодирование, основанное на принципе «голосования по большинству».
    Кодер представляет собой регистр-очередь, заполненными битами вектора, который необходимо закодировать. Обработка начинается с нулевой ячейки. Для бита находящегося в нулевой ячейки вычисляются необходимые характеристики, а вышедший из очереди бит перемещается в конец очереди, в двенадцатую ячейку, и может быть использован для вычисления необходимых данных для бита, находящегося в нулевой ячейки. Механизм кодирования будет работать до тех пор, пока в нулевой ячейки не побывают все биты, исходного вектора. Перед кодером расположен ключ, у которого есть два положения. В первом положение ключ пропускает биты из канала в регистр, пока регистр не будет заполнен полностью. После того как регистр заполнен, ключ переводится в состояние два, начинается кодирование и в нулевую ячейку попадают биты из последней(12-ой) ячейки регистра, после вычисления необходимых для них характеристик.
    image

    Можно сказать, что представленный кодер, задан с помощью «образующего полинома» g(x)=1+ x+x^4+x^6.
    Таким образом, с процессе кодирования будет получены две части зашифрованного сообщения, которые в последствие будут объединены и переданы в канал, как единый вектор. Первая — информационная (u) будет содержать биты, исходного сообщения, переданные на прямую из нулевой ячейки регистра, кодируемого сообщения. Вторая – проверочная (v) будет содержать биты полученные путем сложения бит из ячеек регистра с индексами, соответствующим ненулевым степеням «образующего полинома» g(x).

    Пример работы кодера


    Пусть нам нужно зашифровать следующее сообщение: 0111011011011. Информационная ветвь (u) будет полностью соответствовать исходному сообщению, т.е. будет равна «1101101101110».
    Проверочная ветвь (v) будет состоять из бит полученных за счёт сложения «по модулю два» бит, из 0-ой, 1-ой, 4-ой и 6-ой ячеек регистра.
    Пример:
    1. В регистре: 1 0 1 1 1 0 1 1 0 1 1 0 1
    V = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1;
    2. В регистре: 1 1 0 1 1 1 0 1 1 0 1 1 0
    V = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1;
    ......
    13. В регистре: 0 1 1 1 0 0 1 0 1 1 0 1 1
    V = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0;
    После «круга» работы кодера, проверочная часть будет представлять собой вектор: «111000000010».
    Следовательно, в канал будет отправлен вектор «10111011011011110000000010».

    Стоит отметить что формат вектора [ u | v ] не является единственно верным. И может быть с легкостью заменен на любой другой формат, к примеру: [u1 | v1 | u2 | v2…un | vn].

    Работа декодера


    Рассмотрим работу порогового декодера. На первом шаге работы декодера, с помощью входящего в его состав кодера, вычисляются проверочные биты, для принятых из канала информационных битов ветви u, складывается «по модулю два» с принятыми проверочными битами из ветви v. В результате в синдромном регистре сформируется синдром, который указывает на наличие ошибок. Перед регистром кодера в декодере расположен ключ, который работает аналогично ключу в кодере. В первом положение он «впускают» биты из канала в кодер, а после начала декодирования пускают в нулевую ячейку бит, пришедший из двенадцатой ячейки регистра кодера. Ключ перед синдромным регистром работает аналогично. Единственное отличие в том, что в первом состояние он пропускает в регистр биты не сразу из канала, а с сумматора, расположенного перед ключом.
    image
    После заполнения синдромного регистра осуществляется декодирование информационного символа из 0-ой ячейки, для чего в пороговом элементе (ПЭ) осуществляется сравнение суммы элементов синдромного регистра, соответствующих декодируемому символу. В случае, если сумма окажется больше порога, выход ПЭ устанавливается равным 1, что приводит к изменению информационного символа и связанных с ним проверок. В противном случае ПЭ будет 0.
    Рассмотренный декодер является декодером с обратной связью, так как исправление в информационном регистре ошибка за счёт обратной связи удаляется и из синдромного регистра.
    Пусть в исходное сообщение «10111011011011110000000010» будет внесена ошибка «1011111101101 1110000000010».
    Синдромный регистр будет содержать следующие значения: «00000011001010» (самый первый бит — ячейка «0» синдромного регистра на картинке)
    1. В синдромном регистре: «0000011001010» → «0000011001010»
    В пороге: 1, 1 < 2 → изменений нет. В результат идёт значение «1»;
    2. В синдромном регистре: «0000110010100» → «0000110010100»
    В пороге 1, 1 <2 → изменений нет. В результат идёт значение «1»;
    ......
    6 В синдромном регистре: «1100101000000» → «0000000000000».
    В пороге 4, 4 > 2 → изменение есть. В результат идёт значение «0», вносятся изменения в синдром;
    В результате после декодирования мы получим сообщение «1 1 0 1 1 0 1 1 0 1 1 1 0». Ошибка была исправлена. И после инверсии позиций всех бит мы получим исходное сообщение «0 1 1 1 0 1 1 0 1 1 0 1 1».

    Эпилог


    Пороговый декодер является удачным сочетанием простоты реализации, эффективности и скорости работы. Его развитием является многопороговый декодер. Рассказать о котором попробую в ближайшее время.
    Спасибо, всем кто прочёл. Буду рад конструктивным замечаниям/комментариям. Старался быть доходчивым :)
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 25
    • +6
      Пусть нам нужно зашифровать следующее сообщение

      Закодировать?
      • –5
        Да, все верно. Синонимичные понятия.
        • +8
          Неверно. Кодируют с целью передать информацию более надежно — шифруют же с целью защитить ее от перехвата. Это принципиально разные вещи, которыми занимаются совершенно разные науки (теория информации и криптография) при помощи совершенно разных алгоритмов.
          • 0
            Да, кодирование направлено на повышение битовой скорости передачи при ограниченных ресурсах (мощность передатчика, полоса частот, динамический диапазон приёмника) и имеющихся помехах (статистика помех). Кодирование даёт выигрыш за счёт интеллекта.
            Можно кодированием и не заниматься, если есть возможность крутнуть ручку мощности передатчика и/или прибрать себе большую полосу частот (сила есть, ума не надо).
            Шифрование — это, по сути, наложение замка, ключ от которого только у законного абонента. На скорость передачи информации оно никак не влияет.
            Шифрованием также можно не заниматься, если есть «агент», который привезёт важную информацию «своим ходом» («агент» — имеется ввиду индивидуальная линия передачи). Медь есть — ума не надо :).
          • –1
            Отнюдь. Почитайте хотя бы википедию Кодирование и шифрование
            • +2
              В электронике это очень синонимические понятия. Зря что ли Шифратор и дешифратор так называются? Но с криптографией они никак не связаны.
              • –1
                Простите, а причем здесь шифратор? Тут нужен кодер и декодер.
                • +7
                  Шифратор здесь при том, что на самом деле он — кодер. Но исторически сложилось так, что его называют шифратором.
                  • –1
                    Можете называть его и историческим названием. Это ваше право. Правда от этого кодирование шифрованием не станет все равно.
              • +2
                С шифратором — так сложилось исторически. Но сейчас это разные понятия.
            • 0
              Наука не терпит синонимов.
              • 0
                Хе-хе.
                Абелева группа, она же коммутативная.
                Декартово произведение, оно же прямое.
                Линейное пространство, оно же векторное.
                Функция и отображение.

                И это только то, что я вспомнил за пять минут…
                • +1
                  Что поделаешь… Жизнь… Многие ведь наукой занимаются :)
                  Ладно хоть по два синонима. Но, если честно, они вносят кашу, особенно тем, кто учится.
                  Мне вот, например, не нравится говорить то «генераторная матрица», то «производящая» (есть ещё «порождающая», думаю, можно назвать «образующая», но это всё она, единственная).
                  Хороший термин «угол». Угол он и есть угол. Также и с другими областями науки должно быть. Градус он и есть градус. Ватт он и есть Ватт. И так далее.
                  Представьте, было бы: «Водород» (он же «Лёгкий газ», он же «Голубое топливо»), — ну какая это наука? Трёп.
                  • 0
                    к сожалению с градусом не так просто… он есть температурный (Кельвин, Цельсий, Фарангейт и прочее), как измерение угла, как смещение фаз электричества… думаю есть и другие градусы…
                    отсюда же пошло — в военное время прямой угол может достигать 100 градусов :)
                    • 0
                      Да, с градусом я промахнулся: надо вставлять прилагательное.
          • +1
            У Вас на рисунках на входе кодера есть две стрелочки, указывающие на жирную точку. Это что? Обратная связь? Может, там сумматор должен быть?
            Как называются такие коды? Ссылки на литературу (чем Вы руководствовались)?

            При шифровании размеры входных и выходных блоков равны, при помехоустойчивом кодировании размер выходного обязательно больше размера входного, а при сжатии (экономном кодировании) — теоретически должен быть меньше (практически — зависит от источника сообщения, от алгоритма сжатия).
            • 0
              1. точки это ключи. Сумматор обозначается как ⊕, на рисунке он тоже есть. Физический смысли ключей, в том что при начале кодирования/декодирования, через ключ проходит сообщение из канала и полностью заполняет регистр, а в процессе кодирования/декодирования происходит «транспортирование» бита из последней (13-ой) ячейки регистра в первую (с индексом 0).
              2. Данный код является блоковым. Если точнее то, это мажоритарно декодируемый код. Почитать про него можно в вики.
              3. В данном случае выходной блок бит в 2 раза больше входного, так как выходной будет формироваться в из проверочной и информационной части (u и v). И обе части будут необходимы при декодирование.
              4. Пользовался литературой не очень популярной — «Помехоустойчивое кодирование. Методы и Алгоритмы. Справочник». Золоторев, Овечкин. Писал мой руководитель в универе. Книжка не толстая, но ёмкая. Многие вопросы описаны очень вскользь По этому я и пытаюсь расшифровать их в более популярной форме. Если нужно то могу поискать в электронном виде.
              • +1
                Лучше бы вам статью отредактировать, пока еще можете, а не комментарии к ней писать. Понятнее, когда объяснение про ключи идет перед первым рисунком, а не в конце статьи.
                • 0
                  да, поправлю. спасибо за совет
                • 0
                  Хорошо.
                  Интересно, а куда отнести свёрточные коды, с которыми у меня сразу возникла ассоциация? А тут вдруг блоковые, а свёрточные — это не блоковые. Может, это циклический код тогда? Но нет, так как проверочные биты и информационные можно группировать как угодно. Если это просто линейный блочный код, то он мало где применяется. В свёрточных кодах также есть пороговое декодирование, почему у меня и возникли такие ассоциации.
                  • 0
                    Свёрточные коды будут кодировать/декодирвоать непрерывный поток бит, т.е. грубо говоря поступил бит в регистр, мы на основание его и соседних бит его закодировали и отправили в канал. пример Алгоритм Витерби. и так хоть миллион бит, всё непрерывным потоком. А в данном случае мы взяли блок бит, покрутили его, но покрутили всё тот же один единственный блок и закодировали его, потом этот же блок бит декодировали. Всё по блокам.
                    Пороговый декодер в чистом виде мало где используется. но на его основе интересен многопороговый декодер. над которым я сейчас работаю… может быть созрею для ещё одной статейки в ближайшее время :)
                    • 0
                      А можете генераторную матрицу рассмотренного кода привести, раз он блоковый? Просто линейные блочные коды в общем случае не могут быть заданы одним полиномом. Если уж можно одним — это циклический код.
                      Зачем мне надо генераторную матрицу? Я просто не могу классифицировать этот код.

                      Кстати, свёрточный код можно принудительно сделать блочным, обрезав его полубесконечную генераторную матрицу, что на практике и делается (всё-таки, информация передаётся пакетами, и в природе нет бесконечной последовательности битов).
                      • 0
                        Да конечно, сверточный делается искусственно «блоковым» — обрезается для просто реализации и исследования/моделирования, я тоже так делаю для Витерби к примеру. Бесконечность это теория.

                        • 0
                          В общем, это линейный блочный код (26, 13), заданный в систематической форме, если принять формат выхода [u, v]. Столбцы блока Q генераторной матрицы G=[I, Q] являются циклическими перестановками друг друга, что даёт минимальное количество ячеек памяти при реализации кодера (матрица I — диагональная, квадратная). Кодовое расстояние — пять. Кстати, если в полином добавить слагаемое x^11, то кодовое расстояние увеличится до шести. Полином должен выбираться так, чтобы дать максимум величины min( w(polynom), min_[i=1,2,...,12](w(polynom XOR circshift(polynom, i))) ), где w() — количество единиц в коэффициентах полинома polynom, circshift(p, i) — циклический сдвиг коэффициентов полинома p на i-разрядов. Тогда кодовое расстояние будет равно этому максимуму плюс один.
                          Итог: данный код является привлекательным для практического использования.

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

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