ДПФ в порівнянні з класичними алгоритмами по підставі 2. Зазначимо, що алгоритми з основою 2 також можуть бути отримані з використанням розглянутого підходу. Таким чином, розглянутий метод синтезу є загальним і дозволяє синтезувати різні модифікації алгоритму Кулі - Тьюки з довільними постійним і змішаним підставами.
7.2 Алгоритм простих множників
У разі, коли N представимо твором взаємно простих множників, є можливість позбавитися від повертаючих множників в розкладанні (7.4). Тим самим можна досягти ще більшої економії числа операцій.
Щоб позбутися від множників повороту, потрібно зробити перестановку вхідний і вихідний послідовностей, відмінну від (7.2) і (7.3). Такий перестановкою може бути наступна:
для вхідної послідовності
(7.5)
n 1 . = 0, ...., N 1 -1; п 2 = 0,. .., N 2 -1;
для вихідний послідовності
(k 1 N 2 + K 2 ) = X ((s 1 k 2 N 1 + s 2 k 1 N 2 ) mod N), (7.6)
k 1 = 0, ..., N 1 -1; k < sub> 2 = 0, ..., N 2 -1,
де запис п mod N означає В«залишок від ділення п на NВ», а s 1 і s 2 визначаються з наступних рівнянь відповідно до китайської теоремою про залишки про відновлення цілого числа за його обчислюватись: s 1 N 1 = 1mod N 2 , s 1 2 , s 2 N 2 == 1modN 1 , s 2 1 . Тоді алгоритм N = N 1 N 2 - точкового ДПФ представляється у вигляді
Таким чином, алгоритм простих множників (АПМ) є способом представлення одновимірного ДПФ у вигляді багатовимірного, причому розмірність залежить від числа взаємно простих співмножників N. Алгоритм простих множників має ступінчасту форму об'єднання мало точкових перетворень. У даному випадку на першій ступені проводиться N 1 N 2 -точкових ДПФ, а на другій - N 2 N 1 -точкових ДПФ. p> Вперше АПМ був запропонований Гудом [3]. У тому випадку, коли використовувані мало точкові алгоритми синтезовані оптимальним чином за методом Винограду, виходить алгоритм Гуда - Винограду [3]. Оптимальні мало точкові алгоритми ШПФ синтезуються шляхом зведення мало точкового ДПФ до сукупності циклічних згорток. Для останніх Виноградом [2] доведено теорему про існування алгоритму обчислення з мінімальною кількістю множень і був запропонований метод синтезу, заснований на послідовному обчисленні поліноміальних відрахувань по непріводімим поліномах в полі раціональних чисел згідно з поліноміальним варіантом китайської теореми про залишки [3]. br/>
7.3 Алгоритм Винограду
Подальшій економії обчислень в випадку розкладання N на взаємно прості множники можна досягти, якщо ступінчастий характер об'єднання часткових мало точкових перетворень замінити вкладеним. У цьому і полягає ідея алгоритму Винограду. Ідею вкладення мало точкових алгоритмів найлегше зрозуміти на прикладі.
Приклад 5. Розглянемо випадок 6-точкового ДПФ, тобто N = 6. Нехай N 1 = 2, N 2 = 3. Наведемо спочатку алгоритми мало точкових (2 - і 3-точкових) ДПФ, синтезовані оптимальним чином за методом Винограду.
Алгоритм 2-точкового ДПФ
В
має вигляд
(7.8)
де s i -складання, m i -множення; А i і a i - вихідні та вхідні числа. p> Алгоритм 3-точкового ДПФ
В
Має вигляд
,,
,, (7.9)
,,
Перетворимо вихідну 6-точкову послідовність у двовимірну точкову відповідно до (7.5) і (7.6). Тоді матрицю 6-точкового ДПФ можна представити у вигляді прямого твори 2 - і 3-точкових ДПФ і перетворення можна записати у вигляді:
, (7.10)
,,,,
Де
В
Застосуємо до матричних перетворенню (7.10) алгоритм 2-точкового БПФ (7.8). У результаті знайдемо векториі :
В
Для обчислення векторів і використовуємо алгоритм 3-точкового ШПФ (7.9). p> Таким чином, ми як би В«вклалиВ» алгоритм 3-точкового ШПФ в структуру 2-точкового, який оперує 3-точковими векторами. Характерною особливістю В«вкладенихВ» алгоритмів є те, що необхідне число множень для N -точкового алгоритму дорівнює добутку числа множень, необхідних для кожного з часткових алгоритмів. Цей факт легко перевіряється на наведеному ви...
