ЛР7 > Швидке перетворення Фур’є на базі ЦСП

Тема: Реалізація алгоритму FFT над даними з фіксованою крапкою. Дискретне перетворення Фур’є

У даній роботі буде розглянуто реалізацію алгоритму швидкого перетворення Фур’є з прорідженням у часі (Fast Fourier Transform, FFT) з використанням даних у форматі з фіксованою крапкою на мові C.

 

Завдання A

Математичний запис алгоритму швидкого перетворення Фур’є з прорідженням у часі, наведений на рис.1.

 


Рис.1. Математичний запис алгоритму FFT.

 

Наведений вираз показує, яким чином обчислюється N-точкове дискретне перетворення Фур’є (DFT), що складається з двох секцій DFT по N/2-точок. Такий спосіб обчислення називають обчисленням «метелика», а його графічне представлення показано на рис.2.


Рис.2. Графічне зображення алгоритму обчислення «метелика».

 

Приклад програми на мові C, що обробляє дані у форматі з плаваючою комою, подається в Таблиці 1. Програма виконує обчислення комплексного FFT з прорідженням у часі для сигналу з кількістю точок, кратних ступеню числа 2. Вона обчислює N-точкове FFT для вхідного синусного сигналу. Вихідні дані цієї програми повинні бути нулями, за винятком двох відліків – X(k) та X(N-k).

 

Таблиця 1.



Змінюючи константи N і EXP, ми здатні виконувати комплексне FFT для різної кількості точок (кратних ступеню числа 2) за допомогою процедури, наведеної в Таблиці 2.

 

Таблиця 2.



 

Оскільки наведена програма обчислює комплексне FFT, для вхідних даних, представлених лише реальною частиною, масив уявних відліків сигналу повинен бути заповнений нульовими значеннями. Підпрограма, що наведена в Таблиці 2, обчислює комплексне FFT з прорідженням у часі (як зображено на рис.2). Щоб зберегти результати від можливого переповнення, на кожному етапі обчислення проміжні результати масштабуються. Програма обчислення комплексного перетворення Фур’є обробляє два комплексних значення та два цілих значення. Це – комплексний вхідний відлік сигналу X[N], кількість точок перетворення EXP (кратних ступеню числа 2), початковий масив комплексних коефіцієнтів перетворення Фур’є W[EXP], та масштабний коефіцієнт перетворення SCALE. Робота алгоритму FFT відбувається таким чином, що комплексний вхідний масив даних перезаписується комплексним вихідним масивом. Наведена у Таблиці 1 програма формує початковий масив комплексних коефіцієнтів перетворення Фур’є.

З теорії відомо що дані, які використовуються для обчислення FFT, спочатку повинні бути відсортовані в біт-реверсному порядку. Приклад програми, яка виконує біт-реверсне сортування N-точкового сигналу, наведено у Таблиці 3. Дана функція, написана на мові C та використовує можливості біт-реверсного режиму адресації процесора.

 

Таблиця 3



 

    Перехід від даних, представлених у форматі з плаваючою комою, до представлення даних у форматі з фіксованою крапкою відбувається за допомогою внутрішніх функцій мови С. Реалізація обчислення алгоритму «метелика» для FFT з прорідженням у часі та використанням внутрішніх функцій мови С для процесора C55x наведене нижче:

 


 

У наведеній програмі, X[] – масив комплексних відліків вхідного сигналу, а U[] – масив комплексних коефіцієнтів перетворення Фур’є. Масштабування результату відбувається за допомогою операції здвигу вправо на 1 біт, яке замінює операцію множення на 0.5.

 

Виконайте наступні кроки завдання A:

 

1. Створіть новий проект у середовищі CCS; назвіть його expА та збережіть його у відповідній директорії. Скопіюйте командний файл лінкера exp7.cmd, icomplex.h та input7_i.dat з директорії вхідних даних до завдання. Додайте до проекту файли exp7а.с, exp7.cmd, fft_a.c, ibit_rev. Підключить бібліотеку засобів динамічної підтримки rst55.lib (розташована у директорії C:\ti\c5500\cgtools\lib). Виконайте команду Project→Scan All Dependencies. Після її виконання в папці Include проекту повинен з’явитися файл icomplex.h. Запустіть програму на компіляцію. Використайте згенерований файл input7_і.dat (розміщений в робочій директорії), як вхідний сигнал для обробки.

2. Завантажте програму до процесора. Відкрийте графічне вікно для перегляду вхідного сигналу. Параметри налагодження графічного вікна наведені на рис.3.

 


Рис.3 Приклад настройки графічного вікна для виведення вхідного сигналу.

 

3. Відкрийте графічне вікно для перегляду спектру вхідного сигналу. Параметри налагодження графічного вікна наведені на рис.4.


Рис.4 Приклад настройки графічного вікна для виведення спектру вхідного сигналу.

 

4. Відкрийте графічне вікно для перегляду результатів швидкого перетворення Фур’є. Параметри налагодження графічного вікна наведені на рис.5.



Рис.5 Приклад настройки графічного вікна для виведення результатів FFT.


5. Встановіть пробну точку в рядку 59 файлу exp7а.с (біля команди spectrum[i] = (int)((ltemp.re+ltemp.im)>>13);). За допомогою команди Debug → Probe Points підключіть пробну точку для відображення даних у графічних вікнах. Параметри підключення пробної точки наведені на рис.6.

 


Рис.6 Підключення пробної точки до графічних вікон.

 

6. Запустіть програму на виконання в режимі анімації. Поясніть отриманий результат.

 

Завдання для самостійної роботи

 

Змініть значення кількості точок перетворення для FFT з 128 на 1024. Перевірте працездатність програми.