19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

6386. Організаційно-юридичний план 26.77 KB
  Індивідуальна підприємницька діяльність: одна особа є власником бізнесу та провадить підприємницьку діяльність без створення юридичної особи. Приватне підприємство: одна особа є власником бізнесу, веде його із залученням найманих робітників, зареєструвавшись, як юридична особа.
6387. Клиент, сервер и другие программы 244.53 KB
  Клиент, сервер и другие программы. Рассмотрим типы программ, обеспечивающих работу Web и использующих протокол HTTP. Понято, что никакой HTTP-обмен невозможен без клиента и сервера. Клиент формирует запрос, который обрабатывается сервером. Однако, п...
6388. Преимущества использования XML 30.28 KB
  Преимущества использования XML. XML позволяет компоновать документ из отдельных независимых элементов. Использование XML даёт возможность передавать по сети не весь ресурс, а лишь ту его часть, которая требуется пользователю. XML упрощает создание н...
6389. Переменные в Web-программировании 34.07 KB
  Переменные. Для объявления переменной используется следующее выражение: [модификаторы] тип имя_переменной В данном случае тип - это либо один из простых типов (int, char, Boolean и т. д.), либо имя класса. Простые типы используются так же, как...
6390. Оператор import в Web-программировании 28.61 KB
  Оператор import. Чтобы избавить разработчика от необходимости указывать полные имена и в то же время позволить ему воспользоваться преимуществами пакетов, используется оператор import. Если вы собираетесь работать в программе с другими классами паке...
6391. Объекты в языке JavaScript 106.95 KB
  Объекты. В языке JavaScript не предусмотрены средства для работы с классами в том виде, в котором они реализованы в C++ или Java. Разработчик сценария не может создать подкласс на основе существующего класса, переопределить метод или выполнить какую...
6392. Объекты в Web-программировании 39.8 KB
  Чтобы вызвать метод setTimeout () объекта Window, достаточно указать имя этого метода и задать параметры, а чтобы узнать имя окна, можно обратиться к свойству name. Обращение document.write () означает то же самое, что и window.document.write (), об...
6393. Основы Web-программирования на PHP 29.74 KB
  PHP. Быстрый старт. Первая программа на PHP. Вставив инструкцию print междуPHP-тегами, мы даем команду серверу послать приветствие Hello, world! в браузер. Это аналогично тому, что мы ввели данный текст в HTML-код...