19545

Быстрые схемы дискретного преобразования Фурье

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

2 Лекция 14. Быстрые схемы дискретного преобразования Фурье. Обычные формулы для вычисления ДПФ требуют большого количества умножений: где число точек в ДПФ. Существуют приемы позволяющие уменьшить это количество. Они называются быстрыми схемами БПФ. Пр

Русский

2013-07-12

515.42 KB

4 чел.

2

Лекция 14. Быстрые схемы дискретного преобразования Фурье.

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

Случай

 Любое число в интервале  однозначно представляется двоичным вектором длины . Если последовательность  задана, то положим

. В дальнейшем, что упростить изложение, введем обозначение , откуда . Имеем

. Основное замечание заключается в следующем: суммирование по индексу  равносильно суммированию по всем двоичным индексам .

, каждый из которых принимает два значения.

Для числа  существует аналогичное двоичное представление:. Рассмотрим самую внутреннюю сумму. . Нетрудно видеть, что это некоторая функция . Следующая сумма принимает вид . Этот процесс продолжается. Окончательно имеем . Количество сумм равняется , в каждой из которых лишь одно умножение. Для вычисления всех коэффициентов нужно  умножений. Другое преимущество этой схемы - экономный расход оперативной памяти.

Случай   с взаимно простыми сомножителями

Рассмотрим другой крайний случай, когда  и . В этом случае существуют целые , для которых . Отсюда следует, что

   (1)

При этом можно считать выполненными неравенства

.(2)

Если такое неравенство для , например, не имеет места, можно разделить на . Для

любого целого  из (1) вытекает

. При ограничениях типа (2)  находятся однозначно. Имеем

. Числа  - взаимно простые. Следовательно имеем для любого целого

. Теперь . Раскрывая скобки и отбрасывая члены кратные , получим показатель вида .

Из равенства  следует, что , поэтому весь показатель сравним с . Это означает, что . Вводя обозначения , окончательно получим  =

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


 

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

29551. ФРАЗЕОЛОГІЗМИ У ЗАГОЛОВКАХ СУЧАСНИХ ЗМІ ТУРЕЧЧИНИ 419.5 KB
  15 Класифікації фразеологізмів у вітчизняному та турецькому мовознавстві. Функціонування фразеологізмів у заголовках газет.22 Трансформація фразеологізмів у заголовках газет.28 Стилістичні помилки у вживанні фразеологізмів .
29552. Влияние утренней гимнастики на повышение умственной работоспособности младших школьников 67.14 KB
  Особенности влияния утренней гимнастики на работоспособность детей младшего школьного возраста Значение утренней гимнастики. Работоспособность детей младшего школьного возраста. Анатомо физиологические особенности детей младшего школьного возраста. Комплексы утренней гимнастики для детей младшего школьного возраста.
29553. Оценка текущей маркетинговой стратегии предприятия и разработке рекомендаций по повышению ее эффективности 1.63 MB
  В условиях рыночной экономики невозможно добиться стабильности, успешного функционирования предприятия без четкого и эффективного планирования деятельности организации, постоянного сбора и аккумуляции информации как о состоянии целевых рынков, положении на них конкурентов, так и о собственных перспективах и возможностях, что подтверждает актуальность темы курсовой работы.
29554. Белые стихи в лирике А.А. Тарковского 117 KB
  Стих – это текст, ощущаемый как речь повышенной важности, рассчитанная на запоминание и повторение. Стихотворный текст достигает этой цели тем, что делит речь на определенные, легко охватываемые сознанием части. Кроме общеязыкового членения на предложения, части предложений, группы предложений, здесь присутствует еще и другое деление...
29555. Разработка средств генерации графических текстов для информационных систем 1.07 MB
  В наше время существует достаточно много типов представления информации. И далеко не все отличаются хорошей информативностью, их бывает достаточно сложно интерпретировать. Основной ошибкой разработчика является то, что он создает интерфейс какой-либо программы, ориентируясь в основном на свои предпочтения
29556. Моделирование динамики щитовидной железы у детей школьного возраста 859.5 KB
  В результате проведенных исследований разработали математическую модель динамики объёма щитовидной железы и проследили за её зависимостью от различных морфо-антропометрических характеристик у детей школьного возраста. Для этого использовались разные показатели. В качестве таких показателей выступили: пол ребёнка, возраст, рост, масса тела.
29557. Проектування потокової лінії механічної обробки деталі і розрахунок її техніко-економічних показників 683 KB
  Потокове виробництво в Україні було деякий час одним з найбільш високорозвинених. Але в нинішніх нестабільних умовах як сам верстатний парк так і способи виробництва починають морально застарівати. Це спричинено нестачею коштів на оновлення обладнання, розривом економічних зв’язків, станом економіки та іншими причинами, пов’язаними із цими.
29558. Основи теорії масового обслуговування. Системи массового обслуговування 140.84 KB
  Мета курсового проекту - застосування теоретичних та практичних знань основ теорії ігор та статистичних рішень і теорії масового обслуговування (ТМО) для вибору і обгрунтування управлінських рішень в умовах невизначеності.