Реферат: Математичекие основы теории систем анализ сигнального графа и синтез комбинационных схем

Гипероглавление:
Министерство специального и высшего образования
Хабаровский государственный технический университет
Кафедра «Автоматика и системотехника»
Курсовой проект
По предмету: Математические основы теории систем
Выполнил студент  гр. УИТС-21у:
Д.И. Хоменко
Проверил:
В.В. Воронин
г. Хабаровск
2003 г. ЗАДАНИЕ
РЕФЕРАТ
Содержание
Задание 1. Анализ сигнальных графов.
1.1       Выбор варианта задания
1.4 Матрица инцидентности
1.5 Построение бинарных матриц путей выхода для заданных контрольных точек.
1.6 Бинарная матрица контуров.
1.7 Матрица касания контуров
1. 8 Матрица касания путей и контуров
1.9 Формула Мэзона для заданного сигнального графа
Для х13
Задание 2. Синтез комбинационных схем.
2.1 Определение поставленной задачи
2.2 Составление логических функций
2.2.1 Дизъюнктивная совершенная нормальная форма
2.2.2 Конъюнктивная совершенная нормальная форма
2.3 Минимизация булевых функций
2.3.1 Пример минимизации методом неопределенных коэффициентов
2.3.2 Пример минимизации методом Квайна-Мак-Класки.
2.3.3 Пример минимизации картами Карно
2.4 Совместная минимизация всех функций
2.5 Запись МДНФ в заданном базисе
Таблица 3.3.3
Таблица 3.3.4
Таблица 3.4.5
3.4 Обобщенная функциональная схема структурного автомата
3.5 Каноническая система логических уравнений
3.6 Минимизация логических функций
3.7 Построение комбинационной схемы автомата с памятью
ЗАКЛЮЧЕНИЕ
Приложение 1.
Приложение 2
--PAGE_BREAK--    продолжение
--PAGE_BREAK--
Задание 1. Анализ сигнальных графов. 1.1       Выбор варианта задания
Из букв, образующих фамилию, имя и отчество получим три множества А, В и С символов русского алфавита.

Хоменко А={Х, О, М, Е, Н, К}

Дмитрий
B
={Д, М, И, Т, Р, Й}

C
={И, Г, О, Р, Е, В, Ч}

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

½
A
È
B
½
=
½
{ Х, О, М, Е, Н, К, Д, И, Т, Р, Й }
½
=11

½
(
A
È
B
)
Ç
С
½
=
½
{Е, И, О, Р}
½
=4

½
C
\
A
½
=
½
{И, Г, Р, В, Ч}
½
=5

½
A
È
B
½
=
½
U
\
A
È
B
½
=33-11=22

По полученным результатам построим схему автоматического управления системой.
<img width=«611» height=«343» src=«ref-1_112969446-6457.coolpic» v:shapes="_x0000_s4184 _x0000_s2048 _x0000_s1165 _x0000_s1166 _x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188 _x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1193 _x0000_s1194 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1204 _x0000_s1205 _x0000_s4164 _x0000_s4165 _x0000_s4166 _x0000_s4167 _x0000_s4168 _x0000_s4169 _x0000_s4170 _x0000_s4171 _x0000_s4172 _x0000_s4173 _x0000_s4174 _x0000_s4175 _x0000_s4176 _x0000_s4177 _x0000_s4178 _x0000_s4179 _x0000_s4180 _x0000_s4181 _x0000_s4182 _x0000_s4183">
Вершины отмеченные серым цветом – это заданные контрольные точки.
1.3 Матрица смежности

Матицей смежности графа G называется матрица R=[rij] размером nxn, где n – число вершин графа, в которой

<img width=«284» height=«53» src=«ref-1_112975903-837.coolpic» v:shapes="_x0000_i1025">



x

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

y

x



1



























x1





1

1























x2









1





















x3









1





















x4











1





1

1











x5













1

















x6















1















x7











1

















1

x8





















1









x9





















1









x10





























1

x11

























1





x12



























1



x13

1





















1







y























1








    продолжение
