Міністерство освіти та науки України Національний університет „Львівська політехніка” кафедра ЕОМ Лабораторна робота №3 з курсу: „Алгоритми і засоби цифрової обробки сигналів” Тема: Швидкі алгоритми обчислення дискретних тригонометричних перетворень Львів – 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них перетворень.