http://sernam.ru/book_tec.php?id=149
"Выражение (9.39) показывает, что для определения одного коэффициента ДПФ сигнальной последовательности из N отсчетов, необходимо выполнить около N операций умножения на комплексное число и столько же сложений, а для нахождения всех коэффициентов объем вычислений составит . В частности, при надо осуществить более миллиона умножений и сложений. Если длины обрабатываемых массивов превышают тысячу единиц, то дискретная спектральная обработка сигналов в реальном масштабе времени требует высокопроизводительных вычислительных комплексов.
Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей. Для этого число отсчетов N разделяется на множители (например, ). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала. В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.
.......................
Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно N*log2(N) операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в N*log2(N) раз. Например, при количестве отсчетов 2^10, имеем log2(N)=10 и сокращение числа операций составляет N*log2(N)~=100. При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч. "
Тут вроде как понятным языком изложено : http://www.phys.nsu.ru/cherk/Vestnik_Fou..._15_09.pdf
"На всякий пожарный", прицеплю:
"Выражение (9.39) показывает, что для определения одного коэффициента ДПФ сигнальной последовательности из N отсчетов, необходимо выполнить около N операций умножения на комплексное число и столько же сложений, а для нахождения всех коэффициентов объем вычислений составит . В частности, при надо осуществить более миллиона умножений и сложений. Если длины обрабатываемых массивов превышают тысячу единиц, то дискретная спектральная обработка сигналов в реальном масштабе времени требует высокопроизводительных вычислительных комплексов.
Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей. Для этого число отсчетов N разделяется на множители (например, ). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала. В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.
.......................
Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно N*log2(N) операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в N*log2(N) раз. Например, при количестве отсчетов 2^10, имеем log2(N)=10 и сокращение числа операций составляет N*log2(N)~=100. При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч. "
Тут вроде как понятным языком изложено : http://www.phys.nsu.ru/cherk/Vestnik_Fou..._15_09.pdf
"На всякий пожарный", прицеплю:
