Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Логический синтез вычислительных схем

Функции и аргументы в алгебре логики определены на множестве {0, 1} и, следовательно, могут принимать только два значения. Различные комбинации значений аргументов называются наборами. Для каждого набора аргументов можно задать два значения функции алгебры логики (ФАЛ), следовательно, для п аргументов можно получить (2") различных функций. С целью получения новых функций можно использовать принцип суперпозиции, позволяющий подставлять одни функции вместо аргументов в другие функции. Система ФАЛ, позволяющая получать любые, сколь угодно сложные функции, называется функционально полной системой, а набор элементов, реализующих данные функции, — функционально полным набором или базисом. При построении дискретных устройств наибольшее распространение получили функции, реализующие следующие операции (рис. 1.25).

а б в г

Рис. 1.25. Логические блоки операций: а — операция инверсия (инвертор); б — операция конъюнкция (конъюнктор); в — операция дизъюнкция (дизъюнк-тор); г — операция отрицание дизъюнкции (дизъюнктор с отрицанием)

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

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

В последовательностных схемах выходные сигналы в любой момент времени зависят не только от комбинации входных сигналов, но и от предыстории их изменения, т. е. от изменения последовательности сигналов во времени. Последовательностные схемы характеризуются наличием так называемых петель, по которым выход некоторого элемента соединяется со входом этого самого элемента (через другие элементы схемы). С учетом этой задержки значение выходного сигнала по времени запаздывает на время задержки по сравнению с моментом изменения входных сигналов (рис. 1.26).

Комбинационная схема

Рис. 1.26. Комбинационная схема

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

В общем случае последовательностная схема представляет собой некоторый цифровой автомат (рис. 1.27).

В комбинационных схемах (КС) значение выходного сигнала в любой момент времени зависит только от комбинации входных сигналов (в этот момент времени с учетом задержки распространения сигнала по элементам схемы).

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

Основные параметры комбинационных схем — стоимость и быстродействие. Быстродействие схемы оценивается задержкой

Последовательностная схема

Рис. 1.27. Последовательностная схема

распространения сигналов от входов схемы к ее выходу. Для абстрактных КС эту задержку принято считать в виде:

Т = кх,

где т — задержка на одном логическом элементе; к — максимальное количество логических элементов, через которые проходит сигнал от входов к выходу.

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

Примечание. В ряде случаев перед построением логической блок-схемы устройства по логической функции последнюю, пользуясь соотношениями алгебры логики, следует преобразовать к более простому виду (минимизировать). Для логических схем «ИЛИ», «И» и «НЕ» существуют типовые технические схемы, реализующие их на интегральных схемах. Для построения современных компьютеров обычно применяются системы интегральных элементов, у которых с целью большей унификации в качестве базовой логической схемы используется всего одна из схем:

«И — НЕ» (штрих Шеффера);

«ИЛИ — НЕ» (стрелка Пирса);

«И - ИЛИ - НЕ».

Пример 1.28. Три человека участвуют в тайном голосовании. Составить логическую схему, регистрирующую результаты тайного голосования большинством голосов.

Пусть Л — первый человек, голосующий «за», В — второй человек, голосующий «за» и С — третий человек, голосующий «за». Составим таблицу истинности (табл. 1.18) интересующего нас итогового высказывания Т7 (предложение принимается большинством голосов).

Таблица 1.18. Таблица истинности

А

В

с

Т7

Ответ

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

АВС

1

0

0

0

1

0

1

1

АВС

1

1

0

1

АВС

1

1

1

1

АВС

Искомое высказывание имеет вид:

Р= АВС + АВС + АВС + АВС.

После упрощения функция принимает вид:

Г= ВС(А + И) + А(ВС+ ВС) = С( В + В А) + АВС =

= С(В + А) + АВС = СВ + СА + АВС = В(С + АС) + СА =

= В(С + А) + СА = ВС + ВА+ СА.

Таким образом, логическая схема, реализующая процесс голосования, будет иметь вид (рис. 1.28).

Логическая схема

Рис. 1.28. Логическая схема

Пример 1.29. Как в условиях примера 1.28 реализовать электрическую схему, зажигающую лампочку, если хотя бы один из участников проголосовал «за»?

Составим таблицу истинности для указанного случая (табл. 1.19).

Таблица 1.19. Таблица истинности

А

В

с

Т

Ответ

0

0

0

0

т о, о)

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

1

Далее составим логическую функцию. В данном случае целесообразнее выбрать те строки, где Р= 0. Это состояние /?(0, 0, 0). Тогда Г= (А + В + С).

Электрическая схема для указанного случая имеет вид (рис. 1.29).

Электрическая схема

Рис. 1.29. Электрическая схема

Пример 1.30. Какое высказывание реализует приведенная ниже электрическая цепь? Если можно, то нарисуйте более простую электрическую цепь, реализующую то же самое высказывание (рис. 1.30).

Электрическая цепь

Рис. 1.30. Электрическая цепь

Решение. Электрическая цепь реализует высказывание:

/г= ЛВ + (АВ + В).

Упростим полученную логическую функцию:

Р=(А + )В + АВ = В + АВ = В + А.

Таким образом, упрощенная электрическая цепь, реализующая исходное высказывание, имеет вид (рис. 1.31).

Электрическая цепь

Рис. 1.31. Электрическая цепь

Пример 1.31. Для представленной ниже электрической цепи (рис. 1.32) введем следующие высказывания:

А — «элемент А вышел из строя»;

В — «элемент В вышел из строя»;

С — «элемент С вышел из строя»;

/) — «элемент /) вышел из строя».

Электрическая цепь

Рис. 1.32. Электрическая цепь

Что можно сказать о состоянии цепи, если:

  • а) высказывание А + BCD — истинно;
  • б) высказывание Л(В + С + D) — истинно. Решение.
  • а) высказывание А + BCD = 1 (истинно).

А

BCD

А+ BCD

0

0

0

0

1

1

1

0

1

1

1

1

Таким образом, отсюда следует, что

А = О, BCD= 1 ^ В=С= D= 1;

А= 1, BCD = 0; А = 1, BCD= 1

или то, что:

  • • элемент А работает (Л = 0), а все элементы, соединенные параллельно (В, С, /)), вышли из строя. Цепь разомкнута;
  • • элемент А, соединенный последовательно с остальными тремя элементами, вышел из строя, и поэтому независимо от состояния остальных элементов цепь будет разомкнутой;
  • б) высказывание А(В + С + 1))= 1 (истинно).

А

(В + С + D)

А(В + С + D)

0

0

0

0

1

0

1

0

0

1

1

1

Так как известно, что А(В + С + /)) — истинно, то возможна только одна ситуация:

А= 1, В + С+0=оА = 0, ВС + I) = 1 А = О,

BCD= 1 А = О, BCD = 0.

Таким образом, элемент А исправен = 0) и обязательно исправен, по крайней мере, один из элементов — В, С, О. Следовательно, цепь замкнута и ток проходит по цепи.

Пр и мер 1.32. Нарисуйте одну из наиболее простых электрических цепей, реализующую данное высказывание:

(А + В)((С + В)^В)^В.

Решение. Преобразуем данное высказывание:

(.А + В)((С + В)->В)->В=(А + В)(С + В) +В)->В =

= (А + В)(СВ + В)^В=(А + В)(СВ + В)^В =

= (А + В)(С+ В)^В =(АС + ВС + А В + В) —> В =

= (АС + ВС + В) -> В = (АС + В) -> В = (АС + В) +В =

= АСВ + В =(А +С)В + В = В + А + С.

Таким образом, электрическая цепь имеет вид (рис. 1.33).

Электрическая цепь

Рис. 1.33. Электрическая цепь

Пр и мер 1.33. Нарисуйте одну из наиболее простых логических схем, реализующую данное высказывание:

(ІР + д) ? (Р+д) +Р-Упростим данную функцию:

Р= (ІР + Я)(Р + д) + Р = (Р + Я?) + Р = Р + Я?.

Таким образом, логическая схема имеет вид (рис. 1.34).

рдг

В

Пример 1.34. Для данной схемы запишите логическое выражение (рис. 1.35).

А

В

С

Логическая схема

Рис. 1.35. Логическая схема

Решение. Г= (А V В V С) л (В V А V С).

Пример 1.35. Для данной схемы запишите логическое выражение (рис. 1.36).

Логическая схема

Рис. 1.36. Логическая схема

Представление логической функции в виде графа

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

Пусть с некоторого устройства поступают сигналы х, у, z, х, у, z, (х, У, Z инвертированные сигналы, т. е. сигналы противоположного содержания), на вычислительное устройство (ВУ), логика работы которого описывается булевой функцией:

f{x, у, Z) = ((х А у) V Л У Л z)) V Л z) =

= ху v xyz v yz,

причем блоки суммирования и умножения ВУ имеют только два входа.

Тогда изображение булевой функции в виде дерева имеет следующий вид (рис. 1.37).

Изображение булевой функции в виде дерева

Рис. 1.37. Изображение булевой функции в виде дерева

На выходе, у основания дерева имеем значение логической функции /, которая является корнем дерева.

 
<<   СОДЕРЖАНИЕ   >>