Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Как видно, из формул (5.4) и (5.5), чтобы вычислить ДПФ или ОДПФ последовательности из элементов, требуется выполнить операций с комплексными числами. Если длины обрабатываемых массивов имеют порядок тысячи или более, то использовать эти алгоритмы дискретного спектрального анализа в реальном масштабе времени затруднительно из-за ограниченного быстродействия вычислительных устройств.
Выходом из положения является алгоритм быстрого преобразования Фурье (БПФ), предложенный в 60-х годах XX века. Существенно сократить число операций удаётся за счёт того, что обработка входного массива сводится к нахождению ДПФ (или ОДПФ) массивов с меньшим числом членов.
Предположим, что число отсчётов , где - целое число. Разобьём входную последовательность на две части с чётными и нечётными номерами.
(5.6)
И представим -й коэффициент ДПФ в виде:
Из формулы видно, что первая половина коэффициентов ДПФ исходного сигнала с номерами от 0 до (N/2)-1 выражается через коэффициенты ДПФ двух частных последовательностей:
=0, 1, 2,…,( /2)-1 (5.7)
Учтём, что последовательности коэффициентов, относящихся к чётной и нечётной частям входного массива, являются периодическими с периодом N/2:
Кроме того, входящий в формулу (5.7) множитель при можно преобразовать так:
Отсюда находим выражение для второй половины множества коэффициентов ДПФ
(5.8)
Формулы (5.7) и (5.8) лежат в основе алгоритма БПФ. Далее вычисления строят по итерационному принципу: последовательности отсчётов с чётными и нечётными номерами вновь разбивают на две части. Процесс продолжают до тех пор, пока не получается последовательность, состоящая из единственного элемента. ДПФ этого элемента совпадает с ним самим.
Число операций, необходимых для вычисления БПФ оценивается как .
Выигрыш в скорости вычислений по сравнению с традиционным ДПФ достигает сотен и даже тысяч при достаточных длинах входных массивов.
Дата публикования: 2014-11-26; Прочитано: 285 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!