Лабораторна робота № .6
”Використання способів зменшення часової складності алгоритму на прикладі алгоритму швидкого перетворення Фурье".
Мете роботи:
Ознайомлення з алгоритмом ШПФ.
Засвоєння способів зменшення часової складності алгоритмів.
Теоретичні відомості:

HYPERLINK \l "_Цифрове_оброблення_сигналів"HYPERLINK \l "_Цифрове_оброблення_сигналів"Цифрове оброблення сигналів
HYPERLINK \l "_Цифрове_оброблення_сигналів"Дискретне перетворення Фурье (ДПФ )
HYPERLINK \l "_Швидке_перетворення_Фурье" Швидке перетворення Фурье ( ШПФ )
HYPERLINK \l "_Апаратна_реалізація_"Апаратна реалізація і час виконання алгоритмів ШПФ
HYPERLINK \l "_Реалізація__алгоритмів_1"Реалізація алгоритмів ШПФ в реальному масштабі часу
HYPERLINK \l "_РОЗШИРЕННЯ_СПЕКТРА_АНАЛІЗОВАНОГО" Розширення спектра сигналу і зважування з використанням віконної функції
HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності

Завдання на лабораторну роботу
Користуючись програмою HYPERLINK "..\\Spectr\\Spectr.exe"Spectr.exe :
Задати варіант завдання і натиснути кнопку "ОК"
Проаналізувати отриманий спектр сигналу
Дати характеристику вхідного сигналу, якому відповідає отриманий спектр
Визначити значення N
Визначити параметри A, C, E, F, AI, CI вхідного сигналу
y(n) = ACos(2Pi*C*n/(N - E) -2Pi/F) + Inf(AI, CI)
Варіанти завдання:
N, N+30, N+60, де N – номер по списку
HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Цифрове оброблення сигналів
В сучасних каналах зв'зку широко використовуються пристрої цифрового оброблення сигналів. Ці пристрої реалізують той чи інший алгоритм цифрового оброблення. Прикладами таких алгоритмів є аналіз і синтез цифрових фільтрів, спектральний аналіз сигналів, кепстральній аналіз, модуляція сигналу, демодуляція, перенос та інверсія спектру та інші.
Цифровий фільтр являє собою пристрій, який перетворює вхідний сигнал. Вид перетворення повністю визначається характеристиками фільтру. Фільтр призначений для частотної селекції сигналів. Він пропускає з малим ослаьленням корисні частотні складові (гармоніки) спектра сигналу і значно послаблює гармоніки, присутність яких у спектрі вихідного сигналу є небажаною.
Існують різні способи реалізації фільтрів зі скінченими імпульсними характеристиками. Серед них - пряма згортка і шидка згортка.
Пряма згортка
Нехай x(nT) і h(nT) – дві періодичні послідовності з періодами по N відліків.
Періодичною ( циклічною ) згорткою таких послідовностей називається послідовність y(nT), яка визначається співвідношенням:
EMBED Equation.3 ,
Послідовність y(nT) також є періодичною з періодом N відліків, тому достатньо обчислити її на одному періоді, наприклад при n = 0, 1, … ,N-1. Це співвідношення справедливе і для скінчених послідовностей x(nT) і h(nT) (n = 0, 1, … ,N-1), якщо розглядати їх як один період відповідних їм періодичним послідовностям. Періодична згортка скінчених послідовностей також буде скінченою.
Якщо EMBED Equation.3 ,то кількість операцій множення додавання в кожному рядку дорівнює N, кількість рядків теж дорівнює N. Тому загальна кількість множень додавань (часова складність) дорівнює N2.
Швидка згортка.
Одним із варіантів швидкої згортки може бути обчислення згорки за допомогою операції ДПФ. Для цього необхідно виконати наступні дії:
Обчислення ДПФ послідовності x(nT) :
EMBED Equation.3 , k = 0, 1, … ,N-1
EMBED Equation.3 ;
Обчислення ДПФ послідовності h(nT) :
EMBED Equation.3 , k = 0, 1, … ,N-1
Перемноження коефіціентів отриманих ДПФ :
Y(k) = X(k) H(k), k = 0, 1, … ,N-1
Обчислення ЗДПФ послідовності Y(k) :
EMBED Equation.3 , n = 0, 1, … ,N-1
Послідовність y(nT) і є згортка.
Звідки видно, що операція згортки в часовій області еквівалентна множенню в частотній області. Це співвідношення має велике значення через те, що дозволяють виконувати лінійне оброблення сигналів і моделювати лінійні системи. Стосовно до цих задач x(nT) та y(nT) розглядаються як вхідний та віхідний сигнали системи, а h(nT) – як її імпульсна характеристика.
Таким чином, згортку можна виконувати або безпосередньо за співвідношенням (1), або непрямим методом, використовуючи ДПФ для перетворення періодичних функцій часу в частотну область. В останньому випадку для отримання Y(k) при заданих h(nT) i x(nT) потрібно обчислити і перемножити відповідні перетворення H(k) i X(k). Після чого Y(k) перетворюється за допомогою зворотнього ШПФ у вихідний сигнал системи y(nT).
На перший погляд обчислення згортки в частотній області здається більш тривалою операцією в порівнянні з прямим методом. Насправді ж непрямий метод може бути швидшим. Причина цього полягає в існуванні ефективного методу обчислення ДПФ та ЗДПФ, відомого як "Швидке перетворення Фур'е".
Кепстральний аналіз дозволяє розділяти сигнал і заваду, які взаємодіють через згортку Для розділення у загальному випадку використовується лінійний фільтр. Для того, щоб його застосувати, необхідно перетворити сигнал і заваду, які взаємодіють через згортку у їх суму EMBED Equation.3 . Це перетворення наступне:
EMBED Equation.3 >ШПФ> фільтр > EMBED Equation.3 >ЗШПФ> EMBED Equation.3 .
Цей вираз називається кепстром. Тепер за допомогою лінійного фільтру можна позбавитися завади EMBED Equation.3 , отримати EMBED Equation.3 і повернутися до початкового значення EMBED Equation.3 без завади. Для цього потрібно пройти описаний ланцюг у зворотному порядку.

HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Дискретне перетворення Фурье
У 1807 р. французький математик і фізик Жан Батист Жозеф Фурье представив до Французького Інституту (Institut de France) доповідь про синусоїдальне представлення температурних розподілів. Доповідь містила спірне твердження про те, що будь-який безперервний періодичний сигнал може бути представлений сумою вибраних належним чином сигналів синусоїдальної форми. Серед членів комітету, публікацій, що займалися розглядом публікацій, були два відомі математики - Жозеф Луї Лагранж і Пьер Симон де Лаплас. Лагранж категорично заперечив проти публікації на підставі того, що підхід Фурье непридатний до розривних функцій, таких як сигнали прямокутної форми. Робота Фурье була відхиена, перш за все через заперечення Лагранжа, і була видана після смерті Лагранжа, приблизно п'ятнадцятьма роками пізніше.
Насправді і Фурье, і Лагранж, принаймні частково, мали рацію. Лагранж мав рацію в тому, що підсумовуванням сигналів синусоїдальної форми неможливо точно сформувати сигнал, що містить вертикальний фронт. Але можна дуже точно до нього наблизитися, якщо використовувати достатню кількість гармонійних сигналів. (Це описується ефектом Гіббса і сьогодні добре зрозуміло вченим, інженерам і математикам).
Аналіз Фурье закладає основи багатьох методів, що застосовуються в області цифрової обробки сигналів (ЦОС). По суті справи, перетворення Фурье (фактично існує декілька варіантів таких перетворень) дозволяє зпівставити сигналу, заданому в часовій області, його еквівалентне представлення в частотній області. Навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фурье дозволяє визначити відповідний сигнал в часовій області.
На додаток до частотного аналізу, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фурье його імпульсної реакції. І навпаки, якщо певна частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотного перетворення Фурье над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їх імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра.
Сімейство перетворень Фурье (перетворення Фурье, ряди Фурье, дискретні ряди Фурье і дискретне перетворення Фурье) представлено на рис..2. З часом ухвалені визначення отримали розвиток (не обов'язково цілком логічний) залежно від того, чи є сигнал безперервно-аперіодичним (continuous-aperiodic), безперервно-періодичним, дискретно-аперіодичним (continuous-periodic)або дискретно-періодичним (sampled-periodic). В даному контексті термін sampled означає те ж саме, що discrete (дискретний) (тобто дискретні за часом вибірки).

ЗАСТОСУВАННЯ ДИСКРЕТНОГО ПЕРЕТВОРЕННЯ ФУРЬЕ (ДПФ)
EMBED PBrush
Рис. 1
Цифровий спектральний аналіз
Аналізатори спектра
Обробка мови
Обробка зображень
Розпізнавання образів
Проектування фільтрів
Обчислення імпульсної характеристики по частотній
Обчислення частотної характеристики по імпульсній
Швидке перетворення Фурье (IПФ) - це простий алгоритм для ефективного обчислення дискретного перетворення Фурье (ДПФ)
СІМЕЙСТВО ПЕРЕТВОРЕНЬ ФУРЬЕ ЯК ФУНКЦІЯ СИГНАЛУ В ЧАСОВІЙ ОБЛАСТІ
EMBED PBrush
Рис. 2
Єдиний член цього сімейства, який має відношення до цифрової обробки сигналів, - це дискретне перетворення Фурье (ДПФ), яке оперує дискретною за часом вибіркою періодичного сигналу в часовій області. Для того, щоб бути представленим у вигляді суми синусоїд, сигнал повинен бути періодичним. Але як набір вхідних даних для ДПФ доступне лише кінцеве число відліків (N). Цю дилему можна вирішити, якщо в думках розмістити нескінченне число однакових груп відліків до і після оброблюваної групи, утворюючи, таким чином, математичну періодичність (але не реальну), як показано на рис.2.
Фундаментальне рівняння для отримання N-точкового ДПФ виглядає таким чином:
По відношенню до цього рівняння потрібно зробити деякі термінологічні роз'яснення (також див. рис.3). Х(k) (прописна буква Х) представляє собою частотний вихід ДПФ в k-ой точці спектра, де k знаходиться в діапазоні від 0 до N-1. N представляє собою число відліків при обчисленні ДПФ.
Зверніть увагу, що "N" не треба плутати з роздільною здатністю АЦП або ЦАП, яка вподальшому також позначається буквою N.
Значення х(n) представляє собою n-й відлік в часовій області, де n також знаходиться в діапазоні від 0 до N-1. В загальному рівнянні х(n) може бути дійсним або комплексним.
Зверніть увагу, що косинусоїдальні і синусоїдальні компоненти в рівнянні можуть бути виражені в полярних або прямокутних координатах, зв'язок між якими визначається формулою Ейлера:
Вихідний спектр ДПФ Х(k) є результатом обчислення згортки між вибіркою, що складається з вхідних відліків в часовій області, і набором з N пар гармонійних базисних функцій (косинус і синус). Концепцію добре ілюструє рис.4, на якому представлена дійсна частина перших чотирьох точок спектра (показані тільки косинусоїдальні гармонійні базисні функції). Подібна ж процедура використовується для обчислення уявної частини спектра на основі синусоїдальних функцій.
Перша точка Х(0) є простою сумою вхідних відліків в часовій області, тому що cos(0) = 1. Коефіцієнт масштабування 1/N не враховується, але повинен бути присутнім в кінцевому результаті. Зверніть увагу, що Х(0) - це середнє значення відліків в часовій області, або просто зсув по постійному струму. Друга точка ReX(1) отримана множенням кожного відліку з часової області на відповідне значення косинусоіди, що має один повний період на інтервалі N, з подальшим підсумовуванням результатів. Третя точка ReX(2) отримана множенням кожного відліку з часової області на відповідну точку косинусоїди, яка має два повні періоди на інтервалі N, з подальшим підсумовуванням результатів. Так само, четверта точка ReX(3) отримана множенням кожного відліку з часової області на відповідну точку косинусоїди з трьома повними періодами на інтервалі N і підсумовуванням результатів. Цей процес продовжується, поки не будуть обчислені всі N вихідних відліків. Подібна процедура, але з використанням синусоїд, застосовується для обчислення уявної частини частотного спектра. Косинусоїди і синусоїди є базисними функціями даного перетворення.
ДИСКРЕТНЕ ПЕРЕТВОРЕННЯ ФУРЬЕ (ДПФ)
Періодичний сигнал може бути розкладений на суму вибраних належним чином косинусоїдальних і синусоїдальних функцій (Жан Батист Жозеф Фурье, 1807)
ДПФ працює з кінцевим числом (N) оцифрованих за часом відліків х(n).
Коли ці групи відліків повторюються, вони стають періодичними з точки зору перетворення
Комплексний спектральний вихід ДПФ Х(k) є результатом згортки вхідних відліків з базисними функціями синуса і косинуса:
Рис. 3
ЗГОРТКА ВІДЛІКІВ В ЧАСОВІЙ ОБЛАСТІ З БАЗИСНИМИ ФУНКЦІЯМИ ПРИ ДПФ ДЛЯ N=8
EMBED PBrush
Рис. 4
Припустимо, що вхідний сигнал є косинусоїдальним, і має період N, тобто він містить один повний період в нашій вибірці. Також приймемо його амплітуду і фазу ідентичними першій косинусоїдальній базисній функції cos(2рn/8). Вихідний спектр містить одну ненульову точку ReX(1), а всі інші точки ReX(k) є нульовими. Припустимо, що тепер вхідна косинусоїда зсунута вправо на 90 градусів. Значення згортки між нею і відповідною базисною косинусоїдальною функцією дорівнює нулю. Але алгоритм перетворення передбачає обчислення згортки з базисною функцією sin(2рn/8), необхідне для отримання ImX(1). Це показує, чому необхідно розраховувати як дійсні, так і уявні частини спектра для визначення і амплітуди і фази частотного спектра.
Зверніть увагу, що згортка синусоїдальної/косинусоїдальної функції будь-якої частоти, відмінної від частоти базової функції, дає нульове значення і для ReX(1), і для ImX(1).
Подібна процедура застосовується при обчисленні зворотнього ДПФ для відновлення відліків в часовій області х(n) з відліків в частотній області Х(k). Відповідне рівняння виглядає таким чином:
Існує два основні типи ДПФ: дійсне ДПФ і комплексне ДПФ. Рівняння, представлені на рис..5, описують комплексне ДПФ, де і вхідні, і вихідні величини є комплексними числами. Оскільки вхідні відліки в часовій області є дійсними і не мають уявної частини, уявна частина вхідних відліків завжди приймається рівною нулю. Вихід ДПФ Х(k) містить дійсну та уявну компоненти, які можуть бути перетворені в амплітуду і фазу.
Дійсне ДПФ виглядає дещо простіше і, в основному, є спрощенням комплексного ДПФ. Більшість алгоритмів обчислення швидкого перетворення Фурье (ШПФ) складена з використанням формату комплексного ДПФ, тому важливо розуміти, як працює комплексне ДПФ і як воно співвідноситься з дійсним ДПФ. Зокрема, якщо відомі вихідні частоти дійсного ДПФ і вимагається використовувати зворотне комплексне ДПФ для обчислення відліків в часовій області, треба знати, як розмістити вихідні точки дійсного ДПФ у форматі комплексного ДПФ перед виконанням зворотного комплексного ДПФ.
На рис. 6 показані вхідні дані і результати обчислень дійсного та комплексного ШПФ (FFT). Зверніть увагу, що результат обчислення дійсного ДПФ дає дійсне та уявне значення Х(k), де k знаходиться в діапазоні від 0 до N/2. При цьому уявні точки ImX(0) і ImX(N/2) завжди рівні 0, тому що рівні 0 sin(0) і sin(nр).
Результат обчислень в частотній області Х(N/2) відповідає частотному діапазону, рівному половині частоти дискретизації fs/N. Ширина кожного елемента розділу по частоті рівна fs /N.

EMBED PBrush
КОМПЛЕКСНЕ ДИСКРЕТНЕ ПЕРЕТВОРЕННЯ ФУРЬЕ (ДПФ)
Рис. 5
ВХІДНІ/ВИХІДНІ ДАНІ ДПФ
EMBED PBrush
Рис. 6
Комплексне ДПФ має дійсні та уявні значення і на вході, і на виході. Практично, уявні частини відліків в часовій області встановлюються в нуль. При розгляді спектра, одержуваного унаслідок обчислення комплексного ДПФ, корисно знати, як пов'язати його з результатом обчислення дійсного ДПФ і навпаки. Заштриховані області в діаграмі відповідають точкам, які є загальних і для дійсного , і для комплексного ДПФ.
Рис. 7 розкриває відношення між дійсним і комплексним ДПФ більш детально. Вихідні точки дійсного ДПФ розташовуються в діапазоні від 0 до N/2, причому значення ImX(N/2) і ImX(0) завжди рівні 0. Точки між N/2 і N - 1 містять негативні частоти в комплексному ДПФ. Зверніть увагу, що ReX(N/2+1) має таке ж значення, як і ReX(N/2-1). Так само, ReX(N/2 + 2) має таке ж значення, як і ReX(N/2-2) і т.д. Видно, також, що ImX(N/2+1) рівно ImX(N/2-1), але узято із знаком мінус, і ImX(N/2+2) рівно ImX(N/2 - 2), але узято із знаком мінус і т.д. Іншими словами, ReX(k) має парну симетрію щодо N/2, а ImX(k) має непарну симетрію щодо N/2. Таким чином, на основі дійсних компонентів ДПФ можуть бути згенеровані негативні частотні компоненти комплексного БПФ.
Рівняння для комплексного і дійсного ДПФ приводяться на рис. 8. Видно, що рівняння для комплексного ДПФ працюють майже однаково, будь то процедура обчислення ДПФ Х(k) або зворотнього ДПФ х(n). Дійсне ДПФ не використовує комплексні числа, і рівняння для Х і х(k) істотно розрізняються. Також перед використанням рівняння для обчислення відліків в часовій області х(n), значення ReX і ReX(0) повинен бути поділені на два. Ці подробиці пояснюються в главі 31 книги, приведеної в списку літератури під номером 1, і читач може вивчити даний матеріал перед тим, як використовувати ці рівняння.
ВІДТВОРЕННЯ КОМПОНЕНТ ВІД'ЕМНОЇ ЧАСТОТИ КОМПЛЕКСНОГО ДПФ ПО ДІЙСНОМУ ДПФ
EMBED PBrush
Рис. 7
Вихідний спектр ДПФ може бути представлений або в полярній системі координат (амплітудою і фазою), або в алгебраїчній формі (дійсною і уявною частинами), як показано на рис.9. Обидві указані форми знаходяться у взаємно однозначній відповідності.
РІВНЯННЯ КОМПЛЕКСНОГО І ДІЙСНОГО ДПФ
EMBED PBrush
Рис. 8





ПЕРЕТВОРЕННЯ ДІЙСНИХ ТА УЯВНИХ КОМПОНЕНТ ДПФ В АМПЛІТУДУ ( MAG ) І ФАЗУ ( ? )
EMBED PBrush
Рис. 9







HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Швидке перетворення Фурье
Для розуміння принципів роботи ШПФ, розглянемо ДПФ на 8 точок, представлене на рис.10 в розгорненому вигляді. Зверніть увагу, що для спрощення таблиці ми вводимо наступне визначення:

Це веде до визначення коефіцієнтів повороту (повертаючих множників):

Коефіцієнти повороту представляють базисні гармонійні функції, записані в експоненціальній формі. Зверніть увагу, що 8-точкове ДПФ, представлене на діаграмі, вимагає 64 операцій множення з комплексними числами. N-точкове ДПФ вимагає N2 операцій множення з комплексними числами. Знання кількості множень важливе тому, що на реалізацію операцій множення затрачуються істотні обчислювальні ресурси DSP. Насправді, загальний час, що вимагається для обчислення ДПФ, прямо пропорційний кількості множень з урахуванням необхідного числа додаткових операцій.
8-точкове ДПФ (N = 8)
EMBED PBrush
Рис. 10
Швидке перетворення Фурье (ШПФ) є не більше ніж алгоритмом для прискореного обчислення ДПФ шляхом скорочення необхідного числа операцій множення і додавання. Дане перетворення було запропоновано Кулі і Таки (J.W. Cooley і J.W. Tukey) в 1960-х роках і фактично було відкриттям заново ідеї Рунге, Даніельсона і Ланкоса (Runge, Danielson і Lanczos (1903). Перше згадування даної ідеї зустрічається ще задовго до появи комп'ютерів і калькуляторів, коли чисельні обчислення могли займати багато годин. Крім того, більш ніж століттям раніше даний метод використовував німецького математика Карл Фрідріх Гаус (1777 - 1855).
Для розуміння основних концепцій ШПФ і його походження, корисно звернути увагу, що ДПФ, показане на рис.10 в розгорненому вигляді, може бути сильно спрощеним, якщо використовувати властивості симетрії і періодичності коефіцієнтів повороту, як показаним на рис.11. Результатом переробки виразів для ДПФ є швидке перетворення Фурье (FFT), яке вимагає тільки (N/2)log2(N) множень комплексних чисел. Обчислювальна ефективність ШПФ в порівнянні з ДПФ стає дуже істотною, коли кількість точок ШПФ збільшується до декількох тисяч, як це витікає з рис.12. Очевидно, що ШПФ обчислює всі компоненти вихідного спектра (або все, або жодного!). Якщо необхідно розрахувати тільки декілька точок спектра, ДПФ може виявитися більш ефективним. Обчислення одного вихідного відліку спектра з використанням ДПФ вимагає тільки N множень з комплексними числами.
ВЛАСТИВОСТІ СИМЕТРІЇ І ПЕРІОДИЧНОСТІ ПОВЕРТАЮЧИХ МНОЖНИКІВ WN r
EMBED PBrush
Рис. 11
ШВИДКЕ ПЕРЕТВОРЕННЯ ФУРЬЕ (ШПФ) В ПОРІВНЯННІ З ДИСКРЕТНИМ ПЕРЕТВОРЕННЯМ ФУРЬЕ (ДПФ)
EMBED PBrush
Рис. 12
Алгоритм ШПФ по основі 2 розділяє повне обчислення ДПФ на комбінацію 2-точкових ДПФ. Кожне 2-точкове ДПФ містить базову операцію множення з накопиченням, звану метеликом і ілюстровану на рис.13. На діаграмі показані два представлення метелика: верхня діаграма фактично є функціональним представленням метелика, побудованим на цифрових перемножувачах і суматорах. В спрощеній нижній діаграмі операції множення позначаються множником біля стрілки, а під підсумовуванням маються на увазі дві стрілки, що сходяться в точці.
8-точкове ШПФ з проріджуванням в часі (decimation-in-time, DIT) обчисляє остаточний результат з використанням трьох каскадів, як це витікає з рис.14. Вісім вхідних відліків з часової області спочатку розділяються (або проріджуються) на чотири групи 2-точкових ДПФ. Потім чотири 2-точкових ДПФ об'єднуються до двох 4-точкових ДПФ. Потім два 4-точкових ДПФ об'єднуються для того, щоб отримати остаточний результат Х(k). Докладно процес розглянутий на рис.15, де показані всі операції множення і підсумовування. Неважко помітити, що базова операція метелика 2-точкового ДПФ формує основу для всього обчислення. Обчислення здійснюється в трьох каскадах. Після того, як закінчується обчислення першого каскаду, немає необхідності зберігати які-небудь попередні результати. Результати обчислення першого каскаду можуть бути збережені в тих же самих регістрах або елементах пам'яті, які спочатку зберігали початкові відліки з часової області х(n). Так само, коли закінчується обчислення другого каскаду, результати обчислення першого каскаду можуть бути вилучені. Таким же чином здійснюється обчислення останнього каскаду, замінюючи в пам'яті проміжний результат обчислення попереднього каскаду. Зверніть увагу, що для того, щоб алгоритм працював належним чином, вхідні відліки за часом х(n) повинні бути впорядковані певним чином з використанням алгоритму реверсування бітів.

БАЗОВА ОПЕРАЦІЯ МЕТЕЛИК В АЛГОРИТМІ ШПФ З ПРОРІДЖУВАННЯМ ЗА ЧАСОМ
EMBED PBrush
Рис. 13
ОБЧИСЛЕННЯ 8-ТОЧКОВОГО ДПФ В ТРЬОХ КАСКАДАХ З ВИКОРИСТАННЯМ ПРОРІДЖУВАННЯ ЗА ЧАСОМ
EMBED PBrush
Рис. 14

АЛГОРИТМ 8-ТОЧКОВОГО ШПФ З ПРОРІДЖУВАННЯМ ЗА ЧАСОМ
EMBED PBrush
Рис. 15
Алгоритм реверсування бітів, використовуваний для реалізації проріджування за часом, представлений на рис.16. Десятковий індекс n перетвориться у його двійковий еквівалент. Потім двійкові розряди розташовуються в зворотному порядку і перетворяться назад в десяткове число. Реверсування бітів часто виконують апаратурою ЦОС в генераторі адреси даних (DAG), спрощуючи таким чином програмне забезпечення, скорочуючи кількість додаткових операцій і прискорюючи обчислення.
На рис.17 і 18 представлено обчислення ШПФ з використанням алгоритму з проріджуванням по частоті (DIF). Цей метод вимагає, щоб алгоритм реверсування був застосований до адрес вихідних відліків Х(k). Зверніть увагу, що метелик для алгоритму з проріджуванням по частоті (DIF) злегка відрізняється від метелика для алгоритму з проріджуванням по часу, як це показано на рис.19.
Використання алгоритмів з проріджуванням по часу, в порівнянні з алгоритмами з проріджуванням по частоті, в значній мірі є питанням переваги, оскільки обидва алгоритми дають однаковий результат. Певні обмеження тієї або іншої системи можуть зробити одне з двох рішень оптимальним.
Необхідно відзначити, що алгоритми, що вимагаються для обчислення зворотного ШПФ, майже ідентичні тим, які необхідні для обчислення прямого ШПФ, якщо взяти до уваги, що йдеться про використання комплексного ШПФ. Насправді, корисний метод перевірки алгоритму комплексного ШПФ полягає в здійсненні ШПФ з відліками в часовійобласті х(n), а потім - в обчисленні зворотного ШПФ з відліками з частотної області Х(k). В кінці цього процесу повинен бути отримані первинні відліки з часової області Re х(n), а уявна частина Im х(n) повинна бути нульовою (в межах помилки математичного заокруглення).
EMBED PBrush
ПРИКЛАД БІТ-РЕВЕРСИВНОГО ПРОРІДЖУВАННЯ ДЛЯ N = 8
Рис. 16

ОБЧИСЛЕННЯ 8-ТОЧКОВОГО ДПФ В ТРЬОХ ЕТАПАХ, АЛГОРИТМ З ПРОРІДЖУВАННЯМ ПО ЧАСТОТІ
EMBED PBrush
Рис. 17
EMBED PBrush
АЛГОРИТМ 8-ТОЧКОВОГО ШПФ З ПРОРІДЖУВАННЯМ ПО ЧАСТОТІ
Рис. 18
БАЗОВА ОПЕРАЦІЯ МЕТЕЛИК В АЛГОРИТМІ ШПФ З ПРОРІДЖУВАННЯМ ПО ЧАСТОТІ
EMBED PBrush
Рис. 19
ШПФ,що обговорювалися до цих пір, представляють алгоритм ШПФ по основі 2, тобто їх обчислення засновано на 2-точкових базових операціях типу метелик. Мається на увазі, що число точок в ШПФ повинен бути ступінь числа 2. Якщо число точок в ШПФ є ступенем числа 4, тоШПФ може бути розділено на множину 4-точкових ДПФ, показану на рис.20. Таке перетворення називається алгоритмом ШПФ по основі 4. Базова операція метелик ШПФ по основі 4 з проріджуванням по частоті представлена на рис.21.
Алгоритм ШПФ по основі 4 вимагає меншої кількості множень з комплексними числами, але більшої кількості операцій сумовування, чим ШПФ по основі 2 для такої ж кількості точок. В порівнянні з алгоритмом ШПФ по основі 2, алгоритм по основі 4 використовує більш складну адресацію і додаткові коефіцієнти повороту, але меншу кількість обчислень. Остаточна економія часу обчислення розрізняється для різних DSP, але алгоритм ШПФ по основі 4 може бути больш ніж вдвічи швидким, ніж алгоритм по основі 2 для DSP з оптимальною архітектурою.

ТРЬОХКАСКАДНЕ ОБЧИСЛЕННЯ 16-точкового ДПФ НА ОСНОВІ АЛГОРИТМУ З ПРОРІДЖУВАННЯМ ЗА ЧАСОМ ПО ОСНОВІ 4
EMBED PBrush

Рис. 20
"МЕТЕЛИК" АЛГОРИТМУ ШПФ ПО ОСНОВІ 4 З ПРОРІДЖУВАННЯМ ЗА ЧАСОМ
EMBED PBrush
Рис. 21








HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Апаратна реалізація і час виконання алгоритмів ШПФ
В загальному випадку, вимоги по використовуваній пам'яті для N-точкового БПФ наступні: N комірок для дійсних даних, N комірок для уявних даних і N комірок для синусоїдальних базисних функцій (іноді згадуваних, як коефіцієнти повороту). Додаткові елементи пам'яті будуть бути потрібними у разі використання зважування з використанням віконних функцій (windowing). Якщо ухвалені вимоги по пам'яті задоволені, DSP повинен виконати необхідні обчислення за необхідний час. Багато виробників DSP або проводять тест продуктивності для указаного розміру ШПФ, або визначають час обчислення для базової операції "метелик". При порівнянні характеристик ШПФ важливо упевнитися, що у всіх випадках використовується однаковий тип ШПФ. Наприклад, тест 1024-точкового ШПФ на одному DSP, отримане за допомогою алгоритму ШПФ по основі 2, не повинен порівнюватися з тестом алгоритму ШПФ по основі 4 для іншого DSP.
Інше міркування щодо ШПФ полягає у виборі процесора з фіксованою або з плаваючою крапкою. Значення, що відповідають результатам обчислення метелика, можуть бути більше, ніж початкові дані при обчисленні метелика. Це збільшення оброблюваних числових значень може створювати потенційну проблему в DSP з фіксованим числом розрядів. Для запобігання переповнюванню, дані потрібно масштабувати, зазделегідь залишаючи достатню кількість додаткових розрядів для збільшення значень оброблюваних даних. Альтернативний метод полягає в тому, що дані можуть масштабуватися після кожного каскаду обчислення ШПФ. Методика масштабування даних після кожного проходу ШПФ відома як блокова плаваюча крапка (block floating point). Він називається так, тому що повний масив даних масштабується як єдине ціле, незалежно від того, чи дійсно кожний елемент в блоці вимагає масштабування. Блок масштабується так, щоб відносні співвідношення між даними залишилися колишніми. Наприклад, якщо кожне слово даних зсунуто вправо на один розряд (поділено на 2), абсолютні значення змінюються, але щодо один одного співвідношення даних залишаються колишніми.
В 16-розрядному DSP-процесорі з фіксованою крапкою після множення формується 32-розрядне слово. Сімейство цифрових сигнальних процесорів Analog Devices ADSP21xx характеризується розширеним динамічним діапазоном, який реалізується в операціях множення з накопиченням за допомогою 40-розрядного внутрішнього регістра акумулятора.
Використання DSP-процесора з плаваючою крапкою усуває потребу в масштабуванні даних і тому призводить до більш простої реалізації алгоритму ШПФ, але наслідком цього спрощення є збільшення часу обробки, який потрібен для складних арифметичних обчислень з плаваючою крапкою. Крім того, 32-розрядний DSP-процесор з плаваючою крапкою, очевидно, буде мати менший рівень шумів округлення, ніж 16-розрядний DSP-процесор з фіксованою крапкою. На рис.5.22 приведені дані по реалізації ШПФ для популярних DSP-процесорів Analog Devices. Зокрема, що DSP-процесор ADSP-TS001 TigerSHARC пропонує обидва режими: і з плаваючою, і з фіксованою крапкою, забезпечуючи, таким чином, виняткову гнучкість програмування.

РЕЗУЛЬТАТИ ПОРІВНЯННЯ РЕАЛІЗАЦІЇ АЛГОРИТМІВ ШПФ ПО ОСНОВІ 2 НА РІЗНИХ ПРОЦЕСОРАХ
EMBED PBrush
Рис. 22







HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Реалізація алгоритмів ШПФ в реальному масштабі часу
Вимоги до DSP для реалізації алгоритмів ШПФ в реальному масштабі часу.
Існує два основні способи обробки сигналів в реальному масштабі часу: обробка одного відліку в кожний моменту часу (безперервна обробка) і обробка одного пакету даних в кожний моменту часу (пакетна обробка). Системи, засновані на безперервній обробці, такі як цифровий фільтр, одержують дані у вигляді одного відліку в кожний моменту часу. В кожному такті новий відлік поступає до системи, а оброблений відлік передається на вихід. Системи, засновані на пакетній обробці, такі як побудований на ШПФ цифровий аналізатор спектра, одержують дані у вигляді цілого пакету відліків. Відбувається обробка всього пакету початкових даних, результатом якої є пакет перетворених вихідних даних.
Для забезпечення функціонування в реальному масштабі часу повний розрахунок ШПФ повинен виконуватися в проміжку, що відповідає часу накопичення одного пакету даних. Передбачається, що, поки проводиться обчислення ШПФ поточного пакету даних, DSP-процесор накопичує дані для наступного пакету. Накопичення даних є однією з сфер, де важливу роль грають спеціальні архітектурні особливості DSP. Безперервне отримання даних полегшується, завдяки можливостям гнучкої адресації даних в DSP в поєднанні з використанням різних каналів прямого доступу до пам'яті (DMA).
Розглянемо DSP процесор ADSP-TS001 TigerSHARC, який обчисляє 1024-точкове 32-розрядне комплексне БПФ з плаваючою точкою за 69 мкс. Очевидно, що максимальна частота дискретизації рівна 1024/69 мкс = 14,8 MSPS. Це означає, що сигнал має ширину смуги частот меншу, ніж 7,4 МГц. Також передбачається, що немає додаткових витрат процесорного часу, пов'язаних з БПФ, або обмежень, пов'язаних з передачею даних.
ПРИКЛАД ОБЧИСЛЕННЯ ШПФ В РЕАЛЬНОМУ МАСШТАБІ ЧАСУ

Рис. 23
Наведений приклад дає оцінку максимальної ширини смуги сигналу, який може бути оброблений даним DSP-процесором з урахуванням характеристик реалізованого на ньому ШПФ. Інший підхід полягає в тому, щоб, задаючись шириною смуги сигналу, розробити вимоги до DSP для обробки сигналу в даній смузі. Якщо ширина смуги частот сигналу відома, необхідна частота дискретизації може бути визначеною шляхом її множення на коефіцієнт 2 - 2,5 (збільшення частоти дискретизації може бути потрібним для ослаблення вимог до попереднього АЦП ФНЧ , що знімає ефект накладення спектра, (antialiasing filter)). Наступним кроком визначається число точок ШПФ, що вимагається для досягнення бажаної дозволяючої здатності по частоті. Роздільна здатність по частоті виходить діленням швидкості дискретизації fs на число точок ШПФ N. Ці і інші міркування з приводу ШПФ представлені на рис.24.
РЕАЛІЗАЦІЯ ШПФ В РЕАЛЬНОМУ МАСШТАБІ ЧАСУ
Рис. 24
Число точок ШПФ також визначає мінімальний рівень шуму ШПФ щодо рівня широкосмугового шуму, і це також повинен бути враховано при виборі числа точок ШПФ. На рис.25 представлені співвідношення між рівнем сигналу, що відповідає повному динамічному діапазону системи, рівнем широкосмугового шуму (що вимірює в ширині смуги від 0 до fs/2) і мінімальним рівнем шуму ШПФ. Зверніть увагу, що виграш відносно сигнал/шум ШПФ визначається числом точок ШПФ. ШПФ діє подібно аналоговому аналізатору спектра з шириною смуги розгортки fs N. Збільшення числа точок підвищує роздільну здатність ШПФ і звужує смугу частот, що пропускаються їм, скорочуючи, таким чином, мінімальний рівень шуму. В цьому аналізі ми нехтували шумом, викликаним помилкою округлення при реалізації ШПФ. На практиці АЦП, який використовується для оцифровки сигналу, виробляє шум квантування, який є домінуючим шумовим джерелом в системі.
Тепер прийшов час досліджувати характеристики реально існуючих DSP-процесорів і час реалізації ШПФ на цих процесорах, щоб уявити собі, при яких умовах ми можемо здійснювати обробку сигналів в реальному масштабі часу. Це означає, що ШПФ повинен бути розраховано протягом часу накопичення пакету даних, рівного N/fs. Інші міркування, такі як використання процесора з фіксованою крапкою порівняно з процесором з плаваючою крапкою, використання алгоритму по основі 2 порівняно з алгоритмом по основі 4, споживана процесором потужність і вартісні показники, можуть також бути предметом розгляду.
ВИГРАШ ВІДНОСНО СИГНАЛ/ШУМ ПРИ ШПФ БЕЗ УРАХУВАННЯ ПОМИЛКИ ЗАОКРУГЛЕННЯ

Рис. 25




HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Розширення спектра сигналу і зважування з використанням віконної функції
Розширення спектра аналізованого сигналу при обчисленні ШПФ може бути краще всього проілюстровано на виконанні N-точкового ШПФ з синусоїдальним вхідним сигналом. Буде розглянуто дві ситуації. В першому випадку співвідношення між частотою дискретизації і частотою вхідного синусоїдального сигналу таке, що у вибірці міститься в точності ціле число періодів синусоїдального сигналу. Нагадаємо, що обчислення ДПФ передбачає, що вибірка повторюється нескінченне число разів до і після досліджуваного фрагмента сигналу, формуючи в такий спосіб нескінченний безперервний періодичний сигнал, як показано на рис.26. За таких умов форма вхідного сигналу представляє собою безперервну синусоїдальну функцію, і на виході ДПФ або ШПФ буде один ненульовий частотний відлік, що відповідає частоті вхідного сигналу.
ШПФ СИНУСОЇДАЛЬНОГО СИГНАЛУ З ЦІЛИМ ЧИСЛОМ ПЕРІОДІВ У ВИБІРЦІ


Рис. 26
Рис. 27 відображує ситуацію, коли у вибірці немає цілого числа періодів синусоїдального сигналу. Розриви, які утворюються в кінцевих точках вибірки, призводять до розширення спектра аналізованого сигналу внаслідок появи додаткових гармонік. На додаток до появи бічних пелюсток, відбувається розширення основної пелюстки, що призводить до зниження дозволяючої здатності по частоті. Цей процес еквівалентний перемножуванню вхідного синусоїдального сигналу з прямокутним імпульсом, який має відому частотну характеристику sin /х(х)і пов'язані з цим широка основна пелюстка і бічні пелюстки.
ШПФ СИНУСОЇДАЛЬНОГО СИГНАЛУ З НЕЦІЛИМ ЧИСЛОМ ПЕРІОДІВ У ВИБІРЦІ

Рис. 27
Зверніть увагу, що перша бічна пелюстка тільки на 12 дБ нижче за головну, і що бічні пелюстки мають спад тільки 6 дБ/октаву. Така ситуація неприйнятна для більшості задач аналізу спектра. Оскільки в практичних додатках ШПФ для спектрального аналізу точні вхідні частоти невідомі, потрібно зробити певні кроки до зменшення бічних пелюсток. Воно досягається вибором віконної функції з більш складною формою, чим прямокутна. Вхідні відліки за часом множаться на відповідну функцію вікна, що спричиняє за собою обнулення сигналу на краях вибірки, як показано на рис.28. Вибір функції вікна є, перш за все, компромісом між збільшенням ширини основної пелюстки і розміром бічних пелюсток.
Математичні функції, що описують чотири популярні віконні функції (Хеммінга, Блекмана, Хеннінга і мінімальна 4-елементна Блекмана-Харріса), представлені на рис.29. Оцифровані віконні функції зазвичай обчисляються заздалегідь і зберігаються в пам'яті DSP з метою мінімізації обчислень безпосередньо при реалізації ШПФ. Частотні характеристики прямокутного вікна, вікон Хеммінга і Блекмана представлені на рис.30. Рис.31 ілюструє компроміс між збільшенням ширини основної пелюстки, амплітудою першої бічної пелюстки і спадом рівня бічних пелюсток для популярних функцій вікна.
ЗВАЖУВАННЯ З ВИКОРИСТАННЯМ ФУНКЦІЇ ВІКНА ДЛЯ ЗМЕНШЕННЯ ЕФЕКТУ РОЗШИРЕННЯ СПЕКТРА

Рис. 28
ДЕЯКІ ПОШИРЕНІ ФУНКЦІЇ ВІКНА

Рис. 29
ЧАСТОТНА ХАРАКТЕРИСТИКА ПРЯМОКУТНОГО ВІКНА, ВІКОН ХЕММІНГА І БЛЕКМАНА ДЛЯ N = 256

Рис. 30


ПОШИРЕНІ ВІКНА І ЇХ ХАРАКТЕРИСТИКИ

Рис. 31




HYPERLINK \l "_top"Зміст ? HYPERLINK \l "_Цифрове_оброблення_сигналів" Цифрове оброблення сигналів ? HYPERLINK \l "_Дискретне_перетворення__1"ДПФ ? HYPERLINK \l "_Швидке_перетворення_Фурье_1"ШПФ ? HYPERLINK \l "_Апаратна_реалізація__1" Апаратна реалізація і час виконання алгоритмів ШПФ ? HYPERLINK \l "_Реалізація__алгоритмів_1" Реалізація алгоритмів ШПФ в реальному масштабі часу ? HYPERLINK \l "_Розширення_спектра_сигналу_1" Розширення спектра сигналу і зважування з використанням віконної функції ? HYPERLINK \l "_Методи_зменшення_часової" Методи зменшення часової складності
Методи зменшення часової складності
При конструюванні комп'ютерних засобів однією з найбільш важливих задач є побудова ефективного алгоритму перетворення, зберігання та передачі даних. Ефективність алгоритму оцінюється за такими характеристиками складності:
часова складність
програмна складність
ємкістна складність
структупна складність
апаратна складність
В залежності від конкретних вимог, які висуваються до комп'ютерної системи чи пристрою, та чи інша характеристика може набувати більшої або меншої ваги. Найчастіше саме значення часової складністі стає вирішальним при виборі більш ефективного алгоритму.
Швидке перетворення Фурье є алгоритмом для прискореного обчислення ДПФ шляхом скорочення необхідного числа операцій множення і додавання. Асимптотична часова складність ДПФ EMBED Equation.3 , ШПФ EMBED Equation.3 . Але програмна складність суттєво більша у алгоритму ШПФ.
При реалізації алгоритму FFT на компьютері використовуються наступні методи зменшення часової складності:
еквівалентні перетворення
Цей спосіб передбачає зменшення часової складності переходом від однієї форми представлення алгоритму до іншої змінюючи лише правило безпосереднього перероблення, залишаючи всі інші параметри без змін.
«Еквівалентні перетворення», які використані у виводі формул ШПФ
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Об’єктом еквівалентних перетворень є вираз: EMBED Equation.3 у проміжному виразі (1).
Перетворення приведені у послідовності операцій (2). Кінцевий результат вираз (3)
Використавши ряд Тейлора
f(x) = EMBED Equation.3
представимо
EMBED Equation.3 = 1 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 + . . . + EMBED Equation.3 + . . .
EMBED Equation.3 = EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 + . . . + EMBED Equation.3 EMBED Equation.3 + . . .
EMBED Equation.3 = EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 + . . . + EMBED Equation.3 EMBED Equation.3 + . . .
EMBED Equation.3 = 1 + EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 EMBED Equation.3 + EMBED Equation.3 + EMBED Equation.3 EMBED Equation.3 - EMBED Equation.3 + EMBED Equation.3 EMBED Equation.3 + EMBED Equation.3 + . . .
EMBED Equation.3 = EMBED Equation.3 + EMBED Equation.3 EMBED Equation.3
________________________________
попередні обчислення
Значення повертаючих множників EMBED Equation.3 можуть бути підраховані заздалегідь і зберігатись у вігляді таблиці. Доступ до табличних значень виконується дуже швидко.
апросикмація
Апроксимація (наближення) – заміна одного математичного об’єкту іншим з метою спрощення обчислень. Об’єктом апроксимації частіше за все є одномісні функції з операціями ділення, піднесення до степені, логарифмування. Інструментом апроксимації, як правило, є степеневі ряди. Часова складність обчислення їх звичайно менша складності первинної функції
розбиття вхідних даних
X(k) = Re(X) +jIm(X)
Варіант розбиття вхідних даних проілюстровано на рис.15
розбиття вихідних даних (проміжних результатів)
В формулі (1) відліки k діляться на парні 2k і непарні 2k+1. Для парних маємо (2) EMBED Equation.3
EMBED Equation.3
Еквівалентними перетвореннями отримуємо вираз (3) Для X(2k+1) робимо те саме.
EMBED Equation.3
EMBED Equation.3
Варіант розбиття вхідних даних проілюстровано на рис.14
розбиття задачі на підзадачі
Прикладом розбиття задачі на підзадачі може бути вирішення задачі розділення сигналу і завади за допомогою кепстрального аналізу.
EMBED Equation.3 >ШПФ> фільтр > EMBED Equation.3 >ЗШПФ> EMBED Equation.3 .
Сам алгоритм ШПФ також можно розбити на підзадачі:
визначення повертаючих множників W
біт-інверсні перетворення при виборі вхідних даних(результатів) чи повертаючих множників
визначення "метелика" ШПФ
об'эднання 2-точкових ШПФ в 4-точкові


ЛІТЕРАТУРА
Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, Second Edition, 1999, California Technical Publishing Р.О. Box 502407, San Diego, CA 92150. Also available for free download at: HYPERLINK "http://www.dspguide.com/" http://www.dspguide.com/or HYPERLINK "http://www.analog.com/" http://www.analog.com/
С. Britton Rorabaugh, DSP Primer, McGraw-Hill, 1999.
Richard J. Higgins, Digital Signal Processing in VLSI, Prentice-Hall 1990.
А. V. Oppenheim and R. W. Schafer, Digital Signal Processing, Prentice-Hall, 1975.
L. R. Rabiner and В.Gold, Theory and Application of Digital Signal Processing, Prentice-Hall, 1975.
John G. Proakis and Dimitris G. Manolakis, Introduction to Digital Signal Processing, MacMillian, 1988.
Fredrick J. Harris, On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform, Proc. IEEE, Vol. 66, No. 1, 1978 pp. 51-83.
R. W. Ramirez, The FFT: Fundamentals and Concepts Prentice-Hall, 1985.
J. W. Cooley and J. W. Tukey, An Algorithm for the Machine Computation of Complex Fourier Series, Mathematics Computation, Vol. 19 pp. 297-301, April 1965.
Digital Signal Processing Applications Using the ADSP-2100 Family, Vol. 1 and Vol. 2, Analog Devices, Free Download at: HYPERLINK "http://www.analog.com/" http://www.analog.com/
ADSP-21000 Family Application Handbook, Vol. 1, Analog Devices Free Download at: HYPERLINK "http://www.analog.com/" http://www.analog.com/