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

  • Просмотров 5018
  • Скачиваний 45
  • Размер файла 588
    Кб

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

для вычисления N-точечной ДПФ будет порядка Nv, т.е. уменьшается примерно в N/log2N раз. Так, при 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(п).