Синтез и анализ комбинационных схем

В.Ф. Жирков

Синтез и анализ комбинационных схем

Методические указания
к выполнению домашних заданий

Московский государственный технический университет 
имени Н.Э. Баумана

ISBN 978-5-7038-4485-4 

© МГТУ им. Н.Э. Баумана, 2016
© Оформление. Издательство 
 
МГТУ им. Н.Э.Баумана, 2016

УДК 681.3.05
ББК 32.97
        Ж73

Издание доступно в электронном виде на портале ebooks.bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/255/book1489.html

Факультет «Информатика и системы управления»
Кафедра «Компьютерные системы и сети»

Рекомендовано Редакционно-издательским советом
МГТУ им. Н.Э. Баумана в качестве методических указаний

Жирков, В. Ф.
Синтез и анализ комбинационных схем : методические 
указания к выполнению домашних заданий / В. Ф. Жирков. 
Москва: Издательство МГТУ им. Н. Э. Баумана, 2016. — 
39, [5] c. : ил.

ISBN 978-5-7038-4485-4

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

УДК 681.3.05
ББК 32.97

Ж73

ПРЕДИСЛОВИЕ

В данных методических указаниях предлагаются домашние задания № 1, 2 и 3 по теме «Синтез и анализ комбинационных схем», 
которые выполняются последовательно. Учебным планом по дисциплине «Схемотехника ЭВМ» выполнение заданий предусмотрено  
в V семестре.
Цель методических указаний — изучение принципов построения 
комбинационных схем, закрепление практических навыков при решении задач синтеза и анализа комбинационных схем.
Теоретический подход к синтезу комбинационных схем (КС) широко освещается в технической литературе. К КС относятся типовые 
функциональные узлы ЭВМ, цифровых устройств (дешифраторы, 
шифраторы, мультиплексоры, демультиплексоры, сумматоры, узлы 
контроля, преобразователи кодов и др.) и специализированные узлы.
При практическом применении и анализе функционирования КС 
разработчик сталкивается с явлением возникновения ложных выходных 
сигналов, не предусмотренных теоретической моделью схемы на языке алгебры логики.  
Ложные выходные сигналы возникают потому, что в теоретическом 
описании работы схемы не учитываются переходные процессы в источниках входных сигналов и задержки входных сигналов схем,  
не принимаются во внимание искажения фронтов и спадов сигналов, 
поступающих от разных источников, временные задержки по линиям 
связи различной длины.
В вышеперечисленных случаях говорят о гонках, или состязаниях, 
входных (двух и более) сигналов, приводящих к ложным выходным 
сигналам. Учет этих факторов затруднен, а в большинстве практических 
случаев невозможен. Наиболее эффективным способом исключения 
ложных выходных сигналов, вызванных гонками входных сигналов, 
является стробирование в асинхронных комбинационных схемах  
и синхронизация приема выходных сигналов комбинационных схем 
на входах синхронных триггеров. 

Темой «Синтез и анализ комбинационных схем» объединены три 
домашних задания, посвященные вопросам теоретического синтеза 
КС и анализу их работы. В заданиях рассмотрены вопросы выявления, 
объяснения и устранения ложных выходных сигналов с помощью 
стробирования и синхронизации приема сигналов в запоминающие 
элементы (триггеры).
Задачами, которые решаются в процессе выполнения домашних 
заданий, являются:
— освоение методики синтеза КС;
— выполнение анализа функционирования КС;
— выявление помех в КС, не предусмотренных математическим 
описанием (моделью) схем функциями алгебры логики и вызванных 
гонками (состязаниями) входных сигналов и переходными процессами 
в схемах;
— освоение эффективного метода борьбы с помехами, вызывающими риски сбоя в комбинационных и последовательностных схемах;
— введение стробирования и синхронизации (тактирования).

ДОМАШНИЕ ЗАДАНИЯ ПО ТЕМЕ
«СИНТЕЗ И АНАЛИЗ КОМБИНАЦИОННЫХ СХЕМ»

Дано: функция алгебры логики (ФАЛ) f (x4, x3,  x2, x1) четырех переменных x4, x3, x2, x1. ФАЛ определена номерами наборов, на которых 
она равна единице.
Требуется последовательно выполнить домашние задания № 1, 2, 3.

Домашнее задание № 1

Схема выполнения:
— составить таблицу истинности ФАЛ;
— по таблице истинности найти совершенную дизъюнктивную 

нормальную форму (СДНФ) и совершенную конъюнктивную нормальную форму (СКНФ) функции f (x4, x3, x2, x1), представить СДНФ 
и СКНФ  функции на картах Карно;
— минимизировать функцию f (x4, x3, x2, x1), определив ее минимальные дизъюнктивную и конъюнктивную нормальные формы (ДНФ 
и КНФ);
— преобразовать минимальные ДНФ и КНФ ФАЛ f (x4, x3, x2, x1) 

