Алгоритм Чейза

Пролог


Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга, она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь.

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

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


Немного теории


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

Декодирование блокового кода может быть осуществлено посредством жёсткого или мягкого принятия решения. В декодировании с жёстким принятием решения, каждому принимаемому биту в демодуляторе приписывается значение
0 или 1. Декодер с мягким принятием решения принимает не только бинарную величину 1 или 0, но также доверительную величину, связанную с заданным битом. Декодер будет использовать эту мягкую информацию, и на выходе мы получим такое же жёсткое решение.
Если кратко, то на вход жесткого декодера, из канала, поступает вектор из значение 0 или 1. На вход мягкого декодера поступает вектор из значений (-∞; +∞). Использование мягких решений даёт больше возможностей, так как предоставляет более широкий маневр по исправлению возникающих помех.
Алгоритм Чейза — блоковый код с мягким решением.


Алгоритм Чейза


Алгоритм Чейза — это понятный и относительно эффективный алгоритм исправления ошибок(помех) в передаваемом сообщение. Главной идеей алгоритма является генерирование массива кодовых слов, которые будет содержать слово, ближайшее к принятой последовательности. Алгоритм основан на том, что если слово, декодированное обычным жёстким решением содержит ошибку, то одно из «ближайших» к нему кодовых слов скорее всего совпадает с переданным.


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


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

1. Пусть у нас есть исходный вектор u = [1, 0, 0, 1];


2. Кодируем его по алгоритму Хэмминга и получим с = [1, 0, 0, 1, 1, 0, 0];


3. Добавляем проверку чётности — с[8] = ∑с mod 2. Стоит отметить, что для данных целей удобно использовать расширенный код Хэмминга. Но о нём лучше отдельно.
В итоге получаем с = [1, 0, 0, 1, 1, 0, 0, 1].


4. Вносим некоторые помехи и получаем вектор r = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, -0.73, 1.97].


5. Мы используем второй алгоритм Чейза. Он характеризуется следующим методом генерирования массива проверочных кодовых слов:

  • Выбрать из принятого вектора r p наименее надёжных бит, то есть p бит наименьших по модулю. Последний бит в векторе в расчёт не принимается, так как он проверяет чётность и может быть вычислен на основание прочих бит;
  • Выбрать число v =< p;
  • Сгенерировать массив вспомогательных векторов h. Состоящий из векторов длинной p, со всевозможной комбинаций битов со значением 1, количество которых в одном векторе должно быть не больше v, и битов со значением 0 на остальных позициях (см. пример ниже);
  • Сгенерировать массив проверочных векторов e. По следующим правилам:
    • Каждый вектор должен быть на один бит короче вектора r;
    • Массив векторов должен быть такой же длины, как и массив вспомогательных векторов, сгенерированный, на предыдущем шаге;
    • Каждый вектор должен состоять из нулевых бит, кроме позиций наименее надежных бит, выбранных на первом шаге. На данных позициях должны располагаться биты из массива вспомогательных векторов h.


