19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

858. Внешняя политика США в 1953-1975 годах 198 KB
  Основные черты внешнеполитической стратегии США 1953–1975 годах. Крупнейшие внешнеполитические инциденты 1953–1975 годах. Внешняя политика США в 1953-1975 годах.
859. Основы организации бизнеса 162.5 KB
  Развитие в России всех видов собственности и видов деятельности, современных предприятий и представительств зарубежных стран. Формы собственности и организация управления. Адаптация к рынку. Тенденции организационных изменений при переходе к рынку. Программы государственной поддержки малого бизнеса.
860. Интеграция организаций и ее сфера. Понятие венчурных фондов и организаций 176.5 KB
  Разновидности трестов. Финансово-промышленные группы. Их классификация. Формы финансово-промышленных групп. Преимущества их пред другими субъектами рынка. Направления деятельности ФПГ. Понятие венчурных фондов и организаций. Транснациональные кампании. Их типы и основные характеристики. Международные совместные предприятия.
861. Основы профессиональных информационных технологий 158 KB
  Рассмотреть основные понятия, термины и определения информатики и информационных технологий. Информация и ее свойства. Информационные технологии в профессиональной деятельности. Цель и задачи изучения учебного курса Информатика и информационные технологии в профессиональной деятельности.
862. Детские церебральные параличи 164 KB
  Заболевание центральной нервной системы. Глубокая недоношенность и гидроцефалия. Травматическое повреждение головного и спинного мозга. Атонически-астатическая форма. Реабилитационные мероприятия при ДЦП. Клинико-педагогическая характеристика речевых нарушений при ДЦП.
863. Самоорганизация в живой и неживой природе 136.5 KB
  Порядок и беспорядок в природе. Особенности эволюционных процессов. Синергетический подход в естествознании. Общие свойства систем, способных к самоорганизации. Качественное описание процесса самоорганизации. Синергетика и самоорганизация.
864. Виды производства молока 33.5 KB
  Промышленность выпускает большой разнообразный ассортимент молочных продуктов. Блочное молоко долго хранится и применяется для изготовления шоколада и шоколадных конфет.
865. Полномочия Верховной Рады Украины 37 KB
  Назначение очередных и внеочередных выборов в органов местного самоуправления. Предоставление согласия на назначение Президентом Украины на должность Генерального прокурора Украины; высказывание недоверия Генеральному прокурору Украины, которая имеет следствием его отставку из должности.
866. Организация и планирование производства. Управление дистанцией сигнализации и связи 782.5 KB
  Расчет технического штата для обслуживания устройств СЦБ и связи. Поездная и станционная радио и громко говорящая связь. Расчет эксплуатационного штата телеграфно-телефонной станции. Расчет штата производственной базы дистанции. Четырех недельный план-график технического обслуживания устройств СЦБ чётной сортировочной горки ГАЦ.