Metod_B1.V.DV.05.02_09.03.01_04.06.2016_pr

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

Для склеивания пар применяются те же правила, но добавляется еще одно условие: разности у склеиваемых пар должны быть одинаковы. При этом оказывается, что переменные в выражении одинаковы.

	0	0	*
	1	1	*	(0, 1),	(1) *	(0, 1, 4, 5),		(1, 4)	(с)
		4	*
				(0, 4),	(4) *	(0, 1, 4, 5),		(4, 1)
	2	3	*
				(1, 3),	(2) (а)	(4, 6, 12, 14),		(2, 8)	(d)
		5	*
				(1, 5),	(4) *	(4, 6, 12, 14),		(8, 2)
		6	*
				(4, 5),	(1) *
						(10, 11, 14, 15) (1, 4)			(e)
		10	*
				(4, 6) ,	(2) *	(10, 11, 14, 15)		(4, 1)
		12	*
				(4, 12),	(8) *
	3	11	*
				(3, 11),	(8) (в)
		14	*
				(6, 14),	(8) *
			*
	4	15		(10, 11), (1) *
				(10, 14), (4) *
				(12, 14), (2) *
				(11, 15), (4) *
				(14, 15), (1) *

Возьмем, например, пары (0, 1),(1) и (1, 3), (2). 0 и 1 склеиваются, 1 и 3

тоже, но разности у них не одинаковы – поэтому склеивание невозможно (у

первой пары нет переменной D, у второй пары нет переменной С – они,

конечно, и не могут склеиваться).

В результате склеивания пишем уже четверки (0, 1, 4, 5) и две разности

(1, 4), т.е. в результирующем выражении нет 2-х переменных B и D.

После завершения этих склеиваний получают, если возможно,

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

Обозначим пары и четверки, которые не участвовали в склеивании,

латинскими буквами. Тогда

f (A, B,C, D) a b c d e . При получении

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

берут любую из конституент 1, участвующих в операции склеивания, и

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

Например, для импликанты а получим: 0001 = ABCD . Разность 2

говорит о том, из выражения необходимо исключить переменную с весом 2,

т.е. С. Тогда а = ABD .

Аналогично получим:

=

AВC

для в: 0011 = ABСD , в =

D , d = ВD , для e: 1111 = f (A, B,C, D) ABD BCD

BCD , для с: 0001 =	ABCD , с = AC , для d: 0100 =
AC, e = АС. В результате получим:
AC BD AC .

Занятие 2. Диаграммы Карно-Вейча для полностью определённых ПФ.

Минимизация не полностью определённых ПФ. Построение

комбинационных схем

Диаграмма Вейча является фактически таблицей истинности ПФ,

которая представляется не в виде столбцов, а в виде специальных карт.

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

Переключательные функции двух аргументов

Пример 2.6. f (A, B) AB AB AB . Диаграмма Вейча имеет следующий вид:

Для представления функции с помощью диаграмм Вейча или карт Карно следует записать 1 в клетках таблицы, соответствующие наборам,

Тогда: f (A, B) A B . на которых функция равна 1, а 0 в остальные клетки.

При склеивании соседние конституенты будем обводить овалом.
Переключательные функции трех аргументов
Пример 2.7.		f (A, B,С) ABС ABС АВС АВС ABС АВС .
Диаграмма Вейча состоит из 8 клеток и имеет следующий вид:
	00	01	11	10
BC				Тога f (A, B,C) AB AB C .
A
0	1	0	1	1
1	1	1	0	1

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

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

(импликант).

Переключательные функции четырех аргументов

В диаграммах Вейча и картах Карно для четырех аргументов соседними клетками являются крайние клетки каждого столбца и строки.

Поэтому такую диаграмму следует рассматривать как свернутую в тор.

Пример 2.8.			f (A, B,C, D) (0, 1, 4, 5, 9, 10, 11, 13, 14, 15).
Диаграмма Вейча состоит из 16 клеток и имеет следующий вид:
CD	00	01	11	10	Построим схему в булевом базисе
AB					(рис. 2.1):
00	1	1	0	0
01	1	1	0	0		&
11	0	1	1	1		&		D	1
										f
10	0	1	1	1	A	&	AC
f (A, B,C, D) AC CD AC .									Рис. 2.1
Построим схему,				реализующую функции f (A, B,C, D)				в базисе И-НЕ (штрих
Шеффера). Для этого осуществим переход от булевого базиса к базису И-НЕ:
f (A, B,C, D) AC CD AC AC CD AC .
Схема,		реализующая			функцию	&		AC
					И-НЕ,
f (A, B,C, D)			в	базисе
приведена на рис. 2.2.						&		CD	&	f
					A	&
									Рис. 2.2
	Построим схему, реализующую функции					f (A, B,C, D) в базисе ИЛИ-НЕ
(стрелка Пирса). Для этого осуществим переход от булевого базиса к базису

ИЛИ-НЕ:

Схема, реализующая

f (A, B,C, D)

в базисе

приведена на рис. 2.3.

f (A, B,C, D) AC СD AC A C C D A C .

функцию ИЛИ-НЕ,

A	1
C
C		1		1	f
	1	CvD	•
	1	AvC
										Рис. 2.3
		Переключательная функция для пяти аргументов
Пример 2.8. f (A, B,C, D, Е) (2, 3, 6, 7, 9, 10, 11, 13, 14, 15, 16, 18, 20, 22, 24,
26, 28, 30). Диаграмма Вейча состоит из 32 клеток и имеет следующий вид:
		CDE	000	001	011	010	110	111	101	100
		AB
		00	0	0	1	1	1	1	0	0
		01	0	1	1	1	1	1	1	0
		11	1	0	0	1	1	0	0	1
		10	1	0	0	1	1	0	0	1
				f (A, B,C, D, E) AD ABE AE
		В этой диаграмме, как и прежде, соседними являются крайние клетки
