Швидкі алгоритми обчислення дискретних тригонометричних перетворень . Лабораторна робота з Алгоритми і засоби цифрової обробки сигналів. Робота № 200072

Швидкі алгоритми обчислення дискретних тригонометричних перетворень

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми і засоби цифрової обробки сигналів

Група:

КСМ

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти та науки України Національний університет „Львівська політехніка” кафедра ЕОМ Лабораторна робота №3 з курсу: „Алгоритми і засоби цифрової обробки сигналів” Тема: Швидкі алгоритми обчисленнядискретних тригонометричних перетворень Виконав: студент групи КСМ-5 Львів – 2004 р. Мета роботи: Дослідити швидкі алгоритми дискретних тригонометричних перетворень і порівняти їх з алгоритмами безпосереднього обчислення т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. Дискретне перетворення Хартлі Дискретне перетворення Хартлі (ДПХ) кінцевої 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. Порядок виконання Для поставленої задачі застосовуємо методики розкладу дискретного тригонометричного перетворення вхідної послідовності х(n), для даного варіанту N рівне 256 елементів. Згідно завдання отримаємо послідовність результатів дискретного тригонометричного перетворення вхідної послідовності від заданих значень х(n), де n = 0,1, …, N – 1. Дані про час виконання приведено далі: Висновок: На цій лабораторній роботі дослідив швидкі алгоритми дискретних тригонометричних перетворень і порівняв їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень.

Лабораторна робота Алгоритми і засоби цифрової обробки сигналів

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись