Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Ужгородський національний університет
Інститут:
Не вказано
Факультет:
Інженерно технічний
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра копм’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи цифрової обробки сигналів»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 6
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількістьточок
1024
Основа ШПФ
2
Прорідження
частотне
Частота роботи процесора
0,25МГц
Розрядністьвхіднихданих
24(12+12)
Тип вхідного інтерфейсу, пристрою
USB
Тип вихідного інтерфейсу, пристрою
Спец.(20 нс)
Анотація
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2 для 24-розрядних вхідних даних з частотним прорідженням, розроблено:
граф алгоритму ШПФ з основою 2;
біт інверсний порядок видачі даних;
блок-схему перетворення;
обчислено часові ресурси для виконання обчислення;
функціональну схему;
програму виконання алгоритму ШПФ.
Зміст
Вступ 5
1. Теоретична частина 6
1.1. Основні визначення 6
1.2. Властивості повертаючих множників 6
1.3. Основні формули 7
2. Практична частина 9
2.1. Побудова графа алгоритму ШПФ з основою 2 9
2.2. Біт інверсний порядок видачі даних 11
2.3. Блок-схема перетворення 12
3. Розрахунковий розділ 13
4 Розробка функціональної схеми 15
5. Розробка програми 16
Висновки 19
Література 20
Вступ
Перетворення Фур'є - це функція, що описує амплітуду та фазу кожної синусоїда, що відповідає певній частоті. Амплітуда представляє висоту кривої, а фаза - початкову точку синусоїда.
Алгоритм швидкого перетворення Фур'є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур'є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2).
Розробка програм алгоритму ШПФ є одним з етапів розробки процесора ШПФ, ефективність якої суттєво впливає на технічні параметри процесора.
Основними сферами застосування ДПФ є:
- цифровий спектральний аналіз - аналізатори спектра, обробка мови, обробка зображень, розпізнавання образів;
- проектування фільтрів - обчислення імпульсної характеристики за частотною та частотної характеристики за імпульсною.
Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення.
Швидке перетворення Фур'є застосовується в багатьох галузях: радіолокации, стисненні відео та зображень, геології. Багато з цих задач вимагають виконання перетворень в реальному часі, з мінімальною часовою затримкою обчислень.
Для зменшення часу, необхідного для виконання перетворень, можливо розпаралелювання задачі, виконання її на паралельній обчислювальній системі.
1. Теоретична частина
1.1. Основні визначення
Визначення 1. Дано кінцеву послідовність x0, x1, x2,..., xN-1 (у загальному випадку комплексних чисел). ДПФ полягає в пошуку послідовності X0, X1, X2,..., XN-1, елементи якої обчислюються за формулою:
/ (1)
Визначення 2. Зворотне ДПФ полягає в пошуку послідовності x0, x1, x2,..., xN-1, елементи якої обчислюються за формулою:
/ (2)
Основною властивістю перетворень (1) і (2) є те, що з послідовності {x} отримується (при прямому перетворенні) послідовність {X}, а якщо застосувати до {X} зворотне перетворення, то знову отримується вихідна послідовність {x}.
Визначення 3. Величина / називається повертаючим множником.
1.2. Властивості повертаючих множників
При k = 1 /
Пряме перетворення Фур’є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд: / (3)
Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (rejφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент). Модуль відповідає довжині вектора, а аргумент - куту повороту. Модуль повертаючого множника /. дорівнює одиниці, а фаза - 2π/N. Оскільки при множенні комплексних чисел, представлених у показниковій формі, їхні модулі перемножуються, а аргументи підсумовуються, множення вихідного числа на повертаючий множник не змінить довжину вектора, але змінить його кут. Тобто, відбудеться повертання вектора на кут 2π/N.
З формули (3) можна визначити геометричний зміст перетворення Фур’є таким чином: представити N комплексних чисел-векторів з набору {x}, кожне у вигляді суми векторів з набору {X}, повернених на кути, кратні 2π/N.
/
Рис. 1. Геометричне тлумачення повертаючих множників
1.3. Основні формули
Теорема 1. Якщо комплексне число представлене у вигляді e j2πN, де N - ціле, то e j2πN = 1.
Теорема 2. Величина /періодична по k і по n з періодом N. Тобто, для будь-яких цілих l і m виконується рівність:
/ (4)
Теорема 3.
Для величини /справедлива формула: / (5)
З наведених теорем визначається основна ідея алгоритму ШПФ:
Необхідно розділити суму (1) з N доданків на дві суми по N/2 доданків, і обчислити їх окремо. Для обчислення кожної з підсум, треба їх теж розділити на дві і т.д.
Необхідно повторно використовувати вже обчислені доданки.
При обчисленні алгоритму ШПФ застосовують або "проріджування за часом" (в першу суму попадають доданки з парними номерами, а в другу - з непарними), або "проріджування за частотою" (в першу суму попадають перші N/2 доданків, а в другу - інші). Обидва варіанти рівноцінні. В силу специфіки алгоритму доводиться застосовувати тільки N, що є ступенями 2.
Теорема 4. Визначимо ще дві послідовності: {x[even]} і {x[odd]} через послідовність {x} таким чином:
x[even]n = x2n, x[odd]n = x2n+1, (6)
n = 0, 1,..., N/ 2-1
Нехай до цих послідовностей застосовані ДПФ і отримані результати у вигляді двох нових послідовностей {X[even]} і {X[odd]} по N/2 елементів у кожній.
Елементи послідовності {X} можна виразити через елементи послідовностей {X[even]} і {X[odd]} за формулою:
/ (7)
Формула (7) дозволяє скоротити число множень удвічі (не враховуючи множень при обчисленні X[even]k і X [odd]k), якщо обчислювати Xk не послідовно від 0 до N - 1, а попарно: X0 і XN/2, X1 і XN/2+1,..., XN/ 2-1 і XN. Пари утворяться за принципом: Xk і XN/2+k.
Теорема 5. ДПФ можна обчислити і за формулою:
/ (8)
З теореми випливає, що можна не зберігати обчислені значення X[even]k і X[odd]k після обчислення чергової пари, і одне обчислення /можна використовувати для обчислення двох елементів послідовності {X}.
На цьому кроці буде виконане N/2 множень комплексних чисел. Якщо застосувати подібні схеми для обчислення послідовностей {X[even]} і {X[odd]}, то кожна з них вимагатиме N/4 множень, разом ще N/2. Продовжуючи аналогічно далі log2N разів, можна дійти до сум, що містять лише один доданок, так що загальна кількість множень рівна (N/2)log2N.
Висновок:
В основі алгоритму ШПФ лежать такі формули:
/ (9)
Відомі два різновиди алгоритмів ШПФ - проріджування за часом (decimation in time - DIT) і проріджування по частоті (decimation in frequency - D1F), що мають однакову обчислювальну складність.
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.
Метелик ШПФ показаний на рис. 2, де
Рис. 2. Двохточкове ШПФ (Метелик)
X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники.
Граф-алгоритм для 32 точкового ШПФ за основою 2 показаний на рис. 3.
/
Рис. 3. Граф алгоритм 32-точкове ШПФ з основою 2 та прорідженням зачастотою
На рис. 3 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз.
2.2. Біт інверсний порядок видачі даних
Ще однією особливістю алгоритму з прорідженням за частотою є те, що прямий порядок слідування даних на вході графу змінюється двійково-інверсним на виході. Тому для видачі даних в прямому порядку потрібно здійснити двійково-інверсну перестановку за правилом описаним в табл.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 операційдодавання;
6 операційчитання з пам`яті:
- 2*2=4 (для читаннядійсної та уявноїчастинивхіднихвідліків);
- 1*2=2 (для читаннядійсної та уявноїчастиникомплекснихкоефіцієнтів);
4операційзапису:
- 2*2=4 (для записудійсної та уявноїчастинивхіднихвідліків);
В результаті на одну базовуопераціюприпадає 20 операцій: Nна 1 мет=20 (оп).
Тривалістьвиконанняобчислення ШПФ:
Тривалість виходу даних із процессору (USB):
Частота роботи USB: , звідси цикл надходження команди: .
Тнадх=2,5*24=60нс – такт надходження даних;
Вибираємо послідовний спеціалізований інтерфейс, тоді тривалість виходу даних:
Твих=20нс*24розрядів=480нс – такт виходу даних;
Тривалість надходження даних у процесор, тривалість обчислення ШПФ та тривалість виходу даних із процесора:
4 Розробка функціональної схеми
/
Рис. 5. Функціональна схема
Universal Serial Bus (Інтерфейс USB) є послідовною, напівдуплексною, двонаправленою шиною. Специфікація периферійної шини USB була розроблена лідерами комп'ютерної і телекомунікаційної промисловості (Compaq, DEC, IBM, Intel, Microsoft, NEC і Northern Telecom) для підключення комп'ютерної периферії поза корпусом ПК з автоматичною автоконфігурацією (Plug&Play). Перша версія стандарту з’явилася в 1996 р.
Для пристроїв USB 2.0 регламентовано три режими роботи:
Low-speed, 10-1500 Кбіт / c (клавіатури, миші, джойстики),
Full-speed, 0,5-12 Мбіт / с (аудіо-, відеопристрої),
High-speed, 25-480 Мбіт / с (відеопристрої, пристрої зберігання інформації).
Спеціалізована шина може бути як паралельною, так і послідовною, в даному проекті береться як послідовний інтерфейс з часом передачі даних 20 нс, що є задано завданням. Він використовується для передачі даних між центральним процесором і платами оперативної пам'яті. Спеціалізована шина володіє високою швидкістю передачі, що забезпечує майже миттєвий обмін потрібними даними.
5. Розробка програми
Структуру програми, щовиконуєобчислення за алгоритмом ШПФ можнауявитинаступним чином:
/
Рис.6. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент массиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 1 повертаючий множник, тому його розмір: 10*512*1=5120 (10 – кількість ярусів, 512 – кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданийнижче
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. На першому ярусі є 1 група операцій по 512 відлікам, на другому – 2 групи по 256 відліка на кожному і так до останього, де є 512 групи по 2 відліка кожна.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляє вже безпосередньо групу.
Змінні temp1, temp2 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаючого множника для даної базової операції.
Висновки
Під час виконання розрахунково-графічної роботи було розглянуто приклад реалізації обчислювальної системи, в основі якої лежить алгоритм швидкого перетворення Фур’є за основою 2. Дана система обробляє вхідний сигнал, що є 24-розрядним і надходить з тактом, який дорівнює 60 нс. Вхідні дані представляються 1024-ма вхідними відліками, що містять дійсну та уявну частину.
В результаті набуто досвід у проектуванні обчислювальної системи, розглянуто основні компоненти, з яких вона складається, засвоєно алгоритми, на основі яких виконується обчислення.
Література
Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов /Пер. с англ. А.Л.Зайцева, Э.Г.Назаренко, Н.Н.Тетекина; Под ред. Ю.Н.Александрова. - М.:Мир, 1978. - 848 с.
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Куприянов М. С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. – Спб. : Политехника, 1998.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Бабак В.П., Хандецький А.І., Шрюфер Е. Обробка сигналів: підручник для вузів., К., Либідь, 1996.- 390с.
Мельник А.А. Проектирование поточного процессора БПФ на специализированных БИС.- Львов, 1990.- 43с.
Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма.- М. Мир, 1980.- 552с.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Цифровая обработка сигналов/ А.Б.Сергиенко – СПб.:Питер, 2002.-608с.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора