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

32 у (0) у(4 Т) у(2Т) у (3 Т) у (Т) у(5Т) х(0) х(4Т) х(2Т);х(ЗТ) х(Т) х(5 Т) х(4 Т) х(2Т) х(0) ,'х(Т) х(5 Т) х(ЗТ) х(2Т) х(0) х(4Т) ',х(5 Т) х(ЗТ) х(Т) х(3 Т) х(Т) х(5 Т) 'х (0) х(4Т) х(2 Т) х(Т) х (5 Т) х(3 Т) 'х(4 Т) х(2Т) х(0) х(5 Т) х (3 Т) х(Т) 'х(2 Т) х(0) х(4 Т) Л (О) Ь (2 Т) Ь (4 Т) й(ЗТ) * й(5 Т) й (Т) 1.5. НЕКОТОРЫЕ ПЕРСПЕКТИВНЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДПФ 1 5.1. Алгоритм Винограда Алгоритм Винограда 11.12) основан на представлении матрицы У=Уз Х ХУаХ ... ХУ -точечного ДПФ, где все У~ — взаимно-простые числа, в виде прямого произведения матриц %-точечных ДПФ 1(' 7 7 ~,з )1г2 % ~ 7 уб ~ г,' уз )р2 )3гб 1р 4 т 7 7 7 )р 2 й б )р4 1(~5 11г6 )р 4 уз у! (Р Ю'~ ~1)г,' )Рз )р! 7 13,з 7 )Р~ 7 )т', Тогда искомое ДПФ примет вид: б Х (0) = ~ х (и Т); э=О Х (1) — х (0) Х (3) — х (0) Х (2) — х (0) Х (6) — х (0) Х (4) — х (0) Х (5) — х (0) / х(Т) х (3 Т) х (2 Т) х (6Т) х (4 Т) х (5 Т) (1.72) 2 — 89 33 ~Ъ = 1'Рч, ®'~и, ® " ® 11~ ч и сведении вычисления Л'~-точечных ДПФ к вычислению круговых сверток с использованием модульной арифметики в кольце полицомов (см.

1.4.7). Алгоритм Винограда, имеющий «гнездовую» структуру, существенно эффективнее классических алгоритмов БПФ: при приблизительно равном числе операций сложения он требует на 80% меньше операций умножения. Вычисление ДПФ коротких последовательностей. При У=р, ро, 2о, где р— простое, нечетное число, а)1, ДПФ можно свести к вычислению круговых сверток: 1. Пусть У=р. Тогда матрица ДПФ Жр~ь „~з путем соответствующей перестановки строк и столбцов может быть преобразована в циклическую матрицу Жэ, размера (р — 1) Х (р — 1).

