Прикладная теория цифровых автоматов
Кодування МСА
-
МСА
P1P2P3
М1
0 0 0 (щp1щp2щp3)
М2
0 0 1 (щp1щp2p3)
М3
0 1 0 (щp1p2щp3)
М4
0 1 1 (щp1p2p3)
М5
1 0 0 (p1щp2щp3)
Часткові МСА М1-М5 наведені в табл.1.2-1.6
Таблиця 1.2
Часткова МСА М1
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
Ak |
|
|
A0 |
щx1 |
щx1щx2 |
x1x2 |
||||||
|
A1 |
1 | ||||||||
|
A2 |
1 | ||||||||
|
A3 |
1 | ||||||||
|
A4 |
1 | ||||||||
|
A5 |
1 | ||||||||
|
A6 |
1 | ||||||||
|
A7 |
1 | ||||||||
|
A8 |
1 |
Таблиця 1.3
Часткова МСА М2
|
A1 |
A3 |
A6 |
A7 |
A9 |
A10 |
A11 |
A12 |
A22 |
Ak |
|
|
A0 |
1 | |||||||||
|
A1 |
1 | |||||||||
|
A3 |
1 | |||||||||
|
A6 |
1 | |||||||||
|
A7 |
x3 |
щx3 |
||||||||
|
A9 |
1 | |||||||||
|
A10 |
1 | |||||||||
|
A11 |
1 | |||||||||
|
A12 |
1 | |||||||||
|
A22 |
1 |
Таблиця 1.4
Часткова МСА М3
|
A6 |
A12 |
A13 |
A14 |
A15 |
A16 |
Ak |
|
|
A0 |
1 | ||||||
|
A6 |
1 | ||||||
|
A12 |
1 | ||||||
|
A13 |
1 | ||||||
|
A14 |
щx1 |
x1 |
|||||
|
A15 |
x3 |
щx3 |
|||||
|
A16 |
1 |
Таблиця 1.5
Часткова МСА М4
|
A2 |
A6 |
A8 |
A9 |
A13 |
A17 |
A18 |
Ak |
|
|
A0 |
щx1 |
x1 |
||||||
|
A2 |
1 | |||||||
|
A6 |
1 | |||||||
|
A8 |
x2 |
щx2 |
||||||
|
A9 |
1 | |||||||
|
A13 |
1 | |||||||
|
A17 |
1 | |||||||
|
A18 |
1 |
Таблиця 1.6
Часткова МСА М5
|
A1 |
A2 |
A6 |
A17 |
A19 |
A20 |
A21 |
Ak |
|
|
A0 |
1 | |||||||
|
A1 |
1 | |||||||
|
A2 |
1 | |||||||
|
A6 |
1 | |||||||
|
A17 |
1 | |||||||
|
A19 |
x1щx2 |
x1x2 |
щx1 |
|||||
|
A20 |
1 | |||||||
|
A21 |
1 |
На наступному етапі побудуємо об'єднану МСА М0, в якій рядки відмічені всіма мітками Аi, крім Аk, а стовпці - всіма, крім А0. На перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-формула переходу з вершини Аi у вершину Аj для n-ої ГСА. Наприклад, формула переходу А0®А1 буде мати вигляд F0,1=щx1щp1щp2щp3+ щp1щp2p3+ +p1щp2щp3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому змінні p1..pq не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину Аi перехід завжди здійснюється при незмінному значенні pq, то це значення pq в рядку Аi замінимо на “1", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні щp1 і щp2, отже в рядку А3 щp1 і щp2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=щp3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8).
По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати слідуюче вираження: Ai®Fi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слідуючу систему формул:
A0®щx1щp1щp2щp3A1+щp1щp2p3A1+p1щp2щp3A1+x1щx2щp1щp2щp3A2+x1x2щp1щp2щp3A3+
+щx1щp1p2p3A8+x1щp1p2p3A13+щp1p2щp3A14
A1®щp1щp3A2+p1щp3A6+щp1p3A7
A2®щp1щp2щp3A6+щp1p2p3A18+p1щp2p3A21
A3®щp3A4+p3A11
A4®A5
A5®А6
Таблиця 1.7
Об`єднана МСА Мo
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak |
|
A0 |
_ _ _ _ x1p1p2p3+ _ _ +p1p2p3+ _ _ +p1p2p3 |
_ _ _ _ x1x2p1p2p3 |
_ _ _ x1x2p1p2p3 |
_ _ x1p1p2p3 |
_ x1p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||
A1 |
_ _ _ p1p2p3 |
_ _ p1p2p3 |
_ _ p1p2p3 |
||||||||||||||||||||
A2 |
_ _ _ p1p2p3 |
_ p1p2p3 |
_ _ p1p2p3 |
||||||||||||||||||||
A3 |
_ _ _ p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||||||
A4 |
_ _ _ p1p2p3 |
||||||||||||||||||||||
A5 |
_ _ _ p1p2p3 |
||||||||||||||||||||||
A6 |
_ p1p2p3 |
_ _ _ p1p2p3 |
_ _ p1p2p3 |
_ _ p1p2p3 |
_ _ p1p2p3 |
||||||||||||||||||
A7 |
_ _ x3p1p2p3 |
_ _ _ p1p2p3 |
_ _ _ x3p1p2p3 |
||||||||||||||||||||
A8 |
_ x2p1p2p3 |
_ _ _ p1p2p3+ _ _ +x2p1p2p3 |
|||||||||||||||||||||
A9 |
_ p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||||||
A10 |
_ _ p1p2p3 |
||||||||||||||||||||||
A11 |
_ _ p1p2p3 |
||||||||||||||||||||||
A12 |
_ _ p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||||||
A13 |
_ p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||||||
A14 |
_ _ _ x1p1p2p3 |
_ _ x1p1p2p3 |
|||||||||||||||||||||
A15 |
_ _ x3p1p2p3 |
_ _ _ x3p1p2p3 |
|||||||||||||||||||||
A16 |
_ _ p1p2p3 |
||||||||||||||||||||||
A17 |
_ _ p1p2p3 |
_ p1p2p3 |
|||||||||||||||||||||
A18 |
_ p1p2p3 |
||||||||||||||||||||||
A19 |
_ _ _ x1x2p1p2p3 |
_ _ x1x2p1p2p3 |
_ _ _ x1p1p2p3 |
||||||||||||||||||||
A20 |
_ _ p1p2p3 |
||||||||||||||||||||||
A21 |
_ _ p1p2p3 |
||||||||||||||||||||||
A22 |
_ _ p1p2p3 |
Таблиця 1.8
Об`єднана мінімізована МСА Мo
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
A9 |
A10 |
A11 |
A12 |
A13 |
A14 |
A15 |
A16 |
A17 |
A18 |
A19 |
A20 |
A21 |
A22 |
Ak |
|
A0 |
_ _ _ _ x1p1p2p3+ _ _ +p1p2p3+ _ _ +p1p2p3 |
_ _ _ _ x1x2p1p2p3 |
_ _ _ x1x2p1p2p3 |
_ _ x1p1p2p3 |
_ x1p1p2p3 |
_ _ p1p2p3 |
|||||||||||||||||
A1 |
_ _ p1p3 |
_ p1p3 |
_ p1p3 |
||||||||||||||||||||
A2 |
_ _ _ p1p2p3 |
_ p1p2p3 |
_ _ p1p2p3 |
||||||||||||||||||||
A3 |
_ p3 |
p3 |
|||||||||||||||||||||
A4 |
1 |
||||||||||||||||||||||
A5 |
1 |
||||||||||||||||||||||
A6 |
_ p1p2p3 |
_ _ _ p1p2p3 |
_ _ p1p2p3 |
_ _ p1p2p3 |
_ _ p1p2p3 |
||||||||||||||||||
A7 |
x3p3 |
_ p3 |
_ x3p3 |
||||||||||||||||||||
A8 |
x2p2p3 |
_ _ p2p3+ _ +x2p2p3 |
|||||||||||||||||||||
A9 |
p2 |
_ p2 |
|||||||||||||||||||||
A10 |
1 |
||||||||||||||||||||||
A11 |
1 |
||||||||||||||||||||||
A12 |
_ p2p3 |
_ p2p3 |
|||||||||||||||||||||
A13 |
p3 |
_ p3 |
|||||||||||||||||||||
A14 |
_ x1 |
x1 |
|||||||||||||||||||||
A15 |
x3 |
_ x3 |
|||||||||||||||||||||
A16 |
1 |
||||||||||||||||||||||
A17 |
_ _ p1p2p3 |
_ p1p2p3 |
|||||||||||||||||||||
A18 |
1 |
||||||||||||||||||||||
A19 |
_ x1x2 |
x1x2 |
_ x1 |
||||||||||||||||||||
A20 |
1 |
||||||||||||||||||||||
A21 |
1 |
||||||||||||||||||||||
A22 |
1 |
A6®щp1p2p3A2+щp1щp2щp3A7+щp1щp2p3A12+p1щp2щp3A19+щp1p2щp3Ak
A7®x3p3A6+щp3A8+щx3p3A9
A8®x2p2p3A17+щp2щp3Ak+щx2p2p3Ak
A9®p2A8+щp2A10
A10®A3
A11®Ak
A12®щp2p3A22+p2щp3A13
A13®p3A9+щp3Ak
A14®щx1A15+x1A16
A15®x3A6+щx3Ak
A16®A12
A17®p1щp2щp3A2+щp1p2p3A6
A18®Ak
A19®x1щx2A2+x1x2A20+щx1A21
A20®A17
A21®Ak
A22®Ak
При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx1+Вщx1, де А і В -деякі вирази, а x1 і щx1-логічні умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13, А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в інших є вирази виду Аn®xj(А) +щxjpi(В). Тут pi відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднаній ГСА бути не повинно. Для їх усунення скористаємося слідуючим правилом: додавання виразу [PqАn] не змінить формулу, якщо набір Pq не використовується для кодування ГСА або вершина Аn відсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A8®x2p2p3A17+щp2щp3Ak+щx2p2p3A спрощується таким чином A8=p3(x2p2A17+щx2p2Ak)+щp3щp2Ak=p3p2(x2A17+щx2Ak)+щp3щp2Ak=


![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()