|
Главная | Продукция и услуги | Статьи | Полезная информация | Сертификаты | Награды | Отзывы | Контакты |
Продукция и услуги
|
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналовПеревод с английского И. И. Грушко Москва «Мир» 1989 Книга американского специалиста, посвященная актуальным прикладным задачам построения быстрых алгоритмов цифровой обработки сигналов (автор известен по его «Теории и практике кодов, контролирующих ошибки» (М.: Мир, 1986)). Для ускорения типичных для таких задач вычислений используется организация данных в виде конечных алгебраических структур (групп, колец, полей), что позволяет применить структурные теоремы алгебры и теории чисел. В двух из двенадцати глав книги содержится краткое, ио строгое и систематическое изложение соответствующих разделов математики, как правило, недостаточно известных инженерам-прикладникам. Для математиков-прикладников, программистов, инженеров — разработчиков систем обработки дискретных сигналов, студентов и аспирантов университетов. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ.—М.: Мир, 1989.—448 с, ил.
Содержание книги
Предисловие к русскому изданию
Глава 1. Введение
Глава 2. Введение в абстрактную алгебру
Глава 3. Быстрые алгоритмы коротких сверток
Глава 4. Быстрые алгоритмы дискретного преобразования Фурье
Глава 5. Теория чисел и алгебраическая теория полей
Глава 6. Вычисления в суррогатных полях
Глава 7. Быстрые алгоритмы и многомерные свертки
Глава 8. Быстрые алгоритмы многомерных преобразований
Глава 9. Архитектура фильтров и преобразований
Глава 10. Быстрые алгоритмы, основанные на стратегии дублирования
Глава 11. Быстрые методы решения теплицевых систем
Глава 12. Быстрые алгоритмы поиска по решетке и по дереву
Приложение А. Набор алгоритмов циклических сверток ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Предлагаемая читателю книга известного американского специалиста в области теории информации и ее приложений Р. Блей-хута посвящена построению быстрых алгоритмов цифровой обработки сигналов — вычислительных алгоритмов, повсеместно возникающих в таких приложениях, как все виды связи, радиолокация, радиоастрономия, цифровая голография, медицинская электроника и т. п. Отсутствие подобной книги остро ощущалось многими специалистами в перечисленных областях — конструкторами информационных систем различного назначения. В частности, Р. Блейхут указывает, что он почувствовал ее необходимость во время работы над своей предыдущей книгой «Теория и практика кодов, контролирующих ошибки», в которую ему пришлось включить несколько специальных глав с описанием алгоритмов быстрого вычисления преобразования Фурье, которые, конечно, никак не зависят от данного конкретного приложения. (Книга была переведена в 1985 г. на русский язык и быстро разошлась.) Хотя в настоящую книгу вошли и алгоритмы решения тепли-цевых систем уравнений (возникающих в таких приложениях, как линейное предсказание, построение авторегрессионных фильтров, теория кодирования и др.), и алгоритмы быстрого поиска по древовидному графу (возникающие, например, при декодировании сверточных кодов), сердцевиной книги являются быстрые алгоритмы преобразования Фурье и вычисления цифровой свертки (линейной и циклической). В основе таких быстрых алгоритмов лежит специальная организация массивов данных в виде конечных алгебраических структур (групп, колец, полей), что создает предпосылки для применения структурных теорем алгебры и теории чисел. Это позволяет строить практически приемлемые алгоритмы, обеспечивающие работу цифровых процессоров в реальном масштабе времени. К настоящему времени накопился широкий ассортимент различных по своей архитектуре и теоретическим предпосылкам алгоритмов, но пока инженеры-разработчики и программисты не знакомы с их теоретическим обоснованием, вопрос о широком использовании этих алгоритмов остается открытым. Данная книга весьма удачно ликвидирует образовавшийся разрыв. С одной стороны, в ней в двух из глав дается краткое, но строгое и систематическое изложение необходимых разделов алгебры и элементарной теории чисел, как правило, недостаточно известных инженерам-прикладникам. С другой стороны, в остальных 10 главах дается систематическое и исчерпывающее описание накопленных к настоящему времени быстрых алгоритмов преобразования Фурье, вычисления цифровых сверток и решения систем теплицевых уравнений не только для привычных в инженерной практике полей комплексных и вещественных чисел, но и для полей Галуа. Книга несомненно будет полезна широкому кругу читателей — математикам-прикладникам, программистам, инженерам-разработчикам систем обработки данных, — а также может быть рекомендована для включения в программу преподавания математики будущим инженерам-конструкторам систем обработки дискретной информации. В. И. Сифоров ПРЕДИСЛОВИЕ В настоящее время цифровая обработка сигналов переживает взрыв. Ее используют повсюду, включая радиолокацию, сейсмографию, связь, радиоастрономию и медицинскую электронику. Активно разрабатываются и находят рыночный спрос цифровые процессоры — специализированные цифровые компьютеры для обработки сигналов. Такое широкое использование порождает еще более широкий спрос на цифровые процессоры, применяемые в некоторых случаях в массовых масштабах. Одним из путей удовлетворения этих потребностей является выбор разумно построенных алгоритмов. Вместо того чтобы повышать быстродействие процессора от одного миллиона умножений в секунду до пяти миллионов умножений в секунду, можно для некоторых задач попытаться так организовать вычисления, чтобы быстродействия в один миллион умножений в секунду оказалось достаточно. К настоящему моменту имеется хорошо разработанная теория, позволяющая подойти к решению задач с этих позиций. Она хорошо известна теоретикам, специалистам в данной области, но на практике инженеры-конструкторы часто пренебрегают ей, поскольку она пока недоступна в виде цельного учебного курса. Инженер-конструктор должен хорошо знать предмет, чтобы выбрать алгоритм, нужный в данном конкретном приложении, среди смущающего разнообразия известных быстрых алгоритмов свертки или быстрого преобразования Фурье. Данная книга является результатом курса, прочитанного автором в Корнеллском университете и корпорации ИБМ под названием «Быстрые алгоритмы цифровой обработки сигналов». Курс был построен с расчетом на стажирующихся инженеров-электриков и аспирантов первого года обучения; его целью было воспитание инженеров, которые свободно владеют предметом. Эта же цель является первой в данной книге. Второй целью является формирование широкого взгляда на состояние работ в области быстрых алгоритмов цифровой обработки сигналов, который сможет стимулировать новые работы в будущем. Если собрать воедино все нити, то многое становится более очевидным. Например, перенесение БПФ-алгоритмов Кули—Тьюки, Гуда—Томаса и Винограда в произвольное поле облегчило понимание взаимосвязи между многими последующими идеями. Я думаю, что важно различать быстрый алгоритм, функцию, которую он вычисляет, и приложение, в котором он используется. Это разные элементы, и, когда их смешивают, они могут терять свою ясность. Таким образом, я настаиваю на том, чтобы отличать дискретное преобразование Фурье от быстрого преобразования Фурье. Первое из них является преобразованием, а второе - алгоритмом для вычисления первого. Подобно этому, алгоритм, Витерби не является методом вычисления последовательности максимального правдоподобия; он представляет собой алгоритм вычисления кратчайшего пути на решетке — пути, который в некоторых приложениях будет путем максимального правдоподобия, но не обязан быть им. Но и тогда, когда кратчайший путь действительно является путем максимального правдоподобия, не следует смешивать определение максимального правдоподобия с алгоритмом вычисления его пути. В соответствии с этим подходом в данной книге мало обсуждаются возможные приложения; после постановки задачи все внимание уделяется построению хорошего алгоритма ее решения. Обсуждение возможных приложений цифровой обработки сигналов следует искать в других источниках. Идея написания этой книги возникла во время работы над более ранней книгой «Теория и практика кодов, контролирующих ошибки». Во многих главах этой книги приходилось рассматривать быстрые алгоритмы вычислений в конечных полях, хотя по существу алгоритмы не зависели от выбранного поля. Я почувствовал, что стоило бы поместить эти алгоритмы в отдельную книгу, описать их независимо от использования и дополнить многими другими важными в цифровой обработке сигналов алгоритмами. Изложение затрагивает многие области теории вычислений и теории алгоритмов. Однако в первую очередь нас интересуют инженерные задачи нахождения лучших алгоритмов цифровой обработки сигналов; асимптотический анализ играет второстепенную роль. В настоящей книге используются разделы математики, которые могут быть незнакомы типичному читателю с инженерным образованием. Поэтому в книгу включен весь необходимый математический аппарат и строго доказываются все теоремы. Мне представляется, что если этому предмету предстоит стать самостоятельной и зрелой дисциплиной, то вся необходимая математика должна быть частью этой книги; ссылки на другие источники не могут быть адекватной заменой. Инженер не может уверенно овладеть предметом, если ему часто предлагается принять утверждение на веру или обратиться к своей математической библиотеке. Необходимая для построения быстрых алгоритмов математика содержится в гл. 2 и 5. Эти главы можно сначала прочитать бегло, но к ним следует возвращаться по мере необходимости. Одним из недостатков, которые некоторые читатели заметят в книге, является недостаточность рекомендаций по практическому использованию алгоритмов. Такие темы, как длина машинного слова, погрешность округления и время работы алгоритма А на компьютере В, вообще не рассматриваются. Это сознательное решение вызвано тем, что я не столь мудр, чтобы делать широкие обобщения по этим вопросам. В немногих встречавшихся мне исследованиях на эти темы всегда рассматривались узко сформулированные задачи, и я не доверяю любому общему выводу, сделанному на основе имеющихся данных. Мне кажется, что конструктору следует решать эти вопросы в контексте конкретной задачи и непосредственно изучать литературу, чтобы узнать, как поступают в аналогичных случаях другие конструкторы. Среди рассматриваемых настоящей книге алгоритмов многие уже широко используются в практической деятельности. Другие станут важны в будущих приложениях, когда цифровая обработка сигналов будет более разнообразной и широко применяемой. Некоторая часть, возможно, никогда не станет полезной. Я стремился дать широкий обзор; какие из методов окажутся практически важными, предстоит решить инженерам-конструкторам в следующие несколько десятилетий. Сердцевиной книги являются описываемые в гл. 3 и 7 алгоритмы циклической свертки и описываемые в гл. 4 и 8 алгоритмы быстрого преобразования Фурье. В гл. 7 и 8 описываются многомерные аналоги алгоритмов гл. 3 и 4 соответственно, и при желании их можно читать сразу после этих глав. Изучение одномерных алгоритмов свертки и преобразования Фурье завершается лишь в контексте многомерных задач. Главы 2 и 5 представляют собой математические введения; некоторые читатели, возможно, предпочтут пользоваться ими как приложением, обращаясь к ним лишь по мере надобности. Главы 6 и 9 следует читать отдельно, следом за гл. 3 и 4. Главы 10, 11 и 12 в основном независимы; каждую из них вполне можно читать независимо от остального, материала книги. Скачать книгу Быстрые алгоритмы цифровой обработки сигналов. Москва, Издательство Мир, 1989
|
143502 МО, г.Истра-2, ул. Заводская, 43А. Тел. (49631) 4-66-21. E-mail: toroid2011@mail.ru |