Синтез цифрового автомата

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

-разбиением множества  S является множество его подмножеств которые не пересекаются между собой и при объединении дают множество S. Эти подмножества называются блоками -разбиения.

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

 

 

 

 

 

 

1. Определение СП разбиений

Определение СП-разбиений  основано на предположении, что рассматриваемые состояния находятся в одном блоке. Если в разных блоках совпадает хотя бы 1 состояние, то эти блоки объединяются.

Ищем СП-разбиения, попарно рассматривая все состояния:

{1 2}   X1{36}                   объединяем блоки, имеющие хотя бы одно одинаковое состояние и

X2 {4}          получаем один блок {123456}. Это значит, что в данном случае              

X3{41}            => СП-разбиения нет. В таком случае ставил «Х»

X4{61}                   Аналогично рассматриваем все пары состояний   

X5{54}                    

 

{13}    X1{34} {1345}X1{134}

X2{4}                                                    X2{14}

X3{4}        => {1345}{62};                   X3{134}         =>  {123456};   X

X4{62}                                                    X4{126}

X5{54}                                                    X5{125}

 

{14}    X1{13}         {1245} X1{134}

X2{14}                                                                X2{14}

X3{34}           => {1345}{26};                           X3{134}           => {123456};  X

X4{26}                                                                 X4{126}

X5{15}                                                               X5{125}

 

{15}    X1{3}              {12456}    X1{1346}

X2{4}                                                                X2145}

X3{14}           => {12456}{3};                         X3{134}           => {123456};  X

X4{16}                                                               X4{126}

X5{25}                                                               X5{1245}

 

{16}    X1{34}    {13456}    X1{134}

X2{45}                                                                X2{145}

X3{14}           => {13456}{3};                           X3{134}           => {123456};  X

X4{6}                                                                 X4{126}

X5{45}                                                               X5{1245}

 

{23}    X1{46}        {12346}   X1{1346}

X2{4}                                                                    X2{145}

X3{1}           => {12346}{5};                               X3{143}          => {123456};  X

X4{12}                                                                  X4{126}

X5{14}                                                                  X5{1245}

{24}    X1{16}                                                  {12346}  X1{1345}

X2{14}                                                                   X2{145}

X3{13}        => {12346}{5};                                 X3{143}           => {123456};   X

X4{12}                                                                    X4{126}

X5{13}                                                                    X5{1245}

 

{25}    X1{34}                                                  {245}  X1{136}

X2{4}                                                                 X2{14}

X3{1}        => {1}{245}{36};                           X3{13}             => {123456};   X

X4{1}                                                                X4{12}

X5{24}                                                               X5{124}

 

{26}    X1{46}                                                  {2456}  X1{1345}

X2{45}                                                                 X2{145}

X3{1}        => {1}{2456}{3};                             X3{13}           => {123456};   X

X4{1}                                                                   X4{12}

X5{4}                                                                   X5{124}

 

 

{34}    X1{14}                                                  {134}  X1{134}

X2{1}                                                                 X2{14}

X3{3}        => {134}{2}{5};                             X3{34}             => {1345}{26}; 

X4{2}                                                                 X4{26}

X5{1}                                                                 X5{15}

 

      {1345}      X1{134}

X2{14}

X3{3134}         => {123456};   X

X4{126}

X5{125}

 

{35}  X1{34}                                    {12} X1{36}

X2{4}                                                                      X2{4}

X3{1}          => {12}{345};                                    X3{41}          => {123456};   X

X4{12}                                                                      X4{61}

X5{12}                                                                     X5{54}

 

 

 

{33}    X1{4}                                   

X2{5}                                                                      

X3{1}          => {14}{36}{2};                                    

X4{2}                                                                    

X5{14}       

    

{14}    X1{13}         {1245} X1{134}

X2{14}                                                                X2{14}

X3{34}           => {1345}{26};                           X3{134}           => {123456};  X

X4{26}                                                                 X4{126}

X5{15}                                                                 X5{125}

 

{45}    X1{13}                                   