Взаимно-однозначное соответствие между показателями степени элементов Р'чэ матрицы %р ~ и индексами элементов циклической матрицы (1.43) задается так: д:= а" (тоб р), п =-- О, ..., р — 2, (1.711 г-е а — первообразный корень числа р [1.12!. Пример 1.20. Пусть У=р=7. Первообразным корнем числа 7 является а =3. Тогда соответствие (1.~!) запишется так: 'п 0 1 2 3 4 5 д132645 а матрица %;,э, =0 преобразуется к виду Выражение (1.72) представляет собой 6-точечную круговую свертку последовательностей [Р"т, Фзт, 1(727, Ятет, ИГ'7, 1Г'7) и [х(Т), х(ЗТ), х(4Т), х(6Т), «(2Т), х(5ТЦ, для вычисления которой с помощью полиномиальных преобравований требуется восемь операций умножения и 34 — сложения (см.табл.1.5). Для вычисления всего ДПФ и этому числу операций добавляются одна операция умножения иа 12О и две операции сложения (см. табл. 1.6).

2. Пусть У=ра, а~1 — целое. В этом случае вычисление ДПФ сводится к вычислению двух ро-'-точечных ДПФ и одной (р — 1)ро-'-точечной круговой свертки. Это эквивалентно одной (р — 1)ра — ', двум (р — 1)ра — 2, четырем (р— — 1) ро-з,..., 2о — '(р — 1)-точечным сверткам, Взаимно-однозначное соответствие между показателями степени элементов Р,~ циклических матриц %<„п„а — а, Р й=1... а, и индексами элементов матрицы (1.43) задается равенством да/р: — а,~ (той р + ), в=О, „, (р — 1) р~ — 1, шде аь — первообразный корень числа ра+' — ~, Лримар 1.21.

Пусть У=32. В этом случае первообразные корнч а~=аз= =2. Соответствие (1.73) для я=1,2 занишется так: и, О 1 2 а 4 Б й О 1 д ! 2 4 8 7 5 д 3 б 'Тогда 2 3=6-точечная круговая свертка будет иметь вид Х(1) Х(2) Х(4) Х(8) 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 з 7 з ! 2 9 9 9 9 9 х (Т) х(2 Т) х(4 Т) х (8 Т) 9 9 ~9 9 9 9 11 9 9 ~9 9 9 9 Х(7) Х(5) ! х(7Т) х (5 Т) Последовательности Х(ЗА), А=О, 1, 2 и Х(л), А=О, ..., 8, вычисляются с помощью 3-точечных ДПФ: Х (0) Х (3) Х (6) 1 1 9 9 ~9 1" 9, х (0) + х (3 Т) + х (6 Т) х (Т) + х (4 Т) + х (7 Т) х (2 Т) + х (5 Т)+ х (ЗТ) Х (0) Х (1) Х(2) Х (6) Х (7) Х (8) 1 1 х (0) 07з 1Р9 ~'9 (~а х (3 Т) 9 9 х(6Т) 6 3 Х (3) Х (4) Х (5) Последовательности Х(А) и Х(А) такие, что 34 Х (1) Х (2) Х (4) Х (8) Х (7) Х (5) Таким образом, вычисление 9-точечного ДПФ свелось к вычислению 6-точечной круговой свертки и двух 3-точечных ДПФ, которые, в свою очередь, можно определить с помощью 2-точечной круговой свертки.

3. Пусть У=2а, а)2 — целое. В этом случае вычисление ДПФ сводится к вычислению двух 2а — '-точечных ДПФ и двумерной 2Х2а-'-точечной круговой свертки, матрица которой имеет вид %' 2а — 2 %" 2а — 2 У" %' 2а-2 2а-1 где %',а 2 и %" а-гпредставляют собой циклические матрицы размера 2а-д)4 Х2а-'. Взаимно-однозначное соответствие между показателями степени !7! и !72 элементов матриц %' а — 2 н %" а 2 н индексами элементов матрицы (1.43) име- ет внд [1.121: !7 = 5" (и!ос$2а); !72 = — 5" ( и!од 2"), п = О...,, 2а 2 — 1.

(1.74) Пример 7.22. Пусть У 2'. Соответствия (1.74) запишутся так: ! дд !7д 1 5 ' дд — 1 — 5 Тогда: ~н "в~ 2= в' — ' 8 — ! 2 йг — в в 1Г в ~8 ~8 8 8 к (Т) Х (1) Х (5) Х (7) к(5 Т) У вЂ” 1 1Р— в в в (7 Т) у — в у — 1 в в Х (3) к (3 Т) Последовательности Х(2а), а=о, .„, 3, ью 4- еч ДПФ: 2' 35 х(1) Х (2) Х (4) Х (8) х (7) Х (5) х (1) Х (2) х (4) х (8) х (7) Х (5) (р 1 йг — в в в йг — в йг — 1 в в 8 8 '1 В ив ~В в 1 и Х(в), А=О, ..., 7, вычисляются с помо-,: -Х(0)— 1 1 1 1 х(0) +х(4Т) х(Т) +х(5Т) х (2 Т) + х (6 Т) 1 !Г~~ 1 ИУ~ 8 8 у6 у6 8 )Р4 8 йу2 8 Х (2) Х (4) Х (6) 1 1 1 1 х (0) х (Т) х(2 Т) 1 х(ЗТ) 1 1 — 1 1 — 1 1 — 1 1 — 1 — 1 Х (4) Х (5) Х (6) 1 1 1 1 х (0) 1 1 — 1 х (2 Т) х (4 Т) 1 — 1 1 — 1 Х (3) ~ 1 — 1 — 1 1 < х(6Т) Х (7) Х (!) Х (5) Х (7) Х (1) Х (1) Х (5) Х (5) Х (7) Х (7) Х (3) Х (3) Х (3) Вычисление ДПФ рассматриваемым методом не требует умножения иа комплексные коэффициенты, т.

е. коэффициенты являются либо чисто действительными„либо чисто мнимыми. Вычисление ДПФ комплексных последовательностей требует вдвое больше операций умножения и сложения. В !1.12] приведены алгоритмы вычисления ДПФ коротких последовательностей для А!=2, 3, 4, 5, 7, 8, 9, 16. В табл. 1.6 приводится число требуемых ири этом арифметических операций. Вычисление ДПФ длинных последовательностей. Пусть У=У~ Уа и )Ч~ и Жя — взаимно-простые числа.

