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


 

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

84096. Демократический режим и его признакии 22.3 KB
  В демократическом государстве существует взаимная ответственность государства и личности.Предоставление широкой свободы личности предприятиям и организациям в сфере экономической деятельности которая при демократическом политическом режиме составляет основу материального благосостояния граждан.Реальная гарантированность прав и свобод личности и реальная возможность реализовать данные права и свободы.Наличие эффективной и квалифицированной судебной защиты прав и свобод личности от произвола и беззакония со стороны кого бы то ни было.
84097. Антидемократические государственно-правовые режимы 25.92 KB
  Основными чертами тоталитарного политического режима являются следующие: государство стремится к глобальному господству над всеми сферами общественной жизни к всеохватывающей власти; общество полностью отчуждено от политической власти но оно не осознает этого ибо в политическом сознании формируется представление о единстве слиянии власти и народа; господствует монопольный контроль над экономикой средствами массовой информации культурой религией и т. фактически устраняется плюрализм; происходит централизация государственной...
84098. Функции государства: понятие, признаки, содержание 20.68 KB
  Функции государства это основные направления внутренней и внешней деятельности государства в которых выражаются и конкретизируются его классовая и общечеловеческая сущность и социальное назначение. В этом определении выделены наиболее существенные признаки функций государства. Функции государства непосредственно выражают и предметно конкретизируют его классовую и общечеловеческую сущность.
84099. Внутренние функции государства современного государства и их содержание 22.02 KB
  Охранительная функция: Это функция государственной деятельности проявляется в обеспечении государством общественного и правового порядка защите и охране прав и интересов граждан и организаций защите конституционного строя и государства от противоправных посягательств. Обеспечение внутреннего мира и согласия в обществе урегулирования общественных отношений снятие социальных противоречий неизбежных в обществе состоящем из различных классов групп слоев это насущная необходимость одна из тех причин которые вызывали возникновение...
84100. Внешние функции государства современного государства и их содержание 23.61 KB
  Защита государства от вооруженных нападений других государств. Функция защиты из вне: Данная функция является важнейшим направлением деятельности государства ибо она нацелена на защиту мирного труда суверенитета и территориальной целостности государства. 30 Формы и методы осуществления функций государства Государство должно выполнять свои функции в присущих ему формах применять в своей деятельности различные методы.
84101. Механизм государства, государственный аппарат: понятие и их соотношение 21.97 KB
  Механизм государства есть та реальная организационная материальная сила располагая которой государство осуществляет власть. Механизм является структурным и предметным олицетворением государства представляет собой материальное вещество из которого оно состоит. Можно сказать что механизм суть деятельное постоянно функционирующее выражение государства.
84102. Понятие государственного органа. Классификация государственных органов 24.37 KB
  Классификация государственных органов Первичным и важнейшим структурным элементом механизма государства является орган государства. Государственный орган это звено элемент механизма государства участвующее в осуществлении функций государства и наделенное для этого властными полномочиями. Раскрытие понятия признаков данного органа позволяет глубже познать механизм государства в целом. Хотя орган государства и обладает определенной самостоятельностью автономией он служит частью единого механизма государства занимает в государственной...
84103. Государственные учреждения в механизме государства 22.34 KB
  Для обозначения этой системы обычно используют понятие механизм государства. Механизм государства – это совокупность государственных органов осуществляющих государственную власти и обеспечивающих реализацию функций государства. Первичной ячейкой государства выступают его органы и учреждения.
84104. Принципы формирования и деятельности государственного аппарата 21.91 KB
  Они подразделяются на общие принципы относящиеся к механизму государства в целом и частные принципы действие которых распространяется лишь на некоторые звенья государственного механизма отдельные органы или группы органов. Общие принципы принято делить на две группы. К первой относятся принципы закрепленные в Конституции Российской Федерации ко второй принципы сформулированные в Федеральном законе Об основах государственной службы Российской Федерации и иных федеральных законах О Конституционном Суде Российской Федерации О...