Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 55
Текст из файла (страница 55)
Прн желании можно входные данные подавать в естественном порядпе, но тогда пересеченпя ливий нз лнаграмме првмут более сложный вяд. При напнсанкя программы БПФ-алгорнтма Кулн †Тыч удобнее выбрать форму, в которой вычисляемые выходные данные запвсывзются в памяти в переставлеяном виде. Перед нспальзова. пнем этих данных надо выполнять обратную перестановку.
Другой . возможностью является написание программы алгорнтма в таком виде, когда на каждом шаге нтераш1в вычисленные данные возвращаются в память в таком порядке, что адресзцня данных па следующем юаге нтерации совпадает с анресашгей яа прошлом шаге, Имеется много сшюобов таких перестановок; нх детализаляя является «ущесгвенной частью структуры программы клн аппарзтурнога модуля Конструктор должен решать, какая часть данных будет перенндексярована пря запамянання, какая часть данных будет переннлекснрована прн вызове, н какая часть рабочей памяти может быть использована сверх того объема, который отведен для запоминания входного массива данных.
Большой БПФ-алгоритм Винограда не является столь регулярным, гак что его реалнзацвя не может иметь такого аккуратного вида. Однако, селя приступая к программной или аппаратурнай реалкаацин, пцательно проанализировать структуру алгоритма, то ее люжно сделать достаточно упорядоченной. Проиллюстрируем некоторые возможности на примере построения 83- точечного БПФ-алгоратма Винограда нз 7-точечнага и 9-точечного БПФ.алгарятмав Винограда. Предположим, что в ыалых БПФ. алгоритмах Винограда матрацы профакторнзовавы в ваде 97, = г, г, Р с 9.6 БПФ. юратя Куан — Т жно «ам а розе аша ш щз .
Рчс 9.10 Бпф шз ку» — т пка щэ 3 у 9 жа *з аб чы Р .9ы.ду ча бб зза Г». в, «з* ««ггз«ф «юза» «г аз«юш «е = С,В,А, и УУ, = С,В,А„ где В, и В„ представляют собой дивта. нальные матрицы соответственна размерностей 9 и 11, Тогда большой БПФ-алгоритм Винограда записывается в виде Вг = (С,ХС«)(В«ХВ«)(АгХА«) = (С«КС)В«з(АгКА«). Каждый из крайних множителей мы будем использовать н виде кронекераеского произведения, не вроизвадн вычисления новой матрицы, равной этому нроненеравскаму произведению.
Член Вг и В, заменим, однако, на диагональную матрицу Вз,. Реалвзация рассматриваемого БПФ-алгоритм« начинаешя с перезаписи данных в виде двумерной (ух9)-таблицы. Первое умножение кагкдаго нз 7 столбцов таблицы на матрицу Аз удлиннет сталбпы да 11. Следующее за этим умножение каждой из 1! строк на матрицу А,. приводит к их удлинению до 9. Теперь данные записаны з видедвумернай (9х 11) таблицы. Умножим поэлементно зту матрицу на 99 констант матрицы Вм, кшорые заранее должны быть записаны в цастояннои запоминающем устройстве. (Более точна, Вм представляет собой диагональную нагряну размерности 99, яо для простоты ее здесь лучше рассматривать как (9 м 11)-таблицу, элементами которой служат упорядоченные соответствующим образом элементы диагонали матрипы Вм.) Полученную таблицу данник уменыпнм теперь в объеме, умножая сначала каждый нз 9 стачбцов на См а затем каждую из 9 строк на матрицу Ст.
Эш приведет к вычислению всех 63 компонент преобрааавания Фурье входного вектора, записанных " в виде (7 х 9)-таблицы. Остается талька переупарядочить иампаненты, одновремшгна записывая их н виде одиомернога массива. На рис. 9.12 иллюстрируется структура использования малых преобразований Фурье в !5-точечном БПФ-алгоритме Винограда Из рисунка ясна, «ак простые логические цепи многократна использукггся для реализации указзнных функпнй. Аналогичную структуру можно использовать н для других длин преобразований.
В тех приложениях, в катормх необходима вычислять л-точечное преобразование Фурье непрерывного потока даняых, можно воспользоваться конвейерной схемой. Показанная на рнс. 9.!3 конвейерная архитектура относится к высокоэффективному !008-точечиому БПФ-алгоритму. Такая структура может быть предложена для гипотетичесной радиолокационной задачи, в которой необходимо вычислять 1063-точечное преобразование Фурье бесконечной последовательности данных. Этот способ позволяет достигать скоростей вычисления порядка миллионов отсчетов а секунду.
Входные данные распределяются цо банкам 16-точечных модулей БПФ, пройдя через которые они поступают в бавк 63-точечных модулей БПФ. Ва время обработки данных в 63-точечных модулях в 16-точечных модуляя начинается обработка следующего пакет» данных. Этим достигается одновре- г ы Зэа Гк9 Арюктуг Ф р пр Ерээа З Ркс 9яа. АЭ ю Гр 1аса-л ечасг БПФ. 98 Пркерэза 1г Фур ° рэ ь . лю ы 339 меннасть вычисления обоих ВПФ В такую конвейерную архитектуру можно добавить параллельно работающие преобразователи, реализующие необходимые перестановки коыпоиеиг данных. Тогда конвейер будет содержать четыре каскада — два для вычислений и два для перестановок компонент.
Может оказаться удабныы, например, выбрать дтп первого банка девять 16-точечиых модулей, а для второго — восемпадпать 66-точечных модулей. Тогда каждый 16.точечный модуль должен в пределах одного пакета выполнять 7 вычислениИ. Выбор соответствующих семи векторов с шины данных регулируется про. стыки мегодачк управления памятью и пкклпчесиими выборками из памяти. Аналогична, передача данных с выхода 16-точечных модулей на пентральную шину данных управляется векоторым фиксированным протоколом.
Определенный протокол управляет также обработкой данных в 63-точечных модулях. 9.8. Преобразование Фурье ограниченного диапазона Предположим, чта при и временных компонентах преабразо. вания Фур~е питерсе представляют меныпе чем и частатпмх компонент. Скажем, имеется приложение, в катарам обработке подлежат 10 000 вреченнмх иамвонент. Это позволяет вычислить 10 000 компонент спектра, из котормх нужны не все. а, возком~то, талька 100.
Воспользовавшись 10 000-точечным ВПФ, можно вычислить все спектральные компоненты, а затем ненужные отбросить. Но лучше воспольаоваться прореживающей филырапией п преобразованием Фурье ограниченного диапазона. Преобразование Фурье ограниченного диапазона относится скорее исего к другой области пифровай обработки сагиалав; оио ие представляет собой быстрого алгоритма и том смысле, который вкладывается в зта понятие в данной кинге.
Л1ы талька хатим упомянуть его как неиоторый яругай метод, характер которого сильно отличается от изучаемых вами алгоритмов. В своем большинстве наши алгоритмы косят харзктер машмати. ческих тождеств. Вопросы точности относятся к реалиэапии алгпрнтмов, но не к их построению Если ответ неточеа, та зта не вина алгоритма, как такового, а скорее связано с невозможностью записи чисел бесконечной длины при выполнении саоженип и ултножсння. В преобрааавапии Фурье ограниченнога диапазона появляется новый феномен. Она представляет собой не математическое тожде. ство, а всего лишь приближенное вычисление, хотя н дает сколь угодна точное приближение.
Общий вид преабразаваиия Фурье ограниченного диапазона предсгавлеи на рис. 9.14. лаз з з * и Замечании Задачи 340 Г 9 Ар юипурз фальшак к пр сбр н кй Рис 914. В не «еар бр а «я Фурюсгр ' юод Центральной теоремой в исследованиях прорежнвающих фильтров является теорема отсчетов, Скорость отсчетов времеиибга дискретного сигнала ие может быть меньше скорости Найквиста. Если скорость отсчетов сделать меньше, чем удвоенная максимальная частота ненулевой компоненты, то эти компояенты начинают мшкладыватьсяз на компоненты с меньшими частотамм, создавая фальшивый «образ . При вычислении преобразования Фурье ограничевнага диапазона данные сначала пропускаются через низкочастотный прореживающнй фильтр, ноторый подавляет ненужные спеитральные компонегпы и сохраняет те спектральные «оипоненты, которые представляют интерес.
Практически используемые низкочастотные фильтры, построенные методами дискретной техники, не являютс» совершенныии низкочастотными фильтрами. Они ие- многО и»меняно нужные спектральные «омпонеиты и не полностью подавляют нежелательные спектральные компоненты, так что преобразование Фурье ограниченного диапазона ие является точным. После выполнения прорежнвысщей фильтрапии лля вычисления нужных спектральных компонент можно воспользоваться БПФ.алгоритмом малой длины. Если полоса нужных спектральных компонент начин»ется не с нули, то вада просто ввести показанный на рис. 9.14 модулнрующнй множитель мы.
Это обеспечивает такой частотяый сдвиг представляющих интерес частотных компонент, что оин начинаются с нули. 9.1. Д з , г если рнвно елани д ул, -ф р.ю ц»в, л пр а й 2.фил гр.секч»к, сю рмн М (з) = 1 з'з ум мке»ий и ло А ( ) - 2л -(- ЗА (л(2) чаю»«муля мАП)-О 9.2. Ог юкнвая п са кш в га 3 алгорюма к ум р й 3.
ю *й й. юй зер н, н грс гь мм д м нмр ц» двумерную 9.ю ач уи . «й ум, юергку. 9.3, для лн«й ой се ргкн наине пр лд и гь вюд и:.Рюрм к «рый по снюму духу будет чю-го редним микку юлом лера«рн и е- бр а ола Каков» го пра нумюгва н иа оаы к 7 9.4. Д « . а гарн и, вмчнслвож й гр» пюл дсвпюь ы юма нв зд.
Да у, Ч к у р йс О ( Зд МЫГКСЮ ЮЫУЛЯ нпи дпрофльрс100овд .Ок»,ни ум греби ° люнзмнсргзаз« б. оп«мы з П Р ь ар и й гм см»ий »гор и 4.гю ой сн рк й ф р кни к р с смывами юмпснипам». й, *карр я. н б о рдю р ° и н-г Д', б',бз, =О, ..., Л -, 'С вЂ” 2. а-е ю «ср «юБПФ р,кб . и«и. «июрыеп пращ ы лю . Испсльзу 46 й БПФ.. Рн Вв огрюз. прзмеякгь аго 9.9. В и» а ьал р зф юр- «шиш о. компл*«с ыз ч сю С«льн л а с р з пр д« ы н н ю.,юы мялась, п а д иу, юмв мо н с ю рзб С о р ым (1966) ю гил, и с , »ю *и ц р ок А р ю и Баррас (1974) пю ал«, з к моин В а о ру«»» р д 0 й л у н фарм с кцюзирозакня п ы юду рюдс я любу В» ц у.
П976) дю «числ н я бвошн ц «л- (1979, 19И). К ру«ю» д а р . «Румын« юций фнлюрса яи. р длоюно лм м н рс (19731 О п, л ы го р во обз рз 342 Гл. 9. Ар«зю ур ф ро» ы эрюбраю»й ра р ээ ы«э э ««ююгру аа«пр р ж зэыш«ф«эюуэ . Об р рэбп аэ «~ рпслэа«з «р р ээээю мш««а «Зг«з эжэ Крэшюрэ Рэ. б рэ Пэзц, Ээ нсэ ю «э . уы ш««иб и лэ эсжэ«зй, ыы э р юа«э срээ эз й «арэ«шр. р э««эы» БПЕ. аг ритмов, жз э, э шбрю«ь эппэрюур ую р ««ы««ш «р с ы р вать ю«э эр рэ ую ршз«ээц«ю э«усу«ту«э)» арэ«юр«т «и шз ят эт ючээ «эыбрююю рээ«гэ г рипа, ур эа «ршрэы эу ша, рх г «гуры эрэаэш рэ «юу «тээ пр гз ымэ э. Н «шэр э иссээх ээ««э «эрэ«гэр«сгю был« прэ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
