Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 142
Текст из файла (страница 142)
Циклическая свертка трехэлементных последовательностей. Прямое вычисление (19.49) Н' 2 = » 270+» 1У1 Ь» ОЛ, В 1 = » 2»2 + У1УО +» ОУ1, В 0» 2У1 +» 1У2 +»ОУО требует девяти операций умножений и шести операций сложения. Модульная алгебра, с использованием китайской теоремы об остатках для произведения модулей 2 3 (з — 1)(з + з+ 1) = з — 1 позволяет сократить число операций умножения до четырех за счет увеличения числа сложений.
При этом обеспечивается цикличность свертки с длиной цикла 3. Восстановленное произведение находят согласно 2 (28.10), вводя вычеты н 1(з) и в2(з) сомножителей»зз + 2 2 ! Уз в» О, узз ь у!в ь УО по модулям з — 1 и з + з + 1, и1(5) = (3 +3 ! 1)йс/3— 2 — (з + л — 2)~(з)/3 (шод (з — !)), (19.51) где Д1(з) =(»2+» ! +»о)(У2+у! муо); ~(з) = ((»1 — »2)з+ +" 0 " 2П(у! У2)з + УО ЛП Число операций операций умножения сокращается до пяти или четырех при быстром перемножении двучленов.
19.9.3. Матричная фориа записи алгоритьсое ускоренного вычисления коротких сверток Возможна в двух разновидностях записей и = со(Ь» ау) и в = с 8 а у . (19. 52) Матрицы а и Ь первой записи обеспечивают приведение многочленов сигнала и импульсной характеристики фильтра, коэффициенты которых образуют их векторы у и», к остаткам. Точка в этой записи — нестандартный знак понолспонентного перелсножения состаапяюсцих векторов (остатков), в результате которого образуется новый вектор.
Матрица со восстанавливает коэффициенты многочлена-произведения (свертки) по остаткам. Во второй записи вектор с точкой Ь» заменен заранее вычисляемой диагональной матрицей: 8 = /с йа8 (Ь»), (19.53) содержащей его элементы на диагонали. Матрица с = со!/с воспроизводит с точностью до этого же коэффициента матрицу сО в упрощенном виде. Ниже приводятся примеры матричной записи. т Для циклической свертки 2х2 в = !! в О в 1!! и (19.54) а=Ь=с= /с = 1/2. 1 — 1~ Для линейной свертки 2х2 в = 1! и о и ! и Ц и 1 0 1 0 ! 0 0 а= 1 1, /сЬ= 1/2 1/2, с= 0 1 -1.
1 — 1 1/2 — 1/2 — 1 1 1 т Для циклическойсверткиЗхЗ в =!! во в ! в2!! и 1 0 — 1 †! — 1 2 1 1 1 0 — 1, /сЬ= о 1 ! — 2 1 0 1 — 1 Наряду с использованием китайской теоремы об остатках, для ускорения вычислений применяют; ° запоминание промежуточных результатов; ° замену умножений чисел на целочисленные степени числа 2 сдвигами двоичных разрядов и т.д. 19.9.4. Технология сведения длинных циклических сверток к коротким Наряду с модуяьной апгеброй .многочпенов можно использовать модупьную арифметику чисел, явпяюсс!ился номерами (индексалси) свертываемых последовательностей. Его полагают произведением взаимно простых модулей п = пс п2 ...
пв Индексы переменных выражают через остатки от деления на модули: К, = /с(шос! и,), /. = /(шос! п,). Перемножение же матриц (!9. 52) переходит в кронекеровское, что заменяет однократное весовое суммирование многократным. Остановимся на случае р = 2, связанном с переходом от однократного к двукратному весовому суммированию. В этом случае и = р (с!хс2) йа8 Н/с!Ь!х/с2Ь2)р»Ка1ха2)р у. (19.55) 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 ! 0 0 0 0 0 0 ! 0 0 0 0 0 0 0 0 1 Уо Уоо Уос Ую У! У2 уз У4 У5 =РУ. У1! У20 Ущ 309 Здесь р — пврестановачная матрица; х — знак кроненеровского матричного умножения (см.
разд. 26.2); аь /с, Ьс, с, (/ = 1, 2) — матричные параметры коротких сверток. Пусть, п! = 3, п2 = 2, т.е. п = б. Десятичные индексы /' = О, 1, 2, 3, 4, 5 векторов у, » заменяются парными индексами в системе остаточных классов — остатками от деления индексов на 3 и 2. Так, индекс 0 заменяется на 00, индекс 1 на 11, индекс 2 на 20, индекс 3 на 01, индекс 4 на 1О, индекс 5 на 21.
Составляющие векторов у, » с новыми индексами упорядочиваются согласно (19.52). Это требует преобразования векторов у, » перестановочными матрицами р: М(и) А(и) М(и) А(и) 5 470 7 958 1О 176 14 748 20 420 26 304 52 788 7! 265 95 744 241 680 950 1 280 1 056 2 280 3 200 3 648 7 680 !О 032 12 160 29 184 18 20 24 30 36 48 60 72 84 120 !84 230 272 418 505 900 1 120 ! 450 2 !00 3 096 !80 2!О 240 360 420 504 840 1 008 1 260 2 520 38 50 56 80 95 132 200 266 320 560 19.9.9.
Алаоритмы ДПФ Виноерада (АВПФ) АВПФ малой длины. Для простых и экспоненциой Ч2л/и альные множители (19.24) зв, где зв = е, принимают лишь и неодинаковых значений, одно из которых единица. Ненулевые числа и, т, /с, т/с являются элементами простого числового поля Галуа Ог(п) с некоторым примитивным элементом а (разд. 28.3) и стеиенячи а, выражаются взяты.ми ио модулю и: т=а,/с=а,т/с=а (шос)и).
Здесы,) — также элементы рассматриваемого поля. Вьгчисление ДПФ С сводится к циклическим сверткам размера (и — 1) и операциям сложения; С = СЬ а т'. (19.56) Здесь С и 3/ — комплексные вектор-столбцы, а — прямоугольная вещественная матрица, Ь вЂ” диагональная вещественная матрица, С вЂ” матрица, элементами которой являются чисто вещественные (или мнимые) числа.
Набор АВПФ малой длины и приведен в 18.23, приложение Б] для простых и и их степеней. АВПФ большой длины. Пусть число и элементов является произведением р взаимно простых чисел ин Выражение (19.56) при р = 2 переходит в С = р (С! хС2) (Ь ! хЬ2) (а! ха2) р 3/, (19.57) т где р и р — перестановочные матрицы. Таблица 19.3. Сопоставление затрат АВПФ и БПФ Кули-Тьюки ]8.23] Затраты АВПФ Затраты БПФ Л/(и) А(и) М(и) А(и) 320 768 1 792 4 006 9 216 20 480 45 056 212 992 30 60 120 240 504 1 008 2 520 !0920 72 144 288 648 1 584 3 564 9 504 38 760 384 888 2 076 5 016 14 642 34 920 100 188 320 196 32 64 128 256 512 ! 024 2 048 8 192 480 ! 152 2 688 6 144 43 824 30 720 67 584 3!9 488 310 В ходе расчетов (19.52) вычисляются вошедшие в (19.55) кронекеровские произведения вида ахЬ, которые дают блочные матрицы !!ай Ь!!.
После расчетов (19.52) двоичные индексы составляющих вектора зч возвращаются перестановочной матрицей р, входящей в (19.55) в десясиичную форму. Затраты вычисления, а именно число умножений М(п) и число сложений А(п), требуемых для проведения п-точечных вещественных циклических сверток, приведены в табл. 19.2 !8.23]. Таблица 19.2. Затрат!в вычисления пиитических свериюк М(п) и А(п) ]8.23] В табл. 193 сопоставлены затраты арифметических операций М(п) и А(п) АВПФ и БПФ Кули-Тычки.
Сокращение затрат АВПФ обеспечивается за счет усложнения программирования, 19.9.б. Теоретико-числовые преобразования (ТЧП) как метод цифровой обработки Как и описанные в разд. 19.9.1-19.9.5 преобразования с использованием модульной алгебры многочленов, ТЧП ускоряют обработку за счет усложнения программирования. Они устраняют влияние ошибок округления чисел, вследствие проведения всех арифметических операций в системе остаточных классов. Существенным недостатком ТЧП, кроме усложнения программирования, является жесткие требования к длинам обрабатываемых последовательностей (см. ниже).
Прямые (ТЧП) и обратные (ОТЧП) теоретико-числовые преобразования подобны операциям ДПФ и ОДПФ. Они проводятся в числовых полях с большим, но ограниченным числом элементов, являющихся разновидностями полей Галуа Ссг(р) (разд. 28.3). Обычно используют паля простых чисел: ° Ферма с числами р = 2" + 1, р = 2, 4, 8, 16; ° Мерсенна с числами р=2"-1, р = 3,5,7, 13, 17, 19.
31,51. Алгоритмы ТЧП и ОТЧП имеют вид и-! п! ел = ~~~ уиа (шодр), уи = — ~д.а~~ (шос(р). (19.58) им) ил Для преобразований Ферма (ТЧПФ) и Мерсенна (ТЧПМ) число а яазяется корнем нз единицы в поле вещественных чисел (см. разд. 28.3), взаимно простых с р, т.е. удовлетворяет уравнению а =1,/=р — 1. (19.59) Имеется аналогия с ДПФ, ОДПФ„в которых вводился Чзп/п корень из единицы е в поле комплексных чисел. Сравнения (19.58), (19.59) основаны на матричном сравнении !!а !! !!а !! = и1 (шод р). (19.60) Длина последоватесьности п должна быть делителем числа р — 1, что и вводит упомянутое выше ограничение в использование ТЧПФ. Примеры ТЧПФ и ОТЧПФ.
Пусть р = а = и = 4. Проверим допустимость выбора указанных параметров. Найдем ТЧПФ последовательности 1, 2, О, О и ОТЧПФ от этого ТЧПФ. 4 В данном случаер =2 +1 =17. Число и = 4 является 4 делителем р — 1 = 2 = 16. Число ТЧПФ является взаимно простым с р, значение а = 256 = ! (шод 17). Остальные О 4 характерные степени а принимают значения: а = а -4 1 3 2 2 3 1 =а =!,а =а =4,а =а =16,а =а =1З,значение п = 13 (шод 17). Числа а — 1 не имеют общих множителей с р для всех /с от О до р — 1. Заметим, что указанные параметры приняты в иллюстративных целях, хотя на практике выбирают намного большие значения р. ТЧПФ имеет вид: яо = 1 1» 2 1 е О+ 0 = 3 (аос! 17), 8! = 1 1 е 2 13 е 0 -ь 0 = ! 0 (аод ! 7), 82 = 1.1» 2 16» 0 + 0 = 16 (люб 17), 82=11+24+0+0=9. (аод17).
ОТЧПФ восстанавливает заданную выборку: уо = 13(3 1 е 10.1+ 16 1+ 9 1) =! 3.4 = 1 (аод 17), у! =!З(З!»10 4» 16.!6+913) =13 8 =2 (аос1 17), уг = 13(3.1 + 10.16 + ! 6 1 + 9 16) = 13 О = О, (пюд 17), уз =!3(3 1»1013+1616-ь94) = 13 0=0 (аос1 17). На рис. 19.28,а представлена числовая последовательность, на рис. 19.28,6 — ТЧП. По аналогии с ДПФ введены их отрицательные значения, например, -4 = 13 (аод ! 7). Суммирование гармоник ТЧП по аод 17 возвращает к исходной последовательности (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
