Арифметические методы синтеза быстрых алгоритмов дискретных преобразований

• Автор: Чернов, Владимир Михайлович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Самара
• Количество страниц: 277 с. : ил.

Введение
Глава 1. Совмещенные алгоритмы дискретных ортогональных преобразований с представлением данных в альтернативных алгебрах

1.1. Совмещенные многомерные БПФ с представлением данных в алгебрах Клиффорда

1.1.1. Основная теорема

1.1.2. Примеры ВПФ с совмещением в четырехмерных алгебрах Клиффорда

1.2. Методы синтеза быстрых алгоритмов дискретных преобразований с представлением данных в полях алгебраических чисел

1.2.1. Представление данных в циклотомических кодах

1.2.2. Алгоритмы двумерных ДОЛ, реализуемые в кодах Гамильтона - Эйзенштейна

1.2.3. Быстрые алгоритмы одномерного ДПФ с восьмикратным совмещением в алгебре матриц

1.3. Алгоритмы ДПФ с совмещением в групповых алгебрах циклических групп

1.3.1.Некоторые свойства групповых алгебр циклических групп

1.3.2. Быстрый алгоритм вспомогательного преобразования со значениями в групповой алгебре
1.3.3. Быстрый алгоритм ДПФ с асимптотическим понижением порядка мультипликативной сложности
1.3.4. Некоторые специальные случаи
Комментарии
Основные результаты главы
Глава 2. Дискретные преобразования с базисами, порожденными группами Галуа циклотомических полей
2.1. Дискретные ортогональные преобразования с базисами из периодов полей деления круга
2.2. Редукция Галуа дискретных преобразований, порожденных гауссовыми периодами круговых полей
2.2.1. Схема декомпозиции ДПГ типа Кули-Тьюки
2.2.2. Редукция Галуа ДПГ (общий случай)
2.3. Быстрые алгоритмы многомерных ДПФ, использующие редукцию Галуа
2.4. Некоторые замечания об эффективности алгоритмов Рейдера-Винограда
Комментарии
Основные результаты главы
Глава 3. Унифицированный метрический подход к синтезу быстрых алгоритмов многомерного ДПФ
3.1. Алгоритмы двумерного ДПФ с расщеплением основания нецелого порядка
3.1.1. Альтернативная интерпретация редукции Кули-Тьюки
3.1.2. Чесс-алгоритмы двумерного ДПФ
3.1.3. Алгоритмы ДПФ-2 с "мультипокрытием" области суммирования
3.2. Специальный случай: алгоритмы многомерного ДПФ с расщеплением основания нецелого порядка при N
3.2.1. Алгоритмы двумерного ДПФ с покоординатным

прореживанием области суммирования
3.2.2. Чесс-алгоритмы двумерного ДПФ для Ы=2Г
3.2.3. Интерпретация алгоритмов двумерного ДПФ как алгоритмов с расщеплением основания нецелого порядка
3.2.4. Алгоритмы двумерного ДПФ с "мультипокрытиями" области суммирования
3.3. Многомерные БА ДПФ с расщеплением основания нецелого порядка
3.3.1. Алгоритмы ДПФ-й с простым покрытием области суммирования
3.3.2. Алгоритмы ДПФ-П с "мультипокрытием"
области суммирования
3.3.3. Алгоритмы ДПФ-П, порожденные максимальными
покрытиями
Комментарии
Основные результаты главы
Глава 4. Алгоритмы вычисления дискретной циклической свертки с представлением данных в рекуррентных системах счисления
4.1. Основные определения и теоремы
4.2. Параллельные алгоритмы дискретных шифт-ТЧП для -данных, представленных в рекуррентных системах
счисления первого порядка
4.2.1. Шифт-ТЧП по модулю составных чисел
Мерсенна
4.2.2. Шифт-ТЧП по модулю составных чисел

т.п. + nan
Strrq.na; а,Ъ) = ) х+а, п2+Ь)( ы1-) . (1.29)
п1 ,и2
Положим ) = х(2п1+а,2а2+Ь) и введем функцию
q(n1tn2) со значениями в алгебре и:
х00(п1 ,п2)+х01 (о, ,n2)i+x10(n1 ,n2)j+xu (п., ,п2)й
= q(nrn£) (1.30)
Определим "кватернионный спектр" QCmnig), равенством:

гД пцп,+ паха
Q(mr ш2) = 2 q(n., ,д2)(иН) г (1.31)
п1,п2

Для реконструкции x(m1sm2) достаточно вычислить
Q(m1,m2) для т1, т2 = 0,1N1 —1, с помощью (1.27) найти
S(m1,m2; a,b):
4 S (т1,т2; 0,0) = Q (ш1,щ2) +Qa (т,,,т2)+QP (т1,т2)+Q7 (т1, т,2); 44S (т1, т2; 0,1 ) = Q(m1 ,m2)+Qa(m1 ,m2)-Qp(m1 ,m2)-QT(m1 ,а2); 4J3(m1 ,m2;1,0) = CKn ,m,2 )-Qa(m1 ,m,2 )+Qp (m1 ,m2)-QT(m1 ,m2);
4ftS(m1 ,m2;1,1 ) = Q(m1 ,m2)-Qa(m1 ,m2)-QP(m1 ,m2)+QT(m1 ,m.2),

Qa(m1,m2) = «(Q , ra2)), (m1 ,m2 ) = p(Q(-m1 ,-m2)),
Q7(m1,m2) = T(Q(-m1,-m2)), а также выполнить 3 (N.-1)2 умножений на степени константы