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

                                        G₁(x) = 1 + x + x²,                                           (2.5)

                                                 G₂(x) = 1 + x².                                               (2.6)

    Пусть, например, кодируется последовательность  m  = (1010… .  Соответствующий информационный полином запишется  как   m(x) = 1 + x².

Тогда на входе первой ячейки выходного  регистра при кодировании будет  последовательность  U ₁ = (11011000… ,  которой  соответствует  полином  U₁(x) = 1 + x + x³ + x⁴,  а на входе второй ячейки — U ₂ = (10001000…  и, соответственно, полином   U₂ (x) = 1 + x⁴.

    Легко заметить, что при этом справедливы  равенства

                               U₁(x) = m(x) × G₁(x),                                                  (2.7)

                                 U₂(x) = m(x)× G₂(x).                                                  (2.8)

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

      Таблица 2.1

    В качестве примера кодера с k₀ ¹ 1 можно привести кодер сверточного (12,9)  кода Вайнера-Эша с параметрами: k₀ = 3,  n₀ = 4,  k = 9,  n = 12,  R = ¾  (рис. 2.3).

          

Рис. 2.3

    Пусть,  например, m = (100.000.000....  Тогда кодовое слово U =     =(1001.0001.0001.0000.... ).  Видно, что это – систематический код, в котором к трем информационным символам добавляется один проверочный, зависящий от значений информационных символов не только текущего кадра, но и двух предшествующих кадров. При этом влияние одного кадра информационных символов распространяется на 12 символов кодовой последовательности, то есть кодовая длина блока для этого кода  n = 12. [16] 

         
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1.4.2 Синдромное декодирование сверточных кодов 

    Предположим, что нами принята полубесконечная  последовательность  r, состоящая из слова сверточного кода и вектора ошибки:

                                              r  = U + e.                                                         (2.9)

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

                                            S =  r× H =  e × Н.                                                  (2.10)

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

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

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

    Схема декодера для сверточного (12,9)-кода Вайнера-Эша изображена ниже  (рис. 2.4). Исправление ошибок с помощью данного декодера производится на сегментах из трех кодовых кадров  -  n = 12.

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

  

  Рис.  2.4

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

    После аналогичных проверок для второго и третьего кадров принятой последовательности на выходе регулирующего буфера оказывается первый кадр принятой последовательности, в регистре синдрома — трехбитовый синдром, соответствующий принятому сегменту из трех кадров, а на выходе адресной логики — дешифрированный по  синдрому S вектор ошибки  e.

    Исправленный  кадр записывается в выходной регистр, при этом исправление производится только при наличии единицы на входах схем “И”, что соответствует присутствию ошибки именно в первом кадре. После исправления ошибки регистр синдрома сбрасывается. Потеря второго и третьего битов синдрома при этом не имеет значения, так как ни во втором, ни в третьем кадрах ошибки быть не должно (она была в первом кадре, а значит, во фрагменте из трех кадров ошибки больше быть не должно).[13]

    Все возможные конфигурации ошибок в  первых трех кадрах и соответствующие  им первые три бита синдрома приведены в табл. 2.2.

 

    

                                                                                                      Таблица 2.2

                

              

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.4.3 Декодирование сверточных кодов. Алгоритм  Витерби

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

    Для двоичного симметричного канала без памяти (канала, в котором вероятности передачи   0  и  1,  а   также вероятности   ошибок  вида  0 ® 1  и 1 ® 0 одинаковы, ошибки в j-м и i-м символах кода независимы) декодер максимального правдоподобия сводится к декодеру минимального хеммингова расстояния. Последний вычисляет расстояние Хемминга между принятой последовательностью  r  и всеми возможными кодовыми векторами U_i и выносит решение в пользу того вектора, который оказывается ближе к принятому.

    Естественно, что в общем случае такой декодер  оказывается очень сложным и при больших размерах кодов  n  и  k  практически нереализуемым.

    Характерная структура сверточных кодов (повторяемость структуры за пределами окна длиной n) позволяет создать вполне приемлемый по сложности декодер максимального правдоподобия.

    Впервые идея такого декодера была предложена Витерби. Работает он следующим образом.

    Предположим, на вход декодера поступил сегмент  последовательности r длиной b, превышающей кодовую длину блока n. Назовем b окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной b) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова примем в качестве оценки информационного кадра декодированного слова.

    После этого в декодер вводится  n₀  новых символов, а введенные ранее самые старые  n₀ символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. [12]