p> X (k 4 k 3 k 2 k 1 ) = (n 4 n З n 2 n 1 ) <В
В
Тепер розпишемо алгоритм по щаблях:
т = 0 - інверсія вхідної послідовності:
В
Х 0 (n 1 2 3 + n 2 2 2 + n 3 2 + n 4 ) = x (n 4 2 3 + n 3 ' 2 2 + n 2 2 + n 1 );
В
т = l - перетворення В«метеликВ» послідовності Х 0 :
В В
т = 2 - перетворення В«метеликВ» послідовності X 1 :
В
m = 3 - перетворення В«метеликВ» послідовності Х 2 :
В
m = 4 - перетворення В«метеликВ» послідовності Х З :
В
Шукана вихідна послідовність
В
В
Малюнок 7
Спрямований граф отриманого в прикладі 16-точкового ШПФ з зазначенням джерел елементарних помилок округлення творів та масштабування, а також шляхів їх розповсюдження зображений на рис.7. Помилки округлення з'являються в місцях множення комплексних чисел на нетривіальні повертають множники.
Помилки масштабування з'являються на обох входах кожної операції В«метеликВ» через зсув вхідних чисел на один розряд вправо (розподіл на два).
Елементарні помилки округлення і масштабування, що виникають на різних щаблях алгоритму, призводять до того, що відліки ДПФ X (k) на виході обчислюються неточно.
Позначимо помилку обчислення k-ro відліку ДПФ через e (k) = X '(k)-X (k), де Х' (k)-обчислене значення відліку.
Аналіз траєкторій поширення елементарних помилок, що виникають на різних щаблях алгоритму, дозволяє зробити наступні висновки:
1. Елементарна помилка з дисперсією , виникає на т-й щаблі алгоритму. викликає помилку з дисперсією в 2 vm вихідних точках ШПФ.
2. Дисперсія помилки кожного вихідного відліку алгоритму, обумовленої округленням творів, дорівнює сумі помилок, 2 vm з яких викликається помилками т-й щаблі.
Перейдемо до аналізу арифметичних помилок. У силу того, що математичне сподівання всіх елементарних помилок дорівнює нулю, математичне очікування результуючої помилки E (e (k)) = 0 для всіх k. Тоді СКЗ помилок ДПФ буде визначатися тільки дисперсією елементарних помилок.
Дисперсія помилок округлення твори двох комплексних чисел на т-й щаблі дорівнює 4 . Множник з'являється через масштабування на т попередніх щаблях шляхом ділення навпіл.
Обчислимо СКЗ помилок e (k), k = 0, ..., N-1. З аналізу алгоритму БПФ (8.3) і відповідного спрямованого графа випливає, що нетривіальні множення, пов'язані з обчисленням відліку Х (k), з'являються, починаючи з щаблі
(8.5)
де. Це пояснюється тим, що перша поява
одиниці в двійковому поданні,, відповідає множенню на коефіцієнт -1 на щаблі т, тоді на наступній т + l-й щаблі наявність коефіцієнта = 1 призведе до множенню на j, а вже на т +2 і далі щаблях всі множення будуть нетривіальними. Це добре простежити, аналізуючи вираз (8.3), що описує т-у щабель алгоритму. Можна показати шляхом обчислень s (k), що для визначення відліків з номерами k = 0, N/4; N/2; 3N/4 не потрібно виконання нетривіальних множень, всі множення тут на;. Помилка округлення цих відліків дорівнює нулю. А для обчислення СКЗ помилок округлення відліків з іншими k скористаємося другим виводом. В результаті отримаємо
(8.6)
Приклад 7. Розглянемо обчислення помилок округлення відліків 16-точкового ШПФ. Для цього випишемо для кожного номера відліку його двійкове подання. Потім користуючись виразом (8.6), обчислюємо помилки округлення. Результати розрахунків наводяться в табл.1. Зауважимо, що відліки з номерами k = 4, 8, 12 обчислюються точно так, як s (k)> 4, де 4-максимальне число можливих ступенів алгоритму, тобто у формуванні відліків з номерами 0, 4, 8, 12 беруть участь множення тільки на тривіальні множники (див. також граф на мал. 5).
Обчислимо СКЗ помилки, усереднене по всіх k. На перших двох щаблях алгоритму (т = 1,2) усі множення є точними, так як множники тривіальні ; на виходах т-й щаблі (т = 3, ..., у) з'являється N творів в блоках, причому чотири твори в кожному блоці є точними в результаті множення також на тривіальні множники.
Таблиця 1
В В
Тоді, користуючись висновком 1, отримуємо br/>
(8.7)
У разі 1...