X2{14}                                                                      

X3{13}          => {123456};                                    

X4{12}                                                                    

X5{12}     

 

{46}    X1{14}                                    {13456} X1{134}

X2{15}                                                                        X2{145}

X3{13}          => {13456}{2};                                    X3{134}          => {123456};   X

X4{2}                                                                          X4{126}

X5{14}                                                                        X5{1245}

 

{56}    X1{34}                                {23456} X1{1346}

X2{45}                                                                      X2{145}

X3{1}          => {1}{23456};                                    X3{13}          => {123456};   X

X4{24}                                                                      X4{12}

X5{24}                                                                      X5{124}

 

 

 

                                                       

Отсюда следует, что СП-разбиений  нет.

 

 

 

 

 

2. Декомпозиция автоматов при отсутствии СП-разбиений

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

Определим ортогональные  π-разбиения из множества состояний  минимизированного автомата.

π1={1234; 56},  π2={1256; 34}, π3={135; 246}.

Каждое π-разбиение  соответствует новому автомату, т.е  обозначим блоки π-разбиений через  состояния автоматов:

π1->E{e1=1234; e2=56}

π2->C{c1=1256; c2=34}

π3->D{d1=135; d2=246}.

Для каждого  разбиения построим функцию перехода компонентных автоматов на основе функции перехода исходного автомата. Функции переходов компонентных автоматов определяют реакцию автоматов E, C, D на внешнее входное воздействие и что исходный автомат находится в состояние К, соответствующему произведению алфавитов компонентных автоматов.

e₁*c₁*d₁=1  e₂*c₁*d₁=5

e₁*c₁*d₂=2  e₂*c₁*d₂=6

e₁*c₂*d₁=3  e₂*c₂*d₁= *

e₁*c₂*d₂=4  e₂*c₂*d₂= *

 

Автомат E

δ	1	2	3	4	5	6
x1	e1	e2	e1	e1	e1	e1
x2	e1	e1	e1	e1	e1	e2
x3	e1	e1	e2	e1	e1	e1
x4	e2	e1	e1	e1	e1	e1
x5	e2	e1	e1	e1	e1	e1

 

 

 

 

         

Автомат C

δ	1	2	3	4	5	6
x1	c2	c1	c2	c1	c2	c2
x2	c2	c2	c1	c1	c2	c1
x3	c2	c1	c1	c2	c1	c1
x4	c1	c1	c1	c1	c1	c1
x5	c1	c2	c1	c1	c1	c2

 

Автомат D

δ	1	2	3	4	5	6
x1	d1	d2	d2	d1	d1	d2
x2	d2	d1	d1	d1	d1	d1
x3	d2	d1	d1	d1	d1	d1
x4	d2	d1	d2	d2	d1	d1
x5	d1	d2	d1	d1	d1	d2

 

 

 

 

 

 

Для того, чтобы  определить взаимное влияние автоматов друг не друга, определяют τ и Ө–разбиение для каждого автомата в отдельности.

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

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

Определим τ–разбиения  для компонентных автоматов, путем  сравнения столбцов таблиц переходов:

τ_e= {123};{25};{6}.

τ_c ={1};{2};{3}; {4}; {5}; {6}.

τ_d = {1};{26};{3};{4};{5}.

Определим η–разбиения  для компонентных автоматов, путем  сравнения строк таблиц их переходов:

Өe = {12};{34};{56}.

Өc = {1};{2};{3};{4}: {5}.

Өd = {1};{23};{4};{5}.

1.3.3 Определение входных сигналов компонентных автоматов и составление таблиц

 Влияние автоматов друг на друга определяется по следующему правилу: если произведение π-разбиений i-го автомата  меньше или равно τ-разбиению i-го  автомата, то составляющая определяется как произведение π-разбиений исключая π-разбиение i-го автомата.

π₁*π₂={12,34,56}

π₁*π₃={13,5,24,6}

π₂*π₃={15,26,3,4}

π₁*π₂*π₃={1,2,3,4,5,6}