--PAGE_BREAK--1.4 Матрица инцидентности
Матрицей инцидентности графа G называется матрица S=[sij] размера nxm, где n – число вершин графа, а m – число дуг графа, в которой:

<img width=«209» height=«83» src=«ref-1_112976740-878.coolpic» v:shapes="_x0000_i1026">

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






w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

x

















1





















-1

x1

1

1













-1























x2

-1

















1





















x3



-1

















1



















x4













1

1



-1

-1

1

















x5









1













-1

-1















x6









-1

1





























x7











-1













1

1













x8













-1















1











x9















-1















1









x10





























-1

-1

1







x11





1





























-1

-1



x12





-1

1

































x13







-1





























1

1

y



























-1





-1

1






    продолжение
--PAGE_BREAK--1.5 Построение бинарных матриц путей выхода для заданных контрольных точек.
Согласно заданию на курсовую работу выделено множество К контрольных точек (выходов). Оно имеет вид:

К={
x
1
,
x
4
,
y
,
x
13
}

Построим матрицы путей для каждого из этих выходов.

Бинарная матрица P
=
||
pij
||путей размера lxm, где l
– число путей, строится по следующему правилу:

<img width=«251» height=«51» src=«ref-1_112977618-700.coolpic» v:shapes="_x0000_i1027">

Матрица путей выхода для
x
1



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

















1

























Матрица путей выхода для
x
4



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1















1

1





















2



1













1



1





















Матрица путей выхода для
y



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1















1

1



1



1

1











2

1











1



1

1













1







3

1













1

1

1











1

1







4



1





1

1





1



1

1



1













5



1









1



1



1



1



1



1







6



1











1

1



1









1

1









    продолжение
--PAGE_BREAK--Матрица путей выхода для
x13



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

x

1



1

1

1

1





1

1



1



1



1









x1

1



1

1





1



1

1









1



1

1





x2

1



1

1







1

1

1











1

1

1





x3



1

1

1

1

1





1



1

1



1













x4



1

1

1





1



1



1







1



1

1





x5



1

1

1







1

1



1









1

1

1







    продолжение
--PAGE_BREAK--1.6 Бинарная матрица контуров.
Бинарная матрица контуров C
=
||
cij
||
размера h
xm, где  h— число контуров, строится по следующему правилу:

<img width=«268» height=«51» src=«ref-1_112978318-726.coolpic» v:shapes="_x0000_i1028">

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



w1

w2

w3

w4

w5

w6

w7

w8

u9

u10

u11

u12

u13

u14

u15

u16

u17

u18

u19

u20

1

1



1

1

1

1





1

1



1



1







1



1

2

1



1

1





1



1

1









1



1

1



1

3

1



1

1







1

1

1











1

1

1



1

4



1

1

1

1

1





1



1





1







1



1

5



1

1

1





1



1



1







1



1

1



1

6



1

1

1







1

1



1









1

1

1



1

7









1

1













1















8





1

1





























1




    продолжение
--PAGE_BREAK--1.7 Матрица касания контуров
Бинарная матрица контуров Ck
=
||
cij
||
размера h
xk, где  k— число контуров, строится по следующему правилу:

<img width=«349» height=«48» src=«ref-1_112979044-830.coolpic» v:shapes="_x0000_i1029">





1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

1

2

1

1

1

1

1

1

1

1

3

1

1

1

1

1

1

1

1

4

1

1

1

1

1

1

1

1

5

1

1

1

1

1

1

1

1

6

1

1

1

1

1

1

1

1

7

1

1

1

1

1

1

1



8

1

1

1

1

1

1



1



    продолжение
--PAGE_BREAK--1. 8 Матрица касания путей и контуров
Бинарная матрица контуров Cl
=
||
cij
||
размера l
xk, где  l— число путей для заданного выхода, строится по следующему правилу:

<img width=«333» height=«48» src=«ref-1_112979874-807.coolpic» v:shapes="_x0000_i1030">
Для
x
1



1

2

3

4

5

6

7

8

1

1

1

1

1

1

1







Для
x
4



1

2

3

4

5

6

7

8

1

1

1

1

1

1

1





2

1

1

1

1

1

1







Для
y




1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1



2

1

1

1

