Устройство для вычисления цифровой свертки Советский патент 1987 года по МПК G06F17/14 

Изобретение относится к вычислительной и информационно-измерительной технике, может быть использовано для цифровой обработки сигналов и изображений, а также в устройствах кодирования, принцип действия которых основан на теории конечных полей (полей Галуа) и колец, и является усовершенствованием устройства по авт. св. № 1295415,

Длина импульсного отклика не должна превышать в известном устройстве половины величины объема теоретико- числового преобразования (ТЧП) N, которое должно удовлетворять условию

N

НОД(Р -1, Р,-1, ,.., Р„-1) (1)

где вертикальная черта а | S означает; а делит & НОД - наибольший общий делитель и модуль ТЧП

М . Р

Ы-2 1

. (2)

Цель изобретения - расширение диапазона длин обрабатываемых последовательностей.

На чертеже представлена функци- ональная схема устройства для вычисления цифровой свертки.

Устройство содержит п-разрядный регистр 1, умножитель 2 по модулю М блок 3 вычисления свертки, вход 4 задания корректирующего множителя, первый вход 5 умножителя, вход 6 задания последовательности отсчетов, первый 7 и второй 8 информационный входы блока 3 вычисления свертки, вход 9 разрешения записи, тактовый вход 10, управляющие входы 11-13, информационный выход 14.

В большинстве известных методов вычисления свертки модуль М предполагается простым. Для случая состав-рО(

.ногоМ Р7 Р

)W.-Z

объем ТЧП N

должен удовлетворять (1) и для чисел -1 слишком мал для практического применения указанных модулей.

Рассмотрим, при каких требованиях к значениям элементов сворачиваемых последовательностей и параметрам ТЧП возможно вычисление цифровой свертки объема N по составному моду.oi

лю . Р,. . .. для N, не удовлетворяющему условию (1), но делящему нацело некоторые, хотя бы одно, из чисел ().

Пусть в кольце целых чисел по модулю М ,1 ,.,. ,M-l существует обратный к N элемент N и корень из единицы порядка N TeZ. Произведение матрицы (е) обратного ТЧП и матрицы Ху,(е) прямого ТЧП (Х|(е) 6° , l,,N-1) не равно единичной по модулю М матрице, так как не выполняется условие цикличности.

Матрица (e)-Xj(e)

15

modM

кроме единичной по модулю М диагонали, содержит ненулевые элементы. В 20 худшем случае недиагональные элементы не равны нулю, для которых имеем:

. N-I .. .,,

-( : -it it

;.. N ) -б modM

-1 JLL ( N ) g modM,

(3)

30 a также g;.|j., g,;j и . Из соотношения (3) следует, что матрица D содержит не более N-1 различных между собой элементов, что и позволяет обозначить их через g,, g,

8н-1 V Свертка вычисляется по схеме

35,

(х)ТЧП(Ь) ,

где ОТЧП - обратное ТЧП.

В матричном виде имеем:

(е)-X, ,(e)-h

1

(4)

45

Увыч (х®Н)х(е) X (е)х

(x®h)D-у.

. Знаком ® обозначено умножение в кольце Yg - значение свертки, вычис-. 50 ленное согласно (4), которое может отличаться от истинного значения у.

Условие цикличности свертки выполняется для модуля F, определенного как

Л.

t

(5)

где f равен тем .из , определенных в разложении М, для которых выполня31354

ется условие N I () (для четного N необходимо уточнить условия выбора корня 5).

Отсюда следует, что g или g2 i-FniodM, ,N-1.

Приведем матрицу D к диагональной по модулю М. Для этого умножим (4)

на R такое, что , где Рд - проной строки, матриц прямого и обратностьте числа из разложения М, для ко- ю о нет повторяющихся элементов, торых не выполняется условие N|(Pg- -1) и которые не входят-во все g, ,N-1.

Исходя из структуры матрицы D, сле;.,,

дует, что все элементы g, ,N-1

равны между собой:

Имеем:

R R5,F R:),F R R,F

I f

R.HM -F F

R N-v-F

Л/

R

0 0 R 0 0 R

«

0 0 0

0.0 0

R

, R.y;(R.y; )modM, ,N-1. Так как R|M, обратный элемент R modM не существует, что не позволяет однозначно восстановить значение у. Оно может отличаться от у

вы ч

на

величину, кратную FmodM. Запишем это следующим образом:

У; У;ВЬШ +p;FmodM, , (6)

где р; - неизвестный коэффициент, прини -1ающий одно из значений О, Т, 2,...,(M|F-1).

Определим, каким должен быть коэффициент 1, чтобы выполнялось равен-

