Методы быстрого декодирования линейных блоковых кодов

• Автор: Федоренко, Сергей Валентинович
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 220 с. : ил.

Содержание
Введение

1. Комбинаторное декодирование линейных блоковых

1.1. Декодирование но обобщенным информационным

совокупностям

1.1.1. Понятие обобщенной информационной совокупности. Алгоритм декодирования

1.1.2. Построение тпокрытий из кодовых слов . .

1.1.3. Таблица декодеров по обобщенным информационным совокупностям

1.2. Табличное декодирование .

1.2.1. Синдромное декодирование

1.2.2. Декодирование по информационным совокупностям .

1.2.3. Декодирование в надкодах
1.2.4. Комбинирование алгоритмов декодирования
1.2.5. Декодирование кодов с большой группой
симметрии
1.2.6. Декодирование квадратичновычетных кодов
1.3. Асимптотика
1.3.1. Обзор алгоритмов декодирования линейных
блоковых кодов для декодеров с жесткими решениями
1.3.2. Сложность декодирования линейных блоковых кодов
1.4. Выводы.
2. Алгебраическое декодирование
2.1. Алгебраическое декодирование по обобщенным информационным совокупностям
2.1.1. Основные понятия и определения . .
2.1.2. Укорочения Ь,дкодов
2.1.3. Применение декодирования укороченных Ь5,0зк одов.
2.2. Генетическая связь алгебраических методов декодирования
2.2.1. Основные понятия и определения
2.2.2. Алгоритм Гао
2.2.3. Оригинальный алгоритм Велча Берлекэмпа
2.2.4. Интерпретация Чамберса
2.2.5. Алгоритм Велча Берлекэмпа в частотной области
2.2.6. Вывод алгоритма Гао.
2.2.7. Расширенный алгоритм Евклида
2.2.8. Корректность алгоритма Гао .
2.2.9. Пример
2.2 Замечания к разделу
2.3. Декодирование в надкодах.
2.3.1. Основные определения
2.3.2. Дополнительные тождества
2.3.3. Алгоритм исправления трех ошибок
2.3.4. Декодирование свыше конструктивного расстояния на основе надкодов.
2.3.5. Пример
2.4. Выводы.
3. Вычисление дискретного преобразования Фурье над конечным полем
3.1. Вычисление корней многочлена
3.1.1. Алгоритм быстрого поиска корней многочлена
3.1.2. Результаты моделирования .
3.1.3. Специальные разложения многочленов .
3.1.4. Гибридный метод .
3.1.5. Аналитические методы вьпшсления корней
многочленов степени до четырех.
3.1.6. Сравнение методов вычисления корней многочлена
3.2. Циклотомический алгоритм.
3.2.1. Основные понятия и определения
3.2.2. Быстрое вычисление преобразования Фурье .
3.2.3. Пример
3.2.4. Сравнение сложности алгоритмов БПФ . . .
3.3. Рекуррентный метод.
3.3.1. Основные понятия и определения
3.3.2. Алгоритм Рейдера
3.3.3. Свойства матрицы эквивалентного преобразования
3.3.4. Упорядочение чисел из полной системы вычетов .
3.3.5. Быстрое вычисление ДПФ
3.3.6. Примеры вычисления ДПФ
3.4. Вычисление синдрома
3.4.1. Вычисление неполного ДПФ с помощью
циклотомического алгоритма.
3.4.2. Вычисление неполного ДПФ с помощью ре
куррентного метода.
3.5. Выводы.
4. Декодирование по кодовым решеткам 1
4.1. Представления кодов с заданной группой симметрии
4.1.1. Две конструкции кодов.
4.1.2. Приведение матриц кода к квазициклическо
му представлению.
4.2. Циклические замкнутые решетки
4.3. Звездные решетки.
4.3.1. Представление кода Голея в виде звездной решетки
4.32. Декодирование кода Голея по звездной решетке
4.3.3. Замечания к разделу.
4.4. Декодирование кодов Рида Соломона по звездным решеткам
4.4.1. Разложение Варди Беэри
4.4.2. Метод декодирования.
4.5. Выводы.
5. Вопросы реализации
5.1. Приложение методов быстрого декодирования линейных блоковых кодов к системам связи
5.1.1. Многошаговое декодирование итеративных кодов Хэмминга.
5.1.2. Результаты моделирования .
5.2. Схема вычисления ДПФ.
5.3. Реализация циклотомического алгоритма вычисления ДПФ на программируемой логической интегральной схеме
5.4. Выводы.
Заключение
Библиографический список
Введение
Актуальность


