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

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

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

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

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

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

Допустим, что требуется вычислить число Л, равное

А = ас -\- ad + be -\- bd.

В том виде, как оно записано, это вычисление содержит четыре умножения и три сложения. Если число А надо вычислять много раз для различных множеств данных, то мы быстро заметим, что

А = (а+Ь)(с +d)

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

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

(е +iO = (а + ib)- (с +id)

можно записать через умножения и сложения вещественных чисел:

е = ас - bd, f = ad -\- Ьс.

Эти формулы содержат четыре вещественных умножения и два вещественных сложения. Если умножение более трудоемкая one-

эффективный алгоритм дае.;!

рация, чем сложение, то более равенствами

е = {a - b)d +a{c~d), f = (a - b)d + b{c + d). В такой форме алгоритм содержит три вещественных умножения и пять вещественных сложений. Если в серии умножений комплексных чисел величины cud суть константы, то члены с + d и с - d также являются константами, и их можно вычислить заранее, независимо от процесса умножения. Тогда для вычисления одного произведения комплексных чисел нам понадобится три вещественных умножения и три вещественных сложения.

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

Предваряя дальнейшие рассмотрения, задержимся на этом примере подольше. Рассмотренное выше умножение комплексных чисел можно представить в виде

где вектор с

матрица

Ь] представляет комплексное число а +/6, представляет комплексное число с + /d и вектор [е, fV представляет комплексное число е + . Такое матрич-но-векторное произведение является одной из форм записи произведения комплексных чисел.

Другой алгорим дается матричным равенством с -d О О 1 Г1 О О c+d О О 1 0 О dJLl-1 которое можно рассматривать как необычную форму разложения матрицы;

(с - d) О О ] Г 1 О О (c + d) О О 1 О О dj[l -1

В сокращенной записи алгоритм дается равенством

где А - матрица размера 3x2, которую мы назовем матрицей предсложений; D - диагональная матрица размера 3x3, которая включает в себя все общие умножения алгоритма, и В - матрица размера 2X3, которую мы назовем матрицей постсложений.

Мы увидим, что многие из лучших процедур вычисления свертки и дискретного преобразования Фурье могут быть приведены к такому же матричному виду, в котором центральная матрица является диагональной, а стоящие по ее бокам матрицы содержат в качестве своих элементов только О и ±1. Структура таких быстрых алгоритмов сводится к серии сложений, за которой следует серия умножений, за которой следует другая серия сложений.

В качестве последнего примера этого вводного раздела рассмотрим быстрый алгоритм умножения матрицы. Пусть С = АВ, где А и В - матрицы размеров (1хп) и (nxm) соответственно. Стандартное правило вычисления матрицы С дается правилами

1 = 1.....1, 1 = 1,..., т,

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

Воспользуемся применительно к элементам матриц А и В тождеством

аА + <hbi = ( i + Ьг) (Oj + bi) - аа, - b.

Предположим, что п четно (в противном случае можно, не меняя произведения С, дополнить матрицу А нулевыми строками, а матрицу В нулевыми столбцами). Применяя выписанное тождество к парам строк матрицы А и к парам столбцов матрищл В, запишем

Оц = S (йг, 26-1 + Ьа. j) (Of, 2ft + hh-i. ij -

*=i t=i / - .....

Такая форма вычислений экономит умножения, поскольку второй член зависит только от i и его не надо перевычислять для каждого /, а третий член зависит только от ; и его не надо перевычислять для каждого i. Полное число умножений, необходимых для такого вычисления матрицы С, равно (1/2) п1т + 4- (1/2) п{1 + т), а полное число сложений равно (3/2) я/т + + /т + (п/2 - 1) (/ + т). Для матриц большого размера это

Алгоритм

Прямое вычисление

дискретного преобразования Фурье 1000X1000 БПФ-алгоритм Кули-Тьюкн

1024X1024 Гибридный БПФ-алгоритм Кули-Тьюки/Вннограда 1000X1000 БПФ-алгорнтм Винограда

1008Х 1008 БПФ-алгоритм Нуссбаумера-Кйендалла 1008Х1008

Рис. 1.1. Сравнение характеристик некоторых двумерных алгоритмов преобразования Фурье.

составляет примерно половину числа умножений, необходимых в прямом алгоритме.

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

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

выходе от шести до четырех может показаться не очень существенным после того, как уже получено уменьшение от сорока до шести. Но это недальновидная тЪчка зрения. Это дальнейшее улучшение может вполне окупить затраты времени на разработку Алгоритма при построении больших систем.

Рис. 1.1 содержит другой важный урок. Вход таблицы, обозначенный как гибридный БПФ-алгоритм Кули-Тьюки/Винограда, соответствует алгоритму вычисления двумерного (1000x1000)-точечного преобразования Фурье, в котором на каждую точку сетки на выходе требуется 40 вещественных умножений. Этот пример может помочь развеять злополучный миф о том, что дискретное преобразование Фурье применимо только тогда, когда длина блока равна степени двух. На самом деле возможность цифровой обработки сигналов не ограничивается только такими длинами блоков; для многих значений длин блоков имеются хорошие алгоритмы.

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

Сверхбольшие интегральные схемы, называе\ш1е чипами, теперь стали доступными. Чип может содержать порядка 100 ООО логических элементов, и поэтому неудивительно, что теорию алгоритмов часто рассматривают как способ эффективной организации этих элементов. Иногда выбор алгоритма позволяет существенно улучшить характеристики чипа. Конечно, их можно также улучшить, увеличив размер чипа или повысив его быстродействие; эти возможности более широко известны.

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

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