19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

81894. Уровни менеджмента в организационной иерархии 40.53 KB
  Менеджеры высшего звена президент вицепрезидент генерал ректор университет. Менеджеры среднего звена главный бухгалтер главный инженер директор предприятия капитан. Менеджеры низшего звена начальник цеха мастер начальник отдела по маркетингу сержант Три основных уровня менеджеров. Менеджеры низшего звена Функции: осуществление контроля за выполнением производственных заданий; непосредственное руководство рабочими и сотрудниками; обеспечение информацией руководителей высших уровней о выполнении производственных заданий.
81895. Перспективные формы организаций 41.13 KB
  Идея формирования эдхократической организации зародилась еще в середине века в американской компании ХьюлеттПаккард . Отсюда следует что организационная структура управления эдхократической организации порой жестко не определена иерархическое строение ее может довольно часто изменяться у менеджеров не всегда есть жесткая привязка к определенной сфере деятельности. Организационную структуру управления эдхократической организации обычно ассоциируют со схемой концентрической формы.
81896. Общие функции менеджмента 38.02 KB
  Суть управленческой деятельности на всех уровнях управления обеспечивают функции менеджмента. На сегодняшний день к функциям менеджмента относится : планирование организация мотивация контроль регулирование. Планирование главная функция менеджмента которая предусматривает прогнозирование определение целей стратегии политики и задач того или иного формирования; означает сознательный выбор решения что работы как кому и когда Организация как функция менеджмента направлена на формирование управляющих и управляемых систем а...
81897. Планирование в системе менеджмента 38.41 KB
  Осуществляя связь между современным состоянием организации и тем которого она хочет достичь в будущем процесс планирования включает принятие решений о том что делать когда делать и кто будет делать. Результатом процесса планирования являются планы. Принципы планирования А.Файоль определил четыре основных принципа планирования назвав их общие черты хорошей программы действия: единство; непрерывность; гибкость; точность.
81898. Дерево целей как инструмент по реализации планов предприятия 38.6 KB
  Если миссия задает общие ориентиры направления функционирования организации выражающие смысл ее существования то конкретные конечные достояния к которым стремится организация фиксируются в виде её целей т. По установившемуся мнению существует два типа целей с той точки зрения какой период времени требуется для их достижения. В принципе в основе разделения целей на эти два типа лежит временной период связанный с продолжительностью производственного цикла.
81899. Организация как функция менеджмента 37.4 KB
  Функция организации реализуется двумя путями: через административно-организационное управление и через оперативное управление. Цель функции организации – формирование структуры субъекта и объекта управления и взаимосвязи между ними через делегирование департаментацию разделение труда по горизонтали диапазон контроля нормы управляемости централизацию и децентрализацию управление и регламентацию. Принципы функции организации.
81900. Принципы, используемые при разработке организационной структуры управления 36.98 KB
  Организационная структура управления опирается на основные принципы управления: принцип иерархичности уровней управления каждый нижестоящий уровень контролируется вышестоящим и подчиняется ему; принцип целеполагания ОСУ должна прежде всего отражать цели и задачи организации а следовательно быть подчиненной производству товаров или услуг; принцип соответствия в ОСУ должен реализовываться принцип соответствия полномочий и ответственности работников с одной стороны и квалификации и уровня культуры с другой именно с помощью ОСУ...
81901. Горизонтальное разделение труда 37.6 KB
  Разделение всей работы на составляющие компоненты обычно называется ГОРИЗОНТАЛЬНЫМ РАЗДЕЛЕНИЕМ ТРУДА. Разделение большого объема работы на многочисленные небольшие специализированные задания позволяет организации производить гораздо больше продукции чем если бы то же самое количество людей работало самостоятельно. В очень малых организациях горизонтальное разделение труда может не прослеживаться достаточно четко.
81902. Вертикальное разделение труда 38.52 KB
  Поскольку работа в организации разделяется на составляющие части ктото должен координировать работу группы для того чтобы она была успешной. В этом случае на первый план выступает обособление функции управления суть которой состоит в целенаправленном координировании и интегрировании деятельности всех элементов организации. В укрупненном плане вертикальное разделение труда осуществляется по следующим направлениям: общее руководство выработка и воплощение главных перспективных направлений деятельности организации; технологическое...