Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 2
Текст из файла (страница 2)
Д г ут удущих приложениях, когда цифровая обработка сигналов будет более. разнообразной н ширака применяемой. Некоторая часть, возможно, никогда не станет полезной. Я агре. чески важным, милуя дать широкий обзор; какие нз метадон окажутс утся арак«ими, предстоит решить инженерам-конструкто ам в следующие несколько десятилетий. рам Се ит .рдцевннай книги валяются описываемые в гл. 3 7 в гл. и алга. р мы циклической свергни и описываемые в гл. 4 и 8 быст го п соб азо и алгоритмы ра р разования Фурье. В гл. 7 и 8 описываются миогостаенно, и при же- мернме аналоги алгоритмов гл. 3 и 4 соответственно, лапин их можно читать сразу после этих глав.
Иэ чение р в гзерткн и преобразования Фурье завершается лишь в контексте многомерных задач. Главы 2 и б представляют «тателн, возможно, собой математнчесние введения; некоторые ч предпочтут пользоваться ими «ак при.чажением, обраща с щаясь к ним ре надобности. Главы б в 9 следует читать отдельно, следом за гл. 3 и 4. Главм 19, 1! и 12 в основном независимы; кзждую нз них вполне можно читать аезааисимо ат остального материала,«инги.
БЛАГОДАРНОСТИ Тем. что я написал дзваую книгу, л больше всего обязан Шиуэлю Винбграду Бсэ его существенного вклада в рассматринаечую область она была бы бесформенной н яамнога более короткой. Он щедро уделял мне время, проясняя чногнс моменты и аросматривая первоначальные наброски Статьи Винограда, а тзкже книга Нуссбаумера явля«отса источниками большей части машр»гала, обсуждаемого в этой книге. Книга не достиглз бы своего ныиепгнего уровня без неоднократных рецензировэнпй н критики Я особенно признателен профессору Б.
В. Диксону за несколько чрезвычайно падробнмх рецензий, которые сильна улучшили ее качество. Я также признателен профессору Тоби Бергеру, профессору К С Баррас!, профессору Дж, !'нбсону, профессору Дж. Г. Проакису, про. фессору Т. Б. Парксу, доктору Б. Райсу, профессору И. Сугияме, доктору В Ваидеркулку и профессору Дж. Вергеэе эз валезную критику. Книга не была бы написана без поддержка компзнпи «Интервейшнал Б««энес Машина». Я глубоко благодарен ИБ«И за зту полдер«кку, а также Кариеллскому унпверсигегу за предоставленную возможность апробации первого варианта рукописи с помощью «урса лекпий. Самую важную поддержку мне оказала иоя жена Барбара, без помощи которой эта кинга никогда не была бы написана.
гз В» а а б С РИЕ а ГОРЮжэ Глава 1 ВВЕДЕНИЕ Вычислительные алгоритмы встречаются повсеместно, и эф. фективные варианты таких алгоритмов весьма высоко ценятся я теми, кто ими пользуется Мы рассматриваем в основном толь скоторые тяпы вычислений, а именно те, которые связаны с цифио раной обработкой сигналов в включают такие задачи, как цифровая фильтрация, дискретное преобразование Фурье, корреляция и спектральный анализ Наша основная цель состоит в описании современных методов цифровой реализации этих вычислений. рнчсч . интересует не построение весовых множителей в от.
водах цифрового филыра, а органнззция способа нх вычисления при реализации филшра. Нас также не интересует, зачем кому.то нужно, скажем, дискретное преобразование Фурье; нас заботит только та, кап могкво вычислить эта преобразование эффективно Удивителыю, что для решения столь узко специального вопроса разработз|га столь глубоко развитая теория. ).). Введение в быстрые алгоритмы Люб й можи ° юбой алгоритм, подобно большинству инженерных у й устро ств, о описывзть либо через соотношение между входом и выходом, либо детально обьясвяя его внутреннюю структуру.
П нменяя к некоторой новой задачеметоды цифрпной обработки сигна. лов,мм сталкиваемся с заданием алгоритмов через соотношение вход. выход При заданном сигнтле нли записанных некоторым образом данник основное внимание сосредоточивается на том, что надо с этими данными сделать, г, е каков должен быть выход алгоритма, если на сто акад подаются те илн иные данные. Примерами такого выхода служат профильтрованная версия входа или его преобразование Фурье. Такая связь вхола с выходом в алгоритме математически мажет быть записана без детального вы.
писываиия всех шагов, веобходнмых для выполнения вычислений. , опирающейся на вход. выход точки зрения, сама задача построения хороших алгоритмов обработки информации может быть трудной и тапкой. но в данной книге она не рассматривается Мы предполагаем что уже задан злгорнтм типа вход-выход, описанный в терминах фильтров, преобразований Фурье, интерполянкй, прорежиианий, корреляций, модуляций, гистограмм, матричных операций н им подобных. Все такие алгоритмы могут быть записаны математической формулой, н, следовательно, вычисаены в прямом соответствии с этой записью.
Такую реализа. цию алгоритма вычислений будем называть прямой. Кто то может быть вполне удоилетворен прямой реализацией алгоритма; в течение многих лет большинство пользователей очи. тали такие реализзции удовлетворительными, и даже сейчас некотороые нз ннх так считают. Но с тех пор, как люди начали решать подобные задачи, другие люди изчали искать более эффектиавые пути нх решения.
Именна эту историю мы хотим рассказать — историю быстрык алгоритмов. Под быстрыми алгаритмамн мы повимаеи детальное описание вычислительной процедуры, которая не является очевидным способом вычисления выхода па данному вкоду. Как правило, быстрый алгоритм жертвует кои. цсптуальной ясностью вычислений в пользу их эффективности. Дону тим, то гребу тс вычислить число А, равное А = ю+ш(.(-Ьа.(-Ы. В том виде, как оно записано, это нычнсленне содержит четыре умножения и три сложения. Если число А нада вычислять много раз для различных множеств данных, то мы быстро заметим, что А = (а ф Ь) (с -)- б) представляет собой эквивалентную форму, требующую лишь одного умножения и двух сложений, так что она предпочтительнее исходной. Этот простенький пример весьма тривиален, но он на самом деле нллюстрируег большинство тем, о которык иам предстоит рассгждзть.
Все, что мы делаем, можно представлять себе как хитроумную расстановку скобок в вмчислениях. Но для больших задач быстрые алгоритмы не удается найти простым просмотром вычислений; ик построение потребует весьма развитой теории. Нетривиальным, хот» все еще простым прииером служит быстрый алгоритм вычисления произведения комплексных чисел. Произведение комплексных чисел (е з ())= (а+гЫ ° (с+гб) можно записать через умножения и сложения выцествениых чисел: е = ос — Ьб, 1 = лб + Ьс, Эти формулы содержат четмре вещественных умножении и два вещественных сложения. Если умножение более трудоемкая апе- тб Ы Гл.
1. Втдтзе 11, Вв д е з В«тиме злг р рация, чем сложение, то более «эффективный алгоритм дае. я равенствами е=(а — Ь)б 1-а(с — б), 1 = (а — Ь) б й Ь (с -, 'б). В такой форме алгоритм содержит три вепгествеаиых умножения и пять вещественных сложений Вели в серии умножений комп- лексных чисел величины с и б суть константы, то члены с и с — б также являются «оастантами, и их можно зычисллпь зараню, независимо от прапесса умножения. Тогда для вычисле- ния одного произведения коннлексных чисел нам понадобится три вещественных умножения и три вещественных сложения.
Мы обменяли адно умножение на одно сложение. Это может быть пелесоабразно, юлька если в конструкции процессора уда- стся воспользоваться этим преимуществом Некоторые процес- соры скансгруироианы в расчете на использование четырех ве- щественных умножений Лля вычислен«« произведения комплекс- нык *1исел; в агом случае преимущества улучшевнаго алгоритма терн :я. Прелваряя дальнейшие рассмотрения, залержимся на этом при- мере потольше.
Рассиотреиное выше умножение иомплексных чисел можно представить в виде ~'3=~' ."3И тле вектор (а, Ыг представляет «омплексное число а .(- )Ь, (с матрица [б 1 представляет комплексное число с -1- М и веке~ тор 1г, 1)г представляет «очплекснае число е -1- (А Тиков матрич- но-векторное произведение является одной из фарм записи про- изведения комплексных чисел. Другой аагорим дается матричным равенством (и;,)[ ' ':1[' ']() которое можно рассматривать как необычную форму разложения матриши (;-ли,;)['р ' ' '[[' '1 В сокращенной записи алгоритм дается равенством ~ —. ВВА [ Ь ~, где А — матрица размера 3х2, каюрую мм назовем матрицей предсложеиий; Π— диагональная матрица размера Зх 3, нагорая в«лючает в себя асс общие умножения алгоритма, и  — матрица размера 2х 3, ноторую мы назовем магри«ей постслажений.
Мы увидим, чта многие из лучших процедур вычисления сверг. ки и дискретного преобразования Фурье могут быть приведенм к такому же матричному виду, и катаром не«трельная матрица ивляегся диагональной, а стоящие по ее бокам матрицы содержат в качестве своих элементов юлька О и Ф 1. Структура таких быстрых алгорнтлюв сводится к серии сложений, за которой следует серия улгножений, за которой следует другая серия сложений. В качестве паследнега примера этога вводного раздела рассмотрим быстрый алгоритм умножения матрицы. Путь С = АВ, где А и  — матрицы размеров (1хп) и (лхт) соответственна. Стандартное правила вычисления матрицы С дается правилами са= 2) апбы, 1=1....,1, )=1,", т, и содержит в соответствии с этой записью л(ш умножений и (л— — 1) йл сложений.
Мы построим алгоритм, который почти в два раза уменьшает число умножений, но увеличивает число сложений, таи что общее гисла операций слегка возрастет. Воспользуемся применительво к элементам матриц А и В таждесгиом а,Ь, -(-а,Ь, = (а, -(-Ь,) (л, -1-Ь,) — а,а, — Ь,Ь,. Предположим, чта л четио (в противном случае можно, не меняя произведения С, дополнить матрицу А нулеными строками, а матрицу В нулевыми столбцами). Применяя выписанное тож- дество и парам стран матрицы А и к парам столбцов матрицы В, запишем м сгт = Хюз («1,1« 1+Ьзь,т) (ал,т+ Ьт-л.д 1-1 гз и 1 = 1, ..., 1, — Хз а1,т,л1, л — хюз Ьль-л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
