444 Предметный указатель

- многочленов 62

- ~ по модулю р (х) 180

- с единицей 39

- целых чисел 58 коммутативность 34 корень МЕГогочлена 70 корреляция 24

- взаимная 327

- циклическая 32 кронекеровское произведение (матриц) 53

левый смежный класс 38 лидер смежного класса 38 линейная зависимость векторов 50

- комбинация векторов 49

- свертка 23 линия задержки 22

матрица 50

- вырожденная 51

- главная диагональ 51

- единичная 51

-, канонический ступенчатый вид 56

- квадратная 50

- невырожденная 5[

- обменная 5[

- персимметричная 380 -, побочная диагональ 51

- сопровождающая 115

- теплицева 54, 373

- транспонированная 51

- элемептарная 55

машина с конечным числом состояний 402

метод перекрытия с накоплением 304

--- суммированием 307

метрика 405

- Фано 412 минор 52 многочлен 62

- круговой 184

- минимальный 182

- неприводимый 63

- нулевой 62

- приведенный 62

- простой 63

-, формальная производная 64

наибольший общий делитель (НОД) 58, 63

наименьшее общее кратное (НОК) 58, 63

начало координат 48

нулевое пространство матрицы 56

иуль группы 36

- поля 43

обратимость 34 обратимый элемент 40, 42 обратный элемент 34

---, левый 40

--, правый 40

определитель (матрицы) 51 ортогональное дополнение 49 ортогональный вектор 49 очередь 348

перекрытия метод 27 переменная 115

- неопределенная И 5 подгруппа 36 подполе 46

- констант 114 поле 43

- вычисления 114

- Галуа 44

- конечное 44

-, характеристика 46 порядок группы 34

- элемента 37, 172 потомок 348 правило Горнера 144 правый смежный класс 38 преобразование полиномиальное 243,

- Нуссбаумера 248 преобразование Фурье см. дискретное

преобразование Фурье (ДПФ)

--рекурсивное по основанию 2 352

-- свойства 76

- числовое Мерсенна 198

--Ферма 196

примитивный элемент поля 47 произведение внешнее 54

- групп 36

- кронекеровское 53

- на скаляр 47

- подкомпонентное 48

- скалярное 48 пространство векторное 47

- столбцов матрицы 56

- строк матрицы 56

размерность векторного пространства 49

ранг матрицы 57

--по столбцам 56

--по строкам 56

расстояние 405

- евклидово 405

-, расходимость 407 расширение поля 46 регистр сдвига 22 рекурсивная процедура 344

Предметный указатель

решетка 403

-, диаграмма состояний 404

-, длина кодового ограничения 403

- маркированная 405

свертка двумерная 220--222

- линейная 22, 80

- по секциям 308

- циклическая 24, 81

свойства преобразования Фурье 76 скаляр 47, 62, 115 смежный класс 37

-- левый 38

-- правый 38

список 347

- двойной связанный 349

- обратный 348

- связанный 349 сравнение по модулю 59, 65 стек 348

- алгоритм 410 степень многочлена 62 стратегия дублирования 341 сумматор 22

существование единицы 34 такт 22

теорема о свертке 29 теплицева матрица 54, 379

- система уравнений 372 транспозиция 52 , транспонированная матрица 51 трансформационный принцип 310

факторкольцо 176 фильтр 22

- авторегрессионный 22, 27

- интерполяционный 324

- кососимметрнческий 319

- прореживания 324

- с восстановлением 324

- симметрический 319

- с конечным импульсным откликом

(КИО) 22

- с подавлением 324 фильтрация секционная 305 функция Эйлера 170

характеристика кольца 40

- поля 46

целый элемент кольца 40 цепочка 348 цикл 37

циклическая группа 35 чип 17

числа взаимно-простые 58

- Шевилла 213 число простое 58

- - Мерсенна 195

- - Ферма 195

- трансцендентное 183

числовое преобразованиеМерсенна 198

--Ферма 196

--Шевилла 213

элемент единичный 34

- образующий 34

- обратимый 40

- обратный 34

- примитивный поля 47, 187

- сопряженный 183

- целый кольца 40 элементарные операции над строками

матрицы 55

ОГЛАВЛЕНИЕ

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

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

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

Глава 1. Введение......................... 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. Матричная алгебра....................... 50

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

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

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

Задачи............................... ?б

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

Глава 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 1. Элементарная теория чисел...........

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

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

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

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

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

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

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

170 176 180 182 184 187 189 191

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

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

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

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

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

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

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

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

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

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

Замечания............................. 2!9

...... 220

е свертки .

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

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

й........... 303

Глава 9. Архитектура фильтров и преобра;

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

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

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

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

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