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

Е. Блейхут

БЫСТРЫЕ АЛГОРИТМЫ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

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

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

ББК 32.811

Б68 УДК 519.725

Блейхут Р.    

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

ISBN 5-09-001009-2

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

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

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

Глава 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