Если сделать перестановку входной и выходной последовательностей, как н в алгоритме взаимно-простых делителей (см. 1.3.5), то Таблица 1.6 Число операций Число операций умноже- умножения ! умноже- умножения ния иа 148 ! сложения ния на 'Ит' ~ сложения 2 ~ 7 6 '~ 8 8,~ я 17 , 16 0; 2 8 2 ~ ~1 2 о 10 5 1 10 36 26 45 74 1 6 Г= Х (0) Х (1) Х (2) Последовательности л (л) и Х(й) такие, что х (3 Т)+х(7 Т) +х (4 Т) +х(5 Т) + х (6 Т) +х(7 Т) матрицу исходного ДПФ можно представить в виде прямого произведения матриц У,- и Ж2-точечных ДПФ: %=;-%ч З%!ч . Пример 1.23.

Пусть У=15; №=3; 512=5. Из уравнений (1.37) и (1.38) 5, 3=1 (птод 5); 82 5— = 1 (птод3), т. е. 3~=52=2. Переставим элементы х(аТ) согласно (1.35): х ((а1 5 + а,) Т) = х ((а, 3 + а1 5) (птос1 5) Т), а1 = О, 1, 2; а, = О, ..., 4 . Введем векторы: па = [х. ((О ! 5 й) Т), х ((1+ 5 й) Т), х ((2 + 5 й) Т), х ((3+ 5 й) Т), х ((4 + 5 й) Т) ]; 21а = [Х (О+ 5 й), Х (1 + 5 й), Х (2 + 5 й), Х (3 + 5 й), Х (4 -!- 5 й) ], й = 0,1,2. Тогда искомое ДПФ преобразуется к виду 112 3 5 3 5 3 5 Па Ц = )~з %5 )рз %5 и'з %5 п1 (175) 2)2 3 5 3 5 3 5 п2 где Я22=е-12аl', % — матрица 5-точечного ДПФ. Матрица выражения 11.75) и есть прямое произведение %2З%2. Для вычисления векторов 62, 1)1 и 02 воспользуемся алгоритмом вычисления 3-точечного ДПФ [1.12]: 81 п1 + п2 82 п1 п2 ! 82 81 + пО 2а '! - 222 тз — — %5 82 , 'й11 — — ! соз — — 1 ! %2 81 , 'п12 — — 1 5|п %2 Я2 ,' 3 ~ 3 52 — — п12+ 1п1 , '85 = 82 + п12 , '52 = 81 — 2п2 1!О тз ! ~1 52 ! 1!2 82' Для вычисления векторов гпе, т, и 1п2 необходимо использовать алгоритм 5-точечного ДПФ.

Элементы полученного массива следует переставить согласно (1.36) для получения искомого массива: Х ((6й,+10й,) (п1об 15))=Х (й, 5+й,), й,= О, 1,2; й,= 0,,4. Таким образом, У1-точечное ДПФ требует а~ операций сложения и т~ операций умножения, включая й1 умножений на !Р; №-точечное ДПФ требует а1 операций сложения и т2 операций умножения, включая й, умножений на %'~. Тогда число требуемых операций сложения А и умножения М для У-точечного ДПФ составит: т1т2 й1й2! А = )У1 а, г- т2 а1.

