Чикуров Н.Г. Логический синтез дискретных систем управления

Подождите немного. Документ загружается.

а б в

Рис. 3.6. Карты Карно (второй вариант)

а)

2121

xxxxF +=

1 1

б)

4321432143214321

xxxxxxxxxxxxxxxxF +++=

в)

321321321321

xxxxxxxxxxxxF +++=

1 1

Рис. 3.7. Представление логических функций на картах Карно

1 1

Рис. 3.8. Простая импликанта

Эта простая импликанта может быть представлена произведением,

содержащим одну переменную х

, так как вхождение 1 в этой функции

образуют произведения

xx и

xx .

Таким образом, склеивание

112212121

1)( xxxxxxxxx =×=+=+

мы выполнили графически (рис. 3.8).

Переменная, отсутствующая в произведении, имеет различные

значения для двух конституент соответствующей импликанты (рис. 3.9).

43214321

xxxxxxxxF += .

421

xxxF =

Рис. 3.9. Простая импликанта для карты четырех переменных

В общем случае простая импликанта соответствует произведению, в

котором всегда отсутствует одна переменная.

Четыре соседних конституенты образуют импликанту, которая

соответствует произведению без двух переменных. Те переменные, которые

не сохраняют постоянное значение на этой импликанте, опускают (рис. 3.10):

4321432143214321

xxxxxxxxxxxxxxxxF +++= .

1 1

xxF

Рис. 3.10. Импликанта из четырех конституент

Аналогичные виды простых импликант представлены на рис. 3.11.

1 1 1

1 х

1 1 х

1 1

211

xxF=

321

xxF=

421

xxF=

a б в

Рис. 3.11. Виды простых импликант

Другие виды простых импликант показаны на рис. 3.12.

Импликанта, полученная в результате склеивания некоторого

множества конституент, покрывает эти конституенты.

Для представления функции каждая 1 должна быть использована, по

крайней мере, в одной импликанте и ни в какой импликанте не должна быть

использована ни одна пустая клетка. В этом случае говорят, что все единицы

карты должны быть покрыты простыми импликантами (рис. 3.13).

Если выбраны самые большие импликанты и использовано по

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

дизъюнктивная нормальная форма (рис. 3.14).

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1

1 1

1 1 х

1 1 1 1

xF=

а б в

Рис. 3.12. Другие виды простых импликант

а x

б x

21211

xxxxx +=+

1211

xxxx

Рис. 3.13. Варианты покрытия единиц простыми импликантами

Дальнейшее упрощение возможно за счет вынесения общих

множителей за скобки.

Поучительный пример.

Минимизировать функцию

bccaabF ++=

Следует сначала привести функцию к совершенной дизъюнктивной

нормальной форме (СДНФ).

abc

aabcbbcaccabbccaabF

=+++++=++= )()()(

Теперь можно минимизировать логическую функцию обычным

способом (рис. 3.15).

1 1

Рис. 3.14. Минимизация логических функций в дизъюнктивной

нормальной форме

Рис. 3.15

1 1

1 1 1

42143131

xxxxxxxxF ++=

1 1 1 1

1 1

32132142143

xxxxxxxxxxxF +++=

1 1

1 1 1

231

xxxF

1 1 1

Принимая во внимание клетки карт Карно, не содержащие единиц, и

поступая с ними так же, как мы поступали с клетками с единицами, можно

получить двойственную форму, т.е. конъюнктивную нормальную форму

(рис. 3.16).

Рис. 3.16. Получение конъюнктивной нормальной формы

Часто при определении работы системы при некоторой комбинации

значений входных переменных безразлично, какое будет значение выхода.

Такие комбинации называют безразличными состояниями. На карте Карно

их можно помечать знаком ~ (тильда).

Для увеличения размеров простых импликант в любые клетки,

имеющие знак ~ , можно условно помещать единицы (рис. 3.17).

Рис. 3.17. Минимизация логической функции с использованием

безразличных состояний

В большинстве реальных систем число безразличных состояний

значительно превышает число обязательных и запрещенных состояний.

Чтобы не затенять карту большим количеством знаков ~ , мы в дальнейшем

~ ~ 1

1 1 ~ ~

1 1

~ ~

421

xxxF +=

1 1

42143131

xxxxxxxxF ++=

0 0

42143131

xxxxxxxxF ++=

будем обозначать обязательные состояния знаком 1 , запрещенные – знаком

0, а для безразличных состояний оставлять пустые клетки (рис. 3.18).

Рис. 3.18. Обозначение безразличных состояний в виде пустых клеток

Для минимизации логических функций с большим количеством

(7¸ 8) переменных требуются достаточно обширные карты Карно, что

усложняет процедуру минимизации.

Чтобы успешно решать такие задачи, необходимы правила

формального выделения простых импликант на картах Карно. Прежде чем

сформулировать эти правила, рассмотрим два понятия: ось симметрии и поле

симметрии карты Карно.

Ось симметрии – это любая прямая, проведенная на карте Карно

параллельно одной из её сторон и касающаяся конца одной из скобок (сами

стороны не являются осями симметрии) (рис. 3.19). Оси симметрии,

проходящие через середину карты, называются главными.

Рис. 3.19. Оси симметрии карты Карно

Ось

симметрии

Ось

си

мметрии

Главная ось

симметрии

0 1

1 1

1 1 0 0

0 0

421

xxxF +=

Поле симметрии – это все клетки, расположенные слева и справа

(или сверху и снизу) от оси симметрии на расстоянии, равном 1/2 длины

скобки, с которой соприкасается данная ось симметрии (рис. 3.20).

Рис. 3.20. Поле симметрии карты Карно

Замечание:

Длина наружных скобок карты при условном увеличении числа

переменных возросла бы в два раза. Поэтому ширину поля симметрии для

оси, касающейся наружной скобки, принимают равной не половине её

длины, а всей её длине.

Теперь сформулируем правила выделения простых импликант на

карте Карно:

1) Фигура простой импликанты должна иметь форму

прямоугольника (с учетом замкнутости противоположных краёв карты) и

содержать 2

клеток, где 2

и 2

- количество клеток, содержащихся в

каждой из сторон прямоугольника (k1 и k2 – простые числа).

2) Фигура импликанты должна быть симметричной относительно её

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

симметрии каждой из этих осей (рис. 3.21).

3) Фигура импликанты может состоять из нескольких частей. Тогда

общее количество осей симметрии для такой импликанты в одном из

направлений (горизонтальном или вертикальном) определяется по формуле

N = 2n – 1,

где n – количество частей, из которых состоит импликанта в заданном

направлении;

N – количество осей симметрии.

На рис. 3.22 условно показаны три варианта таких импликант.

В этом случае импликанта должна быть симметричной относительно

каждой из осей симметрии в пределах её поля симметрии (рис. 3.23).

Поле симметрии

Ось

симметрии

0 0 0

0 1 0

Неверно! Импликанта вышла за пределы поля симметрии.

0 0 0

0 1 0

Верно! Импликанта находится внутри поля симметрии

Рис. 3.21. Условия симметрии импликанты

2-я ось

симметрии

1-я ось симметрии

Поле симметрии

для 1-й оси

2-я ось

симметрии

1-я ось

симметрии

Поле симметрии

для 2-й оси

a) n = 1; N = 1

б) n = 2; N = 3

в) n = 3; N = 5

Рис. 3.22. Оси симметрии импликант

Импликанта

Ось

симметрии

Оси

симметрии

Импликанта

Оси

симметрии

Импликанта