"> Iterative_FFT (a) _Reverse_Copy (a, A)
n=a. length//n є ступенем 2s=1 to lg (n)=2 s
w m=e 2i?/n
for k=0 to n - 1 by m=1j=0 to m/2 - 1=wA [k + j + m/2]=A [k + j] [k + j ]=u + t [k + j + m/2]=ut
w=ww m
Процедура Bit_Reverse_Copy розміщує дані вихідного масиву a в масиві A в необхідному порядку, тобто здійснює зворотний перестановку або реверс бітів. Наприклад, якщо масив а=(0, 1, 2, 3, 4, 5, 6,7), то на виході вийде масив А=(0, 4, 2, 6, 1, 5, 3,7). Нумерація елементів змінюється згідно з правилом реверсу бітів.
Кожен алгоритм має обчислювальну складність? (nlg (n)). При цьому рекурсивний алгоритм розбиває вихідний масив на частини і зберігає їх копії, а ітераційний копіює масив тільки один раз в необхідному порядку. Крім того ітераційний алгоритм вимагає обчислення lg (n) і округлення його до цілого числа, що так само затримує виконання перетворення.
У результаті для реалізації був обраний рекурсивний алгоритм.
Так як алгоритм розрахований на відділення обчислювального модуля від ПК і бібліотека математичних обчислень не використовується, зведення експоненти в комплексну ступінь реалізованачерез обчислення синуса.
Для обчислення синуса розкладемо його в ряд Тейлора, для чого реалізовуємо так само функцію зведення числа в ступінь і обчислення факторіала.
Для роботи з комплексними числами знадобиться клас, який реалізує їх в алгебраїчній формі, а так само функції додавання, віднімання та множення комплексних чисел.
Так як алгоритм розрахований на кількість відліків рівне ступеню двійки, а на вхід приходить кратне десяти, то перед початком перетворення доповнимо [6] сигнал нулями.
Продемонструємо роботу алгоритму для вектора з 8 елементів.
Рекурсивний алгоритм ШПФ для вектора з 8 елементів
2.2 Метод кореляції
Кореляція [7] - величина, характеризує взаємну залежність двох випадкових величин.
Кореляція двох функцій f (x) іh (x) визначається виразом
Де - комплексно сполучена функція до f (x). Так як у нашому випадку обидві вхідні функції дійсні, то.
Автокорреляция - статична взаємозв'язок між двома випадковими величинами з одного ряду, але взятих зі зрушенням.
За графіком автокореляційної функції можна судити про періодичність базової функції, а отже, про її частотних характеристиках.
2.3 Метод головних компонент
Метод головних компонент (МГК) [8] трансформує опис стаціонарного стохастичного процесу таким чином, що вихідна простір редуцированного розміру зберігає найбільш важливу інформацію про вихідний процесі. Застосовується для зменшення розмірності простору і виділення найбільш значимої інформації.
Нехай - випадковий вектор, а позначає очікуване (середнє) значення матриці автокореляції по всіх векторах. При кінцевій кількості векторів цю матрицю можна описати таким чином
де матриця даних утворена послідовністю векторів.
Позначимо власні числа матриці автокореляції, - сполучені з ними власні вектори. Власні значення та вектори пов'язані залежністю
Де Власні числа симетричною неотрицательной матриці, якою є, є раціональними і невід'ємними.
Впорядкуємо їх в послідовності убування і, відповідно до цієї послідовністю впорядкуємо власні вектора. Візьмемо перший власних значень. У цьому випадку матриця перетворення буде мати вигляд, при. Ця матриця визначає лінійне перетворення.
Вектор являє собою вектор головних компонент, що мають найбільший вплив на реконструкцію вектора даних
З погляду машинної реалізації методу найскладнішим завданням є знаходження власних чисел і векторів матриці. [9] Для вирішення цієї проблеми найчастіше пріменяетсяQR метод пошуку власних векторів і власних чисел.
Реалізація
Продемонструємо реалізацію методів статистичної обробки, а так само функцію побудови графіків для візуалізаціі результату, читання даних з файлу і головну функцію, через яку здійснюються виклики всіх методів.
Повний текст програми наведений у додатку А.
Перетворення Фур'є
Функція обчислення швидкого перетворення Фур'є приймає на вхід покажчики на масив вихідних даних, масив резул...
