Глава 6. Вычисление дискретного преобразования Фурье

ВВЕДЕНИЕ

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

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

Вспомним, что дискретное преобразование Фурье (ДПФ) определяется выражением (см. гл. 3)

где Обратное дискретное преобразование Фурье (ОДПФ) имеет вид

В (6.1) и (6.2) как так могут быть комплексными. Выражения в (6.1) и (6.2) отличаются только знаком экспоненты от и скалярным коэффициентом Поэтому рассуждения, касающиеся вычислительных процедур для (6.1), применимы с очевидными изменениями к (6.2).

Чтобы проиллюстрировать важность эффективных вычислительных алгоритмов, поучительно сначала рассмотреть непосредственное вычисление ДПФ. Так как может быть комплексным, то можно записать

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

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

Большинство подходов к улучшению эффективности вычисления ДПФ использует следующие свойства величин

Например, используя первое свойство, т. е. свойство симметрии функции можно сгруппировать слагаемые в (6.3) следующим образом:

Аналогичную группировку можно произвести для других слагаемых в (6.3). Посредством этого метода число умножений можно сократить приблизительно вдвое. Можно также использовать тот факт, что для определенных значений произведения функции принимают значения 1 или 0, при которых не требуется умножение. Однако при сокращениях такого типа количество вычислений все еще остается приблизительно пропорциональным . К счастью, второе свойство, т. е. периодичность комплексной последовательности позволяет достигнуть существенно большего сокращения количества вычислений.

Вычислительные алгоритмы, использующие как симметрию, так и периодичность последовательности были известны задолго до появления быстродействующих ЦВМ. В то время приветствовалась любая схема, уменьшающая количество ручных вычислений даже в 2 раза. Рунге (Runge) [2], а позже Даниэльсон (Danielson) и Ланцош (Lanczos) [3] описали алгоритмы, при которых количество вычислений было приблизительно пропорционально а не Однако это различие не было слишком: важным для тех малых значений которые можно было осуществить при ручных вычислениях. В 1965 г. Кули (Cooley) и Тьюки (Tukey) [1] опубликовали алгоритм вычисления дискретного

преобразования Фурье, применимый при составном т. е. когда является произведением двух или большего числа целых чисел. Опубликование этой статьи вызвало значительный интерес к дискретному преобразованию Фурье при обработке сигналов и привело к открытию ряда вычислительных алгоритмов, которые стали известны под названием алгоритмы быстрого преобразования Фурье (БПФ). В целом все множество таких алгоритмов часто называется БПФ [5].

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

В этой главе будет рассмотрен ряд алгоритмов вычисления дискретного преобразования Фурье, которые отличаются друг от друга по эффективности, но все они более эффективны, чем прямое вычисление по (6.3). Первым будет рассмотрен метод Герцеля (Gortzel) [6, 7], который требует количества вычислений, пропорционального но с меньшим, чем при прямом методе, коэффициентом пропорциональности. Наибольшее внимание будет уделено алгоритмам БПФ, т. е. алгоритмам, при которых количество вычислений приблизительно пропорционально Мы не будем стараться рассмотреть все алгоритмы, но проиллюстрируем общие принципы всех алгоритмов этого типа, рассматривая детально только несколько из наиболее часто используемых схем.