19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

46448. Субъекты PR и общественных коммуникаций. Общественность как объект PR-деятельности и как субъект публичных коммуникаций 16.05 KB
  Общественность как объект PRдеятельности и как субъект публичных коммуникаций. В качестве субъекта PR может выступать заказчик инициатор а также исполнитель PR деятельности. Субъектзаказчик может быть обозначен как базисный субъект PR а исполнитель как технологический субъект PR. Базисный субъект PR субъект публичной сферы на оптимизацию коммуникационной среды которого направлена деятельность определенной PR структуры технологического субъекта PR.
46450. Внешнеполитическая деятельность в условиях новой геополитической ситуации 16.07 KB
  Распад СССР изменил положение России на международной арене. Прежде всего предстояло добиться признания России в качестве правоприемницы бывшего Советского Союза в ООН. В том числе о признании суверенности России о переходе к ней прав и обязанностей бывшего СССР в 19931994 гг. Правительство России присоединилось к предложенной НАТО программе Партнерство во имя мира попросив в последствии НАТО заключить с ним отдельное соглашение.
46451. Уголовное право и процесс в 1930-е годы. Советское законодательство о государственных и имущественных преступлениях как юридическая основа массовых репрессий 16.12 KB
  Основная цель уголовного права в 1930е гг. Принципы уголовного процесса: 1 неприкосновенность личности; 2 гласность; 3 участие защитника и представителей общественности в судебном разбирательстве только на стадии судебного разбирательства; 4 всестороннее и объективное исследование обстоятельств по делу; 5 свободная оценка судом доказательств. Стадии уголовного процесса: 1 возбуждение уголовного дела; 2 дознание и предварительное следствие; 3 предание суду; 4 судебное разбирательство; 5 вынесение приговора; 6 кассационное...
46452. Основные ступени в образовании понятий 16.16 KB
  Первая ступень проявляется в поведении ребенка раннего возраста образование неоформленного и неупорядоченного множества выделение кучи какихлибо предметов которые выделяются ребенком без достаточного внутреннего основания. Первый этап образования синкретического нерасчлененного образа или кучи предметов. Группа новых предметов берется ребенком наугад с помощью отдельных проб которые сменяют друг друга тогда когда обнаруживается их ошибочность. Второй этап синкретический образ или куча предметов образуется на основе...
46454. Культура речи – необходимое условие профессиональной деятельности 16.27 KB
  Эмоциональная культура включает умение регулировать свое психическое состояние понимать эмоциональное состояние собеседника управлять своими эмоциями снимать волнение преодолевать нерешительность устанавливать эмоциональный контакт. Культура профессиональной речи включает: владение терминологией данной специальности; умение строить выступление на профессиональную тему; умение организовать профессиональный диалог и управлять им; умение общаться с неспециалистами по вопросам профессиональной деятельности. Знание терминологии...
46456. Анализ и диагностика затрат предприятия 16.34 KB
  Затраты образующие себестоимость продукции группируются в соответствии с их экологическим содержанием по следующим элементам: материальные затраты; затраты на оплату труда; отчисления на социальные нужды; амортизация основных фондов; Материальные затраты наиболее крупный элемент затрат на производство. Их доля в общей сумме затрат составляет 6080 лишь в добывающих отраслях промышленности она невелика. Состав материальных затрат неоднороден и включает расходы на сырье материалы за вычетом стоимости возвратных отходов по цене их...