19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

67135. Пьер де Ронсар, Луис де Камоэнс, Уильям Шекспир 42.5 KB
  Первым начали использовать стихию народного языка для обогащения поэтики. Уже в следующем веке слава его начинает меркнуть. Очень нелицеприятного откликались о нем классицисты 19 века, его стихам не хватало стройности и порядочности. Эта эстетика не соответствовала духу его поэзии.
67136. Русская культура на переходе от средневековья к новому времени 32 KB
  Примечательно что в 17 веком появляется обличение лени пассивности уже приветствуется динамизм умение приспособиться к изменениям нового времени. Изменения этого времени было уже нельзя предотвратить. Это переходная эпоха к новому времени.
67137. Культурогенез. Научные и философские концепции культурогенеза 34 KB
  Вопросы происхождения культуры затрагивались многими историками и философами но первые научные исследования в этой области связаны с работами антропологами эволюционистов 19 века. Философский подход он опирается на первоначальный набор аксиом из которого путём умозаключений философ строит свою теорию культурогенеза.
67138. Михаил Юрьевич Лермонтов 1814 – 1841 37 KB
  Внешне он производил впечатление очень демонического героя который очень легко относился к своему дару. Биография Лермонтова биография человека очень трагическая. Лермонтов узнал и полюбил красоту русской природы былину об Иване Грозном предание о Степане Разине и Емельяне Пугачеве.
67139. Комфортные условия жизнедеятельности в техносфере 22.59 KB
  Техносфера – регион биосферы, в прошлом преобразованный людьми с помощью прямого или косвенного воздействия технических средств. Взаимодействие человека и техносферы. Человек и окружающая его среда (природная, производственная, городская, бытовая и др.) в процессе жизнедеятельности постоянно взаимодействуют друг с другом.
67140. Историческая школа. Инициатор Франс Боас (1856-1942) 31.5 KB
  Цель антропологии по его мнению состоит в реконструкции всей истории человечества при этом он говорит о том что существуют общие законы развития культуры но при этом он призывал к осторожности к их формулировке потому что культуры имеют собственную уникальную историю каждая культура индивидуальная.
67142. Грамматические категории 90 KB
  Грамматическое значение и грамматическая форма тесно связаны в грамматической категории (ГК). Этот факт не оспаривается никем, но определение ГК строится либо с опорой на форму, либо с опорой на грамматическое значение (ГЗ). Грамматическая категория (греч. katēgoria ‘суждение, определение’) – система противопоставленных друг другу рядов грамматических форм с однородными значениями
67143. Полисемия. Понятие моно- и полисемии 179 KB
  Изменение лексического значения Типы переноса наименования. Метонимия Расширение и сужение лексического значения Улучшение и ухудшение лексического значения Типы метафор и метонимий по закрепленности в системе языка и степени образности Развитие семантической структуры слова в разных языках...