в базисы функций И-НЕ и ИЛИ-НЕ соответственно;
— составить логические схемы в базисах логических элементов 

(ЛЭ) И-НЕ и ИЛИ-НЕ, реализующих заданную ФАЛ;
— провести анализ временных диаграмм работы логических схем 

в базисах ЛЭ И-НЕ и ИЛИ-НЕ, выявить ложные сигналы на выходе, 
вызванные гонками входных сигналов.

Домашнее задание № 2

Схема выполнения:
— преобразовать минимальные ДНФ и КНФ ФАЛ f (x4, x3, x2, x1), 

введя в функции сигнал стробирования;

— составить логические схемы в базисах ЛЭ И-НЕ и ИЛИ-НЕ;
— устранить ложные сигналы на выходе логических схем с помощью сигнала стробирования;
— определить временное положение сигнала стробирования.

Домашнее задание № 3

Схема выполнения:
— устранить ложные сигналы логических схем в базисах ЛЭ И-НЕ 
и ИЛИ-НЕ, реализующих заданную ФАЛ, с помощью синхронизации 
приема выходных сигналов комбинационных схем в синхронные 
триггеры.
Варианты домашних заданий представлены в табл. 1.

Таблица 1

Варианты домашних заданий

Номер 
варианта

Номера наборов переменных, 

на которых функция алгебры логики равна единице

1-я группа
2-я группа
3-я группа
1 
1, 2, 3, 4, 7 ,8, 12, 13, 15
1, 3, 7, 8, 9, 12, 14, 15
0, 3, 4, 6, 7, 9, 10, 11, 12
2
0, 2, 3, 4, 6, 11, 13, 15
0, 3, 5, 7, 8, 10, 11, 12
0, 1, 6, 7, 8, 9, 11, 15
3
0, 4, 7, 8, 9, 11, 12, 15
0, 1, 3, 4, 8, 11, 12, 14, 15 0, 3, 4, 7, 8, 12, 14, 15
4
1, 2, 3, 6, 10, 13, 14, 15
0, 3, 4, 7, 8, 11, 14, 15
2, 5, 6, 7, 9, 10, 11, 13
5
1, 4, 7, 9, 10, 11, 12, 15
0, 1, 3, 4, 5, 9, 10, 13, 14 0, 3, 4, 7, 10, 13, 14, 15
6
1, 4, 7, 8, 10, 12, 13, 14, 15 0, 2, 3, 4, 7, 8, 12, 13, 15 0, 3, 4, 5, 6, 7, 10, 12, 13
7
2, 4, 5, 6, 8, 11, 14, 15
0, 2, 3, 4, 6, 11, 13, 15
0, 1, 2, 4, 5, 7, 9, 12
8
0, 1, 2, 3, 7, 8, 9, 12, 14, 15 0, 4, 7, 8, 9, 11, 12, 15
3, 5, 7, 8, 9, 10, 11, 12, 13, 14
9
1, 4, 5, 6, 7, 10, 11, 13
1, 2, 3, 6, 10, 13, 14, 15
0, 1, 2, 3, 6, 10, 13, 15
10
3, 4, 7, 10, 11, 13, 14, 15
1, 4, 7, 9, 10, 11, 12, 15
0, 3, 5, 6, 7, 11, 13, 15
11
0, 3, 4, 5, 6, 9, 11, 12, 14
1, 4, 7, 8, 10, 12, 13, 14, 15 0, 1, 2, 4, 5, 8, 11, 14, 15
12
0, 3, 7, 8, 10, 11, 12, 14, 15 2, 4, 5, 6, 8, 12, 14, 15
3, 4, 5, 7, 8, 11, 12, 13, 15
13
1, 2, 3, 5, 6, 7, 9, 11, 12
0, 1, 2, 3, 7, 8, 9, 10, 14, 15 1, 2, 3, 4, 9, 10, 11, 14, 15
14
0, 2, 4, 6, 8, 11, 12, 14
1, 4, 5, 6, 7, 10, 11, 13
0, 1, 6, 7, 8, 9, 12, 15
15
1, 2, 4, 6, 7, 8, 10, 14
3, 4, 7, 10, 11, 13, 14, 15 0, 1, 3, 5, 9, 10, 12, 13
16
1, 3, 4, 5, 7, 10, 11, 12, 14
0, 3, 4, 5, 6, 9, 11, 12, 14 0, 2, 3, 4, 5, 10, 11, 13, 15
17
0, 4, 5, 6, 7, 8, 9, 11, 12, 15 0, 3, 7, 8, 10, 11, 12, 14, 15 0, 1, 2, 3, 4, 7, 8, 12, 14, 15
18
2, 5, 6, 7, 9, 11, 12, 14
1, 2, 3, 5, 6, 7, 9, 11, 12
1, 2, 3, 4, 6, 9, 14, 15
19
3, 5, 6, 8, 11, 13, 14, 15
0, 2, 4, 6, 8, 11, 13, 15
1, 2, 5, 6, 7, 11, 12, 15
20
0, 1, 3, 7, 9, 10, 11, 13
1, 2, 4, 6, 7, 8, 10, 14
0, 3, 6, 8, 10, 11, 13, 14, 15
21
3, 5, 7, 10, 11, 12, 14, 15
1, 3, 4, 5, 7, 10, 11, 12, 14 2, 3, 4, 5, 7, 11, 13, 15

