Устройство для вычисления цифровой свертки

(54) уСТРОйС ВОЙ СВЕРТКИ (57) Изобрет тельной и ин ной технике но для цифро и изображени О ДЛЯ ВЫЧИСЛЕНИЯ Оие относится к вы рмационно-измерит может быть исполь исл льоватки сигналов в устройствах вои обра й, а так ОСУДАРСТБЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидеУ 1295415, кл. С 06 кодирования, принцип действия которых основан на теории конечных полей (полей Галуа) и колец. Цель изобретения - расширение диапазона длин обрабатываемых последовательностей. Поставленная цель достигается тем, что в состав устройства входят и-разрядный регистр (Г=2 -1, Г - модульь преобразования), умножитель по модулю г 2, блок вычисления свертки 3, вход задания корректирующего множителя 4, первый вход 5 умножителя, вход задания последовательности отсчетов 6, первый 7 и второй 8 входы блока вычисления свертки, вход разрешения записи 9, тактовый вход 10, а управляющие входы 11, 12 и 13, инфорф мационный выход 14, 1 ил,1 13542Изобретение относится к вычисли-тельной и информационно-измеритель ной технике, может быть использовано для цифровой обработки сигналов и5 изображений, а также в устройствах кодирования, принцип действия которых основан на теории конечных полей (полей Галуа) и колец, и является усовершенствованием устройства по авт, св, У 1295415.Длина импульсного отклика не должна превышать в известном устройстве половины величины объема теоретикочислового преобразования (ТЧП) И, ко торое должно удовлетворять условиюМ НОД(Р, -1, Р -1, , Р -1) (1)где вертикальная черта а )8 означает; 20 а делит оНОД - наибольший общий делитель и модуль ТЧП 05 2Пусть в кольце целых чисел по модулю М Е =10,1 Мсуществует обратный к И элемент И и кореньогизз единицы порядка И Е = 41 еЕ . Проиэведение матрицы х (е) обратного ТЧП и матрицы х (е) прямого ТЧП (х,(е)= =Я , 1,К=О,И) не равно единичнойепо модулю М матрице, так как не выполняется условие цикличности,Матрица Р=х, (е) х,(е)=1 К К,К 1 1ф КншойМ Кн Кн 2 ф ффкроме единичнои по модулю М диагонали, содержит ненулевые элементы. В худшем случае недиагональные элементы не равны нулю, для которых имеем:(3) шос 1 М,(4) 55Р=К,(5) Цель изобретения - расширениедиапазона длин обрабатываемых последовательностей,На чертеже представлена функциональная схема устройства для вычисления цифровой сверткиУстройство содержит и-разрядныйрегистр 1, умножитель 2 по модулю М,блок 3 вычисления свертки, вход 4задания корректирующего множителя,первый вход 5 умножителя, вход 6 задания последовательности отсчетов,первый 7 и второй 8 информационныйвходы блока 3 вычисления свертки,вход 9 разрешения записи, тактовыйвход 10, управляющие входы 11-13информационный выход 14,В большинстве известных методоввычисления свертки модуль М предполагается простым. Для случая составного М=Р РРобъем ТЧП Идолжен удовлетворять (1) и для чиселйМ=2 -1 слишком мал для практическогоприменения указанных модулей. Рассмотрим, при каких требованиях к значениям элементов сворачиваемых последовательностей и параметрам ТЧП возможно вычисление цифровой свертки объема И по составному моду.лю М=Р РРдля И, не удовлетворяющему условию (1), но делящему нацело некоторые, хотя бы одно, из чисел (Р,-1). М=о а также К;,;, =К и К1 =К 1,;Из соотношения (3) следует, что матрица 0 содержит не более Иразличных между собой элементов, что и позволяет обозначить их через К К., 3 5,Свертка вычисляется по схеме у=х 1 =ОТЧПТЧП(х)тЧП(Ь)7,где ОТЧП - обратное ТЧП, В матричном виде имеем: х=х (е) х, Н=х,(е) Ь; 45 Увьч =х, (е) (хУН)=х,(е) х, (е)(хай)=0 у,Знаком Р обозначено умножение в кольце Е,; у щ - значение свертки, вычис-,ленное согласно (4), которое может отличаться от истинного значения у.Условие цикличности свертки выполняется для модуля Г, определенного как где Г равен тем .из Р определенныхв разложении М, для которых выполняК нч К ЩГКЭ,Г К2 тпоЛ 1= м нв ф К 0 0О 0 К 0О 0 0 КО 25 =0 (щостР) . О0 0К Я 1(щойМ) . если 3 135 ется условие И(Г) (для четного М необходимо уточнить условия выбора корня Е).Отсюда следует, что и щойР=О или и =1 Гпюс 1 М, 2=1,И.Приведем матрицу 0 к диагональной по модулю М. Для этого умножим (4) на К такое, что К=ПР , где Рз - простые числа из разложения М, для которьж не выполняется условие И(Р - -1) и которые не входят во все и 2=1,И.Имеем: Значит, К у, =(К у; ц )щос 1 М, т.=О,В.Так как К М, обратный элемент К щодМне существует, что не позволяет однозначно восстановить значениеу, Оно может отличаться от ущ навеличину, кратную Рпюс 1 М. Запишемэто следующим образом: у =утвыц +Рщос 1 М, 1=0,И, (б) где З, - неизвестный коэффициент, принимающий одно из значений О, 1, 2(МГ).Определим, каким должен быть коэффициент , чтобы выполнялось равенство у( х,тт)=у( х,тт)щостМ у(Дх,тт)= у(х,Ь)=(у, (х,Ь)+ +Р)щос 1 М=( у,(х,Ь)+р 8 Р) (щос 1 М),ПриР=О(щос 1 М) у( х,Ь)=у,ы( х,Ь),(7)Итак, если все элементы одного из массивов (х или Ь) имеют множитель щос 1 М (далее - корректирующий множитель) такой, чтоР=М, с помощью ТЧП можно вычислить истинную циклическую цифровую свертку объема И та 4205кого, что не все составляющие разложения М удовлетворяют условию Б (Р, --1), =1,щ.Требования к модулю Р существенно,5зависят от того, четное или нечетноеИ выбирают, Пусть И нечетное,В строках, кроме первой, единичной строки, матриц прямого и обратного ТЧП нет повторяющихся элементов.Исходя из структуры матрицы Э следует что все элементы 821 г=1 уя равны между собой: а й-т 5 , =д=И (1+с,+с, +,.+с. )шос 1 М==т 1 Ы) Ы, -1) 1 М. Запишем модуль М как М=Р. Теперь в щос 1 Р= щосП 1)пюс 1 Г=1(пюс 1 Г) и дщойР=И -1) ( -1)шойГ= Итак, при нечетном И модуль Р может быть определен из (5).Рассмотрим случай четного Н.30 Для невырожденности матриц ТЧП наЯ накладывается дополнительное условие: 35Значения и., Е=1,Мне все равнымежду собой. Можно показать, что имеются только три различных значенияОбозначим их через В,а 40 й(2 Фтв соответствии с положенйемв первой строке матрицы П.Выпишем элементы пя ,дд,=Б (1+Я+Я Я )щос 1 М а,=2 И (1.ЕЯ" )шоаМВп =( - ) 1(1+6)щос 1 М - "и Я 50 Как показано выше=0(щос 1 Г) для Э модуля Р, определяемого (5), дрос 1 Р=(2 М (1+6 +Е Е)щос 1 Р=Составитель А,БарановТехред А.Кравчук Корректор Л, Пилипенко Редактор Н.Тупица Заказ 5695/44 Тираж 671 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб д, 4/5 Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4 Итак, в случае четного М на выборН г-корня с, = .11 е 2, накладываются следу.ющие условия: При проектировании и создании устройства для вычисления свертки выбираются параметры ТЧП М, Е, исходя иэ которых вычисляют, используя (2), (7), (8), корректирующий множительи определяют возможные значения И,Устройство для вычисления цифровой свертки работает следующим образом. Перед началом работы в регистр 1записывается значение корректирующего множителяс помощью входов 4,9и 10 регистра 1. Далее временнаядиаграмма работы устройства не отличается от временной диаграммы известного устройства с той лишь разницей,что все управляющие сигналы подаютсяс задержкой, равной задержке, которую вносит умножитель 2,Значения входной последовательности Б, подаваемой на входы 6 умно- жителя 2, последовательно умножаются на корректирующий множитель шос 1 М и вместе с значениями последовательности Б поступают соответственно на входы 7 и 8 блока вычисления свертки,10 Формула изобретения Устройство для вычисления цифровой свертки по авт. св. Р 1295415,о т л и ч а ю щ е е с я тем, что,с целью расширения области применения за счет расширения диапазонадлин обрабатываемых последовательностей в него введены п-разрядныйьорегистр (М=2 -1, М-модуль преобразования) и умножитель по модулю М,выход которого подключен к информационному входу блока преобразованияФурье-Галуа, первый вход умножителя25 по модулю М подключен к выходу и-разрядного регистра, информационный входкоторого является входом задания корректирующего множителя устройства,входом задания последовательностиотсчетов которого является второйвход умножителя по модулю М, тактовыйвход и вход разрешения записи и-разрядного регистра являются соответственно тактовым входом и входом разрешения записи устройства,