Авторитетность издания
Добавить в закладки
Следующий номер на сайте
Сверточные коды с алгебраическим декодированием
Аннотация:
Abstract:
Авторы: Мирончиков Е.Т. () - , Титова Е.М. () - | |
Ключевые слова: математика, сверточные коды, система связи, декодирование |
|
Keywords: , , , |
|
Количество просмотров: 13267 |
Версия для печати Выпуск в формате PDF (8.40Мб) |
Во многих системах связи применяются сверточные коды, однако их использование ограничено из-за сложности декодирования. Например, алгоритм декодирования Витерби целесообразно применять, если длина кодового ограничения не больше 10–15. Поиск алгоритмов декодирования, позволяющих работать с более сложными кодами, является актуальной задачей. Предлагаем подход к упрощению реализации декодирования. Основная идея заключается в поиске подкласса сверточных кодов, для которого декодирование можно выполнять уже известными методами, разработанными для блоковых алгебраических кодов.
Для получения сверточного кода необходимо найти пару ортогональных полиномиальных матриц, которые принято называть порождающей и проверочной [1]. Переменная x, входящая в эти полиномиальные матрицы, рассматривается как задержка на один временной такт. Порождающая и проверочная матрицы сверточного кода взаимно однозначно определяют друг друга, что позволяет вычислить одну из них по другой. Таким образом, для задания сверточного кода достаточно построить проверочную матрицу, а порождающую матрицу, определяющую кодирующее устройство, можно вычислить по проверочной матрице. Для получения проверочной матрицы сверточного кода построим проверочную матрицу кода Рида–Соломона над полем GF(qm). Этот код имеет следующие параметры: длина n=qm-1, число информационных символов k, минимальное кодовое расстояние d=n-k+1. Данный код может исправить Пусть a будет примитивным элементом поля GF(qm). Выберем код Рида–Соломона с генератором g(x), корнями которого являются элементы a1,a2,…,ar, где r=n–k. Пусть H¢ будет проверочная матрица размера r´n для этого кода Рида–Соломона. Теперь сконструируем из проверочной матрицы кода Рида–Соломона проверочную матрицу сверточного кода. В простейшем случае укоротим проверочную матрицу кода Рида–Соломона на один столбец, чтобы ее длина была четной. Разобьем n-1 столбцов полученной матрицы на две равные подматрицы
где Вычислить порождающую матрицу, зная проверочную матрицу, можно несколькими способами. Обычно, используя элементарные преобразования, приводят проверочную матрицу где Когда проверочная матрица представлена в форме (2), порождающая матрица кода определяется следующим образом: Схема процесса вычисления синдрома Полученная матрица Опишем декодирование полученного сверточного кода. В рассматриваемом примере на каждые 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) следующим образом: · определим коэффициент при старшей степени полинома · вычислим полином · вычислим полином f(x), равный остатку от деления произведения · полином L(x) равен Полином L(x) можно рассматривать как аналог преобразования Фурье последовательности ошибок на отрезке сверточного кода, контролируемом проверочной матрицей. Для получения вектора ошибки для блока длины n-1 требуется выполнить обратное преобразование. С этой целью определим вспомогательные полиномы Вычислим остатки Далее найдем спектральные полиномы: Вектор ошибки блока определяется выра- жением В качестве примера рассмотрим характеристики сверточных кодов, полученные из кода Рида–Соломона длины 127 над полем Таким образом, мы рассмотрели метод построения сверточного кода, допускающего пошаговое исправление ошибок последовательно на каждом блоке сверточного кода. Подобные коды имеют специфическую структуру, допускающую алгебраическое декодирование. Для реализации процесса декодирования использовалась модификация алгоритма Гао [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. |
Постоянный адрес статьи: http://swsys.ru/index.php?page=article&id=1652 |
Версия для печати Выпуск в формате PDF (8.40Мб) |
Статья опубликована в выпуске журнала № 4 за 2008 год. |
Возможно, Вас заинтересуют следующие статьи схожих тематик: