Богнер, Константинидис - Введение в цифровую фильтрацию (1044115), страница 16
Текст из файла (страница 16)
На входе следует положить а(А)— : х(А), А=О, 1, ..., 1ч' — 1 (7.17) П5 гллвл 7 (7.18) и на выходе — =Х(п), А (а) п=0,1, ...,У вЂ” 1. МЕТОДЫ ПРЕОВРЛЗОВЛНИЯ ФУРЬЕ Чтобы использовать этот же алгоритм для выполнения ОДПФ, обрабатываемые данные должны быть перетасованы следующим образом: а(А) = — Х(Л~ — й), А=1, 2, ..., Л~ — 1, а (О) = Х (О), Р.19) и для получения заданной последовательности во временнбй области нужно сделать замену А(п)=х(п), п=0, 1, ..., Л~ — 1. (7.20) Нетрудно, конечно, получить схему вычислений, позволяющую найти М значений А (и) по М значениям а (А) в соответствии с формулой (7.16) . Пример такой структурной, схемы показан на Фиг.
7.9. Блок-схема непосредственного вычисления ДПФ. ю и ог амм по этой струкц иг. ф . 7.9. Составить соответствующую р р у осто что факт многократного повторетурной схеме настолько просто, что ф й остается незамеченным. ти « . Э «лишние» ния одинаковых операци ест операции появляются по следующим причинам. выр (7.16) входят произведения общего вида а(А)К "'. В' является периодическои с пеРиодом М. ля Весовая функция И7 является М вЂ” 1 произведение такзаданного при ически, п ичем число этих пеРиодов равже будет меняться периодически, Р оизведения в п еделах одного периода пр но К Более того, даже в п~~ „, п 'р Следователь- могут образовывать компле плексно-соп яженные па с щественно уменьшить число умножений, нео ходимых д чении последовательност и А,п,.
щения вычисие . остигнуть этого сокраще Алгор тмы и зволяющ д ы по общим названием «ы лительной нагрузки, известны под ы образование Фурье» (БПФ). Следует подчерк у вое» преобразование, а всего Еще одно более незначительное увеличение гн то в том случае, когда о ра атыалгоритма может быть достигну яются ействительными величинами то о ус ваемые данные являются дейс бладает комплексем что ДПФ действительных чисел о л ловлено тем, что р . С . ельно достаточно вычислять п яженной симметрией. ледовател но-сопряжен Под обно этот вопрос рассматрилишь одну половину спектра.
одро вается в разд. 7.9. мя столь ши око,2~, что, ДПФ применяется в настоящее время столь р ЦВМ, . ля его выполнения используются к оме ниверсальных р у р для г ф овые устройства. Они делятся ибо пе иферийное устройство для аз аботанные ци ро выполнения БПФ, соединенное с универсальной ЦВМ, либо спести. Эта техника достаточно хорошо разр отана; статье 200 машин, которые могут выполнять речислено около м льзовать п„еМик оп ограммирование дает возможность иополь затратах труда разработчиков. При микропрограммировании грамма содержится в программиру р ро раммирование включает получение алгоритма Ооычно мик, оп ог амм г аммь:, кото„ая затем представс последующим составлением прогр ляется набором машинных команд д воичной о ме.
ти команб ды затем заносятся в ППЗУ, которое „р е п- в ащается таким о разом квивалент небольшого частка в постоя нно запрограммированныи эквивален в воичном виде памяти машины, обычно содержащего программу в д (после ее компиляции). ВФ 117 116 ГЛАВА т МЕТОДЫ П!'ЕОВРАЗОВАИИЯ ФХРЬГ 7.5. Быстрое преобразование Фурье Вывод БПФ из ДПФ трактуется для изучающих этот вопрос различными способами 14 — 7~. Например, ДПФ можно рассматривать как действия с матрицами, и тогда БПФ выводится в результате факторизации матриц.
Были также получены короткие рекурсивные уравнения, ценные тем, что дают математическую формулпровку принципа БПФ. Они особенно полезны при составлении программ. Мы используем менее строгий подход, вполне достаточный для объяснения вывода БПФ, его сути и способов программирования. Начнем с того, что запишем соотношение (7.16) в виде М вЂ” ! А(п)=~,' а(/г) ехр( — 2лргп), п=О, 1, ..., У вЂ” 1. ~=о Возьмем последовательность а(/г), показанную на фиг. 7.10, и разделим ее на две подпоследовательности у(/г) и е(/г), такие, что у (/г) =а (2/г), 1, А! е (/г) =а (2/г+ 1),) Пусть ДПФ у(/г) и е(/г) будут соответственно У(п) и 2(п). Тогда А (и) можно записать как М/2 — 1 А(п)= — ~~ (а(2й)ехр( 1 ).1. ~-о +а(2/г+1) ехр /~ + ~ ~11 /)/ = — У(п)+ехр 2(п) .
Используя принятое ранее более компактное обозначение для экс- поненты ', получим А (п) = — [1А (п) + Р'"Л(/ф. (7.21) С точки зрения вычислений можно считать А (и) Л/-,размерным массивом комплексных чисел. Аналогично У (и) и 2 (п) являются такими же массивами, и, )поскольку обе эти функцяи )периодические (с периодом Л//2), массивы имеют 1размерность Л~/2.
Очень удобно ис- ' Автор здесь и ниже использует экспоненту со знаком минус Я)'= — ехр 1 — 2л//)1'). — Прим. перев. /)/ п=О, 1, ...х —, А (и) =У(п), о формуле. ез льтата выполняется п тогда вычисление ко ечного р у А(п) — ! А (и)+ А и+в М 2 х необходимое дли выполнени~ ..Ф. Фиг 710. Первое прореживание данных, . ить вычисление таким способом, то нельЕстественно, если проводить в з будет найти значени~ ( ) д 11/ " — периодическая функция с периодом , о ладаю ством Я7 — (и+А!/2) — Я7 — и Поэтому следующие две операции: А (и) — — А (и)+ А п+ — К А ( п -1- — ) — ( А (и) — А ( и -1- — ) рх") п для п=О, 1, ..., Л//2 — 1.
Следопозволят вычислить значения А(п) для п= ательно, все значения и, мо „ в х Лг/2-точечных преобразований и умножением на в двух -т ч эффициенты. Эта процедура показа памяти для хранения А (и) и более- пользовать одри л те же ячейки памяти дл коротких У(п) и Х(п). При этом методь! првоврлзовлн я чных п еобразований может быть по- Каждое из двух У/2-точечных пре . каждая входная ользованного приема, т.
е. ка лучено повторением использ ва азбивается на две п подпоследовательпоследовательность снова р ности длиной М/4. В обо у боих сл чаях нео ходимо б подобрать соответ эффициенты. для исходи ои пары последова ствующие весовые коэ,„ ию М-точечного претельностей, которые соотв у етств ют вычислению образования, коэффициепт равен К, =ехр( — 2п!/М).
Для М/2-точечного преобразования имеем К!~д — — ехр [ — 2щ/(М/2И =У~!.. М/2-точечных преобразований нужно иметь чеСледовательно, для ~ -точ ч А(и) ~ — 2 А(и)+А и+ 4 А 'Д72п ! А и 1- — ~ — А (и) — А ~ и + 4 +4/ 2 и+ А и+ +А и+ 4 А — А и+ — — А и+ 4 !'!' где всюду Ф и 0 1 4 Если М вЂ” кратно 2, т. е.
если М =2', процедура последовательн р р ного п о ежив ания входных данных и пеожет быть пвоведена г раз д о тех пор, пока В б ное п еобразование. ся пр не останется двухточечное пр последовательных ге коэффициенты В риме аф г 712 ных, хранящихся в массиве А (и). качестве п г аф для вычи ф ычисления преобразопоказан полныи направленный р ф ван.ия при И=8. фиг. 7.12, входные данные х ы х(й) которые преобраКак видно из,„иг.
стественном порядке, зуются в массив ( ), р А(и) асполагаются не в ес ого прореживания данчто является результатом м последовательного п а точек преобразования. ных для уменьшения числа б м. Если индектасовки можно хорошо и о пояснить следующим о разом. с ой фо ме ~например, х(6) сы входных д анных записать в двоичнои,„орме а получается путем инвер- (110) 1 то новое положение числ в виде х~ екса.
Так, для приведенного примера сии двоичных разрядов индекса. ак, д М11ТОДЫ 11РВОВРЛЗОВЛ1!ИЯ ФУР1»Г 12Г х х а1 х о а1 о 1о о а» х о о о Е" о .О 1о х а1 ° в а1 о .х .О х 1: х а1 о х 7 б Эффективность алгоритма БПФ При непосредственном вычислении ДПФ, рассмотренном ранее- и иллюстрируемом фиг. 7.9, для вычисления каждого из У значений А(п) требуется У комплексных умножений. Поскольку умножение — самая медленная из всех операций, выполняемых на ЦВМ, то время, необходимое для вычисления ДПФ таким способом, будет почти точно пропорционально У'.
С другой стороны, исследуя направленный граф на фиг. 7.12, находим, что БПФ требует Л1/21од2 У комплексных умножений. Действительно, конечный или любой промежуточный массив А(п) получается из предыдущего с помощью Л'/2 взвешиваний, каждое,из которых включает одно комплексное умножение. Всего таких цик.- лов взвешивания г, 1причем г=1од, Л1.
, Я з~~ Ю аЮ -а а» с» с» х »аД„~ ~ о,д с~ ~ ~ ~ф~ а» й» ~ а» а» а»<~» »»а» а, а» с~а» Ю» а а %» » а» а» ~ »а .О С» а > ~з Е х(110) становится х(011), что при преобразовании к десятичному. виду дает номер 3. Таким образом, х(6) становится третьим, а х(3) — шестым. Эта перетасовка носит название двоичной инверсии. Еще одна интересная особенность направленного графа — возможность проведения вычислений с «замещением». Как было показано, необходимый объем памяти определяется лишь потребностью хранить Л1 исходных чисел. По мере выполнения преобразования исходные данные не сохраняются; на их место записываются сначала промежуточные результаты, а затем отсчеты преобразования в естественном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
