Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра ЕОМ Лабораторна робота №3 «Швидкі алгоритми обчислення дискретних тригонометричних перетворень» Варіант: 2  1.Мета роботи: дослідити швидкі алгоритми дискретних тригонометричних перетворень і порівняти їх з алгоритмами безпосереднього обчислення тригонометричних перетворень. 2.Загальні відомості: Алгоритми швидкого перетворення Фур’є (ШПФ) можуть бути отримані за допомогою послідовного застосування операції розкладу одномірного масиву вхідних відліків сигналу на двохмірний. Ця операція здійснена тільки у випадку, коли N (довжина послідовності) є складним числом (N = N1 ( N2 ( ... ( Nj). Якщо N просте, його неможливо розкласти на прості співмножники; для такої послідовності алгоритмів ШПФ не існує. В більшості практичних випадків вхідну послідовність штучно продовжують додаванням нульових відліків до отримання N як складного числа. Для характеристики розкладу використовують поняття “основа”, якщо всі співмножники однакові (N1 = N2 = ... = Nj) і “рощеплена основа”, якщо співмножники неоднакові. Приклад. N = 64 = 2 ( 2 ( 2 ( 2 ( 2 ( 2 - основа 2. N = 64 = 4 ( 4 ( 4 - основа 4. N = 128 = 2 ( 4 ( 4 ( 4 - рощеплена основа 2-4. Дискретне перетворення Фур’є Дискретне перетворення Фур’є (ДПФ) кінцевої послідовності {x(n)}, 0 ( n ( N-1 визначається як
, k = 0, 1, ..., N-1 (1) де
. Суть алгоритмів ШПФ в тому, що якщо N складне число і є степенем двійки (N=2m), то вихідна послідовність розбивається на дві коротші послідовності, ДПФ яких можуть бути скомбіновані таким чином, щоб утворилось ДПФ вихідної послідовності. Методика побудови алгоритмів ШПФ наступна. Введемо дві (N/2) - точкові послідовності {x1(n)} і {x2(n)} з парних і непарних членів x(n) відповідно, x1(n) = x(2n) і x2(n) = x(2n + 1), n = 0, 1, ..., N/2-1. Тоді формулу розкладу можна записати так:
де X1(k) і X2(k) є N/2 - точкові ДПФ парних і непарних відліків вихідної послідовності. Застосовуючи цю формулу розкладу X1(k) і X2(k) до пори, поки X1(k) і X2(k) не стануть двохточковим ДПФ, отримаємо алгоритм ШПФ з прорідженням в часі. Для отримання іншої розповсюдженої форми алгоритмів ШПФ вихідну послідовність розбивають на дві (N/2) - точкові послідовності таким чином: перша складається з перших N/2 відліків, а друга з решти, x1(n) = x(n) і x2(n) = x(n + N/2), n = 0, 1, ..., N/2-1. При такому розбитті N - точкове ДПФ можна записати так
де X1(k) і X2(k) є N/2 - точкові ДПФ першої та другої половини відліків вихідної послідовності. Алгоритми ШПФ, що отримані з застосуванням цієї методики називаються алгоритмами з прорідженням по частоті. 3.Порядок виконання роботи: 1. Застосовуючи методики розкладу, отримати алгоритм обчислення заданого перетворення за певними “основою” і розмірністю. 2. Скласти процедуру на мові високого рівня для безпосереднього (прямого) обчислення тригонометричного перетворення. 3. Скласти процедуру на мові високого рівня для обчислення швидкого перетворення по алгоритму отриманому в п.1. 4. Виміряти часи виконання процедур п.2 і п.3. 5. Порівняти часи виконання процедур п.2 і п.3, і пояснити отримані результати. 4.Завдання: Швидке перетворення Фур`є за основою 4 над 256-точками 4.Моделювання функції:
Параметри функції: Форма сигнала – синус; Частота – 20; Амплітуда – 5; Фаза - 0; Інтервал виборок 0.001 Текст програми на мові С: Main.cpp //------------------------------------------------------------------- #include <vcl.h> #pragma hdrstop #include "Main.h" #include <fstream.h> #include <math.h> //#include <SysUtils.h> //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; double a[512]; //-----...