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

согласно (1.55) — (1.58) вычксляем: 1) ТЧПФ последовательности х: 1 1 1 1 ' 2 -Х=т,х( 617)= 1 4 16 '3 Х !5 1 !6 1 16 1 13 16 4 0 (тос$17). 28 1 1 -т,= 1 Рв= 3 Р,=б Р,= 17 Рв = 257 Ра = 65 537 1 1 ! 4', 4' 4' 4' 4' 4' 43 46 49 18 78 243 213 1 10 5 9 1 1 13 1 1 1 1 13 16 4 16 1 16 4 16 13 2) ТЧПФ последовательности Ь: 3 3 33 — = !6 ( 'й") 9 9 27 10 1 1 1 1 1 4 16 13 1 16 1 16 1 13 16 4 ! 2 Х О о Н = Той (гной 17)— 3) У= — Х Нт— = [3, 90, 80, 90]т=— [3, 5, 12, 5]т(той 17). 4) ОТЧПФ от Т дает искомую свертку: у=Т-'ОУ— = [2, 2, 14, 2]т (той 17). Так как результаты должны лежать в диапазоне [ — 8, 8], то окончательно у = [2, 2, — 3, 2]т. (Сравните с примером 1.13). Теоретико-числовым преобразованием Мерсенна [1.12] называется пара следующих преобразований: р †! Х (л) вз ~ х (пТ) 2"~ (той Ч), А=О..., р — 1; п=о р — 1 х(п Т) — = р ' ~~~ Х(й)2 "~ (той а),п=О,, р 1, а=о (1.59) (1.60) 1 1 1 1 1 1 2 4 В 16 1 4 16 2 8 (той 31) 1 8 2 16 4 1 16 8 4 2 1ак как Б-'— = 25(той 31), то 1 1 1 1212 Т '=5 х 1 2 а 2 и 2 — 3 2 — а 1 2 — а 2 — з матрица ОТ 1 1 2 а 2 — а 2 — 6 2 — з 2 — а 2 2 — га 2-" ЧПМ 1 1 1 1 1 1 16 8 4 2 = 25 1 8 2 16 4 (той 31) ° 1' 4 16 2 8 1 2 4 8 16 Теперь вычисляем: 1) ТЧПМ последовательности х: Х=Т„х=— [1, 2, 10, 19, 9]т (той 31); 2) ТЧПМ последовательности Ь: Нка Т„'яка [3, 5, 9, 17, 2]т (пюй 31); 3) произведение коэффициентов полученных ТЧПМ: У=— НХт=— [3, 10, 28, '13, 18]т (гной 31); 4) ОТЧПМ последовательности т': у=Т вЂ” '„У= [2, 2, 28, 2, О] т (той 31).

Так как результат должен лежать в диаказоне [ — 15„15], то искомая свертка будет равна у=[2, 2, — 3, 2, 0]т. (Сравните с примером 1.14.) 1.4.7. Испольооваиие модульной арифметики в кольце полииомов Последовательность у(пТ), равная круговой свертке последовательностей х(пТ) н п(пТ), п=О,..., У вЂ” 1, является последовательностью коэффициентов полинома 29 тде и — простое положительное число; д=2Р— 1 — простое число (чясло Мерсеина). В качестве р могут быть ныбраны числа 2, 3, 5, 7, 13, 17, 19, 31, 61.

С точки зрения обеспечиваемого динамического диапазона наиболее широко используются числа 31 н 61. Преобразование Мерсенна не обладает структурой БПФ и для своей реализации требует (р — 1)' операций сдвига и р(р — 1) — сложения. Пример 1.15. С помощью ТЧПМ найдем свертку последовательностей: х= = [2, — 2, 1, О, 0]т; !т= [1, 2, О, О, О]т. Выбеоем р=5, тогда о=2' — 1=31.

Матрица ТЧПМ имеет вид ! 1 1 1 1 1 2 2а 2а 24 Тм = 1 2а 24 2а 2 1 2а 2а 29 21а 1 24 2а 2га 2м 1' (г) =: Х (г) Н (г) (шод (г~ — 1)), (1.61) где л! — ! М вЂ” ! Х (г) = У, х (1Т) »1; Н(г) = ~~', Л(1Т) г! ь=а т=з 1'(г) = 1" у ((Т)»!. 1=о Для вычисления (1.61) воспользуемся китайской теоремой об Остатках. Если представить полипом гх — 1 в виде произведения Л взаимно-простых полиномов с коэффициентами из поля рациональных чисел (использование других полей рассмотрено в [1.121) Ь г — 1= Ц Р! (г), (Р1 (г), ..., Рр,(г)) =1, т=! (1.62) 1' (г) = ~ р, 1'! (г) Я! (») О! (г) -(шоб (» — 1)) ! л! =! (1.63) где У! (г) = Х (г) Н (г) (шод Р! (г)) О! (г) = (г~ — 1)/Р! (г), (1.64)) (1.65) полиномы Я!(г) должны удовлетворять соотношениям Я! (») Б! (») = 1 (шой Р! (»)), 1= 1э ..., Л (1.66) Х (г) =х (О)+х(Т) г, Н (г) =Л (О)+Л (Т) г; У (г) = у (О) + у (Т) г = (х (О) + х (Т) г) (Л (О) + Л (Т) г) (шос$ (»2 — 1)) ° Представим г' — 1=Р2(г)Р2(г), где Р,(г) =г — 1; Р,(г) =»+1. Тогда 1'1 (г) = т1 = (х (О) + х (Т)) (Л (О) + Л (Т)); г'2 (г) = т2 — — (х (О)— — (Т)) (Л (0) — Л (Т)) .

Согласно (1.65) 5ю (») = г —,1; 52 = г — 1. Согласно (!.66) Я1(г) (г-', 1) =— ==! (шод(г — 1)); !»2(г) (г — 1) =1(шоб(г+1)). Отсюда Я1(г) =1/2; Я2(») = — 1~2. Подставляя полученные значения в (1.63), получаем т1 т2 т1 ! !пз т1 т2 У (г)= — (г+1) — — (» — 1)= +г~ ' ~ =у(0)+у(Т)г, 2 2 2 1 2 / нли (0) = (т1 ' т2)~'2 у (Т) = (тт — т,),'2.

В том стучае, когда неооходимо говтсрить вычисление для различных последовательностей х(пТ) при одной и той же последовательности Л(пТ), целесообразно Все Вы:асления, связаннь!е только с Л(пТ), выполнять заранее и для дальнейшего использования хранить в ячейках памяти. Такая предварительная обраоотка данных сугдественно повышает эффективность вычислений. Пример 1.1б. Вывести алгоритм вычисления круговой свертки последовательностей х(пТ) и Л(пТ) длиной Л~=2. Согласно (1.61): Пример 1.1у. Алгоритм 2-точечной круговой свертки с предварительной обработкой данных (см.

пример 1.16) имеет вид: Бд — х (О) + х (Т); 8н =- х (0) — х (Т); Л (О)+Л(Т)~ 1Л(О) — Л (Т)~ т,= у (0)=т,+т,; у(Т) =тг — т,. В (1.12] показано, что минимальное число операций умножения, требуемых для вычисления (1.16), составляет 2У вЂ” К, где К равно числу различных непривадимых в поле 0 множителей полинома 2лс — 1. Для многих (особенно простых) Лб это число достижимо ценой чрезмерного увеличения числа операций сложения.

ПОЭТОМУ ПРЕДПОЧТИТЕЛЬНЫМИ ЯВЛЯЮТСЯ Таи НаамнаЕМЫЕ СУбаПТИМаЛЬНЬ1Е алгоритмы с несколько большим числом операций умножения, но гораздо меньшим числом операций сложения. В 11.12] приведены алгоритмы с предварительной обработкой данных для нескольких значений Лб.

В табл. 1.5 приведено число Таблица 1.5 ! б Число опсрнцна Число операция умножения ~ сложения ! ~ умножения ~ сложения б ~ 4 ! бб ~ 7 ~ бб 46 81 4 5 ~ 15 ~~ 8 ' 14 5 ~' 10, 31,", 9 19 Лбб — 1 Л'б — 1 У (птТ.и,Т)= ~~ 5' х(11 Т, 1б ~) 8((и,— 1,)Т,(пн — 1н)Т), Е, 0 с,-=с где 1, = 1(спад Лл~); 1н = 1 (спос1 Л'н); и, = — и (шос( Л'1); ин = — и (шос( Л1н), и „1= О, ..., Л' — 1.

Пример 1.18. Рассмотрим алгоритм вычисления б-точечной круговой свертка. Положчм Л' =2; Лсн=3. Сопоставйм каждому индексу п=О, ..., 5 пару координат (иь пя), где и,=п(спас(2); пя=п(шаб 3). Тогда получим следующее взаимно-однозначное отображение: О -м (О, О), 1 -э-(1, 1), 2 -~ (О, 2), 3 -я. (1, 0), 4-б- (О, 1), 5 б- (1, 2).

31 требуемых арифметических операций, неоаходимых "ля их реализации. В том случае, когда Л'=ЛссЛбн, где Лбб и Лн — взачмна-простые числа, исходную матрицу свертки, полученную путем соответствующей перестановки строк и столбцов, можно представить в виде циклической н.атрицы размера У,ХЛ'ь злемеитами которой, в свою очередь, являются циклические матрицы разлсера ЛснХЛз, и свести тем самым вычисление Л'-точечной свертки к вычислению Лб; и Л''н-точечных сверток (алгоритм Агарваля — Кули [1.12]). Рассматриваемый метод является, па существу, методом представления одномерной Л'-точечной свертки в виде двумерной (Л'.ХЛн)-точечной свертки: Теперь изменим порядок расположения элементов у(пТ) в векторе У матричного выражения (1.42) таким образом, чтобы сначала размещались элементы, для которых п»=0; п»=0, 1, 2, а затем элементы, для которых и»=1; по = =О, 1, 2, т.

е. у(0), у(4Т), у(2Т), у(ЗТ), у(Т), у(5Т). Тогда искомая свертка записывается в виде (1.67) Матрица последнего выражения представляет собой циклическую матрицу раз- мера 2Х2 (Л1»ХЛ»»), элементами которой являются циклические матрицы размера ЗХЗ (Л»2ХЛ»2), Вычисление (1.67) сводится к вычислению 2- и 3-точечных кру- говых сверток. Пусть: Уо = (у (О), у (4 Т) у (2 Т) )т ° У» (у (3 Т), у (Т), у(5 Т))т Но=(й(0) й (2 Т), Ь (4 Т))~ ~ Н» = ~1(3 Т) й(5Т) 7„(Т))тх(0) х(4Т) х(2Т) х(ЗТ) х(Т) х(5Т) Хо= х(4Т) х(2Т) х(0) ' Х»= х(Т) х(5Т) х(ЗТ) х(2 Т) х(0) х(4Т) х(5 Т) х(3 Т) х(Т) Тогда Используя алгоритм 2-точечной свертки (см. пример 1.17), волучаем: Х +Х М»= — (Но+Н») ' 2 Хо — Х, Мо = — (Но — Н»); 2 уо = М»+ Мо ' ~'1 = М» — М2. Для вычисленгя М и М2 применяется алгоритм 3-точечной свертки.

Пусть»п~ и то — числа требуемых умножений для Л»к и Л-точечных сверток соответственно [(Л"ь Л2) =Ц. Аналогично а~ и ао — числа требуемых операций сложения. Тогда для Л'~ХЛ»2-точечной свертки число требуемых операций умножеяия т н сложения а составит соответственно: (1.68) (1.69) Л» и2 ~ 1п2 п1' Пример 1.19.

Пусть А~=6; Л11=2; Л»2=3. Согласно табл. 1.5 т~ — — 2; то=4; а,=4; а»=11. Пользуясь формулами (1.68) и (1.69), получаем: т=2 4=8; а= =2.11+4.4=38. Теперь положим: Л»,=З; Л»2=2. Тогда: т~=4; п»2=2; а1=11; а»=4. Аналогично чаходим: п»=8; а=З 4+2.11=12+22=34. Расчеты показывают, что второй вариант является более экономичным по числу требуемых операций сложения.