Теперь сгенерируем проверочные вектора на примере нашего вектора r = [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97].
  • Пусть p = 3, тогда позиции наименее надежных бит — [1, 5, 7] (нумеруем начиная с индекса 1), [-1.02, -1.1, -2, 1.95, 0.98, -2.34, 0.73, 1.97];
  • Пусть v = 2;
  • Сгенерируем массив вспомогательных векторов h:
    h[1] = [0, 0, 0],
    h[2] = [0, 0, 1],
    h[3] = [0, 1, 0],
    h[4] = [0, 1, 1],
    h[5] = [1, 0, 0],
    h[6] = [1, 0, 1],
    h[7] = [1, 1, 0];
  • Сгенерируем массив проверочных символов e:
    e[1] = [0, 0, 0, 0, 0, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[1] на позициях 0, 1 и 2 соответственно,
    e[2] = [0, 0, 0, 0, 0, 0, 1], используем на позициях 1, 5 и 7 элементы из вектора h[2] на позициях 0, 1 и 2 соответственно,
    e[3] = [0, 0, 0, 0, 1, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[3] на позициях 0, 1 и 2 соответственно,
    e[4] = [0, 0, 0, 0, 1, 0, 1], используем на позициях 1, 5 и 7 элементы из вектора h[4] на позициях 0, 1 и 2 соответственно,
    e[5] = [1, 0, 0, 0, 0, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[5] на позициях 0, 1 и 2 соответственно,
    e[6] = [1, 0, 0, 0, 0, 0, 1], используем на позициях 1, 5 и 7 элементы из вектора h[6] на позициях 0, 1 и 2 соответственно,
    e[7] = [1, 0, 0, 0, 1, 0, 0], используем на позициях 1, 5 и 7 элементы из вектора h[7] на позициях 0, 1 и 2 соответственно;


6. Проводим демодуляцию вектора r и получаем вектор y. y[i] = r[i] > 0, то 1, иначе 0; И отбрасываем последний бит.
y = [0, 0, 0, 1, 1, 0, 1].


7. Генерируем массив пробных последовательностей t. t[i] = y ⊕ e[i].
Получаем:
t[1] = [0, 0, 0, 1, 1, 0, 1] — y ⊕ e[1],
t[2] = [0, 0, 0, 1, 1, 0, 0] — y ⊕ e[2],
t[3] = [0, 0, 0, 1, 0, 0, 1] — y ⊕ e[3],
t[4] = [0, 0, 0, 1, 0, 0, 0] — y ⊕ e[4],
t[5] = [1, 0, 0, 1, 1, 0, 1] — y ⊕ e[5],
t[6] = [1, 0, 0, 1, 1, 0, 0] — y ⊕ e[6],
t[7] = [1, 0, 0, 1, 0, 0, 1] — y ⊕ e[7];

Это позволяет нам проверить наименее надежные биты. А именно, проинвертировать их, в зависимости от значений вектора e[i] и далее выбрать то значение, которое нам больше будет подходить(см. следующие шаги).
Надежные биты данными операциями затронуты не будут.
Если бы мы использовали только жесткие решения, то не могли бы сделать вывод о том какие биты наименее надежны и проверить их.


8. Применяем к t[i] жесткое решение (в данном случаем алгоритм Хэмминга), но оставляем проверочные символы, и получаем массив векторов s:
s[1] = [0, 0, 0, 1, 1, 1, 1], жесткое решение для t[1],
s[2] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[2],
s[3] = [0, 0, 1, 1, 0, 0, 1], жесткое решение для t[3],
s[4] = [0, 0, 0, 0, 0, 0, 0], жесткое решение для t[4],
s[5] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[5],
s[6] = [1, 0, 0, 1, 1, 0, 0], жесткое решение для t[6],
s[7] = [1, 1, 0, 1, 0, 0, 1], жесткое решение для t[7];


9. Добавляем векторам s[i] проверку на чётность:
s[1] = [0, 0, 0, 1, 1, 1, 1, 0],
s[2] = [1, 0, 0, 1, 1, 0, 0, 1],
s[3] = [0, 0, 1, 1, 0, 0, 1, 1],
s[4] = [0, 0, 0, 0, 0, 0, 0, 0],
s[5] = [1, 0, 0, 1, 1, 0, 0, 1],
s[6] = [1, 0, 0, 1, 1, 0, 0, 1],
s[7] = [1, 1, 0, 1, 0, 0, 1, 0];


10. Проведём модуляцию значений векторов из массива s. По формуле s[i][j] = 2 * s[i][j] — 1:
s[1] = [-1, -1, -1, 1, 1, 1, 1, -1],
s[2] = [1, -1, -1, 1, 1, -1, -1, 1],
s[3] = [-1, -1, 1, 1, -1, -1, 1, 1],
s[4] = [-1, -1, -1, -1, -1, -1, -1, -1],
s[5] = [1, -1, -1, 1, 1, -1, -1, 1],
s[6] = [1, -1, -1, 1, 1, -1, -1, 1],
s[7] = [1, 1, -1, 1, -1, -1, 1, -1];


11. Найдём ближайший к вектору r, вектор из массива s. Используя в качестве метрики евклидово расстояние.
evkl(s[1], r) = 21.96, для s[1]
evkl(s[2], r) = 11.72, для s[2]
evkl(s[3], r) = 16.64, для s[3]
evkl(s[4], r) = 27.24, для s[4]
evkl(s[5], r) = 11.72, для s[5]
evkl(s[6], r) = 11.72, для s[6]
evkl(s[7], r) = 25.00, для s[7]

У нас получилось несколько одинаковых метрик. Выбрать мы можем любой из векторов s. Давайте выберем первый их них, то есть s[2] = [1, -1, -1, 1, 1, -1, -1, 1].


12. Проведём демодуляцию s[2] и получим вектор res. res[i] = s[2][i] > 0, то 1, иначе 0.
res = [1, 0, 0, 1, 1, 0, 0, 1].


13. Отбросим у вектора res проверочные символы и получим оригинальный вектор u = [1, 0, 0, 1], который и требовалось передать.


О помехах


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


Эпилог


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


Литература

По данной теме советую — «Кодирование с исправлением ошибок в системах цифровой связи. Дж. Кларк, Дж. Кейн».

Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 20

    0
    Было бы полезно, на мой взгляд, указать информацию о том какие типы ошибки может исправить и какие детектировать? Тот же код Хэмминга однократные фиксит, а двукратные обнаруживает
      +1
      Про Чейза говорить о гарантированном числе исправляемых ошибок нельзя. Все зависит от веса ошибок. Вес ошибок зависит от уровня шума в канале передачи данных. Об этом постараюсь рассказать в ближайшем топике. Если чуть забегать вперёд и говорить терминами, не описанным в данной статье, то при уровне отношения сигнал/шум 9, без проблем можно получить всего один ошибочный бит на 10 000 000 переданных, т.е. вероятность ошибки 10^-7. Надеюсь не очень мудрёно ответил)
      0
      А меня вот наоборот статья о кодах Хэмминга, приведенная вами, в свое время сбила с правильного направления. Разбирались как раз недавно с блоками памяти, собранных на микросхемах 556РТ7. Так вот там используются еще и микросхемы 553ВЖ1, именно для проверки и корректирования 24-разрядной шины данных. В них используется модифицированный код Хэмминга.
      На 24 разряда идут 6 разрядов Хэмминга и высчитываются по своему алгоритму, я так понял специально адаптированному под схемотехнику.
        0
        Ну приведённая статья скорей наглядна. Показывает на пальцах сам принцип исправление ошибок. Вообще классическое описание Хэмминга немного отличается.
        По поводу шин — скорей всего алгоритм был адаптирован, конечно. При m = 5 (число проверочных символов), длинна кодового слова для Хэмминга была бы n = 2^m — 1 = 31 из которых k = 2^m — m — 1 = 26 были бы информационными, а 5 проверочными. Уменьшение кол-ва информационных символов и увеличения проверочных скорей всего было нужно для просчёта каких то специфических для схемы значений, типа чётности в данной статье. но точно сказать трудно.
          0
          Ну, если не придираться к формулировкам, то соглашусь. Никаких специфичных значений. Микрухи исправляют однократную ошибку и индицируют двукратную. Документацию на аналог можно почитать: SN74LS630. За мелкими исключениями таблицу синдромов микросхемы идентичны.
        0
        Да, интересно. Пишите про Витерби. Уже была статья, но хотелось бы еще.
          0
          … Что-то сложно… Про алгоритм Чейза ни разу не слышал… Это что, табличное декодирование по минимуму расстояния? И всё-таки, «жёсткий» или «мягкий» декодер? И почему помехи искажают вектор из нулей и единиц в дробные числа?.. Что-то я вообще в ауте, хотя преподаю кодирование…
          Придётся что-нибудь написать :).
            +1
            С табличным декодированием признаться сам не сталкивался. Но относительно алгоритма Чейза такого термина ни разу не встречал, так что думаю что это не оно.

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

            Я писал, что искажение заслуживает отдельной статьи. Но вопрос справедливый.

            В комменте ответить сложно. Постараюсь на пальцах. Надеюсь никто не обидится и не заклеймит меня. Это просто для понимания
            Когда мы передаём бит в канал, он превращается в сигал (это всем ясно). Грубо говоря 0, это отсутствие сигнала, а один наличие сигнала, определённой амплитуды. Но вот появляется шум. Он добавляет/отнимает какую свою амплитуду от сигналу. Жесткий демудулятор тупо сравнит с 0.5 и значение принятое из канала. Если < 0.5 то 0, иначе 1. Но на сколько было отклонение не понятно. 0.49 и 0.51 очень близки, но в «жесткую» превратятся в 0 и 1 соответственно. Мягкий декодер изучит наименее «надёжные» биты, которые ближе к половине амплитуда — в данном случае 0.5 (в топике был 0) и рассмотрит какое решение ему ближе с 1 на данной позиции или 0 и возьмёт лучшее.
            Надеюсь не запутал ещё больше. Тут для хорошего примера пару графиков нужно. Вообщем статья и мини-приложение с примером за мной.
              0
              Прошу заранее прощения за возможно глупый вопрос, но не задать не могу, очень хочется знать ;)
              Какого размера в байтах должны быть данными чтобы испорченный один бит можно было восстановить?
                0
                Количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство: 2^k >= k + m + 1,
                где m — количество основных двоичных разрядов кодового слова.
                  0
                  Один испорченный бит гарантировано исправляется даже алгоритмом Хэмминга. Так что при ситуации, когда сильно искажается один из бит вы получите 100% исправление ошибки, при любой длине кода.

                  Если говорить об общем случае, то Чейз эффективен к относительное коротким блокам. В моделирование при длине кодового слова = 31 (m = 5), при p = v = 3 и отношение сигнал/шум = 7. получал ошибку 10^-6, т.е. 1 на 1 000 000 бит. Если память не изменяет. при m = 7 результаты были даже получше. Дальше m = 10 не совался, потому что уже начинает ресурсов не хватать. нужно компьютер обновлять)
                    0
                    Хочу применить восстановление битов в своем протекторе исполняемых файлов. Другими словами я хочу сознательно портить код, так чтобы его читать было невозможно, а в последствии восстанавливать. Основной страх, т.к. еще не проверял, это боюсь что можно будет испортить только 1 бит на очень большой кусок кода. Мне же надо хотя бы на 10-20% куска кода. Вообщем мне хочется управлять степенью восстановления
                      0
                      хочется управлять степенью восстановления

                      то есть Вы имели ввиду «управлять степенью порчи»? Так тогда можно сознательно портить один символ на слово, два символа на слово, три и тому подобное. Код выбирать таким, чтобы он 100% восстанавливал однократную, двукратную, трёхкратную ошибки и так далее согласно степени порчи. Под символом можете понимать байт, два байта… в общем, всё, что покажется удобным. Позиция ошибки в слове будет случайной, но код её всё равно исправит, так как ему важна лишь кратность ошибки.
                        0
                        Да, Вы точнее сформулировал чем я. Действительно имел ввиду «степень порчи». Просто пока мне известны код Хэмминга, слышал о Рид-Соломона, но глубоких познаний нет. Только начал копать эту тему. Пока мое понимание, возможно не правильное, что ошибка может быть только один бит на на 1000 у более байтов. Мне хочется не слишком много доп. информации добавить, но при этом достаточно хорошо попортить данные )
                          0
                          Например, у двоичного кода Хэмминга, исправляющего все однократные ошибки, количество проверочных битов r и длина выходного кодового слова n связаны как n = 2^r — 1, так как количество ненулевых r-разрядных двоичных комбинаций как раз-таки и равно этому числу. То есть возможен ряд (n,k)-кодов (3,1), (7, 4), (15,11)… где k — количество информационных битов.

                          Для порчи следует применять несистематические коды, когда кодовое слово не делится на два блока, типа «ИИИИППП», где И — информационные символы, П — проверочные (контрольные). Иначе можно легко заметить закономерность.

                          Если требуется вводить две, три и более ошибок на слово, то можно посмотреть в сторону кодов Боуза-Чоудхури-Хоквингема.

                          А, вообще, странно защищать информацию избыточными кодами…
                            0
                            Ну странно вообще применять теорию обфускации после компиляторов ;))) Одни инженеры пишут как бы написать оптимизатор в компиляторе так чтобы было хорошо по скорости и памяти. А другие инженеры пишут так чтобы добавить больше кода для усложнения reverse-engineering, тем самым сводят на нет усилия оптимизатора в компиляторе.
                            Я просто ищу новые пути защиты, которые можно применить в моем протекторе ;)
                        0
                        У меня руководитель писал подобное приложение. Для демонстрации возможностей, перед продажей. Я его тыкал, но само кодирование не трогал. По мелочи кое что изменял.

                        Файл в качестве примера был аудио. Это очень наглядно, потому что можно воспроизвести несколько раз и сравнить — в начале, после внесения помех и после восстановления.

                        Там кстати использовался код Рида-Соломона. Код очень шустрый и эффективный, но не простой в реализации.

                        Могу дать совет — с такими вещами надо быть осторожными. Потому что если запишется ошибка в хедер файла, то вообще ничего может не воспроизвестись, не смотря на хорошие результаты работы алгоритма. Так что мы просто хедер мы передавали отдельно. Быстрое и сердитое решение)))))) но это был пример работы а не прод… так что посмотрите и уточните, есть ли в вашем файле критичные секции.
                    0
                    Ладно с табличным декодированием, видимо терминология разная. Это самый примитивный способ декодирования, но и самый трудоёмкий (перебираем всю кодовую таблицу и считаем расстояния между принятым словом и всеми разрешёнными словами, затем выбираем то кодовое слово, которое ближе всего к принятому).

                    По-поводу «жёсткости». Демодулятор работает в мягком режиме и поэтому на вход декодера уже поступают не двузначные символы (биты), а многозначные (3, 4, 5… как правило, более восьми нет смысла делать). Ладно. Декодер всё-таки должен работать в жёстком режиме (на выходе имеется ввиду), так как потребителю, в конечном счёте, нужны биты. Из-за этого у меня путаница и возникла. По сути, демодулятор по принятому импульсу вычисляет число (уровень напряжения) и смотрит в какой интервал оно попало. Чем дальше от центра, тем более достоверным будет результат (в случае передачи битов). Насколько я помню, если область выходных значений демодулятора делится на три интервала (минимальная степень мягкости), то на вход декодера приходят биты 0 и 1 и так называемый стёртый символ (его можно обозначить как X). Линейные блочные коды (тем более и циклические) могут восстанавливать стёртые символы, причём на это требуется столько же ресурсов, сколько и на обнаружение. В этом-то и есть «фишка» мягкого режима, причём есть ещё плюс: с точки зрения теории информации декодеру будет поступать больше информации, чем при жёсткой демодуляции. С этих позиций чем отличается алгоритм Чейзера? Количеством интервалов (то есть там будут стёртые символы X1, X2, Xm)?
                      +1
                      По поводу терминологии «мягкости». Чаще всего речь идёт именно о входных значениях. Когда говорят «Hard decision decoder» или «Soft decision decoder» имеются в виду входные значения. А вот когда речь идёт о выходных значениях, используют другой термин: soft output или hard output. Тот же SOVA — Soft Output Viterbi Algorithm. Хотя, обычно в таких случаях упоминаются и входные данные — Soft Input Soft Output.
                        +1
                        Как всё-таки лаконичен английский для технических приложений — коротко и ясно.

                Only users with full accounts can post comments. Log in, please.