Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 3.3. Быстрое преобразование ФурьеНедостатком дискретного преобразования Фурье является большое количество математических операций, которые необходимо произвести при применении формулы (3.4) или (3.14). Если число степеней свободы сигнала равно Для облегчения вычисления дискретного преобразования Фурье применяют специальные алгоритмы, которые позволяют во много раз сократить объем необходимых вычислений. Такие алгоритмы называют быстрым преобразованием Фурье. Существует несколько различных алгоритмов быстрого преобразования Фурье [2,4]. Каждый из них применяют в определенной ситуации, в зависимости от того, на какие множители может быть разложено число степеней свободы Пусть требуется вычислить дискретное преобразование Фурье числовой последовательности
Поскольку число отсчетов сигнала
Применим дискретное преобразование Фурье к последовательностям
Для сокращения записи обозначим
Нашей конечной целью является вычисление значений
Рис. 3.2. К выводу алгоритма быстрого преобразования Фурье Таким образом, значения
Учитывая, окончательную расчетную формулу для
Процесс вычисления дискретного преобразования Фурье по формулам (3.17), (3.18) схематически изображен на рис. 3.3 с помощью направленного сигнального графа. Здесь каждое из умножений на
Рис. 3.3 Замена восьмиточечного дискретного преобразования Фурье двумя четырехточечными Для вычисления значений Если число степеней свободы сигнала Процесс упрощения алгоритма расчета можно продолжать до тех пор, пока не останутся только простейшие двухточечные дискретные преобразования Фурье. В результате получим сигнальный граф для
Рис. 3.4. Замена четырехточечных дискретных преобразований Фурье двухточечными
Рис. 3.6. Схематическое изображение алгоритма быстрого преобразования Фурье Число умножений определяется числом стрелок на рис. 3.5, а число сложений (вычитаний) — числом кружочков, умноженным на 2. В рассмотренном случае восьмиточечного дискретного преобразования Фурье в соответствии с рис. 3.5 необходимо выполнить Таким образом, при применении данного алгоритма для вычисления дискретного преобразования Фурье последовательности из Кроме рассмотренного алгоритма быстрого преобразования Фурье существует ряд других, которые применяют в тех случаях, когда N не является степенью числа 2, а раскладывается на другие простые сомножители. Все эти алгоритмы подробно рассмотрены в [7].
|
1 |
Оглавление
|