Инструменты пользователя

Инструменты сайта


examination:avs:question40

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

Спектральный анализ – это один из методов обработки сигналов, который позволяет охарактеризовать частотный состав измеряемого сигнала. Преобразование Фурье является математической основой, которая связывает временной или пространственный сигнал (или же некоторую модель этого сигнала) с его представлением в частотной области. Существенный вклад в развитие цифровых методов спектрального анализа внесли эффективные алгоритмы, предназначенные для вычисления дискретного преобразования Фурье, предложенные Д.Кули и Д.Тьюки в 1965 году. Набор алгоритмов, называемых алгоритмами быстрого преобра¬зования Фурье (БПФ), включает разнообразные методы умень¬шения времени вычисления дискретного преобразования Фурье (ДПФ). Поскольку вычисление ДПФ является основной операцией в большинстве задач спектрального анализа, то использование БПФ в некоторых встречающихся на практике случаях, позволяю¬щее ускорить вычисление ДПФ в 100 и более раз по сравнению с методом прямого вычисления ДПФ, имеет чрезвычайно важное значение и должно рассматриваться как неотъемлемая часть при¬менения методов цифровой обработки сигналов для спектрального анализа. Возможно, именно алгоритмы БПФ более чем какие-либо другие методы существенно расширили область применения методов спектрального анализа как средства обработки сигналов. Рассмотрим алгоритмы БПФ с основанием 2 и прорежи¬ванием по времени и по частоте.

Алгоритм БПФ с прореживанием по времени.

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

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

Базовая операция алгоритма с прореживанием по времени (так называемая «бабочка») состоит в том, что два входных числа А и В объединяются для получения двух выходных чисел X и Y следующим образом:

Еще одной особенностью алгоритма с прореживанием по време¬ни (как, впрочем, и большинства других алгоритмов БПФ) яв¬ляется необходимость такой перестановки элементов входной по¬следовательности, чтобы выходная последовательность X(k) имела естественный (прямой) порядок расположения, т. е. k = 0,1, …, N-1. В примере на рисунке 3 для этого требовался следующий порядок размещения входной последовательности: х(0), х(4), х(2), х(6), х(1), х(5), х(3) и х(7). Характер перестановки эле¬ментов входной последовательности может быть описан сравни¬тельно просто. В случае, когда N яв¬ляется степенью 2, входная последовательность должна быть рас¬положена в памяти в двоично-инверсном порядке для того, чтобы выходная последовательность получалась в прямом порядке. Двоично-инверсный порядок определяется следующим образом. Если записать порядковые номера элементов входной последова¬тельности в двоичном коде, используя L двоичных разрядов, при¬чем N = 2^L, а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов вход¬ной последовательности после их перестановки.

Так, для случая N = 8 = 2^3 прямой порядок номеров приведен в таблице слева, а двоично-инверсный порядок – справа. Таким образом, для двоич¬ной инверсии входной последовательности необходим соответст¬вующий алгоритм. Из сказанного выше ясно, что перестановку входной последо¬вательности можно произвести с замещением, меняя в парах мес¬тами числа с прямым и двоично-инверсным номерами и используя для этого лишь одну вспомогательную ячейку памяти. На рисунке 5 показана схема перестановки данных, представленных в таблице.

Алгоритм БПФ с прореживанием по частоте.

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

Базовая операция алгоритма с прореживанием по частоте (так называемая «бабочка») состоит в том, что два входных числа А и В объединяются для получения двух выходных чисел X и Y следующим образом:

examination/avs/question40.txt · Последние изменения: 2014/01/15 12:10 (внешнее изменение)