Устройство для сравнения кодов

 

Издбретение может быть использовано при реализации технических средств ЭВМ и специализированных устройств, решающих комбинаторные задачи, задачи анализа сетей методами теории графов, .задачи оценки надежности структурно-сложных систем, задачи сравнения и преобразования форм представления буровых функций, а также определения булевых дифференциалов . Целью изобретения является расширение области применения путем обеспечения возможности определения факта равенства логической единице любой булевой функцг-ш, заданной дизъюнктивной нормальной формой (ДНФ), на принятом наборе переменных. Устройство содержит входной регистр 1, группу регистров 2 и 3 кода, группы элементов ИЛИ 4-6, группу злементов И 7, элемент ИЛИ 8. 1 ил. 2

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

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

РЕСПУБЛИК

09) (11) Al. дц 4 С 06 F 7/04

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

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

ПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЧМ

ПРИ ГКНТ СССР

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4286019/24-24 (22) 20.07.87 (46) 07.03.89. Бюл. У 9 (72) В.М.Полищук и Н.Н.Шубина (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР

У 1097997, кл. G 06 F 7/00, 1983.

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

Ф 1251068, кл. С 06 F 7/04, 1985. (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ КОДОВ (57} Изобретение может быть использовано при реализации технических средств ЭВМ и специализированных устройств, решающих комбинаторные задачи, задачи анализа сетей методами теории графов, .задачи оцецки надежности структурно-сложных систем, задачи сравнения и преобразования форм представления буровых функций, 1 а также определения булевых дифференциалов. Целью изобретения является расширение области применения путем обеспечения возможности определения факта равенства логической единице любой булевой функции, заданной дизьюнктивной нормальной формой (ДНФ), на принятом наборе переменных. Устройство содержит входной регистр 1, группу регистров 2 и 3 кода, группы элементов ИЛИ 4-6, группу элементов

И 7, элемент ИЛИ 8, 1 ил, 1464 154

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

Цель изобретения — расширение области применения за счет обеспечения 15 возможности определения факта равенства логической единице любой булевой функции, заданной ДНФ на принятом наборе переменных., На чертеже представлена схема уст- 20 ройства.

Устройство содержит входной регистр 1, первую и вторую группы регистров 2 и 3 кода, группы элемен-, тов ИЛИ 4-6, группу элементов И 7, элемент ИЛИ 8, вход 9 и выход 10.

Устройство работает следующим образом.

Элементарная конъюнкция ранга

r m (рангом называется количество

30 переменных Х; кодируе.тся двумя двоичными m-ðàçðÿäíüïÿ кодами А (а<,..., где а;, b; E (1,,0), причем для всех

Х, не содержащихся =-, =-лементарной 35

1 конъюнкции, и только для них в i-x разрядах кода А за.писывается "1" и в остальных разрядах "О", а для всех

Х; - a i õ разрядах кода В записывается "0" и в остальных разрядах

1 . Например„ элементарная конъюнкция Х„Х Х при m = 5 будет представлена кодами А (01001) и В (11011) .

При таком способе кодирования определение факта поглощения элемен- 45 тарной конъюнкциеи принятого набора переменных Х (Х,,..., Х;,...,Х ), где

Х„= 0 или 1 (з = 1, n) осуществляется проверкой следующего условия

lTl щ ъ

/ (/ а; Х;) = A, (V Ь, Х, ) = 1

1=

В исходном состоянии каждая элементарная конъюнкция заданной функции,представленная кодами А и В, - 55 записывается в регистры 2 и 3 соответственно. Незадействсванные регистры 2 и 3 (не содержащие элементарных конъюнкций) должны быть обнулены.

Идентифицируемые наборы в процессе проверки заносятся поочередно во входной регистр 1. Значащие разряды проверяемых наборов в регистре 1 могут варьироваться только в пределах значения К (К c m), где К вЂ” количество переменных заданной булевой функции. На выходе 10 устройства логическая "1" будет сформирована лишь в том случае, если проверяемый набор поглощается хотя бы одной из элементарных конъюнкций из заданных в регистрах 2 и 3.

Действительно, если проверяемый набор поглощается данной элементарной конъюнкцией, то на выходах всех элементов ИЛИ 4-6, связанных с регистрами, содержащими коды А и В данной элементарной конъюнкции, будут единичные сигналы, что обеспечивает формирование единичного сигнала на выходе элемснта И. 8 и выдачу его через элемент ИЛИ 7 на выход 10 устройства.

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

Устройство для сравнения кодов, содержащее входной регистр, первую группу из и регистров кода, где и максимально возможное количество сравниваемых кодов, и групп по ш двухвходовых элементов ИЛИ, где т количество разрядов сравниваемых кодов, группу из и элементов И, элемент ИЛИ, группу из п-, m-входовых элементов ИЛИ, причем информационный вход устройства соединен с информационным входом входного регистра, прямой выход -го разряда которого, где i = 1,2...,m соединен с первыми входами всех i --х двухвходовых элементов ИЛИ всех групп, инверсный выхор i-ro разряда j-го регистра кода первой группы, где 1 = 1,2;...,и, соединен с вторым входом i-го двухвходового элемента ИЛИ 1-й группы, выход которого соединен с i-M входом

j-ro элемента И группы, выход которого соединен с j-м входом элемента

ИЛИ, выход которого является выходом устройства, выход j --ro m-входового элемента ИЛИ группы соединен с (m+1)-м входом j--o элемента И группы, о т л и ч а ю щ е е с я тем, что, с цельк расширения области применения за счет обеспечения возможности определения факта равенства логичес1464154

Составитель В.Горохов

Редактор Н.Яцола Техред Л.Олийнык Корректор В.Романенко

Заказ 825/51 Тираж 667 Подписное

Ю ю

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

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

Производственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 101 кой единице любой булевой функции, заданной .ДНФ на принятом наборе переменных, в него введена вторая группа из и. регистров кода и и групп по

m двухвходовых элементов ИЛИ, причем инверсный выход i-гд разряда входного регистра соединен с первыми входами i-х двухвходовых элементов ИЛИ групп с (и+1)-й по 2п-ю, прямой выход i-ro разряда j-ro регистра кода второй группы соединен с i-м входом

j-ro m-входового элемента ИПИ группы и с вторым входом i-Fo двухвходового элемента ИЛИ (В+))-й группы, выход которого соединен с (m+1+i)-м входом

j-го элемента И группы.