"justify"> Для здійснення процесу фільтрації цифрового сигналу по одному з алгоритмів швидкою лінійною згортки необхідно виконати наступні етапи:
) виконати швидке перетворення Фур'є (ШПФ) над комплексними отсчетами x (n) і отримати послідовність X (k). По ідеї, ШПФ необхідно виробити і над відліками імпульсної характеристики h (n), але доцільно виходити з припущення, що проектований фільтр не буде змінювати свою частотну характеристику в процесі роботи. Таким чином, можна виконати ШПФ над h (n) і внести результат H (k) на згадку проектованого фільтру
) виконати перемножування відповідних відліків X (k) і H (k), отримавши нову послідовність Y (k) = X (k). H (k)
) виконати зворотне ШПФ над Y (k).
Перш ніж приступити до оцінки кількості апаратурних ресурсів доцільно розглянути структурну схему фільтра, функціонуючого за алгоритмом швидкої згортки (БС-фільтр) двох послідовностей із застосуванням потокового швидкого перетворення Фур'є. Блок - схема БС-фільтра наведена на малюнку 2.2. <В
Малюнок 2.2 Блок-схема фільтра швидкої згортки
Доцільно зауважити, що послідовність відліків x (n) може виявитися на багато довше ніж h (n). У цьому випадку рекомендується робити секціонування лінійної згортки, тобто розбити більш довгу послідовність на секції, обчислити часткові згортки, з яких потім сформувати шукану вихідну послідовність y (n). Існує кілька методів обчислення згортки при виконанні яких кількість операцій буде приблизно однаковим, однак логічніше всього вибрати метод перекриття з накопиченням, так як він найбільше підходить для обчислення згортки із застосуванням алгоритмів потокового ШПФ і ОБПФ. p align="justify"> З метою пояснення останнього твердження розглянемо сутність методу перекриття з накопиченням. Для прикладу розглянемо послідовність HH (n) містить Nh = 256 відліків, а послідовність x (n) складається з Nх = 128 і доповнена кількістю N0 = 128 нульових відліків. Таким чином, дві наступні один за одним послідовності x (n) перекриваються один з одним на ділянках довжиною по N0 відліків. Ділянка перекриття знаходиться в кінці секції, що і є зручністю при застосуванні алгоритмів потокового ШПФ і ОБПФ. У розглянутому методі немає жодних операцій додавання відліків часткових згорток, на відміну від методу перекриття з підсумовуванням. p align="justify"> Тепер необхідно оцінити кількість операцій на всіх трьох етапах обчислення. При обчисленні ШПФ за алгоритмом з основою 2 необхідно, щоб кількість оброблюваних відліків було одно 2b, де b - ціле число і не менше, ніж N = N х + N0. Тоді ШПФ буде N = 256 - точковим. Неважко показати, що кількість обчислень базових операцій [2], необхідних для виконання будь-якого алгоритму ШПФ дорівнюватиме:
(N/2) log2N. (2.18)
Якщо врахувати, що послідовність відліків x (n) комплексна, то...
