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

@webhosting · Регистрация: 03.08.2011

Студворк — интернет-сервис помощи студентам

Добрый день, проблема следующем: в NAG реализовано ББФ для случая, когда N (число слагаемых) не содержит простых делителей больше 19, а в Maple – для случая, когда N не имеет простых делителей отличных от 2,3 и 5. Сколько я ни бился в интернете находил только описание алгоритма для N=2^m. Может быть кто-нибудь знает, где можно почитать описание ББФ для общего случая (желательно на русском).

HighPredator · 08.08.2011, 20:17

Кормен, Лейзерсон, Ривест "Алгоритмы. Построение и анализ" Второе издание. Часть 7. Глава 30. "Полиномы и быстрое преобразование Фурье".
В общем случае вы можете брать любое N и дополнить нулями до требуемой алгоритмом длины. На конечный результат не повлияет.

@webhosting · 09.08.2011, 16:31 **[ТС]**

Спасибо,
про вариант вополнения нулями или усечения до степени двойки я знал, но ББФ мне нужно для рассчета спектральной плотности, а изменение длины приводит к изменению точек в которых плотность будет вычислена.

HighPredator · 09.08.2011, 22:13

Сообщение от webhosting

изменение длины приводит к изменению точек в которых плотность будет вычислена

У вас не изменится функция, полученная через интеграл Фурье, поскольку нулевые значения сигнала в ряд не внесут вклад. А следовательно не изменится и СПМ, поскольку она задается амплитудами из БПФ. Кажется так.

@grizlik78 · 09.08.2011, 23:08

Сообщение от Predator_2004

У вас не изменится функция, полученная через интеграл Фурье, поскольку нулевые значения сигнала в ряд не внесут вклад. А следовательно не изменится и СПМ, поскольку она задается амплитудами из БПФ. Кажется так.

Осторожнее надо с нулями. Просто дополнить — это вряд ли.
Дискретное преобразование Фурье:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\dot C_k = \sum_{n=0}^{N-1}e^{-j\frac{2\pi nk}{N}}$
Посчитайте для последовательности $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{1,\: 1,\: 1\}$ и для $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{1,\: 1,\: 1,\: 0\}$
В первом случае получится
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{3,\: 0,\: 0\}$
во втором
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\{3,\: -j,\: 1,\: j\}$

HighPredator · 09.08.2011, 23:19

grizlik78, То есть вы хотите сказать, что константный сигнал из единиц может быть представлен в виде только одной синусоидальной функции с амплитудой 3?

@grizlik78 · 09.08.2011, 23:25

Predator_2004, учитывая что частота у неё равна нулю — да, конечно. Это 3*cos(0)

HighPredator · 09.08.2011, 23:30

А фаза? Даже если она тоже ноль то 3*1=3 а не 1

У вас же действительные коэффициенты я так понял.

@grizlik78 · 09.08.2011, 23:38

Замечание понятно, но если приведённую мной формулу выводить, то перед суммой получится коэффициент 1/N и тогда всё сходится

Просто традиционно этот коэффициент переносят в обратное дискретное преобразование Фурье. От этого меняется только размерность в области частот.
Сигнал в примере действительный, но это не важно, формула справедлива и для комплексных.

Добавлено через 2 минуты
Только я, балбес, сигнал в формуле потерял

Добавлено через 47 секунд
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\dot C_k = \sum_{n=0}^{N-1}s_n e^{-j\frac{2\pi nk}{N}}$

HighPredator · 09.08.2011, 23:44

БПФ сделан для того чтобы не считать интеграл руками, поэтому для большого количества точек можно дополнять нулями так как вклад от "краевых эффектов" из-за нулей не сильно сказывается на точности. Для "коротких" сигналов как в вашем примере это сильно заметно.

@grizlik78 · 10.08.2011, 00:25

Честно говоря, не знаю, для чего было придумано дискретное преобразование. Но понимать его особенности при использовании желательно. Главная особенность — это то, что и сам сигнал и его спектр являются периодическими.
Дополнение нулями, конечно, в большинстве случаев не меняет сильно форму спектра. Но дополнение нулями эквивалентно увеличению периода и скважности периодического сигнала (если расстояние между отсчётами не менять). В этом случае меняется частотная сетка, ведь расстояние между частотными дискретами обратно пропорционально периоду. То есть тот же диапазон частот будет представлен большим количеством частотных отсчётов, а сам спектр, как сказал ТС, будет вычислен в других точках. Это не всегда допустимо.

