Запишем выражение для дискретного преобразования Фурье сигнала 
:
| (1) |
В алгоритме БПФ с прореживанием по времени производится разделение исходного сигнала в соответствии с двоично-инверсной перестановкой. И получили первую и вторую половину спектра. В алгоритме с прореживанием по частоте, наоборот, исходный сигнал 
делится пополам, т.е. 
и 
. Тогда выражение (1) можно переписать:
| (2) |
Учтем что
| (3) |
Тогда
| (4) |
Рассмотрим теперь четные отсчеты спектра 
| (5) |
Учтем что
| (6) |
Тогда
| (7) |
Таким образом четные отсчеты спектра рассчитываются как ДПФ суммы первой и второй половины исходного сигнала.
Рассмотрим теперь нечетные отсчеты спектра 
| (8) |
Основной операцией алгоритма БПФ, называемой базовой, является одновременное (параллельное) вычисление двух отсчетов ДПФ.
Окончательно выражение для четных и нечетных отсчетов спектра:
| (9) |
При делении сигнала на четные и нечетные отсчеты, в алгоритме с прореживанием по времени получали первую и вторую половины спектра. В данном случае алгоритм с прореживанием по частоте наоборот по первой и второй половине сигнала позволяет рассчитать четные и нечетные спектральные отсчеты (поэтому и называется прореживание по частоте). Разница алгоритмов еще и в том, что при прореживании по времени умножение на поворотные коэффициенты производилось после ДПФ четной и нечетной последовательности, а в данном алгоритме умножение на поворотные коэффициенты производится до ДПФ.
На рис.1 приведен направленный граф базовой операции, получивший название ”бабочка” по ассоциации с изображением графа. Верхний выход соответствует сумме, а нижний разности.
Смысл приведенных преобразований заключается в том, что требуемая N-элементная ДПФ может быть представлена как функция N/2 элементных ДПФ.
Рисунок 1: Граф бабочка для алгоритма БПФ с прореживанием по частоте
Важно отметить, что количество ”бабочек” т.е. базовых операций алгоритма, на каждом этапе одинаково и содержит N/2 ”бабочек”.
Алгоритм 8-точечного БПФ представляет собой трёхэтапную процедуру.
= 
=8, r=3, r-прореживаний до достижения одноточечной последовательности
Представим в виде графа алгоритм БПФ с прореживанием по частоте основанный на разбиении — объединении при N=8
Рисунок 2: Граф алгоритма БПФ с прореживанием по частоте для N=8
На первом этапе исходный сигнал делится на 2 половины (красные и синие стрелочки). Далее вычисляются
| (10) |
Тогда если выполнить ДПФ 
, то получим четные отсчеты спектра в соответствии с (9), а если ДПФ 
- то нечетные отсчеты спектра. Таким образом одно ДПФ длительности 
заменили двумя ДПФ длительности 
. Для вычисления каждой из ДПФ половинной длительности снова применим прореживание по частоте. В результате получим:
| (11) |
В результате получили 4 ДПФ по 2 точки каждое, которые также можно выполнить при помощи графа бабочки. На выходе получим спектральные отсчеты, которые будут переставлены. На первом уровне преобразования получались четные и нечетные отсчеты спектра, на втором уровне четные и нечетные отсчеты делились снова на четные и нечетные. В результате для расстановки спектральных отсчетов на места необходимо применить двоично-инверсную перестановку.
Домашнее задание:
…………………….
Создание проекта
После запуска Project Navigator двойным кликом по иконке
появляется главное окно программы (Рис. 1.1)
Рис. 1.1. Главное окно программы Project Navigator
Для того чтобы создать новый проект, нужно нажать кнопку «New Project…» в приветственном окне программы, или через контекстное меню File – New Project…
Откроется мастер создания нового проекта «New Project Wizard» (Рис. 1.2)
Рис. 1.2. Мастер создания нового проекта
В данном окне нужно задать следующие параметры:
Name: название проекта, которое автоматически задает расположение проекта в файловой системе и рабочую директорию.
Top-level source type: файл-источник высшего уровня. Именно этот тип будет считаться главным в проекте, и на его основе будет проходить создание проекта. В данной работе форма представления файла верхнего уровня проекта будет HDL.
Следующее окно представляет собой выбор устройства и сопутствующих настроек для компиляции и симуляции проекта. В данном окне ничего менять не нужно, оно должно соответствовать рис. 1.3, в котором уже заданы все нужные параметры для корректной работы программы на отладочной плате Atlys Spartan-6.
Рис. 1.3. Настройки проекта
После нажатия кнопки «Далее» («Next») будет показана суммарная информация по проекту (Рис. 1.4).
Рис. 1.4. Суммарная информация проекта
По завершению работы мастера создания нового проекта, в левой частей главного окна программы (Панель проекта) появится пустая заготовка текущего проекта.