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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (5и 4 С 06 F 15 332

ВСЕСРЩ,11 P q

1) ю

3 l„", IP".-,:;

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н Д BTOPCHOMY СВИДЕТЕЛЬСТВУ (61) 1295415 (21) 4089541/24-24 (22) 14.07.86 (46) 23,11.87. Бюл. N. 43 (71) Физико-механический институт им.Г.В.Карпенко (72) О.А.Вакульский и Л.В.Вариченко (53) 681.32 (088.8) (56) Авторское свидетельство СССР .

У 1295415, кл. С 06 F 15/332, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЦИФРОВОЙ СВЕРТКИ (57) Изобретение относится к вычислительной и информационно-измерительной технике и может быть использовано для цифровой обработки сигналов и изображений, а также в устройствах

ЛК, 1354205 А2 кодирования, принцип действия которых основан на теории конечных полей (полей Галуа) и колец. Цель изобретения — расширение диапазона длин обрабатываемых последовательностей.

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

1 13542

Изобретение относится к вычисли- тельной и информационно-измеритель-! ной технике, может быть использовано для цифровой обработки сигналов и

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

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

N НОД(Р, -1, P -1, ..., Р -i) (1) где вертикальная черта а IP означает: 20 а делит о НОД вЂ” наибольший общий делитель и модуль ТЧП

05 2

Пусть в кольце целых чисел по модулю M Z =)0,1,...,М-11 существует обратный к N элемент N и корень нгиз единицы порядка N f = g1EZ . ПроиэFT) ведение матрицы х (е) обратного ТЧП и матрицы х (е) прямого ТЧП (х,(е)=

=Я, 1,cC--ON-1) не равно единичной

g0 по модулю М матрице, так как не выполняется условие цикличности.

Матрица D=x (е) х,„(е)=

Кi ° ° ° gNI

К, 1 ... Кн z

modM

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

;с;е

К =N Я -f, modM=

Ъ

=о

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

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

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

В большинстве известных методов вычисления свертки модуль М предполагается простым. Для случая составного М=Р P ... Р " объем ТЧП N должен удовлетворять (1) и для чисел

И

M=2 -1 слишком мал для практического применения указанных модулей.

Рассмотрим, при каких требованиях к значениям элементов сворачиваемых последовательностей и параметрам

ТЧП возможно вычисление цифровой свертки объема N no составному моду:лю М=Р", Р7" P для N, е удовлетворяющему условию (1), но делящему нацело некоторые, хотя бы одно, из чисел (Р;-1).

И-1

= и

G=o (3) modM, у=х«1=ОТЧП(ТЧП(х).ТЧП(П)7, 4О где ОТЧП вЂ” обратное ТЧП.

В матричном виде имеем: (4) х=х (е) ° х, Н=х,(е) ° h;

45 вь ч =х м е) (хаН) =х (е) х,„ (е)"

x(x(Bh) =D у.

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

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

Р К, f2 (5) где Г равен тем .из Р определенных

У в разложении М, для которых выполнязо à также gi, =К; и gi

Из соотношения (3) следует, что матрица D содержит не более N-1 различных между собой элементов, что и позволяет обозначить их через gi

3 5, Свертка вычисляется по схеме

R м-(R 1(2

RQ м; F

К ЩР

КЭ,F R 2 шоЛ1=

R ° D= м-(м-в

R 0 0 ... 0

0 R 0 ... 0

0 0 R ... О

25 =0(modF) .

О ° О О .... R

Я $ 1 (modM) . если

3 135 ется условие N 1(ft-1) (для четного

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

Отсюда следует, что g modF=O или

g, FmodM, Z=i,N-1, Приведем матрицу D к диагональной по модулю M. Для этого умножим (4) на R такое, что R=llP, где P — простые числа из разложения M для которьж не выполняется условие Nj(P—

-1) и которые не входят во все я

Z=19N-1.

Имеем:

Значит, R у =(R у; „ч )modM, i=O,N-1.

Так как R) М, обратный элемент R modM не существует, что не позволяет однозначно восстановить значение у. Оно может отличаться от у „ч на величину, кратную Ршос1М. Запишем это следующим образом: у, =у; выц + (;FmodM i=O,N-1, (6) где P, — неизвестный коэффициент, принимающий одно из значений О, 1, 2,...,(MIF-1).

Определим, каким должен быть коэффициент, чтобы выполнялось равенство y(g ° х,h) =у „„(х,h)modM

y(g ° х,h)=g у(х,h)=g(y,, (х,h)+

+PF) modM= (g у „,„(х,h)+ g P F) (modM) .

При g ° F=Î(modM) у(х,h)=y „,„((t ° х,h), (7)

Итак, если все элементы одного из массивов (х или h) имеют множитель

)modM (далее — корректирующий множитель) такой, что f F=M, с помощью

ТЧП можно вычислить истинную циклическую цифровую свертку объема N та4205 кого, что не все составляющие разложения М удовлетворяют условию N j(P>—

-1), j =1,m.

Требования к модулю F существенно.

5 зависят от того, четное или нечетное

N выбирают. Пусть N нечетное.

В строках, кроме первой, единичной строки, матриц прямого и обратного ТЧП нет повторяющихся элементов.

Исходя из структуры матрицы D следует что все элементь(821 Е=1уя-1 равны между собой: - (2 м-\

g =g=N (1+/+6 +...+Е )modM=

=N (Е-1) (Я, -1)modM.

Запишем модуль М как М= (Р. Теперь и и

modF=(Q modM) modF=1 (modF) и

gmodF=N (E-1) (g -1)modF=

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

Рассмотрим случай четного N, 30 Для невырожденности матриц ТЧП на

Я накладывается дополнительное условие:

Значения g,,Z=1,N-1 не все равны между собой. Можно показать, что имеются только три различных значения

Обозначим их через g(,я

40 М(2б( в соответствии с положенйем в первой строке матрицы D, Выпишем элементы д,,д,дм (я(=И (1+Я+Я +...+f )modM а,=2 N (1-Е +6+...+Е )modM

g„=() И (1+Я"")тос1М. — б(Я

Как показано выше g =0(modF) для

Э модуля F, определяемого (5), дрос1Р=(2N (1+G +E +...+Е )modF=

=2 N (6 -1) (Е -1)=0(modF), 55

E =1(moclF); f g 1 (modF).

1354? 05

Для выполнения требования — +!

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

Я (2 (modM) ) (Я +1) =0(modF) .

=1 (modM) Я g 1 (modM) 3.

Е -1(modF) .

Составитель А. Баранов

Техред А.Кравчук Корректор Л. Пилипенко

Редактор Н.Тупица

Заказ 5695/44 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r.Óæãoðoä, ул.Проектная,4

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

Н Г- корня . = - 11еХ„ накладываются следу.ющие условия:

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

1 и определяют возможные значения N.

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

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

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

Устройство для вычисления цифро" вой свертки по авт. св. У 1295415, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет расширения диапазона длин обрабатываемых последовательностей в него введены п-разрядный ь и

2д регистр (М=2 -1, М-модуль преобразования) и умножитель по модулю М, выход которого подключен к информационному входу блока преобразования

Фурье-Галуа, первый вход умножителя

26 по модулю M подключен к выходу и-разрядного регистра, информационный вход которого является входом задания корректирующего множителя устройства, входом задания последовательности отсчетов которого является второй вход умножителя по модулю М, тактовый вход и вход разрешения записи и-разрядного регистра являются соответственно тактовым входом и входом разрешения записи устройства,