Software & Systems

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

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

Для получения проверочной матрицы сверточного кода построим проверочную матрицу кода Рида–Соломона над полем GF(qm). Этот код имеет следующие параметры: длина n=qm-1, число информационных символов k, минимальное кодовое расстояние d=n-k+1. Данный код может исправить  ошибок, где  равно целому числу, не превышающему a.

Пусть a будет примитивным элементом поля GF(qm). Выберем код Рида–Соломона с генератором g(x), корнями которого являются элементы a1,a2,…,ar, где r=n–k. Пусть H¢ будет проверочная матрица размера r´n для этого кода Рида–Соломона.

Теперь сконструируем из проверочной матрицы кода Рида–Соломона проверочную матрицу сверточного кода. В простейшем случае укоротим проверочную матрицу кода Рида–Соломона на один столбец, чтобы ее длина была четной.

Разобьем n-1 столбцов полученной матрицы на две равные подматрицы . Сформируем на основе этих подматриц проверочную матрицу сверточного кода  размера r´(n-1)/2. Элементами проверочной матрицы сверточного кода являются полиномы первой степени, вычисленные по правилу:

,                      (1)

где  – элементы подматриц ,  соответственно, i=1,2,…,r, j=1,2,…,(n-1)/2.

Вычислить порождающую матрицу, зная проверочную матрицу, можно несколькими способами. Обычно, используя элементарные преобразования, приводят проверочную матрицу  в модифицированную приведенно-ступенчатую форму [2]: ,                                          (2)

где  – единичная матрица размера r´r; P – матрица размерности r´ks, где . Под элементарными преобразованиями подразумеваются перестановка строк матрицы и прибавление к некоторой строке другой строки, умноженной на произвольный полином.

Когда проверочная матрица представлена в форме (2), порождающая матрица кода определяется следующим образом:  где  – единичная матрица размера ;  обозначает транспонированную матрицу P.

Схема процесса вычисления синдрома

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

Опишем декодирование полученного сверточного кода. В рассматриваемом примере на каждые ks входных символов получаем (n-1)/2 выходных символов кодового слова, которые составляют одно ребро (или один блок) при решетчатом представлении кода. Проверочная матрица контролирует отрезок кодового слова, равный только двум ребрам. На следующем шаге контролируются также два ребра, одно из которых повторно. Этот процесс показан на рисунке. Отметим, что на первом шаге декодирования контролируются последовательность из (n-1)/2 нулевых символов и еще один блок.

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

Рассмотрим процесс поиска и исправления ошибок в кодовом слове. Пусть на некотором шаге декодирования вычислен синдром S(x).

Многочлен Гоппы [3] равен .

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

Вычислим вспомогательный полином L(x) следующим образом:

·    определим коэффициент при старшей степени полинома  и обозначим его через z;

·    вычислим полином , равный отношению ;

·    вычислим полином f(x), равный остатку от деления произведения  на многочлен Гоппы T(x);

·    полином L(x) равен .

Полином L(x) можно рассматривать как аналог преобразования Фурье последовательности ошибок на отрезке сверточного кода, контролируемом проверочной матрицей. Для получения вектора ошибки для блока длины n-1 требуется выполнить обратное преобразование. С этой целью определим вспомогательные полиномы , где  – локаторные полиномы;

Вычислим остатки  от деления полиномов  на соответствующие локаторные полиномы : для i=1,2,…,n.

Далее найдем спектральные полиномы: , где . Полученные спектральные полиномы удовлетворяют сравнениям: ; , если индексы i и j не совпадают, .

Вектор ошибки блока определяется выра- жением . Вычитая E(x) из де- кодируемого отрезка кодового слова, получим очередной блок кодового слова без ошибок.

В качестве примера рассмотрим характеристики сверточных кодов, полученные из кода Рида–Соломона длины 127 над полем . Если использовать разное число проверочных символов в этом коде (например, 34, 36, 38, 40 и 42), то, укоротив код длины 127 на один символ, получим сверточные коды со скоростями 29/63, 27/63, 25/63, 23/63 и 21/63, исправляющие до 17, 18, 19, 20 и 21 ошибки на блоке длины 63 соответственно. Эти коды декодируются алгоритмом, описанным выше.

Таким образом, мы рассмотрели метод построения сверточного кода, допускающего пошаговое исправление ошибок последовательно на каждом блоке сверточного кода. Подобные коды имеют специфическую структуру, допускающую алгебраическое декодирование. Для реализации процесса декодирования использовалась модификация алгоритма Гао [4], предложенная М. Сонном [5], применяемая ранее для кодов Боуза–Чаодхури–Хоквингема и Рида–Соломона. Эта модификация пригодна для декодирования не только укороченных циклических кодов, но и кодов, использующих любую комбинацию локаторных полиномов.

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

Список литературы

1.   Johannesson Rolf, Zigangirov Kamil Sh. Fundamentals of convolutional coding. – IEEE Press, 1999.

2.   Блейхут Р., Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

3.   Goppa V.D. Geometry and Codes. – London: Kluwer academic publishers, 1988.

4.   Gao S. A new algorithm for decoding Reed – Solomon codes. – Clemston University, Chemston, 2002.

5.   Сон М. Об одном алгоритме декодирования кодов РС в каналах с кодовым зашумлением. / Проблемы безопасности информационных систем. Компьютерные системы. – СПб, 2004.