1

1

1





3

1

1

1

1

1

1





4

1

1

1

1

1

1

1



5

1

1

1

1

1

1





6

1

1

1

1

1

1







Для
x13



1

2

3

4

5

6

7

8

1

1

1

1

1

1

1

1

1

2

1

1

1

1

1

1



1

3

1

1

1

1

1

1



1

4

1

1

1

1

1

1

1

1

5

1

1

1

1

1

1



1

6

1

1

1

1

1

1



1


    продолжение
--PAGE_BREAK--1.9 Формула Мэзона для заданного сигнального графа
Используя универсальную топологическую формулу, носящую имя Мэзона, можно получить передачу между любыми двумя вершинами. Формула имеет следующий вид:
<img width=«105» height=«56» src=«ref-1_112980681-412.coolpic» v:shapes="_x0000_i1031">

где <img width=«23» height=«27» src=«ref-1_112981093-120.coolpic» v:shapes="_x0000_i1032"> — передача k-го пути между вершинами jи r
;<img width=«12» height=«23» src=«ref-1_112981213-73.coolpic» v:shapes="_x0000_i1033">D
— определитель графа. Он характеризует контурную часть графа и имеет следующий вид:

<img width=«296» height=«39» src=«ref-1_112981286-708.coolpic» v:shapes="_x0000_i1034">

где, L– множество индексов контуров, L
2— множество пар индексов не касающихся контуров, L
3— множество троек индексов не касающихся контуров, Ki– передача i-го контура, <img width=«25» height=«27» src=«ref-1_112981994-122.coolpic» v:shapes="_x0000_i1035">  — минор пути, это определитель подграфа, полученного удалением из полного графа вершин и дуг, образующих путь <img width=«23» height=«27» src=«ref-1_112981093-120.coolpic» v:shapes="_x0000_i1036">.

D=1-К1-К2-К3-К4-К5-К6-К7-К8+К7К2+К7К3+К7К5+К7К6+К7К8=1- К1-К2-К3-К4-К5-К6-К7-К8+К7(К2+К3+К5+К6+К8)

К1=
W1
W3
W4
W5
W6

<place w:st=«on»>K2=
W3
W4
W7

K3=
W1
W3
W4
W8

K4=
W2
W3
W4
W6
W7

K5=
W2
W3
W4
W7

K6=
W2
W3
W4
W8

K7=
W5
W6

K8=
W3
W4

D=1-
W3
W4(
W1
W5
W6+
W7+
W1
W8+
W2
W6
W7+
W2
W7+2
W2
W8+ 1)+
W5
W6(
W3
W4(
W7+
W1
W5
W6+
W2
W7+
W2
W8+1)-1)
Для
x1

<img width=«51» height=«25» src=«ref-1_112982236-149.coolpic» v:shapes="_x0000_i1037">

<img width=«257» height=«25» src=«ref-1_112982385-405.coolpic» v:shapes="_x0000_i1038">

<img width=«314» height=«49» src=«ref-1_112982790-783.coolpic» v:shapes="_x0000_i1039">

Для
x4

<img width=«65» height=«24» src=«ref-1_112983573-170.coolpic» v:shapes="_x0000_i1040">  <img width=«259» height=«25» src=«ref-1_112983743-407.coolpic» v:shapes="_x0000_i1041">

<img width=«67» height=«24» src=«ref-1_112984150-175.coolpic» v:shapes="_x0000_i1042">  <img width=«259» height=«25» src=«ref-1_112984325-407.coolpic» v:shapes="_x0000_i1043">

<img width=«407» height=«49» src=«ref-1_112984732-997.coolpic» v:shapes="_x0000_i1044">


Для
y


<img width=«99» height=«27» src=«ref-1_112985729-229.coolpic» v:shapes="_x0000_i1045">


<img width=«79» height=«27» src=«ref-1_112985958-200.coolpic» v:shapes="_x0000_i1046">

<img width=«79» height=«27» src=«ref-1_112986158-204.coolpic» v:shapes="_x0000_i1047">

<img width=«100» height=«27» src=«ref-1_112986362-234.coolpic» v:shapes="_x0000_i1048">

