Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розрахунок параметрів виконання алгоритму ШПФ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Розрахунково - графічна робота
Предмет:
Методи, алгоритми та засоби цифрової обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД
«УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра комп’ютерних систем та мереж
Розрахунково-графічна робота
з дисципліни
«Теоретичні основи ЦОС»
на тему:
«Розрахунок параметрів виконання алгоритму ШПФ»
Завдання
Варіант № 18
Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними:
Кількість точок
4096
Основа ШПФ
2
Прорідження
Частотне
Частота роботи процесора
2,0 МГц
Розрядність вхідних даних
32 (16+16), біт (Re +Im)
Тип вхідного інтерфейсу, пристрою
Link-port
Тип вихідного інтерфейсу, пристрою
SPORT
2
Анотація
В розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2 для 32-розрядних вхідних даних з частотним прорідженням, детально описано механізми обчислення швидкого перетворення Фур`є за заданною основою, обчислено часові ресурси для виконання обчислення, створена функціональна схема системи та написана програма, що реалізує вказаний алгоритм ШПФ.
Зміст
Вступ 5
1. Теоретичний розділ 6
1.1. Опис ШПФ 6
1.1.1. Основні визначення 6
1.1.2. Властивості повертаючих множників 6
1.1.3. Основні формули 7
2. Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 9
2.1. Побудова графа алгоритму ШПФ з основою 2 9
2.1.1. Обчислення повертаючих множників WN 10
2.2. Біт інверсний порядок видачі даних 10
2.2.1. Блок-схема перетворення 11
3. Розрахунковий розділ 12
4. Розробка функціональної схеми 14
5. Розробка програми виконання алгоритму ШПФ 15
Висновки 19
Література 20
Вступ
Алгоритм швидкого перетворення Фур’є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур’є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2).
Аналіз Фур’є закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фур’є (фактично існує кілька варіантів таких перетворень) дозволяє співставити сигналу, заданому в часовій області, його еквівалентне представлення в частотній області, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур’є дозволяє визначити відповідний сигнал у часовій області.
Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
1. Теоретичний розділ
1.1. Опис ШПФ
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.1.2. Властивості повертаючих множників
При k = 1
Пряме перетворення Фур’є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд: (3)
Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (rejφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент). Модуль відповідає довжині вектора, а аргумент - куту повороту. Модуль повертаючого множника . дорівнює одиниці, а фаза - 2π/N. Оскільки при множенні комплексних чисел, представлених у показниковій формі, їхні модулі перемножуються, а аргументи підсумовуються, множення вихідного числа на повертаючий множник не змінить довжину вектора, але змінить його кут. Тобто, відбудеться повертання вектора на кут 2π/N.
З формули (3) можна визначити геометричний зміст перетворення Фур’є таким чином: представити N комплексних чисел-векторів з набору {x}, кожне у вигляді суми векторів з набору {X}, повернених на кути, кратні 2π/N.
Рис. 1. Геометричне тлумачення повертаючих множників
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 = (N/4) * 2 і т.д. В результаті елементи початкового одновимірного масиву можна розподілити таким чином, щоб елементарними операціями були двохточкові ШПФ. Для побудови графу N-точкового ШПФ з основою 2 потрібно визначити кількість ярусів (Nяр) графу та кількості метеликів (Nм) на кожному ярусі таким чином:
Nяр = Log2N, для N=4096, Log24096 = 12;
Nм = N/2 = 4096/2= 2048.
Граф-алгоритм для 4096 точкового ШПФ за основою 2 показаний на рис. 2.
Рис. 2. Граф алгоритм 4096-точкове ШПФ з основою 2 з частотним прорідженням
На рис. 2 кільцям відповідають двохточкові ШПФ, стрілками зображено процедуру множення на повертаючі множники.
Метелик ШПФ показаний на рис. 3, де
Рис. 3. Двохточкове ШПФ (Метелик)
X, Y - результати базової операції; А, B - вхідні відліки; WN – повертаючих множники.
2.1.1. Обчислення повертаючих множників WN
Для виконання кожної базової операції на вхід метелика необхідно подати повертаючий множник (коефіцієнт) Wp, де W=e-2jπ/N при прямому ШПФ і W=e2jπ/N при зворотному ШПФ. Для алгоритму ШПФ з прорідженням за часом значення р пов’язані з номерами відліків п, беруть участь у виконанні базової операції на j-й ітерації, таким співвідношенням:
(10)
де j=1 ..., r-1 - номер повертаючих коефіцієнтів, що бере участь в базовій операції; ki - розряди r-ого кода номерів операндів.
Наприклад, для N=64 і r=2 на 1-й ітерації значення р(1) для всіх груп відліків рівне 0, на 2-й ітерації р(1)=k524= =k5N/4, т. д.
На третій ітерації
і т д.
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
…
…
…
…
4093
111111111101
101111111111
3071
4094
111111111110
011111111111
2047
4095
111111111111
111111111111
4095
2.2.1. Блок-схема перетворення
Рис. 4. Блок-схема алгоритму 4096-точкового перетворення за основою 2
3 Розрахунковий розділ
Частота роботи процесора: , звідси цикл виконання команди: .
base – основа базової операції «метелик»;
N – кількість точок вхідного перетворення;
base=2, N=4096
– кількість етапів перетворення;
– кількість базових операцій «метелик» на одному етапі;
– кількість базових операцій у всьому перетворенні;
Для виконання базової операції «метелик» необхідно:
4 операцій множення;
6 операцій додавання;
10 операцій читання з пам`яті:
- 2*2=4 (для читання дійсної та уявної частини вхідних відліків);
- 3*2=6 (для читання дійсної та уявної частини комплексних коефіцієнтів);
4 операцій запису:
- 2*2=4 (для запису дійсної та уявної частини вхідних відліків);
В результаті на одну базову операцію припадає 24 операцій: Nна 1 мет=24 (оп).
Тривалість виконання обчислення ШПФ:
Тривалість надходження даних у процесор для обробки:
– такт надходження даних;
Частота роботи LINK шини: (процесор ADSP21065), звідси цикл надходження команди: . І оскільки шина LINK опрацьовує по 4 розряди, необхідно ще помножити на 4.
Тривалість виходу даних із процесора:
Тривалість надходження даних у процесор, тривалість обчислення ШПФ та тривалість виходу даних із процесора:
4 Розробка функціональної схеми
Рис. 5. Функціональна схема
SPORT- (serial port, послідовний порт) — двонаправлений послідовний інтерфейс, призначений для обміну байтовою інформацією. Послідовний тому, що інформація через нього передається по одному біту, біт за бітом (на відміну від паралельного порту). Найчастіше для послідовного порту персональних комп'ютерів використовується стандарт RS-232c. Раніше послідовний порт використовувався для підключення терміналу, пізніше для модему або миші. Зараз він використовується для з'єднання зджерелами безперебійного живлення, для зв'язку з апаратними засобами обчислювальних систем.
Link-port (ADSP-21065) працює на частоті 60МГц (17нс). Він є паралельним портом; RAM: 544K byte; напруга споживання ядра: 3,3В; напруга споживання периферії: 3,3В; робоча температура -40...100 °C.
5. Розробка програми
Структуру програми, що виконує обчислення за алгоритмом ШПФ можна уявити наступним чином:
Рис. 6. Узагальнена блок-схема алгоритму
Кожен з трьох циклів призначений для правильного визначення номеру відліку в конкретний момент обчислення. Перший цикл визначає номер ярусу, другий – номер базової операції у ярусі, третій – номер відліку у базовій операції.
Вводиться масив, що зберігає відліки, в програмі названий matrix, його номер відповідно – N (кількість точок перетворення). Кожен елемент массиву – комплексне число. Інший массив W призначений для зберігання повертаючи множників. На кожну базову операцію припадає 3 повертаючих множника (четвертий фактично дорівнює 1), тому його розмір: 12*2048*3=73728 (12- кількість ярусів, 2048 - кількість базових операцій в ярусі). Елемент цього масиву є так само комплексним числом.
Текст програми, написаної на мові С, поданий нижче
N=2048;
struct complex
{ double re;
double im;
};
complex W[3*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*3+0].re –
- matrix[x2+i].im*W[n*2048+p*3+0].im;
temp1.im=
matrix[x1+i].im
+ matrix[x2+i].re*W[n*2048+p*3+0].im +
+ matrix[x2+i].im*W[n*2048+p*3+0].re;
temp2.re=
matrix[x1+i].re
+ matrix[x2+i].re*W[n*2048+p*3+0].im +
+ matrix[x2+i].im*W[n*2048+p*3+0].re;
temp2.im=
matrix[x1+i].im
- matrix[x2+i].re*W[n*2048+p*3+0].re +
+ matrix[x2+i].im*W[n*2048+p*3+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. На першому ярусі є 2048 групи операцій по 2 відліка кожна, на другому – 1024 груп і збірка ведеться по 4 відлікам і т.д.
Організація змінної j передбачає, що вона буде вибирати групу відліків для базової операції, спираючись на неї визначаються їх адреси змінними х1, х2. Ці адреси зміщуються за певним законом для кожної групи відліків, використовуючи третій цикл, що обробляє вже безпосередньо групу.
Змінні temp1, temp2 – зберігають тимчасові значення результатів обчислення. Значення f та p визначають адресу повертаючого множника для даної базової операції.
Висновки
В розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 2. Дана система обробляє вхідний сигнал, що є 32-розрядним. Вхідні дані представляються 4096-ма вхідними відліками, що містять дійсну та уявну частину.
В результаті набуто досвід у проектуванні обчислювальної системи, розглянуто основні компоненти, з яких вона складається, засвоєно алгоритми, на основі яких виконується обчислення.
Література
Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.
Куприянов М. С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. – Спб. : Политехника, 1998.
Марков С. Цифровые сигнальные процессоры. Книга 1, М.:фирма МИКРОАРТ, 1996-144 с.
Цифровой процессор обработки сигналов TMS32010 и его применение/Под ред. А.А.Ланнэ.-Л.:ВАС,1990.-296 с.
Применение цифровой обработки сигналов/ Под ред. Э.Оппенгейма.- М. Мир, 1980.- 552с.
Сверхбольшие интегральные схемы и современная обработка сигналов: Пер. с англ.- М.: Радио и связь, 1989.- 472с.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Гольденберг А. Ш., Матюшкин Б. Д., Поляк М. Н. Цифровая обработка сигналов. Справочник. –М.: Радио и связь, 1985-312с.
Цифровая обработка сигналов/ А.Б.Сергиенко – СПб.:Питер, 2002.-608с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора