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

Рассмотрим случай 0=8=2». Так как т=З, то и=О, 1, 2. Для получения входного массива Х,(п) произведем двоична-инверсную перестановки элементов последовательности х(пТ) =х(и), п=О, ..., 7: Хо(0) = Х,(000) =х (000) =х(0); Хо(4)=Хо(100) =х(001) =х(1); Хо(1) = Хо (001) =х(100) =х(4); Хо(5) = Хо (101) = х (101) =х(5); Хо(2)=Х«(010)=х(010)=х(2); Хо(6)=Х»(110)=х(011)=х(3); Хо (3) = Хо (011) = х (1 10) = х (6) ~ Хо (7) = Хо (111) = х (! 11) = х (7) . Направленный граф с использованием «бабочки» и выражения (1.24) изображен на рис.

1.6. Алгоритм с прореживанием по частоте. Исходная последовательность х(иТ1 разбивается на две подпоследовательности хд(пТ)=х(пТ) и хо(пТ)=х((и+ +У12)Т), где п=О, ..., 112 — 1, и отдельно вычисляются четные и нечетные от. счеты ДПФ: Полученные У)2-точечные ДПФ аналогичным образом можно представить через ЛЧ4-точечные и т. д., пока не останутся только двухточечные (~его ч=!ой«М ступеней преобразования).

На т-й ступени (т=О,..., т — 1) пРоизводится преобразование множества У комплексных чисел Х (л) в множество Х(б) Х(1) х(г) Х(3) Х(й Х(б) Х(б) Х(7) Рис. 1.6 комплексных чисел Х +~(п) в соответствии с базовой операцией «бабочкаь, описываемой выражениями: Х +,(р)=Х (р)+Х„()); Х +, (и) = (Х„(р) — Х„())) В"„ (1.27) где р, д и г для каждой ступени оп- ~Ъ г ~'~ ределяются из выражений, аналогичных Х ® (1.26). Направленный граф операции «бабочкаэ изображен на рис. 1.7.

