Лабораторна робота № 3
Швидкі алгоритми обчисленнядискретних тригонометричних перетворень
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень і порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень.
Теоретичні відомості
Алгоритми швидкого перетворення Фур’є (ШПФ) можуть бути отримані за допомогою послідовного застосування операції розкладу одномірного масиву вхідних відліків сигналу на двохмірний. Ця операція здійснена тільки у випадку, коли 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 визначається як
EMBED Equation.2 , k = 0, 1, ..., N-1 (1)
де EMBED Equation.2 .
Суть алгоритмів ШПФ в тому, що якщо 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. Тоді формулу розкладу можна записати так:
EMBED Equation.2
де 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 - точкове ДПФ можна записати так
EMBED Equation.2
де X1(k) і X2(k) є N/2 - точкові ДПФ першої та другої половини відліків вихідної послідовності.
Алгоритми ШПФ, що отримані з застосуванням цієї методики називаються алгоритмами з прорідженням по частоті.
Дискретне перетворення Хартлі
Дискретне перетворення Хартлі (ДПХ) кінцевої N-точкової послідовності x(n), n=0,1,...,N-1, N=2m m=1,2,3,..., т.е. - H(k) = ДПХN{x(n)}, визначається як
EMBED Equation.2 k = 0,1,...,N-1,
де EMBED Equation.2 , EMBED Equation.2 .
Алгоритм БПХ2 з прорідженням в часі. Позначимо через H1(k) і H2(k) ДПХ парних і непарних членів послідовності x(n): H1(k) = ДПХN/2{x(2n)} і H2(k) = ДПХN/2{x(2n+1)}.
Застосовуючи методику аналогічну як і при побудові алгоритмів ШПФ і виконавши відповідні перетворення отримаємо процедуру для розкладу алгоритмів БПХ.
H(k) = H1(k) + a; H(k+N/2) = H1(k) - a;
H(N/2-k) = H1(N/2-k) + b; H(N-k) = H1(N/2-k) - b;
EMBED Equation.2 ; EMBED Equation.2 .
де k = 0,1,...,N/4-1;
Розклад необхідно проводити до тих пір поки H1(k) і H2(k) не будуть двухточковими ДПХ.
Алгоритм ШПХ2 з прорідженням по частоті. Загальна формула розкладу алгоритму з прорідженням по частоті задається виразами:
H(2k) = H1(k); H(2k+1) = H2(k), k=0,...,N/2-1
де H1(k), H2(k) - N/2-точкові ДПХ послідовностів x1(n), x2(n); x1(n) = x(n) +x(n+N/2), EMBED Equation.2 , n = 0,1,...,N/2-1.
На основі цього запишемо процедуру переходу до перетворень меншої розмірності в N-точковому алгоритмі ШПХ2:
a = x(n) - x(n+N/2); b = x(N/2-n) - x(N-n);
x1(n) = x(n) + x(n+N/2); x1(N/2-n)= x(N/2-n) + x(N-n);
EMBED Equation.2 EMBED Equation.2 ,
n = 1, 2, ...,N/4-1.
Продовжуючи на основі цієї процедури розбиття отриманих послідовностей менших розмірностів до двохточкових, синтезуємо алгоритм ШПХ2 з прорідженням по частоті.
Комбінуючи формули розкладу алгоритмів БПХ за основою два і чотири з прорідженням в часі, отримаємо формули розкладу алгоритму за “рощепленою основою” 2-4 (БПХ24)
EMBED Equation.2 ,
де H0(k) = ДПХN/2{x(2n)}, Hl(k) = ДПХN/4{xl(n)}, xl(n) = x(4n+l), l=1,3.
При переході до перетворень меншої розмірності використаємо процедуру:
a13 = H1(0) + H3(0); a31 = H1(0) - H3(0);
d1 = EMBED Equation.2 .H1(N/8); d3 = EMBED Equation.2 .H3(N/8);
H(0) = H0(0) + a13; H(N/4) = H0(N/4) + a31;
H(N/2) = H0(0) - a13; H(3N/4) = H0(N/4) - a31;
H(N/8) = H0(N/8) + d1; H(3N/8) = H0(3N/8) + d3;
H(5N/8) = H0(N/8) - d1; H(7N/8) = H0(3N/8) - d3;
EMBED Equation.2 ;
EMBED Equation.2 ; l=1,3;
a13 = a1 + a3; a31 = a1 - a3; b13 = b1 + b3; b31 = b3- b1;
H(k) = H0(k) + a13; H(N/4-k) = H0(N/4-k) + a31;
H(k+N/4) = H0(k+N/4) + b31; H(N/2-k) = H0(N/2-k) + b13;
H(k+N/2) = H0(k) - a13; H(3N/4-k) = H0(N/4-k) - a31;
H(k+3N/4) = H0(k+N/4) - b31; H(N-k) = H0(N/2-k) - b13,
k=1,2...,N/8-1.
Продовжуючи процес розбиття до двох і чотирьохточкових перетворень, синтезуємо необхідний алгоритм ШПХ24.
Порядок виконання роботи
1. Застосовуючи методики розкладу, отримати алгоритм обчислення заданого перетворення за певними “основою” і розмірністю.
2. Скласти процедуру на мові високого рівня для безпосереднього (прямого) обчислення тригонометричного перетворення.
3. Скласти процедуру на мові високого рівня для обчислення швидкого перетворення по алгоритму отриманому в п.1.
4. Виміряти часи виконання процедур п.2 і п.3.
5. Порівняти часи виконання процедур п.2 і п.3, і пояснити отримані результати.
Література
1. Е.Шрюфер. Обробка сигналів. Цифрова обробка дискретизованих сигналів.-К.:Либідь, 1992.-296 с.
2. И.З.Гоноровский. Радиотехнические цепи и сигналы.-М.:Радио и связь, 1986.- 512с.
3. Радиотехнические цепи и сигналы. Примеры и задачи. Учебное пособие для вузов/Под ред. И.З.Гоноровского.-М.:Радио и связь, 1989.-248 с.
Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.-М.:Мир, 1978.-848 з.
+5. Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
