Синтез логических управляющих устройств

МИКРОПРОЦЕССОРНАЯ ТЕХНИКА

До сих пор мы рассматривали динамические системы, в которых входные и выходные аналоговые сигналы представляют собой непрерывные функции времени. В технике и, особенно, в автоматике распространены также системы, изменение состояния которых происходит скачками. При этом рассмотрением переходных процессов пренебрегают.

Математические модели, отображающие физические или абстрактные явления в виде конечных состояний, называют конечными автоматами (КА). Схема КА изображена на рисунке 11.1. Различают два класса КА:

1) В комбинационных схемах значения выходных величин определяются только комбинациями значений входных параметров, независимо от их последовательности (электронные ключи, шифраторы/дешифраторы).

2) Значение выходных величин последовательностных логических устройств зависит от их состояния в момент внешнего воздействия – они обладают «памятью». Поэтому их реакция диктуется последовательностью изменения входных величин во времени. Это – счетчики, триггеры, регистры памяти и т.п.

При рассмотрении логической структуры КА считают, что входные и выходные переменные изменяются мгновенно в моменты времени, называемые тактами. При этом интервалы между тактами роли не играют. Такие особые состояния системы характеризуются внутренними переменными S (n).

Рис. 11.1. Схема конечного автомата

Работа КА описывается характеристическими функциями, задаваемыми:

1) таблицей переходов S (n+1) – состояний, в которые переходит КА из состояния S (n) при внешнем воздействии Х (n).

2) таблицей выходов Y (n) – номеров выходов, которые включаются при внешнем воздействии Х (n) на КА, находящийся в состояния S (n).

На рис. 11.2 приведена схема КА на четыре входа.

Рис. 11.2. Схема конечного автомата

Функционирование такого КА может быть описано характеристиче-скими функциями в табличной и графической форме.

Таблица переходов

Состояния	A	B	C	D
A	–	2 / 0	1 / 0	3 / 0
B	–	2 / 1	1 / 0	0 / 1
C	–	–	–	2 / 1
D	1 / 0 + 2 / 1	3 / 1 + 0 / 1	–	–

Граф представляет собой систему вершин (узлов), которые соединены дугами – переходами (рис. 11.3). Его вершины – это состояния КА, обозначения на дугах – номер входа / номер выхода.

Рис. 11.3. Схема конечного автомата

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

Входные и выходные переменные имеют два значения – лог.0 и лог.1. Например, логические функции одной переменной можно представить таким образом:

повторение (у = х) инверсия () (y = 0) независимость (y = 1)

x	y		x	y		x	y		x	y

Основные логические функции содержат две входные переменные – a и b. Четыре возможных комбинации этих входов дают 16 комбинаций выходов.

Таблица функций двух переменных

Название функции		Значения входов	Обозначение
a					символьное	буквенное
b
Нулевая
Стрелка Пирса					a + b(a ¯ b)	ИЛИ–НЕ
Запрет a					b ® a
Инверсия a					a	НЕ a
Запрет b					a ® b
Инверсия b					b	НЕ b
Неравнозначность					a ¹ b
Штрих Шеффера					a × b(a ­ b)	И–НЕ
Конъюнкция					a × b	И
Равнозначность					a º b
Повторение b					b
Импликация b					a ® b
Повторение a					a
Импликация a					b ® a
Дизъюнкция					a + b	ИЛИ
Единичная

Графические способы представления логических функций:

1) Круги Эйлера. Все множество состояний системы называется универсум и обозначается прямоугольником с буквой U. Каждое состояние (событие) изображается кружком с наименованием входа (a, b).

2) Диаграммы Вейча – графическое изображение таблицы состояний системы. Такая таблица состоит из групп клеточек (расположенных по строкам или по столбцам), в которых соответствующие входы принимают значения лог.0 или лог.1. При этом в самих клеточках указывают значения выхода (0 / 1). Например, конъюнкция двух переменных a и b

	b = 0	b = 1
a = 0
a = 1

Логическое произведение a × b (конъюнкция И) в булевой алгебре обозначается и изображается кругами Эйлера как пересечение событий

.

Отрицание конъюнкции И–НЕ называют «штрихом Шеффера» a ­ b.

Логическая сумма a + b (дизъюнкция ИЛИ) в булевой алгебре обозначается и изображается с помощью кругов Эйлера так

.

Отрицание дизъюнкции ИЛИ–НЕ называют «стрелкой Пирса» a ¯ b.

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

