Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Цифрова обробка сизналів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Кафедра інформаційних технологій видавничої справи
Інформація про роботу
Рік:
2012
Тип роботи:
Конспект лекцій
Предмет:
Теоретичні основи комп ютерної безпеки
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Кафедра інформаційних технологій видавничої справи
КОНСПЕКТ ЛЕКЦІЙ
з курсу
“Основи цифрової обробки сигналів”
Лектор – Рашкевич Ю.М.
д.т.н., професор
Львів - 2012 р.
Лекція 1. Дискретні сигнали та системи
Основні означення.
Сигнал – матеріальний носій інформації, здатний поширюватися у навколишньому середовищі. Сигнали постають у вигляді електричних, механічних, звукових, ультразвукових, електромагнітних, світлових коливань тощо.
У залежності від характері зміни в часі та зміни на множині значень сигнали класифікуються як неперервні та дискретні в часі, а також як неперервні та дискретні на множині значень. В цифровій обробці сигналів розглядаються дискретні в часі сигнали, які класифікуються наступним чином:
Дискретизовані сигнали – дискретні в часі та неперервні на множині значень,
Дискретні сигнали - дискретні як в часі, так і на множині значень.
Дискретність в часі означає, що значення сигналу визначаються лише в певні моменти часу, тобто для дискретних значень незалежної змінної - часу. Як правило, час дискретизується рівномірно, тобто – t = nT, де T – інтервал між відліками. Математично диск терні в часі сигнали представляються у вигляді впорядкованої послідовності чисел (часто їх називають часовими рядами), для їх опису використовуються наступні позначення:
x(n), N1 ≤ n ≤ N2 , (1)
x(nT), N1 ≤ n ≤ N2 , (2)
{x(n)}, N1 ≤ n ≤ N2 , (3)
{x(nT)}, N1 ≤ n ≤ N2 , (4)
Позначення (2) та (4) використовуються у випадку, якщо для математичного представлення важливою є наявність інформації про період дискретизації (інтервал між відліками) початкового неперервного сигналу. У більшості випадків використовується позначення (1).
У нашому курсі ми будемо, як правило, розглядати дискретизовані сигнали, часовий аргумент яких буде цілим невід’ємним числом. У цьому випадку інтервал зміни аргументу буде зображатися: n = 0,1 … N, або n = .
В цифровій обробці сигналів є ряд сигналів, які часто зустрічаються та відіграють особливу роль в математичних представленнях.
Одиничний імпульс - . Сигнал визначений при n = -∞,∞ і приймає одиничне значення лише при нульовому аргументі:
=
Одиничний скачок – u(n). Сигнал визначений при n = -∞,∞ і приймає одиничне значення лише при невід’ємному аргументі:
u(n) =
Дискретний гармонічний сигнал періодом N:
h(n) = cos(2πn/N)
Дискретна комплексна експонента:
Спадаюча експонента:
g(n) =
Легко показати, що одиничний скачок пов'язаний із одиничним імпульсом співвідношенням:
(5)
Довільний дискретний сигнал (часова послідовність) може бути представлений через одиничний імпульс:
(6)
Лінійна система із постійними параметрами.
Дискретна лінійна систем із постійними параметрами (ЛПП-система) по суті являє собою алгоритм перетворення вхідної послідовності x(n) у вихідну послідовність y(n).
x(n) y(n)
Рис.1. Дискретна ЛПП-система.
Система називається лінійною, оскільки лінійній комбінації вхідних сигналів x1(n) та x2(n) відповідає така ж лінійна комбінація відповідних їм вихідних сигналів y1(n) та y2(n). Тобто:
a x1(n) + b x2(n) → a y1(n) + b y2(n),
де a та b – константи.
Система називається системо із постійними параметрами, оскільки вхідному сигналові x(n), затриманому в часі на постійну величину n0, відповідає сигнал y(n), затриманий на таку ж величину, тобто:
x(n+n0) → y(n+n0)
Основною характеристикою, яка в повній мірі описує властивості ЛПП-системи в часовій області, є імпульсна характеристика h(n), яка є реакцією ЛПП-системи на одиничний імпульс:
→ h(n)
Враховуючи властивості лінійності та постійності параметрів, зв'язок між вхідним та вихідним сигналами та імпульсною характеристикою можна представити у вигляді:
(7)
Перестановка змінних дає іншу формулу:
Математична операція, представлена у формулах (7-8), є надзвичайно поширеною в цифровій обробці сигналів, має власну назву – дискретна згортка, також власне позначення - *. Таким чином, формули (7) та (8) можна об’єднати - y(n) = x(n)* h(n).
Дискретна згортка вимагає значної кількості операцій множення та додавання, тому опис ЛПП-системи в часовій області не є найбільш ефективним.
ЛПП-систему можна фізично реалізувати (використовувати в реальному часі), якщо значення вихідного сигналу при n = n0 залежить від значень вхідного сигналу при n ≤ n0 та не залежить від значень вхідного сигналу при n > n0 (теперішнє не залежить від майбутнього). Необхідною та достатньою умовою цього є рівність нулю імпульсної характеристики при від’ємному аргументі.
ЛПП-система є стійкою (обмеженому сигналові на вході завжди відповідає обмежений сигнал на виході системи), якщо її імпульсна характеристика задовольняє умові:
В частотній області ЛПП-система повністю описується частотною характеристикою, яка є перетворенням Фур’є імпульсної характеристики:
В ЛПП-системах, описаних рівняннями (7-8), значення вихідного сигналу залежать лише від значень вхідного сигналу та імпульсної характеристики. Якщо ж біжуче значення вихідного сигналу залежить також від попередніх значень на виході, то така система описується різницевим рівнянням виду:
, n ≥ 0 (8)
Такими рівняннями, наприклад, описуються рекурсивні цифрові фільтри, вони дають можливість ефективно побудувати ЛПП-систему, знайти її власні частоти, порядок тощо.
Рівняння (7) задає опис ЛПП-системи в часовій області. Для отримання опису системи в частотній області використаємо в якості вхідного сигналу комплексну експоненту x(n)=. На виході системи маємо:
Таким чином, вхідний сигнал пройшов через систему без будь-яких змін, витягнувши при цьому додатковий комплексний множник H(ω), який пов'язаний із імпульсною характеристикою ЛПП-системи наступним чином:
(9)
H(ω) називається частотною характеристикою ЛПП-системи, оскільки вона визначає коефіцієнти передачі на вихід для кожного значення частоти ω.
Приклади задач:
Побудувати графік сигналу .
Побудувати графік сигналу .
Обчислити дискретну згортку сигналів: та .
Лекція 2. Z – перетворення
2.1. Пряме і зворотне Z – перетворення.
Опис та аналіз ЛПП-систем можна значно полегшити, використавши нечасові площини (наприклад, частотну область, Z-площину тощо).
Z-перетворення дискретного сигналу x(n) задається виразом:
(10)
Достатньою умовою збіжності ряду (10) є:
(11)
Множина значень z, яких ряди є збіжними, утворює область збіжності, яка в загальному випадку описується виразом:
(12)
Зворотне Z – перетворення обчислюється наступним чином:
(13)
де С – будь-який контур в області збіжності Z – перетворення, який охоплює точку z=0.
2.2. Властивості Z – перетворення.
Лінійність:
сигнал має Z – перетворення .
Зсув в часовій області:
сигнал має Z – перетворення .
Лінійне зважування:
сигнал має Z – перетворення .
Експоненційне зважування:
сигнал має Z – перетворення .
Обернення часу:
сигнал має Z – перетворення .
Дискретна згортка:
сигнал має Z – перетворення .
Приклади задач:
Обчислити Z – перетворення сигналу: .
Обчислити Z – перетворення сигналу: .
Обчислити Z – перетворення сигналу: .
Обчислити Z – перетворення сигналу: .
Лекція 3. Перетворення Фур’є
Перетворення Фур’є дискретного сигналу.
Опис сигналу в дискретному часі за допомогою перетворення Фур’є задається у вигляді:
(14)
(15)
Легко побачити (див. формули (10) та (13)), що перетворення Фур’є є частковим випадком Z – перетворення. Тобто, перетворення Фур’є отримується шляхом обчислення Z – перетворення на одиничному колі Z – площини: . Із урахуванням того, що |z|=1 на основі формули (11) отримуємо умову збіжності ряду:
(16)
Частота ω інтерпретується як кут на Z – площині. Властивості перетворення Фур’є отримуються на основі властивостей перетворення Фур’є відповідною заміною аргументів. Важливою особливістю перетворення Фур’є також є його періодичність із періодом 2π, що є очевидним, враховуючи наявність у формулі (14) комплексної синусоїди.
Дискретне перетворення Фур’є.
Як для аналогових сигналів, якщо сигнал є періодичним із періодом N:
(17)
то його можна представити не у вигляді інтегралу, а у вигляді суми синусоїд:
(18)
(19)
Вираз (19) задає точне представлення періодичного сигналу. Але формули (18) та (19) також можна використати для представлення скінченого неперіодичного сигналу.
Розглянемо послідовність скінченої довжини, яка є нульовою поза межами інтервалу від 0 до N-1. Згідно (10) її Z – перетворення має вигляд:
(20)
Якщо обчислити X(z) в N рівновіддалений точках одиничного кола, тобто при:
,
то отримаємо:
(21)
Якщо тепер побудувати періодичну послідовність у вигляді нескінченого повторення сегменту x(n) :
, (22)
то відліки X(k) (порівняймо (18) і (21)) являють собою коефіцієнти Фур’є періодичної послідовності із формули (22).
Таким чином, ми можемо описати сигнал довжиною N за допомогою дискретного перетворення Фур’є (ДПФ) у вигляді:
(23)
(24)
Формально відмінність між парами формул (18)-(19) та (23)-(24) полягає у відсутності символів, що позначають періодичність також в наявності у формулах ДПФ діапазонів зміни k та n від 0 до N-1. Але слід пам’ятати, що усі послідовності при використанні ДПФ ведуть себе так, як періодичні. Тобто, якщо початковий сигнал x(n) у формулі (23) не є періодичним, то відновлений на основі його ДПФ за формулою (24) сигнал x(n) вже є періодичним. І лише наявність у формулі (24) обмеження по n від 0 до N-1 дає можливість використовувати для цих різних сигналів одне і те ж позначення.
Періодичність по N сигналу x(n) можна підкреслити наступним чином:
(25)
Властивості дискретного перетворення Фур’є.
Дискретне перетворення Фур’є можна розглядати як дискретизований варіант Z – перетворення. А це означає, що властивості ДПФ із врахуванням періодичності є аналогічними властивостям Z – перетворення.
Лінійність:
сигнал має ДПФ .
Зсув в часовій області:
сигнал має ДПФ .
Обернення часу:
сигнал має ДПФ .
Дискретна згортка:
сигнал має ДПФ .
Множення послідовностей:
сигнал має ДПФ .
Важливою особливістю ДПФ є наявність ефективних алгоритмів його обчислення (кількість операцій множення приблизно дорівнює ) , що зобумовлює його широке використання для розв’язування широкого кола задач цифрової обробки сигналів.
Алгоритм обчислення зворотного ДПФ.
Покажемо, що зворотне ДПФ можна обчислити на основі алгоритму обчислення прямого ДПФ.
Зворотне ДПФ обчислюється на основі (24):
Візьмемо комплексне спряження відлого виразу та домножимо обидві частини на N:
(26)
Права частина виразу (26) являє собою ДПФ сигналу X*(k) і може бути обчислене за допомогою відповідного алгоритму.
Таким чином, зворотне ДПФ у вигляді сигналу x(n) можна обчислити, взявши ще раз комплексне спряження від (26) та розділивши результат на N:
(27)
Таким чином, будь-який алгоритм обчислення ДПФ дозволяє обчислити як пряме, так і зворотне ДПФ. Зауважимо, що це не потребує додаткових операцій множення, оскільки комплексне спряження зводиться до заміни знаку уявної частини, а ділення на N на практиці (як правило N=2р, де р – ціле число) реалізовується зсувом коми у дійсному числі на p=logN розрядів вліво.
Приклади задач:
Обчислити ДПФ сигналу: , N=10.
Обчислити ДПФ: , N=6.
Обчислити ДПФ: , N=10.
Лекція 4. Співвідношення між неперервними та дискретними сигналами
Якщо дискретний сигнал xд(n) отримано шляхом дискретизації із періодом Т неперервного сигналу xн(n), то співвідношення між ними задається виразом: xд(n) = xн(n+Т) для -∞<n<∞ . Розглянемо, яким чином дискретизація впливає на перетворення Фур’є сигналу.
Теорема дискретизації
Для неперервного сигналу пряме та зворотне перетворення Фур’є задається формулами:
(28)
(29)
Подібні співвідношення для дискретизованого сигналу мають вигляд:
(30)
(31)
Оскільки x(nT)=x(t)|t=nT , то можливо пов’язати перетворення Фур’є неперервного та дискретного сигналів, обчисливши (29) для t=nT. При цьому замінимо інтеграл із нескінченими границями нескінченою сумою інтегралів на інтервалах довжиною 2π/T :
(32)
У виразі (32) змінимо порядок виконання операцій додавання та інтегрування:
(33)
Порівнюючи підінтегральні вирази у формулах (31) та (33), отримаємо:
(34)
Формула (34) визначає зміст теореми дискретизації (в деяких літературних джерелах ця теорема називається теоремою Найквіста, або теоремою Котєльнікова) і показує, що спектральна функція дискретизовагого сигналу складається із суми нескінченого числа повторень спектральної функції неперервного сигналу, зсунутих в часовій області на інтервал 2π/T. Для того, щоб повторення спектральної функції неперервного сигналу при додаванні не перекривалися між собою та, відповідно, не спотворювали образ спектральної функції неперервного сигналу на частотному інтервалі від –π/T до π/T, що дасть можливість після дискретизації відновити неперервний сигнал без спотворень, повинна виконуватися умова: ωс≤π/Т (де ωс – гранична частота спектру неперервного сигналу). Це задає вимогу до мінімальної частоти дискретизації:
(35)
Формула (35) є прямим висновком теореми дискретизації, у ній позначає частоту дискретизації, а - максимальну частоту (ширину діапазону частот) неперервного сигналу.
Проріджування та інтерполяція сигналів
Проріджування – процес зниження частоти дискретизації сигналу (у прорідженому сигналі період дискретизації T’=MT). Проріджений сигнал пов'язаний із початковим сигналом співвідношенням: y(n)=x(Mn), а їх перетворення Фур’є – виразом:
(36)
Очевидно, що формула (36) є дійсною, якщо у прорідженому сигналі все ще виконується вимога теореми дискретизації, тобто 1/T’>2fc .
Якщо ж згідно із заданим коефіцієнтом проріджування умова теореми дискретизації перестає виконуватися (у прорідженому сигналі виникне явище перекривання спектральних образів), а практична потреба має вищий пріоритет, то для зменшення спотворення сигналу необхідно перед виконанням процедури проріджування провести попередню фільтрацію сигналу за допомогою фільтра низьких частот (ФНЧ) із частотою зрізу fзр =1/T’.
На відміну від проріджування, процедура інтерполяції сигналу (підвищення його частоти дискретизації) не несе загрози перекривання спектральних образів, оскільки 1/T’ > 1/T, і спектральні образи при інтерполяції лише віддаляються один від одного.
Якщо необхідно змінити частоту дискретизації в дробове число разів (T’=TM/L), то цього можна досягти, послідовно виконавши інтерполяцію в L разів та проріджування в M разів. Для забезпечення виконання умов теореми дискретизації перед процедурою проріджування необхідно виконати відповідну фільтрацію.
x(n) y(n)
Рис. 2. Зміна частоти дискретизації.
Приклади задач:
Визначити частоту зрізу ФНЧ для проріджування у 2 рази сигналу із граничною частотою 80 Гц при початковій частоті дискретизації 200 Гц.
Визначити частоту зрізу ФНЧ для проріджування у 3 рази сигналу із граничною частотою 40 Гц при початковій частоті дискретизації 100 Гц.
Визначити частоту зрізу ФНЧ для проріджування у 1,5 разів сигналу із граничною частотою 25 Гц при початковій частоті дискретизації 60 Гц.
Лекція 5. Згортки дискретних сигналів
Операція дискретної згортки є однією із найпоширеніших операцій аналізу та синтезу сигналів в часовій області. В залежності від особливостей вхідних сигналів дискретні згортки можуть бути круговими (циклічними) або лінійними.
Кругова згортка.
Нехай x(n) та h(n) є періодичними послідовностями із однаковим періодом N. Кругова (циклічна) згортка цих послідовностей визначається формулою:
(37)
Визначимо ДПФ послідовності y(n).
Очевидно, що в силу періодичності перетворення Фур’є Y(k) також є періодичною послідовністю із періодом N. Таким чином, усі послідовності, які фігурують у круговій згортці, є періодичними із однаковим періодом N.
Лінійна згортка.
Лінійна згортка є дискретною згорткою двох скінчених послідовностей різної довжини. Нехай сигнал x(n) має довжину N1, а сигнал y(n) - N2. Лінійна (аперіодична) згортка цих сигналів визначається формулою:
(38)
Легко побачити, що довжина сигналу y(n) дорівнює N3=N1+N2-1. Загальна кількість операцій множення для обчислення згортки за формулою (38) визначається добутком N1N2. При великих довжинах сигналів обчислення дискретної згортки в реальному часі ставить високі вимоги до процесора. Зменшити кількість обчислень можна за допомогою використання схеми обчислення кругової згортки та алгоритму швидкого перетворення Фур’є. Таким метод обчислення лінійної згортки називається швидкою згорткою.
Алгоритм включає наступні кроки:
Доповнення кожного із сигналів справа нулями до загальної довжини N3=N1+N2-1;
Обчислення ДПФ кожного із модифікованих сигналів;
Обчислення скалярного добутку цих ДПФ, що (згідно із 5.1) дає ДПФ сигналу y(n);
Обчислення зворотного ДПФ (отримання y(n)).
Загальна кількість операцій множення (враховуючи необхідні для обчислення ДПФ сигналу довжиною N на основі алгоритму швидкого перетворення Фур’є) в даному випадку є рівною 3N3logN3+N3= N3(3logN3+1).
Секціоновані згортки
В багатьох практичних задачах необхідно виконувати операцію лінійної згортки двох сигналів у випадку, коли довжина одного з них набагато перевищує довжину іншого. Очевидно, що і в цьому випадку можна використати алгоритм швидкої згортки, але він стає неефективним: по-перше, необхідно чекати закінчення довшого сигналу, що приводить до значної затримки; по-друге, сам алгоритм швидкої згортки стає малоефективним, а також виникають інші обчислювальні складності, пов’язані із реалізацією алгоритму швидкого перетворення Фур’є.
Більш ефективним є розбиття (секціонування) довшого сигналу на частини та обчислення часткових згорток із подальшим їх об’єднанням у вихідну послідовність.
Маємо сигнали: x(n) довжиною N1, h(n) довжиною N2, і N1 >> N2 . Розбиваємо x(n) на секції довжиною N3, які не перекриваються між собою:
, (39)
де
(40)
Обчислимо лінійну згортку сигналів x(n) та h(n):
(41)
Довжина кожної із часткових згорток yk(n) у формулі (41) є рівною (N3+N2-1), тобто є ділянка довжиною (N2-1), на якій сусідні часткові згортки перекриваються, і, згідно із (41), їх необхідно додати між собою.
Такий метод обчислення згортки на основі секціонування довгого сигналу називається методом перекривання із підсумовуванням.
Приклади задач:
Обчислити кругову згортку сигналів: x(n)=2n+1 ,h(n)=n2-1, N=4;
Обчислити кругову згортку сигналів: x(n)=(2,3,0,1) ,h(n)=n+2, N=4;
Обчислити лінійну згортку сигналів: x(n)=2n2-3, N1=4; h(n)=(2,-1,3);
Обчислити лінійну згортку сигналів: x(n)=(1,2,3,4); h(n)=3-n, N2=3;
Визначити кількість операцій множення для обчислення лінійної згортки в задачі 4 при використанні методу кругової згортки.
Лекції 6-7. Швидке перетворення Фур’є
Основним недоліком представлення сигналу у вигляді дискретного перетворення Фур’є є велика кількість обчислень (в першу чергу – операцій множення) для його реалізації. Згідно із (23) для обчислення ДПФ сигналу довжиною N необхідно N2 операцій множення. Оскільки в більшості задач цифрової обробки сигналів ДПФ є лише проміжним представленням сигналу, то реалізація дискретних систем в реальному часі ставить надзвичайно високі вимоги до потужності обчислювальних засобів.
В 1965 році двоє американських математиків Джеймс Кулі (Cooley J.W.) і Джон Тьюкі (Tukey J.W.) запропонували алгоритм обчислення ДПФ, за допомогою якого можна суттєво скоротити кількість операцій. Цей алгоритм тепер відомий під назвою алгоритм швидкого перетворення Фур’є (ШПФ).
Алгоритм ШПФ з основою 2.
Перепишемо формулу (23) у вигляді:
, де (42)
Для подальших математичних перетворень розглянемо деякі властивості W:
Враховуючи періодичність і з періодом N комплексної синусоїди, маємо для цілих чисел: ;
і навпаки;
.
Основна ідея алгоритму полягає в розділенні початкового сигналу на 2 рівні частини, обчисленні ДПФ кожної із частин та формуванні ДПФ цілого сигналу на основі ДПФ його частин. Для обчислення ДПФ обох частин сигналу необхідно (N/2)2+(N/2)2=N2/2 операцій множення. Продовжуючи подальший поділ кожної із частинок на 2 (допоки не отримаємо частинки довжиною 1 відлік), можна суттєво скоротити кількість обчислень. Проблемою, яку і розв’язали Кулі і Тьюкі, є формування ДПФ цілого сигналу на основі ДПФ його частин.
Алгоритм ШПФ із проріджування в часовій області
Нехай маємо початковий сигнал x(n) довжиною N. Розділимо його на частини на основі парності порядкових номерів його елементів:
(43)
, .
N -точкове ДПФ сигналу x(n) тепер можна записати у вигляді:
(44)
Із урахуванням другої властивості W формула (44) приймає вигляд:
(45)
де X1(k) та X2(k) – (N/2) - точкові ДПФ послідовностей x1(n) та x2(n). Таким чином, для обчислення X(k) на основі X1(k) та X2(k) нам необхідно додатково N операцій множення. При великих N це практично означає зменшення на 50% обчислювальних затрат.
Оскільки X(k) визначено для , а X1(k) та X2(k) визначені для , то необхідно до визначити формулу (45) для решти k. Це легко зробити, використовуючи властивість періодичності ДПФ:
(46)
Формулу (46), враховуючи третю властивість W можна записати у вигляді:
(47)
Для графічного представлення процесу обчислення ДПФ вводиться поняття базової операції алгоритму ШПФ:
a a+b
Wk
A aWk
b a-b
Рис. 3. Базова операція (метелик) алгоритму ШПФ із основою 2.
Граф процесу обчислення ДПФ 8-точкового сигналу на основі двох 4-точкових ДПФ представлено на рис. 4.
x1(0)=x(0) X1(0) X(0)
x1(1)=x(2) X1(1) X(1)
x1(2)=x(4) X1(2) X(2)
W0
x1(3)=x(6) X1(3) X(3)
W1
x2(0)=x(1) X2(0) X(4)
W2
x2(1)=x(3) X2(1) X(5)
W3
x2(2)=x(5) X2(2) X(6)
x2(3)=x(7) X2(3) X(7)
Рис. 4. Обчислення 8-точкового ДПФ на основі двох 4-точкових.
Наведена схема обчислень може бути використана для розрахунку кожного із 4-точкових ДПФ на основі 2-точкових. За аналогією із перетвореннями, які привели до формули (45), можна отримати:
(48)
, (49)
де A(k) та B(k) – дискретні перетворення Фур’є сигналів a(n) та b(n), які в свою чергу є частинами сигналу x1(n) із парними та непарними порядковими номерами елементів. Аналогічне до (49) рівняння можна записати для X2(k).
Процес зменшення розмірності ДПФ з L до L/2, де L є рівним степені 2, можна продовжувати до того часу, поки не залишаться лише 2-точкові ДПФ (у нашому прикладі це буде вже після другого кроці), які на останньому кроці алгоритму можна розрахувати без використання операцій множення за формулами:
(50)
Заключний граф процесу обчислення 8-точкового ДПФ має вигляд:
x(0) X(0)
W0
x(4) X(1)
W0
x(2) X(2)
W0 W2
x(6) W0 X(3)
x(1) X(4)
W0 W1
x(5) X(5)
W0 W2
x(3) X(6)
W0 W2 W3
x(7) X(7)
Рис. 5. Обчислення 8-точкового ДПФ.
Алгоритм ШПФ із проріджування в частотній області
Даний алгоритм відрізняється від попереднього способом поділу початкового сигналу на частини: в даному випадку послідовності x1(n) та x2(n) являють собою відповідно першу та другу половини сигналу x (n).
(51)
,
Тоді N –точкове ДПФ послідовності x (n) можна записати у вигляді:
(52)
Враховуючи, що , маємо:
(53)
Значення ДПФ початкового сигналу обчислимо окремо для його елементів із парними і непарними номерами в послідовності:
, (54)
(55)
Як показують вирази (54) та (55), парні та непарні елементи ДПФ початкового сигналу можна отримати із N/2 –точкових ДПФ послідовностей:
(56)
(57)
Таким чином, як і в попередньому алгоритмі, обчислення N–точкового ДПФ зводиться до обчислення двох N/2–точкових ДПФ. Базова операція в даному випадку має дещо інший вигляд, оскільки множення на W проводиться після виконання операцій додавання та віднімання в “метелику”:
a a+b
Wn
b (a-b)Wn
Рис. 6. Базова операція алгоритму ШПФ із проріджуванням в частотній області
Перший крок процесу обчислення 8-точкового ДПФ на основі даного алгоритму наведений у вигляді графу на рис. 7.
x(0) f(0) X(0)
x(1) f(1) X(2)
x(2) f(2) X(4)
W0
x(3) f(3) X(6)
W1
x(4) g(0) X(1)
W2
x(5) g(1) X(3)
W3
x(6) g(2) X(5)
x(7) g(3) X(7)
Рис. 7. Обчислення 8-точкового ДПФ на основі двох 4-точкових.
Як і в попередньому алгоритмі, процедуру зменшення розмірності послідовності можна продовжувати аж до отримання послідовностей одиничної довжини. Математичні перетворення на кожному кроці є однаковими. В результаті трьох кроків отримаємо:
x(0) X(0)
W0
x(1) W0 X(4)
x(2) X(2)
W0 W2 W0
x(3) X(6)
W1
x(4) X(1)
W2 W0
x(5) W0 X(5)
W3
x(6) X(3)
W2 W0
x(7) X(7)
Рис. 8. Обчислення 8-точкового ДПФ.
Порівнюючи обидва алгоритми, відзначимо ряд їх спільних властивостей та відмінностей:
Кількість кроків перетворення є однаковою, оскільки вона визначається степенем число 2 у довжині початкової послідовності N.
На кожному кроці кожного алгоритму виконується N/2 операцій множення (множення на W). При цьому певна кількість операцій множення є умовною (множення на W0).
Загальна кількість операцій множення є однаковою – N/2logN, а, враховуючи комплексність W, загальна кількість операцій множення дійсних чисел в алгоритмах ШПФ з основою 2 складає NlogN.
Структура базової операції дещо відрізняється (див. Рис. 3 і Рис. 5).
Проміжні перетворення в першому алгоритмі проводяться в частотній області (рівняння (45)), а в другому – в часовій (рівняння (56)-(57)).
Порядкові номери елементів у вхідних та вихідних послідовностях є відмінними (детальніше нижче).
В цілому є очевидним, що між двома алгоритмами існує набагато більше спільних рис, ніж відмінностей, що свідчить про певну єдність алгоритмів ШПФ з основою 2.
Двійково-інверсна перестановка в алгоритмах ШПФ.
Як показано на рисунках 5 та 8, порядок слідування елементів послідовностей на вході та виході є різними. Це пояснюється поділом на парні та непарні елементи згідно із формулами (43) та (54)-(55). Порядок слідування вхідних елементів в першому алгоритмі та вихідних у другому називають двійково-інверсним. Побудова двійково-інверсної перестановки в алгоритмах ШПФ з основою 2 ілюструється таблицею 1.
Таблиця 1. Формування двійково-інверсної перестановки
Порядковий номер
Двійкове представлення
Двійкова інверсія
Двійково-інверсний номер
0
000
000
0
1
001
100
4
2
010
010
2
3
011
110
6
4
100
001
1
5
101
101
5
6
110
011
3
7
111
111
7
За представленим алгоритмом можна побудувати двійкову інверсію для довільного N, яке є степенем числа 2.
Приклади задач:
Побудувати двійкову інверсію для N =16.
Показати, що при послідовностях одиничної довжини часова та частотна площини при обчисленні ДПФ співпадають.
Описати у вигляді графа процес обчислення ШПФ при N =4.
Лекція 8. Єдність алгоритмів ШПФ
Незважаючи на велике різноманіття алгоритмів ШПФ (і не тільки з основою 2), виявляється, що усі вони можуть бути отримані за допомогою єдиної операції – представлення одномірного масиву двохмірним. Для алгоритмів із основою 2 таке представлення виглядало наступним чином: вектор довжиною N перетворювався у матрицю розміром N/2х2.При цьому в залежності від того, яким чином ми проводили це перетворення (за рядками, чи за стовбцями), отримували перший, чи другий алгоритми.
Розглянемо це перетворення в загальному випадку.
При перетворенні вектора довжиною N в матрицю, яка має L рядків та M стовбців, співвідношення між індексами є наступним: n=Ml+m (m - біжучий номер стовбця, l - рядка). При обчисленні ДПФ його також представимо у вигляді матриці, яка має яка має M рядків та L стовбців. Співвідношення між індексами: k=Lr+s (r - номер стовбця, s - рядка). Підставимо ці співвідношення у формулу ДПФ (42):
(58)
У залежності від порядку виконання операцій у формулі (58) можна отримати два різних алгоритми.
Запишемо (58) у вигляді:
26.12.2013 02:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора