Цифровая обработка сигналов: Справочник - Гольденберг Л.М.
Скачать (прямая ссылка):
hi(nT):
Ni+Nz-2
р(дГ) = 2j. x1(lT)h1((n-l)T), д = 0,..., Nx + Nz-2, (1.52>
/=о
23
и может быть вычислена с использованием (Nt+N2-1)-точечного ДПФ (см.
1.4.2).
4
Пример 1.13. Вычислить линейную свертку двух конечных
последовательностей: х=[2, -2, 1]т; h=[l, 2]т. Здесь Ni=3, W2=2 и,
следовательно, Nt +
-1=4. Сформируем последовательности длиной в четыре отсчета согласно
(1.50) н (1.51):
"хГ^[2, - 2ГГГб]Г; h1==[l, 2, 0, 0]т-
Вычислим круговую свертку последовательностей х, и hi с помощью алгоритма
4-точечного БПФ (см. пример ' ч>-
_=(3,i
4) ОДПФ Y является искомой Сверткой и равно у='[2,2-3,2]т.
1.4.4. Секционированные свертки
В том случае, когда одна из последовательностей гораздо длиннее другой
{Ni"3>N2 или N2~>Ni), используют процедуры, основанные на разбиении
длинной последовательности иа короткие секции и вычислении частичных
сверток, из которых формируется искомая линейная свертка. Существуют два
метода с сек-
, ,Л(лЯ
In
I 1 I I о о-о-о-o-t 0 Nf1 х(пП I? I? т "° ^ -4 -О п •
I aj Хк(пТ1 ! Ц П i я Т ?Тт
^ " ft . I гг
24
ционированием свертки [1.6]: метод перекрытия с суммированием и метод
перекрытия с накоплением.
Метод перекрытия с суммированием. Графическая иллюстрация метода
приведена на рис. 1.14.
Пусть более длинной, а в общем случае неограниченной является
последовательность х(пТ), a h(nT) содержит N2 отсчетов.
Последовательность х(пТ) делится на смежные секции Хь(пТ) по N, отсчетов,
так что
где Хк(пТ)
-с
*(лГ)=2 xh(nT),
ft=0
f х (пТ) при k 1) -1;
, 0 при других значениях л.
Вычисляем k-ю частичную линейную свертку ун(пТ) последовательностей
Хк(пТ) и h(riT), Каждая частичная свертка имеет длину Ni+N3-1 и
перекрывается с (?+1) -частичной сверткой на участке длиной в N3-1
отсчетов. Поэтому на участке перекрытия их отсчеты нужно сложить.
Проделывая указанные действ?:' дте гхс.т получаем искомую свертку:
СО
у (пТ)= Ууь(пТ).
Метод перекрытия с накоплением. Графическая иллюстрация метода приведена
на рис. 1.15. В данном случае перекрываются не выходные, а входные
секции. Пусть h(nT) содержит N3 отсчетов. Длинная последовательность
х(пТ) делится на секции Хк(пТ) по N=Ni+N3-1 отсчетов, так что каждые две
соседние перекрываются на участке длиной в N3-1 отсчетов.
Последовательность h(nT) дополняется нулями до получения длины в N
отсчетов:
h{nT) прн л=0, ... , N3-1 ;
О при n-N3,...,N-1.
Находим k-ю частичную круговую свертку Ук(пТ) последовательностей h,(nT)
и Хк(пТ). Последние (неверные нз-за циклического характера круговой
свертки) N2-1 отсчетов каждой из последовательностей Ун(пТ)
отбрасываются, а остальные присоединяются к верным отсчетам (k-1) -й
секции. Проделывая описанную процедуру для всех к, получаем искомую
свертку.
1.4.5. Методы быстрого вычисления круговой свертки
Существуют три основных метода быстрого вычисления круговой свертки.
Методы различаются требуемым объемом вычислительных операций и памяти, а
также степенью точности, связанной с ошибками округления.
Первый метод, основанный на использовании БПФ н получивший название
метода быстрой свертки, приводит к существенному сокращению требуемого
количества арнфметнческнх операций для последовательностей, длина которых
больше 32. Недостатки метода - значительные ошибки округления, большой
объем памяти, требуемый для хранения комплексных экспоненциальных
коэффициентов, н все еще значительный объем вычислений.
Второй метод, использующий теоретико-числовые преобразования (ТЧП),
является точным, так как служит для преобразования последовательностей в
кольце целых чисел. Существенный недостаток, ограничивающий его
применение в
Л, (лТ) =
25
реальных системах, - зависимость между длиной последовательности N и
требуемой длиной кодового слова, что приводит к длинным кодовым словам
для больших N.
Третий метод - метод модульной арифметики в кольце полиномов,
обеспечивающий высокие эффективность и точность вычислений. Недостаток
этого метода заключается в сложности программирования вычислений, которая
зависит m длины обрабатываемой последовательности.
ШпП
LI ? Т е-о-о-о-
0 NfI N-1
х(пТ1
!? Ь ТИЛ? J.T J?rtl
xA.,(nr; t Ы
xk(nTl -*¦ n ? ¦ n Участок лерек--рытая ' Л!
-0 Pr S 4 А п
yk-i(nTJ
о ?
У, (nTJ 4 у,'"" n
'till Г* ?
yk_tw%w l! i t tii' n
Рис. 1.15
1.4.6. Использование теоретико-числовых преобразований
Так как последовательности в цифровых системах определяются с конечной
точностью, то они могут быть представлены в виде последовательностей
целых чисел, ограниченных сверху некоторым числом.
Теоретико-числовое преобразование определяется для последовательностей
целых чисел х{пТ), п=0,..., N-1 и X{k), k=0, ...,N-I, как пара
преобразований:
[N-l
X (k) = 2 * ("
\n=0
26
T) ank ) (mod M)
(1.53)
имеющих структуру, похожую на структуру ДПФ. Здесь М - целое
положительное число; N - целое положительное число, взаимно-простое с М н
такое, что на него делится число Р-I, где Р - любой из простых