каждого столбца и строки левой и правой половин. Кроме того, соседними
являются клетки расположенные на одной строке и равноудаленные от
центральной вертикальной линии, т.е. диаграмму следует представить ещё и
сложенную по центральной вертикальной линии как страница книги.

Преобразование функции в минимальную конъюнктивную

нормальную форму (КНФ)

Для того, чтобы получить выражение заданной ПФ в форме,

содержащей минимальное количество букв, следует, кроме минимальной ДНФ, получить также минимальную КНФ, и выбрать ту из них, которая

содержит меньшее число букв. Существуют различные методы минимизации КНФ. Рассмотрим один из таких методов, основанный на минимизации

функции f и в переходе			с помощью формулы де Моргана к функции f. При
минимизации	f	можно	использовать все методы, которые применялись

ранее при нахождении минимальной ДНФ. После получения минимальной

ДНФ функции f	с помощью формул де Моргана переходят к минимальной
КНФ функции f.
Пример. Найти	минимальную КНФ функции	f (A, B,C, D) (4,14) 1.

Диаграмма Вейча имеет вид:

CD

AB 00 01 11 10 00 0 0 0 0

01 1 0 0 0

11 0 0 0 1

10 0 0 0 0

Из диаграммы получим:

f (A, B,C, D) D B AC AC .

Тогда:

f (A, B,C, D) D B AC ACDB(A C)( A C)

– минимальная КНФ.

Минимизация не полностью определенных ПФ

В ЭВМ часто применяются КС, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называются

запрещенными. Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е.

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

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

Пример. Найти минимальную ДНФ и минимальную КНФ не полностью

определенной ПФ:	f (A, B,C, D) (2,12,13) 1	,	f (A, B,C, D) (5,9,15) 0	. На
остальных наборах функция не определена.

CD
AB	00 01 11 10
00	-	-	0	1
01	-	0	-	-
11	1	1	0	-
10	-	0	-	-

f (A, B,C, D) D ABC –

– минимальная ДНФ,

f (A, B,C, D) AD BD CD ;

f (A, B,C, D) AD BD CD(A D)(B D)(C D)

– минимальная КНФ.

Минимизация систем переключательных функций

Работа КС, имеющей n входов и m выходов, описывается системой m

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

x1	у1
x2	у2
	КС
xn	уm

Рис.2.4. Комбинационная схема

Если провести минимизацию ПФ, входящих в систему независимо друг от друга, то получится схема, содержащая m изолированных цепей, в общем случае не минимальная. Однако эту схему можно существенно упростить за счет объединения участков схемы, реализующих одинаковые члены. Общая идея минимизации схем со многими выходами сводится к получению

выражений для системы ПФ, в которых наилучшим образом используются конъюнкции, общие для нескольких функций. Покажем, как производится минимизация системы ПФ.

Пример. Пусть дана система из трех ПФ от 4-х аргументов:

CD
	00 01 11 10
00	-	-	0	1
01	0	-	0	-
11	-	1	0	0
10	-	1	-	1

CD

AB 00 01 11 10

00	1	0	0	-
01	-	0	-	-
11	1	-	1	-
10	-	1	0	1

CD
AB	00 01 11 10
00	1	1	0	1
01	0	0	0	0
11	-	1	-	1
10	1	1	0	1

f	(A, B,C, D) ВD
1

AC

;

f f

2

3

(A, B,C, D) ВD (A, B,C, D) ВD

AC AC

АВ АВ

f	(A,
1
BC

B,C, D) AB

f	(A, B,C, D)
2

;

BC

.

Схема, реализующая систему ПФ, приведена на рис. 2.5.

	&
A	&
A	&
	&

1

A

AB

f

1 f

1 f

Рис. 2.5

Занятие 3. Конечные автоматы (КА). Способы их задания.

Элементарные автоматы.

Для задания любого КА S необходимо задавать совокупность из пяти

объектов:	S{A, X, Y, , },
где A =	{a0, a1, a2, ..., am, ..., aM} – множество состояний автомата,

X = {x1, x2, …, xf ,…, xF} – множество входных сигналов или входной алфавит,

Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = [a(t), x(t)],

– функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = [a(t), x(t)].

Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = [a(t), x(t)] и переходит в состояние a(t + 1) = [a(t), x(t)].

Другими словами абстрактный автомат каждой паре символов a(t) и x(t)

ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.

Кроме детерминированных автоматов существуют вероятностные или

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

детерминированные автоматы.

Применяемые на практике автоматы принято разделять на два класса – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Функционирование автоматов строго подчиняется определённым законам. Законы функционирования автоматов описываются следующими системами уравнений:

Автомат Мили:

Автомат Мура:

a(t + 1) = [a(t), x(t)] y(t) = [a(t), x(t)]

t = 1, 2, 3…

a(t + 1) = [a(t),x(t)] y(t) = [a(t)]

t = 1, 2, 3…

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.

Способы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, , }, т.е. необходимо описать входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов .

При этом среди множества A = {a0, a1, …, aМ} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0.

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

	Табличный способ
При табличном способе задания автомат Мили описывается двумя
таблицами: таблицей переходов и таблицей выходов:
Таблица переходов	Таблица выходов

xj/ ai	a0	…	aМ
x1	(a0, x1)	…	(aМ, x1)
…	…	…	…
xF	(a0, xF)	…	(aM, xF)

xj/ai	a0	…	aM
x1	(a0, x1)	…	(aM, x1)
…	…	…	…
xF	(a0, xF)	…	(aM, xF)

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = [ ai, xj], в которое автомат перейдет из состояния ai