Обсуждение:Быстрое преобразование Фурье

Иллюстрация

А откуда видно, что эта иллюсторация сответствует именно алгоритму БПФ, а не рассчитанному в лоб ДПФ? И стоит ли, вообще, иллюстрировать алгоритмы скриншотами работы программ, которые вообще непонятно по какому алгоритму работают и что делают? Как по мне, в этой статье если уж вести речь о иллюстрациях, не помешала бы схема "бабочки".

Скриншот иллюстрирует "Ниже приведен пример вычисления модуля спектра действительного массива чисел на основе реализации быстрого преобразования Фурье, написанный на C++ :" и подобный ему ниже на Delphi, значение амплитуды гармоник представлено как цветовая шкала во времени (для тех кто первый раз это видит). Mexanikus 16:30, 9 ноября 2014 (UTC)

Исходник

А тут нужен сорец и именно на плюсах? Может воткнем что-то более компактное или даже псевдокод? --Oal 18:23, 27 апреля 2007 (UTC)

ИМХО, лучше написать подробные комментарии к уже имеющемуся коду. Мне бы пригодились :-D. Если разбирусь с ним - то подправлю наверн.Lizz 17:48, 10 декабря 2007 (UTC)

А обязательно в коде C++ писать реализацию комплексных чисел? Там же есть <complex>. 85.141.70.96 05:13, 1 апреля 2009 (UTC)

Этот код — образец, как не надо писать программы.92.243.181.209 15:04, 28 августа 2009 (UTC)

Мне кажется, или в статье все эпсилон по-хорошему надо заменить на e? Где же тогда возьмутся гармонические колебания и все такое? --84.51.66.2 19:20, 14 мая 2009 (UTC)Ренат Насыров

Отстань от эпсилон, это обозначение для $e^{-2\pi i}$92.243.181.209 15:04, 28 августа 2009 (UTC)

коментариев к исходному коду действительно не помешало бы. а еще, более подробно описать общий случай, а то там много упущено...

Ощущение, что код писали разные люди. Во-первых, он не запустится (интерфейс функции в описании и в вызове не совпадают; очевидно, не парсится третий (булевый) аргумент, а isign выставляется безусловно). Во-вторых, не лишне добавить не только комментарии (ибо не тривиальный алгоритм), но и псевдокод и ссылку на оригинальное название алгоритма, если таковое имеется. Вообще сомнительно, что комментарии сильно помогут понять код, неплохо бы разжевать алгоритм, а потом уже предоставлять исходники на языках. P.S. Кроме того, не везде / 2 заменено на >> 1. Даблы с интами напутаны. Да и вообще, функция возвращает не Фурье-образ, а энергию гармоник (модуль комплексного числа). Или я ошибаюсь? Очевидно, в этой версии алгоритм никто не запускал. А кто-нибудь его вообще проверял? Спасибо. 109.169.252.68 12:44, 23 февраля 2010 (UTC)

Я проверил алгоритм. В исходнике примера ошибка. Нужно в цикле "for( double x = 0; x <= 10 * M_PI; x += M_PI / 180.0 )" вместо "x <= 10 * M_PI" написать "x < 10 * M_PI". Red5 al 13:57, 5 мая 2010 (UTC)

Я также проверил сырец. Алгоритм прямого преобразования добавляет в каждую гармонику уровень, зависящий от мощности входного сигнала. В итоге - в спектре мощности (то, что вычисляется в последнем цикле ф-ции FFT) появляется постоянная составляющая. Она мало того, что портит всю картину (спектр смещается вверх и часть спектральных максимумов лежит ниже медианы), так еще и сигнал при обратном преобразовании меняет. Я не нашел простого исходника, который можно было бы вставить для примера. 77.35.230.235 23:47, 4 февраля 2011 (UTC) whoami

В связи с вышесказанным, предлагаю удалить исходный код из статьи. (109.169.252.68 12:44, 23 февраля 2010 (UTC)) aka 109.169.153.214 09:25, 24 февраля 2011 (UTC)

Вывод преобразования из ДПФ

Одного меня смущает X слева от знака равно и x справа от знака равно? Я только раза с четвертого начал понимать в чём дело. Не боитесь людей запутать? Мне кажется вывод из ДПФ надо слегка переписать. Aracks 04:13, 29 апреля 2014 (UTC)

Кто автор?

В статьях про алгоритмы принято упоминать их создателей. МетаСкептик12 08:24, 9 июля 2012 (UTC)

Я являюсь автором алгоритма "Ниже приведен пример вычисления модуля спектра действительного массива чисел на основе реализации быстрого преобразования Фурье, написанный на C++ :" и подобного ему ниже на Delphi, этот алгоритм конечно не является на 100% моим творением так как он построен на основе стандартной математической реализации, я исправил ошибки и увеличил быстродействие, а также полностью проверил и протестировал его. Mexanikus 16:43, 9 ноября 2014 (UTC)

Обратное преобразование

Что означает "поделить на N" в общем случае? Если я, допустим, вручную заполнил две таблицы Кели и назвал это полем, то как быть? 217.9.90.17 17:42, 25 июня 2013 (UTC)

Основной алгоритм

@Lukoshkin:: Вы написали: "Таких выражений отличных друг от друга q штук." Почему? По-моему таких выражений будет p штук. Или я не прав? — Алексей Копылов 15:09, 11 апреля 2017 (UTC)

@Alexei_Kopylov:: Я переработал весь раздел. Посмотрите сейчас, пожалуйста. Теперь никаких сложностей для понимания возникнуть не должно. Насчёт "числа отличных" - Вы правы, их действительно p (Хотя всё это, конечно, зависит от представления формулы для ДПФ. Но тем не менее, в том контексте мною была допущена ошибка. За q я понимал в голове, понятие отличающееся от того, что было "на бумаге") Пришлось пересмотреть весь вывод и было найдено большое количество несостыковок. Которые, как оказалось, не исчезли после моего первого редактирования, а перевоплотились в другие, им эквивалентные. Сейчас я вроде как разобрался до конца и познал дзен. Спасибо Чт апр 13 16:43:49 MSK 2017

@Lukoshkin: Спасибо за ответ, я поправил ошибки в формулах, посмотрите, пожалуйста. Кроме того я вижу проблему: сейчас вы пишите, как выполнить преобразование за O(N(p+q)) действий. Отсюда не очевидно, это можно сделать за O(N(p₁+...+p_n)) действий. В старой версии, задача сводилась к задаче для N/q, отсюда получалось O(N(p₁+...+p_n)). В частности для старой версии было важно, что брать в качестве q, а что в качестве p.

Так выглядит кнопка для подписи на верхней панели редактирования

P.S. Пожалуйста, всегда подписывайтесь в обсуждениях: это делается проставлением знаков ~~~~ в конце сообщения или нажатием специальной кнопки. После сохранения страницы, знаки тильды будут автоматически заменены на подпись с указанием времени. В частности, мне не пришло уведомление, которое пришло бы, если использовать шаблон {{ping}} вместе с подписью. — Алексей Копылов 17:17, 13 апреля 2017 (UTC)