Вычислительное устройство для минимизации структур логических схем

 

ОПИСАНИЕ «>428З87

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ в ВИДЕ1еЕВЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 31.03.72 (21) 1766399/18-24 с присоединением заявки Ме— (32) Приоритет—

Опубликовано 15,05.74. Бюллетень М 18

Дата опубликования описания 02.06.75 (51) М. Кл. G 06f 15/34

Государственный комитет

Совета Министров СССР (53) УДК 681.142 (088.8) пв делам изобретений и открытий (72) Авторы изобретения

И. П. Барбаш, В. В. Безбоков, Г. Н. Тимонькин и С. Н. Ткаченко (71) Заявитель ст (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ

МИНИМИЗАЦИИ СТРУКТУР ЛОГИЧЕСКИХ СХЕМ

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

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

;всех возможных минимальных членов логической функции, число которых для функции 10 .переменных превышает 4300. Кроме того, она содержит достаточно сложное устройство ввода исходных данных, устройство управления .и операционное устройство. Все это определяет ее высокую стоимость и низкую эконом,ич.ность.

Известна вычислительная машина для минимизации структуры логических схвм, реализующая алгоритм„разработанный профессором Мавренковым Л. Т. на основе обобщенных кодов, оператора свертьгвания и,графической свертки. Недостатками втокио устройства являются низкое быстродействие, а также за дача отыскан,ия простой импликанты (обобщенного ко да) решается оператором вручную IlO группам из трех логических переменных (триадам) на основании анализа,информации, получаемой с лампочек решетокдешифраторов обобщенных колов, При этом, если в процессе определения импликанты (оообщенного кода) в состав рабочих и условных на боров логической функции оператор ошибочно включит одно или несколько запрещенных наборов, то на основании информации, получаемой с табло, информации (загорается ла мпоч ка «За прет»), оператор должен вернуться,и подобрать новую часть обобщенного кода, при которой погаснет лампочка

«3 апрет».

Аналогичные действия должен выполнить оператор при определении следующих частей обобщенного кода, соответствующих остальным триадам логических переменных.

Успех решения задачи минимизации с помощью этой машины существе и но за висит от опыта и внимания оператора, так как в противном случае он может выбрать неоптимальное решение, т. е. обобщенный код, не соответствующий простой импликанте.

Известны,и другие устройства для анализа и синтеза оптимальных структур логичеЗО ских схем, однако они не позволяют опреде42S3S7 лять простые импликанты (1гмплиценты) логических функций.

Предлагаемое вычислительное устройство для минимизации структур логических схем отличается тем, что оно содержит регистр и блок упра1вленпя, первый зхэд которого соединен с,выхсдо..! генератора импульсов (»a чертеже не указан), а первый выход соединен с:первым входом ".эг::: =" кого блока, второй вход которого соединен через рег!1стр со вторым выходом блока управления, третий вы;ход которого соединен с дешнфратором и логическим блоком, выход которого соединен со .вторым входом блока управления.

Это позволяет автоматически определять простые,импликанты (имплиценты) логических функций при минимизац1ги структур логичес,ких схем.

Преимущест1вамн предлагаемого устройства являются полная автоматизация процесса определения простых имплнкант (имплицент) логических функций, вследствие чего роль оператора сводится только к ввэду исходных данных, высокое быстродействие и исключение субьект!!нных ошиоок оператора, которые могут быть допущены при участии последнего в процессе решения задачи .и анализа ïðîмежуточнык результатов.

На фиг. 1 представлена блок-схема; на фиг, 2 — функциональная схема предлагаемого устройства.

Вычислительное устройство состоит из блока управления 1,,дешнфратора 2, логического блока 3, регистра 4, наборного поля 5 и блока, индикации и регистрации 6.

Блок упра вления 1 содержит два счетчика

7 и 8, дешифратор 9, логическую схему

«ИЛИ» I0 и логические схемы «И» 11.

Он предназначен для формировашгя управляющих сигналов, с1цгхронизирующнх работ у всех узлов вычи сл,1!тельного устройства.

Дешифратор 2 служит для последовательного опроса ячеек наборного поля 5 и формирования признаков запрещенных (рабочих) чисел, заданных на наборном поле по условиям решаемой задачи.

Лотический блок 8 обеспечивает,поразрядное сравнение,запрещенных:и рабочих чисел и формирование признака совпадения значений разрядов запрещенных,н рабочих чисел с учетом .информации, полученной на предыдущих шагах решения задачи минимизации логической функции. Кроме того, логический блок обеспечивает формирование и,выдачу сигналов в блок ин дикацип .и регистрации 6.

Регистр 4 служит для приема и хранения информации, получаемой на предыдущих шагах решения задачи ми!.нмизации логической функции.

Рассмотрим работу предлагаемого вычислительного устройства для минимизац1111 структур логических схем.

Для решения задач 1 определения полной совокупности простых импликант на наборном поле,5 через ввод задаются все запрещенные числа логической функции, описывающей структуру минимизируемой логиче кой схемы. В JIOTH÷åoêèI"! блэк 8 через ввод задается одно 1из,рабо !11х чисел, характеризующих логическую функцию.

При решении за!дачи определения про "т.1х имплицент логической функции на набораo.4 поле 5 задаются все раоочие числа мпннм::1зируемой логической функции, а !в лэгиче",;нй блок 3 вводится одно из запрещенных чисел.

На счетчик 7 блока управления 1 пэслздoaàòåëüío поступают импульсы чер з зв" д.

Выходы счетчлка 7 подключены ко вхэдам !

5 дешифратора 2 и логического блэка 8, В соответствии с сигнала !и, поступающими со счетчика 7, дешифратор 2 последэвательно опрашивает ячейки наборного поля 5. Hp,! определении ячейки наборного поля 5, oîäåp 1> жащей запрещенное (рабочее) число логической функции, дешифратор 2 формирует признак совпа1дения номера запрещенногэ (рабочего) числа и выходов счетчика 7. Пэ этому признаку в логический блок 8 производится сравнение разрядок раоочего и запрещенно:o чисел и формируется признак совпадения значений,разрядов чисел за исключением пер.вого.

Функционирование логического блока на этом шаге определяется логическимп формулаа,м.и:

d„= a;b; +а;6; (i =1,2, ...,и), 1)2I =- 4, 1з,,а„, где а;, а; — прямое и инверсное значение

