Дискретная математика. Ерош И.Л - 15 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

15
Из полученной диаграммы Вейча легко выписывается минимальное
выражение для мажоритарной функции: F = x
2
x
3
Ú x
1
x
3
Ú x
1
x
3
, кото
рое полностью соответствует полученному выше в результате миними
зации с помощью правила склеивания.
Возьмем некоторую функцию F четырех аргументов, диаграмма Вей
ча которой имеет вид
Эта функция принимает значение 1 на пяти наборах, отмеченных на
диаграмме единицами. На остальных наборах функция принимает зна
чение 0. СДНФ этой функции содержала бы 5 конъюнкций ранга 4 каж
дая, объединенные знаками дизъюнкций. Однако из диаграммы Вейча
легко выписывается минимальное выражение функции в дизъюнктив
ной нормальной форме:
F = ùAùC Ú BùCD.
Области в диаграмме Вейча обозначаются так,
чтобы две соседние клетки соответствовали бы
«склеивающимся» конъюнкциям (т. е. конъюнк
циям, отличающимся значением только одного ар
гумента). Это обеспечивает наглядность миними
зации.
В общем случае области в диаграммах Вейча для
функций большого числа аргументов обозначаются
кодом Грэя. Особенностью этого кода является то,
что две соседние комбинации отличаются значением
только одного аргумента. Обычный двоичный код
этому условию не удовлетворяет. Код Грэя исполь
зуется в цифровых кодовых датчиках, что позволя
ет сделать ошибку равномерной при случайных сме
щениях токосъемников, при этом ошибка равна
2
–m
, где m – число двоичных разрядов кодового дат
чика. Это свойство кода Грэя используется для обо
значения областей в диаграммах Вейча.
В табл. 2.5 приведен код Грэя для 4х аргумен
тов (разрядов). Если требуется построить код Грэя
000000 00
100000 10
010000 11
110000 01
00100110
10101110
01101010
11100010
00010011
10011011
01011111
11010111
00110101
10111101
011
11001
11110001
Таблица 2.5

Страницы