Синтез логических схем

Как было показано выше, если есть описание автомата в виде логической формулы, то оно может быть реализовано в виде соответствующей структурной схемы в базисе «И—ИЛ И—НЕ». Решим, к примеру, задачу создания суммирующего одноразрядного устройства, действующего в соответствии с таблицей истинности (табл. 11).

Таблица 11.

Таблица истинности сумматора на два входа

Из этой таблицы видно, что устройство суммирования должно иметь два входа для складываемых двоичных чисел а и Ь и два выхода:

• • вход s — сумма а Ф Ь, подчиняющаяся логическому действию неравнозначности (о₆, т. е. s = ab + аЬ
• • вход р — перенос единицы в старший разряд, подчиняющийся закону конъюнкции (р = ab), так как р = 1 только при а = 1 и b = 1.

На рис. 21, а представлена логическая схема одноразрядного сумматора на два входа ОС-2, построенная на основании записанных исходных формул для s и р. Однако формулу для суммы s можно преобразовать, учитывая при этом, что аа = 0 и ЬЪ = 0:

Результирующая схема, представленная на рис. 21,5, содержит меньше элементов, чем схема на рис. 21, а, хотя функционально обе схемы тождественны.

Рис. 21. Схемы ОС-2: а — логическая; б — результирующая Читатель уже заметил, что законы, теоремы и вытекающие из них следствия дают возможность преобразовать и упростить логические формулы, структурные логические и релейные схемы. Во многом путь преобразования и минимизации логики для получения конечного результата зависит от опыта и знаний разработчика. Недаром считается, что эта работа в какой-то мере сродни искусству.

В целом синтез логических схем заключается в следующем.

• 1. На основании словесного описания действия дискретного автомата составляется таблица истинности для каждого выхода, в которой перечисляются все возможные комбинации входных параметров и соответствующие им значения выходных параметров.
• 2. На основании таблицы истинности записывается логическая функция в СДНФ, в которой при помощи операции дизъюнкции перечисляются все минтермы, дающие 1 на соответствующем выходе.
• 3. Логическая функция преобразуется к виду, требующему минимального количества элементов соответствующего базиса. Эта процедура называется оптимизацией (минимизацией) логики.
• 4. На основании полученной формулы (или формул для нескольких выходов) строится структурная схема автомата. Если в предыдущем пункте удалось добиться поставленной цели, то говорят об автомате с оптимальной (минимальной) логикой.

Проиллюстрируем сказанное на примере синтеза одноразрядного двоичного сумматора на три входа ОС-3.

1. Складываются двоичные числа а, Ь, с. Первый выход должен обеспечить сумму s = а ® b ® с, второй выход — перенос р в старший разряд. Соответствующая таблица истинности приведена ниже (табл. 12).

Таблица 12.

Таблица истинности для сумматора на три входа

2. Логические формулы СДНФ имеют вид:

где s есть логическая сумма 1, 2, 4 и 7 минтермов; р — логическая сумма 3, 5, 6, и 7 минтермов.

3. На основании законов логики функции s н р можно преобразовать:

Для второй скобки в s введем обозначение V= (аЪ + ас + Ъс) и, используя двойное отрицание и закон инверсии Шеннона, получим.

Следовательно, s = {а + b + с)р + abc.

4. Логическая схема сумматора ОС-3 приобретает вид, представленный на рис. 22.

Рис. 22. Схема ОС-3.

С появлением ЭВМ стали широко использоваться формализованные процедуры синтеза логических схем и автоматов. Из множества разработанных методов обычно предпочтение отдается методу, основанному на картах (диаграммах) Карно.