i-го разряда запрещенного (раоочего) числа;

Ь;, Ь; — прямое и инверсное значение

1-го разряда рабочего (запрещенпо 1-о) числа;

d, — признак совпадения значег1ий

1-ых разрядов рабочего и запрещенного чисел; и! — признак совпадения всех рязря45,дов,рабочего и запрещенного чисел за исключением первого.

Аналогично производится прэцес: поразрядного сравнения всех запрещенных (раоочих) чисел с в!веденным в логический блок рабочим (запрещенным) числом. Если в логическом блоке 8 получен признак совпадения и1, То на его выходе формируется сигнал, который поступает через схему «ИЛИ» 10 на вход счетчика 8, а также устанавливает счет55 чик 7 в,исходное состояние. Если в логическом блоке 8 в результате поразрядного сравнения всех запрещенных (рабочих) чисел с введенным рабочим (запрещенным) ".1!ñëoì признак сов падения и! пе получен, тэ 2"-ый

6О импульс поступает через схему «ИЛИ» 10 .на вход счетчика 8, одновременно возвращает в исходное состояние счетчик 7 и записывaåò единицу .в первый разряд регистра 4, соответствующий первому разряду рабочего (запрещенного) числа.

428387 т

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

Если !в логическом блоке 8 в результате поразрядного сравнения всех запрещенньгх (рабочих) чисел с введенным рабочим (запрещенным) числом получен признак совпадения (первый разряд регистра 4 останется н нулевом состоянии). Это означает, что число, отличающееся от введенного в логический блок 8 рабочего (запрещенного) числа значением только первого разряда, находится среди запрещенных (рабочих) чисел наборного поля 5,И, следовательно, не может быть с ним склеено.

В результате записи в счетчик 8 блока управления 1 дешифратор 9 формирует сигнал, поступающий в логический блок 8 и устанавливающий новый режим сравнения, при котором определяется совпадение всех разрядо!в рабочих и запрещенных чисел, кроме !Второго.

После этого на счетчик 7 блока управления 1 поступает новая !серия,импульсов через в!вод. Пр1и этом работа устройства аналогична описанной выше. Логический блок 8 в этом цикле реализует логические формулы;

dl — — а,b, -+ аггг! + уг, d, = айаг + а;Тг; (г = 2, 3, ..., п), m2,d1,,d3,,a,4„ ° .° .° .,d„ где у! — значение первого разряда регистра 4.

Процесс поразрядного сравнения рабочих и запрещенных чисел повторяется п раз (проводится для каждого разряда), в результате чего в,разрядах, регистра 4 записывается информация о всей группе рабочих (запрещенII!IN);!.-iи услов:гых чисел, которые склеены „" !

Введе:!Ным рабочим (запрещенным) ч:!слом.

На оснозан,нн значений разрядоз ре":êòðà 4 .и введе-шого рабочего (запрещенного) ч !сля логическим блоком 8 формируется соответствуюц,ая простая импликанта (пмплицента), которая Отооэажается на блОке !1нднкацип и ,регистрации 6.

После !приведения схемы в исходное со-!

О стояние !з логический блок 8 вводится нозo3 рабочее (запрещенное) число, и повторяется ци!кл огпределения простой им!пликанты (имплиценты), соответствующей дан! ому числу.

Такая процедура проделывается до тех !

5 по р, пока не оудут оослужены,в"e рабэч le (запрещенные) числа, оп!!сы!Вающие условия функционирования минимизируемой логической схемы, Наличие в предлагаемом устройстве свя20 з зей между входами и выходамп блока управления,,регистра и логического блока ооеспе lllвает автоматический режим работы устройсгва в процессе определения простых нмплнкант (имплицент) логической функции для

23 заданного рабочего (запрещенного) числа.

Результаты макетирования и испытаний подтверждают работоспособность устройства

Э

e1 o высокое быстродействие, малые гаоариты и удобство раооты с н!Их!.

Предмет изобретения

Вычислительное устройство для з!Нн!!м!!зации структур логическ!1х схс. 1, содержа!цее

35 логический блок, вход которого подключен к дешифратору, а зы: од — к олоку индикации и регистрации, и. наборное поле, соединенное двухсторонней связью с дешнфратором, от.гичаюигееся тем, что, с целью повышения оысг40 родейстзия, оно содержит регистр и блок управления, первые !вход и выход которого соединены .с логическим блоком, второй

ВыхОд Олока управления подключен к логическому блоку н дешифратору, а третий через

45 регистр — к логическому блоку.

428387

Фиг. 2

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

Техред Т. Курилко

Редактор Е. Семакова

Корректор В. Гутман

Заказ 63/385 Изд. Ко 1577 Тираж 624 Подписное

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

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

Тнп. Харьк. фил. пред. «Патент»