Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов

  

Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов / В.А. Власенко, Ю.М. Лаппа, Л.П. Ярославский. — М.: Наука, 1990. - 180 с.

Монография посвящена разработке и систематизации методов синтеза быстрых алгоритмов свертки и спектрального анализа сигналов. На основе единого матричного аппарата систематизированы известные и синтезированы новые эффективные алгоритмы дискретных преобразований Фурье, Хартли и цифровых сверток. Приведенный математический аппарат позволяет провести наиболее полную структурную классификацию алгоритмов БПФ. Освоение этого аппарата дает возможность эффективно конструировать новые алгоритмы и вычислительные средства цифровой обработки сигналов.

Книга рассчитана на научных работников, инженеров, специализирующихся в области цифровой обработки сигналов.



Оглавление

ВВЕДЕНИЕ
1. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ МАТРИЦ
1.2. Кронекеровское произведение матриц
1.3. Прямая и послойная суммы матриц
1.4. Матрицы перестановок
2. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ОБОБЩЕНИЯ
2.1. Определение одномерного ДПФ
2.2. Определение многомерного ДПФ
2.3. Дискоетное преобразование Виленкина
2.4. Теоретико-числовые преобразования
2.5. Дискретное комбинированное преобразование Фурье
2.6. Дискретное преобразование Хартли
2.7. Многомерное дискретное преобразование Хартли
2.8. Сдвинутое дискретное преобразование Фурье
3. БАЗОВЫЕ ФОРМЫ ФАКТОРИЗАЦИИ
3.1. Факторизация ДПФ для двух произвольных множителей
3.2. Факторизация ДПФ для двух взаимно-простых множителей
3.3. Связь методов факторизации и переходные матрицы
3.4. Обобщение факторизации ДПФ на случай m множителей
3.5. Факторизация ДПХ дня произвольных множителей
3.6. Факторизация ДПХ для взаимно-простых множителей
3.7. Заключение
4. МЕТОДЫ ФАКТОРИЗАЦИИ БАЗОВЫХ МОДУЛЕЙ ДПФ
4.1. Вычисление ДПФ через циклическую сверху
4.2. Разложение модулей ДПФ на прямую сумму циркулярных матриц
4.3. Факторизация базовых модулей теоретико-числовых преобразований
4.4. Факторизация базовых модулей дискретного преобразования Хартли
5. БЫСТРЫЕ АЛГОРИТМЫ, ОСНОВАННЫЕ НА ФАКТОРИЗАЦИИ КРОНЕКЕРОВСКОГО ПРОИЗВЕДЕНИЯ БАЗОВЫХ МОДУЛЕЙ ДПФ
5.1. Построчно-столбцовый метод факторизации или алгоритм простых множителей
5.2. Гнездовой метод факторизации
5.3. Сравнение вычислительных характеристик алгоритма простых множителей и гнездового алгоритма
6. АЛГОРИТМЫ БПФ, СИНТЕЗИРОВАННЫЕ ПО МЕТОДУ ПРОИЗВОЛЬНЫХ МНОЖИТЕЛЕЙ
6.1. Алгоритмы БПФ по смешанному основанию
6.2. Алгоритмы БПФ по основнию r
6.3. Алгоритмы БПФ по основанию 3, 6, 12
7. АЛГОРИТМЫ БПФ РАЗМЕРНОСТИ N=2^n
7.1. Алгоритмы БПФ по основаниям 2, 4, 8 и 16
7.2. Алгоритмы БПФ с вещественными весовыми коэффициентами
7.3. Вычисление ДПФ через быстрое косинусное преобразование
7.4. Алгоритм БПФ с расщепленным основанием
7.5. Гибридные методы факторизации
7.6. Сравнительные оценки вычислительной сложности алгоритмов БПФ с N=2^n
7.7. Алгоритмы редуцированного БПФ
8. АЛГОРИТМЫ БПФ, ОРИЕНТИРОВАННЫЕ НА ВЕЩЕСТВЕННЫЕ ВХОДНЫЕ ДАННЫЕ
8.1. Алгоритмы БПФд с прореживанием по частоте (БПФд - f)
8.2. Алгоритмы БПФд с прореживанием по времени (БПФд — t)
8.3. Алгоритмы редуцированного БПФд
8.4. Алгоритмы БПФд для взаимно-простых множителей
9. БЫСТРЫЕ АЛГОРИТМЫ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХАРТЛИ
9.1. Алгоритмы БПХ по основанию 2
9.2. Алгоритмы БПХ по основанию 4
9.3. Алгоритмы БПХ с расщепленным основанием
9.4. Алгоритм редуцированного БПХ
9.5. Алгоритмы БПХ для взаимно-простых множителей
9.6. Заключение
10. БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ МНОГОМЕРНОГО ДПФ
10.1. Методы построения построчно-столбцовых алгоритмов БПФ-m
10.2. Методы построения гнездовых алгоритмов «квадратного» ДПФ-m
10.3. Методы построения гнездовых алгоритмов «прямоугольного» ДПФ-m
10.4. Методы построения алгоритмов БПФ-m для обработки вещественных данных
10.5. Синтез алгоритмов БПФ-m методом полиномиальных преобразований
10.6. Методы синтеза алгоритмов БПХ-m
11. БЫСТРЫЕ АЛГОРИТМЫ ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ
11.1. Алгоритмы ТЧП по основанию r по модулю простых чисел Ферма
11.2 Алгоритмы ТЧП по основанию l по модулю простых чисел Мерсенна
11.3. Алгоритмы ТЧП с расщепленным основанием
11.4. Алгоритмы ТЧП типа Рейдера-Бреннера
11.5. Теоретико-числовое преобразование Хартли
ЗАКЛЮЧЕНИЕ