Xreferat.com » Рефераты по математике » Алгоритм фильтрации, пример на основе БПФ

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

их приведение к естественному порядку связано с инверсией двоичного представления индексов k в вычисленных значениях Х (k).

Итак, запишем ДПФ (1.1) в виде:

 (4.1)        

Учитывая, что = получаем

. (4.2)

Подставив вместо k в (4.2) значение 2k или (2k+ 1), получим выражения для четных и нечетных отсчетов ДПФ:   .

          

; (4.3)

, (4.4)


где теперь для значений:

 

Х0 (п)=х(п) +x(n+N/2);  (4.5)

Х1(п)=х(п) -х(n+N/2). (4.6)

 

Рисунок 5 - Выполнение базовой операции «бабочка»

Следовательно, вычисление N-точечного ДПФ X(k) сводится к вычислению двух N/2-точечных ДПФ при четных и нечетных значениях k для функций х0(п) и x1 (п) и выполнению базовой операции «бабочка» (рис.5) отличие операции «бабочка» здесь заключается в том, что комплексное умножение выполняется после операции сложения-вычитания.

Ту же процедуру можно теперь применить к x0 (п) и х 1 (п) и перейти от N/2-точечных ДПФ к N/4-точечным ДПФ и, таким образом, свести вычисление Х (2k) и Х (2k + 1) через Х (4k), X(4k+2), X(4k+ 1), X(4k+3). Продолжив этот процесс, перейдем в конечном итоге к 2-точечным ДП Ф с последующим прямым вычислением всех выходных отсчетов Х (k). Полный алгоритм БПФ с прореживанием по частоте и его программная реализация аналогичны рассмотренным выше для метода БПФ с прореживанием по времени.

Необходимо отметить, что в обоих алгоритмах БПФ - и с прореживанием по времени, и с прореживанием по частоте требуется примерно Nlog2 N операций (комплексных умножений) и оба алгоритма могут быть реализованы по способу с замещением, используя только один массив ячеек памяти. В обоих алгоритмах должна быть предусмотрена процедура двоичной инверсии - на входе (при прореживании по времени) или на выходе (при прореживании по частоте).


5. ПРИМЕНЕНИЕ МЕТОДА БПФ ДЛЯ ВЫЧИСЛЕНИЯ ОБРАТНОГО ДПФ (ОДПФ)

По определению (1.2) ОДПФ х(пТ) N-точечной последовательности X(k), k=0, 1,..., N-1, выражается соотношением

(5.1)

причем в общем случае и х(пТ), и Х(k)-комплексные. Пусть х(пТ) и Х*(k)-последовательности, комплексно сопряженные соответственно с х(пТ) и X(k). Согласно (5.1) можно записать

 (5.2)

 

Но выражение суммы в правой части (5.2) есть прямое ДПФ последовательности Х*(k), k=0,..., N-1, и, следовательно, эта сумма может быть вычислена при помощи рассмотренных алгоритмов и программ БПФ.

Таким образом обеспечивается вычисление последовательности Nx* (пТ) и для определения х(пТ) остается взять комплексно сопряженное с Nx*(пТ) выражение и разделить его на N:

 

 


(5.3)

 


6. ПРИМЕНЕНИЕ БПФ ДЛЯ ВЫЧИСЛЕНИЯ РЕАКЦИИ ЦФ

Вычисление реакции у(пТ) ЦФ с импульсной характеристикой h(пТ), п=0, 1,..., N-1, на входное воздействие х(пТ), п=О, 1,...M -1, может быть выполнено на основе алгоритма свертки

 (6.1)

при п=0, 1,..., N+M-2.

Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности у(пТ) ЦФ. С этой целью следует определить ДПФ H(k) и X(k) в N+M-1 точках для последовательностей h(пТ) и х(пТ), затем определить ДПФ Y(k)=H(k)X(k) выходной последовательности у(пТ). Вычисление у (пТ) по ОДПФ Y(k) выполняется, например, по алгоритму (5.3). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что если длина М последовательности х(пТ) велика, то реализация упомянутого выше алгоритма вычисления у(пТ) связана со значительной временной задержкой (для накопления всех М выборок х(пТ)). С целью уменьшения этой задержки можно входную последовательность х(пТ) разбить на отрезки xi(пТ) каждый длиной L и обрабатывать каждый из них независимо от других. Представим

 (6.2)

Тогда можно (6.1) записать в виде

 


                                                                   (6.3)


Где частная свертка

 


                                                                   (6.4)

 

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


7. ДРУГИЕ БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

7.1 Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота

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

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

Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на основе которых впоследствии возникло множество различных эффективных модификаций. Это: 1) обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота; 2) алгоритм простых множителей Гуда-Винограда; 3) алгоритм Винограда.

Для простоты изложения везде будем полагать N=N1N2, где N - длина преобразования. Очевидно, приводимые ниже положения легко могут быть перенесены на более общий случай, когда

Обобщенный алгоритм Кули-Тьюки с произвольным основанием с множителями поворота. Итак, пусть N=N1N2, гдеN1 и N2 - положительные целые. Покажем, что в этом случае вычисление исходного N-точечного ДПФ можно свести к вычислению N1 N2-точечных и N2 N1-точечных ДПФ и N умножениям на множители поворота . Для этого в выражения для ДПФ (1.1)

 


                                                                  (7.1)

где , необходимо сделать подстановку:

 

k=k1 +k2N2, k1=0, …., N2-1; k2=0, …., N1-1; (7.2)

n=n1 +n2N2, n1=0, …., N2-1; n2=0, …., N2-1. (7.3)

Рисунок 6 - Сигнальный граф алгоритма

Тогда ДПФ (7.1) преобразуется к виду

 


                                                                                     (7.4)

Таким образом, полученный алгоритм включает в себя две основные ступени: на первой ступени переставленные в соответствии с (7.3) входные выборки подвергаются N2-точечному преобразованию Фурье. На второй ступени производится вычисление N1-точечных ДПФ. Между первой и второй ступенями осуществляется операция поворота путем умножения на поворачивающие множители . Полученная последовательность на выходе ДПФ должна быть переставлена в соответствии с (7.2).

Пример 4. Пусть N=6, N1=3, N2=2. Положим k=k1+k2*2; n=n1+ +n2*3; n1k2=0,1,2; n2k1=0, 1.

Тогда

 


Соответствующий сигнальный граф алгоритма изображен на рис.6.

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

7.2 Алгоритм простых множителей

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

Чтобы избавиться от множителей поворота, нужно произвести перестановку входной и выходной последовательностей, отличную от (7.2) и (7.3). Такой перестановкой может быть следующая:

для входной последовательности

              (7.5)

n1.=0,...., N1-1; п2=0,..., N2-1;

для выходной последовательности

(k1N2 +k2)=X((s1k2N1 + s2k1N2)mod N),            (7.6)

k1 =0,..., N1 -1; k2 =0,..., N2 -1,

где запись п mod N означает «остаток от деления п на N», а s1 и s2 определяются из следующих уравнений в соответствии с китайской теоремой об остатках о восстановлении целого числа по его вычетам: s1N1 = 1mod N2, s1<N2, s2N2 == 1modN1, s2 <N1. Тогда        алгоритм N=N1N2 - точечного ДПФ представляется в виде

 


Таким образом, алгоритм простых множителей (АПМ) является способом представления одномерного ДПФ в виде многомерного, причем размерность зависит от числа взаимно простых сомножителей 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) производится преобразование типа «бабочка» выходной последовательности предыдущей

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: