asyan.org
добавить свой файл
1 2
Лабораторна робота № 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 визначається як

, 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 - точкові ДПФ першої та другої половини відліків вихідної послідовності.

Алгоритми ШПФ, що отримані з застосуванням цієї методики називаються алгоритмами з прорідженням по частоті.
^ Дискретне перетворення Хартлі
Дискретне перетворення Хартлі (ДПХ) кінцевої N-точкової послідовності x(n), n=0,1,...,N-1, N=2m m=1,2,3,..., т.е. - H(k) = ДПХN{x(n)}, визначається як
k = 0,1,...,N-1,
де , .

^ Алгоритм БПХ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;
; .
де 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), , 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);

,

n = 1, 2, ...,N/4-1.
Продовжуючи на основі цієї процедури розбиття отриманих послідовностей менших розмірностів до двохточкових, синтезуємо алгоритм ШПХ2 з прорідженням по частоті.
Комбінуючи формули розкладу алгоритмів БПХ за основою два і чотири з прорідженням в часі, отримаємо формули розкладу алгоритму за “рощепленою основою” 2-4 (БПХ24)
,
де 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 = .H1(N/8); d3 = .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;
;

; 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 с.

  1. Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.-М.:Мир, 1978.-848 з.

+5. Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.


Варіанти завдань до лабораторної роботи № 3.

Nп/п

Завдання


Прізвище

Прим.

1

Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі.

Algorithm : ШПФк2 (швидке переотворення Фурье за основою 2) з прорідженням за часом.

N = 256

x(n) = ; n = 0, 1, ..., N-1.








2

Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі.

Algorithm : ШПФк2 (швидке переотворення Фурье за основою 2) з прорідженням за частотою.

N = 256

x(n) = ; n = 0, 1, ..., N-1.








3

Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі.

Algorithm : ШПФк4 (швидке переотворення Фурье за основою 4) з прорідженням за часом.

N = 256

x(n) = ; n = 0, 1, ..., N-1








4

Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі.

Algorithm : ШПФк4 (швидке переотворення Фурье за основою 4) з прорідженням за чатотою.

N = 256

x(n) = ; n = 0, 1, ..., N.










следующая страница >>