СТВО у(2 Х,Ь)Увь1Ч ( Ь)

y(.x,h) 2 y{x,h)2(y,,,, (x,h) + )modM(2-y8«,i4 (x,h) + 2 pF)(modM).

При .(modM) у (g. х,Ь) (t. x,h).

Итак, если все элементы одного из массивов (х или h) имеют множитель jJmodM (далее - корректирующий множитель) такой, что g,, с помощью ТЧП можно вычислить истинную циклическую цифровую свертку объема N такого, что не все составляющие разложения М удовлетворяют условию NJ(Pj- 1), ,m.

Требования к модулю F существенно. зависят от того, четное или нечетное N выбирают. Пусть N нечетное.

В строках, кроме первой, единич о нет повторяющихся элементов,

Исходя из структуры матрицы D, сле;.,,

дует, что все элементы g, ,N-1

равны между собой:

15

N

20

.

. (...-ье )modM N (е-1Г (eSOmodM. Запишем модуль М как . Теперь S modF()(modF) и gmodF N (-1) ()modF 25 0(modF).

Итак, при нечетном N модуль F-может быть определен из (5).

Рассмотрим случай четного N. 30 Для невырожденности матриц ТЧП на 6 накладывается дополнительное условие:

g KmodM).

35

Значения g, ,N-1 не все равны между собой. Можно показать, что имеются только три различных значения g. Обозначим их через g(, 40 §N/241 соответствии с положением в первой строке матрицы D.

Выпишем элементы g, ,g,gf,,2+,

g, (...+ )modM g4.2.N (be + ... + )modM

gH ф Г (H-)modM.

f-n

Как показано вьше, (modF) для модуля F, определяемого (5).

g2modF( (l + .. .)modF 2-N ()- ( -1)0(modF) ,

если

1 (modF) ; e 1 (modF).

Для выполнения требования g

0(modF) корень 6 должен удовлетворять условию:

(2 (modM))- ( +1)0(raodF).

Итак, в случае четного N на выбор

корня С лП Z накладываются следу- . ющие условия:

6: 1(modM) i 1 (modM)

(modF).

При проектировании и создании устройства для вычисления свертки выбираются параметры ТЧП М, , исходя из которых вычисляют, используя (2), (7) , (8) , корректир.зтощий множитель h и определяют возможные значения N.

Устройство для вычисления цифрово свертки работает следующим образом.

Перед началом работы в регистр 1 записьюается значение корректирующего множителя с помощью входов 4,9 и 10 регистра 1. Далее временная диаграмма работы устройства не отли- чается от временной диаграммы известного устройства с той лишь разницей, что все управляющие сигналы подаются с задержкой, равной задержке, которую вносит умножитель 2.

Редактор Н.Тупица Заказ 5695/44

Составитель А.Баранов Техред А.Кравчук

Корректор

Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

й

3542056

Значения входной последовательности S,, подаваемой на входы 6 умножителя 2, последовательно умножаются на корректирующий множитель raodM и вместе с значениями последовательности 5 поступают соответственно на входы 7 и 8 блока вычисления свертки. 10

20

Формула изобретения

Устройство для вычисления цифровой свертки по авт. св. № 1295415, 15 отличающееся тем, что, с целью расширения области применения за счет расширения диапазона длин обрабатываемьгх последовательно- стей, в него введены п-разрядный регистр ( -1, М-модуль преобразования) и умножитель по модулю М, выход которого подключен к информационному входу блока преобразования Фурье-Галуа, первый вход умножителя по модулю М подключен к выходу п-раз- рядного регистра, информационный вход которого является входом задания корректирующего множителя устройства, входом задания последовательности отсчетов которого является второй вход умножителя по модулю М, тактовый вход и вход разрешения записи п-раз- рядного регистра являются соответственно тактовым входом и входом разрешения записи устройства.

25

30

Корректор Л.Пилипенко

Изобретение относится к вычислительной и информационно-измерительной технике и может быть использовано для цифровой обработки сигналов и изображений, а также в устройствах 9 о- 10 кодирования, принцип действия которых основан на теории конечных полей (полей Галуа) и колец. Цель изобретения - расширение диапазона длин об-t рабатываемых последовательностей. Поставленная цель достигается тем, что в состав устройства входят п-разрядный регистр ( -1, М - модуль преобразования), умножитель по модулю М 2, блок вычисления свертки 3, вход задания корректирующего множителя 4, первый вход 5 умножителя, вход задания последовательности отсчетов 6, первый 7 и второй 8 входы блока вычисления свертки, вход разрешения записи 9, тактовый вход 10, управляющие входы 11, 12 и 13, информационный выход 14. 1 ил. (Л N)