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

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

Turbobit.net:Скачать

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

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

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

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

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

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

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

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

В. Я. Сифоров

ОТ АВТОРА

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

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

Р. Э. Бмйхут

ОГЛАВЛЕНИЕ

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

От автора..........................................................7

Предисловие ........................................................8

Глава I. Введение ......................................12

1.1. Введение в быстрые алгоритмы..................12

1.2. Использование быстрых алгоритмов..............................17

1.3. Системы счисления для проведения вычислений..................20

1.4. Цифровая обработка сигналов....................................22

1.5. История быстрых алгоритмов обработки сигналов................29

Задачи..............................................................31

Замечания..........................................................32

Глава 2. Введение в абстрактную алгебру............................33

2.1. Группы........................................................33

2.2. Кольца..........................................................38

2.3. Поля ..........................................................43

2.4. Векторные пространства............................47

2.5. Матричная алгебра............................60

2.6. Кольцо целых чисел................ ...........58

2.7. Кольца многочленов.......................62

2.8. Китайские теоремы об остатка»...........................71

Задачи..............................................................76

Замечания............................. 77

Глава 3. Быстрые алгоритмы коротких сверток........................80

3.1. Циклические и линейные свертки................................80

3.2. Алгоритм Кука—Тоома........................................84

3.3. Алгоритмы Винограда вычисления коротких сверток..............90

3.4. Построение алгоритмов коротких линейных сверток ................98

3.5. Вычисление произведения многочленов по модулю некоторого многочлена ......103

3.6. Построение алгоритмов коротких циклических сверток............105

3.7. Свертки в общих полях и кольцах..............................111

3.8. Сложность алгоритмов свертки..................................ИЗ

Задачи..............................................124

Замечания............................................127

Глава 4. Быстрые алгоритмы дискретного преобразования Фурье. . . 128

4.1. Алгоритм Кули—Тыоки быстрого преобразования Фурье .... 128

4.2. Алгоритм Кули—Тьюки по основанию два......... 133

4.3. Алгоритм Гуда—Томаса быстрого преобразования Фурье..........141

4.4. Алгоритм Герцеля..............................................144

4.5. Вычисление преобразования Фурье с помощью свертки............147

4.6. Алгоритм Винограда для быстрого преобразования Фурье малой длины...........157

Задачи..............................................................167

Замечания..........................................................169


Глава 5. Теория чисел и алгебраическая теория полей....................170

5.1. Элементарная теория чисел....................................170

5.2. Конечные поля, основанные на кольце целых чисел................176

5.3. Поля, основанные на кольцах многочленов........................180

5.4. Минимальные многочлены и сопряжения........................182

5.5. Круговые многочлены..................... 183

5.6. Примитивные элементы..........................187

Задачи..................................189

Замечания..........................................................191

Глава 6. Вычисления в суррогатных полях............................192

6.1. Свертка в суррогатных полях....................................192

6.2. Числовые преобразования Ферма................................196

6.3. Числовые преобразования Мерсенна..............................198

6.4. Алгоритмы свертки в конечных полях............................202

6.5. Комплексная свертка в суррогатных полях........................206

6.6. Преобразования в числовом кольце..............................208

6.7. Числовые преобразования Шевилла......................213

6.8. Алгоритм Препараты—Сервейта..................................216

Задачи..............................................................217

Замечания..........................................................219

Глава 7. Быстрые алгоритмы и многомерные свертки....................220

7.1. Гнездовые алгоритмы свертки..................................220

7.2. Алгоритм Агарвала—Кули вычисления свертки....................226

7.3. Алгоритмы разложения........................................233

7.4. Итеративные алгоритмы..........................................237

7.5. Полиномиальное представление расширений полей................243

7.6. Свертка в полиномиальных расширениях полей....................246

7.7. Полиномиальное преобразование Нуссбаумера..................248

7.8. Быстрая свертка многочленов..................................252

Задачи..............................................................257

Замечания..........................................................258

Глава 8. Быстрые алгоритмы многомерных преобразований..........259

8.1. Алгоритмы Кули—Тьюки по малому основанию..................259

8.2. Гнездовые алгоритмы преобразования............................265

8.3. Алгоритм Винограда быстрого вычисления преобразования Фурье большой длины ....270

8.4. Алгоритм Джонсона—Барраса быстрого преобразования Фурье 277

8.5. Алгоритмы разложения ........................................280

8.6. Улучшенный алгоритм Винограда быстрого преобразования Фурье 286

8.7. Перестановочный алгоритм Нуссбаумера—Кэнделла..............287

Задачи..............................................................300

Замечания..........................................................302

Глава 9. Архитектура фильтров и преобразований......................303

9.1. Вычисление свертки секционированием............................303

9.2. Алгоритмы для коротких секций фильтра..........................310

9.3. Итерирование секций фильтра..................................312

9.4. Симметрические и кососимметрнческие фильтры....................317

9.5. Фильтры прореживания и интерполяции.......... 324

Похожие книги: