Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 28
Текст из файла (страница 28)
Для упрощения выражений последовательиосп, данных х(пТ) записывается как х(п). З.З, Свойства ДПФ КРУговУю коРРевлвию пеРиодических последовательностей конечной длины х»р(Р) н х, (и) можно определить как »2-1 гаа»аа(а) Х~~ х»р(п)хзр(п + Я)~з — О~ ° ° ° ~ А" 1 (3.31) ас (поскольку круговая корреляция определяется с помощью ДПФ). Следовательно, „2(~) = Е 1[Х;(/с)Х2(к)]. (3.32) Уравнение (3.32) называют в»еоремой о корреляции. Круговую корреляцию, которая задается уравнением (3.32), можно преобразовать в линейную с помощью дополняющих нулей. Теперь для последовательностей х,(п) с длиной 121 и хз(п) с длиной »У2 нх линейная корреляция будет иметь длину АР1 + Мз — 1. Для этого последовательность х1(п) заменяют последовательностью х„(п), которая состоит из последовательности х,(п) с добавленными Юз — 1 нулями, а последовательность хз(п), дополненная А»1 — 1 нулями, превращается в последовательность х2.(п).
Теперь линейная взаимная корреляция последовательностей х1(п) и хз(п) задается как г (з) — а'Р [Ха (й)Х2 (/с)] (3.33) где Х1а(а) ро[Х!а(п)] и Хза(а) а Р[Х1а(п)] ° хзр(п) = х1р(п) О» хзр(Р) = Рр'.[Х1(Й)Х2(lс)], (3.34) где Оа обозначает круговую свертку, а х»р(п), х2,(п), хз (и) — конечные периодиче- ские последовательности одинаковой длины. Аналогично уравнению (3.31) хзр(п) можно также записать как хзр(п) = ~ х»р(111)хзр(п — Р»). (3.35) Кроме того, Хз()») = Х1(а)Х2(а), (3.36) где Хз()с) = Го[ха(п)].
Более полно эта тема освещается в главе 5. 7. ДПФ также можно использовать для вычисления круговой и (с помощью дополняющих нулей) линейной свертки. Эти свертки могут быть как во временной, так и в частотной области. В теореме о свертке во временной области говорится, что З.б. Апюритм быстрою преобразования Фурье с децимацией во временной области 133 - " ' г(. ' ' 4 ВтМ1Ь;"=Ми:гэйл( -*,, Вте(ВФЙ'батая-.тМ/йЬ' (бтййевкявв(Ъ~'-'.П Х (ь) ~Ч, х е-г см/и ь = 0,...,)У вЂ” 1.
(3.41) КРоме того, выРажение е гг'/~ запишем как И//т, следовательно =е н=с (3.42) Так что уравнение (3.41) приобретает внд (т-1 Х,(/с) = ~~ х„И/,",,", 1=0,...,Ю вЂ” 1. (3.43) п=с Здесь следует обратить внимание на некоторые соотношения, содержащие И/,т. Вопервых, 14/г (е-гл1//т)г -гг г/и — гм/(н/г) И/ (3.44) Во-вторых, )4г(ь+/т/г) 14гь 14////г И, ь — (ггн///1(/т/г1 И, ь — нг /т — и (т — —,те яе (3.45) Для удобства обобщим полезные результаты, касающнеся И//т, н получим -г /(т (т = е И/(т И /т/г ~ (3.46, а) (3.46, б) (3.46, в) В этом разделе будет показано, как внутреннюю избыточность вычислений, свойственную ДПФ, можно использовать для уменьшения числа требуемых операций н, соответственно, увеличения сюростн вычислений.
Для 1024-точечного ДПФ обьем требуемых вычислений можно снизить в 204,8 раз. Соответствующие алгоритмы получили название "быстрого преобразования Фурье*' (БПФ). Если этот алгоритм прнменяется во временной области, его называют БПФ с прорежнваннем во временной области (временной децимацией — ВД). Первый алгоритм БПФ-ВД появился благодаря Кули (Соо1еу) н Тычки (Тц((еу) (9), в честь которых его часто н называют. Децимация приводит к значительному снижению числа операций, выполняемых с данными во временной области. Следует заметить, что вынтрыш на вычислениях растет по закону Мг — ()т/'2) )обг /тг. Итак, упростим вначале запись н установим неюторые математические соотношения. Уравнение (3.20) можно переписать как Гяеее 3. Дискретные преобразования Ь'/2-1 хг„И/ ™ «=О четная последовательность 12/2-1 [г епь + ~ хг„+1Игл «=О нечетная последовательность Х1(/с) = (3.47) 12/2-1 ь/2-1 И/2 к+И/ь ~ И/2 ь / О )У «=О «=О Из уравнения (3.4б, б) И/2"" — — И/","2, так что уравнение (3.47) приобретает вид ///2-1 К/2-1 Х(й) = ~ч~ кг„И/"/2+ Иф ~ч~ х2„~1И/"/2, й = О,...,/У вЂ” 1.
(3.48) «=О ««О Уравнение (3.48) можно переписать в виде: Х (/с) = Хп (/с) + И/~ОХ12(/с), /с = О,..., 11/ — 1. (3.49) Сравнивая уравнение (3.49) с уравнением (3.43), видим, что Х11(/с) — действительно ДПФ-образ четной последовательности, тогда как Х12(/с) — образ нечетной последовательности. Следовательно, как утверждалось ранее, ДПФ-образ Х1(/с) можно выразить При использовании вычислительной избыточности, выражаемой уравнениями (3.46), последовательносп данных делится на две равные последовательности, одна из которых состоит из элементов с четными порядковыми номерами, а другая — с нечетными.
Чтобы длина последовательностей была одинаковой, они должны состоять из четного количества элементов. Если исходная последовательность состоит из нечетного числа элементов, то необходимо добавить дополняющий нуль, чтобы их число стало четным. Это позволит записать ДПФ Х1(/с) через два ДПФ, Х11(/с) и Х12(к), которые будут соответственно ДПФ-образами данных с четными и нечетными значениями (табл. 3.1). Следовательно, /У-точечное ДПФ превращается в два ДПФ, каждое из которых содержит )т/2 точек.
Затем этот процесс повторяется до тех пор, пока Х,(к) не распадется на 1"т'/2 ДПФ, каждое из которых состоит из двух точек, представляющих собой исходные данные. Таким образом, на практике происходит переупорядочение исходных данных, и вычисляются /т/2 двухточечных ДПФ, которые получают исходные данные парами. Результаты этих ДПФ удобно обьединять в четверки„всего получается 12'/4 четырехточечиых ДПФ, юторые вычисляются и соответственно объединяются в М/8 восьмиточечных ДПФ, которые также вычисляются, и так далее, до тех пор„пока не получится конечное М-точечное ДПФ Х1 (/с).
На каждом этапе для снижения количества комплексных операций используется общий множитель, представляющий собой И/и в некоторой степени. Правомерносп этой процедуры доказывается следующим образом. Индекс н в уравнении (3.43) пробегает значения от я = О до и = 2У вЂ” 1, что соответствует значениям данных хе, я1, хг, кг,..., х,ч 1. Последовательность с четными номерами — это хО, кг, хм..., хн м а последовательность с нечетными номерами— х1, хг,..., хн 1. Обе последовательности содержат по /У/2 точек. Члены четной последовательности можно обозначить хг„, где и пробегает значения от нуля до /т//2 — 1, тогда как члены нечетной последовательности — хг„+1. Тогда уравнение (3.43) можно переписать как 3.$. Аяюритм быстрою преобразования Фурье с децимацией ао временной области 1$$ Хг,(й) = хо+ Иф/,хд /с = О,...,Ж/4 — 1, т.е.
й = 0,1 (3.50) Следовательно, Хж(0) = хо+ха Хм(1) = хо + И/с/аха = -гсм г -ы =хо+И'гхс =хо+е хс —- хо+е хс — — хо — хм Аналогично Хгг(0) = хо+ хо, Хгг(1) = хг — хо Хгг(0) = х, + х„Хгз(1) = х, — х„ Хы(0) = хо+ хт, Хгс(0) = хз — хт откуда видно, что значения прн /с = 0 отличаются от значений при й = 1 только знаком. Зтот момент особо важен, если рассматривается случай Х„(й) (й = О, 1, 2, 3). Теперь Хп(/с) = Хгг(/с) + Ил~/гХгг(/с), (3.51) так что Хм (0) = Кгг(0) + И ч/гХгг(0) = Хм(0) + Хгг(0) (3.52) Хм (1) — Хгд (1) + 14'й/гХгг (1)— = Хгг(1) + е /гХгг(1) = Хм(1) — гХгг(1) Хм(2) = Хгг(2) + ИЯ/гХгг(2) = Хм(2) + е ~~ '~~ж"~Хгг(2) = = Хгг(2) + е '"Хгг(2) = Хм(2) — Хгг(2).
(3.53) (3.54) через два ДПФ-образа: Хп(й) и Хгг(й). При таком подходе козффицнеит Иг~о появляется и в Хп(й), и в Хсг(/с), и вычислять его нужно только один раз. В табл. 3.1 изображен процесс вычисления восьмиточечиого ДПФ. В первой строке записаны данные, тогда как во второй строке дается выражение для ДПФ-образа зтих данных, записанное через ДПФ-образы четной и нечетной последовательностей Х„(й) и Хгг(й) соответственно. В третьей строке приведены переупорядоченные данные, из которых получают Хп(й) и Хм(й).
В четвертой строке даются ДПФ-образы последовательностей из строки 3, выраженные через ДПФ.образы их четных и нечетных последовательностей Хг,(/с), Хгг(й), Хгз(й) и Хы(й). Эти последовательности показаны в строке 5, н видно, что оии состоят из двухточечных последовательностей, ДПФ-образы которых Хг,(/с), Хгг(й), Хгг(й) и Х„(й) выражаются через данные из строки 6. Итак, единое восьмиточечное ДПФ раскладывается на четыре двухточечных ДПФ, каждое из которых дает два значения, например, для Хг,(й) — зто Хг,(0) и Хгг(1). Описанный пРоцесс включает два РазложениЯ, и коэффициент Иснь на каждом псаге возводится в квадрат. Из строки 6 видно, что сГ" о" ! С'Ъ и а н й а н Р. ы с х о й с с с с с О О и о а а и и а Й и с о с я ы а с с~ а а с о Д н Й н и и Ю Ь й~ ~ Р 4 ы а Д й ы с и и О О О1 с а с И ы а.й ы ы с с $ и с Ю - о" и Д + )( ) + ~с Й в $ж а и д о йа ы Ф й й ы с и о ф йР О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