<img width=«81» height=«27» src=«ref-1_112986596-199.coolpic» v:shapes="_x0000_i1049">

<img width=«80» height=«27» src=«ref-1_112986795-203.coolpic» v:shapes="_x0000_i1050">

<img width=«104» height=«27» src=«ref-1_112986998-224.coolpic» v:shapes="_x0000_i1051">


<img width=«253» height=«27» src=«ref-1_112987222-416.coolpic» v:shapes="_x0000_i1052">
    продолжение
--PAGE_BREAK--<img width=«253» height=«27» src=«ref-1_112987638-416.coolpic» v:shapes="_x0000_i1053">
<img width=«104» height=«27» src=«ref-1_112988054-223.coolpic» v:shapes="_x0000_i1054">
<img width=«253» height=«27» src=«ref-1_112988277-412.coolpic» v:shapes="_x0000_i1055"> <img width=«253» height=«27» src=«ref-1_112988689-412.coolpic» v:shapes="_x0000_i1056"> <img width=«644» height=«49» src=«ref-1_112989101-1443.coolpic» v:shapes="_x0000_i1057"> Для х13
<img width=«147» height=«25» src=«ref-1_112990544-286.coolpic» v:shapes="_x0000_i1058">

<img width=«127» height=«25» src=«ref-1_112990830-262.coolpic» v:shapes="_x0000_i1059">

<img width=«88» height=«25» src=«ref-1_112991092-208.coolpic» v:shapes="_x0000_i1060">

<img width=«148» height=«25» src=«ref-1_112991300-293.coolpic» v:shapes="_x0000_i1061">

<img width=«129» height=«25» src=«ref-1_112991593-265.coolpic» v:shapes="_x0000_i1062">

<img width=«128» height=«25» src=«ref-1_112991858-265.coolpic» v:shapes="_x0000_i1063">

<img width=«59» height=«25» src=«ref-1_112992123-161.coolpic» v:shapes="_x0000_i1064">

<img width=«112» height=«25» src=«ref-1_112992284-231.coolpic» v:shapes="_x0000_i1065">
<img width=«112» height=«25» src=«ref-1_112992515-233.coolpic» v:shapes="_x0000_i1066">
<img width=«59» height=«25» src=«ref-1_112992748-161.coolpic» v:shapes="_x0000_i1067">
<img width=«112» height=«25» src=«ref-1_112992909-232.coolpic» v:shapes="_x0000_i1068"> <img width=«112» height=«25» src=«ref-1_112993141-232.coolpic» v:shapes="_x0000_i1069"> <img width=«430» height=«49» src=«ref-1_112993373-1081.coolpic» v:shapes="_x0000_i1070">
Задание 2. Синтез комбинационных схем. 2.1 Определение поставленной задачи
Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет nвыходов и mвходов. На каждый вход может быть подан произвольный символ конечного множества Х, называемого входным алфавитом. Совокупность входных символов, поданных на входы устройства, образует входное слово Рi
в алфавите Х. На выходе устройства появляются выходные слова Qj, составленные из символов выходного алфавита Y. В силу конечности алфавитов X
,
Yи слов Pi
,
Qj(длина слова всегда равна m, а выходного слова — h) общее количество различных входных и выходных слов также конечно.

Элементарный такт работы устройства состоит в том, что при появлении на входе слова Рiустройство выдает на выходах комбинацию символов yi, образующих слово Qj. Если слово Qjопределяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти, или комбинационной схемой.

Алгоритм функционирования комбинационного устройства будет определен, если задать таблицу соответствия {Pi
}->{
Qj
}для всех слов Pi. Если входной алфавит Xсостоит из Kразличных символов, в таблице соответствия будет Kmстрок. Так как символы входного и выходного алфавитов принимают только два значения (в данном случае «1» или «0»), то при синтезе  и анализе логического устройства применяется булева алгебра.

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

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

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

Код Грея является циклическим кодом, получается из двоично-десятичного кода по следующим правилам:

1.     пусть gn
…..
g
1
g
– кодовый набор в коде Грея с (n+1) разрядами.

2.     bn
…
b
1
b
– соответствующее двоичное число.

