Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 4
Текст из файла (страница 4)
Цифровая обработка сейсмической кнфармзпяи является глав ным методом разведке земных недр, а частности одним из важнейших методов поиска залежей нефти. Обрзботкой больших пакетая лент данных занято все процессорное время многих компьютеров, на многие вьшясленяя остаютсз невыполненными. Коьгпьютернгя томография представаяет собой шярпко ясполь зуемый ныне способ объемного синтеза изображений внутреяяих органов человека с помощью множесгвеннык нроекций, получае ыых цри просвечивании рейтгеновскеми лучами Разрэбасыва. ются алг три мы, позволяющее существенно сня т дозы об. у. ченяя, но требования к цяфровой обработке намного превосходят все чракгнчегкя приемлемые в настоащее время Изугаются н дррггзе способы получения нзображений для медицинской лязг.
ностикн в точ числе о помощью ультразвука, ядерного магнит. нога резонанса яли радяоактнвнмх изотопов Неразрушаюший контроль качества цодукцян, например ат. лизок, возможен с помощью воссоздаваемых на компьютере язоб. раженяй энутренянх областей изделия по резулшатам эхолокаця н. В прянпнпе обработка сягналов может быть использована для улучнгеяия качества плохих фотографий, смазанных движенеем камеры яли расфокусяровкой. Однако такая цифровая обработка требует большого объема вычнсленнй.
Обработка на цифровом процессоре спутнаковык фотогрзфнй позволяет совместить несколько изображений илн выделять осо. бенпости, или скомбинировать полученную на различных длинах волн информацию, нля создать сянтеткческяй стереоскопический образ. Например, в метеорологических исследованиях можно соэ. дать подвнжное трехмерное изображение облачного покрова, движущегося над поверхностью земли, яспользун для этого последовательность спутннковых фатографнй. снятых с нескольких точек.
Можно указать н другие приложения быстрых алгоритмов для цифровой обработки сигналов, но уже прнведенных достаточно для гаго, чтобы доказать, что потребность в ннх существует н продолжает расти. Каждое нз пписзнных приложений связана с большим колячеством вьинслеянй, струк~ура которых.
однако чрезвычайно Ю Гл 1. Вэедевз прозрачна н снльво упорядочена, Кроме того, если лля решення некоторой задачи уже создан жесткий модуль влв подпрограмма, то с онн н будут постоянно нспользоватьсн для этой задачи. Име т мысл затратнть усилия на разработку лобратнай схемы, так как хорошие операцвоннме характервсгннв намного важнее стоимости разработки. 1.3. Систеыы счисления для проведения вычислений В й а все кинге, говоря о сложности алгарнтма, мы змеем в виду число умнаженнй в сложений, поскольку зтн операции выбраны в качестве еднннц намеренна сложности. Кто-то молгет захотеть пойтв дальше в, чтобы падсчнтать чвсло необходкцых битовы о ерацвй, поннте есоваться тем, как построено устрой- и нтовых ство умножения. Структура умаожвтеля н сумматора суптесгвевзо зависит от вида представления данных.
Хотя воп псы, с вязанные с системами счнсленвя, вмхаднт за рамки раданного курса, несколько слов во взеденни об агам сказать следует. Возьмем крайний случай, полагая, что основная часть вычнсленвй состоят нз умножений. Тогда сложность можно панязнть, запнсывая дзнвые в логарнфмвческом виде. Сложение прн этом станет более трудоемким, во если сложеннй не слишком ыного, то общий результат улучшится. Тем ве менее, как праввло, мы будем полагать, что входные данные запнсываюгся в одном нз естественных ввдое — как выцесгвенвые, как комплексные влн как целые числа.
В практической реалнзвцнв процессоров для цвфравай обработкв свгналов имеются еще более тонкве вопросы; нспользуютсв формы записи числа как с плавающей, так н с фнксвровзнвой точкой. Для большинства залая гьвфровой обработки вполне достаточной аназывается арвфметвка с фнксярованной точкой н в юнх случаях се в нада выбрать вз сообрзженнй экономвчвостя. Этого положения не следует придерживаться слишком сгрого. В«егла есть соблазн избавиться от многих трудностей проектнровання, перейдя к арвфмегвке с плавающей точкой Однако если чнп влн влгорвтм предназначены для одного.едннственвого првмененвя— например цвфровай фнльтр для цвфрозой радносхемы массового выпуска, — то не стовмасть рюработкн этого чапа играет основную роль; решающую роль играют эксцлуатацвонные характервствкн изделия в стонмасть его твражнровапвл.
Деньги, затраченные на облегчение работм конструктора, нельзя цотрзтнть на улучшение «арактервстян. 1 3. Оч« в ечв» за» пр денна эячвсае й Нсотрнцательное целое число /, меньшее, чем рщ в ш-снмвольной позвцвовнай арифметике с фиксированной тачкой па основанню д записывается в виде /=/а+/тц, /вйэ+ 1 -гЧ ~ 0 </г<6 Чвслп / представляется и-последовательностью коэффициентов (Гз, /ь , / ,) '). Имеется нескольно свособов учета знака числа с фнксвравзнной точкойг зтн способы записи отрицательных чисел называютсв соответственно прямым кодом, даполннтельным кодом н абратнмм кодом.
Прн любом основаннн д прввнла такого представления одни в те же. В двончном случае, О =- 2, даполвнтельный в обратный над!я иногда называются соответственна 2-дополнвтельпын н 1.допалннтельным. Нанбалее прост для поннмання прямой код. Для записи знака числа в нем выдезяется «пепвальная позиция, которая называетсв энзковой в в которую записывается Ь, если число полажнтельна, в 1, если чнс о отрицательно. В процессе вшюлне в о ер цнй сложения в умноження знаковая появляя обрабатывается отдельно от значимых позиций. Часто предпочтение отдается дополнвтельному жлн обратному кодам, поскольку овн проще реалв. зуются в жестком нсполненнв; сумматор просто складывает два чнсла, не делая различия между знаковой н значащвмн цозвцнямв.
Как прямой, тан в обратный коды приводят к двум разным запвсям нуля — паложвтельной в отрицательной, которые следует полагать равнымв. В дополннтеаьном коде нуль запвсывается однозначно. В обратном коде изменение знака числа получается заменой кзждой цифры 1, включая н знаковую пнфру, на д — 1 — /. Например, взятое с обратным знаком десятичное число -1.62 (которое звпнсывается как 062) равно в обратном коде 931. а взятое с обратным знаком двончное число -1-011 (которое запнсывается как 0011) равна в обратном коде 1100.
Обратный нод абчадает тем свойством, что для умножения любого числа на минус алин достаточно каждую цифру заменить ее пополненнем до д — 1. В допалншельнам коде изменение звака каждого числа получаетсв првбавленвем еднннцы к записи этого свела в обратном коде. Г!о определенню мвнус нуль равен нулю. Прв таком соглашеннн взятое с обратным знаком десятвчное число ф62, которое записывалось как 062, равно в дополнительном коде 938, а взятое с обратным знаком дводчное число (011, которое эапнсывалось «ан 0011, равво в дополнительном коде 1101 а (,г Лр .:р 22 Г .
1 В едгиие 1.4. Цифровая обработка снгмвлов Наиболее важной задачей пифровой обработки сигналов является зздага фильтрации длинной последовательности чисел, з наиболее важным устройствам — цифровой фильтр Как правила, длина последовательности данных заранее неизвестна и является столь большой.что ее можно полагать при абрабаткебесканечпой. Числа, составляющие паследоэатсльносгь, ивляюгся обычно либо вен!ест зениыми, либо комплексными, ио нам предстоит работать и с другими вилами чисел Цифровой фильтр представляет собой устройство, формирующее новую гиславую последовательность, называемую выходной последовательностью, по запаиной паследоиательиасти, котора» теперь называется входной последователь.
пастью. Ширака используемые филыры можно строить из эле. метов, схемы которых прнаелены на рис. 1 2 и которые называются разряди.ни регистра сдвига, сумма порами, умнажи лелями иа скагяр и умиажитгляии. Разряд регистра сдвига содержит одно число, которое поступает на его выход. В дискрсгнме моменты времени, именуемые тактами, разряд регигтр гдэига замещает сопержащсеся в нем число числом, поступающим нз его вход, отбрасывая предыдущее содержимое. Как показано на рнс ! 3, рггитпр сдвига представлвст собой несколько соединенных в цепь разрядив регистра сдвига.
Регистр сдвига называется также гоиигй гадергкги. Иы будем рассматривать два наиболее важных типа регистров сдвига, известных под названием фильтра с калечным инпугьсним сткгикем (КИО-фильтр) и лзтарггргсгиаииога фи ьтр . КИО.фильтр, как показзно на рнс. 1.4, представляет собой просто ливню задержки с отводами, в которых выход каждого разряда умножается на фиксированную «оисганту, а результаты складываются вместе Как показано на рнс.
1.5, авторегрессионный фильтр также является линней задержки с отводами, но с обратной свяаью, соединяющей выход со входом. Выходная последовательность КИО-фильтра равна линейной свертке входной по. саедовательнастн и последонательнасти, опксываемой весовымн множнтелячи в отводах фильтра. Линейная свертка является едва ли не самой обшей вычисли. тельной задачей цифровой обработки свгналон, и большую долю времени мы потратим на исследование иопроса ее эффективной реализации.
Еше больше времени мы уделим методам эффективного вычисления циклической свертки. Это может показаться странным, так на» в прнложениях ииклическая свертка возникает естественным образам не столь уж часто. Наше внимание к циклической свертке обусловлено тем, по для ее вычисления имеется иного хороших алгоритмов. Это позволяет разработать быстрые методы вычисления очень длинных линейных сперток, связывая вьгесте нного никли гескмх сверток 1,4, цзфразаз абзг.'ю «* е Ду,г г сг у Рн . 1.2. Элене пи гыи Рэ 13 Р Г ааг Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
