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

Перевод с английского И. И. Грушко

Москва «Мир» 1989

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

Для математиков-прикладников, программистов, инженеров — разработчиков систем обработки дискретных сигналов, студентов и аспирантов университетов.

Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ.—М.: Мир, 1989.—448 с, ил.

Содержание книги
Быстрые алгоритмы цифровой обработки сигналов

Предисловие к русскому изданию
От автора
Предисловие

Глава 1. Введение
1.1. Введение в быстрые алгоритмы
1.2. Использование быстрых алгоритмов
1.3. Системы счисления для проведения вычислений
1.4. Цифровая обработка сигналов
1.5. История быстрых алгоритмов обработки сигналов
Задачи
Замечания

Глава 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. Построение алгоритмов коротких линейных сверток
3.5. Вычисление произведения многочленов по модулю некоторого многочлена
3.6. Построение алгоритмов коротких циклических сверток
3.7. Свертки в общих полях и кольцах
3.8. Сложность алгоритмов свертки
Задачи
Замечания

Глава 4. Быстрые алгоритмы дискретного преобразования Фурье
4.1. Алгоритм Кули - Тьюки быстрого преобразования Фурье
4.2. Алгоритм Кули - Тьюки по основанию два
4.3. Алгоритм Гуда - Томаса быстрого преобразования Фурье
4.4. Алгоритм Герцеля
4.5. Вычисление преобразования Фурье с помощью свертки
4.6. Алгоритм Винограда для быстрого преобразования Фурье малой длины
Задачи
Замечания

Глава 5. Теория чисел и алгебраическая теория полей
5.1. Элементарная теория чисел
5.2. Конечные поля, основанные на кольце целых чисел
5.3. Поля, основанные на кольцах многочленов
5.4. Минимальные многочлены и сопряжения
5.5. Круговые многочлены
5.6. Примитивные элементы
Задачи
Замечания

Глава 6. Вычисления в суррогатных полях
6.1. Свертка в суррогатных полях
6.2. Числовые преобразования Ферма
6.3. Числовые преобразования Мерсенна
6.4. Алгоритмы свертки в конечных полях
6.5. Комплексная свертка в суррогатных полях
6.6. Преобразования в числовом кольце
6.7. Числовые преобразования Шевилла
6.8. Алгоритм Препараты - Сервейта
Задачи
Замечания

Глава 7. Быстрые алгоритмы и многомерные свертки
7.1. Гнездовые алгоритмы свертки
7.2. Алгоритм Агарвала - Кули вычисления свертки
7.3. Алгоритмы разложения
7.4. Итеративные алгоритмы
7.5. Полиномиальное представление расширений полей
7.6. Свертка в полиномиальных расширениях полей
7.7. Полиномиальное преобразование Нуссбаумера
7.8. Быстрая свертка многочленов
Задачи
Замечания

Глава 8. Быстрые алгоритмы многомерных преобразований
8.1. Алгоритмы Кули - Тьюки по малому основанию
8.2. Гнездовые алгоритмы преобразования
8.3. Алгоритм Винограда быстрого вычисления преобразования Фурье большой длины
8.4. Алгоритм Джонсона - Барраса быстрого преобразования Фурье
8.5. Алгоритмы разложения
8.6. Улучшенный алгоритм Винограда быстрого преобразования Фурье
8.7. Перестановочный алгоритм Нуссбаумера - Квенделла
Задачи
Замечания

Глава 9. Архитектура фильтров и преобразований
9.1. Вычисление свертки секционированием
9.2. Алгоритмы для коротких секций фильтра
9.3. Итерирование секций фильтра
9.4. Симметрические и кососимметрические фильтры
9.5. Фильтры прореживания и интерполяции
9.6. Автокорреляция и взаимная корреляция
9.7. Устройства для вычисления БПФ
9.8. Преобразование Фурье ограниченного диапазона
Задачи
Замечания

Глава 10. Быстрые алгоритмы, основанные на стратегии дублирования
10.1. Стратегия деления пополам и дублирования
10.2. Структуры данных
10.3. Быстрые алгоритмы сортировки
10.4. Рекурсивное быстрое преобразование Фурье по основанию два
10.5. Быстрая транспозиция
10.6. Умножение матриц
10.7. Рекурсивный алгоритм Евклида
10.8. Вычисление тригонометрических функций
Задачи
Замечания

Глава 11. Быстрые методы решения теплицевых систем
11.1. Алгоритмы Левинсона и Дурбина
11.2. Алгоритм Тренча
11.3. Алгоритм Берлекэмпа - Месси
11.4. Рекурсивный алгоритм Берлекэмпа - Месси
11.5. Методы, основанные на алгоритме Евклида
Задачи
Замечания

