Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов
Описание файла
DJVU-файл из архива "Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов", который расположен в категории "". Всё это находится в предмете "цифровая обработка сигналов (цос)" из 8 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "цифровая обработка сигналов" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла
Р Блейхут Переаод с английского И. 1Р Грушко Москва кМирн 1989. Рая! А!дог!!!ппа $ог Рфива! Яапа! Ргогеая1пд й1с1уаго Е. В!а1ш1 БЫСТРЫЕ АЛГОРИТМЫ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ Бвк щ.вы Бзз РДК издщ ПРВДИСЛОВИВ К РУССКОМУ ИЗДАНИЮ Блейхут Р. Б58 Быстрые алгоритмы цифровой обработкн сигналов: Пер. о англ. — М; Мяр, 1989. — 448 с., нл.
15ВР) 5-09-00!009-2 Кнн э «мерз Р ' Р ы б ср х лшг юфга В бг б снгяюо (ззтар зж ю а ш Тюрин я Р «юое, «Р юрг Ынхашшю (М.М р.«ЯЩ)).Д яускаре ч хЮ к х««зж ююзхс рухтур(ру . п,па*0), та тпгн.ю ть«гу уг. шеу я х рззл«лю е тнк, к к рз , яымс а ачю ю е. нн ееерю-яз юэх раба ч аз ся юхбр бшях дяскрыя» ы е, шудеятае я з р тае увяз Р яш ЫШОЗЗЕОΠ— 100 Б 041 (брязв з-вз ББК ЗЯ.З11 Рзтя «Р РР юи юг«я 1ЗБМ З-00-001000-З (РУ«з.) 1ЗВМ 0.101-!О!00-0 (зпю.) Сартмкьг 49 Швб Ьу РЫЩ -БыМу РчЬ.
Н юля с Р пу, 1пс. Предлагаемая читателю книга нзвестнога амеряканскога саецналнста в области теорнн инфармапяк н ее приложении Р Блей. хута !освящена построекию быстрых алгоритмов цифровой обработки снгналон — вычнглнтельных злгорчтмав, повсеместно возникающих в таких прнложенняк, кзк все виды связи, радиолокация, радиоастрономия, пяфровзя голография, меднцннская электроняка н т. п. Отсутствие яодабнай кннгн остро о!цущзлось мвагнчя специалистами в перечисленных обчастях — канструктарами информационных систем различного назначения В частности, Р.
Блейхут указывает, чтосы почувствовал ее неабходнчость ва время работы над своей предыду!пей книгой «Теорня и практика кодов, контролирую«цнх ошибкн, в которую ему прншлась включнть нескольно спецнзлю!ых г.тзв с опнсаннем алгоритмов бы. строго вычнслення преобразования Фурье, которые, конечно, никак не зависят от давнага конкретного приложения.
(Книге быда переведена в 1985 г на русскнй язык и быстра разошлась.) Хотя в настоящую ьнягу зашли н алгорнтчы решения теплнценых систем уравнений (вознккаюшнх в тзкнх прялажеянях, как линейное предскззэнне, настроенно звторегрессионных фнльтров, теория колиравзнкя и др.), н алгоритмы быстрого пояска по древовидному графу (возникающие, напркчер, ярн декодяравзянн сверточных подов), сердпевияой кннгн являются быстрые алгоритмы преабразовэння Фурье к вычкслеяня цифровой свертки (линейной я цяклкческай). В основе таких быстрых алгоритмов лежит спепяальная орта. нязацяя массивов денных в внде конечных аюебранческнх структур (групп, колец, полей).
чта создает прежюсычкя для применения структурных теорем алгебры н теория чисел. Эта позволяет строить прзктнческв приемлемые алгарнтмы, обеспечивающие работу цвфравык пропессоров в рсзльяпм часштзбе времени К настоящему времени нзкопнлся шнрокнй ассортимент различных по сваей зркнтектуре и теоретическим предпосылкам алгаратмоз, на пока яоженеры-рэзрзботчкки к прогрзммнсты яе знакомы с их теоретическям обоснавэннем, вопрос о широком использования этих алгоргщмов остается открытым.
Лзннзя кннга весьма' удзчно лкквиднрует абразовэв!яийся разрыв С одной стороны, в ней в двух кэ !2 глен дается краткое, на строгое к систематическое язложеняе необходимых разделав алгебры н элементарная теорин чисел, как праннло, недостаточно нэвестных инженерам-прякладннкач С другой стороны, в остальных 10 главах дается сястечатнческое и нгчерпывзющее опнсаняе накопленных к настоящему времени быстрых алгорнтмов преобразовэння Фурье, вычнслення цифровых сверток и решения 6 ПЗ«х ои к русско у зл«ннм ОТ АВТОРА систем теплицевых уравненвй не только для и ивычных в ин- женерной практике полей комплексных и вещественных чисел, р .
у нругу читателей— Книга несомненно будет полезна шнроьоиу н математннач-оринладннкам, программист ., ач, инженерам-раз- работчикам систем обработки данных, — а т комендована лля включения в программу преподавания матема- тики будущим инженерам-конструкторам систем об аботки и- скре«ной информации. В. И.
Сифорш Подобно таму нан дети перерастают своих родителей, книги могут вмйти эа рамки воз»тожиостей нх авторов. Предлагаемый перевод книги «Быстрые алгоритмы цифровой обработки сигналов» является второй моей пинтой, вышедшей из умелмх рук Инны Грушка, которой н очень благоларен, кап и за перевод первой моей книги «Теория и практика кодов, контролирующих ошибки». Мне известно, что не сущестнует «быстрых алгоритмов» переводов, и поэтому я очень ценю тщательную работу над переводом и исправление опечаток, допущенных в английском издании.
Я нолагаю, что русские читатели найдут здесь много интересного. Предмет книги, алгебраичесний по су«неству, тем не менее ближе к цифровой обработке скгналов, чем к матеыатике. Я надеюсь, ято меня простят за почти полное незнание работ советских авторов в данной области. Р. Э. Бмейхрш ПРЕДИСЛОВИЕ В настоящее время цифровая обработка сигналов переживает взрыв. Ее используют повсюду, включая раднолонацню, сейсмо- А графню, связь, радиоастрономию и медицинскуго электроник ктнвно разрабатываются и находит рыночный сп ос йф ра нку. п овессо ы — с р р — специализированные цифровые компьютеры для обработки сигналов. Такое широкое использовани п еще более широкий спрос иа цифровые процессоры, применяемые в некоторых случаях в массовых масштабах.
Одним из путей удовлетворения ших потребностей являетси выбор рэзуыно востроенных алгоритмов. Вместо того чтобы повыпгать быстродействие процессора от одного миллиона умножений а секунду до пяти миллионов умножений в секунду, можно д нек о от рых задач попытаться так организовать вычисления, чтобы ожно длв быстродействия в адин миллион уынажений в с к секунду оказалось достаточно. К нзстоищему моменту имеется хорошо раэр бота» ая Он твори», позволяющая подойтн к решению задач с эт к й на хорошо известна теоретииам, специалистам в данной области, но на прантике инженеры-конструктОры часто пренебрегают ей, поскольку она пака недоступаа в виде цельного " б уче ного нурса.
Инженер-нонструнтор должен хорошо знать предмет, чтобы выб. рать алгоритм, нужный в данном конкретном приложении, среди смущакицего разнообразия известных быстрых алгоритмов свертки или быс~рого преобразования Фурье. Данная книга является результатом курса, прочитанного автором в Корнеллском университете и корпорации ИБА5 под названием «Быстрые алгоритмы цвфровой обработки сигналов». Курс ыл построен с расчетам иа стюкирующихся инженеров- электриков и аспирантов первого гада обучения; его целью было воспитание инженеров, которые свободно владеют предметом.
Эта же цель является первой в данной книге Второй целью является формирование широкого взгляда на б состояние работ в области быстрых алгоритмов цифровой б отк» сигналов, который сможет стимулировать новые яб о раз 5 ем. Е у»рог . Если собрать воедино все нити, то многое сганаивтся более очевидным. Например, перенесение БПФ-алгоритмов Кули — Тычки, Гуда — Томаса и Винограда в произвольное поле облегчало понимание взаимосвязи между многими последующими идеями. Я думаю, что важно различать быстрый алгоритм, функцию, которую он вычисляет, и приложение, в котором он используется Это разные элементы, и, когда их счешивают, они могут терять свою ясность.
Таким образом, я настаиваю на точ, чтобы отли. ч ать дискретное цреобразов зине Фурье от быстрого преобразования Фурье. й'ервое из них явлиегсн преобразованием, а второе— алгэритмоы для вычисления первого. Подобно этому, алгорнти, Вшербх не является методом вычисления последовательности максименьиого правдоподобия; он представляет собой алгоритм вы шсшихя хратчайшего пути на решетке — пути, который в не. котэрых приложениях будет пушм максимального правдоподобия, но ие обязан бить им Но и тогда, когда кратчайший путь дей твитеаьно является путем максимального правдоподобия, ие следует смешивать определение максимального правдоподобия с шгорзтноьг вичислеаия его пут». В соответствии с этим подходам в ланиой книге мало обсуждаются возможные приложения; после постановки задачи все внимание уделяется построению хорошего алгоритма ее решения Обсуждение возможных пр».
ломений лифровой обработки сигналоа следует искать в других источниках. Идея »вписан»я этой книги возникла ва время работы над бэлзе ран»ей книгой Теория и практика кодов, контролирующих ошибки . Во многих главах эюй книги приходилось рассматривать быстэые алгоритмы вычнслевий в коишных полях, хотя по существу алгорзтмы не зависели от выбранного полн.
5! почувсгеоззл, что стовло бы поместить эти алгоритмы в отдельную книгу, описать их независимо ог использования и дополнить многими дру има важными в цифровой обработке сигналов алгоритмами. Изложение затрагивает многие области теории вычислений и теории алгоритмов Однако в первую очередь нас интересуют инженерные задачи накождения лучших алгоритмов ~гнфровой обрабспхи сигналов; асимптотический анализ играет второстепенную рол В настоящей книге используются разделы ыатеиатики,которые могут быть незнакомы типичному читателю с инженерным абразаваннеч Поэтоиу в ннигу включен весь необходимый математический аппарат н строго токазывакпся все теоремы.Мне представ.
ляется, что если эцгыу предмету предстоит стать самостоятельной и зрелой дисциплиной, то ася необходимая математика должна бмть част~ю этой книги; ссылки на другие источники не могут быть аденватно» заменой Инженер ве может уверенно овладеть предметом, если ему часто предлагается принигь утверждение на веру или обратиться к своей математической библиотеке Необходимая дл» построения быстрых алгоритмов математика содержится в гл. 2 н 5. Эти главы можно сначала прочитать бегло, во к ннм следует возвращаться по мере необходимости Однам из недостатков, которые некоторые читатели заметят в книге, является нетостаточносгь рекомендаций по практнческоиу использованию алгоритмов.
Такие темы, как ллина машинвого слова, погрешность округления и время рабо~ы алгоритма А иа компьютере В, вообще не рассиатриваются. Это сознательное Ю Пр азшоэээ обоб н решение вызваао тем, чта я нс столь мулр, чтоб у р, что ы делать широкие и о щения по этим вопросам. В немногих нстречавш р чавшихся мне сслсдованиях на зти темы всегда рассматривались зка сформу- лированные задачи, и я не доверяю любому общему выводу, еде. ланному на основе имеющихся данных.
Мне кажется, что «анструк. гору следует решать эти вопросы в гшнтексте коннретной задачи и непосредственно изучать литературу, чтобы узнать, кап посту- пают в аналогичных случаях другие ноистр С е н реди рассматриваемых в настоящей «нпгс алгоритмов многие уже широко используются в прантической деятельности.