Курсовая работа: Синтез цифрового аппарата

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}

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

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

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

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

р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

Автомат C

Автомат D

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

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

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

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

ф_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}.

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

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

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

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

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

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

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

Для составления таблиц переходов автоматов C, D и E примем следующие обозначения:

E {e1=1234; e2=56}

C {c1=1256; c2=34}

D {d1=135; d2=246}

U={u₁=x₁, x₂; u₂=x₃; u₃=x₄; u₄=x₅}

V={v₁=x₁; v₂=x₂, x₃; v₃=x₄; v₄=x₅}

W={w₁=x₁; w₂=x₂, x₃; w₃=x₄; w₄=x₅}.

Таблицы заполняем по следующему алгоритму на примере первой ячейки: c1*d1*e1=1. По сигналу u1 (x1, x2) автомат E перейдет в состояния e₁, что мы и запишем в первую ячейку таблицы переходов автомата E.

Таким образом, заполняются все ячейки всех трёх автоматов:

Определение выходных сигналов осуществляется по произведению состояний компонентных автоматов E, C и D и входным сигналам в соответствии с таблицей выходов автомата B.

2. Структурный синтез цифрового автомата

2.1 Кодирование автомата

На основании таблиц переходов и логической функции строится структурная схема сети автоматов. Структурный автомат представляет собой композицию комбинационной (логической) схемы и элементов памяти, связанных со схемой. Входными переменными схемы являются входные переменные автомата - сигналы приходящие на блоки Ue, Vc, Wd. Выходы схемы Fe, Fc, Fd определяют переход автомата в следующее состояние.

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

Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …, xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. Для этого необходимо, чтобы выполнялось условие N2n, где N - число символов входного алфавита.

Кодировать таблицы переходов и выходов будем в соответствии с условиями:

c₁d₁= e₁c₁= e₁d₁= 00 u₁₌w₁= 00 v₁= 000

c₁d₂= e₁c₂= e₁d₂= 01 u₂₌w₂= 01 v₂= 001

c₂d₁= e₂c₁= e₂d₁= 10 u₃₌w₃= 10 v₃= 010

c₂d₂= e₂c₂= e₂d₂= 11 u₄₌w₄= 11 v₄= 011

v₅= 111

Получим закодированные таблицы переходов компонентных автоматов: