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

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

Теоремы быстрого преобразования Фурье (FFT)

Теорема 0

Если комплексное число представлено в виде e j2πN, где N - целое, то это число e j2πN = 1.

Доказательство:

По формуле Эйлера, и ввиду периодичности синуса и косинуса:

e j2πN = cos(2πN) + j sin(2πN) = cos 0 + j sin 0 = 1 + j0 = 1

Теорема 1

Величина периодична по k и по n с периодом N. То есть, для любых целых l и m выполняется равенство:

    (4).

Доказательство:

    (5)

Величина -h = -(nl+mk+mlN) - целая, так как все множители целые, и все слагаемые целые. Значит, мы можем применить Теорему 0:

Что и требовалось доказать по (4).

Теорема 2

Для величины справедлива формула:

Доказательство:

Алгоритм быстрого преобразования Фурье (БПФ) - это оптимизированный по скорости способ вычисления ДПФ. Основная идея заключается в двух пунктах.

  1. Необходимо разделить сумму (1) из N слагаемых на две суммы по N/2 слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.
  2. Необходимо повторно использовать уже вычисленные слагаемые.

Применяют либо "прореживание по времени" (когда в первую сумму попадают слагаемые с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые N/2 слагаемых, а во вторую - остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. Рассмотрим случай прореживания по времени.

Теорема 3

Определим еще две последовательности: {x[even]} и {x[odd]} через последовательность {x} следующим образом:

x[even]n = x2n,
x[odd]n = x2n+1,     (6)
n = 0, 1,..., N/2-1

Пусть к этим последовательностям применены ДПФ и получены результаты в виде двух новых последовательностей {X[even]} и {X[odd]} по N/2 элементов в каждой.

Утверждается, что элементы последовательности {X} можно выразить через элементы последовательностей {X[even]} и {X[odd]} по формуле:

    (7).

Доказательство:

Начинаем от формулы (2), в которую подставляем равенства из (6):

    (8)

Теперь обратим внимание на то, что:

    (9)

Подставляя (9) в (8) получаем:

    (10)

Сравним с формулами для X[even]k и X[odd]k при k = 0,1,…,N/2-1:

    (11)

Подставляя (11) в (10) получим первую часть формулы (7):

Это будет верно при k = 0,1,…,N/2-1.

Согласно теореме 1:

    (12)

Подставим (12) в (10), и заменим по теореме 2:

    (13)

Для k = N/2,…,N-1 по формуле (2):

    (14)

Подставляем (14) в (13):

Эта формула верна для k = N/2,…,N-1 и, соответственно, (k - N/2) = 0,1,…,N/2-1 и представляет собой вторую и последнюю часть утверждения (7), которое надо было доказать.

 

Формула (7) позволяет сократить число умножений вдвое (не считая умножений при вычислении X[even]k и X [odd]k), если вычислять Xk не последовательно от 0 до N - 1, а попарно: X0 и XN/2, X1 и XN/2+1,..., XN/2-1 и XN. Пары образуются по принципу: Xk и XN/2+k.

Теорема 4

ДПФ можно вычислить также по формуле:

    (15)

Доказательство:

Согласно второй части формулы (7), получим:

 

Это доказывает второе равенство в утверждении теоремы, а первое уже доказано в теореме 3.

 

Также по этой теореме видно, что отпадает необходимость хранить вычисленные X[even]k и X[odd]k после использования при вычислении очередной пары и одно вычисление можно использовать для вычисления двух элементов последовательности {X}.

На этом шаге будет выполнено N/2 умножений комплексных чисел. Если мы применим ту же схему для вычисления последовательностей {X[even]} и {X[odd]}, то каждая из них потребует N/4 умножений, итого еще N/2. Продолжая далее в том же духе log2N раз, дойдем до сумм, состоящих всего из одного слагаемого, так что общее количество умножений окажется равно (N/2)log2N, что явно лучше, чем N2 умножений по формуле (2).

Рассмотрим БПФ для разных N. Для ясности добавим еще один нижний индекс, который будет указывать общее количество элементов последовательности, к которой этот элемент принадлежит. То есть X{R}k - это k-й элемент последовательности {X{R}} из R элементов. X{R}[even]k - это k-й элемент последовательности {X{R}[even]} из R элементов, вычисленный по четным элементам последовательности {X{2R}}. X{R}[odd]k - это k-й элемент последовательности {X{R}[odd]}, вычисленный по нечетным элементам последовательности {X{2R}}.

В вырожденном случае, когда слагаемое всего одно (N = 1) формула (1) упрощается до:

,

Поскольку в данном случае k может быть равно только 0, то X{1}0 = x{1}0, то есть, ДПФ над одним числом дает это же самое число.

Для N = 2 по теореме 4 получим:

Для N = 4 по теореме 4 получим:

Отсюда видно, что если элементы исходной последовательности были действительными, то при увеличении N элементы ДПФ становятся комплексными.

Для N = 8 по теореме 4 получим:

Обратите внимание, что на предыдущем шаге мы использовали степени W4, а на этом - степени W8. Лишних вычислений можно было бы избежать, если учесть тот факт, что

Тогда формулы для N=4 будут использовать те же W-множители, что и формулы для N=8:

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

Юрий Болдырев в программе "Разбор полётов" (Эхо мацы, 25.06.18):
Безнаказанность власти влечет гибель народа

ВСЕ ВИДЕО
Знаете ли Вы, что Instance, экземпляр объекта в объектно-ориентированном программировании - это конкретный объект из набора объектов данного класса. Все экземпляры одного класса имеют одинаковый набор операций.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 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