Устройство для свертки по произвольному модулю

 

Изобретение относится к вычислительной технике и может быть использовано при проектировании цифровых систем повышенной надежности. Цель изобретения - сокращение аппаратурных затрат устройства. Устройство содержит регистры 1,11, элементы ИЛИ 2,13, элемент задержки 10, группу 3 вычитателей, группу 5 коммутаторов, группы 6,8 блоков сравнения, группу 7 элементов И, коммутатор 12. По сигналу на входе 16 запуска устройства с информационного входа 15 устройства через коммутатор 12 на второй регистр 11 записывается контролируемый код. С выхода регистра 11 этот код поступает на входы первого операнда вычитателей группы 3. На входы второго операнда вычитателей поступают с группы 4 входов устройства константы вычитания. Результат вычитания анализируется блоками сравнения групп 6,8. Формирование свертки заканчивается при равенстве нулю результата на выходе одного из вычитателей группы 3 или в случае, когда на выходах "Меньше" всех блоков сравнения группы 6 будут единичные сигналы. 1 ил.

СОЮЗ С08ЕТСНИХ

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

РЕСПУБЛИН (51) 5 G 06 F 11 00

»

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

И ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЬГГИЯМ

ПРИ fHHT СССР (21) 4490693/24-24 (22) 05.10.88 (46) 23.09.90. Б»ол. № 35 (72) Л. С. Сорока, А. Ф. Чипига и- В. А. Краснобаев (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹ II243l0, кл. G 06 F I I/00, 1983.

Авторское свидетельство. СССР

¹ 1509903, кл. G 06 F II/00, 1987.

„„SU „„1594541 (5 » УСТРО11СТВО ДЛЯ СВВ 1.КИ ПО

Г1Р0113ВОЛЬ11ГМУ МОДУЛЮ (57) Изобретение относитсн к вычислительной технике и может быть использовано ирн проектировании цифровых систем иов ниенной надежности. Цель изобретения — сокра»пение аппаратурных затрат устройства.

Устройство содержит регистры 1, 11, элементы ИЛИ 2, 13, элемент задержки 10, 1594541 группу 3 вычитателей, группу 5 коммутаторов, гру1шы 6, 8 блоков сравнения, группу 7 элементов И, коммутатор 12. По сигналу на гход» 16 запуска устрокства с информационного входа 15 устройства через коммутатор 12 на второй регистр 1 записывается контролируемый код. С выхода регистра 11 этот код поступает на входы первого операнда вычитателей группы 3. 1-!а входы второго

Изобретение относится K зычислительной техн;:ке и может быть ис:ользованс при проектировании цифровых систем повышенной надежности.

Целью изобретения являегся сокращение аппаратурных затрат устройства.

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

Устройство содержит первый регистр первый элемент ИЛИ 2, группу вычитателей 3, группу 4 входов задания констант вычитания устройства, группу 5 коммутаторов, первую группу блоков 6 сравнения, группу элементов И 7, вторую группу блоков 8 сравнения, ин рормационный выход 9 устройства, элемент 10 задержки, второй регистр 11, коммутатор 12, второй элемент ИЛИ 13, выход 14 признака завершения свертки устройства, информационный вход 15 устройства, вход !6 запуска устройства.

Число констант, необходимых для нормальной работы устройства, определяется выражением где А„,,„, — — максимальное контролируемое число;

P — модуль свертки;

IKI — округление К до большего целого числа.

Константы формируются по следующему закону:

--соиsti=II /2 (XP, P (!) где 1(i(n.

Вычитатели группы 3 формируют значения разностей

А„— con sti, где А — контролируемое число.

Если одна из разностей равна нулю, то

А нацело делится на Р, т. е. имеет нулевое

-значение свертки. Если ни одна из разностей не равна нулю, то берется наименьшая положительная разность Axi и вновь повторятся вычисление разностей А, — consti. Так

|родолжается до тех нор, пока разность не оказывается меньше значения const n. Полученная разность является значением свертки контролируемого числа по модулю P. В ка15 0

ЗО

55 операнда вы гитателей поступают с ггуппь1 4 входов устройства константы вычитания.

Результат вычитания анализируется блоками сравнения групп 6, 8. Формирование свертки заканчивается при равенстве нулю результата на выходе одного из вычитателей группы 3 или в случае, когда на выходах

«Меньше» всех блоков сравнения группы 6 будут единичные сигналы. ил. честве Р может выбираться произвольное число.

Устройство работает следуюгци;> образом.

В исходном состоянии на входы грушгы 4 задания констант выччтания устройства в соответствии с выражением (1) поданы значения констант. Регистры 1 и 11 обпулснь, поэтому на объединенных входах первь х операндов группы 3 Вычитателей информация отсутствует, на выходах вычитателек группы 3 присутствуют значения констант, удовлетворяющие выражению (1), следовательно, на выходах блоков 6 сравнения первой группы и выходах блоков 8 сравнения второй группы управляк>щих сигналов нет, с элементов И 7 группы ничего не подается, коммутаторы 5 группы разомкнуты.

Двоичный код числа А:, от которого необходимо сформировать остаток по заданному модулю Р, подается на информационный вход 15. Одновременно на вход 16 запуска устройства поступает управляющий сигнал, который открывает коммутатор 12 и через элемент.ИЛИ 2 и элемент 10 задержки воздействует на тактовыи вход второго регистра 11, на информационные входы которого с выхода коммутатора 12 поступает код числа А„, в результате чего код последнего записывается в регистр 11. Код числа с выхода второго регистра 11 поступает на входы первых операндов группы вычитателей 3, в результате чего на выходах последних образуются разностные коды А„ — const 1, А — const 2, ..., А„— constn. Там, где эти разностные коды меньше значении констант, на выходах «Меньше» блоков 6 сравнения первой группь1 появляются управляющие сигналы, там, где эти разностные коды больше значений констант, управляющие сигналы появляются на выходах «Больше».

Так как значения констант рассчитаны по формуле (1), то код разности либо равен нулю, либо может попасть в промежуток между рядом расположенными константами.

Если код разности равен нулю, то срабатывает соответствующий блок 8 сравнения второй группы, сигнал с выхода которого через элемент ИЛИ 13 поступает на выход 4

159454!

10 форму>га изобретения

20

30 устройства, сигнализируя о том, что на выходе 9 сформирован остаток r=A„modP=O, а также устанавливает второй регистр l l в нулевое состояние. Если код разности не равен нулю, то в промежутке между рядом расположенными константами i-й блок 8 сравнения первой группы выдает сигнал

«Меньше», à (i+1)-й блок 6 сравнения первой группы выдает сигнал «Больше», следовательно, срабатывает i-й элемент И 7 группы, сигнал с выхода которого включает соответствующий коммутатор 5 группы, а через элемент ИЛИ 2 и элемент 10 задержки обеспечивает запись кода Ак — const г в регистр 11. Этот процесс продолжается до тех пор, пока (А„— const г — const — const,n) (const гг= — Р. В - том случае последний блок 6 сравне-!vÿ первой группы

Выдает cHГнал «1> сньше>>, !10торый ОткрыВ3ет последний I(o;>Iь!ут3тОр 5 Гpi nits, 33 IHсывает код Г=АгпоЙР в первый регистр !, через элемент ИЛИ 3 воздействует на второй (управляющкй; выход устройства, сигнализируя об окончании процесса формирования остатка, а -,àêæ:å обнуляет содержимое второго регистра 11. Код остатка остается на информационных выходах устройства до тех пор, пока на информационные входы 15 не поступит следующее число А„+1, от которого необходимо сформировать остаток, а на вход !6 — сигнал запуска. Ip« этом работа устройства осу;цествляется аналогично описанному выше.

Пример. Выполнение процесса свертки по модулю.

Пусть А„,.„,= 1000; Р=7. Необходимо сформировать остаток для А„=999. Тогда

1000 число констант n=! Iogg — !=8. Значения

7 констант в соответствии с (1) равны:

const 1 =504; const 2=252; const 3= 126;

const 4=63; сопИ 5= — 42; const 6= 21;

const 7=14; const 8=7. Тогда после записи кода числа 999 в регистр 11 на выходах группы вычитателей 3 образуются коды: первого — 495; второго — 747; третьего — 873; четвертого — 936; пятого — 957; шестого—

978; седьмого — 985; восьмого — 992. Поэтому на выходе только первого блока 6 сравнения первой группы появляется сигнал

«Меньше» (495(504), а на выходах остальных блоков 6 сравнения появляется сигнал

«Больше». Следовательно, на первом цикле работы устройства в регистр 11 записывается код числа 495.

На втором цикле работы на выходах вычитателей 3 формируются коды следующих чисел: первого — 9; второго — 243; третьего — 369; четвертого — 432; пятого — 453; шестого — 474; седьмого — 481; восьмого—

488. Поэтому в результате сравнения со своими константами срабатывает второй эле35

55 мент И 7 гр ппы (243(252 и 369)126) и в регистр 11 з;-:!гисывается код числа .43, затем в регистр 11 последовательно -.àïnсываются коды чисел 1 7; 54; 2 и, наконец, 5

Поэтому Н3 шестом цикле работы последний блок 6 ср-внения первой группы выдает сигнал «Меньше», в результате чего код числа

«5» записывается в регистр 1 и поступает на информационный вь|ход устройства.

Устройство для свертки по произвольному модулю, содержащее группу вычитателей, две группы блоков сравнения, Группу элементов И, группу коммутаторов, первый регистр ., первый элемс г; I IЛИ„причем входы

ПЕРВОГО Ol ICP3 НД3 В 1 1 liT3TCЛС и Г!Р !1 и Ы ПОД ключсны к соотвс с ВУ101ц!!.; Входа и за !,як:::1

КОНСT31iT ВЫ -IIIТ11НИЯ УСТРОЙ» . Ва, ВЫХОДЬ1 зуль|атг вычитателей группы соединены с первыми информационными зходами соответст11;:ю цих блоков сравнения первой и второй груlili I» с информационными входами соответствчющих коммутатороВ Гp) !Iны, ВToрые ннформац;гонные входы блоков сравнения второй группы подключены к шине нулевого потенциала устройства, выход «Меньше» каждого i-го блока сравнения первой группы соединен с первым входом i-го элемента И группы (1(i((n — 1, где тг=)!Оог)(А,...,. — наибольшее контролируемое число; Р— значение модуля свертки) выход первого регистра является информ;1цконны>! Выходом устройстВа, От>г!! жюгг еееч гсм, что, с целью сокращения апп;!ратурных затрат устройства, оно содержикоммутатор, элемент задержки, второй р«гистр и второй элемент ИЛИ, причем информационный вход коммутатора является информационным входом устройства, вьгход коммутатора и выходы коммутаторов группы кроме последнегo, объединены llo схеме

МОНТАЖНОЕ ИЛИ и соединены с информационным входом второго регистра, выход последнего коммутатора груillli l соединен с информационным входом первого регистра, выход каждого i-го элемента И группы соединен с управляющим входом i-го коммх:Т3ТОР3 ГР ППЫ И i-и ВХОДОМ IICPBOi O ЭЛЕМЕ1-: .. 1

ИЛИ, выход ко — îðîãî через элемент задержки соединен с тактовым входом второго регистра, выход которого соединен с входами второго операнда вычитателей группы, выход «Больгпе» каждого (i+1) -го блока сравнения первой группы -оединен с вторым входом г-го элемента И группы, выходы равснства блоков сравнения второй группы и выход «Меньше» последнего блока срагнсния первой группы соединень1 с соответствующимк входами второго элемента ИЛИ, Выход которого соединен с установочным вхо! 594541

i осгавитель В. Гречнев

Редактор В. Петраш Те;цн д А. Кравчук Корректор А. Обручар

Заказ 2830 Тираж 568 Подписное

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

1!3035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат «Патент», r. Ужгород, ул. Гагарина, !О! дом второго..регистра и является выходом признака завершения свертки устройства, вход запуска устройства подключен к управляющему входу коммутатора, установочному входу первого регистра и (i+1)-му входу первого элемента ИЛИ, выход «Меньше» последнего блока сравнения первой группы соединен с управляющим входом последнего коммутатора группы и тактовым входом первого регистра.