bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Разбить исходный ППК пополам, относительно оси максимального ранга. Считать любую его половину новым ППК. Перейти к п.1.4. Конец.Применяя алгоритм, проверим, будет ли фигура t на рисунке18.7.8 прямоугольником Карно. По алгоритму:- фигура t симметрична относительно горизонтальной осисимметрии 3-го ранга;- верхняя половина фигуры t симметрична относительно вертикальной оси симметрии 2-го ранга;- верхняя левая четверть фигуры t симметрична относительногоризонтальной оси симметрии 2-го ранга- половина верхней левой четверти фигуры t не охватываетни одной оси симметрии.Следовательно, фигура t будет прямоугольником Карно.На рисунке 18.7.9 даны примеры фигур, не являющихся прямоугольниками Карно.

Фигуры k, m и n не являются прямоугольниками Карно в силу нарушения принципа симметрии. Фигура n не симметрична относительно вертикальной оси симмет121рии 2-го ранга, фигура m не симметрична относительно горизонтальной оси симметрии 3-го ранга. Фигура k симметрична относительно горизонтальной оси симметрии 3-го ранга, но её половина не симметрична относительно горизонтальной оси 2-го ранга.18.7.9. Фигуры k, m и n, не являющиесяпрямоугольниками Карно.На карте Карно булева функция f  x1, x2 ,..., xn  задаётся указанием в каждой клетке значения, которое она принимает нанаборе, соответствующем клетке.Например, на рисунке 18.7.10 в поле карты для 4-х переменных задана функция f  x1, x2 , x3 , x4   1011 0001 1011 0001 .18.7.10. Карта Карно для функции.Записав данную функцию в виде СДНФ и аналитическиупростив с помощью операции склеивания, получим:122f  x1, x2 , x3 , x4   x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x2 x3 x4  x2 x3 x4  x1x3 x4  x1x3 x4  x2 x4  x3 x4 .Карта Карно позволяет получить этот результат графическизначительно быстрее и проще.

Для решения этой задачи используем алгоритм графической минимизации.Алгоритм графической минимизации логических функций:1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности булевой функции f  x1, x2 ,..., xn  .2. Покрыть все единичные наборы минимальным количеством прямоугольников Карно, каждый из которых имеет максимальную площадь.3. Проверить каждую фигуру покрытия на соответствиепринципу симметрии. В противном случае изменить контур фигуры покрытия в соответствии с принципом симметрии так, чтобы она превратилась в прямоугольник Карно.4. Каждому прямоугольнику Карно соответствует одна импликанта, причём, если в границах прямоугольника Карно какаялибо переменная принимает значения как 0, так и 1, то она склеивается.Примечание.

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

Требование получения максимальной площади прямоугольника Карно вызвано стремлением минимизировать длинукаждого слагаемого булевой функции.Найдём с помощью карты Карно минимальную ДНФ функции f  x1, x2 , x3 , x4   1011 0001 1011 0001 . Карта Карно с выде-123ленными прямоугольниками Карно показана на рис. 18.7.11.18.7.11. Карта Карно функции, с выделенными прямоугольниками Карно.Находим импликанты, соответствующие выделенным прямоугольникам.1. Для синего прямоугольника:000000000101000 ;1010 ;010   0  0   x2 x4 .0  00000102. Для красного прямоугольника:0  11001111110111 ; 1011 ; 1  11     11  x3 x4 .0  11 1  11   11Минимальная ДНФ функции f  x1, x2 , x3 , x4  имеет вид:fDmin x2 x4  x3 x4 .По карте Карно можно получить и минимальную КНФ. Дляэтого находят МДНФ инверсной функции f , берут от неё отри-цание f и, применив правила де Моргана, получают МКНФ.Пример 18.7.1.

Для функции, заданной векторноf  x, y, z, w  1101 1010 1101 1100  ,найти минимальную ДНФ и минимальную КНФ с помощью картКарно.Решение. Изобразим таблицу функции f  x, y, z, w :124xyzwf  x, y, z, w00001000110010000111010010101001101011101000110011101001011111001110111110011110Задача нахождения минимальной ДНФ с помощью картыКарно сводится к задаче покрытия всех единиц карты Карно минимальным количеством прямоугольников наибольших размеров,причём разрешается использовать только прямоугольники, симметричные относительно осей симметрий и площади которых являются натуральными степенями двойки.Рис. 18.7.12.

Карта Карно функции, с выделенными прямоугольниками Карно для нахождения МДНФ.Находим импликанты соответствующие выделенным прямоугольникам (рис.18.7.12).1. Для синего прямоугольника:0  00000011000100 ;1000 ;1  00     00   zw .  000  001  002. Для фиолетового прямоугольника:00  1000110010011 ;1011 ;10  1   0  1  yw .00  110  10  11253. Для зелёного прямоугольника:1  00110011011000 ;1001 ;1  01  1  0    xz .1  001  01 1  0 4. Для красного прямоугольника:01000110   01  0   xyw .01  0fМинимальная ДНФ имеет вид: Dmin zw  yw  xz  xyw .Задача нахождения минимальной КНФ с помощью картыКарно сводится к задаче покрытия всех нулей карты Карно минимальным количеством прямоугольников наибольших размеров.Рис.

18.7.13. Карта Карно функции, с выделенными прямоугольниками Карно для нахождения МКНФ.Находим импликанты соответствующие выделенным прямоугольникам (рис.18.7.13):1. Для красного прямоугольника:00101010   010   yzw .0102. Для фиолетового прямоугольника:12611111110  111    xyz .111 3. Для зелёного прямоугольника:01010111   01  1  xyw .111 Минимальная ДНФ функции f имеет вид:fDmin yzw  xyz  xyw .Чтобы получить минимальную КНФ функции f , берём отриfцание от Dmin:ffKmin Dmin yzw  xyz  xyw  yzw  xyz  xyw  y zw  x y z  x yw .19.

Задачи анализа и синтеза логических схемЛогическая схема, имеющая n входов X  x1, x2 ,..., xn  и mвыходов Y   y1, y2 ,..., ym , в обобщённом виде представлена нарис. 19.1.x1x2ЛСy1y2……xnyтРис. 19.1. Обобщённый вид ЛС.Работу логической схемы (рис. 19.1) можно описать:127- системой, выражающей зависимость между множествомвходных переменных X  x1, x2 ,..., xn  и множеством булевыхфункций Y   y1, y2 ,..., ym : y1  y1  x1 , x2 ,..., xn  , y2  y2  x1 , x2 ,..., xn  ,... ...

... ... ... ... ... y  y  x , x ,..., x  ;m 1 2n m- таблицей истинности, имеющей 2n строк (по строке длякаждого набора входных переменных) и (n+m) столбцов (nстолбцов для входов и m столбцов для выходов схемы).Относительно логических схем обычно решаются две задачи:анализа и синтеза.19.1. Задача анализа логических схемЗадача анализа ЛС заключается в выявлении реализуемойбулевой функции.

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

По заданной логической схеме (рис. 19.1.2)составить булеву функцию.Решение. Согласно приведённой выше последовательностидействий, схема разобьётся на три яруса. Пронумеровав полу-128чившиеся ярусы, введём обозначения для каждой выходнойфункции. Запишем все функции, начиная с 1-го яруса:1. f1  f 21  f 22  x4 ;2. а) f 21  f31  x2 , б) f 22  x2  f32 ;3. а) f31  x1 , б) f32  x2  x3 .Теперь запишем все функции, подставляя входные переменные:а) f 21  x1  x2 , б) f 22  x2  x2  x3 .В итоге, получим выходную функцию:f  f1   x1  x2   x2  x2  x3  x4 .11&13 ярус2 ярус&1 ярусРис.19.1.2.

Логическая схема.Пример 19.1.2. Найти математическое описание логическойсхемы (рис. 19.1.3).Решение. Логические функции представленной схемы легконаходятся по её структуре: y1  x1  x2  x1x2 ; y2  x2 x3  x4 .1291111&111Рис.19.1.3. Логическая схема.19.2. задача синтеза логических схемЗадача синтеза ЛС – определить содержимое «чёрного ящика» (рис.

19.2.1), т.е. определить состав логических элементов,входящих в логическую схему, и порядок их соединения междусобой.x1x2…?xnРис. 19.2.1. «Чёрный ящик» с заданной функцией выхода.При построении схем в реальной системе элементов необходимо учитывать ряд конструктивных ограничений, основными изкоторых являются:1. Коэффициент объединения по входу, который представляет собой ограничение на число входов в элемент. Может принимать значения 2,3,4,8,16.1302.

Коэффициент разветвления по выходу, определяющиймаксимальное число логических элементов, которые можно подключить к выходу элемента в условиях его нормального функционирования. Этот коэффициент определяет нагрузочную способность. Варьируется от 10 до 30.Различают ЛС с одним и многими выходами. Разберём этапысинтеза с учётом того, что ЛС может быть многовыходной:а) составление математического описания ЛС, адекватноотображающего назначение схемы (либо в виде таблиц истинности, либо в аналитической форме в виде системы);б) анализ выходных булевых функций, их предварительнаясовместная минимизация в заданном базисе;в) построение логической схемы, реализующей полученныефункции, в заданном базисе, с учётом коэффициента объединения по входам и коэффициента разветвления по выходу.Качество синтезируемой схемы оценивается двумя основными показателями: затратами оборудования и быстродействием.Затраты оборудования определяются ценой схемы по Квайну, абыстродействие схемы задержкой распространения сигналов отвходов схемы до её выхода.Отметим, что при синтезе логических схем необходимо учитывать, в каком виде представляются входные сигналы схемы: впрямом и инверсном или только в прямом.

Характеристики

Список файлов учебной работы