Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ѕыстрое преобразование ‘урье




 лассические формы пр€мого и обратного ƒѕ‘ хот€ и просты и легко реализуемы на Ё¬ћ, однако их практическое применение ограничиваетс€ большим объемом вычислений, которые растут в квадратичной зависимости от объема выборки .

—уществуют различные способы сохранени€ объема вычислений спектра, которые привод€т к так называемым алгоритма быстрого преобразовани€ ‘урье (Ѕѕ‘). јлгоритмы Ѕѕ‘ основаны на устранении избыточности вычислений в классическом ƒѕ‘. Ёта избыточность просматриваетс€ в периодичности фазового множител€ при которой

, в силу того, что

Ќе каса€сь теоретических основ построени€ Ѕѕ‘ перейдем к изложению основных этапов преобразовани€, которые привод€т к Ѕѕ‘ с прореживанием по времени.

Ќаиболее проста€ форма Ѕѕ‘ получаетс€ при равному степени 2, т.е. когда . „исло показывает количество ступеней преобразовани€.

Ётап 1. ¬ходные отсчеты временной функции (при ) подвергаетс€ двоично-инверсной перестановке (ƒ»ѕ). »де€ ƒ»ѕ состоит в следующем6двоичный код номера отсчета переставл€етс€, формиру€ новый номер отсчета:

Ётап 2. ‘ормируетс€ дерево Ѕѕ‘, способ построени€ которого дл€ и изображено на рис.4.1 и рис.4.2

рис.4.1

 

рис.4.2

основу дерева Ѕѕ‘ составл€ют так называема€ операци€ типа УбабочкиФ, котора€ отображена на рис.4.3, на нем же представлен алгоритм работы УбабочкиФ.

рис.4.3

Ётап 3. –еализаци€ операций УбабочкиФ последовательно по ступен€м, начина€ с УмладшейФ.

ћнемоническое правило расстановки весов ребер операций типа УбабочкиФ состоит в следующем: число показателей степени, начина€ с нулевой фазового множител€ последней ступени преобразовани€ равно , где - объем выборки, например, дл€ 8-точечного Ѕѕ‘ этим и множител€ми €вл€ютс€

ƒл€ предшествующей ступени дерева р€д весовых коэффициентов прореживаетс€ за счет выбрасывани€ четных множителей. ¬ результате такого прореживани€ остаютс€ множители и наконец на первой ступени преобразовани€ остаетс€ лишь один фазовый множитель (рис.4.2)

ƒл€ примера вычисли по дереву Ѕѕ‘ (рис.4.2)

–ассчитаем по алгоритму ƒѕ‘

Ёти выражени€ совпадают потому, что

т.к. весовые коэффициенты периодические (рис.4.4)

рис.4.4





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 773 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—лабые люди всю жизнь стараютс€ быть не хуже других. —ильным во что бы то ни стало нужно стать лучше всех. © Ѕорис јкунин
==> читать все изречени€...

473 - | 456 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.009 с.