4.8. Несистематические бпф-укорочения
Порядок мультипликативной группы поля является составным числом n=255=3*5*17. Группа является циклической и порождается примитивным элементом α; она содержит 255 элементов: . Эта группа имеет циклические подгруппы порядка (делят ).
В таблице 1 приведены циклические подгруппы мультипликативной группы поля .
Таблица 1.
Циклические подгруппы мультипликативной группы поля
Порядок подгруппы | Порождающий элемент | Подгруппа |
3 | ||
5 | ||
15 | ||
17 | ||
51 | ||
85 |
В основе несистематического кодирования укороченных РС-кодов лежит дискретное преобразование Фурье (ДПФ) на группе, образуемой ненулевыми элементами поля.
Кодовое слово задается как ДПФ информационного вектора cинформационными символами и нулями, где , а в качестве примитивного элемента выбран корень неприводимого многочлена .
Aлгоритм трехмерного ДПФ позволяет вычислить элементы кодового вектора по формуле:
(24)
Рассмотрим преобразование Фурье длины в поле . Элементами этого преобразование должны быть элементы подгруппы, образованной примитивным элементом (в соответствии с таблицей 1). Перекодируем укороченный вектор (вектор длины 51) в полный вектор (длины 255) таким образом, чтобы все координаты , для которых , были нулевыми. Практически это означает, что мы разместим укороченный вектор только в одной плоскости БПФ-куба там, где . Тогда формулу (24) можно переписать в виде:
(25)
А это означает переход к ДПФ с ядром для вектора . Преобразование Фурье вычисляется как значение многочлена в точках поля: , что эквивалентно работе в подгруппе с ядром : .
Очевидно, что для реализации БПФ-укорочения длины 85 с порождающим элементом из формулы (24) необходимо исключить суммирование по , что достигается путем размещения укороченного вектора в плоскости БПФ-куба там, где . Это означает переход к ДПФ с ядром для мультипликативной подгруппы порядка 85 с шагом 3.
(26)
Проводя аналогичные рассуждения можно построить формулы вычисления ДПФ для всех циклических подгрупп, указанных в таблице 1. Эти БПФ-укорочения можно применить для кодирования укороченными кодами Рида-Соломона над полем длин n=85,51,17,15,5,3.
- Введение
- В дипломной работе рассмотрен спектральный метод кодирования кодов Рида-Соломона над полем gf(). В основе спектрального описания рс-кодов лежит дискретное преобразование Фурье (дпф над конечным полем.
- Раздел 1. Основы теории помехоустойчивого кодирования
- 1.1 Основные определения
- 1.2 Классификация кодов
- 1.3 Принципы обнаружения и исправления ошибок
- 1.4. Корректирующая способность кода
- Раздел 2. Арифметика и структура конечных полей галуа. Многочлены над полями галуа
- 2.1. Введение в теорию конечных полей
- 2.2 Векторное пространство над конечными полями. Линейная зависимость и независимость
- 2.3 Арифметика полиномов, заданных над конечным полем
- 2.4. Расширенные конечные поля
- 2.5 Мультипликативный порядок элементов поля. Примитивные элементы. Другой подход к построению расширения поля Галуа
- 2.6. Некоторые свойства расширенных конечных полей
- Раздел 3. Линейные блоковые коды
- 3.1. Линейные коды
- 3.2. Определение циклического кода. Порождающий полином
- 3.3. Систематический циклический код
- 3.4. Коды Рида-Соломона
- Раздел 4. Спектральное описание циклических кодов
- 4.1. Дискретное преобразование Фурье
- 4.2. Китайская теорема об остатках
- 4.3. Трехмерное преобразование Фурье в поле
- 4.4 Быстрое преобразование Фурье бпф длины 3
- 4.5. Быстрое преобразование Фурье длины 5
- 4.6 Быстрое преобразование Фурье длины 17
- 4.8. Несистематические бпф-укорочения
- Заключение
- Список использованной литературы
- Приложения Приложение 1. Анализ временных характеристик кодера кодов Рида-Соломона
- Приложение 2 Листинг программы