HighPredator · 10.08.2011, 00:37

Сообщение от grizlik78

дополнение нулями эквивалентно увеличению периода

Не совсем. Увеличивается отрезок рассмотрения. Но сам период какой был такой и есть. Не даром берут большие N. И не совсем понял, что значит

Сообщение от grizlik78

а сам спектр, как сказал ТС, будет вычислен в других точках

Спектр по определению, если не путаю, распределение по частотам, т.е. результат БПФ.

@grizlik78 · 10.08.2011, 01:14

Ну хорошо, давай с конкретными числами.
Допустим, у нас есть 100 отсчётов сигнала взятые с интервалом 10 мс. Длительность, получается, 1 с. Если мы будем находить дискретный спектр по этим 100 точкам, то получим 100 отсчётов (коэффициентов) в спектре. Самый первый коэффициент C0 будет соответствовать частоте 0 Гц, коэффициент C1 частоте 1/T = 1 Гц, следующий 2 Гц и так далее. Последний C99 соответствует частоте 99 Гц.
Теперь дополним исходный сигнал нулями до 128. Раз мы не меняли интервал дискретизации, то теперь длительность временного окна стала равна 1,28 c, а расстояние по частоте между каждым из 128 спектральных коэффициентов 1/1,28 = 0,78125 Гц.
То есть теперь имеем значения спектра на частотах 0 Гц, 0,78125 Гц, 1,5625 Гц и так далее.
Последний коэффициент C127 соответствует частоте 99,21875 Гц.
Вот это и значит, что хоть спектр и получили, но не на тех частотах, на которых, возможно, хотелось.

HighPredator · 10.08.2011, 01:36

Абсолютно верно мыслите. А теперь давайте рассмотрим, как велит теория по ЦОС, например 1000 и 1024 отсчетов сигнала соответственно. Поскольку как правило при получении спектра интересуют всех амплитуды на низких частотах. Обратимся к первой частоте. 1*(частота_дискретизации=20)/1000=0.02 и 1*(частота_дискретизации=20)/1024=0.01953125
Мысль я вот какую пытаюсь донести: при работе с БПФ, в силу специфики алгоритма, всегда берутся большие выборки, чтобы убрать, во-первых, эти самые краевые эффекты, а во-вторых, чтобы не проиграть в точности. Если же нет такой возможности, то имеет смысл на мой взгляд руками проинтегрировать.

@grizlik78 · 10.08.2011, 02:00

Ну уж какие частоты нужны и насколько критично влияние лишних нулей, это оставим решать автору темы

Вообще, если речь об оценивании спектра некоторого сигнала, то в общем случае просто одного преобразования Фурье может быть и недостаточно. По этой теме целые книги написаны.

Возвращаясь же к исходному вопросу, могу порекомендовать ТС посмотреть книгу (если ещё не)
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов
Там много чего рассмотрено.
А из более радикального — можно покопаться в исходниках библиотеки FFTW

Там используются любые основания, не только степени двойки. Но я лично что-то не решаюсь

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@webhosting 0 / 0 / 0 Регистрация: 03.08.2011 Сообщений: 9

	Быстрое преобразование Фурье в общем случае 08.08.2011, 17:29. Показов 4363. Ответов 14 Метки нет (Все метки) Добрый день, проблема следующем: в NAG реализовано ББФ для случая, когда N (число слагаемых) не содержит простых делителей больше 19, а в Maple – для случая, когда N не имеет простых делителей отличных от 2,3 и 5. Сколько я ни бился в интернете находил только описание алгоритма для N=2^m. Может быть кто-нибудь знает, где можно почитать описание ББФ для общего случая (желательно на русском). 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	08.08.2011, 20:17
	Кормен, Лейзерсон, Ривест "Алгоритмы. Построение и анализ" Второе издание. Часть 7. Глава 30. "Полиномы и быстрое преобразование Фурье". В общем случае вы можете брать любое N и дополнить нулями до требуемой алгоритмом длины. На конечный результат не повлияет. 1