Примечание. Список вариантов заданий для трех студенческих групп приводится в 
таблицах. Порядковый номер фамилии студента в списке группы является номером 
варианта задания данного студента.

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ, 
РЕКОМЕНДАЦИИ И ПОЯСНЕНИЯ 
К ВЫПОЛНЕНИЮ ДОМАШНИХ ЗАДАНИЙ

Алгебра логики оперирует переменными, которые могут принимать 

только два значения, условно обозначаемые как 0 и 1. Совокупность 
значений n переменных xn, …, x1 называется набором.
Функция f (xn, …, x1) n переменных называется функцией алгебры 

логики, если она, так же как и ее переменные, может принимать только два значения — 0 или 1. ФАЛ называется также переключательной, 
булевой или логической функцией. 

Способы задания функции алгебры логики

Функция алгебры логики может быть задана словесно, алгебраическим 

выражением, таблицей ее значений (таблицей истинности), номерами 
наборов переменных, на которых она равна единице/нулю, и другими 
способами. Табличное задание любой ФАЛ в зависимости от значений ее 
переменных возможно потому, что область ее определения конечна.
Любая ФАЛ n переменных определена на 2n наборах. Число различных ФАЛ n переменных конечно и равно 

2
2 .

n

Действительно, ФАЛ n переменных определена на 2n наборах, на 

которых она может принимать значения 0 или 1. Поэтому в соответствие каждой ФАЛ можно поставить 2n-разрядное двоичное число. Так 
как количество различных 2n-разрядных двоичных чисел равно 
2
2 ,

n

 то 

и количество различных ФАЛ равно 
2
2 .

n

Каждому набору переменных приписывают десятичный номер, 

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

двоичному числу, образованному значениями функции, записанными 

слева направо, начиная со значения ФАЛ на нулевом наборе, т. е. на 
наборе переменных, содержащем все нули (0, 0, … , 0).
Например, функции f (x3, x2, x1) и j (x3, x2, x1), заданные таблицей 
истинности (табл. 2), можно обозначить так: f (x3, x2, x1) = f84 (x3, x2, x1), 
j (x3, x2, x1) = f45 (x3, x2, x1).

Таблица 2

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

Номер 

набора
х3
х2
х1
f (х3, х2, х1)
j (х3, х2, х1)

0
0
0
0
0
0
1
0
0
1
1
0
2
0
1
0
0
1
3
0
1
1
1
0
4
1
0
0
0
1
5
1
0
1
1
1
6
1
1
0
0
0
7
1
1
1
0
1

Набор переменных, содержащий все единицы (1, 1, …, 1), называют также единичным набором.
Функцию f (x3, x2, x1) можно также задать номерами 1, 3, 5 наборов 
переменных x3, x2, x1, на которых она равна единице (см. табл. 2), 
функцию j (х3, х2, х1) — номерами наборов 2, 4, 5, 7.

Правила записи ФАЛ в СДНФ и СКНФ

В СДНФ функция f (хn, …, х1) представляется в виде дизъюнкции 
функций, которые называются конституентами единицы. Конституента единицы имеет также другие названия: характеристическая функция единицы, минтерм.
Конституента единицы — ФАЛ n переменных, которая равна единице только на одном наборе переменных. На остальных наборах 
конституента единицы равна нулю.
Число различных конституент единицы среди функций n переменных равно 2n, т. е. числу различных наборов n переменных. Конституенту единицы будем обозначать буквой m с индексом, равным 
номеру набора, на котором конституента единицы равна единице. 

Обычно конституенты единицы выражают в виде конъюнкции всех 
переменных, каждая из которых входит в конъюнкцию один раз  
в прямой или инверсной форме.
Конституенту единицы mi в виде конъюнкции n переменных получают следующим образом: записывают конъюнкцию n переменных, 
располагая последние в определенной последовательности, например, 
начиная с переменной с наибольшим номером, и двоичное n-разрядное 
число, равное i; над переменными, позиции которых совпадают с позициями нулей в двоичном числе i, ставят знаки отрицания.

