Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
Завдання
Варіант № 16
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
1024
Основа ШПФ
2
Прорідження
частотне
Частота роботи процесора
1,5 МГц
Розрядність вхідних даних
20 (10+10)
Тип вхідного інтерфейсу, пристрою
Зовнішня пам’ять
Тип вихідного інтерфейсу, пристрою
CAN
2
Зміст
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 2
2.1. Побудова графа алгоритму ШПФ з основою 2 2
2.2. Біт інверсний порядок видачі даних 4
2.2.1. Блок-схема перетворення 5
3. Розрахунковий розділ 5
4. Розробка функціональної схеми 7
4.1. Вхідний інтерфейс 7
4.2. Вихідний інтерфейс 8
5. Розробка програми 9
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора
2.1. Побудова графа алгоритму ШПФ з основою 2
Якщо число N є ступенем 2, то його можна записати як (N/2) * 2; аналогічно N/2 = (M/4) * 2 і т.д. В результаті елементи початкового одновимірного масиву можна розподілити таким чином, щоб елементарними операціями були двохточкові ШПФ. Для побудови графу N-точкового ШПФ з основою 2 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином:
Nяр = Log2N, для N=8192, Log28192 = 13;
Nм = N/2 = 8192/2= 4096.
Граф-алгоритм для 8192 точкового ШПФ за основою 2 показаний на рис. 2.
/
Рис. 2. Граф алгоритм 16-точкове ШПФ з основою 2 та прорідженням за частотою
На рис. 2 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз.
Метелик ШПФ показаний на рис. 3, де
Рис. 3. Двохточкове ШПФ (Метелик)
X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники.
2.2. Біт інверсний порядок видачі даних
Ще однією особливістю алгоритму з прорідженням за частотою є те, що прямий порядок слідування даних на вході графу змінюється двійково-інверсним на виході. Тому для видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в табл.1.
Таблиця 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
…
…
…
…
1021
1111111101
1011111111
383
1022
1111111110
0111111111
511
1023
1111111111
1111111111
1023
2.2.1. Блок-схема перетворення
/
Рис. 4. Блок-схема алгоритму 8192-точкового перетворення за основою 2
3. Розрахунковий розділ
16
1024
2
F
1,5
20 (10+10)
Зовнішня пам'ять
CAN
Частота роботи процесора: , звідси цикл виконання команди: .
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 опрацьовує по 16 розрядів, необхідно ще помножити на 16.
Тривалість виходу даних із процесора:
Твих=63нс*16розряди=1008 нс – такт виходу даних;(чисто теоретично 1,6 с)
Тривалість надходження даних у процесор, тривалість обчислення ШПФ та тривалість виходу даних із процесора:
/
Рис. 5. Функціональна схема
5. Розробка програми
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
/
Рис. 6. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент массиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 10*1024*3=30720 (10 - кількість ярусів, 1024 - кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
N=1024;
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*1024+p*3+1].re –
- matrix[x3+i].im*W[n*1024+p*3+1].im +
+ matrix[x2+i].re*W[n*1024+p*3+0].re –
- matrix[x2+i].im*W[n*1024+p*3+0].im +
+ matrix[x4+i].re*W[n*1024+p*3+2].re –
- matrix[x4+i].im*W[n*1024+p*3+2].im;
temp1.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*1024+p*3+1].im +
+ matrix[x3+i].im*W[n*1024+p*3+1].re +
+ matrix[x2+i].re*W[n*1024+p*3+0].im +
+ matrix[x2+i].im*W[n*1024+p*3+0].re +
+ matrix[x4+i].re*W[n*1024+p*3+2].im +
+ matrix[x4+i].im*W[n*1024+p*3+2].re;
temp2.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*1024+p*3+1].re +
+ matrix[x3+i].im*W[n*1024+p*3+1].im +
+ matrix[x2+i].re*W[n*1024+p*3+0].im +
+ matrix[x2+i].im*W[n*1024+p*3+0].re -
- matrix[x4+i].re*W[n*1024+p*3+2].im –
- matrix[x4+i].im*W[n*1024+p*3+2].re;
temp2.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*1024+p*3+1].im -
- matrix[x3+i].im*W[n*1024+p*3+1].re -
- matrix[x2+i].re*W[n*1024+p*3+0].re +
+ matrix[x2+i].im*W[n*1024+p*3+0].im -
- matrix[x4+i].re*W[n*1024+p*3+2].re +
+ matrix[x4+i].im*W[n*1024+p*3+2].im;
temp3.re=
matrix[x1+i].re + matrix[x3+i].re*W[n*1024+p*3+1].re –
- matrix[x3+i].im*W[n*1024+p*3+1].im -
- matrix[x2+i].re*W[n*1024+p*3+0].re +
+ matrix[x2+i].im*W[n*1024+p*3+0].im +
+ matrix[x4+i].re*W[n*1024+p*3+2].re –
- matrix[x4+i].im*W[n*1024+p*3+2].im;
temp3.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*1024+p*3+1].im +
+ matrix[x3+i].im*W[n*1024+p*3+1].re -
- matrix[x2+i].re*W[n*1024+p*3+0].im -
- matrix[x2+i].im*W[n*1024+p*3+0].re +
+ matrix[x4+i].re*W[n*1024+p*3+2].im +
+ matrix[x4+i].im*W[n*1024+p*3+2].re;
temp4.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*1024+p*3+1].re +
+ matrix[x3+i].im*W[n*1024+p*3+1].im -
- matrix[x2+i].re*W[n*1024+p*3+0].im –
- matrix[x2+i].im*W[n*1024+p*3+0].re -
- matrix[x4+i].re*W[n*1024+p*3+2].re +
+ matrix[x4+i].im*W[n*1024+p*3+2].im;
temp4.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*1024+p*3+1].im -
- matrix[x3+i].im*W[n*1024+p*3+1].re +
+ matrix[x2+i].re*W[n*1024+p*3+0].re -
- matrix[x2+i].im*W[n*1024+p*3+0].im -
- matrix[x4+i].re*W[n*1024+p*3+2].re +
+ matrix[x4+i].im*W[n*1024+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 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 4096, 2048, …, 2, 1. На першому ярусі є 4096 групи операцій по 2 відліка кожна, на другому – 2048 груп і збірка ведеться по 4 відлікам і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляє вже безпосередньо групу.
Змінні temp1, temp2 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаючого множника для даної базової операції.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора