• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Основні положення алгоритму ШПФ

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

Оскільки алгоритми ШПФ є одними з найуживаніших при опрацюванні сигналів їх розгляд є доцільним в даному посібнику.

Алгоритм швидкого перетворення Фур'є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур'є (ДПФ), що має складність O(Nlog₂N) на відміну від складності ДПФ порядку O(N²).

Визначення 1. Дано кінцеву послідовність x₀, x₁, x₂,..., x_N-1 (у загальному випадку комплексних чисел). ДПФ полягає в пошуку послідовності X₀, X₁, X₂,..., X_N-1, елементи якої обчислюються за формулою:

(2.1)

Визначення 2. Зворотне ДПФ полягає в пошуку послідовності x₀, x₁, x₂,..., x_N-1, елементи якої обчислюються за формулою:

(2.2)

Основною властивістю перетворень (2.1) і (2.2) є те, що з послідовності {x} отримується (при прямому перетворенні) послідовність {X}, а якщо застосувати до {X} зворотне перетворення, то знову отримується вихідна послідовність {x}.

Визначення 3. Величина

називаєтьсяповертаючим множником.

Властивості повертаючих множників

При k = 1

Пряме перетворення Фур'є можна виразити через повертаючі множники. Тоді формула (2.1) матиме вигляд:

(2.3)

Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (re^jφ) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а φ – аргумент). Модуль відповідає довжині вектора, а аргумент - куту повороту. Модуль повертаючого множника . дорівнює одиниці, а фаза - 2π/N. Оскільки при множенні комплексних чисел, представлених у показниковій формі, їхні модулі перемножуються, а аргументи підсумовуються, множення вихідного числа на повертаючий множник не змінить довжину вектора, але змінить його кут. Тобто, відбудеться повертання вектора на кут 2π/N.

З формули (2.3) можна визначити геометричний зміст перетворення Фур'є таким чином: представити N комплексних чисел-векторів з набору {x}, кожне у вигляді суми векторів з набору {X}, повернених на кути, кратні 2π/N.

Рис.2.1.

Читайте також:

1. II. ЗАГАЛЬНІ ПОЛОЖЕННЯ.
2. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
3. Адвокатура в Україні: основні завдання і функції
4. Амортизація основних засобів, основні методи амортизації
5. Артеріальний пульс, основні параметри
6. Банківська система та її основні функції
7. Білорусь. Характеристика положення та господарства країни.
8. Біржові товари і основні види товарних бірж. Принципи товарних бірж.
9. Блоки схеми алгоритму
10. Будова й основні елементи машини
11. Будова оптоволокна та основні фізичні явища в оптоволокні.
12. Бюджетування (основні поняття, механізм).

Переглядів: 1010