Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
Завдання
Варіант № 26
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
1024
Основа ШПФ
2
Прорідження
часове
Частота роботи процесора
1,5 МГц
Розрядність вхідних даних
20 (10+10)
Тип вхідного інтерфейсу, пристрою
Зовнішня пам’ять
Тип вихідного інтерфейсу, пристрою
CAN
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора
2.1. Побудова графа алгоритму ШПФ з основою 2
Якщо число N є ступенем 2, то його можна записати як (N/2) * 2; аналогічно N/2 = (M/4) * 2 і т.д. В результаті елементи початкового одновимірного масиву можна розподілити таким чином, щоб елементарними операціями були двохточкові ШПФ. Для побудови графу N-точкового ШПФ з основою 2 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином:
Nяр = Log2N, для N=1024, Log21024 = 10;
Nм = N/2 = 1024/2= 512.
Граф-алгоритм для 32 точкового ШПФ за основою 2 показаний на рис. 2.
Рис.2. Граф 32-точкового ШПФ за основою 2 з прорідженням за часом
На рис. 2 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз.
Метелик ШПФ показаний на рис. 3, де
Рис. 3. Двохточкове ШПФ (Метелик)
X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники.
2.2. Біт інверсний порядок видачі даних
Для реалізації ШПФ з прорідженням по частоті 1024-точкове ШПФ розділяють на 512 по 2-точкових ШПФ, далі на 256 4-точкових ШПФ, і так далі аж до 1024- точкового ШПФ.
Ще однією особливістю алгоритму з прорідженням за частотою є те, що прямий порядок слідування даних на вході графу змінюється двійково-інверсним на виході. Тому для видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в табл.1.
Таблиця 1. Біт-інверсне прорідження
Номер
Двійкове представлення
Двійкова інверсія
Двійково-інверсний номер
0
0000000000
0000000000
0
1
0000000001
1000000000
512
2
0000000010
0100000000
256
3
0000000011
1100000000
768
4
0000000100
0010000000
128
5
0000000101
1010000000
640
6
0000000110
0110000000
384
7
0000000111
1110000000
896
8
0000001000
0001000000
64
9
0000001001
1001000000
576
10
0000001010
0101000000
320
11
0000001011
1101000000
832
…
…
…
…
1021
1111111101
1011111111
383
1022
1111111110
0111111111
511
1023
1111111111
1111111111
1023
2.3. Блок-схема перетворення
Рис. 4. Блок-схема алгоритму 1024-точкового перетворення за основою 2
3. Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – кількість точок вхідного перетворення;
base=2
N=1024
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
Для виконання базової операції «метелик» необхідно:
4 операцій множення;
6 операцій додавання;
10 операцій читання з пам`яті:
- 2*2=4 (для читання дійсної та уявної частини вхідних відліків);
- 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів);
4 операцій запису:
- 2*2=4 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 24 операцій: Nна 1 мет=24 (оп).
Тривалість виконання обчислення ШПФ:
Загальна частота роботи зовнішньої пам’яті(флешка): , звідси цикл надходження команди: .
Тривалість надходження даних у процесор для обробки:
Тнадх=2,5нс– такт надходження даних;
Частота роботи CAN шини: , звідси цикл надходження команди: . І оскільки шина CAN опрацьовує по 20 розрядів, необхідно ще помножити на 20.
Тривалість виходу даних із процесора:
Твих=63нс*20розрядів=1260 нс – такт виходу даних;
Тривалість надходження даних у процесор, тривалість обчислення ШПФ та тривалість виходу даних із процесора:
4 Розробка функціональної схеми
Рис.5. Фунціональна схема
Controller Area Network, (CAN) (локальна мережа контролерів, він же CAN-Bus і Інтерфейс CAN) – стандарт, призначений для організації високонадійних та недорогих каналів зв’язку у розподілених системах керування. Найчастіше CAN-інтерфейс використовується як зв’язна ланка між головною магістраллю та багатьма допоміжними датчиками, механізмами і т.д., підключення яких до центральної магістралі не завжди доцільне.
Universal Serial Bus (Інтерфейс USB) є послідовною, напівдуплексною, двонаправленою шиною. Специфікація периферійної шини USB була розроблена лідерами комп'ютерної і телекомунікаційної промисловості (Compaq, DEC, IBM, Intel, Microsoft, NEC і Northern Telecom) для підключення комп'ютерної периферії поза корпусом ПК з автоматичною автоконфігурацією (Plug&Play). Перша версія стандарту з’явилася в 1996 р. Агресивна політика Intel по впровадженню цього інтерфейсу стимулює поступове зникнення низькошвидкісних інтерфейсів, як RS 232C, Access.bus і тому подібне. Проте для високошвидкісних пристроїв строгішими вимогами до продуктивності конкурентом USB є інтерфейс IEEE 1394.
5. Розробка програми виконання алгоритму ШПФ
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис.6.Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент массиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 10*1024*3=30720 (10 - кількість ярусів, 1024 - кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
N=1024;
struct complex
{ double re;
double im;
};
complex W[1*N];
complex matrix[N];
int i,imax,j,x1,x2;
int f; //номер етапу
int p; //номер операції в етапі
complex temp1,temp2;
f=0;
for(imax = N-1; imax <=0; imax = (imax+1)/2 – 1)
{ p=0;
for(j = 0; j < N; j = j + (imax+1)*2)
{
x1 = j + (imax+1)*0;
x2 = j + (imax+1)*1;
for (i = 0; i <= imax; i++)
{
temp1.re=
matrix[x1+i].re
+ matrix[x2+i].re*W[n*1024+p*1+0].re –
- matrix[x2+i].im*W[n*1024+p*1+0].im;
temp1.im=
matrix[x1+i].im
+ matrix[x2+i].re*W[n*1024+p*1+0].im +
+ matrix[x2+i].im*W[n*1024+p*1+0].re;
temp2.re=
matrix[x1+i].re
+ matrix[x2+i].re*W[n*1024+p*1+0].im +
+ matrix[x2+i].im*W[n*1024+p*1+0].re;
temp2.im=
matrix[x1+i].im
- matrix[x2+i].re*W[n*1024+p*1+0].re +
+ matrix[x2+i].im*W[n*1024+p*1+0].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;
}
p++;
}
f++;
}
Значення imax+1 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 512,256, …, 2, 1. На першому ярусі є 512 групи операцій по 2 відліка кожна, на другому – 256 груп і збірка ведеться по 2 відлікам і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляє вже безпосередньо групу.
Змінні temp1, temp2 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаючого множника для даної базової операції.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора