Завдання Варіант № 5 Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними: 5 16384 2 T 1,0 20 (10+10) PCI Зовнішня пам'ять    Кількість точок 16384  Основа ШПФ 2  Прорідження часове  Частота роботи процесора  1,0 МГц  Розрядність вхідних даних 20(10+10)  Тип вхідного інтерфейсу PCI  Тип вихідного інтерфейсу Зовнішня пам'ять   Зміст Вступ 5 1 Теоретичний розділ 6 1.1 Опис швидкого перетворення Фур’є з прорідженням в часі 6 2 Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 9 3 Розрахунковий розділ 11 4 Розробка функціональної схеми 13 5 Розробка програми виконання алгоритму ШПФ 15 Висновки 19 Література 20 2 Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора Табл.2.1. Двійково-інверсна перестановка даних Номер Двійкове представлення Двійкова інверсія Двійково-інверсний номер  0 0000 0000 0  1 0001 1000 8  2 0010 0100 4  3 0011 1100 12  4 0100 0010 2  5 0101 1010 10  6 0110 0110 6  7 0111 1110 14  8 1000 0001 1  9 1001 1001 9  10 1010 0101 5  11 1011 1101 13  … … … …  16381 11111111111101 1011111111111 12287  16382 11111111111110 01111111111111 8191  16383 11111111111111 11111111111111 16383   / Рис.2.1 Блок-схема алгоритму 16384-точкового перетворення за основою 2 / Рис.2.2 Граф 16384-точкового ШПФ за основою 2 з прорідженням по часу 3 Розрахунковий розділ 5 16384 2 T 1,0 20 (10+10) PCI Зовнішня пам'ять    Частота роботи процесора:
, звідси цикл виконання команди:
. base – основа базової операції «метелик»; N – к-ть точок вх. перетворення; base=2; N=16384;
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
;
;
Для виконання базової операції «метелик» необхідно: 4 операцій множення; 6 операцій додавання; 10 операцій читання з пам`яті: - 2*2=4 (для читання дійсної та уявної частини вхідних відліків); - 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів); 4 операцій запису: - 2*2=4 (для запису дійсної та уявної частини вхідних відліків); В результаті на одну базову операцію припадає 24 операцій: Nна 1 мет=24 (оп). Тривалість виконання обчислення ШПФ:
Тривалість надходження даних у процесор для обробки(PCI): Тнадх=0,3нс – такт надходження даних в PCI
Тривалість виходу даних із процесору (Зовнішня пам'ять): Частота роботиUSB:
,(частота роботи взагальному) звідси цикл надходження команди:
. Тривалість надходження даних у процесор для обробки: Твих=2,5нс– такт надходження даних;
Тривалість надходження даних у процессор, виходу із нього та тривалість обчислення ШПФ:
4 Розробка функціональної схеми / Рис.4.1 Фунціональна схема 5 Розробка програми виконання алгоритму ШПФ Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином: / Рис.5.1. Узагальнена блок-схема алгоритму Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції. Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент масиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 14*16384*3=688128 (14 – кількість ярусів, 16384 – кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом. Текст програми, написаної на мові С, поданий нижче N=16384; struct complex { double re; double im; }; complex W[3*N]; complex matrix[N]; int i,imax,j,x1,x2,x3,x4; int f; //номер етапу int p; //номер операції в етапі complex temp1,temp2,temp3,temp4; f=0; for(imax = N-1; imax <=0; imax = (imax+1)/4 – 1) { p=0; for(j = 0; j < N; j = j + (imax+1)*4) { x1 = j + (imax+1)*0; x2 = j + (imax+1)*1; x3 = j + (imax+1)*2; x4 = j + (imax+1)*3; for (i = 0; i <= imax; i++) { temp1.re= matrix[x1+i].re + matrix[x3+i].re*W[n*16384+p*3+1].re – - matrix[x3+i].im*W[n*16384+p*3+1].im + + matrix[x2+i].re*W[n*16384+p*3+0].re – - matrix[x2+i].im*W[n*16384+p*3+0].im + + matrix[x4+i].re*W[n*16384+p*3+2].re – - matrix[x4+i].im*W[n*16384+p*3+2].im; temp1.im= matrix[x1+i].im + matrix[x3+i].re*W[n*16384+p*3+1].im + + matrix[x3+i].im*W[n*16384+p*3+1].re + + matrix[x2+i].re*W[n*16384+p*3+0].im + + matrix[x2+i].im*W[n*16384+p*3+0].re + + matrix[x4+i].re*W[n*16384+p*3+2].im + + matrix[x4+i].im*W[n*16384+p*3+2].re; temp2.re= matrix[x1+i].re - matrix[x3+i].re*W[n*16384+p*3+1].re + + matrix[x3+i].im*W[n*16384+p*3+1].im + + matrix[x2+i].re*W[n*16384+p*3+0].im + + matrix[x2+i].im*W[n*16384+p*3+0].re - - matrix[x4+i].re*W[n*16384+p*3+2].im – - matrix[x4+i].im*W[n*16384+p*3+2].re; temp2.im= matrix[x1+i].im - matrix[x3+i].re*W[n*16384+p*3+1].im - - matrix[x3+i].im*W[n*16384+p*3+1].re - - matrix[x2+i].re*W[n*16384+p*3+0].re + + matrix[x2+i].im*W[n*16384+p*3+0].im - - matrix[x4+i].re*W[n*16384+p*3+2].re + + matrix[x4+i].im*W[n*16384+p*3+2].im; temp3.re= matrix[x1+i].re + matrix[x3+i].re*W[n*16384+p*3+1].re – - matrix[x3+i].im*W[n*16384+p*3+1].im - - matrix[x2+i].re*W[n*16384+p*3+0].re + + matrix[x2+i].im*W[n*16384+p*3+0].im + + matrix[x4+i].re*W[n*16384+p*3+2].re – - matrix[x4+i].im*W[n*16384+p*3+2].im; temp3.im= matrix[x1+i].im + matrix[x3+i].re*W[n*16384+p*3+1].im + + matrix[x3+i].im*W[n*16384+p*3+1].re - - matrix[x2+i].re*W[n*16384+p*3+0].im - - matrix[x2+i].im*W[n*16384+p*3+0].re + + matrix[x4+i].re*W[n*16384+p*3+2].im + + matrix[x4+i].im*W[n*16384+p*3+2].re; temp4.re= matrix[x1+i].re - matrix[x3+i].re*W[n*16384+p*3+1].re + + matrix[x3+i].im*W[n*16384+p*3+1].im - - matrix[x2+i].re*W[n*16384+p*3+0].im – - matrix[x2+i].im*W[n*16384+p*3+0].re - - matrix[x4+i].re*W[n*16384+p*3+2].re + + matrix[x4+i].im*W[n*16384+p*3+2].im; temp4.im= matrix[x1+i].im - matrix[x3+i].re*W[n*16384+p*3+1].im - - matrix[x3+i].im*W[n*16384+p*3+1].re + + matrix[x2+i].re*W[n*16384+p*3+0].re - - matrix[x2+i].im*W[n*16384+p*3+0].im - - matrix[x4+i].re*W[n*16384+p*3+2].re + + matrix[x4+i].im*W[n*16384+p*3+2].im; matrix[x1+i].re = temp1.re; matrix[x1+i].im = temp1.im; matrix[x2+i].re = temp2.re; matrix[x2+i].im = temp2.im; matrix[x3+i].re = temp3.re; matrix[x3+i].im = temp3.im; matrix[x4+i].re = temp4.re; matrix[x4+i].im = temp5.im; } p++; } f++; } Значення imax+1 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 1, 2, 4, 8, …, 16384. Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2, х3, х4. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляю вже безпосередньо групу. Змінні temp1, temp2, temp3, temp4 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаю чого множника для даної базової операції.