(1.76) (1.77) Пример 1.24. Пусть Л'=15; № — — 3; №=5. Согласно табл. 1.6 т1 — — 3; й,=1; а1=6; т2=6; а2=17. Пользуясь формулами (1.76) и (1.77), находим: М=17; А 87. Теперь пусть №-— 5; !Уз=3. Тогда число операций умножения не изменится. а число операций сложения станет равным А=81. 37 1.5.2. Алгоритм Винограда с использованием ТтШ Таблица 1.7 Число операций для действительной входной последователь- ности Число операций для, действительной вход- ~" ной последователь- 1 ности умноже- ~ сложения, ння умвоже- ~ сложения иия 488 61 976 620 ~41 044 1220 ~ 1о3 964 2 3 5.61 ~ 4880 607560 2з 3 5 31 6200 ~412920 2а 5 61 8540 ~1073600 1831 1861 2441 367 2 3 61 373.

2а 3 31 733 2в 3 61 1.5.3. Использование эффективных методов поворота вектора (1ьОРДИИ) КОРДИК" — это совокупность эффективных методов поворота вектора (х, у)=х+1у на угол 0 с помощью только операций сложения и сдвига [1.161, КОРДИК может служить эффективным средством реализации поворачивающих множителей в алгоритмах БПФ. Общее выражение, описывающее КОРДИК, имеет вид: хд —— ах ~ ру;' (1.78) уд — ау ~рх, где хи у1 — координаты вектора„повернутого на угол 8=-,"агс18[фа].

Модуль вектора (хь у1) равен модулю вектора (х, у), умноженному. на коэффициент а = уат+ м Различают две основные разновидности КОРДИКа: полный и оптимальный. Полный КОРДИК представляет собой итерационный гароцесс. В этом случае а=1; р=2 ', где '1 — номер итерации. Процесс поворота вектора (х, у) на угол 8 с точностью до и-го разряда требует л итераций и происходит следующим образом: вначале осуществляется присвоение начальных значений 1=0; 01= — 0; 6~=1, а затем и раз выполняется последовательность операций: и,= з)нп (а,); х~-сд — — х1+ ад ус 2 у~4д= у1 — а~ х~ 2 6~ ) д = 01 — а1 ау + с(д (2 — '); бляд — 6~ (1+ 2 — ад)1/й — 1= 1+ 1. (1.79) * СОЮ1С вЂ” СОогс(1па1е Ко1а11оп 01я11а! Сопдрп(ег. 38 Теоретико-числовые преобразования (см. 1.4.7) могут быть использованы для эффективного вычисления круговой свертки в алгоритме Винограда.

В [1.14, 1.151 предлагается так называемый гибридный алгоритм с использованием ТЧП Мерсенна (см. 1.4.6). В табл. 1.7 приведено число требуемых арифметических операций для И=у'=1+и 2 р, где д' — простое; р=31,61; а=3,5; п=1,2,3. В этом случае ДПФ сводится к вычислению (д' — 1)-точечной круговой свертки, которую, в свою очередь, можно представить в виде прямого произведения а 2" и р-точечных сверток (см. 1,4.7). Для вычисления р-точечной свертки используется ТЧП Мерсенна, требующее р операций умножения н 2р(р — 1) сложения. Пример 1Ж Вычислим 8-точечное ДПФ: 7 Х (й) = ~1 х (и Т) Рз п=в А=О, ...,7.

(1.80) Преобразуем выражение (1.80) согласно алгоритму с множителями поворота (см. 1.3.5), для чего сделаем подстановку: А=йт+Аа 2; и=иг+и, 4; ит,Фа=0, ...,3; А1, и,=0,1. Тогда з Х (/гт+йз 2) = '~~ ~~~~ х ((ит+и 4) 7) 97~1п 1(уа, и, Яга, п1 (1 81) и=в и=в Таким образом, вычисление свелось к 2- и 4-точечным ДПФ, не требующим опе- раций умножения, и умножению на множители поворота 978ь "1. Для реализации множителей поворота используем оптимальный КОРДИК. Пояснения приведены в табл. 1.8 для поворота на О= (2и/8)1-1-л/8.