Бпф с прореживанием по частоте

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

При таком разбиении N-точечное ДПФ последовательности можно записать в виде

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

Запишем выражения отдельно для четных и нечетных отсчетов ДПФ:

Фиг. 6.9. Переход от восьмиточечного ДПФ к двум четырехточечным ДПФ при прореживании по частоте.

Из выражений (6.21) и (6.23) видно, что четные и нечетные отсчеты ДПФ можно получить из -точечных ДПФ последовательностей и , равных

Таким образом, снова вычисление -точечного ДПФ удалось свести к вычислению двух -точечных ДПФ. На фиг. 6.9 эта методика иллюстрируется для случая N = 8.

Описанную методику можно применить повторно и представить каждое из -точечных ДПФ в виде комбинации двух -точечных ДПФ. На фиг. 6.10 и 6.11 показан переход от четырехточечных ДПФ (фиг. 6.9) к двухточечным ДПФ с последующим прямым вычислением двухточечных ДПФ.

Сравнение алгоритмов, иллюстрированных на фиг. 6.3 и 6.11, позволяет выявить два очевидных различия между ними. Во-первых, при прореживании по времени порядок следования входных отсчетов двоично-инверсный, а выходных — прямой и наоборот при прореживании по частоте (фиг. 6.11). Однако это отличие кажущееся, поскольку в обоих алгоритмах порядок следования входных отсчетов может быть прямым, а выходных — двоично-инверсным и наоборот. Второе отличие заключается в несколько ином выполнении базовой операции (см. фиг. 6.12 и 6.4): при прореживании по частоте комплексное умножение выполняется после сложения — вычитания.

Фиг. 6.10. Переход от четырехточечных ДПФ на фиг. 6.9 к двухточечным ДПФ.

Фиг. 6.11. Полный направленный граф восьмиточечного ДПФ с замещением и прореживанием по частоте.

Фиг. 6.12. Базовая операция алгоритма БПФ с прореживанием по частоте.

Легко заметить и сходство между алгоритмами с прореживанием по времени и по частоте. В обоих случаях при вычислении ДПФ требуется около N log2 N операций, вычисления могут быть проведены с замещением и должно быть предусмотрено выполнение двоичной инверсии. В разд. 6.8 будет строго показано, почему эти, казалось бы, различные алгоритмы имеют такое сходство. Будет рассмотрен единый подход к БПФ, для которого алгоритмы с прореживанием по времени и по частоте оказываются частными случаями. С помощью такого подхода проанализирован также случай, когда N является составным целым числом, но не обязательно равным степени 2.

© 2019 Научная библиотека

Копирование информации со страницы разрешается только с указанием ссылки на данный сайт

«Быстрое преобразование Фурье».

Дискретное преобразование Фурье (ДПФ) периодического дискретного сигнала x ( n ) с периодом N определяется как

(12.1),

где — основная частота преобразования ( бин ДПФ).

Выражение (12.1) можно переписать в виде

(12.2),

где (12.3).

Коэффициент W_N называется поворачивающим множителем. Легко показать, что является периодической функцией с периодом N

(12.4).

Поэтому ДПФ X ( k ) также является периодической функцией по аргументу k с периодом N .

Дискретное преобразование Фурье может быть использовано и для представления сигнала x ( n ) конечной длины N , определенного при n =0,1,…, N -1 и равного нулю вне интервала [0, N -1]. Действительно, такой сигнал можно рассматривать как один период соответствующего периодического сигнала и сипользовать преобразования (12.2). Следует только считать, что вне интнрвала [0, N -1] X ( k ) и x ( n ) равны нулю.

Если сравнить ДПФ конечного дискретного сигнала со спектром этого же сигнала, определяемым выражением

(12.5),

то очевидно, что ДПФ представляет собой N отсчетов спектра, взятых на периоде с интервалом дискретизации по частоте, равным .

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

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

Так, если исходный N -отсчетный сигнал разбить на два N /2-отсчетных сигнала, то для вычисления ДПФ каждого из них потребуется около ( N /2) 2 комплексных умножений. Тогда для вычисления искомого N -отсчетного ДПФ потребуется порядка 2( N /2) 2 = N 2 /2 комплексных умножений , т.е. вдвое меньше по сравнению с прямым вычислением. Операцию разбиения можно повторить, вычисляя вместо ( N /2)-отсчетного ДПФ два ( N /4)-отсчетных ДПФ и сокращая тем сасым объем вычислений еще в два раза. Выигрыш в два раза является приблизительным, поскольку не учитывается, каким образом из ДПФ меньшего размера образуется искомое N -отсчетное ДПФ.

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

