Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Звіт
до лабораторної роботи №3
Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ).
ЛАБОРАТОРНА РОБОТА №3
Тема: Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ).
Мета: Навчитися працювати з ДПФ та ШПФ.
Теоретичні відомості:
Дискретне перетворення Фур(є (ДПФ):
ДПФ - це перетворення Фур(є послідовності кінцевої довжини, що є сама по собі також послідовністю, а не перервною функцією і відповідає рівновіддаленим за частотою вибіркам перетворення Фур(є-сигнала.
ДПФ – вводиться як :
,
де х(nT) (n=0,…, N-1)- послідовність з N-часових відліків з періодом T; X(k)- послідовність (k=0,…,N-1) з N-частотних відліків; .
Формула (3.1) - пряме ДПФ.
Формула (3.2) - обернене ДПФ.
ДПФ у матричній формі:
, (3.3)
де X і x – N-вимірні вектори, X=[X(0),X(1),…,X(N-1)]T, х=[x(0),x(T),…,x((N-1)Т)]T; WN-матриця розміром N*N з елементами d(n,k), n,k-індекси за рядком, за стовпчиком d(n,k)=WNnk ; n,k=0,1,2,…N-1.
Формула (3.1) - пряме ДПФ у матричній формі.
Обернена форма формули:
x=WN-1X, (3.4)
де WN-1 - обернена матриця до матриці WN, тобто її елемент; d-1(n,k)=1/N*WN-nk .
ДПФ вводиться для представлення як періодичних послідовностей з періодом N-відліків, так і послідовності кінцевої довжини N.
Коефіцієнти ДПФ кінцевої послідовності дорівнюють значенням її у z-перетворенні у N-точках рівномірно розподілених по одиничному колу. Формула одиничного кола:
,
де к-0,1,2,…N-1.
ДПФ виконується над кінцевою послідовністю N-відліків або над періодичною послідовністю, період якої складається також з N-відліків. Оскільки характеристики спектра послідовностей таких як спектральна густина потужності, амплітуди, фази окремих частот на практиці визначають з використанням тільки кінцевого числа відліків. Звідси випливає, що ДПФ є одним з найважливіших засобів їх визначення.
Властивості ДПФ:
1.Властивість лінійності.
(3.5)
2.Зсув ДПФ.
Нехай , а y(nT) отримується з x(nT) шляхом зсуву на n0 відліків.
(3.6)
, (3.7)
де K0-зсув спектра.
3.Властивість симетрії
Якщо послідовність x(nT) є дійсною то її ДПФ задовольняє таким умовам симетрії:
Дійсна частина: Re(X(k))=Re(X(N-k))
Уявна частина: Im(X(k))= -Im(X(N-k))
(3.8)
Наслідки від властивостей ДПФ:
1) ДПФ симетричної послідовності буде дійсною, тобто
Якщо x (nT)= x ((N-n)T) ( Im (Х(k))=0
2.) Властивість симетрії дозволяє за допомогою одного ДПФ перетворити одночасно дві дійсних послідовності.
Якщо ДПФ то
Тоді:
(3.9)
4) Згортка по колу.
Нехай уU(nT) є згорткою по колу сигналів x (nT) и y(nT)
а) ,
тоді її ДПФ
б) Якщо
то її ДПФ також є згорткою
5.) Спряжена форма обернення.
Обернене ДПФ за формулою (3.2) можна обчислити за допомогою формул для прямого ДПФ.
,
де - комплексне спряження від p
(3.10)
Алгоритми швидких перетворень Фур(є (ШПФ):
Обчислення ДПФ потребує великої кількості операцій (формула 3.1): приблизно N2 додавань і N2 добутків. Якщо розглянути для реальних частин (розпишемо комплекс через уявну і дійсну частини), то операцій буде в 4 рази більше.
Отримуємо 4N2 операцій множення, додавання трохи менше.
Так як кількість обчислень, а значить і час обчислення пропорційне N2, то при прямому методі обчислень ДПФ число арифметичних операцій різко зростає зі збільшенням N, тому були розроблені алгоритми, що зменшують число операцій, які називаються ШПФ. Найчастіше застосовується :
; - натуральне число(оптимальний випадок для БПФ.
Основна ідея, що лежить в основі усіх ШПФ, полягає в зведенні N-точкового ШПФ до обчислення декількох N1-точечних ДПФ, при чому N1<<N.
Існує два великих ділення.
Алгоритми, при реалізації яких потрібна перестановка відліків x(nT) вхідної послідовності, називаються алгоритмами з проріджуванням за часом.
Алгоритми, при реалізації яких потрібна перестановка відліків X(k) вихідної послідовності, називаються алгоритмами з проріджуванням за частотою.
За ефективністю ці два різновиди алгоритмів еквівалентні і дозволяють зменшити кількість потрібних операцій в раз у порівнянні з прямим методом обчислення ДПФ.
Алгоритм з проріджуванням за часом.
Якщо послідовність x(nT) довжиною розділити на дві N/2-точечні послідовності, що складаються з x(nT) парних та окремо непарних номерів.
Запишемо ДПФ:
(3.11)
Тому що:
Проілюструємо на прикладі: N=8.
Будемо використовувати спрямовані сигнальні графи, у яких: гілки, що сходяться у вузол, сумуються, а передача по гілках здійснюється з підписаними під ними коефіцієнтами. Якщо їх немає, то коефіцієнт дорівнює 1.
Де G(k)-чотирьохточкова ДПФ парних точок; Н(к)-ДПФ непарних точок (чотирьохточечна).
Кожна із суми у (5.1) є N/2-точковим ДПФ, яке можна аналогічно через N/4 точкове ДПФ, а N/4(N/8 точечною ДПФ і т.д. доки не лишиться 2-х точечна ДПФ. Таких ступенів перетворення буде:
(=log2N=3 –у нашому прикладі.
Ми розглянемо у прикладі тільки 1-й рівень. Покажемо спрямований граф, що показує розкладення N/2-точечного ДПФ на N/4 точечне ДПФ.
Повний граф:
Алгоритм з проріджуванням за частотою:
Вхідна послідовність x(nT) розбивається на дві послідовності
n=0,1,…,Nn-1
і окремо обчислюються парні та непарні відліки ДПФ:
(3.12)
Отримані N/2-точечні ДПФ аналогічним чином можна представити через N/4-точечні і т.д. до двохточечних.
Алгоритми з проріджуванням за частотою і за часом є індивідуальними: кожний з них може бути отриман з другого шляхом взаємної заміни входу та виходу і оберненням усіх стрілок у спрямованому графі.
Завдання на лабораторну роботу:
1. Для стандартного прямокутного сигналу з частотою, що дорівнює номеру бригади, отримати його дискретний спектр за допомогою застосування ДПФ. Замалювати його амплітудно-частотну характеристику для основної частини одного періоду спектра з записом частот сигналу дискретизації та періоду спектра.
2. Проробити ті самі перетворення з стандартним трикутним сигналом.
3. Проробити ті самі перетворення з стандартним синусоїдальним сигналом.
4. Для початкового прямокутного сигналу порівняти час отримання його ДПФ та ШПФ.
5. Для початкового прямокутного сигналу повторити п.1, змінюючи декілька раз частоту дискретизації, для чого використовувати зміну інтервалу дискретизації в меню стандартного сигналу.
6. В протоколі привести отримані графіки, таблиці та математичні залежності.
7. Зробити виводи про вплив частот сигналу та його дискретизації на отриманий спектр, а також по іншій частині роботи.
Для стандартного трикутного сигналу з частотою 4 Гц був отриманий наступний спектр(за допомогою застосування ДПФ):
Спектр:
N пари
Частота, Гц
Модуль
Фаза, град,
0
0
21, 792
-180
1
0,9765625
27, 9265544
-175,6793813
2
1, 953125
421, 050818
12,0379688
3
2, 9296875
13, 7492127
12,771217
4
3, 90625
2, 7546821
-154,1067836
5
4, 8828125
2, 9320156
-154,300765
6
5, 859375
43, 3754307
26,9971383
7
6, 8359375
7, 6753946
25,4544298
8
7, 8125
2, 6680459
25,4544298
9
8, 7890625
0, 4923248
-81,319482
10
9, 765625
13, 3120728
-135,7781106
11
10, 7421875
5, 8751878
41,3837292
Для стандартного прямокутного сигналу з частотою 4 Гц був отриманий наступний спектр(за допомогою застосування ДПФ):
Спектр:
N пари
Частота, Гц
Модуль
Фаза, град,
0
0
21
0
1
0.9765625
32.5942093
-40.9399412
2
1.953125
649.5807999
-79.7156513
3
2.9296875
35.0616815
61.9787551
4
3.90625
20.8127185
21.6838722
5
4.8828125
29.8417227
-19.6955347
6
5.859375
210.4129968
-59.1193553
7
6.835937
37.148713
82.8183662
8
7.8125
20.2487068
43.2931912
9
8.7890625
26.8974208
1.7474197
10
9.765625
119.1214254
-38.4393002
11
10.7421875
38.764837
103.4755872
Для стандартного прямокутного сигналу(частота збільшена у 5 разів) був отриманий наступний спектр(за допомогою застосування ДПФ):
Спектр:
N пари
Частота, Гц
Модуль
Фаза, град,
0
0
13
0
1
0.1953125
23.5073495
-4.8552449
2
0.390625
24.3411037
-9.6957158
3
0.5859375
25.8463274
-14.5074423
4
0.78125
28.2375547
-19.2779912
5
0.9765625
31.926927
-23.9970748
6
1.171875
37.7445561
-28.6569932
7
1.3671875
47.5727784
-33.2528985
8
1.5625
66.6844624
-37.7828875
9
1.7578125
117.4015651
-42.2479456
10
1.953125
594.2369166
-46.6517762
11
2.1484375
184.7187159
128.9994535
Для стандартного прямокутного сигналу(частота збільшена у 10 разів) був отриманий наступний спектр(за допомогою застосування ДПФ):
Спектр:
N пари
Частота, Гц
Модуль
Фаза, град,
12
1.171875
34.1535928
-3.2420238
13
1.2695313
37.2452432
-3.5052416
14
1.3671875
41.3566624
-3.7666621
15
1.4648438
47.0381973
-4.02609
16
1.5625
55.3324536
-4.2833126
17
1.6601563
68.481392
-4.5380965
18
1.7578125
92.3441729
-4.7901836
19
1.8554688
148.617118
-5.0392859
20
1.953125
439.8033013
-5.2850792
21
2.0507813
389.3132132
174.4728052
22
2.1484375
127.5914595
174.2347902
23
2.2460938
73.6384075
174.0013668
Висновок
На лабораторній роботі я навчився працювати з ДПФ та ШПФ.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора