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

    Идея, лежащая в основе декодера Меггитта, очень проста и  основывается на следующих свойствах циклических кодов:

    -  существует взаимно-однозначное  соответствие между множеством  всех исправляемых ошибок и множеством синдромов;

    -  если S(x) — синдромный многочлен, соответствующий многочлену ошибок    е(x),  то   x×S(x) mod g(x) — синдромный   многочлен, соответствующий x× e(x) mod (xⁿ + 1).

    Равенство а(x) = b(x) mod p(x) читается как “а(x), сравнимо с b(x) по модулю р(x)” и означает, что а(x) и b(x) имеют одинаковые остатки от деления на полином p(x).

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

    Следовательно, основным элементом декодера Меггитта является сдвиговый регистр. Структурная схема декодера Меггитта для циклических кодов произвольной длины приведена на рис. 1.15.

Рис. 1.15

    Декодер работает следующим образом. Перед  началом работы содержимое всех разрядов регистров равно нулю. Принимаемая последовательность r в течение первых n тактов вводится в буферный регистр и одновременно с этим в (n-k)-разрядном сдвиговом регистре с обратными связями производится ее деление на порождающий полином g(x).

    Через n тактов в буферном регистре оказывается принятое слово r , a в регистре синдрома — остаток от деления вектора ошибки на порождающий полином.

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

    После этого синдромный и буферный регистры один раз циклически сдвигаются. Это реализует умножение S(x) на x и деление на g(x). Содержимое  ячеек синдромного регистра теперь равно остатку от деления x×S(x) на g(x) или синдрому ошибки x× е(x) mod (Хⁿ + 1).

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

    Рассмотрим работу декодера Меггитта для циклического (7,4)-кода, исправляющего одиночную ошибку. Схема декодера изображена на рис. 1.16.

    Рис. 1.16

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

    Полином  ошибки в старшем разряде для  (7,4)-кода  Хемминга  имеет  вид  е₆ (x) =  x⁶, соответствующий ему синдромный  полином S₆ (x) =  1 + x³ ( S = (101)), детектор ошибки настроен на это значение синдрома.

    Пусть, например, передана последовательность U = (1001011), ей соответствует кодовый полином U(x) = 1 + x³ + x⁵ + x⁶. Произошла ошибка в третьей позиции е(x) = x³, принятый вектор имеет вид r = (1000011), его полином r(x) = 1 + x⁵ + x⁶.

    Kогда  принятая последовательность полностью  входит в буферный регистр,  в регистре синдрома оказывается  синдром, соответствующий ошибке  е(x) = x³ S₃ = (110). Поскольку он не совпадает с табличным для е₆, на выходе детектора ошибок будет 0 и исправления не происходит. [13]

    Далее производятся однократный циклический  сдвиг принятой последовательности  в  буферном  регистре, однократное деление синдрома x∙S₃ на порождающий полином в регистре с обратными связями и проверка на совпадение синдрома с заданным.

    Последовательность  состояний регистров декодера в  процессе декодирования показана на рис. 1.17. 
 
 
 
 
 

Рис. 1.17

     Таким образом, исправление ошибки в декодере Меггитта осуществляется за 2×n тактов: в течение n тактов производится ввод принятой последовательности в буферный регистр, в течение l тактов — исправление ошибки, и еще в течение n - l  - восстановление буферного регистра в исходное состояние с исправленным словом. Простота декодера достигается увеличением времени декодирования.

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

    1.4 Сверточные коды

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

    При использовании сверточных кодов  поток данных разбивается на гораздо меньшие блоки длиной k символов (в частном случае k₀ = 1), которые называются кадрами информационных символов.

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

    Развитие  теории и практики сверточных кодов  заметно отличается от развития блочных кодов. При построении блочных кодов и методов их декодирования широко использовались алгебраические методы. В случае сверточных кодов это не так. Большинство хороших сверточных кодов было найдено путем просмотра с помощью ЭВМ большого числа кодов и последующего выбора кодов с хорошими свойствами. Декодирование сверточных кодов производится методами, близкими к методам максимального правдоподобия, причем в этом случае они реализуются достаточно просто. [16] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1.4.1 Кодирование с использованием сверточных кодов 

Основными характеристиками сверточных кодов  являются величины:

-   k₀ – размер кадра информационных символов;

    Кодовая длина блока - это длина кодовой последовательности, на которой сохраняется влияние одного кадра информационных символов.[12]

    Наконец, сверточный код имеет еще один важный параметр - скорость R = k/n, которая характеризует степень избыточности кода, вводимой для обеспечения  исправляющих свойств кода.

    Как и блочные, сверточные коды могут  быть систематическими и несистематическими и обозначаются как линейные сверточные (n,k)-коды.

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

    Примеры схем кодеров для систематического (8,4) и несистематического сверточных (6,3)-кодов приведены на рис. 2.1  и 2.2.

Рис. 2.1       Рис. 2.2

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

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

    Импульсная  переходная характеристика фильтра (ИПХ) (а кодер сверточного кода, по сути дела, является фильтром) есть реакция на единичное воздействие вида = (10000..... Для кодеров, изображенных на  рис. 2.1 и 2.2, соответствующие импульсные характеристики будут иметь вид:

                                 H_а = (11.00.00.01.00.00… ,                                      (2.1) 

                                H_б = (11.10.11.00.00.00… .                                       (2.2)

      Еще одна форма задания сверточных кодов – это использование порождающих полиномов, однозначно связанных с ИПХ эквивалентного фильтра:

                                         H_а(x) = 1 + x + x⁷,                                                   (2.3)

                                   H_б(x) = 1 + x + x² + x⁴ + x⁵.                                        (2.4)

    При этом кодовая последовательность U на выходе сверточного кодера получается в результате свертки входной информационной последовательности  m   с импульсной переходной характеристикой  H.

    Рассмотрим  примеры кодирования последовательностей с использованием импульсной характеристики эквивалентного фильтра.

    Пусть m = (110 ...  , тогда для кодера с ИПХ   H = (11.00.00.01.00.00....

U = 11.00.00.01.00.00… 
            11.00.00.01.00… 
 
U  = 11.11.00.01.01.00.00… ,

или  m  = (1011000…

U = 11.00.00.01.00.00.00… 
                 11.00.00.01.00… 
                      11.00.00.01… 
 
U = 11.00.11.10.00.01.01.00… .     

    Иногда  удобнее рассматривать полный порождающий  полином сверточного кода G(x) как совокупность нескольких многочленов меньших степеней, соответствующих ячейкам выходного регистра кодера. Так, для кодера рис. 2.2 соответствующие частичные порождающие полиномы будут следующими: