19099

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

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

Физика

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

Русский

2013-07-11

316.5 KB

12 чел.

Лекция № 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


 

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

27968. Психофизическая зависимость и психофизическая функция 40.9 KB
  Типы и способы межличностоной и межгрупповой коммуникации. Типы и способы межличностоной и межгрупповой коммуникации. Когда говорят о коммуникации в узком смысле слова то прежде всего имеют в виду тот факт что в ходе совместной деятельности люди обмениваются между собой различными представлениями идеями интересами настроениями чувствами установками и пр. Все это можно рассматривать как информацию и тогда сам процесс коммуникации может быть понят как процесс обмена информацией.
27969. Восприятие пространства и удаленности; монокулярные и бинокулярные признаки глубины 30.95 KB
  Восприятие пространства и удаленности; монокулярные и бинокулярные признаки глубины Чувственное отражение субъективный познавательный процесс и результат этого процесса где объективное познание выступает в виде чувственной формы а именно в виде ощущений восприятий и представлений компоненты чувственного отражения. Восприятие 1 субъективный образ предмета явления или процесса непосредственно воздействующего на анализатор или систему анализаторов перцептивный образ или образ восприятия 2 процесс формирования образа предмета или...
27970. Восприятие как процесс категоризации в трудах Дж. Брунера 36.92 KB
  Личность и психика развитие личности и развитие психики: соотношение понятий. Личность и психика развитие личности и развитие психики: соотношение понятий. Понятие личности обозначает человеческого индивида как члена общества обобщает интегрированные в нем социально значимые черты. Петровский Ярошевский Развитие личности процесс качественных психологических личностных изменений в личности а также результат этих изменений.
27971. Память как высшая психическая функция 23.01 KB
  Психология этнической социализации и этнической идентичности. Психология этнической социализации и этнической идентичности. Этническая социализация выполняет функцию формирования множественной и многоуровневой идентичности личности способствующей конструктивному функционированию этничности в жизни индивида и общества: позитивной этнической идентичности и толерантного этнического взаимодействия. Одним из основных институтов этнической социализации является семья.
27972. Эффект Зейгарник. Этническая идентичность: общее описание, структура, становление и формирование, изменения этнической идентичности 18.62 KB
  Механизмы и эффекты межличностного восприятия Этническая идентичность: общее описание структура становление и формирование изменения этнической идентичности. Эффект Зейгарник. Эффект незавершенного действия эффект Зейгарник явление характеризующее влияние на процессы памяти перерывов в деятельности.
27973. Долговременная, кратковременная, оперативная и иконическая память 27.68 KB
  Социальнопсихологический тренинг как средство повышения точности межличностного восприятия Особенности межкультурной коммуникации развитие культурной сензитивности. Непосредственный отпечаток полезен в тех случаях когда сигнал действует очень недолго как при просмотре к ф; он обеспечивает также непрерывность восприятия при моргании или движении глаз. Социальнопсихологический тренинг как средство повышения точности межличностного восприятия В процессе общения должно присутствовать взаимопонимание между участниками этого процесса....
27974. Активное и пассивное, продуктивное и репродуктивное воображение 35.57 KB
  Феномен аттракции в межличностных отношениях различные уровни аттракции. Феномен аттракции в межличностных отношениях различные уровни аттракции. Область исследований связанных с выявлением механизмов образования различных эмоциональных отношений к воспринимаемому человеку получила название исследования аттракции. Феномен аттракции связан с перцептивной стороной межличностного общения возникает при включении в процесс восприятия эмоциональных регуляторов.
27975. Основные свойства внимания и методы их оценки 43.91 KB
  Основные свойства внимания и методы их оценки. В зависимости от объекта выделяют формы внимания: сенсорное перцептивное: зрительное и слуховое интеллектуальное моторное двигательное исполнительское. Внешнее внимание сенсорноперцептивное обращено на объекты внешнего мира необходимое условие познания и преобразования окружающего мира Внимание внутреннее интеллектуальное обращено на объекты субъективного мира человека необходимое условие самопознания и самовоспитания Виды внимания Джеймс По объекту: а чувственное...
27976. Когнитивные теории внимания и их критика. Этноцентризм и этнические стереотипы 28.85 KB
  Допускается существование группы механизмов селекции в канале ограниченной емкости в результате возникают отсеивание информации еще до момента ее полной идентификации в блоке Р. это процесс в котором два или более индивида или группы активно ищут возможность помешать друг другу достичь определенной цели предотвратить удовлетворение интересов соперника или изменить его взгляды и социальные позиции. когда группы с противоречивыми интересами поляризуются по этническому признаку. Всем известный пример внутригрушювого фаворитизма ...