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

М.: Мир, 1989. — 448 с.: ил. — ISBN: 5-09-001009-2.Книга американского специалиста, посвященная актуальным прикладным задачам построения быстрых алгоритмов цифровой обработки сигналов (автор известен по его «Теории и практике кодов, контролирующих ошибки» (М.: Мир, 1986) , PDF ). Для ускорения типичных для таких задач вычислений используется организация данных в виде конечных алгебраических структур (групп, колец, полей), что позволяет применить структурные теоремы алгебры и теории чисел. В двух из двенадцати глав книги содержится краткое, но строгое и систематическое изложение соответствующих разделов математики, как правило, недостаточно известных инженерам-прикладникам.
Для математиков-прикладников, программистов, инженеров — разработчиков систем обработки дискретных сигналов, студентов и аспирантов университетов.Введение
Введение в быстрые алгоритмы
Использование быстрых алгоритмов
Системы счисления для проведения вычислений
Цифровая обработка сигналов
История быстрых алгоритмов обработки сигналов
Задачи
Замечания
Введение в абстрактную алгебру
Группы
Кольца
Поля
Векторные пространства
Матричная алгебра
Кольцо целых чисел
Кольца многочленов
Китайские теоремы об остатках
Задачи
Замечания
Быстрые алгоритмы коротких сверток
Циклические и линейные свертки
Алгоритм Кука-Тоома
Алгоритмы Винограда вычисления коротких сверток
Построение алгоритмов коротких линейных сверток
Вычисление произведения многочленов по модулю некоторого многочлена
Построение алгоритмов коротких циклических сверток
Свертки в общих полях и кольцах
Сложность алгоритмов свертки
Быстрые алгоритмы дискретного преобразования Фурье
Алгоритмы Кули-Тьюки быстрого преобразования Фурье
Алгоритм Кули-Тьюки по основанию два
Алгоритм Гуда-Томаса быстрого преобразования Фурье
Алгоритм Герцеля
Вычисление преобразования Фурье с помощью свертки
Алгоритм Винограда для быстрого преобразования Фурье малой длины
Теория чисел и алгебраическая теория полей
Элементарная теория чисел
Конечные поля, основанные на кольце целых чисел
Поля, основанные на кольцах многочленов
Минимальные многочлены и сопряжения
Круговые многочлены
Примитивные элементы
Вычисления в суррогатных полях
Свертка в суррогатных полях
Числовые преобразования Фурье
Числовые преобразования Мерсенна
Алгоритмы свертки в конечных полях
Комплексная свертка в суррогатных полях
Преобразования в числовом кольце
Числовые преобразования Шевилла
Алгоритм Препараты-Сервейта
Быстрые алгоритмы и многомерные свертки
Гнездовые алгоритмы свертки
Алгоритм Агарвала-Кули вычисления свертки
Алгоритмы разложения
Итеративные алгоритмы
Полиномиальное представление расширений полей
Свертка в полиномиальных расширениях полей
Полиномиальное преобразование Нуссбаумера
Быстрая свертка многочленов
Быстрые алгоритмы многомерных преобразований
Алгоритмы Кули-Тьюки по малому основанию
Гнездовые алгоритмы преобразования
Алгоритм Винограда быстрого преобразования Фурье большой длины
Алгоритм Джонсона-Барраса быстрого преобразования Фурье
Алгоритм разложения
Улучшенный алгоритм Винограда быстрого преобразования Фурье
Перестановочный алгоритм Нуссбаумера-Квенделла
Архитектура фильтров преобразований
Вычисление свертки секционированием
Алгоритмы для коротких секций фильтра
Интегрирование секций фильтра
Симметрические и кососимметрические фильтры
Фильтры прореживания и интерполяции
Автокорреляция и взаимная корреляция
Устройства для вычисления БПФ
Преобразование Фурье ограниченного диапазона
Задачи
Замечания
Быстрые алгоритмы, основанные на стратегии дублирования
Стратегия деления пополам и дублирования
Структуры данных
Быстрые алгоритмы сортировки
Рекурсивное быстрое преобразование Фурье по основанию два
Быстрая транспозиция
Умножение матриц
Рекурсивный алгоритм Евклида
Вычисление тригонометрических функций
Задачи
Замечания
Быстрые методы решения теплицевых систем
Алгоритмы Левинсоиа и Дурбина
Алгоритм Тренча
Алгоритм Берлекэмпа—Месси
Рекурсивный алгоритм Берлекэмпа—Месси
Методы, основанные на алгоритме Евклида
Задачи
Замечания
Быстрые алгоритмы поиска по решетке и по дереву
Поиск по решетке и по дереву
Алгоритм Виттерби
Стек-алгоритм
Алгоритм Фано
Задачи
Замечания
Приложение А. Набор алгоритмов циклических сверток
Приложение Б. Набор малых БПФ-алгоритмов Винограда
Литература