Преобразование Фурье - это математический инструмент для изучения периодических или почти периодических функций. Хорошим примером почти периодических функций является звуковая волна, порождаемая звучанием музыкального инструмента. Давайте рассмотрим простейшее музыкальное устройство - вибрирующую струну Если "щипнуть" натянутую струну, то она начнет вибрировать и ее колебания порождают колебания воздуха вокруг струны.
В результате возникает звуковая волна, периодически распространяющаяся область высокого давления воздуха, сменяющаяся областью низкого давления. Эти волны распространяются в пространстве, удаляясь от источника звука. Для записи звука используется микрофон, имеющий внутри гибкую мембрану Сразу же как звуковая волна достигает микрофона, область высокого давления заставляет мембрану сжиматься, а низкого давления - тянет мембрану в обратном направлении. Микрофон преобразует колебания мембраны в электрический сигнал, который следует движениям мембраны. В аналоговой записи звука электрический сигнал может использоваться для намагничивания ленты, так что интенсивность магнитного поля ленты воспроизводит профиль звукового сигнала. В цифровой записи звука электрический сигнал, создаваемый микрофоном, измеряется. Измерения, проводимые с заданным временным интервалом, могут сохраняться в памяти компьютера. Например, для системы записи СD (компакт дисков) измерения проводятся с частотой 44100 Герц, что означает запись 44100 измерений в секунду Величина сигнала обычно масштабируется в интервале от-1 до 1.
Давайте вернемся к обсуждению колеблющейся струны. Колеблющаяся струна издает звук с некоторой частотой, которая называется базовой частотой $$\omega$$. Оказывается, что струна может колебаться более сложным способом. Она может иметь состояния высокой вибрации с частотой $$2\omega,\; 3\omega,\; 4\omega$$ и так далее. На практике, колебание струны включает колебания высокой вибрации в дополнение к колебаниям с базовой частотой. В музыке,
состояния высокой вибрации, производимые музыкальным инструментом, называются обертонами. Распределение интенсивности обертонов - это то, что отличает один инструмент от другого, играющего одну и ту же ноту.
Ниже на рисунке представлена диаграмма звучания флейты, соответствующая примерно 0,01 секунды записи. Заметьте, что профиль почти периодический, - на диаграмме можно выделить 5 периодов.
Следующая диаграмма показывает спектр частот этой звуковой волны.
Поскольку это звук музыкального инструмента, играющего одну ноту, то диаграмма представляет пики, соответствующие базовой частоте (587 Нz; нота D второй октавы) и обертонам базовой частоты. Заметьте, для этого инструмента в частотном спектре отсутствует второй обертон.
Анализ частотного спектра сигнала, представленного выше, выполнен с использованием дискретного преобразования Фурье (ДПФ), которое мы намереваемся далее обсудить.
Давайте рассмотрим функцию $$f(t)$$, определенную на интервале $$0 \le t \le\pi$$. Мы хотим измерить f(t) в N равноудаленных точках $$t_0, t_1, t_2, \dots, t_{N-1}$$ с расстоянием между точками равным $$\frac{\pi}{N}$$. Первую точку выберем не в 0, а в середине первого интервала - в точке $$t_0=\frac{\pi}{2N}$$ . Тогда $$t_1=t_0+\frac{\pi}{N}=\frac{3\pi}{2N},\; t_2=t_1=\frac{\pi}{N}=\frac{5\pi}{2N}$$, и так далее с общей формулой:
Последняя точка будет закрывать правый конец интервала:
$$t_{N-1}=\frac{(2N-1)\pi}{2N}=\pi-\frac{\pi}{2N}$$Измеряя f(t) в этих точках получим N-компонентный вектор
где $$f_j = f (t_j)$$.
Далее будем полагать, что N четно, N = 2М.
Волны будем моделировать периодическими функциями cos(t) и sin(t). С этого момента будем полагать, что аргументы тригонометрических функций измеряются в радианах. Давайте рассмотрим семейство функций:
Мы можем записать их в более общей форме:
$$u_р(t) = \cos((2р + 1)t),\; u_p(t) = \sin((2р + 1)t),\; р = 0,1, \dots ,М - 1.$$Используя измерения в ряде точек, можно перейти от непрерывных функций к их дискретным аналогам, создавая для каждой функции N-компонентный вектор:
Аналогично, выполним эти действия и для функции $$v_p(t)$$.
Подставляя значения для точек $$t_j$$, получим:
$$\tilde u_p=\left (\cos \left( \frac{(2p+1)\pi}{2N} \right), \cos \left (\frac{(2p+1)3\pi}{2N} \right ), \dots, \cos \left (\frac{(2p+1)(2N-1)\pi}{2N} \right ) \right)\\ \tilde v_p=\left (\sin \left( \frac{(2p+1)\pi}{2N} \right), \sin \left (\frac{(2p+1)3\pi}{2N} \right ), \dots, \sin \left (\frac{(2p+1)(2N-1)\pi}{2N} \right ) \right)$$Здесь р принимает значения р = 0,1,..., М - 1.
В результате мы получили семейство из N векторов в $$R^N$$. Давайте изучим их свойства.
Теорема. Вектора $$\{\tilde u_0, \tilde u_1, \dots, \tilde u_{M-1}, \tilde v_0, \tilde v_1, \dots, \tilde v_{M-1}/}$$ ортогональны друг другу и формируют базис в $$R^N$$
Прежде чем доказывать теорему, вспомним некоторые тригонометрические тождества.
При рассмотрении свойств тригонометрических функций важно все время помнить, что $$\cos(\аlpha)$$ - это Х-координата точки единичного круга, соответствующая углу $$\alpha$$, в то время как $$\sin(\аlpha)$$ - это Y-координата той же точки. Из этого определения непосредственно следуют следующие свойства:
$$\cos(-\аlpha) = \соs \аlpha, \; \sin(-\alpha) = - \sin \аlpha.$$
Только две тригонометрические формулы следует непосредственно держать в памяти:
$$\cos(\аlpha + \beta) = \cos \аlpha \cos \beta - \sin \аlpha \sin \beta,\\ \sin(\аlpha + \beta) = \sin \аlpha \cos \beta + \cos \аlpha \sin \beta.$$Все остальные тождества непосредственно выводимы. Изменяя знак $$\beta$$ в предыдущих формулах, получим:
$$\cos(\аlpha - \beta) = \cos \аlpha \cos \beta + \sin \аlpha \sin \beta,\\ \sin(\аlpha - \beta) = \sin \аlpha \cos \beta - \cos \аlpha \sin \beta.$$Комбинируя формулы, мы получим:
$$\cos(\аlpha + \beta) + \cos(\аlpha - \beta) = 2 \cos \аlpha \cos \beta,\\ \cos(\аlpha - \beta)- \cos(\аlpha + \beta) = 2 \sin \аlpha \sin \beta,\\ \sin(\аlpha + \beta) + \sin(\аlpha -\beta) = 2 \sin \аlpha \cos \beta.$$Нам понадобится следующее
Утверждение. Предположим $$\sin \аlpha \ne 0$$. Тогда
$$\cos(\аlpha) + \cos(3\аlpha) + \cos(5\аlpha) + \dots + \соs((2N - 1)\аlpha) =\frac{\sin(2N\alpha)}{2 \sin \аlpha},\\ \sin(\аlpha) + \sin(3\аlpha) + \sin(5\аlpha) + \dots + \sin((2N -1)\аlpha) =\frac{1 - \cos(2N\alpha)}{2 \sin \аlpha}$$Для доказательства первого тождества нашего утверждения умножим его слева на $$2 \sin \аlpha$$ и применим формулу для $$2 \sin \аlphac \cos \beta$$
$$2 \sin \аlpha \cos(\аlpha) + 2 \sin \аlpha \соs (3\аlpha) + 2 \sin \аlpha \cos (5\аlpha)+\dots + 2 \sin \alpha \cos((2N -1)\аlpha)\\ = (\sin(2\аlpha) - \sin(0)) + (\sin(4\аlpha) - \sin(2\аlpha)) + (\sin(6\аlpha) - \sin(4\аlpha))+\dots+ (\sin(2N\alpha)-\sin((2N-2)\аlpha)).$$Большинство слагаемых в формуле будут взаимно уничтожаться, останется только $$\sin(2N\alpha)$$. Разделив обе стороны на $$2 \sin \аlpha$$, получим первое тождество.
Доказательство второго тождества остается в качестве упражнения.
Доказательство теоремы. Для доказательства нам нужно вычислить скалярное произведение векторов нашего семейства:
$$\tilde u_p*\tilde u_s=\sum_{j=1}^{N-1}\cos \left (\frac{(2p+1)(2j+1)\pi}{2N}\right ) \cos\left ( \frac{(2s+1)(2j+1)\pi}{2N} \right )$$Применяя формулу для произведения косинусов, получим:
$$\frac12\sum_{j=0}^{N-1}\cos \left ( \frac{(2p+2s+2)(2j+1)\pi}{2N} \right )+\cos \left ( \frac{(2p-2s)(2j+1)\pi}{2N} \right )$$Далее, используя предыдущее утверждение вычислим сумму:
$$\frac12 \sum_{j=0}^{N-1}\cos\left ( \frac{(p+s+1)(2j+1)\pi}{N}\right) =\frac{\sin\left (\frac{(p+s+1)\pi}{N}\right )}{4\sin \left (\frac{(p+s+1)\pi}{N}\right )}$$Эти вычисления справедливы при условии, что синус в знаменателе не равен нулю. Это так, поскольку $$0\le p,s \le M-1$$, откуда следует, что $$0 <\frac{(p+s+1)\pi}{N} < \pi$$, следовательно, sin в знаменателе не равен нулю.
Вычисляя вторую сумму, получим:
$$\frac 12 \sum_{j=0}^{N-1} \cos \left(\frac{(p-s)(2j+1)\pi}{N}\right )=\frac{\sin\left ( \frac{(p-s)2N\pi}{N}\right )}{4\sin\left (\frac{(p-s)\pi}{N}\right)}$$Эти вычисления также справедливы при условии, что синус в знаменателе не равен нулю. Здесь знаменатель превращается в ноль только тогда, когда р = s. Заметьте, что оба числителя в этом случае также равны нулю. Следовательно, когда $$р \ne s$$ скалярное произведение $$\tilde u_p*\tilde v_s$$ равно нулю. Если р = s, то первая сумма по-прежнему равна нулю, а во второй все косинусы равны 1, так что скалярное произведение векторов равно N/2. Давайте теперь вычислим скалярное произведение $$\tilde u_p*\tilde v_s$$
Применяя формулу для $$\sin \аlpha \cos \beta$$, получим:
$$\frac12\sum_{j=0}^{N-1}\sin \left (\frac{(2p+2s+2)(2j+1)\pi}{2N}\right)+\sin \left (\frac{(2s-2p)(2j+1)\pi}{2N}\right)$$Используя второе тождество утверждения, упростим суммы:
$$\frac12\sum_{j=0}^{N-1}\sin \left( \frac{(p+s+1)(2j+1)\pi}{N}\right)=\frac{1-\cos\left(\frac{(p+s+1)2N\pi}{N}\right)}{4\sin\left(\frac{(p+s+1)\pi}{N}\right)}$$Так как синус в знаменателе не равен нулю, а числитель обращается в нуль, то сумма исчезнет. Вычисляя вторую сумму, получим:
$$\frca12\sum_{j=0}{N-1}\sin\left( \frac{(s-p)(2j+1)\pi}{N}\right )=\frac{1-\cod\left(\frac{(s-p)2N\pi}{N}\right )}{4\sin \left (\frac{(s-p)\pi}{N}\right )}$$Если $$р \ne s$$, то сумма равна нулю, но и когда р = s, то сумма также равна нулю, поскольку каждое слагаемое суммы становится равным нулю.
Мы заключаем, что $$\tilde u_p*\tilde v_s=0$$ для всех р, s. Вычисление $$\tilde u_p*\tilde v_s$$ остается в качестве упражнения.
Обобщая, имеем:
$$\tilde u_p*\tilde u_s=\tilde v_p*\tilde v_s=\begin{cases} N/2,если p=s,\\ 0,если p \ne s. \end{cases}\;\; \tilde u_p*\tilde v_s=0 \text{для любых p,s}$$Это завершает доказательство теоремы.
Для превращения базиса в ортонормальный базис, разделим каждый вектор на его длину:
$$u_p=\sqrt{\frac2N}\tilde u_p,\;\; v_p=\sqrt{\frac2N}\tilde v_p$$Так как $$\{u_0, u_1, \dots ,u_{M-1},v_0, v_1, \dots, v_{M-1)\}$$ -базис в $$R^N$$, то любой вектор $$f = (f_0,f_1, \dots, f_{N-1})$$ можно представить в этом базисе:
$$f=\sum_{p=0}^{M-1}a_pu_p+b_pv_p$$Коэффициенты $$а_р$$ и $$b_р$$ в этом выражении называются коэффициентами Фурье вектора f. Дискретное преобразование Фурье (ДПФ) - это преобразование вектора измерений в вектор коэффициентов:
Изначальный вектор измерений описывает эволюцию сигнала во времени. Каждый коэффициент Фурье соответствует некоторой частоте. Говорят, что ДПФ - это преобразование сигнала из временной области в частотную область.
Нам необходимо решить задачу представления заданного вектора f в виде линейной комбинации векторов $$\{u_0, u_1, \dots, u_{M-1}v_0, v_1, \dots, v_{M-1}\}$$. Оказывается, что задача намного проще решается, когда базис векторов является ортонормальным.
Утверждение. Пусть $$\{w_1, w_2, \dots , w_{M-1}\}$$-ортонормальный базис в $$R^N$$, пусть f - вектор в $$R^N$$. Тогда коэффициенты разложения f в линейную комбинацию векторов базиса:
могут быть найдены как скалярное произведение:
$$c_j=f*w_j\; for\; j=1,2,\dots, N$$Доказательство. Рассмотрим скалярное произведение обеих сторон линейной комбинации и вектора т:
$$f*w_j=c_1w_1*w_j+c_2w_2*w_j+\dots+c_Nw_N*w_j$$Так как базис ортонормальный, то все скалярные произведения в правой части окажутся равными нулю, за исключением произведения $$w_j*w_j$$, которое равно 1. Отсюда следует справедливость утверждения $$f*w_j=c_j$$.
Из утверждения непосредственно следуют формулы для вычисления коэффициентов Фурье:
$$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*u_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\sin \left(\frac{(2p+1)(2j+1)\pi}{2N}\right)$$Индекс р пробегает значения р = 0,1, ... , М - 1.
Если нам известны коэффициенты Фурье, то можно восстановить исходный сигнал $$f = (f_0, f_1, \dots , f_{N-1})$$. Эта процедура называется обратным преобразованием Фурье.
Так как
$$f=\sum_{p=0}^{M_1}a_pu_p+b_pv_p,$$то можно вычислить $$f_j$$, взявj-ю компоненту каждого вектора:
Как прямое, так и обратное преобразование Фурье являются линейными трансформациями $$R^N$$. При обратном ДПФ вектор (1,0,0, .. . , 0), соответствующий $$а_0 = 1$$ переходит в вектор $$u_0$$. Аналогично, образы стандартных базисных векторов $$е_k$$, являются векторами $$\{u_0, \dots ,u_{М-1}, v_0, \dots ,v_{М-1}\}$$. Так как эти вектора ортонормальны, то мы заключаем, что обратное ДПФ является ортогональной линейной трансформацией. Инверсия ортогональной линейной трансформации - ортогональна. Из этого следует, что прямое ДПФ представляет ортогональную линейную трансформацию.
Это хорошая для нас новость, поскольку это означает, что ДПФ совместимо с парадигмой квантовых вычислений. Квантовая версия ДПФ, которая называется квантовым преобразованием Фурье (КПФ) является основой алгоритма Шора. Мы представим КПФ в следующей лекции.
Величина коэффициента Фурье показывает, насколько сильно соответствующая частота представлена в сигнале. В частности, когда мы применяем преобразование Фурье к периодическому сигналу, появляются пики со значениями $$а_р$$ и $$b_p$$ в точках р, соответствующих обертонам базовой частоты сигнала. Это именно то, что мы видели в спектре диаграммы ДПФ при записи звучания флейты.
Давайте рассмотрим совсем простой пример периодического сигнала, который важен для алгоритма Шора. Зафиксируем два целых числа $$0 \le s \le m$$ и рассмотрим следующую последовательность длины N и периодом m:
Пусть N/m будет большим числом. Нетрудно видеть, что $$f_i = 1$$ для i =s + jm, где j = 0, 1, ... , L - 1. Здесь L - минимальное целое, большее или равное (N - s)/m.
Упражнение. Вычислим ДПФ для последовательности $$(f_0, f_1, \dots, f_{N-1})$$ Покажем, что коэффициенты Фурье даются следующими формулами:
$$a_p= \sqrt{\frac2N}\frac{\sin\left(\frac{(2p+1)(2s+(2L-1)m+1)\pi}{2N}\right)-\sin\left(\frac{(2p+1)(2s-m+1)\pi}{2N}\right)}{2\sin\left(\frac{(2p+1)m\pi}{2N}\right)},\\ b_p= \sqrt{\frac2N}\frac{\cos\left(\frac{(2p+1)(2s-m+1)\pi}{2N}\right)-\cos\left(\frac{(2p+1)(2s+(2L-1)m+1)\pi}{2N}\right)}{2\sin\lefr(\frac{(2p+1)m\pi}{2N}\right)}$$Подсказка. Первое утверждение этой главы может быть полезным в этих вычислениях.
Давайте проанализируем, когда коэффициенты Фурье, полученные в этом упражнении, являются большими числами. Абсолютное значение числителей в этих формулах не может быть больше чем 2, поскольку значения синуса и косинуса не превосходят 1. Единственная возможность стать большим числом - иметь маленький знаменатель $$\sin\left(\frac{(2p+1)m\pi}{2N}\right)$$ . Это происходит, когда $$\frac{(2p+1)m}{2N}$$ близко к целом числу
$$\frac{(2p+1)m}{2N}\approx K,$$Это эквивалентно тому, что
$$p\approx K*\fracNm-\frac12$$Мы видели, что пики в значениях коэффициентов Фурье расположены в точках р, кратных базовой частоте
Смещением на 1/2 можно пренебречь. Заметьте, что положение пиков определяется периодом m и не зависит от s.
ДПФ широко используется в цифровой обработке сигналов, в частности для сжатия аудио файлов (стандарт МРЗ) и изображений (JРЕG). Давайте вкратце обсудим аудио сжатие.
Для звуковой волны большая часть измерений значений сигнала далеки от нулевых значений. Если выполнить ДПФ, то большинство коэффициентов Фурье будут близки к нулю, поскольку типичная звуковая волна находится в сравнительно узком диапазоне частот. Мы можем заменить малые коэффициенты Фурье нулями и хранить только существенные коэффициенты, значительно уменьшая объем данных. Это приводит к некоторому искажению записи, но с малой потерей качества достигается большой коэффициент сжатия.
Преобразование Фурье - это математический инструмент для изучения периодических или почти периодических функций. Хорошим примером почти периодических функций является звуковая волна, порождаемая звучанием музыкального инструмента. Давайте рассмотрим простейшее музыкальное устройство - вибрирующую струну Если "щипнуть" натянутую струну, то она начнет вибрировать и ее колебания порождают колебания воздуха вокруг струны.
В результате возникает звуковая волна, периодически распространяющаяся область высокого давления воздуха, сменяющаяся областью низкого давления. Эти волны распространяются в пространстве, удаляясь от источника звука. Для записи звука используется микрофон, имеющий внутри гибкую мембрану Сразу же как звуковая волна достигает микрофона, область высокого давления заставляет мембрану сжиматься, а низкого давления - тянет мембрану в обратном направлении. Микрофон преобразует колебания мембраны в электрический сигнал, который следует движениям мембраны. В аналоговой записи звука электрический сигнал может использоваться для намагничивания ленты, так что интенсивность магнитного поля ленты воспроизводит профиль звукового сигнала. В цифровой записи звука электрический сигнал, создаваемый микрофоном, измеряется. Измерения, проводимые с заданным временным интервалом, могут сохраняться в памяти компьютера. Например, для системы записи СD (компакт дисков) измерения проводятся с частотой 44100 Герц, что означает запись 44100 измерений в секунду Величина сигнала обычно масштабируется в интервале от-1 до 1.
Давайте вернемся к обсуждению колеблющейся струны. Колеблющаяся струна издает звук с некоторой частотой, которая называется базовой частотой $$\omega$$. Оказывается, что струна может колебаться более сложным способом. Она может иметь состояния высокой вибрации с частотой $$2\omega,\; 3\omega,\; 4\omega$$ и так далее. На практике, колебание струны включает колебания высокой вибрации в дополнение к колебаниям с базовой частотой. В музыке,
состояния высокой вибрации, производимые музыкальным инструментом, называются обертонами. Распределение интенсивности обертонов - это то, что отличает один инструмент от другого, играющего одну и ту же ноту.
Ниже на рисунке представлена диаграмма звучания флейты, соответствующая примерно 0,01 секунды записи. Заметьте, что профиль почти периодический, - на диаграмме можно выделить 5 периодов.
Следующая диаграмма показывает спектр частот этой звуковой волны.
Поскольку это звук музыкального инструмента, играющего одну ноту, то диаграмма представляет пики, соответствующие базовой частоте (587 Нz; нота D второй октавы) и обертонам базовой частоты. Заметьте, для этого инструмента в частотном спектре отсутствует второй обертон.
Анализ частотного спектра сигнала, представленного выше, выполнен с использованием дискретного преобразования Фурье (ДПФ), которое мы намереваемся далее обсудить.
Давайте рассмотрим функцию $$f(t)$$, определенную на интервале $$0 \le t \le\pi$$. Мы хотим измерить f(t) в N равноудаленных точках $$t_0, t_1, t_2, \dots, t_{N-1}$$ с расстоянием между точками равным $$\frac{\pi}{N}$$. Первую точку выберем не в 0, а в середине первого интервала - в точке $$t_0=\frac{\pi}{2N}$$ . Тогда $$t_1=t_0+\frac{\pi}{N}=\frac{3\pi}{2N},\; t_2=t_1=\frac{\pi}{N}=\frac{5\pi}{2N}$$, и так далее с общей формулой:
Последняя точка будет закрывать правый конец интервала:
$$t_{N-1}=\frac{(2N-1)\pi}{2N}=\pi-\frac{\pi}{2N}$$Измеряя f(t) в этих точках получим N-компонентный вектор
где $$f_j = f (t_j)$$.
Далее будем полагать, что N четно, N = 2М.
Волны будем моделировать периодическими функциями cos(t) и sin(t). С этого момента будем полагать, что аргументы тригонометрических функций измеряются в радианах. Давайте рассмотрим семейство функций:
Мы можем записать их в более общей форме:
$$u_р(t) = \cos((2р + 1)t),\; u_p(t) = \sin((2р + 1)t),\; р = 0,1, \dots ,М - 1.$$Используя измерения в ряде точек, можно перейти от непрерывных функций к их дискретным аналогам, создавая для каждой функции N-компонентный вектор:
Аналогично, выполним эти действия и для функции $$v_p(t)$$.
Подставляя значения для точек $$t_j$$, получим:
$$\tilde u_p=\left (\cos \left( \frac{(2p+1)\pi}{2N} \right), \cos \left (\frac{(2p+1)3\pi}{2N} \right ), \dots, \cos \left (\frac{(2p+1)(2N-1)\pi}{2N} \right ) \right)\\ \tilde v_p=\left (\sin \left( \frac{(2p+1)\pi}{2N} \right), \sin \left (\frac{(2p+1)3\pi}{2N} \right ), \dots, \sin \left (\frac{(2p+1)(2N-1)\pi}{2N} \right ) \right)$$Здесь р принимает значения р = 0,1,..., М - 1.
В результате мы получили семейство из N векторов в $$R^N$$. Давайте изучим их свойства.
Теорема. Вектора $$\{\tilde u_0, \tilde u_1, \dots, \tilde u_{M-1}, \tilde v_0, \tilde v_1, \dots, \tilde v_{M-1}/}$$ ортогональны друг другу и формируют базис в $$R^N$$
Прежде чем доказывать теорему, вспомним некоторые тригонометрические тождества.
При рассмотрении свойств тригонометрических функций важно все время помнить, что $$\cos(\аlpha)$$ - это Х-координата точки единичного круга, соответствующая углу $$\alpha$$, в то время как $$\sin(\аlpha)$$ - это Y-координата той же точки. Из этого определения непосредственно следуют следующие свойства:
$$\cos(-\аlpha) = \соs \аlpha, \; \sin(-\alpha) = - \sin \аlpha.$$
Только две тригонометрические формулы следует непосредственно держать в памяти:
$$\cos(\аlpha + \beta) = \cos \аlpha \cos \beta - \sin \аlpha \sin \beta,\\ \sin(\аlpha + \beta) = \sin \аlpha \cos \beta + \cos \аlpha \sin \beta.$$Все остальные тождества непосредственно выводимы. Изменяя знак $$\beta$$ в предыдущих формулах, получим:
$$\cos(\аlpha - \beta) = \cos \аlpha \cos \beta + \sin \аlpha \sin \beta,\\ \sin(\аlpha - \beta) = \sin \аlpha \cos \beta - \cos \аlpha \sin \beta.$$Комбинируя формулы, мы получим:
$$\cos(\аlpha + \beta) + \cos(\аlpha - \beta) = 2 \cos \аlpha \cos \beta,\\ \cos(\аlpha - \beta)- \cos(\аlpha + \beta) = 2 \sin \аlpha \sin \beta,\\ \sin(\аlpha + \beta) + \sin(\аlpha -\beta) = 2 \sin \аlpha \cos \beta.$$Нам понадобится следующее
Утверждение. Предположим $$\sin \аlpha \ne 0$$. Тогда
$$\cos(\аlpha) + \cos(3\аlpha) + \cos(5\аlpha) + \dots + \соs((2N - 1)\аlpha) =\frac{\sin(2N\alpha)}{2 \sin \аlpha},\\ \sin(\аlpha) + \sin(3\аlpha) + \sin(5\аlpha) + \dots + \sin((2N -1)\аlpha) =\frac{1 - \cos(2N\alpha)}{2 \sin \аlpha}$$Для доказательства первого тождества нашего утверждения умножим его слева на $$2 \sin \аlpha$$ и применим формулу для $$2 \sin \аlphac \cos \beta$$
$$2 \sin \аlpha \cos(\аlpha) + 2 \sin \аlpha \соs (3\аlpha) + 2 \sin \аlpha \cos (5\аlpha)+\dots + 2 \sin \alpha \cos((2N -1)\аlpha)\\ = (\sin(2\аlpha) - \sin(0)) + (\sin(4\аlpha) - \sin(2\аlpha)) + (\sin(6\аlpha) - \sin(4\аlpha))+\dots+ (\sin(2N\alpha)-\sin((2N-2)\аlpha)).$$Большинство слагаемых в формуле будут взаимно уничтожаться, останется только $$\sin(2N\alpha)$$. Разделив обе стороны на $$2 \sin \аlpha$$, получим первое тождество.
Доказательство второго тождества остается в качестве упражнения.
Доказательство теоремы. Для доказательства нам нужно вычислить скалярное произведение векторов нашего семейства:
$$\tilde u_p*\tilde u_s=\sum_{j=1}^{N-1}\cos \left (\frac{(2p+1)(2j+1)\pi}{2N}\right ) \cos\left ( \frac{(2s+1)(2j+1)\pi}{2N} \right )$$Применяя формулу для произведения косинусов, получим:
$$\frac12\sum_{j=0}^{N-1}\cos \left ( \frac{(2p+2s+2)(2j+1)\pi}{2N} \right )+\cos \left ( \frac{(2p-2s)(2j+1)\pi}{2N} \right )$$Далее, используя предыдущее утверждение вычислим сумму:
$$\frac12 \sum_{j=0}^{N-1}\cos\left ( \frac{(p+s+1)(2j+1)\pi}{N}\right) =\frac{\sin\left (\frac{(p+s+1)\pi}{N}\right )}{4\sin \left (\frac{(p+s+1)\pi}{N}\right )}$$Эти вычисления справедливы при условии, что синус в знаменателе не равен нулю. Это так, поскольку $$0\le p,s \le M-1$$, откуда следует, что $$0 <\frac{(p+s+1)\pi}{N} < \pi$$, следовательно, sin в знаменателе не равен нулю.
Вычисляя вторую сумму, получим:
$$\frac 12 \sum_{j=0}^{N-1} \cos \left(\frac{(p-s)(2j+1)\pi}{N}\right )=\frac{\sin\left ( \frac{(p-s)2N\pi}{N}\right )}{4\sin\left (\frac{(p-s)\pi}{N}\right)}$$Эти вычисления также справедливы при условии, что синус в знаменателе не равен нулю. Здесь знаменатель превращается в ноль только тогда, когда р = s. Заметьте, что оба числителя в этом случае также равны нулю. Следовательно, когда $$р \ne s$$ скалярное произведение $$\tilde u_p*\tilde v_s$$ равно нулю. Если р = s, то первая сумма по-прежнему равна нулю, а во второй все косинусы равны 1, так что скалярное произведение векторов равно N/2. Давайте теперь вычислим скалярное произведение $$\tilde u_p*\tilde v_s$$
Применяя формулу для $$\sin \аlpha \cos \beta$$, получим:
$$\frac12\sum_{j=0}^{N-1}\sin \left (\frac{(2p+2s+2)(2j+1)\pi}{2N}\right)+\sin \left (\frac{(2s-2p)(2j+1)\pi}{2N}\right)$$Используя второе тождество утверждения, упростим суммы:
$$\frac12\sum_{j=0}^{N-1}\sin \left( \frac{(p+s+1)(2j+1)\pi}{N}\right)=\frac{1-\cos\left(\frac{(p+s+1)2N\pi}{N}\right)}{4\sin\left(\frac{(p+s+1)\pi}{N}\right)}$$Так как синус в знаменателе не равен нулю, а числитель обращается в нуль, то сумма исчезнет. Вычисляя вторую сумму, получим:
$$\frca12\sum_{j=0}{N-1}\sin\left( \frac{(s-p)(2j+1)\pi}{N}\right )=\frac{1-\cod\left(\frac{(s-p)2N\pi}{N}\right )}{4\sin \left (\frac{(s-p)\pi}{N}\right )}$$Если $$р \ne s$$, то сумма равна нулю, но и когда р = s, то сумма также равна нулю, поскольку каждое слагаемое суммы становится равным нулю.
Мы заключаем, что $$\tilde u_p*\tilde v_s=0$$ для всех р, s. Вычисление $$\tilde u_p*\tilde v_s$$ остается в качестве упражнения.
Обобщая, имеем:
$$\tilde u_p*\tilde u_s=\tilde v_p*\tilde v_s=\begin{cases} N/2,если p=s,\\ 0,если p \ne s. \end{cases}\;\; \tilde u_p*\tilde v_s=0 \text{для любых p,s}$$Это завершает доказательство теоремы.
Для превращения базиса в ортонормальный базис, разделим каждый вектор на его длину:
$$u_p=\sqrt{\frac2N}\tilde u_p,\;\; v_p=\sqrt{\frac2N}\tilde v_p$$Так как $$\{u_0, u_1, \dots ,u_{M-1},v_0, v_1, \dots, v_{M-1)\}$$ -базис в $$R^N$$, то любой вектор $$f = (f_0,f_1, \dots, f_{N-1})$$ можно представить в этом базисе:
$$f=\sum_{p=0}^{M-1}a_pu_p+b_pv_p$$Коэффициенты $$а_р$$ и $$b_р$$ в этом выражении называются коэффициентами Фурье вектора f. Дискретное преобразование Фурье (ДПФ) - это преобразование вектора измерений в вектор коэффициентов:
Изначальный вектор измерений описывает эволюцию сигнала во времени. Каждый коэффициент Фурье соответствует некоторой частоте. Говорят, что ДПФ - это преобразование сигнала из временной области в частотную область.
Нам необходимо решить задачу представления заданного вектора f в виде линейной комбинации векторов $$\{u_0, u_1, \dots, u_{M-1}v_0, v_1, \dots, v_{M-1}\}$$. Оказывается, что задача намного проще решается, когда базис векторов является ортонормальным.
Утверждение. Пусть $$\{w_1, w_2, \dots , w_{M-1}\}$$-ортонормальный базис в $$R^N$$, пусть f - вектор в $$R^N$$. Тогда коэффициенты разложения f в линейную комбинацию векторов базиса:
могут быть найдены как скалярное произведение:
$$c_j=f*w_j\; for\; j=1,2,\dots, N$$Доказательство. Рассмотрим скалярное произведение обеих сторон линейной комбинации и вектора т:
$$f*w_j=c_1w_1*w_j+c_2w_2*w_j+\dots+c_Nw_N*w_j$$Так как базис ортонормальный, то все скалярные произведения в правой части окажутся равными нулю, за исключением произведения $$w_j*w_j$$, которое равно 1. Отсюда следует справедливость утверждения $$f*w_j=c_j$$.
Из утверждения непосредственно следуют формулы для вычисления коэффициентов Фурье:
$$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*u_p=\sqrt{\frac2N}\sum_{j=0}^{N-1}f_j\sin \left(\frac{(2p+1)(2j+1)\pi}{2N}\right)$$Индекс р пробегает значения р = 0,1, ... , М - 1.
Если нам известны коэффициенты Фурье, то можно восстановить исходный сигнал $$f = (f_0, f_1, \dots , f_{N-1})$$. Эта процедура называется обратным преобразованием Фурье.
Так как
$$f=\sum_{p=0}^{M_1}a_pu_p+b_pv_p,$$то можно вычислить $$f_j$$, взявj-ю компоненту каждого вектора:
Как прямое, так и обратное преобразование Фурье являются линейными трансформациями $$R^N$$. При обратном ДПФ вектор (1,0,0, .. . , 0), соответствующий $$а_0 = 1$$ переходит в вектор $$u_0$$. Аналогично, образы стандартных базисных векторов $$е_k$$, являются векторами $$\{u_0, \dots ,u_{М-1}, v_0, \dots ,v_{М-1}\}$$. Так как эти вектора ортонормальны, то мы заключаем, что обратное ДПФ является ортогональной линейной трансформацией. Инверсия ортогональной линейной трансформации - ортогональна. Из этого следует, что прямое ДПФ представляет ортогональную линейную трансформацию.
Это хорошая для нас новость, поскольку это означает, что ДПФ совместимо с парадигмой квантовых вычислений. Квантовая версия ДПФ, которая называется квантовым преобразованием Фурье (КПФ) является основой алгоритма Шора. Мы представим КПФ в следующей лекции.
Величина коэффициента Фурье показывает, насколько сильно соответствующая частота представлена в сигнале. В частности, когда мы применяем преобразование Фурье к периодическому сигналу, появляются пики со значениями $$а_р$$ и $$b_p$$ в точках р, соответствующих обертонам базовой частоты сигнала. Это именно то, что мы видели в спектре диаграммы ДПФ при записи звучания флейты.
Давайте рассмотрим совсем простой пример периодического сигнала, который важен для алгоритма Шора. Зафиксируем два целых числа $$0 \le s \le m$$ и рассмотрим следующую последовательность длины N и периодом m:
Пусть N/m будет большим числом. Нетрудно видеть, что $$f_i = 1$$ для i =s + jm, где j = 0, 1, ... , L - 1. Здесь L - минимальное целое, большее или равное (N - s)/m.
Упражнение. Вычислим ДПФ для последовательности $$(f_0, f_1, \dots, f_{N-1})$$ Покажем, что коэффициенты Фурье даются следующими формулами:
$$a_p= \sqrt{\frac2N}\frac{\sin\left(\frac{(2p+1)(2s+(2L-1)m+1)\pi}{2N}\right)-\sin\left(\frac{(2p+1)(2s-m+1)\pi}{2N}\right)}{2\sin\left(\frac{(2p+1)m\pi}{2N}\right)},\\ b_p= \sqrt{\frac2N}\frac{\cos\left(\frac{(2p+1)(2s-m+1)\pi}{2N}\right)-\cos\left(\frac{(2p+1)(2s+(2L-1)m+1)\pi}{2N}\right)}{2\sin\lefr(\frac{(2p+1)m\pi}{2N}\right)}$$Подсказка. Первое утверждение этой главы может быть полезным в этих вычислениях.
Давайте проанализируем, когда коэффициенты Фурье, полученные в этом упражнении, являются большими числами. Абсолютное значение числителей в этих формулах не может быть больше чем 2, поскольку значения синуса и косинуса не превосходят 1. Единственная возможность стать большим числом - иметь маленький знаменатель $$\sin\left(\frac{(2p+1)m\pi}{2N}\right)$$ . Это происходит, когда $$\frac{(2p+1)m}{2N}$$ близко к целом числу
$$\frac{(2p+1)m}{2N}\approx K,$$Это эквивалентно тому, что
$$p\approx K*\fracNm-\frac12$$Мы видели, что пики в значениях коэффициентов Фурье расположены в точках р, кратных базовой частоте
Смещением на 1/2 можно пренебречь. Заметьте, что положение пиков определяется периодом m и не зависит от s.
ДПФ широко используется в цифровой обработке сигналов, в частности для сжатия аудио файлов (стандарт МРЗ) и изображений (JРЕG). Давайте вкратце обсудим аудио сжатие.
Для звуковой волны большая часть измерений значений сигнала далеки от нулевых значений. Если выполнить ДПФ, то большинство коэффициентов Фурье будут близки к нулю, поскольку типичная звуковая волна находится в сравнительно узком диапазоне частот. Мы можем заменить малые коэффициенты Фурье нулями и хранить только существенные коэффициенты, значительно уменьшая объем данных. Это приводит к некоторому искажению записи, но с малой потерей качества достигается большой коэффициент сжатия.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.