19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

2306. Система Mathcad. Основні математичні операції 117.23 KB
  Алгебричні обчислення. Обчислення похідної, первісної, означеного інтегралу. Вирішення нелінійних алгебричних рівнянь. Обчислення систем лінійних алгебричних рівнянь.
2307. Планирование в системе управления деятельностью строительно-монтажных организаций 208.62 KB
  Исходными данными для составления перспективного плана строительно-монтажной организации являются: государственный пятилетний план экономического и социального развития РФ.
2308. Динамика вод Мирового океана, как фактор определяющий биопродуктивность 154.1 KB
  Представления о физической природе течений океанов и морей, их параметрах и свойствах. Классификация течений Мирового океана. Циркуляция вод и промысловое значение Японского моря. Влияние динамики течений на распределение промысловых объектов.
2309. Виды маркетинга в зависимости от разных факторов 134.82 KB
  Виды маркетинга в зависимости от состояния спроса. Развивающийся маркетинг. Стимулирующий маркетинг. Неотделимость услуг от их производителя. Невозможность складирования и транспортировки услуг. Присутствие клиента во время оказания услуги. Принадлежность к той или иной отрасли услуг.
2310. Философия Нового времени 124.65 KB
  Философия Нового времени и её ориентация на науку. Философия Ф. Бэкона. Разработка Бэконовского индуктивного метода познания. Проблема очищения интеллекта от заблуждений. Дуализм Р. Декарта. Дедуктивный метод познания Декарта. Учение о врожденных идеях. Номинализм и материализм Т. Гоббса. Пантеизм Б. Спинозы. Учение о предустановленной гармонии и теория познания Лейбница.
2311. Контроль качества материалов и сварных соединений 991.29 KB
  Металлографический анализ. Классификация видов технического контроля. Энергия излучения. Виды дефектов, встречающихся в основном металле и сварных швах. Магнитные и электромагнитные методы контроля.
2312. Использование нечеткой логики при моделировании и проектировании 736.94 KB
  Membership Function Editor. Пакет Fuzzy Logic Toolbox. Нечеткая логика в программе Simulink. Функции пакета, запускаемые из рабочей области. Нелинейное шумоподавление.
2313. Животные в мире музыки 20.59 KB
  Итак, ребята, я очень рада приветствовать всех вас, пришедших на это мероприятие! Своим присутствием здесь вы показываете, что вы люди творческие, и что музыка не безразлична вам.
2314. Расчет припусков 684.04 KB
  Понятие о припуске и методы его определения. Расчет величины припуска на обрабатываемую поверхность. Методика определения предельных промежуточных размеров и окончательных размеров заготовки.