Глава 12. Быстрые алгоритмы поиска по решетке и по дереву
12.1. Поиск по решетке и по дереву
12.2. Алгоритм Виттерби
12.3. Стек - алгоритм
12.4. Алгоритм Фано
Задачи
Замечания

Приложение А. Набор алгоритмов циклических сверток
Приложение Б. Набор малых БПФ - алгоритмов Винограда
Литература

ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ

Предлагаемая читателю книга известного американского специалиста в области теории информации и ее приложений Р. Блей-хута посвящена построению быстрых алгоритмов цифровой обработки сигналов — вычислительных алгоритмов, повсеместно возникающих в таких приложениях, как все виды связи, радиолокация, радиоастрономия, цифровая голография, медицинская электроника и т. п. Отсутствие подобной книги остро ощущалось многими специалистами в перечисленных областях — конструкторами информационных систем различного назначения. В частности, Р. Блейхут указывает, что он почувствовал ее необходимость во время работы над своей предыдущей книгой «Теория и практика кодов, контролирующих ошибки», в которую ему пришлось включить несколько специальных глав с описанием алгоритмов быстрого вычисления преобразования Фурье, которые, конечно, никак не зависят от данного конкретного приложения. (Книга была переведена в 1985 г. на русский язык и быстро разошлась.)

Хотя в настоящую книгу вошли и алгоритмы решения тепли-цевых систем уравнений (возникающих в таких приложениях, как линейное предсказание, построение авторегрессионных фильтров, теория кодирования и др.), и алгоритмы быстрого поиска по древовидному графу (возникающие, например, при декодировании сверточных кодов), сердцевиной книги являются быстрые алгоритмы преобразования Фурье и вычисления цифровой свертки (линейной и циклической).

В основе таких быстрых алгоритмов лежит специальная организация массивов данных в виде конечных алгебраических структур (групп, колец, полей), что создает предпосылки для применения структурных теорем алгебры и теории чисел. Это позволяет строить практически приемлемые алгоритмы, обеспечивающие работу цифровых процессоров в реальном масштабе времени. К настоящему времени накопился широкий ассортимент различных по своей архитектуре и теоретическим предпосылкам алгоритмов, но пока инженеры-разработчики и программисты не знакомы с их теоретическим обоснованием, вопрос о широком использовании этих алгоритмов остается открытым.

Данная книга весьма удачно ликвидирует образовавшийся разрыв. С одной стороны, в ней в двух из глав дается краткое, но строгое и систематическое изложение необходимых разделов алгебры и элементарной теории чисел, как правило, недостаточно известных инженерам-прикладникам. С другой стороны, в остальных 10 главах дается систематическое и исчерпывающее описание накопленных к настоящему времени быстрых алгоритмов преобразования Фурье, вычисления цифровых сверток и решения систем теплицевых уравнений не только для привычных в инженерной практике полей комплексных и вещественных чисел, но и для полей Галуа.

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

В. И. Сифоров

ПРЕДИСЛОВИЕ

В настоящее время цифровая обработка сигналов переживает взрыв. Ее используют повсюду, включая радиолокацию, сейсмографию, связь, радиоастрономию и медицинскую электронику. Активно разрабатываются и находят рыночный спрос цифровые процессоры — специализированные цифровые компьютеры для обработки сигналов. Такое широкое использование порождает еще более широкий спрос на цифровые процессоры, применяемые в некоторых случаях в массовых масштабах.

Одним из путей удовлетворения этих потребностей является выбор разумно построенных алгоритмов. Вместо того чтобы повышать быстродействие процессора от одного миллиона умножений в секунду до пяти миллионов умножений в секунду, можно для некоторых задач попытаться так организовать вычисления, чтобы быстродействия в один миллион умножений в секунду оказалось достаточно. К настоящему моменту имеется хорошо разработанная теория, позволяющая подойти к решению задач с этих позиций. Она хорошо известна теоретикам, специалистам в данной области, но на практике инженеры-конструкторы часто пренебрегают ей, поскольку она пока недоступна в виде цельного учебного курса. Инженер-конструктор должен хорошо знать предмет, чтобы выбрать алгоритм, нужный в данном конкретном приложении, среди смущающего разнообразия известных быстрых алгоритмов свертки или быстрого преобразования Фурье.

Данная книга является результатом курса, прочитанного автором в Корнеллском университете и корпорации ИБМ под названием «Быстрые алгоритмы цифровой обработки сигналов». Курс был построен с расчетом на стажирующихся инженеров-электриков и аспирантов первого года обучения; его целью было воспитание инженеров, которые свободно владеют предметом. Эта же цель является первой в данной книге.