Поскольку ранг любой Д х (А — 1) подматрицы порождающей матрицы кода Gv не превышает А — 1, то для любых А — 1 позиций кода Gv найдется слово с Е Gv, W(c) = dy которое имеет нули на этих позициях. Следовательно, слово а + с веса d имеет единицы на этих позициях. Итак, множество из 2Л — 2 слов веса d кода Gv образует M(2dy dy А — 1)-покрытие. Ч.т. Лемма 1. V = NV; 7' = п — к; G и Н — порождающая и проверочная матрицы кода Q соответственно. Доказательство. Пусть Ну — проверочная матрица кода G(V). Очевидно, что |V|— rank G(V) = rank Ну. Кроме того, строки матрицы Ну, дополненные нулями на множестве V, ортогональны коду Q. Остальные г — rank Ну строк матрицы Я линейно независимы на множестве V. Поэтому г — rank Ну = rank H(V). Ч.т. Следствие. G(V) = rank G(V). Для построения декодера по обобщенным информационным совокупностям (п, к)-кода G, исправляющего t ошибок, необходимо построить т-покрытие кодовыми словами веса w, т = t — [{(а —T)/2j, где dja определяется неравенством (1). Разобьем множество N = {1,2,. V,. Vr. Vi для г G [1,/] являлось T(n,t,r)-покрытием (большинство известных покрытий Ту-рана построено таким образом) Затем для каждого Vi, г 6 [1,/], строим M(|Vi|, ИДа7;), т)-покрытие из кодовых слов. Объединяя эти М-покрытия, образуем искомое т-покрытие. Используя доказанные выше леммы, можно сократить перебор при построении M(Vi, ИДаД, т)-покрытий. Для этого в качестве множеств V,. Vi должны быть выбраны множества /а1,. G Q и W(а-Д = 2d, j € [1,/]. Тогда в силу леммы 1. M(2d,d, Aj — 1)-покрытие из кодовых слов, вложенное во множество Vj, где Аj = 2d — rank H(Vj). А^ — 1) > т. Согласно следствию, для самодуальных кодов достаточно построить покрытие из кодовых слов на множестве V, V = п/2, так как требуемое покрытие на множестве V совпадает с покрытием для V с точностью до перенумерации позиций. Голея Q. Пример- Покрытие для кода Голея. Для любого вектора а е ? W (а) = 8; существует код ? Хэмминга. Пусть V и V2 — такие множества, что |Vi| = |V2I = и Vi J. V2 = {1,2,. Строим покрытие Ту рана Т(,3,2). Известно [], что это покрытие является оптимальным и состоит из всех 2-подмножеств множества V и всех 2-подмножеств множества И2. Затем построим М(;8,2)-покрытие из кодовых слов. Пусть ai — произвольное кодовое слово минимального веса. Найдем другое кодовое слово а2, для которого W(a2) = 8 и W(ai + а2) = 8. Три слова {ai,a2,ai + а2} вложены в множество V — Iaj (J /а2 и образуют оптимальное М(,8,2)-покрытие, представляющее собой все ненулевые слова (, 2, 8)-кода. Из следствия леммы 1. V2, также образуют М(,8,2)-покрытие. Таким образом, мощность оптимального т-покрытия для кода Голея равна s = 6. Выпишем это покрытие. Пусть порождающая матрица кода Голея представлена в виде [, рисунок . J G = [Дг]^],. С — циркулянтная матрица [; (. С(Х) = 1-f x+xs+x4+x5--xe+xs [, (. Тогда оптимальное т-покрытие из кодовых слов {ai,. Алгоритм декодирования, основанный на этом покрытии, имеет сложность порядка 0 операций над векторами длины г = . Кроме того, необходимо запомнить 6 проверочных матриц, кода. Заметим, что для реализации оптимального алгоритма декодирования (, , 8)-кода Голея по информационным совокупностям, использующего множество из информационных совокупностей [7], требуется около 0 таких операций. Рассмотрим другой пример. Пример. Покрытие для (, , )-кода. При построении т-покрытия для квадратично-вычетного (, , )-кода Q кодовыми словами минимального веса приходится проводить машинный перебор, хотя аналитические рассуждения позволяют сократить его сложность до величины, кратной числу кодовых слов минимального веса. Все укороченные коды Q(Ia), W{а) = , имеют параметры (, , 6). Покрытие Турана Т(,5,3) состоит из всех 3-подмножеств множества V и всех 3-подмножеств множества V2, для которых | Vi I = IV2I = и ViU^ = {1,2, . Построим М(,8,3)-покрытие из кодовых слов. Для этого в соответствие с леммой 1. V — множество ненулевых позиций вектора аі + а2; G = Н — порождающая (она же проверочная) матрица кода Q. Все слова веса , вложенные в множество Vi, образуют требуемое М-гюкрытие. Аналогично из следствия леммы 1.