ЦИФРОВЫЕ УСТРОЙСТВА. Лекция 5. Логические схемы.
2.3.7 Логические схемы
Логические схемы являются одним и методов представления и реализации логических
функций. Эти схемы состоят из логических элементов. Логический элемент – физическое
устройство, реализующее заданную логическую функцию.
Обычно логический элемент реализует элементарную или типовую логическую
функцию. Можно, конечно, для каждой заданной логической функции создать свой
логический элемент в виде микросхемы. Но представляете, сколько разных элементов
пришлось бы создавать! Уже для 5-и переменных нужно создать 25 = 32, 232 = 4 294 967
296, то есть более 4-х миллиардов видов элементов. Ясно, что это нереально. Это и долго,
и дорого. Как здесь быть? Здесь, как обычно в подобных случаях, используется
декомпозиция, то есть разделение сложной задачи на ряд боле простых задач. Эти задачи
решают независимо друг от друга, затем решения объединяются. В нашем случае
создается небольшое количество типовых логических элементов и из них, как из
кирпичиков, составляются сложные логические функции. Логическую функцию можно
также реализовать с помощью логических матриц, но, как мы увидим позже, эти матрицы
также состоят из элементарных кирпичиков. Соединяя эти кирпичики между собой, мы
получаем свою уникальную логическую функцию.
Таким образом, любая логическая функция реализуется с помощью небольшой
номенклатуры логических элементов.
Обычно л.э. реализует базисную элементарную логическую функцию. Как правило,
л.э. содержит несколько входов и один выход. Мы будем использовать графическое
изображение л.э. по ГОСТ 2.743-82. Он изображается прямоугольником произвольных
размеров, внутри которого записывают условное графическое изображение реализуемых
функций: конъюнкция – , дизъюнкция – 1. Инверсия обозначается кружочком у входа
или выхода. В англоязычных странах логические элементы принято изображать иначе.
Везде справа от логического элемента изображаются выходы, слева – входы.
Изображения основных логических функций 2-х переменных представлены на
следующей странице.
Элементарные логические элементы могут иметь более двух входов и реализовывать
более сложные типовые функции.
Как же с помощью элементарных логических элементов воспроизвести заданную
логическую функцию? Путем соединения этих элементов между собой. Что именно
соединять, зависит от функции. Такая совокупность логических элементов, соединенных
между собой называется логической схемой. Логические схемы является основой для
реализации заданной логической функции в техническом устройстве.
Логическая схема составляется по аналитическому выражению логической функции в
следующей последовательности:
1) аналитическое выражение логической функции преобразуется к виду, где можно
выделить логические функции, реализуемые данными логическими элементами.
Образуется система логических функций.
2) Изображают выделенные логические элементы и соединяют входы каждого
элемента с выходами других элементов или с входами схемы согласно аналитическому
выражению.
При преобразовании схемы удобно использовать промежуточные буквенные
обозначения функций, реализуемых л.э. Изображать логическую схему целесообразно,
начиная с выхода, справа налево.
1) Функция НЕ y x (английское название NOT)
2) Функция И у = х2 х1 (английское название AND)
3) Функция ИЛИ у = х2 х1 (английское название OR)
4) Функция И-НЕ y x2 x1 (английское название NAND)
5) Функция ИЛИ-НЕ y x 2 x1 (английское название NOR)
6) Функция исключающее ИЛИ y x1 x2 (английское название XOR)
7) Функция исключающее ИЛИ-НЕ y x 2 x1 (английское название NXOR)
Пример: составить л.с., реализующую функцию
y xgz z
(2.12)
в базисе И, ИЛИ, НЕ. То есть у нас есть только элементы И, ИЛИ, НЕ, но с любым
количеством входов.
Для выражения заданной функции через операции И, ИЛИ, НЕ используем
промежуточные переменные. Обозначим
y1 x g z
(2.13)
Обозначим
y2 y1 x g z
(2.14)
Тогда, используя (2.13), (2.14) функцию (2.12) можно записать в виде
y y2 z .
(2.15)
объединяя (2.13) – (2.15), получаем систему логических функций, в которую входят только
логические элементы базиса И, ИЛИ, НЕ.
y y2 z
y 2 y1
y1 x g z
Мы преобразовали исходную функцию к виду, удобному для реализации логическими
элементами И, ИЛИ, НЕ.
Изображаем логическую схему начиная с конца. В конце стоит элемент ИЛИ с двумя
входами. Изображаем его и обозначаем входы-выходы.
Вообще предлагаемый метод составления л.с. не является единственным, здесь
область творчества учащихся.
2.3.8 Минимизация логических функций. Общие положения
Как мы убедились, логические схемы составляются на основе аналитического
представления функции. Однако аналитическое представление не однозначно, т.е. одну и
ту же функцию можно представить разными аналитическими выражениями, имеющими
разную сложность. Следовательно, и технические устройства по этим выражениям будут
также иметь разную сложность и стоимость. Из этого следует задача: найти такое
аналитическое выражение для функции, которое бы обеспечило минимальную стоимость.
Обычно техническое устройство имеет минимальную стоимость, если оно содержит
минимум логических элементов, а сами элементы – минимум входов. Это соответствует
минимуму первичных термов в аналитическом выражении функции. Напомним, что
первичный терм – это сама переменная или ее инверсия.
Таким образом, цель минимизации – поиск такого аналитического выражения
логической функции, которое имеет минимальное количество первичных термов. Задача
минимизации может быть иной, минимизация может вообще не потребоваться, например,
при реализации функций на некоторых программируемых логических матрицах.
Все методы минимизации основаны на эквивалентных преобразованиях логических
функций.
Задачу минимизации можно решать с помощью преобразований исходной функции,
применяя тождества и теоремы алгебры логики.
Общие правила минимизации можно установить, когда исходная функция задана в
виде таблицы истинности или СДНФ (СКНФ). В основе этих правил лежат операции
склеивания и поглощения соседних минтермов (или макстермов).
Напомним соотношения склеивания и поглощения.
Операции склеивания
x y x y x;
(2.16) Здесь исчезла переменная y.
( x y) ( x y) x
Законы поглощения (х поглощает xу или (xу))
хx у = х;
(2.17)
х (xу) = х;
Конъюнкции в первом выражении (2.16) и дизъюнкции во втором выражении можно
интерпретировать, как минтермы или макстермы, таким образом видно, что
представление функций в СДНФ и СКНФ наиболее приспособлено для минимизации.
При склеивании используется понятие соседнего минтерма (макстерма). Соседними
называются минтермы (макстермы), отличающиеся на один первичный терм, а все другие
термы одинаковые.
Пример: запишем первые три минтерма трех переменных
К0 = x 3 x 2 x1 ; К1 = x 3 x 2 x1 ; К2 = x 3 x 2 x1
Из этой записи видно, что К0, К1 – это соседние минтермы, они отличаются только
одним термом. К1 и К2 – не соседние, они отличаются двумя термами.
Каждый минтерм содержит п соседних из числа 2п.
Операция склеивания заключается в объединении соседних 2m минтермов
(макстермов), где т = 0, 1, 2, …. В результате получается эквивалентная дизъюнкция
(конъюнкция), содержащая на "т" переменных меньше.
Пример:
К0 К1 = x 3 x 2 x1 x 3 x 2 x1 = x 3 x 2 ( x1 x1 ) = x 3 x 2
исчезла переменная х1 – это та переменная, на первичные термы которой отличались
К0 и К1.
Одни и те же минтермы (макстермы) могут склеиваться по несколько раз.
Используются аналитические и графические способы минимизации.
Ааналитические способ минимизации заключается в следующем:
1) Приводим функцию к СДНФ (СКНФ).
2)Производим склеивание соседних минтермов (макстермов).
3) Выполняем дальнейшие упрощения.
Недостатки способа: 1) неоднозначность и ненаглядность процесса склеивания, 2) Нет
уверенности в том, что получен оптимальный результат.
Преимущество метода: Метод может быть формализован для применения ЭВМ.
Поэтому с применением ЭВМ эти недостатки могут быть устранены.
Нашли применение метод минимизации на ЭВМ Квайна и усовершенствованный
метод Квайна – Мак-Класски. Мы их рассматривать не будем, интересующиеся могут
обратиться к соответствующей литературе.
