Учебная дисциплина «Математические основы теории цифровых устройств» (стр. 3 )

-  столбцами таблицы являются 0 - кубы минимизируемых функций без учёта «термов не доставляющих беспокойств» (консти-туент 1);

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

На пересечении строки и столбца ставится метка ( V ) если импликанта отличается от конституенты независимыми координатами с учетом минимизируемых функций - y, f.

Таблица 2.4

Покрытие импликантами

	Конституенты единицы
Импликанта	001 y	010 y	100 y	100 f	101 f
y f	1 — 0			V	V
y f	— 0 0			V	V
y f	1 0 —			V	V	V
y	0 — —	V	V
y	— — 0		V	V
y	— 0 —	V		V
f	1 — —				V	V

Отыскание минимального покрытия функции приводится с использованием обычного алгоритма [1. C.198]. Заметим, что в ядро Квайна не входит ни одна из импликант, так как все столбцы содержат более одной метки.

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

Таким образом, минимальное покрытие функции имеет вид:

(2.17)

На основании (2.17) записывается система уравнений

(2.18)

Таблица 2.5

Преобразованное покрытие по Квайну

	Конституенты единицы
Импликанты	001 y	010 y	100 y	101 f
yf	1 0 –			V	V
y	0 – –	V	V
y	– – 0		V	V
y	– 0 –	V		V

Таблица 2.6

Минимальное покрытие по Квайну

	Конституенты единицы
Импликанты	001	010	101
	y	y	f
y f	1 0 –			V
y	0 – –	V	V

Заметим, что преобразование к виду не целесообразно, так как проводилась совместная минимизация.

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

Рис 2.3. Минимизирующие карты

2.4.5. Получить систему ФАЛ, описывающих преобразование двоичного кода в код Грея (четырёхразрядный).

Решение. Особенностью кода Грея является то, что при переходе к новой комбинации входных сигналов в выходных сигналах меняется только один разряд (табл.2.7).

Минимизация ФАЛ по табл. 2.7 (рис. 2.4) позволяет получит систему уравнений:

(2.19)

При минимизации удобно использовать правило:

если в карте Карно можно выделить два пересекающихся контура с общей нулевой частью, то импликанты, соответствующие этим контурам, объединяются знаком операции «сумма по модулю два».

2.4.6. Используя арифметико-логическое устройство, решить уравнение

минус (2.20)

при .

Решение. Переведем в двоичную систему

Проведем логическое умножение AB = 0001 и возьмем его инверсию . Выполнив сложение по модулю два,

Таблица 2.7

Таблица истинности для кода Грея

N тер-	Независимые переменные (входные сигналы)	Функции (выходные сигналы)
ма	Х3 Х2 Х1 Х0	Г3 Г2 Г1 Г0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

проведем вычитание и получим результат. Порядок расчета оформим в табл. 2.8.

Таблица 2.8

Арифметико-логические функции

A	B	AB			F
0	1	0	1	1	0
1	0	0	1	1	0
0	0	0	1	0	1
1	1	1	0	0	0

2.5. Вопросы для самопроверки

2.5.1. Какие логические функции представлены в табл. 2.9.

Рис.2.4. Минимизирующие карты для преобразователя двоичного кода в код Грея

Таблица 2.9

Булевы функции двух переменных

Независимые переменные	Зависимые переменные (функции)
X1	X2	Y1	Y2	Y3	Y4
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	1
1	1	1	0	1	0

Ответ. Y1 - И (конъюнкция); Y2 - неравнозначность (сложение по модулю два); Y3 - ИЛИ (дезъюнкция); Y4 - И - НЕ (отрицание конъюнкции).