3.     тогда разряд g0 получается из следующего выражения:

gi=bi
Å
bi+1; 0
£
i
£
n-1; gn=bn; где Å— символ операции сложения по модулю 2 (0+0=0, 0+1=1, 1+0=1, 1+1=0).

Закодируем входной алфавит в соответствии с этими правилами и с учетом значений yiсоставим таблицу истинности (см. таблицу 2.1.1).

Таблица 2.1.1

Выходной символ

Сигнал (код)

y1

y2

y3

y4

y5

y6

y7



x4

x3

x2

x1

0

0

0

0

0

1

1

1

1



1

1



1

0

0

0

1







1



1



1

2

0

0

1

1



1

1



1

1

1

3

3

0

0

1

0





1

1

1

1

1

2

4

0

1

1

0

1





1

1

1



6

5

0

1

1

1

1



1

1

1



1

7

6

0

1

0

1

1

1

1

1

1



1

5

7

0

1

0

0







1



1

1

4

8

1

1

0

0

1

1

1

1

1

1

1

12

9

1

1

0

1

1



1

1

1

1

1

13



























10

1

0

1

0

*

*

*

*

*

*

*

8

11

1

0

1

1

*

*

*

*

*

*

*

9

12

1

1

1

0

*

*

*

*

*

*

*

10

13

1

1

1

1

*

*

*

*

*

*

*

11

14

1

0

0

0

*

*

*

*

*

*

*

14

15

1

0

0

1

*

*

*

*

*

*

*

12



Если не удается заполнить  все строки этой таблицы, то функция называется не полностью определенной, а наборы на которых она не определена, носят название запрещенных. В этом случае схема называется неполной. Доопределение функции производится произвольно.
    продолжение
--PAGE_BREAK--
2.2 Составление логических функций
Существует два способа записи логической функции по таблице истинности: запись дизъюнктивной совершенной нормальной формы (ДСНФ) и запись конъюнктивной совершенной нормальной формы (КСНФ). В первом случае образуют дизъюнкции, соответствующие входным наборам, на которых функция принимает значение «1», их объединяют знаками конъюнкции. Во втором случае организуют конъюнкции, соответствующие входным словам, на которых функция принимает значение «0», эти конъюнкции объединяют знаками дизъюнкции. Рассмотрим на примере функции у3.
2.2.1 Дизъюнктивная совершенная нормальная форма
Введем понятие логической степени, которою будем обозначать <img width=«27» height=«20» src=«ref-1_112994454-106.coolpic» v:shapes="_x0000_i1071">. Тогда, логическая степень будет определяться по формуле (2.1)

<img width=«112» height=«48» src=«ref-1_112994560-343.coolpic» v:shapes="_x0000_i1072">              (2.1)

Любую функцию от nпеременных можно представить в виде (см.(2.2))

<img width=«268» height=«36» src=«ref-1_112994903-557.coolpic» v:shapes="_x0000_i1073">      (2.2)

  <img width=«29» height=«36» src=«ref-1_112995460-178.coolpic» v:shapes="_x0000_i1074">означает, что коллективные члены формируются только для таких наборов (α1, α2,…, αn) для которых функция принимает единичное значение.

Форма (2.2) определяет алгоритм перехода от таблицы  истинности к аналитическому ее виду. Для такого перехода используется следующий алгоритм:

а) Выбрать в таблице истинности все наборы, в которых функция               обращается в единицу.

б) Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент хiвходит в данный набор как «1», то он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.

в) Все  полученные конъюнкции объединяют знаком дизъюнкции.

Для функции у3 СДНФ будет иметь вид:

<img width=«527» height=«24» src=«ref-1_112995638-734.coolpic» v:shapes="_x0000_i1075">
2.2.2 Конъюнктивная совершенная нормальная форма
Любую функцию от nпеременных можно представить в виду:

f=  <img width=«165» height=«36» src=«ref-1_112996372-424.coolpic» v:shapes="_x0000_i1076">

<img width=«29» height=«36» src=«ref-1_112996796-174.coolpic» v:shapes="_x0000_i1077">означает, что коллективные члены формируются только для таких наборов, (α1, α2, …, αn) для которых функция принимает нулевое значение.

Следующий алгоритм позволяет перейти от табличной записи функции к СКНФ:

а) Выбрать в таблице истинности все наборы, в которых функция обращается в «0».

б) Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом  если аргумент хiвходит в данный набор как «0», то он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается  его отрицание.

в) Все полученные дизъюнкции объединяют знаком конъюнкции

Функция У3 в виде СКНФ будет иметь вид:

<img width=«392» height=«24» src=«ref-1_112996970-547.coolpic» v:shapes="_x0000_i1078">
    продолжение
--PAGE_BREAK--2.3 Минимизация булевых функций
Минимизация сводится к поиску минимальных форм (ДНФ и КНФ). Минимальной форме соответствует самая простая логическая схема, реализующая данную функцию и требующая минимальных аппаратных затрат.

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

1.     метод неопределенных коэффициентов

2.     метод Квайна-Мак-Класки

3.     карты Карно

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

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

<img width=«629» height=«421» src=«ref-1_112997517-15039.coolpic» v:shapes="_x0000_i1079">
Находим выражения, имеющие в правой части ноль. Исходя из определения дизъюнкции вычеркиваются все элементы  в этих уравнениях и эти же элементы находящиеся в других уравнениях. В итоге получим уравнения:

<img width=«150» height=«184» src=«ref-1_113012556-1710.coolpic» v:shapes="_x0000_i1080">

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

<img width=«99» height=«184» src=«ref-1_113014266-852.coolpic» v:shapes="_x0000_i1081">

<img width=«253» height=«24» src=«ref-1_113015118-394.coolpic» v:shapes="_x0000_i1082">


2.3.2 Пример минимизации методом Квайна-Мак-Класки.
При минимизации по данному методу предполагается, что минимизируемая функция задана в СДНФ. Метод Квайна – Мак – Класки состоит из последовательного выполнения следующий этапов.

Метод Квайна состоит из последовательного выполнения этапов:

1)    Нахождение первичных импликант

2)    Расстановка меток

3)    Нахождение существенных импликант

4)    Вычеркивание лишних столбцов

5)    Вычеркивание лишних

6)    Получение минимального покрытия

Выполним, приведенные этапы, для функции У3.

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

СДНФ, которую мы нашли ранее, для функции У3 имеет вид:

<img width=«527» height=«24» src=«ref-1_112995638-734.coolpic» v:shapes="_x0000_i1083">

Составим минитермы для этой функции:

Таблица 2.2.1

Минитермы длиной 4

Минитермы длиной 3

Нулевая группа

0000+

Нулевая группа

0-00

Первая группа

0100+

Первая группа

-100, -011

Вторая группа

1100, 1010, 0011

Вторая группа

11-0, 1-10, 101-

Третья группа

1110, 1011




Расстановка меток. Остальные этапы нужны, чтобы отбросить некоторые первичные импликанты. На данном этапе составляется таблица, число строк которой равно числу полученных первичных импликант, число столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая – либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка. В таблице 2.2.2 приведем результат расстановки меток:

Таблица 2.2.2



0000

0100

1100

1010

0011

1110

1011





1

2

3

4

5

6

7

1

0-00

У

У











2

-100



У

У









3

-011









У



У

4

11-0





У





У



5

1-10







У



У



6

101-







У





У

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

Существенными являются импликанты 0-00 и -011. Поэтому вычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.

Составим сокращенную таблицу меток:

Таблица 2.2.3


1100

1010

1110

-100

У





11-0

У



У

1-10



У

У

101-



У



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

 С учетом существенных импликант получим две МДНФ для этой функции имеет вид:

1.<img width=«255» height=«24» src=«ref-1_113016246-394.coolpic» v:shapes="_x0000_i1084">

2. <img width=«253» height=«24» src=«ref-1_113016640-399.coolpic» v:shapes="_x0000_i1085">

Число букв составляющих простые импликации в каждом варианте одинаково. Во втором варианте на одно отрицание меньше, поэтому берем его за искомое:

<img width=«253» height=«24» src=«ref-1_113016640-399.coolpic» v:shapes="_x0000_i1086">
    продолжение
--PAGE_BREAK--2.3.3 Пример минимизации картами Карно
Данный метод для минимизации функции в коде Грея. В каждую ячейку записывается значение функции на данном наборе. Затем выделяются группы ячеек размером 2a*2b, где a, bε[0,1,2…], в которых функция принимает значение «1». В каждую группу должно входить максимальное число ячеек. Таких групп должно быть минимальное количество. Каждой группе будет соответствовать конъюнктивный член размером n
-
a
-
b
.Для получения МДНФ каждую группу надо просматривать в горизонтальном и вертикальном измерениях, с нахождения таких переменных, которые не меняют своего значения в пределах группы. Если переменная не меняет своего нулевого значения, то она вписывается в конъюнкцию с отрицанием, если не меняет своего единичного значения, то вписывается без отрицания. Если имеются разорванные группы, то карту Карно надо свернуть в цилиндр. На неопределенных наборах следует доопределить нулем или единицей, в соответствии с выбираемой группой ячеек. Каждая единичная ячейка должна быть включена хотя бы в одну группу.

Составим карту Карно для функции У3 (рисунок 2.3.1).





Рис. 2.3.1 Карта Карно для функции У3
Таким образом, для функции У3 в МДНФ будет иметь следующий вид:

<img width=«255» height=«24» src=«ref-1_113016246-394.coolpic» v:shapes="_x0000_i1087">


    продолжение
--PAGE_BREAK--2.4 Совместная минимизация всех функций
Синтез схем на основе отдельно минимизированных функций является неоптимальным, с точки зрения количества используемых элементов. Так как вероятнее всего, имеются такие конъюнкции, которые дублируют друг друга. Целью данного пункта является нахождение этих конъюнкций.

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

Составим карты Карно для всех функций таблицы истинности (таблица 2.1.1)

<img width=«605» height=«170» src=«ref-1_113017832-2800.coolpic» v:shapes="_x0000_s3083 _x0000_s3084 _x0000_s3085 _x0000_s3086 _x0000_s3087 _x0000_s3121 _x0000_s3093 _x0000_s3094 _x0000_s3095 _x0000_s3096 _x0000_s3099 _x0000_s3100 _x0000_s3101 _x0000_s3103 _x0000_s3104 _x0000_s3105 _x0000_s3106 _x0000_s3107 _x0000_s3109 _x0000_s3110 _x0000_s3111 _x0000_s3112 _x0000_s3113 _x0000_s3117 _x0000_s3118 _x0000_s3119">


1

*

1







1

*

1







1

*

1







1

*

1

1







*

1





*

*

1







*

*







1

*

*







1

*

*

1





1

*

*

1



*

*

1





1

*

*







1

*

*

1







*

*

1





1

*

*

1



*

1

1







*



1







*

1

1





1

*

1

1







*

1

1






<img width=«232» height=«172» src=«ref-1_113020632-1346.coolpic» v:shapes="_x0000_s3122 _x0000_s3091 _x0000_s3092 _x0000_s3097 _x0000_s3098 _x0000_s3102 _x0000_s3108 _x0000_s3114 _x0000_s3115 _x0000_s3116 _x0000_s3120">1

*

1

1





1

*

1

1

 1

*

*

1





1

*

*



1

*

*







1

*

*

1

1

*

1









*

1

1



Тогда МДНФ этих функций будет иметь вид:

<img width=«300» height=«169» src=«ref-1_113021978-2099.coolpic» v:shapes="_x0000_i1088">
    продолжение
--PAGE_BREAK--
 
 Кодирование выходных символов представлено в таблице 3.3.2 .

              

Таблица 3. 3.2

               
Кодирование состояний автомата представлено в таблиц 3.3.3.

    продолжение
--PAGE_BREAK--Таблица 3.3.3

В соответствии с таблицами 3.3.1 – 3.3.3 составляем таблицу переходов – входов в кодированном виде.

Таблица 3.3.4



А также составим кодированную таблицу переходов выходов.

Таблица 3.4.5

    продолжение
--PAGE_BREAK--