Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Ужгородський національний університет
Інститут:
Не вказано
Факультет:
Інженерно технічний
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра копм’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи ЦОС»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 25
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
16384
Основа ШПФ
4
Прорідження
часове
Частота роботи процесора
1,0 МГц
Розрядність вхідних даних
16(8+8)
Тип вхідного інтерфейсу
USB
Тип вихідного інтерфейсу
ЦАП,8р(20 МГц)
Анотація
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для 16-розрядних вхідних даних з часовим прорідженням;
детально описано механізми обчислення швидкого перетворення Фур’є за основою 4,
обчислено часові ресурси для виконання обчислення,
створена функціональна схема системи
написана програма, що реалізує вказаний алгоритм ШПФ.
Зміст
Вступ 5
1 Теоретичний розділ 6
1.1 Опис швидкого перетворення Фур’є з прорідженням в часі 6
2 Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 9
3 Розрахунковий розділ 11
4 Розробка функціональної схеми 13
5 Розробка програми виконання алгоритму ШПФ 15
Висновки 19
Література 20
Вступ
Швидке перетворення Фур'є (ШПФ, FFT) - це алгоритм швидкого обчислення дискретного перетворення Фур'є (ДПФ). Тобто, алгоритм обчислення за кількість дій, менше ніж O(N2), Необхідних для прямого (за формулою) обчислення ДПФ. Іноді під БПФ розуміється один із швидких алгоритмів, званий алгоритмом проріджування по частоті / часу, що має складність O(Nlog2N).
Одна з причин того, що анализ Фур’є грає важливу роль в цифровій обрабці сигналів, полягає в існуванні ефективних алгоритмів дискретного перетворення Фур’є.
Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення.
Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
1 Теоретична частина
1.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
VI
VII
0
0
0
0
0
0
0
4096
1024
256
64
16
4
1
8192
2048
512
128
32
8
2
12288
3072
768
192
48
12
3
1
1
1
1
1
1
4
4097
1025
257
65
17
5
5
8193
2049
513
129
33
9
6
12289
3073
769
193
49
13
7
2
2
2
2
2
2
8
4098
1026
258
66
18
6
9
8194
2050
514
130
34
10
10
12290
3074
770
194
50
14
11
3
3
3
3
3
3
12
4099
1027
259
67
19
7
13
8195
2051
515
131
35
11
14
12291
3075
771
195
51
15
15
…
…
…
…
…
...
...
4095
13311
15615
16191
16335
16371
16380
8191
14335
15871
16255
16351
16375
16381
12287
15359
16127
16319
16367
16379
16382
16383
16383
16383
16383
16383
16383
16383
Рис.2.1 Блок-схема алгоритму 16384-точкового перетворення за основою 4
Рис.2.2 Граф 16384-точкового ШПФ за основою 4 з прорідженням по часу
3 Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – к-ть точок вх. перетворення;
base=4; N=16384;
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
;
;
Для виконання базової операції «метелик» необхідно:
12 операцій множення;
22 операцій додавання;
14 операцій читання з пам`яті:
- 4*2=8 (для читання дійсної та уявної частини вхідних відліків);
- 3*2=6 (для читання дійсної та уявної частини комплексних коеф.);
8 операцій запису:
- 4*2=8 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 56 операцій: Nна 1 мет=56 (оп)
Тривалість виконання обчислення ШПФ:
Тривалість надходження даних у процесор для обробки (USB):
Тнадх=2,5нс – такт надходження даних;
Частота роботи ЦАП: , звідси цикл надходження команди: .
Тривалість виходу даних із процесору:
Твих=50нс*16розрядів=800нс;
Тривалість надходження даних у процессор, виходу із нього та тривалість обчислення ШПФ:
4 Розробка функціональної схеми
Рис.4.1 Фунціональна схема
Universal Serial Bus (Інтерфейс USB) є послідовною, напівдуплексною, двонаправленою шиною. Специфікація периферійної шини USB була розроблена лідерами комп'ютерної і телекомунікаційної промисловості (Compaq, DEC, IBM, Intel, Microsoft, NEC і Northern Telecom) для підключення комп'ютерної периферії поза корпусом ПК з автоматичною автоконфігурацією (Plug&Play). Перша версія стандарту з’явилася в 1996 р.
Технічні характеристики 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)
Цифро-аналоговий перетворювач (ЦАП) - пристрій для перетворення цифрового коду в аналоговий сигнал. Цифро-аналогові перетворювачі є інтерфейсом між дискретним цифровим світом і аналоговими сигналами.
Характеристики ЦАП.
Розрядність - кількість різних рівнів вихідного сигналу, які ЦАП може відтворити.
Максимальна частота дискретизації - максимальна частота, на якій ЦАП може працювати, видаючи на виході коректний.
Монотонність - властивість ЦАП збільшувати аналоговий вихідний сигнал при збільшенні вхідного коду.
THD + N (сумарні гармонійні спотворення + шум) - міра спотворень і шуму вносяться в сигнал Цапом. Виражається у відсотках потужності гармонік і шуму у вихідному сигналі. Важливий параметр при малосигнальних застосуваннях ЦАП.
Динамічний діапазон - співвідношення найбільшого і найменшого сигналів, які може відтворити ЦАП, виражається в децибелах. Цей параметр пов'язаний з розрядністю і шумовим порогом.
Статичні характеристики:
DNL (диференційна нелінійність) - характеризує, наскільки прирощення аналогового сигналу, отримане при збільшенні коду на 1 молодший значущий розряд (МЗР), відрізняється від правильного значення;
INL (інтегральна нелінійність) - характеризує, наскільки передатна характеристика ЦАП відрізняється від ідеальної. Ідеальна характеристика строго лінійна; INL показує, наскільки напруга на виході ЦАП при заданому коді відстоїть від лінійної характеристики; виражається в МЗР;
посилення;
зсув.
Частотні характеристики:
SNDR (відношення сигнал / шум + спотворення) - характеризує в децибелах відношення потужності вихідного сигналу до сумарної потужності шуму і гармонійних спотворень;
HDi (коефіцієнт i-ої гармоніки) - характеризує відношення i-ї гармоніки до основної гармоніці;
THD (коефіцієнт гармонійних спотворень) - відношення сумарної потужності всіх гармонік (крім першої) до потужності першої гармоніки.
5 Розробка програми виконання алгоритму ШПФ
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис.5.1. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент масиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір:
7*4096*3=86016 (7 – кількість ярусів, 4096 – кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
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*4096+p*3+1].re –
- matrix[x3+i].im*W[n*4096+p*3+1].im +
+ matrix[x2+i].re*W[n*4096+p*3+0].re –
- matrix[x2+i].im*W[n*4096+p*3+0].im +
+ matrix[x4+i].re*W[n*4096+p*3+2].re –
- matrix[x4+i].im*W[n*4096+p*3+2].im;
temp1.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*4096+p*3+1].im +
+ matrix[x3+i].im*W[n*4096+p*3+1].re +
+ matrix[x2+i].re*W[n*4096+p*3+0].im +
+ matrix[x2+i].im*W[n*4096+p*3+0].re +
+ matrix[x4+i].re*W[n*4096+p*3+2].im +
+ matrix[x4+i].im*W[n*4096+p*3+2].re;
temp2.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*4096+p*3+1].re +
+ matrix[x3+i].im*W[n*4096+p*3+1].im +
+ matrix[x2+i].re*W[n*4096+p*3+0].im +
+ matrix[x2+i].im*W[n*4096+p*3+0].re -
- matrix[x4+i].re*W[n*4096+p*3+2].im –
- matrix[x4+i].im*W[n*4096+p*3+2].re;
temp2.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*4096+p*3+1].im -
- matrix[x3+i].im*W[n*4096+p*3+1].re -
- matrix[x2+i].re*W[n*4096+p*3+0].re +
+ matrix[x2+i].im*W[n*4096+p*3+0].im -
- matrix[x4+i].re*W[n*4096+p*3+2].re +
+ matrix[x4+i].im*W[n*4096+p*3+2].im;
temp3.re=
matrix[x1+i].re + matrix[x3+i].re*W[n*4096+p*3+1].re –
- matrix[x3+i].im*W[n*4096+p*3+1].im -
- matrix[x2+i].re*W[n*4096+p*3+0].re +
+ matrix[x2+i].im*W[n*4096+p*3+0].im +
+ matrix[x4+i].re*W[n*4096+p*3+2].re –
- matrix[x4+i].im*W[n*4096+p*3+2].im;
temp3.im=
matrix[x1+i].im + matrix[x3+i].re*W[n*4096+p*3+1].im +
+ matrix[x3+i].im*W[n*4096+p*3+1].re -
- matrix[x2+i].re*W[n*4096+p*3+0].im -
- matrix[x2+i].im*W[n*4096+p*3+0].re +
+ matrix[x4+i].re*W[n*4096+p*3+2].im +
+ matrix[x4+i].im*W[n*4096+p*3+2].re;
temp4.re=
matrix[x1+i].re - matrix[x3+i].re*W[n*4096+p*3+1].re +
+ matrix[x3+i].im*W[n*4096+p*3+1].im -
- matrix[x2+i].re*W[n*4096+p*3+0].im –
- matrix[x2+i].im*W[n*4096+p*3+0].re -
- matrix[x4+i].re*W[n*4096+p*3+2].re +
+ matrix[x4+i].im*W[n*4096+p*3+2].im;
temp4.im=
matrix[x1+i].im - matrix[x3+i].re*W[n*4096+p*3+1].im -
- matrix[x3+i].im*W[n*4096+p*3+1].re +
+ matrix[x2+i].re*W[n*4096+p*3+0].re -
- matrix[x2+i].im*W[n*4096+p*3+0].im -
- matrix[x4+i].re*W[n*4096+p*3+2].re +
+ matrix[x4+i].im*W[n*4096+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, 1024, 256, 64, 16, 4, 1. На першому ярусі є 4096 груп операцій по 4 відліка кожна, на другому – 1024 груп і збірка ведеться по 256 відліків і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2, х3, х4. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляю вже безпосередньо групу.
Змінні temp1, temp2, temp3, temp4 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаю чого множника для даної базової операції.
Висновки
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму швидкого перетворення Фур’є за основою 4. Дана система обробляє вхідний сигнал, що є 16-розрядним і надходить з тактом, який дорівнює 2,5 нс. Вхідні дані представляються 16384-ма вхідними відліками, що містять дійсну та уявну частину.
В результаті набуто досвід у проектуванні обчислювальної системи, розглянуто основні компоненти, з яких вона складається, засвоєно алгоритми, на основі яких виконується обчислення.
Література
Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов /Пер. с англ. А.Л.Зайцева, Э.Г.Назаренко, Н.Н.Тетекина; Под ред. Ю.Н.Александрова. - М.:Мир, 1978. - 848 с.
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Куприянов М. С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. – Спб. : Политехника, 1998.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Цифровой процессор обработки сигналов TMS32010 и его применение/Под ред. А.А.Ланнэ.-Л.:ВАС,1990.-296 с.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора