19545

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

Лекция

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

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

Русский

2013-07-12

515.42 KB

4 чел.

2

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

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

Случай

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

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

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

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

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

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

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

   (1)

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

.(2)

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

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

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

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

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

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

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


 

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

12751. Криптоанализ потокового шифра на основе корреляционного метода 171 KB
  Лабораторная работа 3 Криптоанализ потокового шифра на основе корреляционного метода Цель работы Изучить возможность криптоанализа потокового шифратора при помощи вычисления корреляции между шифрующей гаммой и выходами линейных рекуррентных регистро...
12752. Получение знаний о высоковольтных выключателях 496.9 KB
  ЦЕЛЬ РАБОТЫ: Целью работы является получение знаний о высоковольтных выключателях. ПРЕДВАРИТЕЛЬНОЕ ЗАДАНИЕ: Ознакомиться с назначением и типами высоковольтных выключателей характеризующими их параметрами и условиями выбора. Условия выбора выключателей: В о...
12753. Масляные выключатели. Маломасляные выключатели 122.38 KB
  ЦЕЛЬ РАБОТЫ: Целью работы является получение знаний о высоковольтных выключателях. ПРЕДВАРИТЕЛЬНОЕ ЗАДАНИЕ: Ознакомиться с назначением и типами высоковольтных выключателей характеризующими их параметрами и условиями выбора. Масляные выключатели Различаю
12754. Получение знаний об измерительных трансформаторах тока 407.96 KB
  ЦЕЛЬ РАБОТЫ. Целью работы является получение знаний об измерительных трансформаторах тока. ОДНОВИТКОВЫЕ: ТПОЛ: Стержневые трансформаторы тока с литой изоляцией типа ТПОЛ Т трансформатор тока П проходной О одновитковый Л с литой изоляцией. Предназначе...
12755. Получение знаний об измерительных трансформаторах напряжения 91.42 KB
  Целью работы является получение знаний об измерительных трансформаторах напряжения. НОМ – трансформатор напряжения однофазный масляный; НТМИ – трансформатор напряжения трехфазный масляный с дополнительной вторичной обмоткой для контроля изоляции сети; НТМК – тр
12756. Приводы высоковольтных выключателей Управление масляным выключателем ВМПЭ-10 369.83 KB
  ЛАБОРАТОРНАЯ РАБОТА № 4 Приводы высоковольтных выключателей Управление масляным выключателем ВМПЭ10 ЦЕЛЬ РАБОТЫ: Целью работы является получение знаний о приводах высоковольтных выключателей а так же ознакомление со схемой управления масляными выключателями....
12757. Комплектные распределительные устройства 6-10 кВ 236.59 KB
  ЛАБОРАТОРНАЯ РАБОТА № 5 Комплектные распределительные устройства 610 кВ ЦЕЛЬ РАБОТЫ Целью работы является получение знаний о конструкциях ячеек комплектных распределительных устройств 610 кВ ПРЕДВАРИТЕЛЬНОЕ ЗАДАНИЕ Ознакомиться с информацией...
12758. Разъединители, отделители короткозамыкатели 267.85 KB
  ЛАБОРАТОРНАЯ РАБОТА № 6 Разъединители отделители короткозамыкатели. Целью лабораторной работы является получение знаний о разъединителях отделителях и короткозамыкателях используемых в установках выше 1000 В. Разъединитель. Разъединитель предст
12759. Метод наименьших квадратов 1.88 MB
  Метод наименьших квадратов В данной работе содержатся краткие теоретические положения образцы выполнения заданий необходимые для выполнения лабораторной работы индивидуальные задания. Работа предназначена для студентов всех специальностей. Содержание 1. Те...