Лабораторна робота № 7
"Побудова алгоритмів цифрового оброблення сигналів ефективних за часовою складністю.
Швидке перетворення Фур'е".
Мета роботи : Ознайомлення зі способом зменшення часової складності.
Зміст роботи:
I. Теоритична частина.
Цифрове оброблення сигналів.
Пряма згортка.
Швидка згортка.
Дискретне перетворювання Фур'е (ДПФ).
Швидке перетворювання Фур'е (ШПФ).
Метод розбиття вхідних даних.
Метод розбиття задачі на підзадачі.
II. Практична частина
Скласти програму ШПФ (Pascal , C).
Порівняти часову і програмну складність алгоритмів ДПФ і ШПФ.
Порівняти часову і програмну складність алгоритмів прямої згортки та швидкої згортки
III. Висновки.
_____________________________________________________________________________
Цифрове оброблення сигналів.
В сучасних каналах зв'зку широко використовуються пристрої цифрового оброблення сигналів.
Ці пристрої реалізують той чи інший алгоритм цифрового оброблення. Прикладами таких алгоритмів є аналіз і синтез цифрових фільтрів, спектральний аналіз сигналів, модуляція сигналу, демодуляція, перенос та інверсія спектру та інші.
Цифровий фільтр являє собою пристрій, який перетворює вхідний сигнал. Вид перетворення
повністю визначається характеристиками фільтру. Фільтр призначений для частотної селекції сигналів. Він пропускає з малим ослаьленням корисні частотні складові (гармоніки) спектра сигналу і значно послаблює гармоніки, присутність яких у спектрі вихідного сигналу є небажаною.
Існують різні способи реалізації фільтрів зі скінченими імпульсними характеристиками.Серед них -
пряма згортка і шидка згортка.
Пряма згортка
Нехай x(nT) і h(nT) – дві періодичні послідовності з періодами по N відліків.
Періодичною ( циклічною ) згорткою таких послідовностей називається послідовність y(nT), яка визначається співвідношенням:
EMBED Equation.3 , (1)
Послідовність y(nT) також є періодичною з періодом N відліків, тому достатньо обчислити її на одному періоді, наприклад при n = 0, 1, … ,N-1. Це співвідношення справедливе і для скінчених послідовностей x(nT) і h(nT) (n = 0, 1, … ,N-1), якщо розглядати їх як один період відповідних їм періодичним послідовностям. Періодична згортка скінчених послідовностей також буде скінченою.


Швидка згортка.
Одним із варіантів швидкої згортки може бути обчислення згорки за допомогою операції ДПФ.
Для цього необхідно виконати наступні дії:
Обчислення ДПФ послідовності x(nT) :
EMBED Equation.3 , k = 0, 1, … ,N-1
EMBED Equation.3 ;
Обчислення ДПФ послідовності h(nT) :
EMBED Equation.3 , k = 0, 1, … ,N-1
Перемноження коефіціентів отриманих ДПФ :
Y(k) = X(k) H(k), k = 0, 1, … ,N-1
Обчислення ЗДПФ послідовності Y(k) :
EMBED Equation.3 , n = 0, 1, … ,N-1
Послідовність y(nT) і є згортка.
Звідки видно, що операція згортки в часовій області еквівалентна множенню в частотній області.
Це співвідношення має велике значення через те, що дозволяють виконувати лінійне оброблення сигналів і моделювати лінійні системи. Стосовно до цих задач x(nT) та y(nT) розглядаються як вхідний та віхідний сигнали системи, а h(nT) – як її імпульсна характеристика.
Таким чином, згортку можна виконувати або безпосередньо за співвідношенням (1), або непрямим методом, використовуючи ДПФ для перетворення періодичних функцій часу в частотну область. В останньому випадку для отримання Y(k) при заданих h(nT) i x(nT) потрібно обчислити і перемножити відповідні перетворення H(k) i X(k). Після чого Y(k) перетворюється за допомогою зворотнього ШПФ у вихідний сигнал системи y(nT).
На перший погляд обчислення згортки в частотній області здається більш тривалою операцією в порівнянні з прямим методом. Насправді ж непрямий метод може бути швидшим. Причина цього полягає в існуванні ефективного методу обчислення ДПФ та ЗДПФ, відомого як "Швидке перетворення Фур'е".
Розглянемо алгоритм ШПФ проріджуванням по часу, нормальним порядком відліків на вході та двійково-інверсним на виході. На рис1 наведено граф алгоритму для 16 відліків(N=16).
Базовою операцією ШПФ з проріджуванням по часу є "метелик"

EMBED Visio.Drawing.5
Рис.1 Базова операція "метелик" ШПФ.

C1 = A + WB = ( ReA + ImA) + ( ReW + ImW )*( ReB + ImB )
C1 = A – WB = ( ReA + ImA) - ( ReW + ImW )*( ReB + ImB )
ReC1 = ReA + (ReW * ReB – ImW * ImB)
ReC2 = ReA - (ReW * ReB – ImW * ImB)
ImC1 = ImA + (ImW * ReB + ReW * ImB)
ImC2 = ImA - (ImW * ReB + ReW * ImB)
EMBED Equation.3
EMBED Equation.3
На першому етапі всі коефіціенти W дорівнюють W0 , на другому - W0 , W4, на третьому - W0 , W2, W4, W6 , на останньому - W0 , W1, W2 , W3, W4, W5 , W6, W7 .

EMBED Visio.Drawing.5
Рис.2 Граф алгоритму ШПФ (N=16)

ф
ф




___________________________________________________________________
EMBED Equation.3 ,
m = 0, 1, … ,N-1 EMBED Equation.3 .
Де пара співвідношень
EMBED Equation.3 , n = 0, 1, … ,N-1
EMBED Equation.3 , n = 0, 1, … ,N-1
W = exp(2?j/N)
Являють собою ДПФ для двох періодичних послідовностей.