Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
Завдання
Варіант № 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 визначають адресу повертаю чого множника для даної базової операції.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора