Мікропроцесорний локатор для сліпих

дипломная работа

1.3 Аналіз алгоритмів швидкого перетворення Фурє

Основна ідея алгоритмів швидкого перетворення Фурє комплексної послідовності (ШПФк) полягає в збалансованому рекурсивному використанні методики зведення однієї задачі більшої розмірності до задач меншої розмірності. В найпростішому випадку, коли N=2m , де m=1,2,..., N-точкове дискретне перетворення Фурє (ДПФ) зводиться до двох N/2-точкових, кожне з яких в свою чергу замінюється двома N/4-точковими і т.д. до одержання двоточкових ДПФ. На даний час розроблені різні методи побудови алгоритмів ШПФ [4]. Нижче розглянемо найвживаніші при апаратній реалізації.

Алгоритми ШПФ комплексної послідовності за основою два.

Існують два варіанти формул переходу до двох ДПФ меншої розмірності, які отримали назву формул розкладу (ФР) алгоритму ШПФ. В першому з них, що отримав назву алгоритму ШПФк за основою два з часовим прорідженням (ШПФк2t), ФР задається виразом.

X(k)=X1(k)+X2(k) , k=0,1,...,N-1, (1.15)

де X1(k)=ДПФN/2{x(n)}, X2(k)=ДПФN/2{x(2n+1)}.

В другому варіанті, що отримав назву частотного (ШПФк2f) , N-точкове ДПФ замінюється двома N/2 точковими ДПФ наступним чином:

(1.16)

де x1(n)=x(n)+x(n+N/2) , x2(n)=[x(n)-x(n+N/2)].

Обидві форми алгоритмів еквівалентні з точки зору кількості обчислень, вони відзначаються простотою структури. Обчислення за даними алгоритмами вимагає виконання m=log2 N етапів, кожен з яких має N/2 базових операцій (БО). Графи БО алгоритмів ШПФк2t і ШПФк2f наведені відповідно на рис.1.1а і 1.1б.

Рис.1.1 Базові операції алгоритмів ШПФк за основою два: а) з часовим прорідженням; б) з частотним прорідженням

Зауважимо, що в загальному випадку БО складаються з однієї операції множення і двох операцій додавання комплексних чисел, тобто вимагається чотири множення і шість додавань дійсних чисел.

Алгоритми ШПФ комплексної послідовності за основою чотири.

З точки зору кількості необхідних операцій ефективнішими є алгоритми ШПФк за основою чотири (ШПФк4), коли N - точкове ДПФ одразу за один етап розбивається на чотири N/4 - точкові.

Нехай N=4m, m=1,2,... , тоді загальна ФР алгоритму ШПФк4 з часовим прорідженням (ШПФк4t) задається виразом

(1.17)

На основі ФР (1.17) будуємо обчислювальну процедуру

(1.18)

де k=0,1,...,N/4-1; , p=0,1,2,3.

Рекурсивно продовжуючи за формулою (1.17) і процедурою (1.18) розбиття меншої розмірності до чотири-точкових, синтезуємо алгоритм ШПФк4t. Граф БО алгоритму ШПФк4t показаний на рис.1.2.

Рис.1.2 Базова операція алгоритму ШПФк4t

Як і в алгоритмі за основою два, для одержання алгоритму ШПФк4 з частотним прорідженням (ШПФк4f) достатньо розглянути граф ШПФк4t у зворотному напрямку. Граф БО алгоритму ШПФк4f показаний на рис.1.3.

Рис.1.3 Базова операція алгоритму ШПФк4f

Алгоритми ШПФк4 дозволяють на 25% скоротити обчислювальні затрати порівняно з алгоритмами ШПФк2 [4]. Подібним чином будуються алгоритми за основою 8, 16, а також алгоритми за змішаною основою 2-4, 2-4-8 і т.д. У загальному випадку збільшення основи алгоритму веде до зменшення обчислювальних витрат, але при цьому ускладнюється реалізація алгоритму.

Алгоритми ШПФ комплексної послідовності за розщепленою основою два-чотири. Важливим етапом в теорії швидких алгоритмів є розробка алгоритму ШПФк за розщепленою основою два-чотири (ШПФк2-4). В них ФР одержується комбінацією ФР алгоритмів ШПФк2 та ШПФк4 [4]. Так для алгоритму ЩПФк2-4 з часовим прорідженням (ШПФк2-4t), ФР має вигляд

(4.3)

де X(k)=ДПФN {x(n)} ; Xp(k)=ДПФN/4 {x(4n+p)}, p=1,3; X0(k)=ДПФN/2 {x(2n+1)}.

За формулою (4.3) N - точкове ДПФ розбивається на одне N/2- точкове і два N/4- точкові перетворення. На основі (4.3) використовуючи періодичність фазових множників WNr та перетворень Xp(k) будується обчислювальна процедура.

(1.19)

Рекурсивно використовуючи ФР (4.3) та процедуру (4.4) до перетворень меншої розмірності, синтезуємо алгоритм ШПФк2-4t. Граф БО алгоритму ШПФк2-4t показаний на рис.1.4.

Рис.1.4 Базова операція алгоритму ШПФк2-4t

Для отримання алгоритму ШПФк2-4 з частотним прорідженням (ШПФк2-4f) використовують ФР алгоритмів ШПФк2f і ШПФк4f. ФР для алгоритму ШПФк2-4f має вигляд

(1.20)

де x0(n)=x(n)+X(n+N/2); an=x(n)-x(n+N/2), n=0,1,...,N/2-1; x1(n)=(an -jan+N/4), x3(n)=(an+jan+N/4), n=0,1,...,N/4-1.

Процедура переходу до перетворень меншої розмірності наступна:

(1.21)

Шляхом рекурсивного продовження на основі розбиття перетворень меншої розмірності синтезується алгоритм ШПФк2-4f. Граф БО такого алгоритму наведений на рис.1.5.

Рис.1.5 Базова операція алгоритму ШПФк2-4f

Алгоритми ШПФк2-4 вдало поєднують простоту структури алгоритмів за основою два з ефективністю алгоритмів з високою основою. Зберігаючи в основному структуру алгоритмів ШПФк2, вони мають найменші обчислювальні затрати серед розглянутого класу алгоритмів.

Швидке перетворення Фурє (ШПФ) - ефективний алгоритм обчислення ДПФ.

1.4Розробка узагальненого алгоритму обробки сигналу

Узагальнений алгоритм обробки сигналу полягає в отриманні відбитого від перешкоди сигналу і порівнянні його з сигналом що генерувався. Після отримання сигналу йде його обробка і швидке перетворення Фурє. Потім за допомогою інтегралу підраховуємо площу корисного сигналу і порівнюємо її з початковим значенням сигналу. При отриманні певного допустимого значення приймаємо рішення про сигналізування про перешкоду.

Загальна блок схема алгоритму обробки сигналу наведена на рис.1.6

Рис.1.6. Загальна блок схема алгоритму функціонування пристрою

Делись добром ;)