ще алгоритмі.
На закінчення відзначимо, що принцип В«вкладенняВ» малоточечних алгоритмів застосовується також для обчислення N-точкових циклічних згорток, коли N розкладається на взаємно прості множники, якщо є досить ефективні алгоритми малоточечних згорток. Вкладені алгоритми циклічних згорток отримали назву по імені авторів алгоритмів Агарвал-Кулі [3]. У порівнянні з традиційними алгоритмами обчислення згортки з використанням БПФ алгоритми Агарвал-Кулі дозволяють заощадити число множень майже на порядок.
Іншими класами ще більш економних алгоритмів ДПФ і згортки є алгоритми, засновані на теоретико-числових і поліноміальних перетвореннях, з якими можна познайомитися в [3].
8. АНАЛІЗ ТОЧНОСТІ РЕАЛІЗАЦІЇ АЛГОРИТМІВ ШПФ
При реалізації алгоритму ШПФ, як і, при реалізації інших алгоритмів цифрової обробки сигналів, виникають обчислювальні помилки, округленням (усіканням) творів, квантуванням коефіцієнтів і. можливо процедурою масштабування чисел (з метою усунення переповнення суматорів). При аналізі помилок будемо приймати допущення про їх характер, тобто будемо розраховувати вихідну помилку ШПФ як суперпозицію помилок, викликаних кожним незалежним джерелом помилок.
Методику оцінки обчислювальних помилок БПФ розглянемо на прикладі реалізації ШПФ за основою 2 і з проріджуванням за часом. Розглянута методика може бути застосована і для аналізу помилок інших алгоритмів ШПФ. Будемо припускати, що: оброблювані числа представляються за допомогою b 1 +1 розрядів, а коефіцієнти - за допомогою b 2 +1 розрядів з урахуванням знака; для апроксимації творів використовується операція округлення; масштабування проміжних результатів проводиться на вході кожної операції В«МетеликВ» шляхом зсуву чисел на один розряд вправо (розподіл на два); вхідні дані пронормовані таким чином, що, і підкоряються рівномірному закону розподілу тобто мають математичне сподівання рівне нулю, і дисперсію рівну 1/3. Отже, середньоквадратичне значення (СК3) вхідний послідовності одно також 1/3. Відповідно до теореми Парсеваля
В
вихідна послідовність X (k) БПФ матиме СК3 N/3, де N -розмір перетворення. З метою з'ясування методики аналізу помилок отримаємо алгоритм ШПФ в аналітичному вигляді. Для цього в вираз для N = 2 v - точкового ДПФ (5.1)
(8.1)
необхідно підставити двійкове розкладання коефіцієнтів п і k:
(8.2)
в результаті алгоритм ШПФ можна уявити, як раніше переконалися, у вигляді v +1- ступеневої процесу.
На ступені т = 0 проводиться двійковій-інверсна перестановка вхідної послідовності
В
На кожній з інших v ступенів (т = 1, 2, ...., v) виробляється перетворення типу В«метеликВ» вихідний послідовності попереднього ступеня.
Так, на щаблі т = 1 виробляється перетворення послідовності
В
X 0 (n 1 , ..., п v ):
В
На ступені m = 2-перетворення послідовності Х 1 (п 1 , ..., n v-1 , k 1 )
В
На m-го ступеня
(8.3)
Так поступово в двійковому поданні індексу послідовності Х m із збільшенням т відбувається заміна коефіцієнтів n i на k j
Нарешті при т = v
В
Вихідна послідовність останнього ступеня є шуканої:
В
X (k) = X (k v 2 v-1 + ... + k 1 ) = X v (k v 2 v-1 + k v-1 2 v-2 +. .. + k 1 ).
Уявімо індекс елемента т-й щаблі у вигляді
В
(n 1 , ..., n vm , k m ,,. .., k 1 ) = 2 v-1 n 1 +2 v-2 n 2 + ... +2 m n vm +2 m-1 k m + ... + k 1 = 2 m l + q (8.4)
В
Тоді число Xm (2ml + q) можна розглядати як q-й елемент l -го блоку т-й щаблі.
Приклад б. Розглянемо описану процедуру синтезу алгоритму ШПФ з проріджуванням за часом на прикладі 16-точкового ДПФ. У цьому випадку v = 4. Індекси n і k представимо наступним чином: n = n 4 2 3 + n 3 2 2 + n 2 2 + n 1 , k = k 4 2 3 + k 3 2 2 + k 2 2 + k 1.
Підставляючи n і k в вираз для 16-точкового ДПФ, отримуємо
В <...
