Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Ужгородський національний університет
Інститут:
Не вказано
Факультет:
Інженерно технічний
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахункова робота
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра копм’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи цифрової обробки сигналів»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 2
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
2048
Основа ШПФ
2
Прорідження
частотне
Частота роботи процесора
26,0 МГц
Розрядність вхідних даних
16(8+8)
Тип вхідного інтерфейсу
CAN
Тип вихідного інтерфейсу
HOST
Анотація
В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2 для 16-розрядних вхідних даних з частотним прорідженням, розроблено:
граф алгоритму ШПФ з основою 2;
біт інверсний порядок видачі даних;
блок-схему перетворення;
обчислено часові ресурси для виконання обчислення;
функціональну схему;
програму виконання алгоритму ШПФ.
Зміст
Вступ 4
1 ТЕОРЕТИЧНІ ВІДОМОСТІ 6
1.1 Застосування дискретного перетворення Фур’є 6
1.2 Швидке перетворення Фур'є 6
1.3. Властивості повертаючих множників 7
1.4. Основні формули 8
2 ПРАКТИЧНА ЧАСТИНА 10
2.1. Побудова графа алгоритму ШПФ з основою 2 10
2.2. Біт інверсний порядок видачі даних 11
2.3. Блок-схема перетворення 13
3 Розрахунковий розділ 14
4 Розробка функціональної схеми 16
5 Розробка програми виконання алгоритму ШПФ 17
Висновки 20
Література 21
Вступ
Набір алгоритмів, званих алгоритмами швидкого перетворення Фур’є (ШПФ), включає різноманітні методи зменшення часу обчислення дискретного перетворення Фур’є (ДПФ). Оскільки обчислення ДПФ є основною операцією в більшості задач спектрального аналізу, то використовування ШПФ в деяких практичних випадках, дозволяє прискорити обчислення ДПФ в 100 і більше разів у порівнянні з методом прямого обчислення ДПФ.
Той факт, що одновимірний масив чисел можна виразити через двовимірний масив більш ніж одним способом, пояснює різноманіття алгоритмів ШПФ. Звідси витікає, що математична операція переходу з одновимірного простору в двовимірний є основою всіх алгоритмів ШПФ. При такому єдиному підході до алгоритму ШПФ його різні варіанти можуть бути отриманий порівняно простим способом.
Дискретне перетворення Фур’є грає важливу роль при аналізі, синтезі та розробці систем та алгоритмів цифрової обробки сигналів. Одна з причин того, що анализ Фур’є грає таку важливу роль в цифровій обрабці сигналів, полягає в існуванні ефективних алгоритмів дискретного перетворення Фур’є.
Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення.
1 Теоретичні відомості
1.1 Застосування дискретного перетворення Фур’є
Цифровий спектральний аналіз
Аналізатори спектра
Обробка мови
Обробка зображень
Розпізнавання образів
Проектування фільтрів
Обчислення імпульсної характеристики по частотній
Обчислення частотної характеристики по імпульсній
Швидке перетворення Фур'є (БПФ) - це простий алгоритм для ефективного обчислення дискретного перетворення Фур'є (ДПФ)
Аналіз Фур'є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур'є дозволяє зіставити сигналу, заданому в тимчасовій області, його еквівалентне представлення в частотній області. І навпаки, якщо відома частотна характеристика сигналу, то зворотнє перетворення Фур'є дозволяє визначити відповідний сигнал у тимчасовій області. На додаток до частотного аналізу, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур'є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур'є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою ідентичні дискретній імпульсній реакції фільтра.
1.2 Швидке перетворення Фур'є
Вихідними даними для ШПФ є елементи обмеженої послідовності x(n), де n=0,1,.. N-1. Відповідно дискретне перетворення Фур'є має вид:
(1)
(2)
де - повертаючий множник , причому є періодичною послідовністю з періодом N, оскільки , де m - ціле. Безпосереднє обчислення ДПФ (1) для визначення комплексних значень F(k) вимагає для кожного значення k (N-1) множень і (N-1) додавань комплексних чисел чи 4(N-1) множень і 2(N-1) додавань дійсних чисел, а для всіх N значень k=0, 1, ..., N-1 потрібно приблизно N2 множень і N2 додавань комплексних чисел. Таким чином, для великих значень N (порядку декількох сотень) пряме обчислення ДПФ вимагає дуже великого числа арифметичних операцій множення і додавання, що утрудняє реалізацію обчислень у реальному часі.
Швидким перетворенням Фур'є (ШПФ) називають набір алгоритмів, реалізація яких приводить до істотного зменшення обчислювальної складності ДПФ (1).
1.3. Властивості повертаючих множників
При k = 1 /
Пряме перетворення Фур’є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд: / (3)
Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (rejφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент). Модуль відповідає довжині вектора, а аргумент - куту повороту. Модуль повертаючого множника /. дорівнює одиниці, а фаза - 2π/N. Оскільки при множенні комплексних чисел, представлених у показниковій формі, їхні модулі перемножуються, а аргументи підсумовуються, множення вихідного числа на повертаючий множник не змінить довжину вектора, але змінить його кут. Тобто, відбудеться повертання вектора на кут 2π/N.
З формули (3) можна визначити геометричний зміст перетворення Фур’є таким чином: представити N комплексних чисел-векторів з набору {x}, кожне у вигляді суми векторів з набору {X}, повернених на кути, кратні 2π/N.
/
Рис. 1. Геометричне тлумачення повертаючих множників
1.4. Основні формули
Теорема 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=2048, Log22048 = 11;
Nм = N/2 = 2048/2= 1024.
Метелик ШПФ показаний на рис. 2, де
Рис. 2. Двохточкове ШПФ (Метелик)
X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники.
Граф-алгоритм для 32-точкового ШПФ за основою 2 з частотним прорідженням показаний на рис. 3.
/
Рис.3. Граф 32-точкового ШПФ за основою 2 з прорідженням за частотою
На рис. 3 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники. Елементи пам’яті зображено точками та пронумеровано зверху вниз.
2.2. Біт інверсний порядок видачі даних
Для реалізації ШПФ з прорідженням по частоті 2048-точкове ШПФ розділяють на два 1024-точкові ШПФ, далі на чотири 512-точкових ШПФ, і так далі аж до 2- точкових ШПФ. Для обрахунку 2-точкового ШПФ використовуються формули „метелика”.
Отже, в результаті для виконання 2048-точкового ШПФ необхідно 1024 ітерації. При чому, після того, як закінчується обчислення першої ітерації, немає необхідності зберігати які-небудь попередні результати. Результати обчислення першої ітерації можуть бути збережені в тих же регістрах чи комірках пам'яті, що спочатку зберігалися вхідні дані. Так само, коли закінчується обчислення другого каскаду, результати обчислення першого каскаду можуть бути вилучені. У такий же спосіб здійснюється обчислення останнього каскаду, заміняючи в пам'яті проміжний результат обчислення попереднього каскаду.
Слід зауважити, що результат виконання ШПФ отримуємо у біт-інверсному порядку. Тому для адресів вихідних відліків необхідно застосувати біт-інверсний алгоритм. Суть даного алгоритму полягає у наступному: десятковий індекс n перетворюють в його двійковий еквівалент. Потім двійкові розряди розташовуються у зворотньому порядку і перетворюються назад у десяткове число. Приклад наведений у табл. 1.
Таблиця 1. Біт-інверсне прорідження
Номер
Двійкове представлення
Двійкова інверсія
Двійково-інверсний номер
0
00000000000
00000000000
0
1
00000000001
10000000000
1024
2
00000000010
01000000000
512
3
00000000011
11000000000
1536
4
00000000100
00100000000
256
5
00000000101
10100000000
1280
6
00000000110
01100000000
384
7
00000000111
11100000000
1792
8
00000001000
00010000000
128
9
00000001001
10010000000
1152
10
00000001010
01010000000
640
11
00000001011
11010000000
1664
…
…
…
…
2045
11111111101
10111111111
1535
2046
11111111110
01111111111
1023
2047
11111111111
11111111111
2047
2.3. Блок-схема перетворення
/
Рис. 4. Блок-схема алгоритму 2048-точкового перетворення за основою 2
3 Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – к-ть точок вх. перетворення;
base=2; N=2048;
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
;
;
Для виконання базової операції «метелик» необхідно:
4 операцій множення;
6 операцій додавання;
6 операцій читання з пам`яті:
- 2*2=4 (для читання дійсної та уявної частини вхідних відліків);
- 1*2=2 (для читання дійсної та уявної частини комплексних коефіцієнтів);
4 операцій запису:
- 2*2=4 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 20 операцій: Nна 1 мет=20 (оп).
Тривалість виконання обчислення ШПФ:
Швидкість передачі даних CAN шини 1Mbit/c, звідси цикл надходження команди: .
Тривалість надходження даних у процесор:
Твих=1мкс – такт виходу даних;
Частота роботи (HOST в процесорі ADSP-2111): , звідси цикл надходження команди: .
Тривалість надходження даних в процесор:
Тривалість надходження даних у процессор, виходу із нього та тривалість обчислення ШПФ:
4 Розробка функціональної схеми
/
Рис.5. Фунціональна схема
Controller Area Network, (CAN) (локальна мережа контролерів, він же CAN-Bus і Інтерфейс CAN) – стандарт, призначений для організації високонадійних та недорогих каналів зв’язку у розподілених системах керування. Найчастіше CAN-інтерфейс використовується як зв’язна ланка між головною магістраллю та багатьма допоміжними датчиками, механізмами і т.д., підключення яких до центральної магістралі не завжди доцільне.
Безпосередньо стандарт CAN від Bosch визначає передачу у відриві від фізичного рівня - він може бути яким завгодно, наприклад, радіоканалом або оптоволокном. Але на практиці під CAN-мережею зазвичай мається на увазі мережу топології «шина» з фізичним рівнем у вигляді диференціальної пари, визначеним в стандарті ISO 11898. Передача ведеться кадрами, які приймаються усіма вузлами мережі. Для доступу до шини, випускаються спеціалізовані мікросхеми - драйвери CAN шини.
Host Interface порт (ADSP-2111).
ADSP-2111 включає в себе Host Interface Port (HIP), паралельний порт вводу / виводу, що дозволяє легко підключення до хост-процесора. Через HIP, ADSP-2111 можуть бути доступні приймаючої процесор, пам'ять відображається периферійних пристроїв. Хост-інтерфейс порт можна розглядати як область двухпортовой пам'яті, або повідомлення регістрів, що дозволяє зв'язок між обчислювального ядра ADSP-2111 і комп'ютером. Порт інтерфейсу хост-машини повністю асинхронно. Хост процесор може записати дані в HIP у той час як ADSP-2111 є працює на повній швидкості.
5 Розробка програми виконання алгоритму ШПФ
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис. 6. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент масиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 1 повертаючий множник:
11*2048*1=22530 (11 – кількість ярусів, 2048 – кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
N=2048;
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*2048+p*1+0].re –
- matrix[x2+i].im*W[n*2048+p*1+0].im;
temp1.im=
matrix[x1+i].im
+ matrix[x2+i].re*W[n*2048+p*1+0].im +
+ matrix[x2+i].im*W[n*2048+p*1+0].re;
temp2.re=
matrix[x1+i].re
+ matrix[x2+i].re*W[n*2048+p*1+0].im +
+ matrix[x2+i].im*W[n*2048+p*1+0].re;
temp2.im=
matrix[x1+i].im
- matrix[x2+i].re*W[n*2048+p*1+0].re +
+ matrix[x2+i].im*W[n*2048+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 означає кількість груп, по яких проводиться збірка на конкретному ярусі і приймає значення: 2048, 1024, …, 2, 1. На першому ярусі є 1 група операцій по 2048 відліка, на другому – 2 груп по 1024 відліка на кожному і так до останього, де є 1024 групи по 2 відліка.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляє вже безпосередньо групу.
Змінні temp1, temp2 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаючого множника для даної базової операції.
Висновки
В розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2. Дана система обробляє вхідний сигнал, що є 16-розрядним і надходить з тактом, який дорівнює 1мкс. Вхідні дані представляються 2048-ма вхідними відліками, що містять дійсну та уявну частину.
В результаті набуто досвід у проектуванні обчислювальної системи, створена функціональна схема системи за допомогою вхідного інтерфейсу типу CAN та вихідного інтерфейсу типу HOST, які є послідовними. А також була написана програма, що реалізує вказаний алгоритм ШПФ.
Література
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Цифровой процессор обработки сигналов TMS32010 и его применение/Под ред. А.А.Ланнэ.-Л.:ВАС,1990.-296 с.
Бабак В.П., Хандецький А.І., Шрюфер Е. Обробка сигналів: підручник для вузів., К., Либідь, 1996.- 390с.
Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма.- М. Мир, 1980.- 552с.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Цифровая обработка сигналов/ А.Б.Сергиенко – СПб.:Питер, 2002.-608с.
24.03.2013 21:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора