Comments 6
Когда меня просят «на пальцах» рассказать про БПФ и ДПФ, особенно часто об этом просят люди, которые «понимают в технике», то обычно я начинаю рассказывать примерно так: Фурье — это тот же самый радиоприемник, только математический. В обычном приемнике входной сигнал умножается (смесителем) на гетеродин. Гетеродин — это синусоидальный сигнал выработанный локально (в приемнике), если после такого умножения выделить постоянную составляющую, то она будет пропорциональна амплитуде сигнала на частоте гетеродина.
На самом деле все немного сложнее, гетеродин должен быть двойной (синусоида и косинусоида), если умножить анализируемый сигнал на синусоиду и косинусоиду, а потом усреднить все полученные значения, то мы получим вектор, где длинна вектора есть амплитуда, а арктангенс составляющих есть разность фаз, между сигналом и гетеродином.
Так вот если постоянно менять частоту гетеродина, то мы просканируем все частоты и получим спектр. Так работают (работали) аналоговые спектроанализаторы.
ДПФ делает то-же самое, абсолютно. Только не в реальном времени и не с живым сигналом, а с готовым — оцифрованным массивом данных.
БПФ модифицированный и оптимизированный алгоритм, который работает быстрее засчет уменьшения количества умножений. В ДПФ каждая выборка сигнала умножается на синус и косинус «гетеродина», но выборки синусов и косинусов разных частот совпадают во времени, и чтобы не использовати их повторно, они используются оптимально, засчет сортировок и перестановок.
Ну, а дальше уже формулы.
Статья отличная, прочитал с огромным удовольствием, автору спасибо!
На самом деле все немного сложнее, гетеродин должен быть двойной (синусоида и косинусоида), если умножить анализируемый сигнал на синусоиду и косинусоиду, а потом усреднить все полученные значения, то мы получим вектор, где длинна вектора есть амплитуда, а арктангенс составляющих есть разность фаз, между сигналом и гетеродином.
Так вот если постоянно менять частоту гетеродина, то мы просканируем все частоты и получим спектр. Так работают (работали) аналоговые спектроанализаторы.
ДПФ делает то-же самое, абсолютно. Только не в реальном времени и не с живым сигналом, а с готовым — оцифрованным массивом данных.
БПФ модифицированный и оптимизированный алгоритм, который работает быстрее засчет уменьшения количества умножений. В ДПФ каждая выборка сигнала умножается на синус и косинус «гетеродина», но выборки синусов и косинусов разных частот совпадают во времени, и чтобы не использовати их повторно, они используются оптимально, засчет сортировок и перестановок.
Ну, а дальше уже формулы.
Статья отличная, прочитал с огромным удовольствием, автору спасибо!
Единственный способ по-настоящему понять, как работает БПФ — это написать его самому, ну или хотя портировать с одного языка программирования на другой. Чтобы своими глазами в режиме отладки увидеть, как в массиве крутятся и складываются векторы. И про bit-reversal permutation тоже ничего не сказано, и про (а)симметричное масштабирование, и про симметрию (комплексного) спектра на действительных входных данных…
Преобразование из xn → Xk является переводом из конфигурационного пространства в пространство частотноеПо русски это должно звучать как «переходом из временной области в частотную и наоборот». Иногда вместо «область» говорят «домен» (калька с английского).
Python 3.6 ругается:
на строчку:
хочет, чтобы индексы обернули в int()
Slice indices must be integers or None or have __index__ method
на строчку:
return np.concatenate([X_even + factor[:N / 2] * X_odd, X_even + factor[N / 2:] * X_odd])хочет, чтобы индексы обернули в int()
Простите, мой комментарий может показаться резковатым, но накипело.
Если вся книга написана в том же духе, что и эта статья, то мне печально. Увы! Примерно с шестидесятых годов прошлого века в отечественной литературе наметилось стремление к наукообразию. Не знаю, что тому причиной, но факт. И это ужасно.
Вот так сходу представлять FFT в виде матричного умножения? Вы правда верите, что из диковато выглядящей формулы с комплексной экспонентой это очевидно? Вам правда кажется, что это способ, наиболее упрощающий понимание происходящего?
Как по мне, это самый неочевидный способ представления, который может быть полезен в некоторых случаях, но совершенно неинтуитивен и не отражает смысла явления. Вообще, на мой взгляд, сам факт того, что FFT можно представить в матричном виде — забавный математический фокус, не более. Об этом можно было бы упомянуть вскользь ближе к концу статьи, а не выносить это чуть ли не как основу, тем более, что такое представление ничего не добавляет к пониманию метода Кули-Тьюки, но зато сходу грузит читателя непростым для осознания и притом ненужным для понимания целевого алгоритма фактом.
В итоге статья, которая называется "Понимание алгоритма БПФ", сходу путает читателя, отдаляя его от этого самого понимания. Зато красиво, с матрицами.
Вот человек хорошо объяснил, что такое преобразование Фурье. Что-то в духе этого комментария должно было быть в начале статьи. А потом можно было бы объяснить, что FFT — это набор скалярных произведений на базовые ортогональные векторы. Вот это как раз очевидно, но про это в статье — ни слова.
Математически БПФ — это координаты нашего сигнала в пространстве, в котором синусоиды выступают в качестве орт. Физически — (частотный) спектр сигнала. Все!
Какое «конфигурационное пространство»? Что это вообще такое? Впрочем, я понимаю — тот, кто сходу может увидеть в комплексном суммировании матричное умножение, наверняка это знает. Но ему эта статья скорее всего уже не нужна.
Ну а дальше разбор математики с периодичностью, разбиением на две суммы и так далее. Это стандартно.
Вот действительно хорошая статья про FFT. Из нее да, можно понять. Картинки, подробные записи вычислений, ясные объяснения.
в главе 10 нашей будущей книги
Если вся книга написана в том же духе, что и эта статья, то мне печально. Увы! Примерно с шестидесятых годов прошлого века в отечественной литературе наметилось стремление к наукообразию. Не знаю, что тому причиной, но факт. И это ужасно.
Вот так сходу представлять FFT в виде матричного умножения? Вы правда верите, что из диковато выглядящей формулы с комплексной экспонентой это очевидно? Вам правда кажется, что это способ, наиболее упрощающий понимание происходящего?
Как по мне, это самый неочевидный способ представления, который может быть полезен в некоторых случаях, но совершенно неинтуитивен и не отражает смысла явления. Вообще, на мой взгляд, сам факт того, что FFT можно представить в матричном виде — забавный математический фокус, не более. Об этом можно было бы упомянуть вскользь ближе к концу статьи, а не выносить это чуть ли не как основу, тем более, что такое представление ничего не добавляет к пониманию метода Кули-Тьюки, но зато сходу грузит читателя непростым для осознания и притом ненужным для понимания целевого алгоритма фактом.
В итоге статья, которая называется "Понимание алгоритма БПФ", сходу путает читателя, отдаляя его от этого самого понимания. Зато красиво, с матрицами.
Вот человек хорошо объяснил, что такое преобразование Фурье. Что-то в духе этого комментария должно было быть в начале статьи. А потом можно было бы объяснить, что FFT — это набор скалярных произведений на базовые ортогональные векторы. Вот это как раз очевидно, но про это в статье — ни слова.
Математически БПФ — это координаты нашего сигнала в пространстве, в котором синусоиды выступают в качестве орт. Физически — (частотный) спектр сигнала. Все!
Какое «конфигурационное пространство»? Что это вообще такое? Впрочем, я понимаю — тот, кто сходу может увидеть в комплексном суммировании матричное умножение, наверняка это знает. Но ему эта статья скорее всего уже не нужна.
Ну а дальше разбор математики с периодичностью, разбиением на две суммы и так далее. Это стандартно.
Вот действительно хорошая статья про FFT. Из нее да, можно понять. Картинки, подробные записи вычислений, ясные объяснения.
Ну и, конечно, язык, да.
«это реализация на Фортране, которая получила годы доработок и оптимизаций.»
Реализация получила годы? Может быть, «дорабатывалась на протяжении многих лет», или как-то так?
«преподнесли некоторую интуицию»
Видимо, не совсем корректная калька с «brought some insight». Статья, кстати, точно не перевод? Вообще, она носителем русского языка написана?
«справиться с реализацией «черного ящика» фундаментальных инструментов, созданных нашими более алгоритмически настроенными коллегами»
Справиться с реализацией того, что, как следует из продолжения фразы, уже реализовано другими?
Реализация получила годы? Может быть, «дорабатывалась на протяжении многих лет», или как-то так?
«преподнесли некоторую интуицию»
Видимо, не совсем корректная калька с «brought some insight». Статья, кстати, точно не перевод? Вообще, она носителем русского языка написана?
«справиться с реализацией «черного ящика» фундаментальных инструментов, созданных нашими более алгоритмически настроенными коллегами»
Справиться с реализацией того, что, как следует из продолжения фразы, уже реализовано другими?
Не стоит так нервничать, это перевод — сверху есть пометка. Как и возмущаться языком. Что же касается понятности/сложности, то здесь была попытка рассказать алгоритм БПФ на языке программистов, уменьшив количество формул и ссылок на непрограммерские области. А пояснение из комментария выше будет прочитано большинством программистов ровно до слова "гетеродин", после которого пояснения только еще больше запутывают. Вы даете ссылку на статью с якобы хорошими пояснениями, ругая автора данной статьи за матричные умножения, но по вашей ссылке, матричное умножение начинается с 3й страницы, и дальше математике, математика, и только пару последних страниц алгоритм. Возможно для вас именно эта статья была лучше, для комментатора выше — его объяснение, а кому-то именно эта статья — наиболее понятное введение в бпф. Так что чем больше выбора, тем лучше, иногда лучше рассмотреть с разных сторон проблему, чтобы понять суть.
Sign up to leave a comment.
Понимание алгоритма БПФ