Быстрое преобразование Фурье (БПФ) - умный, быстрый алгоритм вычисления ДПФ. Цель остается та же - вычислить коэффициенты Фурье:
$$a_p=f*u_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\cos\left(\frac{(2p+1)(2j+1)\pi}{2N}\right)\\ b_p=f*v_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\sin\left(\frac{(2p+1)(2j+1)\pi}{2N}\right)$$Давайте оценим сложность, задаваемую этими формулами. При определении вычислительной сложности будем учитывать число умножений, игнорируя сложения, поскольку это более легкие операции в сравнения с умножением. Мы предполагаем, что значения синусов и косинусов предварительно вычислены и хранятся в памяти. Проигнорируем множитель $$ \sqrt{\frac2N}$$, так как можно выбрать N/2 как степень 4, тогда деление на степень 2 является простой операцией для компьютера.
Вычисления каждого коэффициента Фурье, будет тогда включать N умножений, а поскольку коэффициентов тоже N, то сложность ДПФ, вычисляемого по этим формулам - $$N^2$$.
БПФ позволяет вычислить те же коэффициенты, но со сложностью $$2N\1og_2(N)$$. Для вектора длины 1024 (что не является чем-то необычным при цифровой обработке сигнала) сложность прямого метода -1048576, а БПФ - 20480. БПФ - рекурсивный алгоритм. Его идея -разбить исходный вектор на два вектора половинной длины, применить рекурсивно БПФ к каждому короткому вектору, а затем комбинировать две последовательности коэффициентов Фурье, построенные для коротких векторов, в последовательность коэффициентов полного вектора.
С этого момента будем полагать, что N - степень 2, $$N = 2^n,\; М == N/2 = 2^{n-1}$$
Давайте разделим вектор $$f = (f_0, f_1, \dots, f_{N-1})$$ на два коротких вектора, где компоненты с четными индексами будут принадлежать одному вектору, с нечетными - другому, $$f = (g_0, g_1, \dots, g_{M-1}h_{M-1})$$ Пока что, мы только ввели новую нотацию, не производя никаких вычислений:
$$g_i=f_{2i},\; h_i=f_{2i+1},\; i=0,1,\dots,M-1$$В результате созданы два вектора длины $$2^{n-1}$$:
$$g=(g_0,g_1,\dots,g_{2^{n-1}-1}),\;\; h=(h_0,h_1,\dots,h_{2^{n-1}-1}$$Давайте применим ДПФ к векторам g и h:
Коэффициенты Фурье для g и h соответственно имеют вид:
Формулы для коэффициентов $$a_s^h$$ и $$b_s^h$$ аналогичны.
Теперь покажем, как можно сконструировать коэффициенты Фурье $$a_p,\; b_p$$ для вектора f из коэффициентов: $$a_s^g$$ и $$a_s^h$$, $$b_s^g$$ и $$b_s^h$$
В качестве упражнения следует вывести формулу для коэффициента $$b_р$$.
$$b_p=\frac{b_p^g+b_p^h}{\sqrt2}\cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)+\frac{-a_p^g+a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)$$Помните, что БПФ - рекурсивный алгоритм, так что коэффициенты последовательностей g и h снова считаются рекурсивно, расщепляя каждую из них на короткие последовательности. Формулы исходного преобразования Фурье применяются только, когда приходим к последовательностям длины 2: $$(f_0, f_1)\to (а_0, b_0)$$:
Теорема. Сложность алгоритма БПФ для вектора длины $$N = 2^n$$г равна $$2N \1og_2(N) = 2n2^n$$.
Доказательство. Докажем теорему индукцией по n. Для базиса индукции, n = 1, N = 2, где используются простые формулы, приведенные выше, число умножений равно 2, что лучше, чем $$2N \1og_2(N)$$.
Давайте рассмотрим шаг индукции. Наше индукционное предположение - для последовательности длины $$2^n$$ сложность БПФ равна $$2n2^n>$$. Оценим сложность БПФ для последовательности длины $$2^{n+1}$$. Чтобы вычислить коэффициенты Фурье $$а_р, b_p$$ мы вначале выполняем БПФ для последовательностей g и h со сложностью $$2 * 2n2^n$$. Тогда для вычисления каждого из $$2^{n+1}$$ коэффициентов Фурье необходимо выполнить два умножения. Общая сложность тогда:
Тем самым теорема доказана.
Остается одно важное замечание. Когда мы выражаем коэффициенты Фурье $$а_р,\; b_p$$через $$а_р^g, b_p^g, а_р^h, b_p^h$$, индекс р находится в пределах $$0 \le р <2^{n-2}$$. Однако, коэффициенты Фурье для g и h определены только для индексов в пределах $$0 \le р < 2^{n-2}$$. Следующая теорема объясняет, как получить коэффициенты Фурье для g и h в пределах $$2^{n-2} \le р < 2_{n-1}$$.
Теорема. Пусть g - вектор длины $$2^{n-1}$$. Пусть $$р = 2^{n-1} - 1 - r$$, где $$0 \le r < 2^{n-2}$$. Тогда
Аналогичное отношение имеет место и для коэффициентов Фурье для h.
Доказательство. Напомним, что коэффициенты Фурье $$а_р^g$$ задаются формулой:
$$a_p^g=\frac{1}{\sqrt{2^{n-1}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left(\frac{(2p+1)(2i+1)\pi}{2^n}\right)$$Подставляя $$р = 2^{n-1} - 1 - r$$, получим
$$a_p^h=\frac{1}{\sqrt{2^{n-2}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos \left( \frac{(2^n-2r-1)(2i+1)\pi}{2^n}\right) =\frac{1}{\sqrt{2^{n-1}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left((2i+1)\pi-\frac{(2r+1)(2i+1)\pi}{2^n}\right)$$Используя тождества $$\cos(2\pi + \аlpha) = \cos(\аlpha),\; \cos(\pi + \аlpha) = - \cos(\аlpha),\;\cos{\alpha) = \cos(\аlpha)$$, упростим формулу и получим:
$$a_p^g=-\frac{1}{\sqrt{2^{n-2}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left(\frac{(2r+1)(2i+1)\pi}{2^n}\right)=-a_r^g$$Доказательство для $$b_p^g$$ остается в качестве упражнения.
В случае, когда $$2^{n-2} \le р < 2^{n-1}$$, запишем р как $$р = 2^{n-1} - 1 - r$$ и мы можем вычислить коэффициенты Фурье для f из коэффициентов Фурье для g и h следующим образом:
Давайте выразим тригонометрические множители в правой части в терминах r:
На последнем шаге мы использовали тождество $$\соs(\frac{\pi}{2} - \аlpha) = \sin \аlpha$$. Аналогично:
$$\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)=\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right)$$Теперь для $$2^{n-2} \le р < 2^{n-1}$$, где $$р = 2^{n-1} - 1 - r$$, получим:
$$a_p=\frac{-a_r^g-a_r^h}{\sqrt2}\sin\left(\frac{(2r+1)\pi}{2^{n+1}}\right)+\frac{b_r^g-b_r^h}{\sqrt2}\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right),\\ b_p=\frac{b_r^g+b_r^h}{\sqrt2}\sin\left(\frac{(2r+1)\pi}{2^{n+1}}\right)+\frac{a_r^g-a_r^h}{\sqrt2}\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right)$$Быстрое преобразование Фурье (БПФ) - умный, быстрый алгоритм вычисления ДПФ. Цель остается та же - вычислить коэффициенты Фурье:
$$a_p=f*u_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\cos\left(\frac{(2p+1)(2j+1)\pi}{2N}\right)\\ b_p=f*v_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\sin\left(\frac{(2p+1)(2j+1)\pi}{2N}\right)$$Давайте оценим сложность, задаваемую этими формулами. При определении вычислительной сложности будем учитывать число умножений, игнорируя сложения, поскольку это более легкие операции в сравнения с умножением. Мы предполагаем, что значения синусов и косинусов предварительно вычислены и хранятся в памяти. Проигнорируем множитель $$ \sqrt{\frac2N}$$, так как можно выбрать N/2 как степень 4, тогда деление на степень 2 является простой операцией для компьютера.
Вычисления каждого коэффициента Фурье, будет тогда включать N умножений, а поскольку коэффициентов тоже N, то сложность ДПФ, вычисляемого по этим формулам - $$N^2$$.
БПФ позволяет вычислить те же коэффициенты, но со сложностью $$2N\1og_2(N)$$. Для вектора длины 1024 (что не является чем-то необычным при цифровой обработке сигнала) сложность прямого метода -1048576, а БПФ - 20480. БПФ - рекурсивный алгоритм. Его идея -разбить исходный вектор на два вектора половинной длины, применить рекурсивно БПФ к каждому короткому вектору, а затем комбинировать две последовательности коэффициентов Фурье, построенные для коротких векторов, в последовательность коэффициентов полного вектора.
С этого момента будем полагать, что N - степень 2, $$N = 2^n,\; М == N/2 = 2^{n-1}$$
Давайте разделим вектор $$f = (f_0, f_1, \dots, f_{N-1})$$ на два коротких вектора, где компоненты с четными индексами будут принадлежать одному вектору, с нечетными - другому, $$f = (g_0, g_1, \dots, g_{M-1}h_{M-1})$$ Пока что, мы только ввели новую нотацию, не производя никаких вычислений:
$$g_i=f_{2i},\; h_i=f_{2i+1},\; i=0,1,\dots,M-1$$В результате созданы два вектора длины $$2^{n-1}$$:
$$g=(g_0,g_1,\dots,g_{2^{n-1}-1}),\;\; h=(h_0,h_1,\dots,h_{2^{n-1}-1}$$Давайте применим ДПФ к векторам g и h:
Коэффициенты Фурье для g и h соответственно имеют вид:
Формулы для коэффициентов $$a_s^h$$ и $$b_s^h$$ аналогичны.
Теперь покажем, как можно сконструировать коэффициенты Фурье $$a_p,\; b_p$$ для вектора f из коэффициентов: $$a_s^g$$ и $$a_s^h$$, $$b_s^g$$ и $$b_s^h$$
В качестве упражнения следует вывести формулу для коэффициента $$b_р$$.
$$b_p=\frac{b_p^g+b_p^h}{\sqrt2}\cos\left(\frac{(2p+1)\pi}{2^{n+1}}\right)+\frac{-a_p^g+a_p^h}{\sqrt2}\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)$$Помните, что БПФ - рекурсивный алгоритм, так что коэффициенты последовательностей g и h снова считаются рекурсивно, расщепляя каждую из них на короткие последовательности. Формулы исходного преобразования Фурье применяются только, когда приходим к последовательностям длины 2: $$(f_0, f_1)\to (а_0, b_0)$$:
Теорема. Сложность алгоритма БПФ для вектора длины $$N = 2^n$$г равна $$2N \1og_2(N) = 2n2^n$$.
Доказательство. Докажем теорему индукцией по n. Для базиса индукции, n = 1, N = 2, где используются простые формулы, приведенные выше, число умножений равно 2, что лучше, чем $$2N \1og_2(N)$$.
Давайте рассмотрим шаг индукции. Наше индукционное предположение - для последовательности длины $$2^n$$ сложность БПФ равна $$2n2^n>$$. Оценим сложность БПФ для последовательности длины $$2^{n+1}$$. Чтобы вычислить коэффициенты Фурье $$а_р, b_p$$ мы вначале выполняем БПФ для последовательностей g и h со сложностью $$2 * 2n2^n$$. Тогда для вычисления каждого из $$2^{n+1}$$ коэффициентов Фурье необходимо выполнить два умножения. Общая сложность тогда:
Тем самым теорема доказана.
Остается одно важное замечание. Когда мы выражаем коэффициенты Фурье $$а_р,\; b_p$$через $$а_р^g, b_p^g, а_р^h, b_p^h$$, индекс р находится в пределах $$0 \le р <2^{n-2}$$. Однако, коэффициенты Фурье для g и h определены только для индексов в пределах $$0 \le р < 2^{n-2}$$. Следующая теорема объясняет, как получить коэффициенты Фурье для g и h в пределах $$2^{n-2} \le р < 2_{n-1}$$.
Теорема. Пусть g - вектор длины $$2^{n-1}$$. Пусть $$р = 2^{n-1} - 1 - r$$, где $$0 \le r < 2^{n-2}$$. Тогда
Аналогичное отношение имеет место и для коэффициентов Фурье для h.
Доказательство. Напомним, что коэффициенты Фурье $$а_р^g$$ задаются формулой:
$$a_p^g=\frac{1}{\sqrt{2^{n-1}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left(\frac{(2p+1)(2i+1)\pi}{2^n}\right)$$Подставляя $$р = 2^{n-1} - 1 - r$$, получим
$$a_p^h=\frac{1}{\sqrt{2^{n-2}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos \left( \frac{(2^n-2r-1)(2i+1)\pi}{2^n}\right) =\frac{1}{\sqrt{2^{n-1}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left((2i+1)\pi-\frac{(2r+1)(2i+1)\pi}{2^n}\right)$$Используя тождества $$\cos(2\pi + \аlpha) = \cos(\аlpha),\; \cos(\pi + \аlpha) = - \cos(\аlpha),\;\cos{\alpha) = \cos(\аlpha)$$, упростим формулу и получим:
$$a_p^g=-\frac{1}{\sqrt{2^{n-2}}}\sum_{i=0}^{2^{n-1}-1}g_i\cos\left(\frac{(2r+1)(2i+1)\pi}{2^n}\right)=-a_r^g$$Доказательство для $$b_p^g$$ остается в качестве упражнения.
В случае, когда $$2^{n-2} \le р < 2^{n-1}$$, запишем р как $$р = 2^{n-1} - 1 - r$$ и мы можем вычислить коэффициенты Фурье для f из коэффициентов Фурье для g и h следующим образом:
Давайте выразим тригонометрические множители в правой части в терминах r:
На последнем шаге мы использовали тождество $$\соs(\frac{\pi}{2} - \аlpha) = \sin \аlpha$$. Аналогично:
$$\sin\left(\frac{(2p+1)\pi}{2^{n+1}}\right)=\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right)$$Теперь для $$2^{n-2} \le р < 2^{n-1}$$, где $$р = 2^{n-1} - 1 - r$$, получим:
$$a_p=\frac{-a_r^g-a_r^h}{\sqrt2}\sin\left(\frac{(2r+1)\pi}{2^{n+1}}\right)+\frac{b_r^g-b_r^h}{\sqrt2}\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right),\\ b_p=\frac{b_r^g+b_r^h}{\sqrt2}\sin\left(\frac{(2r+1)\pi}{2^{n+1}}\right)+\frac{a_r^g-a_r^h}{\sqrt2}\cos\left(\frac{(2r+1)\pi}{2^{n+1}}\right)$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.