promel (967628), страница 50
Текст из файла (страница 50)
В общем случае нали"ие единиц в 2" соседних клетках позволяет исключить и переменных. В атом и заключается метод минимизации с применением карт Карпо. Рассмотрим процесс минимизации на 'примере четырех переменных х. у, г, о функции, заданной следующим логическим выражением: 5 = уго + куо + уго + куг + гго -(- у г о м- у г о. С помощью простейших преобразований представим эту функцию в виде )' = уго (х + х) + хуо (г + г ) + ого (х -ь л ) -+ ког (о -(- о ) ф 213 акции ции более просто, быстро и безошибочно.
Для минимизации лцвю фУ числом пеРеменных до пЯтн-шести наиболее Удобным Яв,'' фуятс метод к а р т К а р н о. „кции с ляетси Карно (рис. 3.20, а — в) представляет собой графическое .„ жение значений всех возможных комби аций перемен ых. зз"'р вами, карту Карно можно рассматривать как графическое „4 ажени ,„иь,ми ело вление всех минтермов заданного числа переменных. „ едставл + хг о (у + у) + у г о (х ф х ) + у г о (х + х ) =- = хуго + хуго + хуго н-хуго+ хуго+ хуго + хуго+ + хуго + хуго + ху го + ху г о + ху г о+ ху г о т х уг После исключения повторяющихся членов функция выраж в СДНФ: Г = хуго + хуго + х уг о + хуго + х уго + хуго + хуго + Рис.
3.21. Карта Карно функ ннн хуго + хуго=- хуг (о Но) =- хуг, + ху г о + х у го а- ху г о + х у г о. Функция состоит из 11 мивтермов, в связи с чем на карте К (рпс, 3,2!) ее будут представлять 11 клеток, отмеченных единиц Так, например, первый минтерм ф Р "" ьр брб бр ,О " 'б' р "н"' Р"". венно !1 и 11, Пять клеток карты' таются свободнымн, Затем на карте Карно необход определить соседние минтермы (кл г гр' и объединить их в минимальное кол уг ! у г г ство групп соседних мпнтермов (клет ' Драя наглядности выделенные груп, УО Г 1! ! ! соседних клеток показывают сплошиб ми линиями. Минимальное- количес.
групп соседних миитермов для рассм рнваемой функции будет равно трем,:; ' В первую группу входят две нижн' клетки второго столбца слева с м,' термами х уго и хуг о. В соответствии с аксиомой 4 в (3.55) инее т. е, переменная о из этой группы может быть исключена, ; Вторая группа состоит из двух пар верхних клеток крайних столб-;йцр цов, определярощих миитермы хуго, хуго н хуго, хуго Сумма этих':-':. минтермов зае! у г (х о + хо+ хо + хо) = — у г (х (о 1- о) + х (о -1- о)) = у г, т.
е, из группы исключаются две переменные; х и о. 'Третья группа состоит из восьми клеток второй н третьей строк, для которых о = 1, а переменные х, у, г входят с прямыми н инверсными значениями, в связи с чем переменные х, у, г из этой группы могут быть исключены, Сумма минтермов обеих строк будет равна о ы На основании проведенных операпий получаем минимальную функцию, выраженную в ДНФ: вести минимизапию той же функ К ггермов, находящихся в пустых нв нн", карты (рис. 3,21) и определяющих нулевое значение функции, инверсное значение г, Порядок проведения минимизации сохрат е, прежним.
Минимизирующие контуры, охватывающие соседние с нулевым значением минтермов рассматриваемой функции, показа ны па рис, 3,21 пунктиром, Из карты Карно находим г' =- х у г ь с уг ь + хгп + хуп. поспользовав1пись инверсным преобразованием (З,б!1 находим иин „нимальную функцию, выраженную в КНФ, равносильную ЛНФ: г =-- (х + у + г + о) (у —,— г -~- о) (х + г Р о) (х + у -~- о) .
31иннмизация функции в ЛНФ или КНФ равноправна, Представление результата минимизации в ЛНФ или КНФ зависит от вида реакции и состава используемых логических элементов Реализация функции в ЛНФ требует преимущественного использования логических элементов И (И вЂ” НЕ), а в КНФ вЂ” логических элементов ИЛИ (ИЛИ вЂ” НЕ) (см, 3 3.10). При использовании логических элементов И (И вЂ” НЕ) логическую функцию целесообразно представать в виде произведения перемеввых, а логических элементов ИЛИ (ИЛИ вЂ” НЕ) — в виде суммы переменных. Задачу решают, воспользовавшись правилом двойной инверсии и теоремой де ййоргана.
Лля рассматриваемой функции соответственно имеем: г" = хугуги, г" = х +у+ г + о + у и г + о -г х ф г -1- и + х+у-!-и . В качестве примеров определим минимальные функции в ДНФ н КНФ, представла нные в виде карт Карно для трех переменных (рн . 3.22) и четырех переменных (рис. 3.23), При нахождении минимальной функции в ЛНФ, представленной картой Карно на рис. 3.22, группировочные контуры должны охватывать минтермы крайних столбцов 1 и 4 (первый контур) и минтермы нижней строки (второй контур) В первой группе минтермов результат не зависит от значеннй х и г, так как они могут "Рннимать либо состояние «О», либо состояние йй в! и гв ху ху ВП ау ГГ 1а га й' Рнс 3 23 Карта Карно функцнн Рнс.
3.22. Карта Карно функции 203 «!». Переменные хи г можно исключить. В итоге первое слагае ределяемой минимальной функции равноу. Во второй группе м' мов результат не зависит от значений х и у, следовательно, ' слагаемое определяется переменной г.
Таким образом, имеем, мвльную функцию в ДНФ: Е, = « +г Г,=нг. Минимальную функцию в КНФ находят из группировки двух' тых клеток карты: откуда 1 у+а т. е. дизъюнктивная н конъюяктивная минимальные формы расс ренной функции совпадают. Для получения минимальной функции в ДНФ, представленной ' той Карно на рпс. 3.23, необходимо составить три минимизирую' контура. В первый контур входят нижняя и верхняя клетки краи, го левого столбца, откуда находим первое слагаемое минималь функции х до. Второй контур состоит из верхней и нижней клеток в: рого столбца справа, откуда определяем второе слагаемое куи И, . конец, третий контур охватывает две верхние строки карты с резул татом г. Таким образом, получаем минимальную функци|о в ДН,.
или г,= х у отрог Минимальную функцию в КНФ находят из трех контуров, охвз..~::*=,, тывакших пусгые клетки: Г» = хне .~- хр2 + »0 с прямым значением Р« =(х + у + г )(к «у+ г)(г +о), г»=» +унга хп Нсг +г )о. Нахождение логических функций и последуицто пх минимнзатгии»' широко применяют при проектировании логических схем комбииа циониого типа (см. 5 3.15). пения различных логических (функциоььальл о п е р а и н й над дискретнымн сигналами прн двоичном окне вых обе их пРедставлениЯ.
спасо Преимущественное распространение получили логические эле- и о те н ц и а л ь н о го типа. В них используются диекретмекты ные сигналы, нулевому значению которых соответствует уровень лизка кого потенциала, а единичному значению — уровень высокого по- „„дала (отрицательного или положительного), Связь потенциаль„р о логического элемента с предыдущим и последующими узлами истеме осуществляется непосредственно, без применения реактивных компонентон, Благодаря .ому преимуществу именно потенпиальные логические элементы нашли почти исключптельное применение в интегральном исполнении в ,яде микросхем. С позиций использования логических микросхем потенциального типа и проводится далее рассмотрение логичевких элементов. Логические биполярные микросхемы чаще выполняют на транзисторах типа и-р-и о напряжением литания Ее) О, Зтиьь обьясняется, что используемые здесь сигналы пмеьот положктельпую полярность.
Уровню высоково пололсипиленога потвнциаяа ь«!») на выходе ссолветствует закрытое состояние транзиапора, а уровню низкого гюпмнь4иала («О») — его открытое состояние. С этой точки зрения, в частности, и следует пониматьдействиесигналана входелогичеекого элемента, ььмекьщего непосредственную связь е другими элементами в конкретной схеме. Для упрощения уровень низкого потенциала сигнала полагаем равным нулю, а процесв перехода транзистора из одного состояния в другое — достаточно быстрым. Логические интегральные микросхемы являьогся элементами, на Основе которых выполняются схемы цифровой техники. ~ 1! ь~ь ь ь !ьь г б) Рзс. 3.24. Условное обозна«евно логического элементе ИЛИ ьа), его таблица нстняностн а временные анаграммы ьб, в) Логический элемент ИЛИ.
сколько входов и один общий вано на рис. 3.24, а. Логический элемент ИЛИ чес кого сложения Логический элемент ИЛИ им выход. Его условное обозначение выполняет о п е р а ц и ю л о' (ди зъюн кци и): Г = «т з- «э + «а + ' + «» (6 где г — функция; «и кгн «,..., к„— аргументы (переменные, дн; ные сигналы на входах).