19099

Цифровая обработка сигналов в частотной области. Быстрое преобразование Фурье

Практическая работа

Физика

Лекция № 12. Цифровая обработка сигналов в частотной области. Быстрое преобразование Фурье. Нахождение спектральных составляющих дискретного комплексного сигнала непосредственно по формуле ДПФ требует комплексных умножений и комплексных сложений. Так как колич...

Русский

2013-07-11

316.5 KB

9 чел.

Лекция № 12.

Цифровая обработка сигналов в частотной области. Быстрое преобразование Фурье.

Нахождение спектральных составляющих  дискретного комплексного сигнала непосредственно по формуле ДПФ  требует  комплексных умножений и  комплексных сложений. Так как количество вычислений, а следовательно, и время вычислений приблизительно пропорциональны , то при больших  количество арифметических операций весьма велико. Поэтому нахождение спектра в реальном времени даже для современной вычислительной техники представляет сложную задачу.

По этой причине представляет значительный интерес вычислительные процедуры, уменьшающие количество умножений и сложений. Основной принцип всех этих алгоритмов заключается в разложении операций вычисления ДПФ сигнала длины  на вычисление преобразований Фурье с меньшим числом точек. Разделив анализируемый набор отсчетов на части, вычисляют их ДПФ и объединяют результаты. Такие процедуры получили название алгоритмов быстрого преобразования Фурье БПФ.

При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживание по времени или по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ). Наиболее простыми и широко используемыми являются алгоритмы БПФ с основанием 2, когда длина последовательности  является целой степенью числа 2, то есть , где целое число.

БПФ с прореживанием по времени.  Рассмотрим идею БПФ с прореживанием по времени на примере деления набора отсчетов пополам. Введя общепринятое в литературе обозначение для дискретных экспоненциальных функций:

,                                                                         (12.1)

Запишем ДПФ сигнала  в виде:

.                                                  (12.2)

Разобьем  на две -точечные последовательности, состоящие из отсчетов с четными и нечетными номерами соответственно. В результате получим:

.                                                    (12.3)

Заменяя индексы суммирования на  при четном  и на  при нечетном , придем к выражению:

.                             (12.4)

Так как ,  то (12.4) можно записать в виде:

                             (12.5)

Каждая из сумм (12.5) является точечным ДПФ: первая – для четных отсчетов исходной последовательности, а вторая – для нечетных. Несмотря на то, что индекс  в формуле (12.5) распространяется на  значений , каждая из сумм требует вычислений только для , так как  и  периодичны по  с периодом .  Объединение же этих сумм приводит к точечному ДПФ . Процесс вычислений значений  в соответствии с (12.5) для восьмиточечной последовательности, то есть для , приведен на рисунке 12.1.

 

Процедура вычислений представлена в виде направленного графа, позволяющего формализовать вычисления. Предполагается, что ветви направленного графа, входящие в узел, суммируются. В тех случаях, когда не указываются коэффициенты передачи, их значение равно единице. Для других ветвей коэффициенты передачи по ветви являются целой степенью .

Из граф-схемы следует, что  получается умножением  на  и прибавлением . Значение  получается умножением  на  и прибавлением  и т.д. Вместе с тем, для  нужно было бы умножить  на  и прибавить . Однако, так как  и  периодичны по  с периодом 4, то  и . Таким образом,  получается умножением  на  и суммированием результата с .  Аналогично вводится коррекция для используемых значений  и  при .

Далее можно вычислить каждое точечное ДПФ в (12.4)  разбиением сумм на два точечных ДПФ. Таким образом,  и  могут быть вычислены в виде:

          (12.6)

                                         (12.7)

При вычислениях точечных ДПФ по формулам (12.6) и (12.7) справедливы все закономерности, отмеченные при разбиении отсчетов последовательности на две группы. Продолжим описанную процедуру разбиения исходной ДПФ на преобразования меньшей размерности, пока не останутся только  двухточечные преобразования.  Двухточечные ДПФ (их число равно ) могут быть вообще вычислены без использования операций умножения. Действительно, для двухточечной последовательности согласно определению ДПФ имеем два спектральных отсчета:

;                                                     (12.8)

.

Число требуемых при этом пар операций «умножение – сложение» можно оценить как . Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы (11.5) уменьшается в  раз. При больших  это отношение становится весьма велико.  Например, при  достигается более чем 100-кратное ускорение, но и это еще не предел. Количество комплексных умножений в алгоритме БПФ с прореживанием по времени может быть сокращено вдвое.

Из рассмотренного алгоритма следует, что на каждой ступени вычислений происходит преобразование одного множества из  комплексных чисел в другое множество из комплексных чисел. Обозначим множество комплексных чисел, получающееся на  ступени вычисления, через . Тогда можно считать  входным массивом, а  – выходным массивом на  ступени вычислений. С учетом введенных обозначений можно представить основную операцию вычислений как операцию, изображенную на рис.12.2 в виде графа:

