Глава 6.

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ.

1.1 Основные принципы быстрых алгоритмов

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

Вместо того , чтобы повышать быстродействие процессора

( или вместе ), можно попытаться организовать вычисление более эффективно, т.е. минимизировать количество вычислительных операций.

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

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

Рассмотрим простой пример: который тем не менее хорошо иллюстрирует главный принцип практических всех быстрых алгоритмов. Для оценки алгоритма в качестве единиц измерения сложности обычно используют число необходимых умножений и сложений.

Допустим, что требуется вычислить число А, равное

(1)

В том виде, в котором оно записано, это вычисление содержит четыре умножения и три сложения.

Несложно заметить, что эквивалентная форма

(2)

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

В отличие от этой простой задачи для большинства практических задач быстрые алгоритмы нельзя найти простым просмотром вычислений. Их построение требует весьмя развитой теории.

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

Дискретное преобразование Фурье (ДПФ) определяется выражением :

(3),

где

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

(4).

При этом x(n) и X(k) , вообще говоря, комплексные.

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

Как видно из (3), при прямом вычислении ДПФ для каждого k

требуется N умножений и N-1 сложений. Так как X(k) должно

вычисляться для N различных значений k, непосредственное

вычисление ДПФ x(n) требует умножений и N(N+1) сложений. Т.е. общее число операций приближенно равно 2 .

Первые подходы к улучшению эффективности вычисления ДПФ

спользовали свойство симметрии и периодичности величин :

1.

2.

Однако при сокращениях такого типа количество вычислений все еще остается равным .

В 1965 г. Кули(Cooley) и Тьюки(Tukey) предложили алгоритм

вычисления ДПФ, при котором количество вычислений пропорционально NlogN, что при больших N существенно сокращает объем вычислений.

Основной принцип этого алгоритма состоит в том, чтобы

разложить вычисление ДПФ на набор ДПФ меньшего порядка.

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

Первый, названный прореживанием по времени,получил такое

название от того, что в процессе вычисления x(n) (индекс n обычно ассоциируется со временем) разлагается на уменьшающиеся подпоследовательности.

По втором общем классе алгоритмов последовательность коэффициентов ДПФ X(k) разлагается на меньшие подпоследовательности, откуда идет название прореживание по частоте.