Швидкі алгоритми обчислення дискретних тригонометричних перетворень. Лабораторна робота з Інші. Робота № 523007

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

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра ЕОМ

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

Рік:

2004

Тип роботи:

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

Предмет:

Інші

Група:

КСМ

Завантажити

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

Міністерство Освіти і Науки України Національний Університет “Львівська політехніка” Кафедра ЕОМ Лабораторна робота № 3 Швидкі алгоритми обчисленнядискретних тригонометричних перетворень Виконали: ст.гр. КСМ-53 Хлян С.В. Прийняв: Ваврук В.Я. Львів 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. Дискретне перетворення Фур’є Дискретне перетворення Фур’є (ДПФ) кінцевої послідовності {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. Порядок виконання роботи Застосовуючи методики розкладу, отримати алгоритм обчислення заданого перетворення за певними “основою” і розмірністю. 13. Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Algorithm : ШПФ2 (швидке переотворення Фур’є за основою 2) з прорідженням за часом. N = 512. x(n) = ; n = 0, 1, ..., N-1. 2. Скласти процедуру на мові високого рівня для безпосереднього (прямого) обчислення тригонометричного перетворення. 3. Скласти процедуру на мові високого рівня для обчислення швидкого перетворення по алгоритму отриманому в п.1. #include "stdio.h" #include "conio.h" #include "math.h" #define FNAME "d:\\res.txt\0" float metelyk1(float ReA,float ReB,float ImA,float ImB,float ReW,float ImW) { return(ReA+ReB*ReW+ImB*ImW); } float metelyk2(float ReA,float ReB,float ImA,float ImB,float ReW,float ImW) { return(ImA-ReB*ImW+ImB*ReW); } float metelyk3(float ReA,float ReB,float ImA,float ImB,float ReW,float ImW) { return(ReA-ReB*ReW-ImB*ImW); } float metelyk4(float ReA,float ReB,float ImA,float ImB,float ReW,float ImW) { return(ReA+ReB*ReW-ImB*ImW); } void main() { float Re[512],Im[512],ReA,ReB,ImA,ImB,W1[10][512],W2[10][512],ReW,ImW; int a,b,N=512,r=2,delta,k,i,x,j,y,p; char fname[20] = FNAME; FILE *out; clrscr; for (i=0; i<=511; i++) { Re[i]=cos(i/511); Im[i]=0; } for (i=1; i<=9; i++) { for (j=0; j<=511; j++) { if (i==1) p=0; else if (i==2) p=((j>>7)%2)*128; else if (i==3) p=((j>>6)%2)*128+((j>>7)%2)*64; else if (i==4) p=((j>>5)%2)*128+((j>>6)%2)*64+((j>>7)%2)*32; else if (i==5) p=((j>>4)%2)*128+((j>>5)%2)*64+((j>>6)%2)*32+((j>>7)%2)*16; else if (i==6) p=((j>>3)%2)*128+((j>>4)%2)*64+((j>>5)%2)*32+((j>>6)%2)*16+((j>>7)%2)*8; else if (i==7) p=((j>>2)%2)*128+((j>>3)%2)*64+((j>>4)%2)*32+((j>>5)%2)*16+((j>>6)%2)*8+((j>>7)%2)*4; else if (i==8) p=((j>>1)%2)*128+((j>>2)%2)*64+((j>>3)%2)*32+((j>>4)%2)*16+((j>>5)%2)*8+((j>>6)%2)*4+((j>>6)%2)*2; else if (i==9) p=(j%2)*128+((j>>1)%2)*64+((j>>2)%2)*32+((j>>3)%2)*16+((j>>4)%2)*8+((j>>5)%2)*4+((j>>6)%2)*2+(j>>7)%2; W1[i][j]=cos(2*3.1415/N*p); W2[i][j]=sin(2*3.1415/N*p); } } for (k=1; k<=9; k++) { delta=N/pow(r,k); x=0; y=x+delta; ReA=Re[x]; ReB=Re[y]; ImA=Im[x]; ImB=Im[y]; ReW=W1[k][y]; ImW=W2[k][y]; Re[x]=metelyk1(ReA,ReB,ImA,ImB,ReW,ImW); Im[x]=metelyk2(ReA,ReB,ImA,ImB,ReW,ImW); Re[y]=metelyk3(ReA,ReB,ImA,ImB,ReW,ImW); Im[x]=metelyk4(ReA,ReB,ImA,ImB,ReW,ImW); for (j=1; j<256; j++) { if ((y+delta)>511) x=(y+delta)%512+1; else x=(y+delta); if ((x+delta)>511) y=(x+delta)%512+1; else y=(x+delta); ReA=Re[x]; ReB=Re[y]; ImA=Im[x]; ImB=Im[y]; ReW=W1[k][y]; ImW=W2[k][y]; Re[x]=metelyk1(ReA,ReB,ImA,ImB,ReW,ImW); Im[x]=metelyk2(ReA,ReB,ImA,ImB,ReW,ImW); Re[y]=metelyk3(ReA,ReB,ImA,ImB,ReW,ImW); Im[x]=metelyk4(ReA,ReB,ImA,ImB,ReW,ImW); } } if ((out = fopen(fname, "at")) == NULL) { printf("Erorr open file"); getch(); return; } //zapys for (i=1; i<=512; i++) { fprintf(out,"\n%i %f %f",i,Re[i],Im[i]); } fclose(out); getch(); } 4. Виміряти часи виконання процедур п.2 і п.3. Дане ШПФ виконується в 9 рівнів. На першому рівні різниця між першим і наступним елементом, які приймають участь в “метелику” є 256, тобто рівна N/r, де N – це кількість точок перетворення, а r – це основа перетворення (в моєму випадку – це 2). Вже на другому рівні різниця між елементами стає в двічі меншою 128 – (N/r2) , а в наступному ще в два рази меншою і так далі поки на 9-ому етапі не складе одиницю. Намалюємо таблицю, де буде показано як змінюються вхідні дані до “метелика”: 1 2 3 4 5 6 7 8 9 0 256 1 257 2 258 .... 254 510 255 511 0 128 256 384 1 129 .... 127 255 383 511 0 64 128 192 256 320 .... 319 383 447 511 0 32 64 96 128 160 .... 415 447 479 511 0 16 32 48 64 80 .... 463 479 495 511 0 8 16 24 32 40 .... 487 495 503 511 0 4 8 12 16 20 .... 499 503 507 511 0 2 4 6 8 10 .... 505 507 509 511 0 1 2 3 4 5 .... 508 509 510 511 Кількість метеликів при даному перетворенні – N/2*log2N= 512/2*9= 2304. Кожний з цих всіх “метеликів” має в собі 4 операції множення і 8 операцій додавання чи віднімання. Порахуємо загальну кількість цих всіх операцій: Множення: 2304*4=9216 Додавання: 2304*8=18432 Загально: 27648 Але звичайно всі вони не виконуються. 5. Порівняти часи виконання процедур п.2 і п.3, і пояснити отримані результати. Нам відомо, що комплексні множники в першому рівні є однакові і “нульові”, тому велика кількість операцій в метелику просто пропадає (не виконується), тому загальна дійсна кількість операцій при ШПФ буде значно меншою, бо навіть на 9-ому етапі ШПФ є пусті операції. Я старався приблизно обрахувати скільки ж операцій пропадає і отримав такий результат: На першому та другому етапах реально виконується тільки операції додавання (на 25%), а операції множення не виконуються; А вже починаючи з наступних етапів операції виконуються вже краще (їх число збільшується). На 3 рівні вже є 6 додавань і 2,5 множень. На 4 рівні кількість операцій, які не виконуються рівне 25%, а з кожним наступним етапом цей показник зменшується приблизно на 2. Отже, з загальної кількості операцій 27648 реально виконується приблизно 20120, а це майже 73%. Висновок: на даній лабораторній роботі я набагато ближче познайомився з перетвореннями Фур’є, а найкраще з ШПФ. Також дійшов висновку, що не всі операції в такому перетворенні можуть виконуватися згідно формул, можливі варіанти коли комплексні множники рівні 0, то операцію множення чи додавання не обов’язково виконувати, оскільки результат виконання вже відомий наперед, а на “пусту” операцію процесор може затрачати свій дорогоцінний час.

Лабораторна робота Інші

31.03.2013 16:03-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись