ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ СТРУКТУР ЛОГИЧЕСКИХ СХЕМ Советский патент 1974 года по МПК G06F7/06 G06F7/38 

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

Известна опециализированиая вычислительная машина для минимизации логических функций, реализующая алгоритм, разработанный профессором Гавриловым М. А., .известный 1ПОД названием метода перебора Гаврилова М. А. Алгоритм дозволяет находить общую |МИИИ.мальную фор/му логической функции с помощью специал.изированной или универсальной вычислительной машины. Такая вычислительная мащина должна содержать запоминающее устройство большой емкости, предназначенное для хранения программы .и iBcex возможных минимальных членов логической функции, число которых для функции 10 переменных превышает 4300. Кроме того, она содержит достаточно сложное устройство ввода исходных данных, устройство управления и операционное устройство. Все это определяет ее высокую стоимость и низкую экономичность.

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

вернуться и подобрать новую часть обобщенного кода, при которой погаснет лампоч-ка «Запрет.

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

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

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

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

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

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

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

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

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

Блок управления / содержит два счетчика 7 л 8, дешифратор 9, логическую схему «ИЛИ ТО и логические схемы «И 11.

Он предназначен для формирования управляюш..их сигналов, синхронизирующих работу всех узлов эычи|СЛ(Ите,льного устройства.

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

Логический блок 5 обеспечивает лоразрядное Сравнение запрещенных ,и рабочих чисел И форм1ирование призна1ка совпадения значений разрядов запрещенных л рабоч,их чисел с учетом .информации, -полученной на предыдущ.их Шагах решевия задачи минимизации логической функци.и. Кроме того, логический блок обеспечивает формирование и выдачу сигналов в блок ин1ди«аци,п .и регистрации 6.

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

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

Для решения задачи определения полной совокупности простых импл.икант на наборном поле 6 через ввод задаются все запрещенные числа логической функции, описывающей структуру миним изируемой логической схе(МЫ. Б логический блок 3 через ввод задается одйю 1ИЗ рабочих чисел, характеризующих логическую функцию.

При решении зацачи онределения простых имплицент логической функции на наборн-эм ттоле 5 задаются все рабочие числа млшимизируемой логической функции, а IB логический блО|К 3 1ВВОД1ИТСЯ ОДио из запрещенных чисел. На счетчик 7 блока управления 1 послздавательно поступают импульсы через ввод. Выходы счетч.ика 7 подключены ко входам дешифратора 2 и логического блока 3. В соответстви.и с сигналами, поступающими со счетчика 7, дешифратор 2 последовательно опрашивает ячейки наборного поля 5. При олределении ячейки наборного поля 5, сод-ержащей запрещенное (рабочее) число логической функции, дешифратор 2 формирует призна.к совпадения номера запрещенного (рабочего) числа и выходов счетчика 7. ;По этому признаку в логический блок 3 производится сравнение разрядок рабочего и запрещенного чисел и формир-уется признак совпадения значений разрядов чисел за исключением первого.

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

di uibi + dib: (i 1,2, ...,n), пц , ds, ... ,dn,

где ui, ui - прямое и инверсное значение J-го разряда запрещенного (ра бочего) чпсла;

fc,, bi - прямое и инверсное значение г-го разряда рабочего (запрещенного) чИСла;

d-i - признак совпадения значений t-bi,x разрядов рабочего и запрещенного чисел;

mi - признак совпадения всех рязрядов рабочего и запрещенного чисел за исключением первого.

Аналогично производится процесс поразрядиого сравнения всех запрещенных (рабочих) чисел с в/веденным в логический блок

рабочим (запрещенным) числом. Если в логическом блоке 3 получен признак совпадения т, то на его выходе формируется сигнал, который поступает через схему «ИЛИ 10 на вход счетчиКа 8, а также устанавливает счетчик 7 в исходное состояние. Если в логическом блоке 3 в результате поразрядного сравнения всех запрещенных (рабочих) чисел с введенным рабочим (запрещенным) числом признак совпадения Ш не получен, то

импульс поступает через схему «ИЛР1 W .на вход счетчика S, о-дноаременно воз:вращает в исходное состояние счетч.ик 7 и записывает единицу в первый разряд регистра 4, соответствующий первому разряду рабочего (запрещенпого) числа. Нлиничное состояние разряда регистра 4 означает, что среди рабочлх (запрещенных) ил.и условных чисел находится число, все разряды кото,рого, кроме первого, совпадают с соответствующ.ими разрядам-и введенного в логический блок 3 рабочего (запрещенного) числа, и это число склеено с .исходным рабо4HiM (запрещенным) числом. Если (В логическом блоке 3 в результате поразрядного сравнен.ия ,всех запрещенных (.рабочих) ч,исел с введенным рабочим (запрещенным) числом получен признак совпадения (первый разряд регистра 4 останется в нулевом состоянии). Это означает, что число, отличающееся от введенного в логический блок 3 ра-бочего (запрещенного) числа значением только первого разряда, находится среДгИ запрещенных (рабочих) чисел наборного поля 5 ,и, следовательно, не может быть с ним склеено. В результате записи в счетчик 8 блока управлеиня 1 дещифратор 9 формирует сигнал, поступающий iB логический блок 3 и устанавливающий новый сравнения, при котором определяется совпадение всех разрядов рабочих и запрещенных ч.исел, кроме второго. После этого на счетчик 7 блока управления / поступает новая серяя .импульсов через В1ВО.Д. При этом работа устройства аиалогич-на описанной выше. Логический блок 3 в этОМ цикле реализует логические формулы: rf, + aib| + Yi, dj uibi + a ibi (i 2, 3, ..., n), m2 t/b dz, Й4, . ..,/„, где YI - значение nepiBoro разряда регистра 4. Процесс поразрядного сравнен.ия рабочих и запрещенных чисел повторяется п раз (проводится для каж.дого разряда), в результате чего в .разрядах регистра 4 записывается информация о всей группе рабочих (запрещенCPiSB.f ных) лли условных чисел, которые склеены с веденным рабочим (запрещенным) числом. Па оснозан.ии значений разрядов регистра 4 н введенного рабочего (запрещенного) числа логическим блоком 5 формируется соответстующая простая импликанта (имплицента), которая отображается на блоке индикации и регистрации 6. После приведения схемы в исходное состояние IB логический блок 3 вводится нозое рабочее (запрещенное) число, и повторяется цикл определения простой им1пликанты (импдиценты), соответствующей данному числу. Такая процедура проделывается до тех пор, пока не будут обслужены все рабоч; е (запрещенные) числа, описывающие условия фун.кционирования минИМиз.ируемой логической схемы. ПалиЧ.ие в предлагаемом устройстве связей между входами и выходами блока управления, .регистра и логического блока обеспечи.вает авто.матический режим работы устройства в процессе определения простых импликант (имплицент) логической функции для заданного рабочего (запрещенного) числа. Результаты макетирования и испытаний подтверждают работоспособиость устройства, его высокое быстродействие, малые габариты и удобство работы с ним. Предмет изобретения Вычислительное устройство для .миним1изации структур логическ1 х схем, содержащее логический блок, вход которого подключен к дешифратору, а выход - ;К блоку .индикации и регистрации, и-наборное поле, соединенное двухсторонней связью с дещифратором, отличающееся тем, что, с целью повыщения быстродействия, оно содержит регистр .и блок управления, первые вход и выход которого соедииены с лог.ическим блоком, второй выход блока управления подключен к логическому блоку и дешифратору, а третий через регистр - к логическому блоку.