Цифровая обработка сигналов: Справочник - Гольденберг Л.М.
Скачать (прямая ссылка):
3) произведение коэффициентов полученных ТЧПМ: Y=HXT=[3, 10, 28, 13, 18]т
(mod 31);
4) ОТЧПМ последовательности Y: y=T-'MY=[2, 2, 28, 2, 0]T(mod31). Так как
результат должен Лежать в диапазоне [-15, 15], то искомая
свертка будет равна у=[2, 2, -3, 2, 0]т. (Сравните с примером 1.14.)
1.4.7. Испольвованве модульной арифметики s кольце полипомов
Последовательность у(пТ), равная круговой свертке последовательностей
х(пТ) и h[nT), n=0,...,N-1, является последовательностью коэффициентов
,полинома
29
Y(z) = X (г) Я (z) (mod (г"- 1)), (1.61)
где
N- 1 N-l N-l
X (г) = У. x (I T) г1; H (z) = У ft(/T) 2f ; К (г) =2 у {IT) г1.
S) i=o /=о
Для вычисления (1.61) воспользуемся китайской теоремой об остатках. Если
представить полином zN-1 в виде произведения k взаимно-простых полиномов
с коэффициентами из поля рациональных чисел (использование других полей
рассмотрено в [1.12])
N А
2 -1 - П Pz (г), (Рх (г) Pft (г)) = 1, (1.62)
/=1
ТО
У (г) = (г) <2г (г) S, (z)^(mod (гЛ' -1)) , (1.63)
где
Yl (г) = X (г) Я (г) (mod Pi (2)) ; (1.64)
Si (2) = (2W - 1)/Рг(г), (1.65)
полиномы Qi (2) должны удовлетворять соотношениям
Qi (г) Si (2) = 1 (mod Pi (2)), 1=1, , k. (1.66)
Пример 1.16. Вывести алгоритм вычисления круговой свертки
последовательностей х{пТ) и h(riT) длиной N=2.
Согласно (1.61):
X (г) = х (0) + х(Т) z, Я (г) = А (0) + А (Т) г;
К (2) = г/ (0) -f j/ (Т) г = (х (0) + х (Г) г) (А (0) + A (Т) г) (mod
(г*- 1))-
Представим z2-l=Pi(z)Рг(г), где Pi(z)=z-1; P2(z)=z+1. Тогда
(г) = щ = (х (0) + х (Г)) (ft (0) + ft (Г)); К2 (г) = т2={х (0) -
- х(Т)) (ft (0)-А (Г)).
Согласно (1.65) Si(z) = z-fl; S2 = z-1. Согласно (1.66) Qi(z) (z-bl)ss
==l(mod(z- 1)); Q2(z) (z-l)==l(mod(z-bl)). Отсюда Q,(z)=l/2; Q2(z) =-1/2.
Подставляя полученные значения в (1.63), получаем
Г а "+.)_!*. (г_,)=Ъ±Д1+г(Д!=^) = в(0,+В<7>. или
у (0) = (mx -f m2)/2 ; у (T)=(m1-mz)j2.
В том случае, когда необходимо повторить вычисление для различных по*
следовательностей х{пТ) при одной и той же последовательности h{tiT),
целесообразно все вычисления, связанные только с h{nT), выполнять заранее
и для дальнейшего использования хранить в ячейках памяти. Такая
предварительная обработка данных существенно повышает эффективность
вычислений.
30
Пример 1.17. Алгоритм 2-точечной круговой свертки с предварительной
обработкой данных (см. пример 1.16) имеет вид:
Si = * (0) + х (Т) ; S2 = x(0) -* (Г);
(h(0) + h(T)\ I h (0)-h (Т)\ "
m-i - ^ ^ j $i • m2 - ^ 2 j S2 ,
у (0) = m1 + т2; у(Т) = тп1-т2.
В [1.12] показано, что минимальное число операций умножения, требуемых
для вычисления (1.16), составляет 2АГ-К, где К равно числу различных
неприводимых в поле С множителей полинома 2N-1. Для многих (особенно
простых) N это число достижимо ценой чрезмерного увеличения числа
операций сложения. Поэтому предпочтительными являются так называемые
субоптимальные алгоритмы с несколько большим числом операций умножения,
но гораздо меньшим числом операций сложения. В [1.12] приведены
алгоритмы с предварительной
обработкой данных для нескольких значений N. В табл. 1.5 приведено
число
Таблица 1.5
N Число операций Л' Число операций
} множения сложения умножения сложения
2 2 4 6 8 34
3 4 11 7 16 70
4 5 15 8 14 46
5 10 31 9 19 81
требуемых арифметических операций, необходимых для их реализации. В том
случае, когда АГ=АГ:АГ2, где Nt и Лг2 - взаимно-простые числа, исходную
матрицу свертки, полученную путем соответствующей перестановки строк и
столбцов, можно представить в виде циклической матрицы размера Л^хЛ'ь
элементами которой, в свою очередь, являются циклические матрицы размера
Лг2хЛг2, и свести тем самым вычисление Л-точечной свертки к вычислению Ад
и Л2-точеч-ных сверток (алгоритм Агарваля - Кули [1.12]).
Рассматриваемый метод является, по существу, методом представления
одномерной Аг-точечной свертки в виде двумерной (Ад ХЛ'2) -точечной
свертки:
Л\-1 N 2-1
у(П1Т,п2Т)= j] У. х(/аТ, l2T)h({ni- tj)T, (n2- l2)T), i[=о K=o
где
= I (mod Ад) ; l2 = I (mod Лг2) ; пг = n (mod Ад); nz = n (mod Лг2), n, 1
= 0 N- 1.
Пример 1.18. Рассмотрим алгоритм вычисления 6-точечной круговой свертки.
Положим A'i=2; Лд=3. Сопоставим каждому индексу "=0, ..., 5 пару
координат (rti, n-г), где ni = n(mod 2); n2 = n(mod 3). Тогда получим
следующее взаимно-однозначное отображение:
0->(0, 0), 1-*(1, 1), 2->-(0, 2),
3->(1, 0), 4-> (0, 1), 5^(1, 2).
31
Теперь изменим порядок расположения элементов у(пТ) в векторе Y
матричного выражения (1.42) таким образом, чтобы сначала размещались
элементы, для которых "1=0; и2=0, 1, 2, а затем элементы, для которых
"1=1; "2= = 0, 1, 2, т. е. 1/(0), г/(47'), г/(27), {/(37), у(Т), {/(57).
Тогда искомая свертка записывается в виде
ft(0) h (2 7)
/1(4 7)
/1(3 7)
/i(5 7)
(Л _ (1.67)
Матрица последнего выражения представляет собой циклическую матрицу
размера 2x2 (NtxNi), элементами которой являются циклические матрицы
размера 3X3 (N2XN2). Вычисление (1.67) сводится к вычислению 2- и 3-
