Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Ужгородський національний університет
Інститут:
Не вказано
Факультет:
Інженерно технічний
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра копм’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи цифрової обробки сигналів»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 11
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
1024
Основа ШПФ
4
Прорідження
часове
Частота роботи процесора
1,8 МГц
Розрядність вхідних даних
20
Тип вхідного інтерфейсу
CAN
Тип вихідного інтерфейсу
USB
Анотація
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для 20-розрядних вхідних даних з часовим прорідженням:
детально описано механізми обчислення швидкого перетворення Фур’є за заданною основою,
обчислено часові ресурси для виконання обчислення,
створена функціональна схема системи,
написана програма, що реалізує вказаний алгоритм ШПФ.
Зміст
Варіант № 11 2
Вступ 5
1 Опис швидкого перетворення Фур’є з прорідженням в часі 6
2 Розробка блок-схеми та метелика заданої функції, порядок слідування відліків 9
3 Розрахунковий розділ 12
4 Розробка функціональної схеми 14
5 Розробка програми виконання алгоритму ШПФ 16
Висновки 20
Література 21
Вступ
Алгоритм швидкого перетворення Фур'є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур'є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2).
Розробка процесора ШПФ на ПЛІС забезпечує однокристальну реалізацію процесора з високою продуктивністю і можливістю реконфігурації структури
При цифровій обробці сигналів різної природи перетворення Фур’є звичайно розглядається як трансформація сигналу з часової ділянки в частотну, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур’є дозволяє визначити відповідний сигнал у часовій області. Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою.
1 Опис швидкого перетворення Фур’є з прорідженням в часі
Дискретний матеріальний сигнал у вигляді кінцевої часової послідовності x(nТ) запишемо як x(nТ), де - число відліків, N – число відліків, T – період дискретизації.
N - точкове дискретне перетворення Фур’є (ДПФ) задається формулою:
де X(k) – частотний k-ий відлік чи k-а спектральна складова сигналу (визначає вихідну частотну послідовність, спектр сигналу),
комплексна експонента, W- ядро перетворення.
При зміні значення n*k на величину кратну N ядро не змінюється (у силу періодичності синуса і косинуса). Тобто ядро по верхньому індексу є періодичною функцією з періодом N. Тому замість добутку n*k можна вставити залишок від ділення його на N , тобто (n*k) mod N. Cпектральна функція X(k) також має період N по аргументу k.
Число множень дійсних відліків сигналу на комплексне ядро в (1) дорівнює N2, а число додавань комплексних чисел – (N -1)N. Кількість цих операцій різко зростає із збільшенням N і приводить до занадто великого часу перетворення.
ДПФ стало широко застосовуватися після винаходу швидких алгоритмів, в основі яких лежить принцип зведення багатоточкового перетворення до малоточкового. Один з них (що став уже класичним) називається ШПФ із проріджу-ванням за часом. Цей алгоритм отриманий за умови, якщо N є ступенем числа 2, тобто , де ν - ціле число, ν≥0.
Основні формули перетворення, до яких ми прийдемо, виходять при розбивці суми в (1) на дві суми, що містять відліки з парними і непарними номерами
Власне кажучи ця операція являє собою зміну порядку сумування (перегрупу-вання доданків), від якого сума не міняється.
Можна записати , . З врахуванням цього (2) прийме вигляд:
Зауважимо, що суми в (3) являють собою N/2 - точкові ДПФ часових відліків з парними номерами в першій сумі, і непарними номерами в другій сумі.
Позначимо, згідно з [1],
X(k) = Xν(k) - ДПФ усіх вхідних відліків дискретного сигналу,
вхідних відліків з парними номерами (перше число в нижньому індексі дорівнює ν - 1, а друге - парному числу (нулю)) ,
вхідних відліків з непарними номерами (друге число в нижньому індексі дорівнює непарному числу (одиниці)).
З урахуванням введених позначень одержимо коротку форму запису (3)
Спектри і є періодичними функціями з періодом N/2 (у ядрі перетворення замість N стоїть N/2). Величина називається повертаючим множником і володіє наступною цікавою властивістю
Ця властивість надає при обчисленні з номерами k від N/2 до (N -1) використовувати відповідні значення раніше обчислених з номерами від 0 до (N/2 -1) (потрібно тільки змінити знак).
За звичай формулу (4) розбивають на два співвідношення для зазначених вище номерів і одержують основні формули (базові співвідношення) перетворення Фур’є у вигляді
Базові співвідношення вже можна назвати швидким перетворенням Фур’є (ШПФ), тому що число операцій зменшилося. Число множень матеріальних відліків сигналу на комплексне ядро дорівнює . До цього потрібно додати множень комплексних чисел. Число додавань дорівнює
Процес розбиття за схемою базових співвідношень можна продовжувати до тих пір, доки не прийдемо до перетворень Фур’є одиничних відліків (що збігаються із самими відліками). Необхідне число операцій при цьому буде значно менше. У такому вигляді це ШПФ називають ШПФ із проріджуванням за часом.
2 Розробка блок-схеми та метелика заданої функції, порядок слідування відліків
Табл.2.1. Порядок слідування відліків для кожного ярусу
I
II
III
IV
V
0
0
0
0
0
256
64
16
4
1
512
128
32
8
2
768
192
48
12
3
1
1
1
1
4
257
65
17
5
5
513
129
33
9
6
769
193
49
13
7
2
2
2
2
8
258
66
18
6
9
514
130
34
10
10
770
194
50
14
11
3
3
3
3
12
259
67
19
7
13
515
131
35
11
14
771
195
51
15
15
…
…
…
…
…
255
831
975
1011
1020
511
895
991
1015
1021
767
959
1007
1019
1022
1023
1023
1023
1023
1023
Рис.2.1 Блок-схема алгоритму 1024-точкового перетворення за основою 4
Для побудови графу N-точкового ШПФ з основою 4 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином:
Nяр = Log4N, для N=1024, Log41024 = 5;
Nм = N/2 = 1024/4= 256.
Граф-алгоритм для 64 точкового ШПФ за основою 4 показаний на рис.2.2.
Рис.2.2. Граф 64-точкового ШПФ за основою 4 з прорідженням по часу
3 Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – к-ть точок вх. перетворення;
base=4;
N=1024;
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
;
;
Для виконання базової операції «метелик» необхідно:
12 операцій множення;
22 операцій додавання;
14 операцій читання з пам`яті:
- 4*2=8 (для читання дійсної та уявної частини вхідних відліків);
- 3*2=6 (для читання дійсної та уявної частини комплексних коеф.);
8 операцій запису:
- 4*2=8 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 56 операцій: Nна 1 мет=56 (оп)
Тривалість виконання обчислення ШПФ:
Швидкість передачі даних CAN шини 1Mbit/c, звідси цикл надходження команди: .
Тривалість надходження даних у процесор:
Тнадх=1мкс – такт виходу даних;
Загальна частота роботи USB , звідси цикл надходження команди: . І оскільки шина USB є послідовним, то необхідно ще помножити на 20.
Тривалість виходу даних:
Твих=2,5*20 = 50 нс– такт надходження даних;
Тривалість надходження даних у процессор, виходу із нього та тривалість обчислення ШПФ:
4 Розробка функціональної схеми
Рис.4.1 Фунціональна схема
CAN (англ. Controller Area Network - мережа контролерів) - стандарт промислової мережі, орієнтований передусім на об'єднання в єдину мережу різних виконавчих пристроїв і датчиків. Режим передачі - послідовний, широкомовний, пакетний.
CAN розроблений компанією Robert Bosch GmbH в середині 1980-х і в даний час широко поширений в промисловій автоматизації, технологіях «розумного будинку», автомобільної промисловості і багатьох інших областях. Стандарт для автомобільної автоматики.
Безпосередньо стандарт CAN від Bosch визначає передачу у відриві від фізичного рівня - він може бути яким завгодно, наприклад, радіоканалом або оптоволокном. Але на практиці під CAN-мережею зазвичай мається на увазі мережу топології «шина» з фізичним рівнем у вигляді диференціальної пари, визначеним в стандарті ISO 11898. Передача ведеться кадрами, які приймаються усіма вузлами мережі. Для доступу до шини, випускаються спеціалізовані мікросхеми - драйвери CAN шини.
Шина USB (Universal Serial Bus - універсальна послідовна шина) з'явилася по комп'ютерних мірках досить давно - версія першого затвердженого варіанту стандарту з'явилася 15 січня 1996 року. Розробка стандарту була ініцііровна вельми авторитетними фірмами - Intel, DEC, IBM, NEC, Northen Telecom і Compaq.
Основна мета стандарту, поставлене перед його розробниками - створити реальну можливість користувачам працювати в режимі Plug & Play з периферійними пристроями. Це означає, що має бути передбачено підключення пристрою до працюючого комп'ютера, автоматичне розпізнавання його негайно після підключення і подальшої установки відповідних драйверів. Крім цього, бажано харчування малопотужних пристроїв подавати з самої шини. Швидкість шини повинна бути достатньою для переважної більшості периферійних пристроїв. Попутно вирішується історична проблема нестачі ресурсів на внутрішніх шинах IBM PC сумісного комп'ютера - контролер USB займає тільки одне переривання незалежно від кількості підключених до шини пристроїв.
Технічні характеристики
Можливості USB випливають з її технічних характеристик:
Висока швидкість обміну (full-speed signaling bit rate) - 12 Mb / s
Максимальна довжина кабелю для високої швидкості обміну - 5 m
Низька швидкість обміну (low-speed signaling bit rate) - 1.5 Mb / s
Максимальна довжина кабелю для низької швидкості обміну - 3 m
Максимальна кількість підключених пристроїв (включаючи множителі) - 127
Можливе підключення пристроїв з різними швидкостями обміну
Відсутність необхідності в установці користувачем додаткових елементів, таких як термінатори для SCSI
Напруга живлення для периферійних пристроїв - 5 V
Максимальний струм споживання на один пристрій - 500 mA (це не означає, що через USB можна живити пристрої із загальним струмом споживання 127 x 500 mA = 63.5 A)
5 Розробка програми виконання алгоритму ШПФ
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис.5.1. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент масиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 5*256*3=3840 (5 – кількість ярусів, 256 – кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
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*256+p*3+1].re –
- matrix[x3+i].im*W[n*256+p*3+1].im +
+ matrix[x2+i].re*W[n*256+p*3+0].re –
- matrix[x2+i].im*W[n*256+p*3+0].im +
+ matrix[x4+i].re*W[n*256+p*3+2].re –
- matrix[x4+i].im*W[n*256+p*3+2].im;
temp1.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*256+p*3+1].im +
+ matrix[x3+i].im*W[n*256+p*3+1].re +
+ matrix[x2+i].re*W[n*256+p*3+0].im +
+ matrix[x2+i].im*W[n*256+p*3+0].re +
+ matrix[x4+i].re*W[n*256+p*3+2].im +
+ matrix[x4+i].im*W[n*256+p*3+2].re;
temp2.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*256+p*3+1].re +
+ matrix[x3+i].im*W[n*256+p*3+1].im +
+ matrix[x2+i].re*W[n*256+p*3+0].im +
+ matrix[x2+i].im*W[n*256+p*3+0].re -
- matrix[x4+i].re*W[n*256+p*3+2].im –
- matrix[x4+i].im*W[n*256+p*3+2].re;
temp2.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*256+p*3+1].im -
- matrix[x3+i].im*W[n*256+p*3+1].re -
- matrix[x2+i].re*W[n*256+p*3+0].re +
+ matrix[x2+i].im*W[n*256+p*3+0].im -
- matrix[x4+i].re*W[n*256+p*3+2].re +
+ matrix[x4+i].im*W[n*256+p*3+2].im;
temp3.re=
matrix[x1+i].re + matrix[x3+i].re*W[n*256+p*3+1].re –
- matrix[x3+i].im*W[n*256+p*3+1].im -
- matrix[x2+i].re*W[n*256+p*3+0].re +
+ matrix[x2+i].im*W[n*256+p*3+0].im +
+ matrix[x4+i].re*W[n*256+p*3+2].re –
- matrix[x4+i].im*W[n*256+p*3+2].im;
temp3.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*256+p*3+1].im +
+ matrix[x3+i].im*W[n*256+p*3+1].re -
- matrix[x2+i].re*W[n*256+p*3+0].im -
- matrix[x2+i].im*W[n*256+p*3+0].re +
+ matrix[x4+i].re*W[n*256+p*3+2].im +
+ matrix[x4+i].im*W[n*256+p*3+2].re;
temp4.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*256+p*3+1].re +
+ matrix[x3+i].im*W[n*256+p*3+1].im -
- matrix[x2+i].re*W[n*256+p*3+0].im –
- matrix[x2+i].im*W[n*256+p*3+0].re -
- matrix[x4+i].re*W[n*256+p*3+2].re +
+ matrix[x4+i].im*W[n*256+p*3+2].im;
temp4.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*256+p*3+1].im -
- matrix[x3+i].im*W[n*256+p*3+1].re +
+ matrix[x2+i].re*W[n*256+p*3+0].re -
- matrix[x2+i].im*W[n*256+p*3+0].im -
- matrix[x4+i].re*W[n*256+p*3+2].re +
+ matrix[x4+i].im*W[n*256+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 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 256, 64, 16, 4, 1. На першому ярусі є 256 групи операцій по 4 відліка кожна, на другому – 64 груп і збірка ведеться по 16 відліків і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2, х3, х4. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляю вже безпосередньо групу.
Змінні temp1, temp2, temp3, temp4 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаю чого множника для даної базової операції.
Висновки
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму швидкого перетворення Фур’є за основою 4. Дана система обробляє вхідний сигнал, що є 20-розрядним і надходить з тактом, який дорівнює 1 мкс. Вхідні дані представляються 1024-ма вхідними відліками, що містять дійсну та уявну частину.
В результаті набуто досвід у проектуванні обчислювальної системи, розглянуто основні компоненти, з яких вона складається, засвоєно алгоритми, на основі яких виконується обчислення.
Література
Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов /Пер. с англ. А.Л.Зайцева, Э.Г.Назаренко, Н.Н.Тетекина; Под ред. Ю.Н.Александрова. - М.:Мир, 1978. - 848 с.
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Куприянов М. С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. – Спб. : Политехника, 1998.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Цифровой процессор обработки сигналов TMS32010 и его применение/Под ред. А.А.Ланнэ.-Л.:ВАС,1990.-296 с.
Агуров П. В. Интерфейс USB. Практика использования и программирования. – СПб: БХВ-Петербург,2004. – 576 с.
Хульцебош Ю. USB в электронике. – BHV-СПб, 2011. – 224 с.
Гук М. Шины PCI, USB и FireWire. – ЗАО Издательский дом "Питер", 2005.– 544с.
CAN Specification”, ROBERT BOSCH GmbH, Postfach 300240, D-7000 Stuttgart 30
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора