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

    -  полученный  остаток  от деления  m(x) × x^n-k на g(x) прибавляют  к m(x) × x^n-k, то есть записывают в младших n-k разрядах кода.[8]

    Алгоритм  кодирования, основанный на делении  полиномов, можно реализовать, используя схему деления. Она представляет собой регистр сдвига, в котором цепи обратной связи замкнуты в соответствии c коэффициентами порождающего полинома g(x) (рис. 1.10).

Рис. 1.10

    Кодирование в схеме рис. 1.10   выполняется  следующим образом:

    -  k символов информационной последовательности m через переключатель П, находящийся в верхнем положении, один за другим передаются в канал и одновременно с этим через открытую схему И записываются в регистр проверочных символов, в котором благодаря наличию цепей обратной связи g₀ ... g_n-k-1 формируется остаток от деления x^n-k × m(x) на g(x) — проверочные символы;

    -  начиная с (k+1)-го такта переключатель переводится в нижнее положение, и из сдвигового регистра выводятся (n-k) проверочных символов; цепь обратной связи при этом разомкнута ( схема И -  закрыта ).

    Для циклического (7,4)-кода Хемминга (а этот код обладает свойством цикличности), используемого в качестве примера и имеющего порождающий полином g(x) = 1 + x + x³, схема кодирования выглядит следующим образом (рис. 1.11): 

Рис. 1.11

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

    На  примере этого же кода и соответствующего ему кодера рассмотрим в динамике процесс кодирования произвольной последовательности m.

    Пусть  m = (1001). Тогда последовательность состояний ячеек сдвигового регистра с обратными связями в процессе кодирования будет определяться табл. 1.4 .

                                           Таблица 1.4

    Еще одним важным свойством циклического (n,k)-кода, вытекающим из теоремы о существовании циклических кодов,  является то, что его порождающий полином делит без остатка двучлен xⁿ +1, то есть

                             xⁿ + 1 = g(x)× h(x) + 0.                                              (1.71)

    Полином h(x) — частное от деления xⁿ +1  на  g(x) - называется проверочным полиномом.

    Поскольку h(x) однозначно связан с g(x), он также определяет код. Следовательно, с помощью проверочного полинома h(x) тоже можно производить кодирование. Схема кодирования на основании проверочного полинома h(x) приведена на рис. 1.12.

Рис. 1.12

    Процедура кодирования на основании h(x) выглядит следующим образом :

    1.  На входе "Разрешение" устанавливается 1, при этом открывается нижняя схема И и закрывается верхняя.

    2. Сообщение m последовательно записывается в k-разрядный сдвиговый регистр и одновременно с этим передается в канал.

    3. По окончании ввода k информационных символов на входе "Разрешение"  устанавливается 0, замыкая через верхнюю схему И цепь обратной связи.

    4.  Производится (n-k) сдвигов, при этом формируются и выдаются в канал (n-k) проверочных символов.

    Для циклического (7,4)-кода с порождающим полиномом g(x)= 1+ x + x³ проверочный полином  h(x) имеет вид

                                          (1.72)

    С учетом этого  схема кодирования  на основании полинома h(x) для (7,4)-кода выглядит следующим образом  (рис. 1.13):

Рис. 1.13  
 

1.3.2 Вычисление  синдрома  и  исправление  ошибок  в циклических кодах 

    Вычисление  синдрома для циклических кодов  является довольно простой процедурой.

    Пусть U(x) и r(х) - полиномы, соответствующие переданному кодовому слову и принятой последовательности.

    Разделив  r(x) на g(x), получим

                           r(x) = q(x)× g(x) + s(x),                                                 (1.73)

где - q(x) — частное от деления,  s(x) — остаток от деления.

    Если  r(x) является кодовым полиномом, то он делится на g(x) без остатка, то есть s(x) = 0.

    Следовательно, s(x) ¹ 0 является условием наличия ошибки в принятой последовательности,  то есть синдромом принятой последовательности.

    Синдром s(x) имеет в общем случае вид

         S(x) = S₀  +  S₁ × x  +  ... +  S_{n- k-1} × x^n-k-1  .                                        (1.74)

    Очевидно, что схема вычисления синдрома является схемой деления, подобной схемам кодирования рис. 1.10  или 1.11 .

    При наличии в принятой последовательности r хотя бы одной ошибки вектор синдрома S  будет иметь, по крайней мере, один нулевой элемент, при этом факт наличия ошибки легко обнаружить, объединив по ИЛИ выходы всех ячеек регистра синдрома.

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

    Пусть

                    e(x) = e₀  +  e₁ × x  +  e₂ × x²  +  ...  +  e_n-1 × x ^n-1                       (1.75)

— полином вектора ошибки.

    Тогда  полином принятой последовательности 

                                r(x) = U(x) + e(x).                                                       (1.76)

    Прибавим  в этом выражении  слева и справа U(x), а также учтем, что

            r(x) = q(x)× g(x) + S(x), U(x) = m(x)× g(x),                                     (1.77)

тогда

         ,                     (1.78)

то  есть синдромный полином S(x) есть остаток от деления полинома ошибки e(x) на порождающий полином g(x).

    Отсюда  следует, что по синдрому S(x) можно однозначно определить вектор ошибки e(x), а следовательно, исправить эту ошибку. [10]

    На  рис. 1.14 приведена схема синдромного  декодера с исправлением однократной  ошибки для циклического (7,4)-кода. По своей структуре она подобна схеме, приведенной на рис. 1.6, с той лишь разницей, что вычисление синдрома принятой последовательности производится здесь не умножением на проверочную матрицу, а делением на порождающий полином. При этом она сохраняет и недостаток, присущий всем синдромным декодерам: необходимость иметь запоминающее устройство, ставящее в соответствие множеству возможных синдромов  S множество векторов ошибок e. Цикличность структуры кода в этом случае не учитывается. 

    Рис. 1.14  
 
 
 
 
 
 
 
 
 
 
 

    3.3 Неалгебраические методы декодирования циклических кодов 

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

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

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

    Одним из неалгебраических методов является декодирование с использованием алгоритма Меггитта, пригодного для исправления как одиночных, так и l-кратных ошибок (на практике l £ 3).

    При декодировании в соответствии с алгоритмом Меггитта также вычисляется синдром принятой последовательности S(x), однако используется он иначе, нежели в рассмотренных ранее синдромных декодерах.[11]