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

(1.2)


причем является периодической последовательностью с периодом N,так как т=О, 1, 2… Непосредственное вычисление ДПФ (5.1) при комплексных значениях х(пТ) требует для каждого значения k (N - 1)умножений и (N - 1) сложений комплексных чисел или 4 (N -1) умножений и (2N - 2) сложений действительных чисел, а для всех N значений k=0, 1,…, N -1 требуется примерно N2 умножений и N2 сложений комплексных чисел. Таким образом, для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ (1.1) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени процессов и спектров.

Быстрым преобразованием Фурье называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности ДПФ (1.1). Исходная идея этих алгоритмов состоит в том, что N-точечная последовательность разбивается, на две более короткие, например на две (N/2) точечные последовательности, вычисляются ДПФ для этих более коротких последовательностей и из этих ДПФ конструируется ДПФ исходной последовательности. Для двух (N/2)-точечных последовательностей требуется примерно умножений комплексных чисел, т. е. число умножений (а также сложений) уменьшается примерно в 2 раза. Аналогично вместо вычисления ДПФ (Н/2)-точечной последовательности можно вычислить ДПФ для двух (Н/4)-точечных последовательностей и таким образом вновь уменьшить требуемое число умножений и сложений. Если N=2v , v>O и целое, то процесс уменьшения размера ДПФ может быть продолжен до тех пор, пока не останутся только 2-точечные ДПФ. При этом общее число этапов вычисления ДПФ будет равно v=log2 N, а число требуемых арифметических операций для вычисления N-точечной ДПФ будет порядка Nv , т.е. уменьшается примерно в N/log2 N раз. Так, при N=1000 для прямого вычисления ДПФ согласно (1.1) требуется примерно N2 = 106 операций комплексных умножений и сложений, а при использовании алгоритмов БПФ таких операций требуется всего порядка 104 , т. е. объем вычислений сокращается примерно на два порядка.

Рассмотрим два алгоритма БПФ: с прореживанием по времени (в которых требуется перестановка отсчетов входной последовательности х(пТ)) и с прореживанием по частоте (в которых требуется перестановка отсчетов выходной последовательности Х(k) ).


2. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ВРЕМЕНИ

Пусть требуется вычислить ДПФ (1.1) при N= 2v , гдеv>O. где v>O целое (если N 2V, то можно последовательность х(пТ) дополнить в конце нулевыми элементами так, чтобы длина результирующей последовательности была степенью 2).

Разобьем исходную N-точечную последовательность х(пТ)=хv (п), где v =log2 N. п=О.. .., N -1, на две (N/2)-точечные последовательности Хv-1,0 (п) и Хv-1,1 (п), состоящие соответственно из четных и нечетных членов х (пТ), т. е.

(2.1)

При этом N-точечное ДПФ (1.1) можно записать в виде

(2.2)

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

(2.3)

Где и - (N/2)-точечные ДПФ соответственно последовательностей и :


; .

Так как Xv (k) должно быть определено для N точек (k=0, 1, ..., N-1) , а Хv-1,0 (k) и Хv-1,1 (k) определяются толькo для N/2 точек (k=0, 1,..., N/2-1), доопределим (2.3) для значений k=N/2, N/2+1,...,N-1; учитывая, что Хv-1,0 (k) и Хv-1,1 (k) периодические функции с периодом Н/2, можно записать

Xv (k+N/2)= Хv-1,0 (k+N/2) + Хv-1,1 (k+N/2)= Хv-1,0 (k)- Хv-1,1 (k),

(2.4)

Так как = = -1.

Формулы (2.3) и (3.4) дают алгоритм вычисления N-точечной ДПФ через (N/2)-точечных ДПФ. Этот алгоритм можно представить направленным графом, имеющим вид «бабочки»

Рисунок 3 – граф имеющий вид «бабочки»

(рис.3, а), в котором выходные числа с и d получаются из входных чисел а и b по правилам

(2.5)

В качестве примера граф на рис.3, б представляет операции (2.3) и (2.4). Аналогично можно теперь выразить (N/2)-точечные ДПФ Хv-1,0 (k) и Хv-1,1 (k) через (N/4)-точечные ДПФ:

(2.6а)


И

(2.7б)

где Хv-2,0 (k) и Хv-2,1 (k) - соответственно (N/4)-точечные ДПФ четных Хv-2,0 (n) и нечетных Хv-2,1 (п)

членов последовательности Хv-1,0 (п), а Хv-2,2 (k) и Хv-2,3 (k)-соответственно (N/4)-точечные ДПФ четных Хv-2,2 (п) и нечетных Хv-2,3 (п) членов последовательности Хv-1,1 (п).

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