Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості icon

Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості



НазваниеМета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості
Дата конвертации11.09.2012
Размер98.75 Kb.
ТипДокументы

Лабораторна робота № 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.











5

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

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

N = 256

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








6

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

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

N = 256

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








7

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

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

N = 512

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








8

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

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

N = 512

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











9

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

Algorithm : ШПХ24 (швидке переотворення Хартлі за розщепленою основою 2-4) з прорідженням за часом.

N = 512.

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








10

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

Algorithm : ШПХ24 (швидке переотворення Хартлі за розщепленою основою 2-4) з прорідженням за частотою.

N = 512

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








11

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

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

N = 512.

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








12

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

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

N = 512.

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











13

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


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


N = 512.

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








14

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


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


N = 512.


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











Похожие:

Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconРоботи мета написання курсової роботи ~
...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconНа методичні вказівки "Стиск зображень з використанням дискретних косинусних перетворень"
Ваврук, Р. Попович до лабораторної роботи з дисципліни “Проектування комп’ютерних засобів цифрової обробки сигналів та зображень”...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconЗавдання та рекомендації до виконання курсової роботи мета написання курсової роботи
...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconМета роботи: вивчити методику розрахунку І вимірювання опору розтікання струму в землі заземлюючих пристроїв. Теоретичні відомості
Електротравма це травма, яка виникла під дією електричного струму або електричної дуги
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconПаралельні та розподілені обчислення
Мета роботи. Побудувати діючу мережу Петрі та довести коректність її роботи шляхом моделювання на пк
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconРеферат з курсу " Лінгвістичне забезпечення інтелектуальних систем " на тему: "Синтаксичний аналіз у системах автоматичного перекладу: концепції та алгоритми"
Синтаксичний аналіз (СінАн) організований і описаний у вигляді процесу перетворень з заданою послідовністю дій
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconМета роботи: Дослідити шляхи виникнення обчислювальної похибки та її вплив на точність обчисленнь. Проаналізувати величину похибки при обчисленні деяких математичних функцій. Загальні відомості
При реалізації обчислень на еом/спеціалізованому пристрої необхідно враховувати ефекти, які викликані кінцевою розрядністю використовуваних...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconМета роботи: ознайомлення з основними методами зменшення шуму. Вибір ефективних засобів зменшення шуму. Короткі теоретичні відомості
Шумом називають небажаний для людини звук або сполучення звуків. З фізичної точки зору шум- неупорядковане сполучення звуків різних...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconЛабораторна робота №2 Комутатори Ethernet
Мета роботи: Дослідити принципи застосування і роботи комутаторів Ethernet та їх ефективне використання в мережі. Визначити внутрішню...
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень І порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень. Теоретичні відомості iconПроектування комп’ютерних засобів цифрової обробки сигналів та зображень
Безвтратні методи стиску не забезпечують потрібного у багатьох випадках степеня стиску зображень. У цьому разі необхідно застосовувати...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы