Гольденберг Л.М. и др. - Цифровая обработка сигналов (Справочник) (1044122), страница 5
Текст из файла (страница 5)
1.13 приведена графическая иллюстрация вычисления круговой свертки по формуле (1.40) для У=4 и лр— - 1. Здесь исходные конечные последовательности периодически продолжены с периодом Л' отсчетов (пунктиром), чтобы показать, как получается круговой сдвиг. Звездочками обозначены выборки, составляющие у(пТ). Результирующая последовательность у(пТ) представляет собой последовательность х(пТ), сдвинутую на пр отсчетов вправо. Х(1 б 7~(г т) р 1 + ~о! ! ! 7 Рис.
1.И Дискретная свертка является одним из способов вычисления выходного сигнала цифрового фильтра по заданному входному сигналу и известной импульсной характеристике фильтра (см. 2.3.3). 1.4.2. Использование ДПФ для вычисления круговой свертки Круговая свертка двух последовательностей х(лТ) и й(пТ) может быть вычислена в результате выполнения следующих действий: 22 1. Вычисления ДПФ последовательности х(лТ): д — 1 Х (й) = Я х (п Т) Яф, А = О,..., М вЂ” 1. л=о 2. Вычисления ДПФ последовательности л(пТ): (1.45) Ф вЂ” 1 Н(А) = Т й(лт) Я7У, й=о,.
° ., Н вЂ” 1 3. Перемножения коэффициентов полученных ДПФ: У (л) = Х (л) Н (в), й = О,, М вЂ” 1. 4. Вычисления ОДПФ последовательности У(в): (1.46) (1.47) Ф вЂ” 1 у (пТ) = — ~~~~ У (Й) Я7,~"", и = О,..., Н вЂ” 1. Н в=о Последовательность у(лТ) есть искомая свертка. (1.48) 1.4.3. Линейная свертка Линейной (апериодической) свертхой двух конечных последовательностей х(пТ) и л(пТ) по Ж~ н Уз отсчетов соответственно называется последовательность у(пТ), определяемая соотношением у(пТ)= ~Ь(1Т)х((и — 1) Т), и=О,..., Уз+На — 2, (1,49) ю о л у (п Т) = ~ х (1Т) й ((и — 1) Т), п = О,..., Нт+ У, — 2.
1=о Последовательность у(пТ) является также конечной и имеет длину Л',+Уз — 1 отсчетов. Сформируем последовательности х~(пТ) и й,(пТ) длиной по У,+Уз — 1 отсчетов: х(пТ) при п=О,..., Мт — 1; хт (п Т) = 0 при и=от,..., Ут+Уа — 2; й(лТ) при п=О,..., Уа — 1; Ь| (иТ) = 0 при п = Л'з,..., Ут+ Н,— 2. Тогда линейная свертка последовательностей х(лТ) и й(пТ) будет +Ма — 1)-точечной круговой свертке последовательностей х~(лТ) и у+У, о у(пТ) = ~~, х,(1Т) Ьт((п — 1) Т), п=О,..., У,+Ма — 2, ю=о 23 (1.50) (1.51г равна (У~+ Ь1(лт): 17рилер 1.12.
Решить пример 1.11 с использованием ДПФ. Пусть ДПФ последовательности х(лТ) равно Х(й). Из (1.19) ДПФ по следовательности и(пТ) равно Н(п)=1(7~~, в=О, ..., У вЂ” 1. Перемножим Х(л) и Н(й); У(й) =Х(л) Яф~, й=О, ..., М вЂ” 1. Согласно свойству сдвига (см.
1.3.2) ОДПФ последовательности У(А) равно хИл — ло)Т). (Сравните с резуль. татом примера 1.11.) и может быть вычислена с использованием (М,+Уз — 1)-точечного ДПФ (см. !.4.2). Пример 1.18. Вычислить линейную свертку двух конечных последовательностей: х=[2, — 2, 1]т; 6=[1, 2], Здесь Ф,=З, Фз=2 и, следовательно, У~+ +Л(~1=4. Сформируем последовательности длиной в четыре отсчета согласно (1.50) н (1.51): хт = [2, — 2, 1, 0]т. йт [1, 2, О, 0]т Вычислим круговую свертку последовательностей х~ и Ь| с помощью алгоритма 4-точечиого БПФ (см.
пример 1 о) 1) ДПФ х~ равно Х~=П,1+Ж, 51 — 21]т' 2) ДПФ Ь! равно Н~=13,1 —.2(, — 1 1+21]~' 3) ДПФ у равно У Х,.нт, '[3,5, — 5,5]т; 4) ОДПФ 7 является искомой сверткой й равно у='[2,2 — 3,2]т. 1.4.4. Секцненнрованные свертки В том случае, когда одна из последовательностей гораздо длиннее другой (У~~Уз или й(з>>У,), используют процедуры, основанные иа разбиении длинной последовательности на короткие секции и вычислении частичных сверток, из которых формируется искомая линейная свертка. Существуют два метода с сек- Рис.
!.14 24 ционированием свертки 11.61: метод перекрытия с суммированием и метод перекрытия с накоплением. Метод перекрытия с суммированием. Графическая иллюстрация метода приведена на рис. 1.14. Пусть более длинной, а в общем случае неограниченной является последовательность х(пТ), а й(пТ) содержит Фз отсчетов. Последовательность х(пТ) делится на смежные секции хь(пТ) по Ф~ отсчетов, так что х(пТ) =,Й хь (пТ), а=о х (и Т) при й У, ( и ч~ (й+ 1) Уд — 1; где хь(пТ) = О при других значениях и.
Вычисляем А-ю частичную линейную свертку уь(пТ) последовательностей хь(пТ) и й(пТ). Каждая частичная свертка имеет длину У~+Уз — 1 и перекрывается с (й+1)-частичной сверткой на участке длиной в Уэ — 1 отсчетов. Поэтому иа учащие перекрытия их отсчеты нужно сложить. Проделывая укаэанные действн= „лц ===.-..'., получаем искомую свертку: у (л Т) = ~' уь (и Т). Метод перекрытия с накоплением. Графическая иллюстрация метода приведена на рис. 1.15. В данном случае перекрываются не выходные, а входные секции. Пусть п(пТ) содержит Уэ отсчетов. Длинная последовательность х(пТ) делится на секции хь(пТ) по Ф=У~+Уэ — 1 отсчетов, так что каждые две соседние перекрываются на участке длиной в У~1 отсчетов.
Последовательность й(пТ) дополняется нулями до получения длины в Ж отсчетов: Ь(пТ) при и= О, ..., Уэ — 1; йт(п Т) = О при и= Фэ, ..., ~Ч вЂ” 1. Находим й-ю частичную круговую свертку уд(пТ) последовательностей Ь~(пТ~ н хь(пТ). Последние (неверные из-за циклического характера круговой свертки) Уэ — 1 отсчетов каждой из последовательностей уд(пТ) отбрасываются, а остальные присоединяются к верным отсчетам (й — 1)-й секции.
Проделывая описанную процедуру для всех й, получаем искомую свертку. 1.4.5. Методы быстрого вычислении круговой свертки Существуют три основных метода быстрого вычисления круговой свертки. Методы различаются требуемым объемом вычислительных операций и памяти, а также степенью точности, связанной с ошибками округления. Первый метод, основанный на использовании БПФ и получивший название метода быстрой свертки, приводит к существенному сокращению требуемого количества арифметических операций для последовательностей, длина которых больше 32. Недостатки метода — значительные ошибки округления, большой объем памяти, требуемый для хранения комплексных экспоненцнальных коэффициентов, и все еще значительный объем вычислений. Второй метод, использующий теоретико-числовые преобраэовиния (ТЧП), является точным, так как служит для преобразования последовательностей в кольце целых чисел.
Существенный недостаток, ограничивающий его применение в реальных системах,— зависимость между длиной последовательности Л! и требуемой длиной кодового слова, что приводит к длинным кодовым словам для больших Л'. Третий метод — метод модульной арифметики в кольце полиноиов, обеспечивающий высокие эффективность и точность вычислений. Недостаток этого метода заключается в сложности программирования вычислений, которая зависит от длины обрабатываемой последовательности. и 1пТ/ Рис. 1.15 1А.6. Использование теоретико-числовых преобразований Так как последовательности в цифровых системах определяются с конечной точностью, то онн могут быть представлены в виде последовательностей целых чисел, ограниченных сверху некоторым числом.
Теоретико-числовое преобразование определяется для последовательностей целых чисел х(пТ), п=О,..., У вЂ” 1 и Х(й), й=О,..., У вЂ” 1, как пара преобразований: )(» — ! х(пТ) = Л)'-1 ~', Х(й)(х "~ (шод М), А: — о (1.54) г! '=г, (щи М), где г(, гь з — целые числа; з)О в том и только в там случае, если 1ви ве гзг(' (шо(1 М) . Использование ТЧП для вычисления круговой свертки двух последовательностей целых чисел х(пТ) и 1)(пТ)=О,...,Л( — 1 аналогично ДПФ (см.
14.2) н заключается в выполнении следующих действий: 1) вычислении ТЧП последовательности х(пТ): .Ч вЂ” ! Х (»): — 2 *( У) " ) (~~( М), »=О. „..Ж вЂ” »» (».5»» п=о 2) вычислении ТЧП последовательности ЦпТ): л( — ! Н (й) г— н ~,. Ь(п Т) и"~ (шой М), Л=О, ..., У вЂ” 1; о=о (1.56) 3) перемножении полученных ТЧП: У (й) = (Х (й) Н (й)) (то6 М). А = О, ..., Л(' — 1; (1.57) 4) вычислении ОТЧП последовательности У(й) К вЂ” ! у (и Т) г— в ~Л' — 1 ~ )'(в)(х "~ (шо(1 М), п=О, ..., М вЂ” 1. (1.58) а=о Последовательность у(пТ) является искомой сверткой. Так как в кольце целых чисел по гпо(1 М числа могут быть представлены однозначно, если их абсолютное значение не превосходит М/2, то х(пТ) и Ь(пТ) должны быть промасштабированы таким образа,(, чтобы ~у(пТ) ~ (М/2.
С тачки зренля эффективности вьп(велений к ТЧП предьявляются следующие требования: число У должно быть представимо в виде гроизведения большого числа сомножителей, чтобы существовал эффективный алгоритм типа БПФ; умножение на степени и должна быть простой операцией; так, если а равно некоторой степени числа 2, то умножение сводится к сдвигам; число М должно иметь двоичное представление с малым количеством разрядов для облегчения операции по шо(1 Л4 и быть достаточно большим, чтобь! исключить переполнение. Наибольшее распространение на практике получили теоретико-числовые преобразования с числами Ферма (ТЧПФ) и Л(ерсенна (ТЧПЛ1). имеющих структуру, похожую на структуру ДПФ. Здесь М вЂ” целое положительное число; Л( — целое положительное число, взаимно-простое с М и такое, что на него делится число Р— 1, где Р— любой из простых сомножителей М„ а — число такое, что Л' является наименьшим положительным целым числом, для которого справедливо а(г— = 1(шод М).
Преобразование (1.53) называется прямым, а (1.54) — обратным ТЧП (ОТЧП). При вычислении ОТЧП встречаются операции сравнения, выполняемые над отрицательными степенями целого числа. По определению [1.12] Теоретико-числовое преобрпзрИНЫ Ферма [1.6, 1.121 является наиболее перспективным, так как позволяет использовать эффективные алгоритмы типа ВПФ. В качестве модуля М выбирается одно из чисел Ферма: М=Р~=2зг+1=2ь+1, 5=2'.
Здесь Р~ называется 1-м числом Ферма. Первые семь чисел равны: простые числа. Рз = 641 Х 6 700 417 Рв = 274 177 Х67 280 421 310 72! . В табл. 1.4 приведены параметры кескольких возможных реализаций ТЧПФ. Таблица .1.4 Л' для а-У2 Идляа 2 а ддя М„,„„ Пример И4. С помощью ТЧПФ вычислить свертку иоследовательносТей: к=[2, — 2, 1, О)-т; Ь=[1, 2, О, 0]т [1.12). В качестве модуля выберем число л(=Ра=17. При У=4 а=4. Матрица ТЧПФ (1.53) принимает внд 1 '1 1 1 1 1 1 1 1 4 — 1 — 4 1 4 16 13 1 — 1 ! — 1 1 16 1 16 1 — 4 —.1 4 1 13 16 4 (птод 17). "Так как 4-' — = — 4(глоб !7), то матрица ОТЧПФ 1 1 1 1 1 — 4 — ! 4 1 — 1 ' ! — 1 1 4 †! — 4 '1 1 1 4-' 4 а 4-' 4 — а 4 †' 4 ь 4 з464 9 -~-'е =4-' (той 17).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