@webhosting 0 / 0 / 0 Регистрация: 03.08.2011 Сообщений: 9
	09.08.2011, 16:31 [ТС]
	Спасибо, про вариант вополнения нулями или усечения до степени двойки я знал, но ББФ мне нужно для рассчета спектральной плотности, а изменение длины приводит к изменению точек в которых плотность будет вычислена. 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	09.08.2011, 23:19
	grizlik78, То есть вы хотите сказать, что константный сигнал из единиц может быть представлен в виде только одной синусоидальной функции с амплитудой 3? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	09.08.2011, 23:25
	Predator_2004, учитывая что частота у неё равна нулю — да, конечно. Это 3*cos(0) 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	09.08.2011, 23:30
	А фаза? Даже если она тоже ноль то 3*1=3 а не 1 У вас же действительные коэффициенты я так понял. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	09.08.2011, 23:38
	Замечание понятно, но если приведённую мной формулу выводить, то перед суммой получится коэффициент 1/N и тогда всё сходится Просто традиционно этот коэффициент переносят в обратное дискретное преобразование Фурье. От этого меняется только размерность в области частот. Сигнал в примере действительный, но это не важно, формула справедлива и для комплексных. Добавлено через 2 минуты Только я, балбес, сигнал в формуле потерял Добавлено через 47 секунд $https://www.cyberforum.ru/cgi-bin/latex.cgi?\dot C_k = \sum_{n=0}^{N-1}s_n e^{-j\frac{2\pi nk}{N}}$ 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	09.08.2011, 23:44
	БПФ сделан для того чтобы не считать интеграл руками, поэтому для большого количества точек можно дополнять нулями так как вклад от "краевых эффектов" из-за нулей не сильно сказывается на точности. Для "коротких" сигналов как в вашем примере это сильно заметно. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	10.08.2011, 00:25
	Честно говоря, не знаю, для чего было придумано дискретное преобразование. Но понимать его особенности при использовании желательно. Главная особенность — это то, что и сам сигнал и его спектр являются периодическими. Дополнение нулями, конечно, в большинстве случаев не меняет сильно форму спектра. Но дополнение нулями эквивалентно увеличению периода и скважности периодического сигнала (если расстояние между отсчётами не менять). В этом случае меняется частотная сетка, ведь расстояние между частотными дискретами обратно пропорционально периоду. То есть тот же диапазон частот будет представлен большим количеством частотных отсчётов, а сам спектр, как сказал ТС, будет вычислен в других точках. Это не всегда допустимо. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	10.08.2011, 01:14
	Ну хорошо, давай с конкретными числами. Допустим, у нас есть 100 отсчётов сигнала взятые с интервалом 10 мс. Длительность, получается, 1 с. Если мы будем находить дискретный спектр по этим 100 точкам, то получим 100 отсчётов (коэффициентов) в спектре. Самый первый коэффициент C0 будет соответствовать частоте 0 Гц, коэффициент C1 частоте 1/T = 1 Гц, следующий 2 Гц и так далее. Последний C99 соответствует частоте 99 Гц. Теперь дополним исходный сигнал нулями до 128. Раз мы не меняли интервал дискретизации, то теперь длительность временного окна стала равна 1,28 c, а расстояние по частоте между каждым из 128 спектральных коэффициентов 1/1,28 = 0,78125 Гц. То есть теперь имеем значения спектра на частотах 0 Гц, 0,78125 Гц, 1,5625 Гц и так далее. Последний коэффициент C127 соответствует частоте 99,21875 Гц. Вот это и значит, что хоть спектр и получили, но не на тех частотах, на которых, возможно, хотелось. 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	10.08.2011, 01:36
	Абсолютно верно мыслите. А теперь давайте рассмотрим, как велит теория по ЦОС, например 1000 и 1024 отсчетов сигнала соответственно. Поскольку как правило при получении спектра интересуют всех амплитуды на низких частотах. Обратимся к первой частоте. 1(частота_дискретизации=20)/1000=0.02 и 1(частота_дискретизации=20)/1024=0.01953125 Мысль я вот какую пытаюсь донести: при работе с БПФ, в силу специфики алгоритма, всегда берутся большие выборки, чтобы убрать, во-первых, эти самые краевые эффекты, а во-вторых, чтобы не проиграть в точности. Если же нет такой возможности, то имеет смысл на мой взгляд руками проинтегрировать. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	10.08.2011, 02:00
	Ну уж какие частоты нужны и насколько критично влияние лишних нулей, это оставим решать автору темы Вообще, если речь об оценивании спектра некоторого сигнала, то в общем случае просто одного преобразования Фурье может быть и недостаточно. По этой теме целые книги написаны. Возвращаясь же к исходному вопросу, могу порекомендовать ТС посмотреть книгу (если ещё не) Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов Там много чего рассмотрено. А из более радикального — можно покопаться в исходниках библиотеки FFTW Там используются любые основания, не только степени двойки. Но я лично что-то не решаюсь 0