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

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

Логарифмический алгоритм БПФ для произвольного N

В "Википедии" нашелся алгоритм сложности O(Nlog2N)для произвольного N. Алгоритм основан на значительном увеличении числа элементов последовательности и дополнении ее нулями. Хотя такое расширение, естественно, будет компенсироваться высокой скоростью алгоритма.

Длина последовательности берется равной N', где N' - степень двойки ближайшая сверху к 2N. То есть, 4N > N' = 2T ≥ 2N. Т.е. число элементов новой последовательности в худшем случае может превышать число элементов исходной последовательности почти в 4 раза. Например, если N = 9, то N' = 32.

Обозначим

Представим формулу (1) в виде:

Преобразуем степень:

kn = 2kn/2 = (−k2 + k2 + 2kn + n2 − n2)/2 = (−k2 + (k + n)2 − n2)/2

Это используем для дальнейшего преобразования формулы (1):

Далее введем обозначения:

x'n = xnW −n2/2

X'k = XkW k2/2

Для n > N, полагаем xn = 0.

Тогда

   (42)

И далее авторы алгоритма выполняют виртуозный "финт ушами". Пусть:

zk = (2N − 2 − k)

wn = W zn2/2

И превращают формулу (42) в:

   (43)

Проверим:

wzk − n = W (zzk − n)2/2 = W (2N − 2 − (zk − n))2/2 = W (2N − 2 − zk + n)2/2 = W (2N − 2 − (2N − 2 − k) + n)2/2 = W (2N − 2 − 2N + 2 + k + n)2/2 = W (k + n)2/2

Правая часть формулы (43) является дискретной сверткой. В общем случае формула свертки имеет вид:

   (44)

где f и g - функции от целых переменных (т.е. дискретные функции). В данном случае роль таких функций играют x'n и wn, которые "зависят" от своих индексов как от целых переменных. Свертка обладает замечательным свойством:

F(f * g) = F(f) F(g)   (45)

где F(f) - это дискретная функция, которая получается из дискретной функции f с помощью быстрого преобразования Фурье.

Дальнейший порядок вычисления таков. Сначала надо вычислить F(x'), то есть взять набор x'n и вычислить БПФ для n = 0...N' − 1. Затем вычислить F(w), для чего взять набор wn и вычислить БПФ для n = 0...N' − 1. Потом по формуле (45) простым перемножением получаем F(x' * w) = F(x') F(w). Просто берем i-й элемент, полученный после БПФ набора x'n, и умножаем на i-й элемент, полученный после БПФ набора wn. В результате получим БПФ свертки x' * w. Теперь у нас есть БПФ свертки, из него надо получить саму свертку. Для этого применяем обратное преобразование Фурье. Теперь нам надо найти X'k. Для этого используем формулу (43). k-й элемент набора Xk будет соответствовать zk-му элементу свертки. Наконец, останется перейти от X'k к Xk.

В процессе вычислений мы применяли алгоритмы порядка сложности N, N' и N'log2N' (когда делали три БПФ). Поскольку N' не может превышать N более, чем в 4 раза, то весь алгоритм имеет сложность O(Nlog2N)

Обратное преобразование требует величины W без минуса в показателе и в конце алгоритма - деления всех полученных элементов на N. Три алгоритма БПФ остаются в этом случае теми же: два прямых перобразования и одно обратное.

На следующей страничке приведен листинг программы, выполняющей прямое и обратное преобразования по этому алгоритму. Оптимизация выполнена примерно теми же способами, что и в предыдущем случае с незначительными модификациями. Переменные x' в алгоритме обозначаются как x_, 2N как N2, N' как N_, zk как N22, π/N (или −π/N при обратном преобразовании) как piN.

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

(время поиска примерно 20 секунд)


Знаете ли Вы, что такое мысленный эксперимент, gedanken experiment?
Это несуществующая практика, потусторонний опыт, воображение того, чего нет на самом деле. Мысленные эксперименты подобны снам наяву. Они рождают чудовищ. В отличие от физического эксперимента, который является опытной проверкой гипотез, "мысленный эксперимент" фокуснически подменяет экспериментальную проверку желаемыми, не проверенными на практике выводами, манипулируя логикообразными построениями, реально нарушающими саму логику путем использования недоказанных посылок в качестве доказанных, то есть путем подмены. Таким образом, основной задачей заявителей "мысленных экспериментов" является обман слушателя или читателя путем замены настоящего физического эксперимента его "куклой" - фиктивными рассуждениями под честное слово без самой физической проверки.
Заполнение физики воображаемыми, "мысленными экспериментами" привело к возникновению абсурдной сюрреалистической, спутанно-запутанной картины мира. Настоящий исследователь должен отличать такие "фантики" от настоящих ценностей.

Релятивисты и позитивисты утверждают, что "мысленный эксперимент" весьма полезный интрумент для проверки теорий (также возникающих в нашем уме) на непротиворечивость. В этом они обманывают людей, так как любая проверка может осуществляться только независимым от объекта проверки источником. Сам заявитель гипотезы не может быть проверкой своего же заявления, так как причина самого этого заявления есть отсутствие видимых для заявителя противоречий в заявлении.

Это мы видим на примере СТО и ОТО, превратившихся в своеобразный вид религии, управляющей наукой и общественным мнением. Никакое количество фактов, противоречащих им, не может преодолеть формулу Эйнштейна: "Если факт не соответствует теории - измените факт" (В другом варианте " - Факт не соответствует теории? - Тем хуже для факта").

Максимально, на что может претендовать "мысленный эксперимент" - это только на внутреннюю непротиворечивость гипотезы в рамках собственной, часто отнюдь не истинной логики заявителя. Соответсвие практике это не проверяет. Настоящая проверка может состояться только в действительном физическом эксперименте.

Эксперимент на то и эксперимент, что он есть не изощрение мысли, а проверка мысли. Непротиворечивая внутри себя мысль не может сама себя проверить. Это доказано Куртом Гёделем.

Понятие "мысленный эксперимент" придумано специально спекулянтами - релятивистами для шулерской подмены реальной проверки мысли на практике (эксперимента) своим "честным словом". Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Форум Рыцари теории эфира


Рыцари теории эфира
 26.11.2020 - 18:27: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Аманды Вольмер - Карим_Хайдаров.
26.11.2020 - 16:10: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
26.11.2020 - 16:09: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
26.11.2020 - 15:34: ВОЙНА, ПОЛИТИКА И НАУКА - War, Politics and Science -> Проблема государственного терроризма - Карим_Хайдаров.
26.11.2020 - 15:32: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Амары Ельской - Карим_Хайдаров.
26.11.2020 - 12:07: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Александра Флоридского - Карим_Хайдаров.
25.11.2020 - 07:52: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
25.11.2020 - 07:51: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от проф. В.Ю. Катасонова - Карим_Хайдаров.
25.11.2020 - 07:37: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Александры Андерссон - Карим_Хайдаров.
25.11.2020 - 06:51: НОВЫЕ ТЕХНОЛОГИИ - New Technologies -> "Зенит"ы с "Протон"ами будут падать - Карим_Хайдаров.
25.11.2020 - 06:47: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМЫ МЕДИЦИНЫ - Карим_Хайдаров.
24.11.2020 - 20:36: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.

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