раньше. Указанная публикация [51 появилась как раз в нужный момент и послужила катализатором применения метода цифровой обработки сигналов в новом контексте. Вскоре после опубликования этой работыСтогхем 161 заметил, что БПФ-алгоритмы могут служить удобным способом вычисления сверток. Технология цифровой обработки может непосредственно использовать ВПФ, так что имеется множество приложений, и поэтому работа Кули и Гьюки стала ширко известной. Лишь несколько лет спустя было осознанно, что другой БПФ-алгоритм, сильно отличающийся от алгоритма Кули-Тьюки, был разработан раньше Гудом 171 (1960) и Томасом [81 (1963). В свое время публикация БПФ-ал-горитма Гуда-Томаса прошла почти незамеченной. Позже Виноград [9, 101 (1976, 1978) опубликовал свой более эффективный, ?iOTH и более сложный, БПФ-алгоритм, который к тому же позволил значительно глубже понять, что в действительности озна- чает процесс вычисления дискретного преобразования Фурье.

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

Различные вариации БПФ-алгоритма Кули-Тьюки появились во многих обличьях. По существу та же самая идея используется для построения многолучевой плоско-фазированной радио-.токационной антенны и известна под названием матрицы Батлера [111 (1961).

Для малых длин блоков быстрые алгоритмы сверток были чпервые построены Агарвалом и Кули [12] (1977) с использованием остроумных догадок, но не на основе общего метода. Общий метод построения быстрых алгоритмов свертки описал Виноград [101 (1978), доказав при этом важные теоремы несуществования .(учших алгоритмов свертки для полей комплексных и вещественных чисел. Агарвал и Кули [121 также указали основанный на китайской теореме об остатках метод разбиения задачи вычисления длинных сверток на задачи вычисления коротких сверток. Их метод в сочетании с методом Винограда, применяемый для вычисления коротких сверток, дает хорошие результаты.

Самая ранняя идея того, что мы предпочитаем называть быстрыми алгоритмами, появилась намного раньше, чем БПФ-алгоритмы. Алгоритм Левинсона 1131 был опубликован в 1947 г. как эффективный метод 4)ешения некоторых теплицевых систем уравнений. Несмотря на чрезвычайную важность этого алгоритма

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

Задачи

1.1. Построить алгоритм 2-точечной вещественной циклической свертки

{s,x -f*so) = (gix + g ) id,x + d ) (mod x-\),

содержащий два умножения и четыре сложения. Относящиеся к g и вычисления не учитывать, полагая нх константами, для которых все вычисления выполняются заранее раз и навсегда.

1.2. Опираясь на задачу 1.1, построить алгоритм 2-точечной комплексной свертки, содержащий только щесть вещественных умножений.

1.3. Построить алгоритм 3-точечного преобразования Фурье

k = Q, I. 2.

в котором имеется только два вещественных умножения.

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

1.5.а. Допустим, что имеется устройство вычисления линейной свертки двух 50-точечных последовательностей. Описать, как это устройство может быть использовано для вычисления циклической свертки двух 50-точечных последовательностей.

б. Допустим, что имеется устройство для вычисления циклической свертки двух 50-точечных последовательностей. Описать, как это устройство может быть использовано для вычисления линейной свертки двух 50-точечных последовательностей. I.e. Доказать, что корреляцию можно вычислять как свертку, записывая одну из последовательностей в обратном порядке и, возможно, пополняя одну из последовательностей отрезком нулей.

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

1.8. Один из алгоритмов вычисления произведения комплексных чисел дается равенствами

е= ас - bd,

f=(a-\-b)ic-\-d)~ac~bd.

32 Гл. 1. Введение

Записать этот алгоритм в матричном виде, подобно тому, как это сделано в тексте главы. Каковы недостатки или преимущества этого алгоритма по сравнению с приведенным выше? 1.9. Доказать свойство сдвига для преобразований Фурье: если (t)} (Id) являются парой преобразования Фурье, то парами преобразования Фурье также являкп-ся

1.10. Доказать, что циклическая корреляция двух вещественных последовательностей g и d удовлетворяет соотношению 1-л

где G и D соответственно преобразования Фурье последовательностей g и d. Замечания

Хорошее изложение начала истории быстрых алгоритмов преобразования Фурье содержится в статье Кули, Левнса и Велча (1) (1967). Основы теории цифровой обработки сигналов можно найти во многих книгах; укажем две из них: Оппенгенм и Шафер (2) (1975) и Рэбинер и Голд (3] (1975).

Алгоритмы умножения комплексных чисел, содержащие три вещественных умножения, в общем стали известны с конца 19S0-X, но поначалу им не придавали должного значения. Описанный нами алгоритм умножения матриц принадлежит Винограду 14) (1968).

Глава 2

ВВЕДЕНИЕ В АБСТРАКТНУК

Хорошие алгоритмы основаны на красивых алгебраических тождествах. Для построения таких алгоритмов необходимо знакомство с мощными структурами теории чисел и современной ал-. гебры. Такие структуры, как множество целых чисел, кольца многочленов и поля Галуа, играют важную роль в построении алгоритмов обработки дискретных сигналов. В настоящей главе излагаются алгебраические сведения, которые необходимы для дальнейшего, но, как правило, неизвестны студентам, специализирующимся в области обработки дискретных сигналов. Сначала изучаются математические структуры групп, колец и полей. Мы увидим, что дискретное преобразование Фурье может быть определено в произвольном поле, хотя наиболее известно его определение в поле комплексных чисел. Затем будут рассмотрены известные понятия матричной алгебры и векторных пространств. Мы покажем, что их можно корректно определить для любого поля. Наконец, мы изучим кольцо целых чисел и кольца многочленов, уделяя особое внимание алгоритму Евклида и китайской теореме об остатках.

2.1. Группы

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

Определение 2.1,1. Группой в называется множество элементов с определенной на нем операций (обозначаемой ), которая удовлетворяет следующим четырем свойствам:

(1) {Замкнутость.) Для каждой пары элементов а и b т этого множества элемент с = а* b принадлежит этому множеству.

(2) (Ассоциативность.) Для всех элементов а, 6 и с из этого множества

а* {Ь*с) = {а*Ь) *с.

2 Блейхут Р.

I 8, 1 .

1 J I 4

I г j 84 е

li I 84 8

8l 8. f 8i 8j

4 с 8i ! 8,

0 12 3 4

0 12 3 4

1 2 3 4 0

2 3 4 0 1

3 4 0 1 2

4 0 12 3

Рис. 2.1. Пример конечной грулпы.

(3) (Существование единицы.) В этом множестве существует элемент е, называемый единичным з.ге.чентом, такой что

а* е е* а = а

для любого элемента а рассматриваемого множества.

(4) {Обратимость.) Для любого а из данного множества существует (называемый обратным к а) некоторый элемент b из этого множества, такой что

а* b - Ь* а = е.

Если G содержит конечное число элементов, то она называется конечной группой. Число элементов в конечной группе G называется ее порядком. На рис. 2,1 приведен пример конечной группы. По существу здесь представлена одна и та же группа, но в разных обозначениях. В случае когда две группы описываются одной и той же структурой, хотя и в разных обозначениях, они называются изо.морфньши ).

Некоторые группы обладают тем дополнительным свойством, что для любых а и b из такой группы

а Ь = Ь*а.

Это свойство называется коммутативностью. Группы, обладающие этим дополнительным свойством, называются коммутативными группами, или абемвыми группа.чи. Мы всегда будем иметь дело с абелевыми группами.

В случае абелевых групп знак групповой операции обозначается плюсом и называется сложением (даже тогда, когда операция не является обычным арифметическим сложением), В этом случае единичный элемент е называется нулем и обозначается О, а обратный к а элемент записывается в виде -а, так что а + (~а) = (~а) + а = 0.

Иногда символ групповой операции обозначатеся точкой и называется умножением (даже тогда, когда оно не является обыч-

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

ным умножением). В этом случае единичный элемент называется единицей и обозначается 1, а обратный к а элемент записывается в виде а , так что

о-а = fl -a = 1.

Теорема 2.1.2. Единичный элемент в каждой группе единствен. Для каждого элемента группы обратный элемент также единствен, и (а ) = а.

Доказательство. Предположим, что е и г являются единичными элементами. Тогда е = е*е = е. Далее предположим, что Ь Ь являются элементами, обратными к а; тогда

b = b* (a*b) = (b*a) *b = b. Наконец, a а = а a = e, так что a является обратным к о . Но в силу единственности обратного элемента (cГ)~ = а.О

Многие общеизвестные группы содержат бесконечное число элементов. Примерами являются: множество целых чисел с операцией сложения; множество положительных рациональных чисел с операцией умножения ). множество вещественных (2x2)-матриц с операций сложения. Многие другие группы содержат только конечное число элементов. Конечные группы могут быть устроены весьма хитро.

Если групповая операция применяется два или более раз к одному и тому же элементу, то можно использовать степенное обозначение. Таким образом, а = а*а и а* = а*а* ... *а,

где справа стоят k копий элемента а.

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

G= \cfi. аК 0=.....а -].

где i; - порядок G. а - образующая, а а° - единичный элемент, а обратный к а элемент равен а?-. Чтобы можно было на самом деле задать группу таким способом, необходимо, чтобы выполнялось равенство а = а . Это вытекает из того, что в противном случае, если а = а при i ф О, то а - = a- и в противоречие с определением мы получаем меньше, чем q, элементов.

1) Этот пример дает удобный повод, чтобы сделать предостережение по поводу терминологии. В случае произвольной абелевой группы групповая операция обычно называется сложением, но не обязательно является обычным сложением. В данном примере она является обычным умножением.