Соотношения, соответствующие этому графу, имеют вид:

                                                              (12.9)

Из-за вида графа на рис.12.2  эта операция называется «бабочкой». Выражения (12.9) подсказывают метод сокращения числа комплексных умножений вдвое. Так как

,  соотношения (12.9) можно записать в виде:

                                                                 (12.10)

Так как на каждую ступень разбиения имеется  «бабочек» вида (12.10), а общее число ступеней равно , то общее число пар операций «умножение-сложение» сокращается до  .

PAGE  1


EMBED Equation.DSMT4  

EMBED Equation.DSMT4  

EMBED Equation.DSMT4  

N|2

ДПФ

N|2

ДПФ

Рис.12.1

Рис. 12.2


 

А также другие работы, которые могут Вас заинтересовать

74001. Основные направления и этапы внешней политики СССР в годы «холодной войны» 19.09 KB
  Основные направления и этапы внешней политики СССР в годы холодной войны. Победа СССР в войне значительно изменило его международное положение. СССР принял участие в создании ООН где ему было определено место одного из постоянных членов Совета безопасности.президент США сформулировал доктрину Трумена меры против экспансии СССР.
74002. Перестройка 1985 – 1990 годов 22.31 KB
  Именно эти меры положили начало развалу политической системы СССР поскольку именно партийная вертикаль обеспечивала реальное функционирование политической системы; советские органы были властью сугубо номинальной а потому оказались не готовы к выполнению возложенных на них полномочий. когда оппозиции удалось добиться отмены 6й статьи Конституции СССР закрепляющей особую роль КПСС в государственной системе СССР и внушительного представительства в ряде...
74003. Становление новой российской государственности в 1990-е годах 18.55 KB
  Распавшийся Советский Союз оставил весьма сложное наследство России в виде экономического кризиса всеобщего социального недовольства и наконец отсутствия реальной российской государственности. В условиях краха умеренной и консервативной моделей периода перестройки вполне естественной была победа весьма радикальной для России концепции демократического либеральнорыночного государства с ориентацией на западные страны. В принципе основные направления реформ к моменту их осуществления в России были уже испытаны в ряде государств Восточной...
74004. Основные этапы развития исторической науки в России XVIII – начале XX веков 20.07 KB
  Главною заслугою Миллера было собирание материалов по русской истории; его рукописи так наз. И исследования Миллера имели значение он был одним из первых ученых заинтересовавшихся позднейшими эпохами нашей истории им посвящены его труды: Опыт новейшей истории России и Известие о дворянах Российских. видное место трудами по русской истории занял и М.
74005. Основные этапы развития советской исторической науки 23.2 KB
  Начало новому этапу в развитии марксистской исторической мысли положили труды В. И. Ленина. Особенно большое значение для И. имела разработка Лениным теоретико-методологических основ общественных наук (в том числе исторической науки)...
74006. Влияние колониальной эксплуатации на традиционное общество в Индии в XIX – начале ХХ веках 23.77 KB
  Влияние колониальной эксплуатации на традиционное общество в Индии в XIX начале ХХ вв. Заключительным этапом средневековой истории Индии стало возвышение на ее севере в начале XVI в. Власть моголов в Индии укрепилась в годы полувекового правления Акбара 14521605 завоевавшего Бенгалию а вместе с ними и выход к морю. Таким образом в Индии XVIXVII вв.
74007. Кризис традиционной японской цивилизации в период сегуната Токугава(1603 - 1867) 20.34 KB
  Кризис традиционной японской цивилизации в период сегуната Токугава1603 1867 Политическое объединение Японии в начале XVII в. Однако объединение страны носило несколько условный характер так как в Японии продолжали существовать более 200 княжеств которые обладали известной степенью автономии. В Японии периода Токугава крупных городов насчитывалось семнадцать среди которых особое положение занимали Эдо Осака. С установлением власти Токугава в Японии широкое распространение получили конфуцианские идеи в интерпретации философа Чжу Си.
74008. Версальско-вашингтонская система международных отношений: становление, эволюция, кризис 32.17 KB
  Вильсон выступал за умеренность в требованиях к Германии, желая не допустить превосходство одной из них в Европе. Соединённые Штаты стремились усилить своё влияние в Европе. Именно с этой целью Вильсон предложил включить в Версальский договор статьи о создании Лига Наций
74009. Мировой экономический кризис 1929 – начала 30-х гг. Причины, региональные особенности, пути преодоления, итоги и значение 36.42 KB
  В противовес классическому принципу невмешательства государства в экономику была признана ведущая роль государства в регулировании национального хозяйства с целью повышения эффективности спроса населения на товары потребления Это основа от кот.