Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Быстрое преобразование Фурье

Преобразование БПФ для N=PQ

Пусть N = PQ. Этот представляет собой более общий случай, чем рассмотренный в предыдущей главе. Теперь не требуется, чтобы P или Q были степенями двойки.

Напомним основную формулу:

    (1).

Рассмотрим формулу:

    (41).

Эта формула эквивалентна формуле (1). В самом деле:

Двойная сумма по pQ + q - это все равно, что одинарная сумма по n, просто порядок слагаемых другой.

Вернемся к формуле (41). В скобках там стоит обычное прямое БПФ, только не для всех xn, а для последовательности из P штук, взятых с шагом Q. Количество последовательностей равно Q. Элементы последовательности выбираются формулой xpQ + q, где p - номер элемента, q - номер последовательности.

Пусть мы умеем вычислять БПФ для P элементов за время Z(P). Нам понадобится вычислить Q таких БПФ, на что потратим время O(QZ(P)). Тем самым мы получим все множители в скобках из формулы (41). После этого надо будет вычислить N элементов Xk, каждый из которых потребует O(Q) действий, итого потребуется еще O(NQ) действий, а в сумме - O(QZ(P) + QN) действий.

В предыдущем алгоритме P - было степенью двойки, а для такого числа элементов мы умеем вычислять БПФ за O(Plog2P) шагов, т.е. Z(P) = Plog2P, и получится O(QZ(P) + QN) = O(QPlog2P + QN) = O(Nlog2P + N2/P) действий. Тем самым, мы несколько более простым путем получим ту же оценку сложности алгоритма.

Если P - не степень двойки, мы умеем вычислять ПФ за O(P2) шагов, т.е. Z(P) = P2, и получится O(QZ(P) + QN) = O(QP2 + QN) = O(N2/Q + N2/P) действий. Если P и Q достаточно велики, это лучше, чем O(N2).

Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Юрий Болдырев отвечает 12 апреля 2018

ВСЕ ВИДЕО
Знаете ли Вы, что компонентное сборочное программирование - это объектно-ориентированное сборочное программирование, основанное на распространении классов в бинарном виде и предоставление доступа к методам класса через строго определенные интерфейсы. Компонентное сборочное программирование поддерживают технологические подходы COM, CORBA, .Net.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 20.04.2018 - 20:37: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
28.03.2018 - 18:15: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
22.03.2018 - 09:33: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
04.10.2017 - 15:26: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
04.10.2017 - 05:02: Беседка - Chatter -> "Зенит"ы с "Протон"ами будут падать - Карим_Хайдаров.
03.10.2017 - 18:16: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
03.10.2017 - 07:24: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
03.10.2017 - 05:48: Беседка - Chatter -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.
02.10.2017 - 19:04: АСТРОФИЗИКА - Astrophysics -> Апериодическая комета C/2014 Q2 Lovejoy - Карим_Хайдаров.
02.10.2017 - 14:57: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
01.10.2017 - 13:58: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
01.10.2017 - 07:23: СОВЕСТЬ - Conscience -> НАСАтые астропиндосы - Карим_Хайдаров.
Bourabai Research Institution home page

Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution