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

О П И С А Н И Е ( )428387ИЗОБРЕТЕНИЯ Союз Советских Сониалистических РеспубликК АВТОРСКОМУ в.ВИДЕ 1 еЕЯЬСТВУ висим от авт. свидетельства М. Кл. 6 061 15/3 2) Заявлено 31.03,72 (21) 1766399/18-24 м заявки Мо -исоединен тосударствекиык комитет Совета Министров СССР) Приоритетубликованота опублико 15,05.74. Бюллетень Уе вания описания 02.06,75 К 681.14 (088.8 в делам изобретении и открытий(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ МИНИМИЗАЦИИ СТРУКТУР ЛОГИЧЕСКИХ СХЕИзвестны вычислительные устройства для минимизации структур логических схем, содержащие логическое устройство, дешифратор, наборное поле и устройство индикации,Известна специализированная вычислительная машина для минимизации логических функций, реализующая алгоритм, разработанный профессором Гавриловым М. А., известный под названием метода переоора Гаврилова М. А. Алгоритм позволяет находить общую минимальную форму логической функции с помощью специализированной или универсальной вычислительной машины. Такая вычислительная машина должна содержать запоминающее устройство большой емкости, предназначенное для хранения программы,и ;всех возможных минимальных членов логической функции, число которых для функции 10 переменных превышает 4300. Кроме того, она содержит достаточно сложное устройство ввода исходных данных, устройство управления ,и операционное устройство. Все это определяет ее высокую стоимость и низкую эконом,ич.ность.Известна вычислительная машина для минимизации структуры логических схвм, реализующая алгоритмразработанный профессором Мавренковым Л. Т. на основе обобщенных кодов, оператора свертьгвания и,графической сверточки. Недостатками втокио устройства являются низкое быстродействие, а также задача отыскан,ия простой импликанты (обобщенного кода) решается оператором вручную по группам из трех логических переменных (триадам) на основании анализа,информации, получаемой с лампочек решетокдешифраторов обобщенных колов, При этом, если в процессе определения импликанты (оообщенного кода) в состав рабочих и условных наборов логической функции оператор ошибочно включит одно или несколько запрещенных наборов, то на основании информации, получаемой с табло, информации (загорается лампочка Запрет), оператор должен вернуться,и подобрать новую часть обобщенного кода, при которой погаснет лампоч,ка 3 апрет.Аналогичные действия должен выполнить оператор при определении следующих частей обобщенного кода, соответствующих остальным триадам логических переменных.Успех решения задачи минимизации с помощью этой машины существевно зависит от опыта и внимания оператора, так как в противном случае он может выбрать неоптимальное решение, т. е. обобщенный код, не соответствующий простой импликанте.Известны,и другие устройства для анализа и синтеза оптимальных структур логических схем, однако они не позволяют определять простые импликанты (1 гмплиценты) логических функций.Предлагаемое вычислительное устройство для минимизации структур логических схем отличается тем, что оно содержит регистр и блок управленця, первый зхэд которого соединен с,выходом генератора импульсов (нд чертеже не указан), а первыц выход соединенпервым вхэдо лдгцческсгэ олскд, второЙ вход которого соединен через регистр со вторым выходом блока управления, третий вы;ход которого соединен с дешцфратором и ло. гическим блоком, выход которого соединен со .вторым входом блока управления.Это позволяет автоматически определять простые,импликанты (имплицецты) логических функций прц минимизацги структур логичес,ких схем.Преимуществами предлагаемого устройства являются полная автоматизация процесса определения простых импликант (имплицент) логических функций, вследствие чего роль оператора сводится только к вводу исходных данных, высокое быстродействие и исключение субьективных ошиоок оператора, которые могут быть допущены при участии последнего в процессе решения задачи и анализа промежуточньйс результатов.На фиг. 1 представлена блок-схема; на фцг, 2 - функциональная схема предлагаемого устройства.Вычислительное устройство состоит из блока управления 1 дешцрратора 2, логического блока 3, регистра 4, наборного поля 5 ц блока, индикации и реп 1 страцци 6.Блок управления 1 содержит два счетчика 7 и 8, дешифратор 9, логическую схему ИЛИ 10 и логические схемы И 11.Он предназначен для формцровашгя управляющих сигналов, спгхронцзирующцх работу всех узлов вычцслит:льного устройства.Дешифратор 2 служит для последовательного опроса ячеек наборного поля 5 и формирования признаков запрещенных (рабочих) чисел, заданных на наборном поле по условиям решаемой задачи.Логический блок 3 обеспечивает,поразрядное сравнение,запрещенных:и рабочих чисел и формирование признака совпадения значений разрядов запрещенных,ц рабочих чисел с учетом, информации, полученной на предыдущих шагах решения задачи минимизации логической функц 11 ц. Крохе того, логический блок обеспечивает формирование и,выдачу сигналов в блок индикаццп,и регистрации 6.Регистр 4 служит для прцеиа и хранения информации, получаемой на предыдущих шагах решения задачц мц 1;цм 1 здции логической функции.Рассмотрим работу предлагаемого вычислительного устройства для минлмизаццц структур логических схем.Для решения задачи определения полной совокупности простых импликант на наборном поле 5 через ввод задаются все запрещенные числа логической функции, описывающей структуру минцм 11 зируемэй логиче койсхемы. В логический блэк 3 через ввод зада 5 ется одно из рабочих чисел, характеризующихлогическую функцию.При решении задачи определения про"т химплицент логической функции на наборномполе 5 задаются все раоочие числа мцню 11 о зируемой логической функции, а в лэгцче"к .йблок 3 вводится одно из запрещеняых чисел.На счетчик 7 блока управления 1 последовательно поступают импульсы через зв"д.Выходы счетчика 7 подключены ко входам5 дешифратора 2 и логического блэка 3, В соответствии с сигнала 11, поступающими сосчетчика 7, дешцфратэр 2 последэвательноопрашивает ячейки наборного поля 5. Прцопределении ячейки наборного поля 5, содер 21 жащей запрещенное (рабочее) число логической функции, дешифратор 2 формирует признак совпадения номера запрещенногэ (рабочего) числа и выходов счетчика 7. Пд этомупризнаку в логический блок 3 производится25 сравнение разрядок раоочего ц запрещенногэчисел и формируется признак совпадения значений,разрядов чисел за исключением первого,Функционирование логического блока наЗо этом шаге определяется логическимц формула,ми:д= а;Ь, + а, Ь; ( = 1,2, , и),111112 13 )1где а;, а; - прямое и инверсное значение-го разряда запрещеннэгс (рдоочего) числа;Ь;, Ь; - прямое и инверсное значениеК-го разряда рабочего (запрещений с) числа;сУ; - признак совпадения зндчег 1 цй1-ых разрядов рабочего и запрещенного чисел;и, - признак совпадения всех рязря 45 дсв,рабочего и запрещенногд чисел за исключением первого.Аналогично производится процесс поразрядного сравнения всех запрещенных (рабочих) чисел с введенным в логический блок рабочим (запрещенным) числом. Если в логическом блоке 3 получен признак совпадения и то ца его выходе формируется сигнал, который поступает через схему ИЛИ 10 навход счетчика 8, а также устанавливает счет чцк 7 в,исходное состояние. Если в логическом блоке 3 в результате поразрядного сравнения всех запрещенных (рабочих) чисел с введенным рабочим (запрещенным) числом признак совпадения и, пе получен, тд 2"-ый 5 О импульс поступает через схему ИЛИ 10 навход счетчика 8, одновременно возвращает в исходное состояние счетчик 7 ц записывает единицу в первый разряд регистра 4, соответствующий первому разряду рабочего (запре щенцдго) числа,428387 ас. тЕдиничное состояние разряда регистра 4 означает, что среди рабочих (запрещенных) или условных чисел находится число, все разряды которого, кроме первого, совпадают с соответствуюцими разрядами введенного в логический блок 3 рабочего (запрещенного) числа, и это число склеено с,исходным рабочигм (запрещенным) числом,Если в логическом блоке 3 в результате поразрядного сравнения всех запрещенньгх (рабочих) чисел с введенным рабочим (запрещенным) числом получен признак совпадения (первый разряд регистра 4 останется н нулевом состоянии). Это означает, что число, отличающееся от введенного в логический блок 3 рабочего (запрещенного) числа значением только первого разряда, находится среди запрещенных (рабочих) чисел наборного поля 5,и, следовательно, не может быть с гз склеено. В результате записи в счетчик 8 блокауправления 1 дешифратор 9 формирует сигнал, поступающий в логический блок 3 иустанавливающий новый режим сравнения,при котором определяется совпадение всехразрядов рабочих и запрещенных чисел, кроме второго.,После этого на счетчик 7 блока управления 1 поступает новая серия,импульсов черезввод. При этом работа устройства аналогичнаописанной выше. Логический блок 3 в этомцикле реализует логические формулы;гг, = а,Ь, + аггг + 1 гг,д, =аЬ, +а;Ь (1=2, 3, , и),иг -- ггг, ггз, сг,г,где у - значение первого разряда регистра 4.Процесс поразрядного сравнения рабочих и запрещенных чисел повторяется и раз (проводится для каждого разряда), в результате чего в,разрядах, регистра 4 записывается информация о всей группе рабочих (запрещенных) нли услов:ьх чисел, которые склеены сВведе:ны рабочим (запрещенным) ч:слом.На оснозан,нн значений разрядов регистра 4.и введе:шого рабочего (запрещенного) ч слалогическим блоком 3 формируется соответствуюгцая простая импликанта (пмплицента),которая Отооражается на блоке 1 нднкацип и,регистрации 6.После приведения схемы в исходное со 10 стояние в логический блок 3 вводится нозоераоочее (запрещенное) число, и повторяетсяцикл определения простой импликанты (имплиценты), соответствующей дан ому числу.Такая процедура проделывается до тех15 по р, пока не оудут оослужены,все рабочие(запрещенные) числа, опСыВающие условияфункционирования минимизируемой лэг:ческой схемы,Наличие в предлагаемом устройстве свя 20 ззей между входами и выходамп блока управлениярегистра и логического блока ооеспечпвает автоматический режим работы устройсгва в процессе определения простых нмп;шкант (имплицент) логической функции для25 заданного рабочего (запрещенного) числа,Результаты макетирования и испытанийподтверждают работоспособность устройства)его высокое быстродействие, малые гаоаритыи удобство раооты с нихг,30 Предмет изобретения Вычислительное устройство для минимизации структур логических схс, содержащее 35 логический блок, вход которого подключен кдешифратору, а выход - к олоку индикации и регистрации, и. наборное поле, соединенное двухсторонней связью с дешнфратором, от.гичаюигееся тем, что, с целью повышения оысг родействия, оно содержит регистр и блокуправления, первые вход и выход которого соединены с логическим блоком, второй ВыхОд Олока управления подключен к логическому блоку н дешифратору, а третий через45 регистр - к логическому блоку.Заказ 63/385 Изд. Мо 1577 Тираж 624 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб д. 4/5 Тнп. Харьк. фил. пред. кПатент