Второй целью является формирование широкого взгляда на состояние работ в области быстрых алгоритмов цифровой обработки сигналов, который сможет стимулировать новые работы в будущем. Если собрать воедино все нити, то многое становится более очевидным. Например, перенесение БПФ-алгоритмов Кули—Тьюки, Гуда—Томаса и Винограда в произвольное поле облегчило понимание взаимосвязи между многими последующими идеями.

Я думаю, что важно различать быстрый алгоритм, функцию, которую он вычисляет, и приложение, в котором он используется. Это разные элементы, и, когда их смешивают, они могут терять свою ясность. Таким образом, я настаиваю на том, чтобы отличать дискретное преобразование Фурье от быстрого преобразования Фурье. Первое из них является преобразованием, а второе - алгоритмом для вычисления первого. Подобно этому, алгоритм, Витерби не является методом вычисления последовательности максимального правдоподобия; он представляет собой алгоритм вычисления кратчайшего пути на решетке — пути, который в некоторых приложениях будет путем максимального правдоподобия, но не обязан быть им.

Но и тогда, когда кратчайший путь действительно является путем максимального правдоподобия, не следует смешивать определение максимального правдоподобия с алгоритмом вычисления его пути. В соответствии с этим подходом в данной книге мало обсуждаются возможные приложения; после постановки задачи все внимание уделяется построению хорошего алгоритма ее решения. Обсуждение возможных приложений цифровой обработки сигналов следует искать в других источниках.

Идея написания этой книги возникла во время работы над более ранней книгой «Теория и практика кодов, контролирующих ошибки». Во многих главах этой книги приходилось рассматривать быстрые алгоритмы вычислений в конечных полях, хотя по существу алгоритмы не зависели от выбранного поля. Я почувствовал, что стоило бы поместить эти алгоритмы в отдельную книгу, описать их независимо от использования и дополнить многими другими важными в цифровой обработке сигналов алгоритмами. Изложение затрагивает многие области теории вычислений и теории алгоритмов. Однако в первую очередь нас интересуют инженерные задачи нахождения лучших алгоритмов цифровой обработки сигналов; асимптотический анализ играет второстепенную роль.

В настоящей книге используются разделы математики, которые могут быть незнакомы типичному читателю с инженерным образованием. Поэтому в книгу включен весь необходимый математический аппарат и строго доказываются все теоремы. Мне представляется, что если этому предмету предстоит стать самостоятельной и зрелой дисциплиной, то вся необходимая математика должна быть частью этой книги; ссылки на другие источники не могут быть адекватной заменой. Инженер не может уверенно овладеть предметом, если ему часто предлагается принять утверждение на веру или обратиться к своей математической библиотеке. Необходимая для построения быстрых алгоритмов математика содержится в гл. 2 и 5. Эти главы можно сначала прочитать бегло, но к ним следует возвращаться по мере необходимости.

Одним из недостатков, которые некоторые читатели заметят в книге, является недостаточность рекомендаций по практическому использованию алгоритмов. Такие темы, как длина машинного слова, погрешность округления и время работы алгоритма А на компьютере В, вообще не рассматриваются. Это сознательное решение вызвано тем, что я не столь мудр, чтобы делать широкие обобщения по этим вопросам. В немногих встречавшихся мне исследованиях на эти темы всегда рассматривались узко сформулированные задачи, и я не доверяю любому общему выводу, сделанному на основе имеющихся данных. Мне кажется, что конструктору следует решать эти вопросы в контексте конкретной задачи и непосредственно изучать литературу, чтобы узнать, как поступают в аналогичных случаях другие конструкторы.

Среди рассматриваемых настоящей книге алгоритмов многие уже широко используются в практической деятельности. Другие станут важны в будущих приложениях, когда цифровая обработка сигналов будет более разнообразной и широко применяемой. Некоторая часть, возможно, никогда не станет полезной. Я стремился дать широкий обзор; какие из методов окажутся практически важными, предстоит решить инженерам-конструкторам в следующие несколько десятилетий.

Сердцевиной книги являются описываемые в гл. 3 и 7 алгоритмы циклической свертки и описываемые в гл. 4 и 8 алгоритмы быстрого преобразования Фурье. В гл. 7 и 8 описываются многомерные аналоги алгоритмов гл. 3 и 4 соответственно, и при желании их можно читать сразу после этих глав. Изучение одномерных алгоритмов свертки и преобразования Фурье завершается лишь в контексте многомерных задач. Главы 2 и 5 представляют собой математические введения; некоторые читатели, возможно, предпочтут пользоваться ими как приложением, обращаясь к ним лишь по мере надобности. Главы 6 и 9 следует читать отдельно, следом за гл. 3 и 4. Главы 10, 11 и 12 в основном независимы; каждую из них вполне можно читать независимо от остального, материала книги.

Скачать книгу Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Издательство Мир, 1989