Цифровая обработка сигналов. Основные понятия и определения. Сигналы и их спектральное представление, страница 9

Начиная со значения  значения  – повторяются. Кроме того, в пределах одного периода первые  значений  отличаюся от вторых  значений лишь знаком. Действительно,  ; , и т.д.

Устранение избыточных умножений приводит к так называемому быстрому преобразованию Фурье (БПФ). Оно позволяет многократно

сократить число операций и обеспечивает более скоростные и эффективные вычисления коэффициентов ДПФ.

Рассмотрим один из способов построения алгоритмов БПФ, называемый способом прореживания по времени.

Пусть требуется вычислить ДПФ входной последовательности (массива отчетов) дискретного сигнала , имеющего четное число отсчетов, причем , где т – целое число.

Представим входную последовательность в виде двух предпоследовательностей с четными и нечетным номерами и половинным числом членов в каждой последовательности (рисунок 2.15): ; ; . Определим спектры этих последовательностей с четным и нечетными номерами отдельно:

;

, где .

Следовательно, значения  ДПФ найдется как сумма

            (2.15)

где .

Таким образом, N-точечное преобразование  , можно произвести, вычислив два  точечных преобразования:  и , с последующим их объединением по формуле (2.15). На рисунке 2.16 показан этот прием для .

Если учесть, что ; ; , то можно сократить число умножений вдвое. Алгоритм БПФ с учетом выше приведенных соотношений приведен на рисунке 2.17.

Если  в свою очередь делить на 2, то вычисления каждого из преобразований  и  можно также свести к двум -точечным преобразованием, что вызывает дополнительное уменьшение требуемого количества операций, умножение. Такая сортировка осуществляет до тех пор, пока не образуется  последовательностей по два элемента в каждой. На рисунке 2.18 показано сведение 8-точечного преобразования к четырем 2-х точечным. На рисунке 2.19 дана полная схема вычислений, в которой дополнительно приведены вычисления, требуемые для 2-х точечных преобразований.

Если N представляется целой степенью двух , то вычисления разбиваются на  этапов, в каждом из которых требуется  комплексных умножений. Таким образом, количество умножений равно . Например, при -точечном преобразовании это чи число умножений окажется равным , в то время как при

N-точечном ДПФ потребовалось бы  операций умножения. Как видим, БПФ обеспечивает существенное сокращение объема вычислений (в данном примере в 200 раз).

Следует обратить внимание на то, что исходные отсчеты попадают на входы преобразователя не в естественном порядке , а в порядке .

Для получения номеров отсчетов в требуемой последовательности необходимо номера отсчетов, следующие в естественном порядке, представить в двоичной системе счисления, а затем в каждом из двоичных представлений переставить разряды, записав их в обратном, так называемом, двоично-инверсном порядке