Пример 1. Записать конституенту единицы m27, n = 6.
Записываем 6-разрядное двоичное число, равное 27 : 27{10) = 
= 011011(2) и конъюнкцию шести переменных, начиная со старшей 
переменной х6: x6 x5 x4 x3 x2 x1. Из записи двоичного числа 011011 следует, что знаки отрицания нужно поставить над шестой и третьей 
переменными: m27 = 
6
5
4
3
2
1.
x x x x x x

Дизъюнкция конституент единицы, равных единице на тех же наборах, что и заданная функция, называется СДНФ ФАЛ. Любая ФАЛ 
f (xn, …, x1), кроме константы нуль, может быть представлена в СДНФ:

 
f (xn, …, x1) = mj1 ∨ mj2 ∨ … ∨ mjl, 
(1)

где j1, j2, …, jl — номера наборов, на которых ФАЛ равна единице;  
l — число таких наборов, на которых ФАЛ равна единице.
Справедливость соотношения (1) вытекает из того, что каждая 
единица функции f (xn, …, x1) в ее СДНФ представляется конституентой единицы с соответствующим номером. Из соотношения (1) следует, что любая ФАЛ имеет единственную СДНФ.
Структура СДНФ такова, что на произвольном наборе переменных 
в правой части соотношения (1) или все конституенты единицы равны 
нулю, если функция на этом наборе равна нулю, или только одна из 
конституент единицы равна единице, а остальные равны нулю, если 
функция на этом наборе равна единице. Поэтому справедливость соотношения (1) сохранится, если в нем знак дизъюнкции заменить на 
знак сложения по модулю два:

 
f (xn, …, x1) = mj1 ⊕ mj2 ⊕ … ⊕ mjl. 
(2)

Представление ФАЛ в виде (2) называют совершенной полиномиальной нормальной формой (СПНФ).
Любая ФАЛ может быть задана таблицей ее значений в зависимости от значений переменных. Переход от табличного представления 

ФАЛ к алгебраическому в виде СДНФ выполняют в следующей последовательности:
— записывают ряд конъюнкций всех переменных и соединяют их 
знаками дизъюнкции; количество конъюнкций равно числу наборов, 
на которых заданная ФАЛ равна единице;
— под каждой конъюнкцией записывают набор переменных, на 
котором ФАЛ равна единице; над переменными, равными нулю в этом 
наборе, ставят знаки отрицания.
Это правило называют правилом записи ФАЛ по единицам, т. е. 
по единичным значениям функции.

Пример 2. Представить функцию ϕ (x3, x2, x1), заданную табл. 2,  
в СДНФ.
Так как функция ϕ (x3, x2, x1) трех переменных принимает значение, 
равное единице, на четырех наборах переменных, то записываем четыре конъюнкции трех переменных, объединенные знаком дизъюнкции, и под каждой конъюнкцией — соответствующие наборы переменных:

3
2
1
3
2
1
3
2
1
3
2
1
0 1 0
1 0 0
1 0 1
1 1 1

x x x
x x x
x x x
x x x
∨
∨
∨

Расставляя знаки отрицания над переменными, равными нулю  
в каждом наборе, получим:

3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
(
,
,
)
.
x
x
x
x x x
x x x
x x x
x x x
ϕ
=
∨
∨
∨

Пример 3. Представить функцию штрих Шеффера f14 (x2, x1) 
в СДНФ.
Функция f14 (x2, x1) равна единице на трех наборах переменных: 
0,0; 0,1 и 1,0. Поэтому 
14
2
1
2
1
2
1
2
1
(
,
)
.
f
x
x
x x
x x
x x
=
∨
∨
 Эту форму функции 

f14 (x2, x1) можно преобразовать и привести к принятой записи:

14
2
1
2
1
2
1
2
1
2
1
1
2
1
2
2
1

2
2
1
2
2
2
1
2
1
2
1
2
1

(
,
)
(
)
1

(
)(
)
1 (
)
.

f
x
x
x x
x x
x x
x
x
x
x x
x
x x

x
x x
x
x
x
x
x
x
x
x
x x

=
∨
∨
=
∨
∨
=
⋅ ∨
=

=
∨
=
∨
∨
= ⋅
∨
=
∨
=

В СКНФ заданная ФАЛ f (xn, …, x1) представляется в виде конъюнкции функций, которые называются конституентами нуля. Конституента нуля имеет также другие названия: характеристическая 
функция нуля, макстерм.
Конституента нуля — ФАЛ n переменных, которая равна нулю 
только на одном наборе переменных. Число различных конституент