Первый алгоритм называется алгоритмом Б ПФ с пр ореживанием по времени.

Пусть задан N -отсчетный дискретный сигнал x ( n ). Примем, что N равно степени двойки. Если это не так, то всегда можно легко доплнить заданный сигнал нулевыми отсчетами до количества отсчетов, равного ближайшей степени двойки.

Разобъем исходный сигнал x ( n ) на два N /2-отсчетных сигнала x ₁ ( n ) и x ₂ ( n ), составленных соответственно из четных и нечетных отсчетов исходного сигнала x ( n )

(12.6).

N -точечное ДПФ сигнала x ( n ) можно записать как

(12.7).

С учетом того, что

(12.8)

(12.9)

(12.10),

где X ₁ ( k ) и X ₂ ( k ) – N /2-отсчетные ДПФ сигналов x ₁ ( n ) и x ₂ ( n ) соответственно.

Таким образом N -точечное ДПФ X ( k ) может быть разложено на два N /2-точечных ДПФ, результаты которых объединяются согласно (12.10).

Если бы N /2-точечные ДПФ вычислялись прямым способом, то для вычисления N -точечного ДПФ потребовалось бы ( N 2 /2+ N ) комплексных умножений. При больших N (когда N 2 /2>> N ) это позволяет сократить время вычислений на 50%.

Поскольку X ( k ) определено при , а X ₁( k ) и X ₂( k ) определены при , необходимо доопределить формулу (12.10) для . Учитывая, что X ₁( k ) и X ₂( k ) – периодические функции с периодом N /2, можно записать

(12.11),

поскольку .

Поэтому окончательно для N -точечного ДПФ можно записать

(12.12).

На рис.12.1 представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных ДПФ.

В БПФ с прореживанием по частоте выделяют в исходном ДПФ два слагаемых, соответствующих двум следующим друг за другом половинам исходной последовательности:

. (3.1)

Из второй суммы можно выделить множитель

.

Этот множитель равен 1 или -1 в зависимости от четности номера вычисляемого спектрального отсчета , поэтому в последующем четные и нечетные номера отсчетов частоты рассматриваются отдельно.

После выделения множителя ±1 комплексные экспоненты в обеих суммах (для четных и нечетных номеров спектральных отсчетов) становятся одинаковыми и их можно вынести за скобки:

, (3.2)

. (3.3)

Записанные суммы представляют собой ДПФ суммы и разности половин исходной последовательности, при этом разность перед вычислением ДПФ умножается на комплексные экспоненты . Каждое из двух используемых здесь ДПФ имеет размерность N/2.

Таким образом, при вычислении БПФ с прореживанием по частоте из исходной последовательности длиной N получают две последовательности и длиной N/2:

, (3.4)

. (3.5)

ДПФ последовательности дает спектральные отсчеты с четными номерами, ДПФ последовательности — с нечетными номерами:

, (3.6)

. (3.7)

Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ с прореживанием по частоте показан на рисунке 3.1.

Так как комплексный экспоненциальный множитель в данном алгоритме применяется к результату вычитания двух сигналов, то «бабочка» БПФ с прореживанием по частоте имеет другую структуру: рисунок 3.2.

Алгоритм БПФ с прореживанием по частоте применяется реже, чем с прореживанием по времени, так как в последнем случае на выходе получаем отсчеты ДПФ в естественном порядке следования.

Рисунок 3.1 – вычисление 8-точечного ДПФ с использованием двух 4-х точечных ДПФ путем прореживания по частоте

Рисунок 3.2 – условное обозначение «бабочки» и ее структурная схема при прореживании по частоте

Свойства БПФ

1. Наибольшее ускорение вычислений благодаря применению БПФ достигается при длине исходной последовательности, равной целочисленной степени 2. Снижение вычислительных затрат по сравнению с непосредственным использованием ДПФ составляет раз.

2. Экономия вычислительных затрат достигается за счет объединения всех слагаемых, умножаемых на одинаковые множители и трансформации некоторых множителей в 1 или -1.

3. Если длина исходной последовательности – простое число, вычисление ДПФ возможно только по формуле ДПФ либо за счет дополнения исходной последовательности нулями.

4. БПФ не является приближенным алгоритмом. При отсутствии вычислительных погрешностей он дает точно такой же результат, что и исходное ДПФ.

5. Алгоритм БПФ предназначен для одновременного расчета всех спектральных отсчетов. Если необходимо получить лишь отдельные отсчеты, то может оказаться предпочтительной прямая формула ДПФ или известный алгоритм Герцеля.

Дата добавления: 2017-09-19 ; просмотров: 729 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