1) конъюнктивная (КНФ) – произведение сумм входных параметров, которым соответствуют ложные значения выходной величины – у = 0;

2) дизъюнктивная (ДНФ) – сумма произведений входных параметров, которым соответствуют верные значения выходной величины – у = 1.

Причем, если в каждом члене нормальной функции представлены все входные параметры (в прямом или инверсном виде), имеем совершенную нормальную форму (СКНФ или СДНФ).

Например, алгоритм принятия решения голосованием трех человек (a, b, c) можно представить в виде следующей таблицы соответствия.

a	b	c	y	Совершенные нормальные формы:
				1) конъюнктивная (произведение сумм)
				2) дизъюнктивная (сумма произведений) Слагаемые нормальных форм называются термами.

К логическим высказываниям применимы такие законы матлогики:

	Конъюнктивная форма	Дизъюнктивная форма
Переместительный	a × b = b × a	a + b = b + a
Сочетательный	a(bc) = b(ac) = c(ab)	(a + b) + c = a + (b + c)
Распределительный	a × (b + c) = a × b + a × c	a + b × c = (a + b)×(a + c)
Повторения	a × a = a	a + a = a
Двойной инверсии	a = a
Нулевого множества	a × 0 = 0	a + 0 = a
Универсального множества	a × 1 = a	a + 1 = 1
Дополнительности	a × a = 0	a + a = 1
Де Моргана	a × b = a + b	a + b = a × b

Правила де Моргана формулируются следующим образом:

1) конъюнктивная форма – отрицание произведений равно сумме отрицаний;

2) дизъюнктивная форма – отрицание суммы равно произведению отрицаний.

Покажем, как можно получить первое из этих правил:

a	b	ab	ab		a	b	a + b

Эти правила важны для упрощения (минимизации) логических выражений. Так, основатель математической логики английский математик Буль предложил все 16 функций двух переменных выразить через три функции: НЕ, И, ИЛИ, которые называют базисом Буля. Затем было показано, что и эти базисные функции можно реализовать с помощью всего одной функции И–НЕ (штрих Шеффера).

Посмотрим, как это можно сделать, пользуясь условными обозначениями логических элементов на схемах. Функция двух переменных изображается прямоугольником с двумя входами (слева) и одним выходом (справа). Внутри прямоугольника указывается условное обозначение операции: & (И) – логическое произведение, 1 (ИЛИ) – логическая сумма. Светлый кружок на выходе означает отрицание (инверсию НЕ).

Таким образом, штрих Шеффера – функция И–НЕ –

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

а функции базиса Буля

При выполнении сложных комбинационных схем стараются обойтись минимальным количеством однотипных логических элементов. Для упрощения логических выражений удобно применять специальные таблицы соответствия – карты Карно.

Пусть задана логическая функция двух переменных y = f (х₁, х₁) в виде следующей таблицы

х1	х2	y					х2
					х1

Каждой комбинации (набору) входных переменных {х_i} можно поставить в соответствие клетку карты Карно. Обозначения входов располагают по внешним сторонам карты напротив ее строк и столбцов, охватывая их фигурными скобками. Каждый вход делит карту на две равные части. В одной из них (напротив обозначения переменной) значение входа истинно (лог.1), в другой – ложно (лог.0).

В результате, соседние клетки отличаются значением лишь одной переменной х_i, причем при переходе в соседнюю клетку оно изменяется на противоположное (лог.0 / лог.1). В каждую клетку записывается значение логической функции y {0 или 1}, соответствующее набору входов.

По карте Карно можно составить различные аналитические выражения, описывающие условие срабатывания логического устройства y = f (х_і) = 1. Самое простое выражение получается при объединении максимального числа клеток, содержащих лог.1, в правильные конфигурации, например

Число m входов в терме, описывающем правильную конфигурацию из n клеток в карте Карно на N входов, равно

m = N – log ₂ n.

Для получения простейших логических выражений по карте Карно:

1. Выделяем правильные конфигурации максимальной площади, учитывая, что конфигурации могут пересекаться (т.е. одна и та же клетка может участвовать в различных конфигурациях). При этом карту Карно можно «склеивать» в цилиндр (как вертикально, так и горизонтально).

2. Каждую конфигурацию описываем логическим произведением входов (конъюнкцией).

3. Составляем дизъюнктивную нормальную форму (ДНФ) логической функции y = f (х_і) = 1 в виде суммы конъюнкций.

Дата добавления: 2014-01-07