Реферат: Алгоритм фильтрации, пример на основе БПФ

Для вычисления векторов и используем алгоритм 3-точечного БПФ (7.9).

Таким образом, мы как бы «вложили» алгоритм 3-точечного БПФ в структуру 2-точечного, который оперирует 3-точечными векторами. Характерной особенностью «вложенных» алгоритмов является то, что требуемое число умножений для N -точечного алгоритма равно произведению числа умножений, требуемых для каждого из частичных алгоритмов. Этот факт легко проверяется на приведенном выше алгоритме.

В заключение отметим, что принцип «вложения» малоточечных алгоритмов применяется также для вычисления N-точечных циклических сверток, когда N разлагается на взаимно простые множители, если имеются достаточно эффективные алгоритмы малоточечных сверток. Вложенные алгоритмы циклических сверток получили название по имени авторов алгоритмов Агарвала-Кули [3]. По сравнению с традиционными алгоритмами вычисления свертки с использованием БПФ алгоритмы Агарвала-Кули позволяют сэкономить число умножений почти на порядок.

Другими классами еще более экономных алгоритмов ДПФ и свертки являются алгоритмы, основанные на теоретико-числовых и полиномиальных преобразованиях, с которыми можно познакомиться в [3].

8. АНАЛИЗ ТОЧНОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ БПФ

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

Методику оценки вычислительных ошибок БПФ рассмотрим на примере реализации БПФ по основанию 2 и с прореживанием по времени. Рассматриваемая методика может быть применена и для анализа ошибок других алгоритмов БПФ. Будем предполагать, что: обрабатываемые числа представляются с помощью b₁ +1 разрядов, а коэффициенты - с помощью b₂ +1 разрядов с учетом знака; для аппроксимации произведений используется операция округления; масштабирование промежуточных результатов производится на входе каждой операции «бабочка» путем сдвига чисел на один разряд вправо (деление на два); входные данные пронормированы таким образом, что, и подчиняются равномерному закону распределения т. е. имеют математическое ожидание равное нулю, и дисперсию равную 1/3. Следовательно, среднеквадратическое значение (СК3) входной последовательности равно также 1/3. В соответствии с теоремой Парсеваля

выходная последовательность X(k) БПФ будет иметь СК3 N/3, где N -размер преобразования. С целью уяснения методики анализа ошибок получим алгоритм БПФ в аналитическом виде. Для этого в выражение для N=2^v - точечного ДПФ (5.1)

(8.1)

необходимо подставить двоичное разложение коэффициентов п и k:

(8.2)

в результате алгоритм БПФ можно представить, как ранее убедились, в виде v+1-ступенчатого процесса.

На ступени т=0 производится двоично-инверсная перестановка входной последовательности

На каждой из остальных v ступеней (т= 1, 2,….,v) производится преобразование типа «бабочка» выходной последовательности предыдущей ступени.

Так, на ступени т = 1 производится преобразование последовательности

X₀ (n₁ ,…,п_v ):

На ступени m=2 -преобразование последовательности Х₁ (п₁ , ..., n_v-1 , k₁ )

На m-й ступени

(8.3)

Так постепенно в двоичном представлении индекса последовательности Х_m с увеличением т происходит замена коэффициентов n_i на k_j

Наконец при т = v

Выходная последовательность последней ступени является искомой:

X(k)=X(k_v 2^v-1 +... +k¹ )=X_v (k_v 2^v-1 +k_v-1 2^v-2 +. .. +k₁ ).

Представим индекс элемента т-й ступени в виде