Гольденберг Л.М. и др. - Цифровая обработка сигналов (Справочник), страница 3

Элементы %-2)г равны (1-2(п )1) 1у -е (е Ц7 — (ен)е(»(ое «)) 1 1 У Дискретное преобразование Фурье вводится для представления как периодических последовательностей с периодом У отсчетов, так и последовательностей конечной длины У. Коэффициенты ДПФ конечной последовательности равны значениям ее Л-преобразования в У точках, равномерно распределенных ай по единичной окружности, т.

е. Х(Ь)=Х(г))г=е( У, й=О,..., У вЂ” 1. Сопоставляя Фурье. преобразование и ДПФ, можно отметить следующее. Фурье-преобразование и понятие «спектр» относятся к бесконечной последовательности х(пТ) в целом [см. (1.10)]. В тех случаях, когда речь идет о преобразованиях спектра бесконечной последовательности в целом [см„ например, (1.11), (1.12)), ДПФ применяется относительно редко. Так, сдвиг спектра [см. (1.12)1 н инверсия спектра (см.

пример 1.5) выполняются умножением отсчетов х(пТ) на множители, зависящие от и. Цифровая фильтрация (см, разд. 2), реализующая изменение спектра входного сигнала по заданному закону, также выполняется, как правило, без применения ДПФ. Исключением, но весьма важным является применение ДПФ для вычисления линейной свертки (см. 1.4.3), что в сочетании с методами секционнрования свертки (см.

1.4.4) позволяет эффективно реализовать нерекурсивную цифровую фильтрацию бес«ы~~о ~о о~а~ донген (м. р ед. 2). ((~ыр р онр~ е дур (ю. (1.19) н (1.20)) ~ нонн е е юд конечной последовательностью У отсчетов нли над периодической последовательностью, у которой период состоит из У отсчетов. (Поскольку характеристики спектра последовательности, такие как спектральная плотность мощности, амплитуды и фазы отдельных частот (см.

разд. 8), определяются всегда с использованием конечного числа отсчетов этой последовательности, ДПФ является 1 одним из важнейших средств их определения. 1.3.2. Свойства дискретного преобразования Фурье Линейность. Если Х(Ь) и У(я) есть ДПФ последовательностей х(пТ) и у(пТ) соответственно, то ДПФ последовательности ах(пТ)+Ьу(пТ), где и и Ь вЂ” произвольные константы, равно аХ(й)+ЬУ(й). Сдвиг, Пусть Х(й) — ДПФ последовательности х(пТ), а последовательность у(пТ) получается из последовательности х(пТ) путем сдвига (в случае конечной последовательности — кругового сдвига) на пе отсчетов (рнс. 1.4). Тогда ДПФ последовательности у(пТ) равно У(й) =Х(й) 1рф~ Аналогичный результат справедлив для сдвига коэффициентов ДПФ. Если Х(Ь) и У(Ь) есть ДПФ последовательностей х(пТ) и у(пТ) соответственно н У(й) =Х(й — Кр), то у(пТ) =х(пТ) йГ~~" '. На рис.

1.4 приняты следующие обозначения: х,(пТ) — периодическая последовательность, причем х„(пТ) =х(пТ) при п=О, 1... У-1; х,((п — пр)Т)— периодическая последовательность, сдвинутая относительно хе(пТ) на пе отсче. тов; х((п — п,)Т) — конечная последовательность, полученная круговым сдвигом х(пТ) на и, отсчетов; х((п — пп)Т) =х ((и — пе)Т) при п=О, 1,..., У вЂ” 1. Свойства симметрии. Если последовательность х(пТ) является действительной, то ее ДПФ удовлетворяет следующим условиям симметрии: Ке (Х (й)) = Ке (Х (У вЂ” й)); 1гп (Х (й)) = — 1гп (Х ()т' — й)); ] Х (й)] = [ Х ()Ч вЂ” й)]; агн Х (й) = †а Х (л/ — й). Дискретное преобразование Фурье симметричной последовательности х(пТ) =х((И вЂ” и) Т) является действительным. хр/!п-лр]Т), лре2 ф лт х((л-пр) Т) у!х у/ л? г) Рис.

1А Свойства симметрии позволяют с помощью 'одного ДПФ преобразовывать одновременно две действительные последовательности. Пусть действительныв последовательности х(пТ) и у(пТ) имеют ДПФ Х(й) и У(й) соответственно, а последовательность и(пТ) =х(пТ)+1у(пТ) имеет ДПФ У(й) =Х(й)+1У(й). Тогда: Ке (Х (й) ) = [Ке (У (й) ) + Ке (У (М вЂ” й)) ]/2; 1тп (г (й)) =. [Ке (У (Л! — й)) — Ке (У (й))]/2; Ке (у (й)) = [1гп (У (й)) + 1п! (У (Л/ — й) Ц/2; 1гп (Х (й)) = [1!п (У (й)) — 1п! (У (М вЂ” й)) ]/2.

Круговая свертка (см. 1.4.1). Пусть х(пТ) и у(пТ) имеют ДПФ Х(й) !к У(й) соответственно. Если последовательность и(пТ) равна круговой свертке последовательностей х(пТ) и у(пТ): Л-! и (и Т) = ~~ х (1Т) у ((п — 1) Т), )=о п=О,..., )х' — 1, то ее ДПФ равно У(й) =Х(й)У(й). Если х(пТ) и у(пТ) имеют ДПФ Х(й) и У(й) соответственно, то ДПФ последовательности и(пТ) =х(пТ) у(пТ) равно (с точностью до постоянного множителя) круговой свертке Х(й) и У(й):  — 1 У(й)=- — ,'«~ ~Х(1)1'(й — 1), й=О,..., Л/ — 1. )!/ )=в Сопряженная формула обращения. Обратное ДПФ (1.20) можно вы~повять с помощью формулы для прямого ДПФ З! — 1 х (и Т) = Р (пТ), где Р (и Т) = — 1', Х (й) йу~~, и = О,..., У вЂ” 1 0==о (черта сверху означает комплексное сопряжение).

И$И 1.3.3. Многомерное дискретное преобразование Фурье Многомерным (1-мерным) ДПФ 1-мерных последовательностей называется пара следующих преобразований: №1И,! 101 — 1 Х(й1 пя ..., й1) = ~~1~ У, ... ~ х(п, Т, и, Т,..., и! Т) Я71ч', '...Ят,,~! л,=0 л,=о л1:~О й1=0,..., У,— 1,..., й1=0,..., У1 — 1; (1.22) № — 1 1Ч,— 1 !в Ф вЂ” 1 «(пхТ, п,Т,..., п1Т)= ~! У.... ~, 'Х(й„й„..., й1)Х УУ...У ь,=о 1,=0 21=0 Хцт а~л~ % аалх ур л1"! !чу м~ з11 ю пг — — О,..., У1 — 1,..., п1=0,..., У1 — 1. (1.23) Преобразованпе (1.22) называется прямым, а преобразование (1.23) — обратным многомерным ДПФ. 1.3.4.

Алгоритмы БПФ с основанием 2 Вычисление ДПФ непосредственно по формуле (1.19) требует весьма большого числа операций: примерно У' операций умножения и № операций сложения комплексных чисел. Быстрым преобразованием Фурье (БПФ) называют набор алгоритмов, позволяющих резко уменьшить число операций, необходимое для вычисления ДПФ. Алгоритмы с основанием 2 используются при У=2ч, т)0, т — целое.

Основная идея, лежащая в их основе, заключается в сведении вычисления исходного У-точечного ДПФ к вычислению нескольких №-точечных ДПФ, причем Уг=2ч~ и У~ч: У. Алгоритмы, при реализации которых требуется перестановка отсчетов х(пТ) входной последовательности (см. пример 1.6), называются алаоритмами с прореживанием по времени, Алгоритмы, прн реализации которых требуется перестановка отсчетов Х(й) выходной последовательности( см. пример 1.7), называются алгоритмами с прореживапием по частоте. По эффективности зти две разновидности алгоритмов эквивалентны н позволяют уменьшить число требуемых арифметических .операций примерно в У/ч раз по сравнению с прямым методом вычисления ДПФ.

Алгоритм с прореживаннем по времени. Если последовательности х(пТ) длиной У=2ч разделить на две У(2-точечные последовательности, состоящие нз х(пТ) с четными и нечетными номерами соответственно, то выражение для ДПФ (1.19) можно записать в виде 1Ч/2 — 1 Л/2 — 1 Х(й)= ~ х(2пТ)Я7",.~~2+И'з1 ~~ х((2п+!) Т) ИУ",у~2, А=О, °, У вЂ” 1. л=о л=о (1.24) Ка дая из сумм в (1.24) является ЛЧ2-точечным ДПФ, которое аналогичным обр зом можно представить через Л/4-точечные, а АЧ4-точечные через У18- точечные и т. д., пока не останутся только 2-точечные. Таких ступеней пре образования всего т=1ойдк.

На и-ступени (и=О,..., э — 1) производится пре. образование множества Ф комплексных чисел Х (п) в множество М комплексных чисел Х +,(и) в соответствии с базовой операцией «бабочка», описывае. мой выражениями: Х„+д'(Р)=Х„,(Р)+УРкХ ®; Х +,(4)=Х„(Р) — УРкХ Ж, (1.25);:;:ч1 где р, д и г зависят'пт номера ступени и и могут быть определены из выра. жений, аналогичных (1.24).

Входная последовательность нулевой ступени Хо(и) получается перестановкой последовательности х(пТ) в соответствии с двоичной инверсией номе ров, т. е. число х(иТ) с номером (и„..., ио) в двоичном представленин запоминается на месте Хо(по,-, п„д) Направленный граф, реализующий «бабочку», изображен на рис. 1.5. Здесь сигналы ветвей, входящих в узел, суммируются; сигнал ветви умножается на Хпт 1(Р1 Х „~(6 ХтФ Хи,Ю -1 Рис. 1.5 коэффициент, записанный рядом с ветвью. Если коэффициент не указан, та он полагается равным 1. к1з — д Х(2й) = ~ (хд(п Т)+хо(пТ)) (Ркк1з', л=о к12 — 1 Х(2й+1) — ~ (х (пТ) — х (иТ))'Рлч (Рл л=о 1б (1.26) Пример 1.6.