периодична по k и по n с периодом N. То есть, для любых целых l и m выполняется равенство: Если комплексное число представлено в виде 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
Величина периодична по k и по n с периодом N. То есть, для любых целых l и m выполняется равенство:
(4).
Доказательство:
(5)
Величина -h = -(nl+mk+mlN) - целая, так как все множители целые, и все слагаемые целые. Значит, мы можем применить Теорему 0:
Что и требовалось доказать по (4).
Для величины справедлива формула:
Доказательство:
Алгоритм быстрого преобразования Фурье (БПФ) - это оптимизированный по скорости способ вычисления ДПФ. Основная идея заключается в двух пунктах.
Применяют либо "прореживание по времени" (когда в первую сумму попадают слагаемые с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые N/2 слагаемых, а во вторую - остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. Рассмотрим случай прореживания по времени.
Определим еще две последовательности: {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.
ДПФ можно вычислить также по формуле:
(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:
|
|
 |
