Быстрое преобразование Фурье (FFT) — это один из самых красивых алгоритмов из всех когда-либо созданных. Он местами сложен для понимания, но в этом видео он рассматривается в простом контексте — умножение многочленов. Шаг за шагом, задавая нужные вопросы, находятся идеи-бриллианты, расскрывая глубинную суть БПФ.
*https://www.youtube.com/watch?v=qO-HpEgmd6U
**https://300.ya.ru/v_Z1sPZP2C
таймкроды
00:00:02 Повторение фразы
- Фраза «посмотри на себя в зеркало» повторяется несколько раз.
00:04:51 Невозможность логарифмировать
- Упоминается невозможность логарифмировать обратное проектирование.
00:18:26 Технические термины
- Перечисляются различные технические термины, включая BPFF, FFT, BPF и другие.
00:23:54 Повторение «омега»
- Многократное повторение слова «омега».
00:26:43 Завершение
- Выражение недовольства: «мне это не нравится».
В этом видео
Введение
0:02
Мир алгоритмов широк, но часто их можно
0:05
разделить на два разных класса. Первый
0:07
класс — это те, которые по определению
0:09
полезны. Подумайте о стандартных
0:11
графовых алгоритмах, таких как DFS или
0:13
BFS. Такие алгоритмы появляются повсюду.
0:16
Они эффективно, и поэтому нам нравится
0:18
понимать их. Второй класс алгоритмов,
0:20
который мы изучаем — это просто чисто
0:23
красивые. Вспомните, как вы впервые
0:25
увидели невероятно простую рекурсивную
0:27
реализацию ханойских башен. Если у вас
0:29
есть душа, то вы испытали чувство
0:31
удивления, чувство благоговейного
0:33
трепета. Несмотря на элегантность такого
0:35
алгоритма, на самом деле он не так уж
0:37
полезен или эффективен, но мы всё равно
0:39
изучаем его так же, как читаем
0:41
художественное произведение. Это
0:43
вдохновляет нас и мотивирует к
0:45
нестандартному мышлению. Сегодня я хочу
0:47
поговорить об алгоритме, который по
0:49
праву относится к обоим классам и о
0:51
любимом многими алгоритме быстром
0:53
преобразовании фурье.
0:56
Быстрое преобразование фурье или БПФ без
0:59
привлечения является одним из самых
1:01
важных алгоритмов, созданных в прошлом
1:02
веке. Большая часть современных
1:04
технологий, которые мы располагаем
1:06
сегодня, таких как беспроводная связь,
1:08
GPS и фактически всё, что связано с
1:11
обширной областью обработки сигналов,
1:13
основано на идеях БПФ. Кроме того, это
1:16
один из самых красивых алгоритмов,
1:18
которые вы когда-либо видели. Глубина и
1:20
огромное количество блестящих идей,
1:21
заложенных него, просто поражают. легко
1:24
упустить из виду красоту БПФ, поскольку
1:27
он часто используется в довольно сложных
1:28
задачах, требующих больших
1:30
предварительных знаний, таких как
1:32
дискретное преобразование фулье,
1:34
преобразование временной области в
1:35
частотную и многое другое. И, честно
1:38
говоря, чтобы в полной мере оценить
1:40
возможности применения БПФ, вы не
1:42
сможете избежать ни одной из этих идей.
1:44
Но я хочу сделать кое-что немного
1:46
по-другому. Мы используем
1:48
исследовательский подход в изучении БПФ
1:50
в контексте, который вам всем знаком с
1:52
полиномиальным умножением. Я вижу
1:55
структуру этого видео примерно так:
1:56
начать с какой-то общей точки зрения, а
1:59
затем медленно задавать вопросы,
2:01
которые, надеюсь, помогут вам открыть
2:03
для себя поистине гениальные идеи,
2:05
лежащие в основе быстрого преобразования
2:07
фурье. Хорошо, давайте начнём.
Небольшая ремарка
2:11
Небольшая ремарка. ФТ — это английская
2:14
аббревиатура БПФ. Даже в русскоязычной
2:16
литературе часто можно заметить именно
2:18
FFTТ, а не БПФ. Поэтому это стоит
2:20
запомнить. Начало здесь простое. Нам
Умножение многочленов
2:23
даны два многочленна, и мы хотим найти
2:25
произведение. Наша задача будет
2:27
заключаться в разработке эффективного
2:28
алгоритма для решения этой задачи.
2:31
Математически мы знаем один алгоритм для
2:32
умножения многочленов. Это многократное
2:35
применение свойства дистрибутивности.
2:37
Все вы, возможно, инстинктивно применяли
2:39
этот алгоритм на уроках математики ещё
2:41
до того, как мы попробовали эту идею. Но
2:44
вообще первый вопрос, который мы должны
2:45
решить — это представление многочленов в
2:47
компьютере. Наиболее естественным
2:49
способом их представления являются
2:51
коэффициенты. В компьютере же мы
2:53
сопоставляем коэффициенты со списками.
2:55
Это помогает расположить наши
2:57
коэффициенты в следующем порядке.
2:58
Главным образом потому, что теперь
3:00
коэффициент катого индекса
3:02
сопоставляется с коэффициентом члена
3:04
катой степени. Мы будем называть это
3:07
представление многочлена, представление
3:09
коэффициентами.
3:14
В общем случае, при наличии двух
3:15
многочленов степени D произведение будет
3:17
иметь степень 2D. И время выполнение
3:20
этого алгоритма, если реализация с
3:22
помощью простой дистрибутивности будет
3:24
равно OD², поскольку каждый член
3:27
многочления а должен быть умножен на все
3:30
члены в многочлени B. Теперь возникает
3:32
вопрос: можно ли сделать лучше?
Представления многочленов
3:36
Первое. По-настоящему умная идея
3:38
возникает, когда мы немного по-другому
3:40
смотрим на многочленное. Чтобы увидеть
3:42
ключевой концепт здесь, давайте взглянем
3:44
на один из простейших многочленов.
3:46
Многочлен первой степени или линейная
3:48
функция. Мы можем представить любую
3:50
линию ровно с двумя коэффициентами. Один
3:52
для свободного члена, один для
3:54
коэффициента при переменной. Ключевая
3:56
часть, которая делает это представление
3:58
допустимым, заключается в том, что
4:00
каждое представление имеет взаимно
4:02
однозначное отображение на уникальную
4:03
линию. Но какие другие представления
4:06
линий обладают этим свойством? На самом
4:08
деле существует несколько разумных
4:10
представлений. Но то, которое мы
4:12
собираемся использовать — это
4:13
представление двумя точками. Из
4:15
геометрии мы знаем, что любая прямая
4:17
может быть представлена двумя различными
4:19
точками. И оказывается, что у этого есть
4:22
изящное продолжение для любого
4:24
многочлена. Любой многочлен в степени d
4:27
может быть однозначно представлен d +
4:30
одной точкой. Например, если я дал вам
4:32
три случайные точки, это означает, что
4:34
существует ровно одна квадратичная
4:36
функция, которая проходит через все три
4:38
точки. Если я дам вам четыре точки,
4:41
существует ровно одна кубическая
4:43
функция, проходящая через все эти точки.
4:46
Это утверждение, возможно, немного
4:47
удивительно, поэтому заслуживает
4:49
доказательства. Предположим, я даю вам d
4:51
одну уникальную точку многочлена пи dТ
4:53
степени от x. Мы хотим показать, что для
4:56
этого набора точек существует только
4:57
один набор коэффициентов. Итак, если мы
5:00
действительно вычислим наш многочлен в
5:01
каждой из этих точек, то получим
5:03
следующий набор уравнений. Всякий раз,
5:05
когда у вас есть система уравнений, её
5:07
запись в виде матричного векторного
5:09
произведения почти всегда полезна для
5:11
анализа. Одним из приятных свойств этой
5:13
матрицы является то, что если каждая из
5:15
наших исходных точек уникальна, как в
5:17
данном случае, то матрица всегда будет
5:19
обратимой. Самый простой способ показать
5:22
это — это вычислить определитель,
5:24
который, как вы обнаружите, отличен от
5:25
нуля. Но я также приведу хорошее
5:27
линейное алгебраическое доказательство
5:29
этого факта в описании для тех, кто
5:31
заинтересован. В любом случае это
5:33
означает, что для каждого набора точек
5:35
существует уникальный набор
5:37
коэффициентов и, следовательно,
5:39
уникальный многочлен. Если сделать шаг
5:42
назад, то это означает, что на самом
5:44
деле существует два способа
5:46
представления многочленов в степени d.
5:48
Первый из которых является привычным
5:50
представлением коэффициентами, а второй
5:53
всего лишь d + одной точкой, которую мы
5:56
будем называть представление значениями.
6:00
Приятным свойством использования
6:02
представления значениями является то,
6:04
что умножать многочлены намного проще.
Преимущества представления с помощью значений
6:07
Допустим, я попрошу вас умножить эти два
6:10
многочлена a отx и bx. Мы знаем, что
6:13
результирующий многочлен cx будет
6:15
четвёртой степени, поэтому нам
6:17
понадобится пять точек, чтобы однозначно
6:19
представить результат. Теперь мы можем
6:21
взять по пять точек от каждого из двух
6:23
многочленов, а затем просто умножить
6:26
значение функции одно на другое, чтобы
6:29
получить произведение двух многочленов в
6:31
виде представления значениями. Следуя
6:33
нашему предыдущему правилу, через эти
6:35
точки проходит только один многочлен
6:38
четвёртой степени. Этот многочлен имеет
6:40
следующий вид в представлении
6:42
коэффициентами. И это действительно
6:44
произведение наших исходных многочленов
6:46
A отx и b отx. Поскольку операция
6:48
умножения выполняется в представлении
6:50
значениями, мы теперь сократили время
6:53
умножения с наших исходных операций OD d
6:55
квадрате до порядка операции от D.
Схема умножения многочленов
7:00
Итак, давайте предложим план
7:02
усовершенствования метода
7:03
полиномиального умножения.
7:06
Нам даны два многочленной степени D
7:08
каждый в коэффициентном представлении.
7:10
Мы знаем, что умножение выполняется
7:12
быстрее при использовании представления
7:13
значениями. Поэтому всё, что мы сделаем
7:15
это оценим каждый из этих многочленов
7:18
в D плюс одной точке. Умножим каждую из
7:20
этих точек попарно, чтобы получить
7:22
произведение многочленов представлений
7:24
значениями. И затем, наконец, каким-то
7:27
образом преобразуем многочленность
7:29
представления значениями обратно в
7:31
конечное представление коэффициентами.
7:33
Это грандиозный план, но есть несколько
7:35
частей головоломки, которые мы ещё не
7:37
разгадали. Чего нам на самом деле не
7:39
хватает, так это какой-то волшебной
7:40
шкатулки, которая могла бы принимать
7:42
многочленно в коэффициентном
7:43
представлении и преобразовывать их
7:45
представление значениями, а затем
7:47
наоборот. Это волшебная шкатулка, друзья
7:49
мои, и, поверьте, она действительно
7:51
волшебная. Это быстрое преобразование
7:53
фурье.
7:56
Давайте сначала сосредоточимся на
7:58
преобразовании многочленов из
7:59
коэффициентного представления
8:00
представления значениями, которое мы
8:02
будем называть для простоты вычислением.
Вычисление значений многочленов
8:05
У нас есть многочлен в степени d, и мы
8:07
хотим вычислить этот многочлен в n
8:09
точках, где n некоторое число большее
8:11
или равное, чем d +1. Давайте подумаем о
8:14
самом простом способе сделать это. Мы
8:16
можем выбрать n случайных координат x и
8:19
просто вычислить соответствующую
8:20
координату y. Это работает. Но когда мы
8:24
разбираем, что на самом деле здесь
8:25
происходит, мы сталкиваемся с нашим
8:27
старым врагом. Для получения каждого
8:29
значения требуется ОD операции, что
8:32
приводит к тому, что этот метод
8:33
выполняется за O от N d, что в конечном
8:36
итоге равно OD d² для вычисления всех
8:38
конечных точек. Мы вернулись к тому, с
8:40
чего мы начали. Но можем ли мы найти
8:42
способ оптимизировать это?
8:46
Что ж, давайте попробуем упростить
8:48
задачу. Допустим, вместо рассмотрения
8:50
общего многочлена мы хотели бы просто
8:52
вычислить простой многочлен типа px = x²
8:55
8 точках. Теперь вопрос в том, какие
8:58
точки нам следует выбрать. Существует ли
9:00
какой-то набор точек, когда знание
9:02
значения одной точки немедленно
9:04
подразумевает значение другой? Конечно
9:07
же, на самом деле такие точки
9:08
существуют.
9:10
Если мы выберем точку x рав 1,динице, мы
9:13
сразу узнаем значение в точке -1.
9:15
Аналогично, если мы выберем x = 2, мы
9:18
автоматически узнаем значение в точке
9:20
-2. Развивая эту идею, ключевым
9:22
свойством, которое нам нужно, является
9:24
то, что наши восемь точек должны быть
9:26
положительно отрицательными парами.
9:28
Причина, по которой это работает,
9:30
заключается в свойстве чётных функций,
9:32
когда функция, вычисленная при
9:33
отрицательном x, будет равна функции,
9:35
вычисленной при положительном x. Хорошо?
9:38
Но тогда возникает следующий вопрос: а
9:40
как насчёт таких функций, как x³?
9:42
Работает ли тот же трюк? На самом деле,
9:44
да, но с одной оговоркой. Каждое
9:46
положительное значение x будет иметь то
9:48
же значение, что и отрицательное
9:50
значение x, но с другим знаком. Таким
9:52
образом, в этих двух случаях
9:54
односоставных многочленов нечётной и
9:56
чётной степеней вместо оценки восьми
9:58
отдельных точек мы фактически можем
10:01
обойтись оценкой только четырёх
10:03
положительных точек, из которых мы уже
10:05
сразу узнаём значение соответствующих
10:07
отрицательных точек.
10:11
Давайте посмотрим, сможем ли мы
10:12
распространить эту идею на более общий
10:14
многочлен. Вдохновляясь нашими ранними
10:17
исследованиями, давайте разделим наш
10:18
многочлен на члены чётной и нечётной
10:21
степеней. Если мы выделим x из членов
10:23
нечётной степеней, то в итоге получим
10:25
два новых многочлена, где эти новые
10:27
многочлены имеют только члены чётной
10:29
степени. Давайте на самом деле дадим
10:31
этим многочленам официальные названия,
10:33
первый из которых представляют чётные
10:35
члены even terms, а второй нечётные от
10:37
terms раскрытия скобок. Этот факт
10:40
позволяет нам повторно использовать
10:42
множество вычислений между
10:43
положительными и отрицательными парами
10:45
точек. Дополнительным фактом является
10:46
то, что поскольку эти чётные, нечётные
10:48
многочлены являются функциями от x², они
10:51
являются многочленами второй степени,
10:53
что является гораздо более простой
10:55
задачей, чем наш первоначальный
10:56
многочлен пятой степени.
10:59
Обобщим эти наблюдения. Если у нас есть
11:01
многочлен в степени n — 1, который мы
11:03
хотим оценить в n точках, мы можем
11:05
разделить многочлен на чётные и нечётные
11:07
члены. И теперь эти два меньших
11:09
многочлена будут иметь степень n пополам
11:11
-1. Итак, как мы можем оценить эти
11:14
многочлены с половиной степени нашего
11:16
исходного многочлена? Что ж, что здесь
11:18
прекрасно, так это то, что это всего
11:20
лишь ещё одна задача вычисления. Но на
11:23
этот раз нам нужно вычислить полиномы
11:24
для каждого из наших исходных входных
11:26
данных в квадрате. И это прекрасно
11:28
работает, поскольку наши исходные точки
11:30
были парами положительных и
11:32
отрицательных значений. Так что если
11:34
изначально у нас было n точек, то теперь
11:36
у нас будет n пополам. Это начинает
11:38
смахивать на начало рекурсивного
11:39
алгоритма. Давайте взглянем на картину в
11:42
целом. Мы хотим вычислить многочен пи от
11:45
x в конечных точках, где конечные точки
11:47
имеют положительно отрицательные пары.
11:50
Мы разделили многочленно компоненты
11:51
нечётной и чётной степеней. И теперь у
11:53
нас есть два более простых многочлена
11:55
степени n пополам -1. Как только мы
11:58
рекурсивно вычислим эти меньшие
12:00
многочлены, мы сможем посмотреть на
12:02
каждую точку в нашем исходном наборе
12:04
конечных точек и вычислить
12:05
соответствующее значение, используя
12:07
взаимосвязь между положительно
12:09
отрицательными парами точек. Это даёт
12:12
нам представление значениями нашего
12:14
исходного полинома. Если мы сможем
12:16
заставить это работать, это будет
12:18
означать, что у нас есть рекурсивный
12:19
алгоритм ОАНГо операции, поскольку две
12:22
рекурсивные подзадачи имеют двое меньше
12:23
размер, чем исходная, и для вычисления
12:26
конечных точек требуется линейное время.
12:28
Это было бы огромным улучшением по
12:30
сравнению с нашим предыдущим
12:31
квадратичным временем выполнения. Но
12:34
есть одна серьёзная проблема. Можете ли
12:36
вы определить её?
12:39
Проблема возникает на этапе рекурсии.
12:41
Вся схема основана на том факте, что
12:43
многочлен будет иметь положительно
12:45
отрицательные пары точек для вычисления.
12:47
Это работает на верхнем уровне, но на
12:49
следующем уровне мы оцениваем n пополам
12:51
точек, где каждая точка представляет
12:53
собой квадратичное значение. Все они в
12:55
конечном итоге оказываются
12:57
положительными. Таким образом рекурсия
12:59
прерываются и возникает естественный
13:01
вопрос: можем ли мы соединить эти новые
13:04
точки в положительноотрицательные пары?
13:07
Некоторые из вас, возможно, уже поняли
13:09
это, но на самом деле это приводит к
13:11
третьей абсолютно гениальной идее,
13:12
лежащей в основе БПФ. Это возможно
13:15
только в том случае, если мы расширим
13:17
область возможных начальных точек,
13:19
включив в неё комплексные числа. Для
13:22
специального выбора комплексных чисел
13:24
рекурсивное соотношение работает
13:25
идеально, когда каждый последующий набор
13:28
точек будет содержать пары положительных
13:30
и отрицательных значений.
13:33
Но какой возможно набор начальных точек
13:35
обладает этим свойством?
13:37
Это сложный вопрос, и чтобы ответить на
13:39
него, мы проведём небольшой версненеринг
13:41
на примере. Допустим, у нас есть
Какие точки вычислять?
13:43
многочен третьей степени, для
13:45
представления значений которого
13:46
требуется как минимум n равное четырём
13:48
точкам. Эти точки должны быть
13:50
положительно отрицательными парами,
13:51
чтобы мы могли записать их как x1 — x1,
13:54
x2 — x2.
13:58
Мы знаем, что рекурсивный шаг потребует,
13:59
чтобы мы вычислили нечётную и чётную по
14:01
степени части многочлена в двух точках
14:04
x1² и x2². Теперь ключевым ограничением
14:08
здесь является то, что для того, чтобы
14:09
рекурсия сработала, эти две точки также
14:12
должны быть положительно отрицательной
14:13
парой. Поэтому у нас есть
14:15
эквивалентность между x2² и — x1².
14:20
На нижнем уровне рекурсии будет 1 то1 в
14:23
степени 4.
14:25
Теперь, что приятно, мы можем выбирать
14:27
эти точки. Давайте посмотрим, что
14:29
произойдёт, если мы выберем наш
14:31
начальный x1 равным 1. Это означает, что
14:34
две наший точки равны 1 и -1, что на
14:37
следующем уровне рекурсии x1² и -x1²
14:41
также должны быть равны 1 и -1,
14:44
соответственно. И в нижнем слое у нас
14:46
есть только одна точка, которая в
14:48
конечном итоге равна 1. Теперь возникает
14:51
вопрос, какое значение x2 мы должны
14:53
выбрать, чтобы при произведении x2² мы
14:56
получили -1? Ответом на этот вопрос
14:59
является мнимая единица. То есть четыре
15:01
точки, которые нам нужны для вычисления
15:03
этого многочлена — это 1, -1, i и -i.
15:07
Ii.
15:09
Альтернативный подход к тому, что мы
15:10
только что сделали, заключается в том,
15:12
что мы, по сути, просто решили уравнение
15:14
x вче степени равно 1, поскольку на
15:17
нижнем уровне рекурсии значение любой из
15:19
наших исходных точек в степеничетыре
15:21
было равно единице. Мы знаем, что это
15:23
уравнение имеет четыре решения, каждое
15:25
из которых определяется особым набором
15:27
точек, называемых корнями четвёртой
15:29
степени из единицы. Давайте посмотрим,
15:32
можно ли это обобщить.
15:35
Если задан многочлен пятой степени, нам
15:37
потребуется, чтобы n было больше или
15:39
равно шести. Так как наш рекурсивный
15:41
метод разбивает каждую задачу пополам,
15:43
удобно просто выбрать степень двойки.
15:46
Поэтому давайте выберем, что n = 8.
15:48
Теперь нам нужно найти восемь точек,
15:50
которые имеют положительно отрицательную
15:52
пару. Так что каждая из этих точек при
15:54
возведении в восьмую степень равна
15:56
единице. Мы видим, что правильные точки
15:58
это корни восьмой степени из единицы.
16:01
Обобщая это на любой многочлен степени
16:03
d, мы выберем, что n больше или равно d
16:06
одной точке, так что n — это степень
16:08
двойки, а точки, которую мы должны
16:10
выбрать, являются корнями nной степени
16:13
из единицы. Этот факт заслуживает более
16:15
подробного объяснения, почему это
16:17
работает. Но прежде, чем мы ответим на
16:19
этот вопрос, давайте сформулируем
16:21
несколько моментов. Корни и степени из
Почему корни N-ой степени из единицы?
16:23
единицы являются решением следующего
16:25
уравнения. Их лучше всего представить в
16:28
виде точек, расположенных на одинаковом
16:29
расстоянии друг от друга на единичной
16:31
окружности. Угол между этими точками
16:33
равен 2 пи на n. Учитывая этот факт,
16:36
хорошим способом компактного написания
16:38
этих точек является экспоненциальная
16:40
запись с помощью формулы. Один из
16:42
стандартных способов определения корней
16:44
числа один заключается в определении так
16:46
называемого омега-члена, как i, в
16:49
степени 2 пи на i по n. И это позволяет
16:52
нам довольно компактно определять
16:54
отдельный корни из числа один. Вот
16:56
несколько примеров.
17:00
Итак, теперь, когда мы говорим, что
17:02
хотим вычислить многочлен с корнями
17:04
степени из единицы, на самом деле это
17:06
означает, что мы хотим вычислить его с
17:08
омега в степени 0, омегой в степени 1 и
17:11
так далее, пока омега не будет в степени
17:13
n — 1.
17:17
Итак, вернёмся к нашему первоначальному
17:19
вопросу о том, почему вычисление
17:21
многочлена πx в корнях nной степени из
17:23
единицы работает для нашего рекурсивного
17:25
алгоритма. Есть два ключевых свойства,
17:28
которые здесь играют. Во-первых, наш
17:29
исходный набор точек состоит из
17:31
положительно отрицательных пар, где для
17:33
корня g этой степени омега в степени g
17:36
омега в степени g + n пополам будет
17:38
соответствующей парой.
17:42
Теперь на нашем рекурсивном шаге мы
17:44
возведём в квадрат каждую из этих точек
17:46
и преобразуем их в полиномы чётной и
17:47
нечётной степеней. Вот что происходит,
17:49
когда мы возводим в квадрат наши
17:51
исходные n коне из единицы.
17:54
Это раскрывает второе ключевое свойство
17:56
корней наной степени из единицы. Когда
17:59
мы возводим n корней из единицы в
18:00
квадрат, мы получаем n пополам корней из
18:02
единицы, которые также являются
18:04
положительно отрицательными парами и
18:06
являются как раз подходящим количеством
18:08
точек для двух новых многоченнов
18:10
половиной степени. Эта же схема
18:12
сохраняется на каждом уровне рекурсии,
18:14
пока в итоге мы не получим только одну
18:16
точку. Насколько это чертовски красиво?
Реализации FFT (БПФ)
18:22
Итак, теперь мы готовы изложить суть
18:24
алгоритма быстрого преобразования фурье.
18:26
Бpф будет использовать представление
18:28
коэффициентами для многочлена степени n
18:31
1, где n в степень двойки. Мы
18:34
определим омегу как i в степени 2 пи на
18:36
i по n, что позволит нам легко
18:38
определять корни из единицы. Первый
18:41
случай, который нам нужно обработать —
18:43
это базовый случай, который будет иметь
18:45
место, когда n равно 1. Всё это
18:47
означает, что мы вычисляем многочлен в
18:49
одной точке. Рекурсивный случай — это
18:52
два обращения к БПФ. Цель состоит в том,
18:54
чтобы эти многочлены теперь были в два
18:56
раза меньше нашего исходного многочлена,
18:58
поэтому их нужно будет вычислять только
19:00
в n пополам корней из единицы.
19:02
Предполагая, что рекурсия работает,
19:04
результатом этих вызовов будет
19:06
соответствующее представление значениями
19:07
этих полиномов чётной и нечётной
19:09
степеней, которые мы обозначим как Y и
19:12
Y.
19:14
Теперь перейдём к сложной части, которая
19:16
заключается в том, чтобы взять выходные
19:18
данные этих рекурсивных вызовов и
19:20
объединить их, чтобы получить
19:22
представление значениями нашего
19:24
исходного многочленной степени n — 1.
19:26
Ранее мы видели, что ключевой идеей было
19:28
использовать взаимосвязь положительно
19:30
отрицательных пар. Но теперь нам нужно
19:32
немного изменить эту логику для наших
19:34
входных корней из единицы. В качестве
19:36
краткого замечания, да, я изменил
19:38
индексацию на нулевую, потому что мы
19:40
готовимся к написанию некоторого кода.
19:43
Мы знаем, что gt входная точка будет
19:45
соответствовать корню gТ степени
19:47
единицы, что приводит к следующему
19:49
соотношению.
19:51
Ранее мы также видели, что парная точка
19:53
с отрицательной омегой в степени g равна
19:55
омеги в степени g + n пополам благодаря
19:57
свойствам корней из единицы. Используя
20:00
этот факт, мы можем изменить второе
20:02
уравнение следующим образом.
20:06
И, наконец, ещё один факт. Приятно то,
20:08
что индекс g в нашем списке Y и Y
20:11
соответствует чётным и нечётным
20:13
многочленам, вычисленным в омега в
20:15
степени 2G. Это позволяет нам переписать
20:18
наше уравнение следующим образом, что
20:20
значительно упрощает реализацию кода.
20:23
Как уже упоминалось, эта часть довольно
20:24
сложная, поэтому я рекомендую вам не
20:26
торопиться и убедиться, что каждый из
20:28
этих шагов действительно выполняется.
20:31
Заключительный шаг алгоритма BPФ
20:33
заключается в том, чтобы вернуть
20:34
значение полинома пи, вычисленные в
20:36
корнях ной степени из единицы.
20:40
Давайте теперь переведём эту общую
20:42
логику в код. Наша функция fт будет
20:45
принимать пи, который представляет собой
20:47
коэффициенты многочлена пи. Сначала мы
20:50
определим n как длину пи и предположим,
20:52
что n — это степень двойки. Просто для
20:55
ясности существует реализация БП, в
20:57
котором могут обрабатывать числа N, не
21:00
являющиеся степенью двойки, но они
21:02
намного сложнее. В случае со степенями
21:04
двойки вполне покрывают основные идеи и
21:06
алгоритмы. Теперь мы рассматриваем
21:09
базовый вариант, который заключается
21:11
всего лишь в возвращении нашего
21:12
исходного пи. Это имеет смысл, поскольку
21:15
у нас есть только один элемент, делающий
21:17
пи полиномом нулевой степени или
21:19
константой. В противном случае мы
21:21
определяем омега, как мы описали, а
21:23
затем переходим к рекурсивному шагу.
21:25
Первая часть рекурсивного шага требует
21:27
разделения полинома в чётной и нечётной
21:29
степенях, что довольно легко сделать.
21:31
Затем мы рекурсивно вызываем нашу
21:33
функцию f(ФТ для этих многочленов,
21:35
которые теперь имеют половину от степени
21:37
нашего исходного многочлена. Мы
21:39
обозначаем выходные данные как y и y,
21:43
как это делали в схеме. Теперь пришло
21:45
время собрать всё это воедино. Мы
21:47
инициализируем наш выходной список,
21:49
который будет содержать конечное
21:50
представление значениями. Затем для всех
21:52
значений g n пополам мы вычисляем
21:55
представление значениями, как мы
21:57
описали. Заполнив все значениями в нашем
21:59
списке, мы возвращаем этот список. И это
22:02
и есть БПФ в целом. Довольно странно,
22:04
что все идеи, о которых мы говорили, в
22:06
конечном итоге объединяются в 11 строк
22:08
по-настоящему элегантного кода. Давайте
22:11
теперь подробно рассмотрим нашу исходную
22:12
схему и посмотрим, где мы находимся.
22:14
Теперь у нас есть способ эффективно
22:15
преобразовывать коэффициентные
22:17
представления в представлении значениями
22:18
с помощью БПФ. Итак, теперь единственным
22:20
недостающим элементом является обратный
22:22
процесс преобразования с представления
22:24
значениями в коэффициентное
22:25
представление, которое формально
22:27
называется интерполяцией.
22:30
Вот тут всё и становится по-настоящему
Интерполяция и обратное FFT (БПФ)
22:32
тяжёлым. Ведь на первый взгляд идея
22:33
обратного перехода кажется значительно
22:35
более сложной задачей. Давайте сделаем
22:37
шаг назад и посмотрим на эту проблему с
22:39
другой точки зрения. Вычисление,
22:41
интерполяция тесно связано. И как мы
22:43
видели ранее, мы можем выразить
22:44
вычисление в виде матричного векторного
22:46
произведения. У нас есть вектор
22:48
коэффициентов, умноженный на матрицу
22:50
наших точек, чтобы получить
22:51
представление значениями. Теперь в
22:53
алгоритме БПФя точка была
22:55
соответствующим корнем из единицы, что
22:57
позволяло нам переписать
22:58
матрично-векторное произведение
23:00
следующим образом. В большинстве
23:02
учебников и справочных материалов эта
23:04
конкретная матрица имеет специальное
23:06
название дискретное преобразование фурье
23:08
или матрица ДП. БПФ по сути является
23:11
алгоритмом для эффективного вычисления
23:12
этих типов матрично-векторных
23:14
произведений. Вычисление в корнях из
23:16
единицы — это один из случаев, когда
23:18
появляется этот тип матрично-векторного
23:20
произведения. Вот почему мы можем
23:22
использовать БПФ.
23:26
В любом случае приятный факт обф в этом
23:28
контексте заключается в том, что
23:30
интерполяция намного проще для
23:31
понимания. Для интерполяции требуется
23:34
инвертировать эту матрицу ДП. Нам дано
23:37
представление значениями нашего
23:38
многочлена. И мы хотим найти
23:40
коэффициентное представление, что
23:42
означает, что мы должны умножить
23:43
представление значениями на величину,
23:45
обратную матрицы DPF.
23:48
Итак, позвольте мне показать вам, как
23:49
выглядит обратная матрица к этой. Я
23:52
намеренно пропускаю здесь много важных
23:53
фактов по линейной алгебре, поскольку
23:55
это было бы совершенно другое видео. Но,
23:57
учитывая, что это обратная матрица, что
23:59
вас удивляет?
24:02
Это действительно удивительно, но эта
24:04
обратная матрица выглядит почти так же,
24:06
как наша оригинальная матрица DPF.
24:08
Фактически единственное отличие
24:10
заключается в том, что каждая отдельная
24:12
омега в нашей исходной матрице ДП теперь
24:14
просто заменена на омегу в степени
24:16
мину1дини и с коэффициентом нормализации
24:19
1 на n. Это указывает на возможность
24:22
повторного использования логики БПФ для
24:24
интерполяции, поскольку структура
24:26
матрицы в основном та же. Давайте
24:28
формализуем предположение, выполнив
24:30
прямое сравнение. При вычислении с
24:32
использованием БПФ нам задан набор
24:34
коэффициентов, и мы вычисляем многочлен
24:36
в корнях из единицы, чтобы получить
24:38
представление значениями. Это включало в
24:40
себя следующее матрично-векторное
24:42
произведение, где мы определяем омега
24:44
как i в степени 2 i / n. Рассматривая
24:48
интерполяцию, мы теперь хотим определить
24:50
то, что формально называется обратным
24:52
алгоритмом BPF. Обратный алгоритм БПФ
24:54
будет использовать представление
24:56
значениями, в котором каждое значение
24:58
вычислялось в корнях из единицы, и даст
25:00
нам набор коэффициентов для исходного
25:02
многочлена, в основном изменяющих то,
25:04
что делал исходный метод БПФ. Как мы
25:07
только что видели, для этого требуется
25:08
умножение на величину обратную матрицы
25:10
DPF. Мы отметили, что каждая омега в
25:13
нашей исходной матрице DPF теперь
25:15
соответствует 1 на N омега в степени -1.
25:19
Теперь суть в том, что это означает, что
25:21
мы можем определить обратный БПФ как ту
25:23
же функцию BPF, но теперь вызываемую для
25:25
представления значениями с омегой,
25:28
определённой как 1 на n, у i в степени —
25:31
пи/ n. Вот и всё. Благодаря этим
25:35
небольшим изменениям у нас появился
25:37
обратный БПФ, который выполняет
25:39
интерполяцию. Чтобы нам было предельно
25:42
ясно, что за волшебство только что
25:43
произошло, позвольте мне напомнить об
25:45
оригинальной реализации БПФ. И теперь
25:48
позвольте мне показать вам обратную
25:50
реализацию БПФ, которая использует
25:52
представление значениями в качестве
25:54
входных данных. Что мы буквально делаем,
25:56
так это копируем нашу реализацию БПФ,
25:59
меняем название рекурсивных вызовов на
26:01
соответствующее, а затем буквально
26:03
изменяем одну строчку кода, одна строка,
26:06
и всё, в этом есть смысл. Так что если у
26:09
вас всё в порядке с головой, значит, вы
26:11
не поняли. Давайте взглянем на то, что
Резюме
26:14
мы только что сделали. Мы использовали
26:16
БПФ для решения задачи умножения
26:17
полиномов, где первая блестящая идея
26:19
заключалась в умножении многочинов с
26:21
использованием представления значениями.
26:23
Преобразование многочленов представления
26:25
значениями требовало от нас
26:27
соответствующего набора подходящих
26:29
точек. Наши первые попытки решить эту
26:31
проблему вдохновили нас на умную идею
26:33
использования положительно отрицательных
26:35
пар. Но рекурсия не сработала полностью,
26:37
пока мы не расширили область применения
26:39
до комплексных чисел. Следующая
26:41
блестящая идея возникла в результате
26:43
использования корней ной степени из
26:45
единицы, где точки на каждом уровне
26:47
рекурсии объединены в пару плюс-минус.
26:49
Эта схема вычисления с использованием
26:51
корней из единицы отражает суть
26:53
алгоритма БПФ. Столкнувшись с проблемой
26:56
обращения процессов с пять с помощью
26:57
интерполяции, мы обнаружили нечто
27:00
поистине поразительное. Обратный БПФ —
27:02
это тот же алгоритм, но с одной
27:04
незначительной поправкой. Итак, если мы
27:06
взглянем на то, что мы только что
27:08
сделали, то обнаружим не одну, не две,
27:11
не три, а четыре абсолютно с
27:13
ногшибательные идеи, которые
27:14
объединяются, чтобы БПФ работало. Мне
27:17
действительно нужно больше говорить о
27:18
том, почему это любимый многими
27:20
алгоритм? На этом видео всё. Спасибо за
27:23
просмотр. Вы можете поддержать видео
27:25
лайком и подписаться на канал.
27:29
Пока. M