Швидке перетворення Фур'є (ШПФ) - це складний алгоритм, і його деталі, зазвичай вивчають ті, хто займається питаннями цифрової обробки сигналів. Цей розділ описує загальні принципи роботи БПФ, заснованого на використанні комплексних чисел. Якщо ви маєте досвід роботи в комплексній математики, то легко зрозумієте істинний сенс алгоритму. Не хвилюйтеся, якщо від вас вислизнуть деякі деталі: мало вчених і інженерів, які використовують БПФ, можуть написати програму з нуля.
У частотної і тимчасової області сигнал представлений N комплексними точками. Кожна з цих точок складається з двох чисел: дійсної та уявної частини. Наприклад, коли ми говоримо про комплексне відліку X [42], мова йде про комбінації ReX [42] і ImX [42]. Після множення двох комплексних змінних, необхідно об'єднати чотири окремі компоненти в дві. Подальше обговорення теми «Як працює БПФ» використовує специфічні терміни: сигнал, точка, відлік і значення представляють собою поєднання реальної та уявної частин.
БПФ працює з розкладанням N -точковий часового проміжку сигналу на N тимчасових сигнальних проміжків, кожен з яких складався з однієї точки. Другий крок полягає в розрахунку N частотних спектрів, відповідного цим тимчасовим сигнальним проміжків. Після цього, на основі N спектрів синтезується єдиний частотний спектр.
Малюнок 12.2 показує приклад поділу тимчасової області з використанням ШПФ. У цьому прикладі 16-ти точковий сигнал розкладається на чотири окремі компоненти. Перший етап полягає в розбиття 16-ти точкового сигналу на два сигнали по 8 точок. На другому етапі відбувається розкладання цих сигналів на чотири сигналу по 4 точки. Дана процедура триває до тих пір, поки не буде сформовано N сигналів складаються з однієї точки. Черезстрочная розкладання використовується при поділі вибірки сигналу на дві вибірки. Сигнал розділяється як при парному, так і при непарній кількості відліків в вибірок. В системі проводиться 2 N етапів в розкладанні, тобто на 16-ти точковий сигнал (2 4) передбачає 4 етапи, 512 точки (2 7) вимагає 7 етапів, 4096 точки (2 12) передбачає 12 етапів і т.д. Запам'ятаємо, це значення - воно буде багато раз зустрічатися в цьому розділі.
Малюнок 12.2 - Процедура розбиття сигналу
Тепер, коли зрозуміла структура розкладання, її можна значно спростити. Розкладання є не більше ніж перерозподіл відліків сигналу. Це ілюструє малюнок 12.3. Зліва представлені номери відліків початкового сигналу, разом з їх двійковими еквівалентами. Справа, змінені номери, а також їх виконавчі еквіваленти. Ідея полягає в тому, що виконавчі числа є інверсією один одного. Наприклад, відлік №3 (0011) можна отримати з відліку №12 (1100). Відлік № 14 (1110) виходить з відліку № 7 (0111), і так далі. Розбиття тимчасової області в БПФ зазвичай, проводиться з використання алгоритму сортування інвертованих біт. Це передбачає зміну N тимчасових областей, з підрахунком в двійковому вигляді і перевертанням біт зліва на право (наприклад, в крайній правій колонці в Рис. 12.3).
Малюнок 12.3 - Процедура перерозподілу відліків сигналу
Наступним кроком алгоритму БПФ є знаходження частоти спектрів одноточечного сигналів, визначеного в тимчасовій області. Це робиться елементарно: спектр одноточечного сигналу дорівнює самому собі. Це означає, що на цьому етапі нічого не треба. Хоча не варто забувати, що кожен з одноточкових сигналів тепер є спектр частот, а не сигнал у часовій області
Останній крок у БПФ полягає в тому, щоб об'єднати N спектрів частот в зворотному по відношенню до тимчасового поділу порядку. У цьому випадку алгоритм не функціонує належним чином. На жаль, зворотне швидке перетворення не застосовується, а ми повинні повернутися на якомусь етапі до часу. На першому етапі, 16 одноточкових частотних спектра об'єднуються в 8 частотних спектра по 2 точки кожен. На другому етапі 8 частотних спектрів синтезується в 4 спектра, і так далі. На останньому етапі отримуємо результат БПФ у вигляді 16 точкового частотного спектра.
Малюнок 12.4 показує, як два частотних спектра, кожен з яких складався з 4 точок, об'єднані в єдиний частотний діапазон на 8 очок. Об'єднання має виключити однакові розкладання в тимчасовій області. Іншими словами, операція в частотної області повинна відповідати операції в тимчасовій області з виключенням перетинів. Розглянемо два сигнали тимчасової області. 8 точковий тимчасової сигнал формірутеся в два етапи: розведенням кожного 4-точкового сигналу нулями, для того, щоб отримати 8-ми точковий сигнал, а потім об'єднувати сигнали разом. Тому сигнал 1 перетворюється в a0b0c0d0. а 2 стане 0e0f0g0h. Підсумовування цих двох сигналів дає 8-точковий сигнал aebfcgdh. Як показано на рис. 12.4, доповнення тимчасової реалізації сигналу нулями відповідає дублювання частотного спектра. Таким чином, спектри частот в БПФ, дублюються, а потім додає один до іншого.
Малюнок 12.4 - Процедура синтезу частотного спектра сигналу
Для досягнення відповідності, двох сигналів у часовій області розбавляються нулями в трохи іншому вигляді. В одному сигналу, непарні відліки дорівнюють нулю, а в іншому сигналі парні відліки дорівнюють нулю. Іншими словами, один із сигналів тимчасової області (0e0f0g0h на рис. 12.4) зсувається вправо на один відлік. Цей зсув в тимчасовій області відповідає множення на спектр синуса. Щоб побачити це, згадаємо, що зрушення у времененной області еквівалентний згортання сигналу зі зміщеною дельта-функцією. Спектр зміщеною дельта функція є синусоїдою.
Малюнок 12.5 показує схема суміщення двох 4-х точкових спектру в один 8-ми точковий. Зауважимо, що рис. 12.5 формується за базовою схемою рис 12.6 з повторенням знову і знову.
Малюнок 12.5 - схема суміщення двох 4-х точкових спектру в один 8-ми точковий.