4.5. Быстрое преобразование Фурье длины 5
5-точечное ДПФ с ядромзадается равенством
,
непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+++) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:
,
Аналогично,
,
,
и, наконец,
Дальнейшего уменьшения числа умножений можно добиться за счет перехода к циркулянту и использования полиномиальной свертки (ПС). Приведем необходимые сведения:
Утверждение 4.5.1. Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.
Действительно, ()()≜, где , и
Если умножение происходит в поле F, то , где ,
Следствие 4.5.1. Два многочлена степени m над полем F можно перемножить, выполняя не более умножений чисел в поле F.
Например, для m=3 (с учетом, что char GF()=2) имеем:
(10)
≜
где t≜ (так что при вычислении по модулю многочлена надо делать редукцию по модулю ); согласно утверждению 4.5.1:
≜
≜
≜
Для вычисления , , опять воспользуемся утверждением 4.5.1. Имеем
(11)
Таким образом, для вычисления коэффициентов многочлена необходимо только 9 (вместо 16) умножений. Точные формулы для коэффициентов многочлена (при ) имеют вид:
(12)
Для коэффициентов при, согласно (10)-(12)
,
,
,
,
(13)
,
,
Если произведение вычисляется в кольце F(так что ), то формулы (10)-(12) принимают вид:
≜, (10а)
(11a)
, ≜
,
.
Вычисление вектора гдеа – циркулянт, первая строка которого задается вектором , равносильно вычислению в F произведения , где и .
Подчеркнем, что преобразуемая последовательность , за исключением первого элемента, дает реверсивный порядок коэффициентов многочлена при координате стоит коэффициент .
Утверждение 4.5.2. Для ДПФ простой длины n всегда существует такая перестановка строк и столбцов матрицы Фурье, что она может быть превращена в окаймленный циркулянт.
Этот результат принадлежит Рейдеру. Мы подробно проиллюстрируем соответствующий алгоритм в следующем пункте, посвященному БПФ длины 17, а сейчас вернемся к БПФ длины 5.
Прежде всего избавимся от единичного окаймления матрицы Фурье:
= )
В столбцах и строках матрицы, стоящей в правой части равенства выполним перестановку . Если выполним такую же перестановку координат у векторов d и его спектра А, получаем
) (14)
Циркулярная матрица для БПФ длины 5 получается, если задать нумерацию ненулевого элемента поля GF(5) с образующей 3: 1 (mod5), 33 (mod5), 4 (mod5), 2 (mod5): .
Этим задача свелась, согласно утверждения 4.5.2, к вычислению многочлена c(x)=d(x)w(x)mod(x-1), где d(x)= или, иначе, циклической свертки с=с
Для вычисления этой циклической свертки длины 4, перепишем формулы (13) в более удобном для организации экономного вычисления виде:
, ;
(15)
Этот алгоритм содержит 9 умножений и 17 сложений. Но если появляются какие-то условия на коэффициенты или,то число вычислений уменьшается. Например, если =0 или 1, то число умножений равно только 5. В нашем случае и так как - ядро БПФ длины 5, то=1. Учитывая это, из формул (13) – (14) окончательно приходим к следующему алгоритму:
, , , , , , , , , , , . (16)
Так что алгоритм БПФ длины 5 в поле в нашем случае содержит 5 умножений и 11сложений.
- Введение
- В дипломной работе рассмотрен спектральный метод кодирования кодов Рида-Соломона над полем 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 Листинг программы