В рассматриваемом алгоритме, в Рис. 1.7 отличие от алгоритма с прореживанием по времени, в двоично-инверсионном порядке располагается не входная, а выходная последовательность Х(А). Рис. 1.8 16 Х(б) =Хс(И х(7) =Ха(() х(гп=,т,(г) х(бт) =Х а) Х(ФТ) =Л,(() Я(б)7 =Ха(б) х(бГ) =Х (б) Х(7)) =Хр(7) х (б) Х,(1) .х (г) ХОЩ Ха(() Хб(б) Хб(б) Х (7) ХФ Х(1) х(г) ХФ Х(й ХЯ Х(б) Х(7) Пример 1.7.

Рассмотрим случай У=8, ч=З. Направленный граф 8-точечногб( ДПФ с использованием операции «бабочка» н выражения (1.26) изображен на, рнс. 1.8. Алгоритмы с прореживанием по времени и по частоте являются дуальными: каждый из ннх может быть получен нз другого путем взаимной замены входа и выхода и обращения направления всех стрелок в направленном графе (см. рис. 1.6 и 1.8). .ФОРТРАН вЂ” программа, реализующая алгоритм БПФ с основанием 2 прн прорежизании по времени, приведена в [1.61. В пакете прикладных программ ЕС ЭВМ имеется подпрограмма РРТСО, которая также реализует алгоритм БПФ.

1.3.5. Алгоритмы БПФ длн произвольного составного У (1.28) й = /)д + й, У„п ~ пд + и, Уд, где пд, А,=О, ..., У,— 1, п„йд — — О,..., А)а — 1. Тогда (1 19) преобразуется к виду /))) — ! У« — ! Х(й,+ИМ,)= Х Х х((яд+и Уд)т)УРК',"' (РФ'"' (Рж;%' л)=0 л«=0 (1.29) Пример 1.8. Пусть У=6; У!=3; У»=2. Согласно (1.28) положим /д=/д)+ +/)д 2; п=пд+п».З; и), /д»=О, 1, 2; и», /д) =)О, 1. Тогда 3 ! х)й)) 2)= т, ~ «()~)3~)т) ) «'"') )« '"'~ «' '"'. л,=о л,=е Соответствующий направленный граф изображен на рис. 1.9. Х(0/=Х(0/ Х И =Х(4/ Х(4/=ХЙ х(0/ =м(0/ кР// =х(П лип =х(т// ))1) )"/ =И)/ Х(1/=Х()/ Х(З=Х(О Х(Я =Х(0/ х(4г/ =Х(47/ к(г/ =))(07/ Рис. 1.9 Алгоритмы БПФ с произвольным основанием.

Используя алгоритм с мно. жителями поворота, можно получить алгоритмы БПФ с основаниями, отличнымн от 2. На практике наибольшее применение нашли алгоритмы с основаниями 4, 8 и 16, позволяющие значительно сократить число требуемых операцяй по сравнению с алгоритмами с основанием 2. В табл. 1.3 приведены выражения для Алгорнтм с множителями поворота. Пусть У=У)Ум где Уд н Уд — любые положительные целые. В этом случае вычисление У-точечного ДПФ можно свести к определению У) Уд-точечных и Уз У)-точечных ДПФ и У умножениям г/ на множители поворота (Р)л. Для этого в (1.19) необходимо сделать следую-1)д/ Ъ щую подстановку; Таблица 1 Алгоритм Действие Число действитель- Число дейетвитель- НЫХ УМНОжЕНИй ~ НЫХ СЛОХ2ЕНИО С основанием 2 (« — 2)М+2 (3« — 2) М+2 (2« — 4) М+4 (2« — 4) М+4 М=2« «>1, целое С основанием 4 (3«/4 — 2) М+ 2 (275« — 2) М+ 2 (3«/2 — 4) М+ 4 (3«/2 — 4) М+ 4 М= (22) «Сз «/2>1, целое 13М«/6 М«/6 С основанием 8 (7«/12 — 2) М+ 2 (2,75« — 2) М+ 2 (7«/6 — 4) М+4 (4«/3 — 4) М+ 4 М (22) Ыз «/3>1, целое 37М«/16 Полное преобразова ние расчета числа требуемых арифметических операций для алгоритмов с основа- ниями 2, 4, 8 и 16.

Предполагается, что для выполнения базовой операции (2, 4, 8 или 16-точечного ДПФ) используется алгоритм, требующий минимального числа умножений и сложений. Прииер 1.У. Построить алгоритм 16-точечного ДПФ с основанием 4. По ложим М=16=МеМз, где М2=4; Ма=4. Согласно (1.28) и (1.29) /з 'п2+пз 4; п=лз+пз 4; пг, пз, /зт, йз=О, ..., 3; 3 3 х(2,.2.2, О=7, т. *02,-2,,2)г) 22! ~) и!2" ~ в,'" л,=О п2=0 (1.30) Построим алгоритм вычисления базового 4-точечного ДПФ 3 Х(й) =",,х(пТ)Ц", й=О,..., 3. п=О (1.3! ) Положим й = йз + /гз 2; п = пз + пз 2; йз, йз, пз, пз = 0,1.

Подставляя (1.32) в (1.31), получаем (1.32) 1 ! х(22+2 22= ~ ~ *О~~+~ 2)г~т2'"') Я ! ~1 е2'"' (222! н 2=0 л,=0 Направленный граф, соответствующий (1.33), изображен на рис. 1.10. Направ ленный граф 16-точечного ДПФ изображен на рнс. 1.11. 18 С основанием 16 М= (2') «г' «/4ъ1, целое Вычисление (М/2) « 2-точечных ДПФ Поворот Полное преобразова- ние Вычисление (М/4) «/22 4-точечных ДПФ Поворот Полное преобразова- ние Вычисление (М/8) «/3 8-точечных ДПФ Поворот Полное преобразова- ние Вычисление (М/16) «/4 16-точечных ДПФ Поворот (15«/16 — 4) М+4 (15«/32 — 2) М+2 (25«/16 — 4) М+ 4 (89«/32 — 2) М+ 2 ~, Алгоритм взаимно-простых делителей. Пусть У=МдУм где Мд н Уз — взаимно-простые, т.

е. (УдМд)*= 1, а однозначное отображение между числами л= =О,...,У вЂ” 1; й=О,...,У вЂ” 1 и парами (пь пз), (хь хз); пь й1 — — О,...,У1=1, пз, из=О,..., Мз — 1 определяется соотношениями: и = пд Мз+ пз. й = йд Уз+ лз. (1.34) х(а) х(а Х(21 х(т Х(1) х(г Х(Л х(зт) Рис. ).)О Пусть последовательность х(лТ) получается из последовательности х()дТ) пере. стаиовкойаа «((пд Уз+ пз) Т) = хИпа Мд+ пд Мз) (шоб М) 7), (1.35) а последовательность Х(х) получается из последовательности ДПФ Х(х) пе- рестановкой (1.36) .121 изз (1.37) (1.38) Рис. 1.1) ' ЗаПИСЬ (Уь УЗ) ОЗНаЧаЕт, «зибольший ОбщИй дЕЛИтЕЛЬ ЧИСЕЛ М, и Мдъ. Запись п(тоби) означает чостаток от деления числа и на число т», например 21(той 5) =1. 19 Х (Йд Мз+ йз) = Х Изд й, У, + з, /гд Мз) (шоб М)) .

Числа з~ и зз определяются согласно китайской теореме об остатках уравнений: зд Уд. :1 (шоб Мз), зд ( Уд; зз У2 = 1 (пдоб Мд) в зз ( Мд ° х(а) х(т) х(2Т) х(ат) хС4Т) х(от) х!бт) х(тт) хит) тат) х()ат) х())т) х()гт) х(1зт) Х(14Т) х(1бт) м(а) Х(!) ил Х(а) Х(Ц Х(б) Х(б) Х(7) Х(а) Ч~П1 ия х()а) Х(аа х(12) хауз) Х(14) Х()б) Тогда справедливо выражение Л'» — 1 /М,— 1 л (лтЛа+ла) = ~, ~ ~~ х ((лтЛ»а+па) Т) Я7»)» "» (»',~ л,=0 ~, л,=О (1.39) и= Йт 2+па, ')а=от 2+)аа~ лт — — О,1,2; йа» ла — — 0,1. Из з,.3=1(пзоб 2); э~<2; за 2=— 1(гпоо3); за<3 найдем: з,=1; за=2. Получим элементы вектора х(пТ) из х(лТ) перестановкой (1.35) Х(5) Х(Т) Х(2Т) хЯТ) ХМТ) хГ5Т' х(5) 'х(т) х(гт) х(5П х (ОТ) х(5Т) и элементы выходного вектора Х()а) нз Х(л) перестановкой (1.36) Х(1) Х(2) Х(5) Х(Й Х(5) Х()) Х(2) Х(3) Х(Й Х(5) Согласно (1.39) 2 ' 1 х(» 2'»~=~ (у„[~,,»~ ~»»,, щ», л,— О,л,=о Соответствующий направленный граф изображен на рнс.

1.12. и (О) х(зт) х(е) Х(2) х(и х(г~ х (ОТ) Х(1) х(з) х(зу Х(2Т) х(5Т) Рис. 1,12 20 Алгоритм взаимно простых делителей позволяет избавиться от множителей поворота и свести вычисление У=У~Ха-точечного ДПФ к вычислению Л'~- и Ла-точечных ДПФ и является по существу методом отображения одномерного ДПФ на многомерное (см. 1.3.3). Пример 1.10. Рассмотрим случай Л~=б. Пусть У~=3; Л(а=2. Сеглаано (1.34) положим: 1.4. ДИСКРЕТНАЯ СВЕРТКА И ЕЕ ВЫЧИСЛЕНИЕ 1.4.1. Круговая свертка Пусть х(пТ) и Ь(иТ) — две периодические последовательности с периодами по Х отсчетов.

Круговой (периодической или циклической) свергкой таких последовательностей называется последовательность у(пТ), определяемая соотношением у (пТ) = ~ Ь (1Т) х ((л — 1) Т) . (1.40): Запись (1,40) эквивалентна записи ч — 1 у (лТ) = '~~ х (! Т) Ь ((и — 1) Т) . 1 О (1.41) Последовательность у(пТ) также является периодической с периодом в У отсчетов, поэтому достаточно вычислять ее на одном периоде, например при л= =О,...,У вЂ” 1. Соотношения (1,40) и (1.41) справедливы и для конечных последовательностей х(пТ), Ь(пТ) (л=О,....,л' — 1), если рассматривать их как один период, соответствующих им периодических последовательностей. Круговая свертка конечных последовательностей будет также конечной.

В матричной форме круговая свертка имеет вид у=Нх или у=ХЬ, где у, й, х — Л'-мерные векторы; у=[у(0), у(Т)... у((Х вЂ” ЦТ))~; й=[й(0), Ь((й! — 1) Т),..., Ь(Т))~ х = [х (0), х ((У вЂ” 1) Т),..., х (Т) ) ~, а Н и Х вЂ” циклические матрицы размера ЯХЬЕ: Ь (0) Ь (Т)... Ь ((У вЂ” 1) Т) Ь (Т) Ь (2Т)... й (0) Ь (2Т) Ь (ЗТ)...Ь (Т) (1.43г Ь ((У вЂ” 1) Т)... Ь ((У вЂ” 2)Т) х (О) х (Т)... х ((У вЂ” 1) Т) х (Т) х (2Т)... х (0) х (2Т) х (ЗТ)...

х (Т) (1.44г х ((Ж вЂ” !) Т)... х ((У вЂ” 2) Т) ПРимер й11. Вычислить круговую свертку последовательностей х(пТ) длины )У и Ь(пТ) =Ь((п — по)Т), иа>О. Представим ЦпТ) в виде последовательности длины У: 21 Вычисление 1-мерного ДПФ (см. 1.3.3) сводится к вычислению Юь Ьг2...; °...л1~-точечных ДПФ, для реализации которых могут быть использованы алго-. ритмы БПФ. О при О~п(пр; 1 при п=лр', О при пр(лк М вЂ” 1. Ь(п Т) = На рис.