Алгоритм фильтрации, пример на основе БПФ (стр. 4 из 6)
 |
Таким образом, алгоритм простых множителей (АПМ) является способом представления одномерного ДПФ в виде многомерного, причем размерность зависит от числа взаимно простых сомножителей N. Алгоритм простых множителей имеет ступенчатую форму объединения мало точечных преобразований. В данном случае на первой ступени производится N1N2-точечных ДПФ, а на второй ступени - N2 N1-точечных ДПФ.
Впервые АПМ был предложен Гудом [3]. В том случае, когда используемые мало точечные алгоритмы синтезированы оптимальным образом по методу Винограда, получается алгоритм Гуда - Винограда [3]. Оптимальные мало точечные алгоритмы БПФ синтезируются путем сведения мало точечного ДПФ к совокупности циклических сверток. Для последних Виноградом [2] доказана теорема о существовании алгоритма вычисления с минимальным количеством умножений и был предложен метод синтеза, основанный на последовательном вычислении полиномиальных вычетов по неприводимым полиномам в поле рациональных чисел в соответствии с полиномиальным вариантом китайской теоремы об остатках [3].
7.3 Алгоритм Винограда
Дальнейшей экономии вычислений в случае разложения N на взаимно простые множители можно достичь, если ступенчатый характер объединения частичных мало точечных преобразований заменить вложенным. В этом и заключается идея алгоритма Винограда. Идею вложения мало точечных алгоритмов легче всего понять на примере.
Пример 5. Рассмотрим случай 6-точечного ДПФ, т. е. N=6. Пусть N1=2, N2=3. Приведем сначала алгоритмы мало точечных (2- и 3-точечных) ДПФ, синтезированные оптимальным образом по методу Винограда.
Алгоритм 2-точечного ДПФ
имеет вид
(7.8)где si-сложения, mi-умножения; Аi и ai - выходные и входные числа.
Алгоритм 3-точечного ДПФ
Имеет вид
, 
, 
, 
, 
(7.9) 
, 
, 
Преобразуем исходную 6-точечную последовательность в двумерную точечную в соответствии с (7.5) и (7.6). Тогда матрицу 6-точечного ДПФ можно представить в виде прямого произведения 2- и 3-точечных ДПФ и преобразование можно записать в виде:
, (7.10) 
, 
, 
, 
,Где
Применим к матричному преобразованию (7.10) алгоритм 2-точечного БПФ (7.8). В результате найдем векторы
и 
: 
Для вычисления векторов
и 
используем алгоритм 3-точечного БПФ (7.9).Таким образом, мы как бы «вложили» алгоритм 3-точечного БПФ в структуру 2-точечного, который оперирует 3-точечными векторами. Характерной особенностью «вложенных» алгоритмов является то, что требуемое число умножений для N-точечного алгоритма равно произведению числа умножений, требуемых для каждого из частичных алгоритмов. Этот факт легко проверяется на приведенном выше алгоритме.
В заключение отметим, что принцип «вложения» малоточечных алгоритмов применяется также для вычисления N-точечных циклических сверток, когда N разлагается на взаимно простые множители, если имеются достаточно эффективные алгоритмы малоточечных сверток. Вложенные алгоритмы циклических сверток получили название по имени авторов алгоритмов Агарвала-Кули [3]. По сравнению с традиционными алгоритмами вычисления свертки с использованием БПФ алгоритмы Агарвала-Кули позволяют сэкономить число умножений почти на порядок.
Другими классами еще более экономных алгоритмов ДПФ и свертки являются алгоритмы, основанные на теоретико-числовых и полиномиальных преобразованиях, с которыми можно познакомиться в [3].
8. АНАЛИЗ ТОЧНОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ БПФ
При реализации алгоритма БПФ, как и, при реализации других алгоритмов цифровой обработки сигналов, возникают вычислительные ошибки, округлением (усечением) произведений, квантованием коэффициентов и. возможно процедурой масштабирования чисел (с целью устранения переполнения сумматоров). При анализе ошибок будем принимать допущения об их характере, т. е. будем рассчитывать выходную ошибку БПФ как суперпозицию ошибок, вызванных каждым независимым источником ошибок.
Методику оценки вычислительных ошибок БПФ рассмотрим на примере реализации БПФ по основанию 2 и с прореживанием по времени. Рассматриваемая методика может быть применена и для анализа ошибок других алгоритмов БПФ. Будем предполагать, что: обрабатываемые числа представляются с помощью b1+1 разрядов, а коэффициенты - с помощью b2+1 разрядов с учетом знака; для аппроксимации произведений используется операция округления; масштабирование промежуточных результатов производится на входе каждой операции «бабочка» путем сдвига чисел на один разряд вправо (деление на два); входные данные пронормированы таким образом, что
, и подчиняются равномерному закону распределения т. е. имеют математическое ожидание равное нулю, и дисперсию 
равную 1/3. Следовательно, среднеквадратическое значение (СК3) входной последовательности равно также 1/3. В соответствии с теоремой Парсеваля 
выходная последовательность X(k) БПФ будет иметь СК3 N/3, где N-размер преобразования. С целью уяснения методики анализа ошибок получим алгоритм БПФ в аналитическом виде. Для этого в выражение для N=2v -точечного ДПФ (5.1)
(8.1)необходимо подставить двоичное разложение коэффициентов п и k:
(8.2)в результате алгоритм БПФ можно представить, как ранее убедились, в виде v+1-ступенчатого процесса.
На ступени т=0 производится двоично-инверсная перестановка входной последовательности
На каждой из остальных v ступеней (т=1, 2,….,v) производится преобразование типа «бабочка» выходной последовательности предыдущей ступени.
Так, на ступени т = 1 производится преобразование последовательности
X0(n1,…,пv):
На ступени m=2 -преобразование последовательности Х1 (п1,..., nv-1, k1)
На m-й ступени
(8.3)Так постепенно в двоичном представлении индекса последовательности Хmс увеличением т происходит замена коэффициентов ni на kj
Наконец при т = v
Выходная последовательность последней ступени является искомой:
X(k)=X(kv2v-1 +... +k1)=Xv(kv2v-1 +kv-12v-2+... +k1).
Представим индекс элемента т-й ступени в виде
(n1,..., nv-m,km,,..., k1)=2v-1n1+2v-2n2+… +2mnv-m+2m-1km+…+k1=2ml+q (8.4)
Тогда число Xm(2ml+q) можно рассматривать как q-й элемент l-го блока т-й ступени.
Пример б. Рассмотрим описанную процедуру синтеза алгоритма БПФ с прореживанием по времени на примере 16-точечного ДПФ. В этом случае v=4. Индексы n и k представим следующим образом: n=n423+n322+n22+n1, k=k423 +k322 +k22+k1.