Геометричне трактування дискретного перетворення Фур'є
Слід підкреслити, що МІП-сигнал виду (1.309) є лише однією з можливих моделей дискретного сигналу. Такі модульовані послідовності можна застосовувати для опису імпульсних коливань АІМ або ШІМ. При обробці ж радіотехнічних сигналів за допомогою обчислювальних пристроїв дискретний сигнал виступає не як послідовність імпульсів, а як упорядкована послідовність чисел. Роль часу при цьому відіграє ціла змінна – номер відповідного відліку.
Дискретному перетворенню Фур'є можна придати цікаву й глибоку інтерпретацію, якщо послідовність 
розглядати як вектор в 
-мірному евклідовому просторі. У такому просторі є лінійно-незалежних векторів
| (1.326) |
утворюючих базис, який будемо називати натуральним базисом. При цьому очевидно, що
 ,
|
інакше відлікові значення 
служать проекціями вектора 
на відповідні базисні вектори.
Оскільки розглянутий простір є евклідовим, норма цього вектора
 ,
|
у той час як скалярний добуток двох векторів і 
обчислюється за формулою
 .
|
Вектори й ортогональні, якщо 
.
Поряд із натуральним базисом в -мірному евклідовому просторі можна ввести багато інших базисних систем.
Серед них особливу роль відіграє базис Фур'є, елементами якого служать вектори
| (1.327) |
Очевидно, що 
-ю компонентою 
-го базисного вектора є число 
. При будь-яких і це число є одним з можливих значень кореня -й степені з одиниці.
|
|
|
Скалярний добуток елементів базису Фур'є
| (1.328) |
Тут верхня рівність суми обертається в нуль коли 
, оскільки всі доданки є комплексними числами з одиничним модулем та лінійно наростаючим аргументом. При додаванні відповідні вектори завжди утворюють на комплексній площині правильний замкнений багатокутник.
Отже, базис Фур'є ортогональний, але не нормований на одиницю, оскільки
 .
| (1.329) |
Знайдемо коефіцієнти розкладання деякого вектора х за елементами базису Фур'є:
 .
| (1.330) |
Для цього помножимо обидві частини рівності (1.330) скалярно на базисний вектор 
з фіксованим номером :
 .
|
Тому що базис Фур'є ортогональний, то в правій частині відмінним від нуля виявиться лише доданок з номером 
,
звідки
 ,
|
що повністю збігається з формулою (1.323), яка отримана на основі моделі МІП-сигналу.
Швидке перетворення Фур'є
Як видно з формули (1.323) або (1.325), щоб обчислити ДПФ або ЗДПФ послідовності з елементів, потрібно виконати 
операцій з комплексними числами. Якщо довжини оброблюваних масивів мають порядок тисячі або більш, то використовувати ці алгоритми дискретного спектрального аналізу в реальному масштабі часу важко через обмежену швидкодію обчислювальних пристроїв.
|
|
|
Виходом з положення є алгоритм швидкого перетворення Фур'є (ШПФ), запропонований в 60-х роках XX сторіччя. Суттєво скоротити число виконуваних операцій тут вдається за рахунок того, що обробка вхідного масиву зводиться до знаходження ДПФ (або ЗДПФ) масивів з меншим числом членів.
Будемо вважати, і це суттєво для методу ШПФ, що число відліків 
, де 
– ціле число.
Принцип розбивки вхідної послідовності. Розіб'ємо вхідну послідовність 
на дві частини з парними та непарними номерами:
| (1.331) |
та подамо -й коефіцієнт ДПФ у вигляді
|
Безпосередньо видно, що перша половина коефіцієнтів ДПФ початкового сигналу з номерами від 0 до 
виражається через коефіцієнти ДПФ двох часткових послідовностей:
| (1.332) |
Тепер врахуємо, що послідовності коефіцієнтів, які відносяться до парної та непарної частин вхідного масиву, є періодичними з періодом 
:
 .
|
Крім того множник, який входить у формулу (1.332) при 
можна перетворити так:
|
Звідки знаходимо вираз для другої половини множини коефіцієнтів ДПФ:
|
|
|
| (1.333) |
Формули (1.332) і (1.333) лежать в основі алгоритму ШПФ. Далі обчислення будують по ітераційному принципу: послідовності відліків з парними та непарними номерами знову розбивають на дві частини. Процес продовжують доти, поки не вийде послідовність, яка складається з єдиного елемента. Легко бачити, що ДПФ цього елемента збігається з ним самим.
Можна показати, що число операцій, необхідних для обчислення ШПФ, оцінюється як 
.
Виграш у швидкості обчислень у порівнянні із традиційним ДПФ досягає сотень і навіть тисяч при достатніх довжинах вхідних масивів.
Дата добавления: 2018-04-15; просмотров: 278; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!