Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов

М.: Мир, 1989. - 448 с., ил.
Книга американского специалиста, посвященная актуальным прикладным задачам построения быстрых алгоритмов цифровой обработки сигналов (автор известен по его «Теории и практике кодов, контролирующих ошибки» (М.: Мир, 1986)). Для ускорения типичных для таких задач вычислений используется организация данных в виде конечных алгебраических структур (групп, колец, полей), что позволяет применить структурные теоремы алгебры и теории чисел. В двух из двенадцати глав книги содержится краткое, но строгое и систематическое изложение соответствующих разделов математики, как правило, недостаточно известных инженерам-прикладникам.
Для математиков-прикладников, программистов, инженеров — разработчиков систем обработки дискретных сигналов, студентов и аспирантов университетов.
Оглавление:
Введение
Введение в быстрые алгоритмы
Использование быстрых алгоритмов
Системы счисления для провеления вычислений
Цифровая обработка сигналов
История быстрых алгоритмов обработки сигналов
Задачи
Замечания

Введение в абстрактную алгебру
Группы
Кольца
Поля
Веторные пространства
Матричная алгебра
Кольцо целых чисел
Кольца многочленов
Китайские теоремы об остатках
Задачи
Замечания

Быстрые алгоритмы коротких сверток
Циклические и линейные свертки
Алгортм Кука-Тоома
Алгоритмы Винограда вычисления коротких сверток
Построение алгоритмов коротких линейных сверток
Вычисление произведения многочленов по модулю некоторого многочлена
Построение алгоритмов коротких циклических сверток
Свертки в общих полях и кольцах
Сложность алгоритмов свертки


Быстрые алгоритмы дискретного преобразования Фурье
Алгоритмы Кули-Тьюки быстрого преобразования Фурье
Алгоритм Кули-Тьюки по основанию два
Алгоритм Гуда-Томаса быстрого преобразования Фурье
Алгоритм Герцеля
Вычисление преобразования Фурье с помощью свертки
Алгоритм Винограда для быстрого преобразования Фурье малой длины

Теория чисел и алгебраическая теория полей
Элементарная теория чисел
Конечные поля, основанные на кольце целых чисел
Поля, основанные на кольцах многочленов
Минимальные многочлены и сопряжения
Круговые многочлены
Примитивные элементы

Вычисления в суррогатных полях
Свертка в суррогатных полях
Числовые преобразования Фурье
Числовые преобразования Мерсенна
Алгоритмы свертки в конечных полях
Комплексная свертка в суррогатных полях
Преобразования в числовом кольце
Числовые преобразования Шевилла
Алгоритм Препараты-Сервейта

Быстрые алгоритмы и многомерные свертки
Гнездовые алгоритмы свертки
Алгоритм Агарвала-Кули вычисления свертки
Алгоритмы разложения
Итеративные алгоритмы
Полиноминальное представление расширений полей
Свертка в полиномиальных расширениях полей
Полиномиальное преобразование Нуссбаумера
Быстрая свертка многочленов

Быстрые алгоритмы многомерных преобразований
Алгоритмы Кули-Тьюки по малому основанию
Гнездовые алгоритмы преобразования
Алгоритм Винограда быстрого преобразования Фурье большой длины
Алгоритм Джонсона-Барраса быстрого преобразования Фурье
Алгоритм разложения
Улучшеный алгоритм Винограда быстрого преобразования Фурье
Перестановочный алгоритм Нуссбаумера-Квенделла

Архитектура фильтров преобразований
Вычисление свертки секционированием
Алгоитмы для коротких секций фильтра
Итерирование секций фильтра
Симметрические и кососимметрические фильтры
Фильтры прореживания и интерполяции