Прикладная теория цифровых автоматов (работа 2)

TYPE=RANDOM FORMAT=PAGE>14


1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА

1.1. Побудова ГСА

По описах граф-схем, приведених в завданні до курсової роботи, побудуємо ГСА Г>1>-Г>5> (мал. 1.1-1.5), додавши початкові і кінцеві вершини і замінивши кожний оператор Yi операторною вершиною, а кожну умову X>i> - умовною.

1.2. Методика об'єднання ГСА

У ГСА Г>1>-Г>5> є однакові ділянки, тому побудова автоматів за ГСА Г>1>-Г>5> приведе до невиправданих апаратурних витрат. Для досягнення оптимального результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати число операторних і умовних вершин. Заздалегідь помітимо операторн³ вершини в початкових ГСА, керуючись сл³дуючими правилами:

1) однакові вершини Y>i> в різних ГСА відмічаємо однаковими мітками A>j>;

2) однакові вершини Y>i> в межах однієї ГСА відмічаємо різними мітками A>j>;

3) у всіх ГСА початкову вершину помітимо як А>0>, а кінцеву - як A>k>.

На наступному етапі кожн³й ГСА поставимо у відповідність набір змінних P>n>Î {P>1>...P>q>}, де q=]log>2>N[, N -к³льк³сть ГСА. Означувальною для ГСА Г>n> ми будемо називати кон`юнкцию P>n>=p>1>eÙ...Ùp>q>n еÎ{0,1}, причому p0=ùр, p1=р. Об'єднана ГСА повинна задовольняти сл³дуючим вимогам:

1) якщо МК A>i> входить хоча б в одну часткову ГСА, то вона входить і в об'єднану ГСА Г>0>, причому тільки один раз;

2) при підстановці набору значень (е>1>...e>n>), на якому P>q>=1 ГСА Г>0> перетворюється в ГСА, рівносильну частков³й ГСА Г>q>.

При об'єднанні ГСА виконаємо сл³дуючі етапи:

-сформуємо часткові МСА М>1> - М>5>, що відповідні ГСА Г>1> - Г>5>;

- сформуємо об'єднану МСА М>0>;

- сформуємо системи дужкових формул переходу ГСА Г>0>;

- сформуємо об'єднану ГСА Г>0>.

1.3. Об'єднання часткових ГСА

Часткові МСА М>1>-М>5> побудуємо по ГСА Г>1>-Г>5> (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками A>i>, що входять до ГСА, крім кінцевої A>k>.

ПОЧАТОК A>0>

1

0 X>1> 1

2

A>1>

3

0

4 X>2> A>2> 1

5

A>3>

6

A>4>

7

A>5>

8

A>6>

9

A>7>

10

A>8>

К³НЕЦь A>k>

Мал.1.1. Часткова граф-схема алгоритму Г>1>

ПОЧАТОК A>0>

1

A>1>

2

A>7>

0 3 1

X>3>

4 5

A>9 > A>6>

6 7

> >A>10> A>12>

8 9

> >A>3> A>22 >

10

A>11>

К³НЕЦЬ A>k>

> > Мал.1.2. Часткова граф-схема алгоритму Г>2>

ПОЧАТОК A>0>

1

A>11>

0 2 1

X>1>

3 4

A>15 > A>16>

6

5 1

X>3> A>12>

0 > >

7 8

A>6> A>13>

К³НЕЦЬ А>k>

Мал.1.3. Часткова граф-схема алгоритму Г>3>

ПОЧАТОК A>0>

1

0 1

X>1>

2

A>13>

3

A>9>

4

A>8>

5

1 X>2>

6 0

A>17>

7

A>6>

8

A>2>

9

A>18>

К³НЕЦЬ A>k>

Мал.1.4. Часткова граф-схема алгоритму Г>4>

ПОЧАТОК A>0>

1

A>1>

2

A>6>

3

A>19>

4

0 1

X>1>

5

0 X>2>

1

6

A>20>

7

A>17>

8

A>2>

9

A>21>

К³НЕЦЬ A>k>


Мал.1.5. Часткова граф-схема алгортиму Г>5>

Стовпці МСА відмітимо всіма мітками A>i­>, що входять до ГСА, крім початкової A>0>. На перетині рядка A>i> і стовпця A>j> запишемо формулу переходу f>ij> від оператора A>i> до оператора A>j>. Ця функція дор³внюº 1 для безумовного переходу або кон`юнкц³¿ логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з м³ткою A>i> у вершину з м³ткою Aj.

За методикою об'єднання закодуємо МСА таким чином:

Таблиця 1.1

Кодування МСА

МСА

P>1>P>2>P>3>

М>1>

0 0 0 (ùp>1>ùp>2>ùp>3>)> >

М>2>

0 0 1 (ùp>1>ùp>2>p>3>)

М>3>

0 1 0 (ùp>1>p>2>ùp>3>)

М>4>

0 1 1 (ùp>1>p>2>p>3>)

М>5>

1 0 0 (p>1>ùp>2>ùp>3>)

Частков³ МСА М>1>-М>5> наведен³ в табл.1.2-1.6

Таблиця 1.2

Часткова МСА М>1>

A>1>

A>2>

A>3>

A>4>

A>5>

A>6>

A>7>

A>8>

A>k>

A>0>

ùx>1>

ùx>1>ùx>2>

x>1>x>2>

A>1>

1

A>2>

1

A>3>

1

A>4>

1

A>5>

1

A>6>

1

A>7>

1

A>8>

1

Таблиця 1.3

Часткова МСА М>2>

A>1>

A>3>

A>6>

A>7>

A>9>

A>10>

A>11>

A>12>

A>22>

A>k>

A>0>

1

A>1>

1

A>3>

1

A>6>

1

A>7>

x>3>

ùx>3>

A>9>

1

A>10>

1

A>11>

1

A>12>

1

A>22>

1

Таблиця 1.4

Часткова МСА М>3>

A>6>

A>12>

A>13>

A>14>

A>15>

A>16>

A>k>

A>0>

1

A>6>

1

A>12>

1

A>13>

1

A>14>

ùx>1>

x>1>

A>15>

x>3>

ùx>3>

A>16>

1

Таблиця 1.5

Часткова МСА М>4>

A>2>

A>6>

A>8>

A>9>

A>13>

A>17>

A>18>

A>k>

A>0>

ùx>1>

x>1>

A>2>

1

A>6>

1

A>8>

x>2>

ùx>2>

A>9>

1

A>13>

1

A>17>

1

A>18>

1

Таблиця 1.6

Часткова МСА М>5>

A>1>

A>2>

A>6>

A>17>

A>19>

A>20>

A>21>

A>k>

A>0>

1

A>1>

1

A>2>

1

A>6>

1

A>17>

1

A>19>

x>1>ùx>2>

x>1>x>2>

ùx>1>

A>20>

1

A>21>

1

На наступному етапі побудуємо об'єднану МСА М>0>, в як³й рядки відмічені всіма мітками А>i>, крім А>k>, а стовпці - всіма, крім А>0>. На перетині рядка А>i> і стовпця А>j> запишемо формулу переходу, яка формується таким чином: F>ij>=P>1>f>ij>1+...+P>n>f>ij>n (n=1...N). Де f>ij>n-формула переходу з вершини А>i> у вершину А>j> для n-о¿ ГСА. Наприклад, формула переходу А>0>®А>1> буде мати вигляд F>0,1>=ùx>1>ùp>1>ùp>2>ùp>3>+ ùp>1>ùp>2>p>3>+ +p>1>ùp>2>ùp>3>. У результаті ми отримаємо об'єднану МСА М>0> (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г>0> як ГСА Г>n>, ми підставляємо певний набір P>n>=1, при цьому зм³нн³ p>1>..p>q> не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину А>i> перехід завжди здійснюється при незмінному значенні p>q>, то це значення p>q> в рядку А>i> замінимо на “1", а його інверсію на “0". Наприклад, у вершину А>3> перехід здійснюється при незмінному значенні ùp>1> і ùp>2>, отже в рядку А>3> ùp>1> і ùp>2> замінимо на “1", а p>1> і p>2> на “0". У результаті отримаємо формули F>3,4>=ùp>3>, F>3,11>=p>3>. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М>0> (табл.1.8).

По таблиці складемо формули переходу для об'єднаної ГСА Г>0>. Формулою переходу будемо називати сл³дуюче вираження: A>i>®F>i,1>А>1>+..+F>i,k>А>k>, > >де F>i,j>-> >відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо сл³дуючу систему формул:

A>0>®ùx>1>ùp>1>ùp>2>ùp>3>A>1>+ùp>1>ùp>2>p>3>A>1>+p>1>ùp>2>ùp>3>A>1>+x>1>ùx>2>ùp>1>ùp>2>ùp>3>A>2>+x>1>x>2>ùp>1>ùp>2>ùp>3>A>3>+

+ùx>1>ùp>1>p>2>p>3­>A>8>+x>1>ùp>1>p>2>p>3>A>13>+ùp>1>p>2>ùp>3>A>14>

A>1>®ùp>1>ùp>3>A>2­>+p>1>ùp>3>A>6>+ùp>1>p>3>A>7>

A>2>®ùp>1>ùp>2>ùp>3>A>6>+ùp>1>p>2>p>3>A>18>+p>1>ùp>2>p>3>A>21>

A>3>®ùp>3>A>4>+p>3>A>11>

A>4>®A>5>

A>5>®А>6>

Таблиця 1.7

Об`ºднана МСА М>o>

A>1>

A>2>

A>3>

A>4>

A>5>

A>6>

A>7>

A>8>

A>9>

A>10>

A>11>

A>12>

A>13>

A>14>

A>15>

A>16>

A>17>

A>18>

A>19>

A>20>

A>21>

A>22>

A>k>

A>0>

_ _ _ _

x>1>p>1>p>2>p>3>+

_ _

+p>1>p>2>p>3>+

_ _

+p>1>p>2>p>3>

_ _ _ _

x>1>x>2>p>1>p>2>p>3>

_ _ _

x>1>x>2>p>1>p>2>p>3>

_ _

x>1>p>1>p>2>p>3>

_

x>1>p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>1>

_ _ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>2>

_ _ _

p>1>p>2>p>3>

_

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>3>

_ _ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>4>

_ _ _

p>1>p>2>p>3>

A>5>

_ _ _

p>1>p>2>p>3>

A>6>

_

p>1>p>2>p>3>

_ _ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>7>

_ _

x>3>p>1>p>2>p>3>

_ _ _

p>1>p>2>p>3>

_ _ _

x>3>p>1>p>2>p>3>

A>8>

_

x>2>p>1>p>2>p>3>

_ _ _

p>1>p>2>p>3>+

_ _

+x>2>p>1>p>2>p>3>

A>9>

_

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>10>

_ _

p>1>p>2>p>3>

A>11>

_ _

p>1>p>2>p>3>

A>12>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>13>

_

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>14>

_ _ _

x>1>p>1>p>2>p>3>

_ _

x>1>p>1>p>2>p>3>

A>15>

_ _

x>3>p>1>p>2>p>3>

_ _ _

x>3>p>1>p>2>p>3>

A>16>

_ _

p>1>p>2>p>3>

A>17>

_ _

p>1>p>2>p>3>

_

p>1>p>2>p>3>

A>18>

_

p>1>p>2>p>3>

A>19>

_ _ _

x>1>x>2>p>1>p>2>p>3>

_ _

x>1>x>2>p>1>p>2>p>3>

_ _ _

x>1>p>1>p>2>p>3>

A>20>

_ _

p>1>p>2>p>3>

A>21>

_ _

p>1>p>2>p>3>

A>22>

_ _

p>1>p>2>p>3>

Таблиця 1.8

Об`ºднана м³н³м³зована МСА М>o>

A>1>

A>2>

A>3>

A>4>

A>5>

A>6>

A>7>

A>8>

A>9>

A>10>

A>11>

A>12>

A>13>

A>14>

A>15>

A>16>

A>17>

A>18>

A>19>

A>20>

A>21>

A>22>

A>k>

A>0>

_ _ _ _

x>1>p>1>p>2>p>3>+

_ _

+p>1>p>2>p>3>+

_ _

+p>1>p>2>p>3>

_ _ _ _

x>1>x>2>p>1>p>2>p>3>

_ _ _

x>1>x>2>p>1>p>2>p>3>

_ _

x>1>p>1>p>2>p>3>

_

x>1>p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>1>

_ _

p>1>p>3>

_

p>1>p>3>

_

p>1>p>3>

A>2>

_ _ _

p>1>p>2>p>3>

_

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>3>

_

p>3>

p>3>

A>4>

1

A>5>

1

A>6>

_

p>1>p>2>p>3>

_ _ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

_ _

p>1>p>2>p>3>

A>7>

x>3>p>3>

_

p>3>

_

x>3>p>3>

A>8>

x>2>p>2>p>3>

_ _

p>2>p>3>+

_

+x>2>p>2>p>3>

A>9>

p>2>

_

p>2>

A>10>

1

A>11>

1

A>12>

_

p>2>p>3>

_

p>2>p>3>

A>13>

p>3>

_

p>3>

A>14>

_

x>1>

x>1>

A>15>

x>3>

_

x>3>

A>16>

1

A>17>

_ _

p>1>p>2>p>3>

_

p>1>p>2>p>3>

A>18>

1

A>19>

_

x>1>x>2>

x>1>x>2>

_

x>1>

A>20>

1

A>21>

1

A>22>

1

A>6>®ùp>1>p>2>p>3>A>2>+ùp>1>ùp>2>ùp>3>A>7>+ùp>1>ùp>2>p>3>A>12>­+p>1>ùp>2>ùp>3>A>19>+ùp>1>p>2>ùp>3>A>k>

A>7>®x>3>p>3>A>6>+ùp>3>A>8>+ùx>3>p>3>A>9>

A>8>®x>2>p>2>p>3>A>17>+ùp>2>ùp>3>A>k>+ùx>2>p>2>p>3>A>k>

A>9>®p>2­>A>8>+ùp>2>A>10>

A>10>®A>3>

A>11>®A>k>

A>12>®ùp>2>p>3>A>22>+p>2>ùp>3>A>13>

A>13>®p>3>A>9>+ùp>3>A>k>

A>14­>®ùx>1>A>15>+x>1>A>16>

A>15>®x>3>A>6>+ùx>3>A>k>

A>16>®A>12>

A>17>®p>1>ùp>2>ùp>3>A>2­>+ùp>1>p>2>p>3>A>6>

A>18>®A>k>

A>19>®x>1>ùx>2>A>2>+x>1>x>2>A>20>+ùx>1>A>21>

A>20>­®A>17>

A>21>®A>k>

A>22>®A>k>

При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx>1>+Вùx>1>, де А і В -деякі вирази, а x>1> і ùx>1>-логічн³ умови переходу. Формули переходу для вершин А>3>, А>4>, А>5>, А>9>, А>10>, А>11>, А>13>, А>14>, А>15>, А>16>, А>18>, А>20>, А>21>, А>22> вже є елементарними (розкладеними), а в інших є вирази виду А>n>®x>j>(А) +ùx>j>p>i>(В). Тут p>i> відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднан³й ГСА бути не повинно. Для їх усунення скористаємося сл³дуючим правилом: додавання виразу [P>q>А>n>] не змінить формулу, якщо набір P>q> не використовується для кодування ГСА або вершина А>n> в³дсутня в ГСА з кодом P>q>. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A>8>®x>2>p>2>p>3>A>17>+ùp>2>ùp>3>A>k>+ùx>2>p>2>p>3>A спрощується таким чином A>8>=p>3>(x>2>p>2>A>17>+ùx>2>p>2>A>k>)+ùp>3>ùp>2>A>k>=p>3>p>2>(x>2>A>17>+ùx>2>A>k>)+ùp>3>ùp>2>A>k>=

1 X>j >0

P>i >0

1

Мал.1.6 Приклад чекаючо¿ вершини P>i>

=[ùp>3>p>2>(x>2>A>17>+ùx>2>A>k>)]+p>3>p>2>(x>2>A>17>+ùx>2>A>k>)+ùp>3>ùp>2>A>k>+[p>3>ùp>2>A>k>]=ùp>2>A>k>+p>2>(x>2>A>17>+ùx>2>A>k>). Тут вершина А>8 >не зустр³чаºться у ГСА ,в кодах яких присутн³ комб³нац³¿ ùp>3>p>2 >³> >p>3>ùp>2>. Нижче наведено розклад ус³х неелементарних формул переходу.

A>0>=p>1>(ùp>2>ùp>3>A>1>)+ùp>1>(ùx>1>ùp>2>ùp>3>A>1>+ùp>2>p>3>A>1>+x>1>ùx>2>ùp>2>ùp>3­>A>2>+x>1>x>2>ùp>2>ùp>3>A>3­>+

+ùx>1>p>2>p>3>A>8>+x>1>p>2>p>3>A>13>+p>2>ùp>3>A>14>)=p>1>(ùp>2>ùp>3>A>1>)+[p>1>ùp>2>ùp>3>A>1>]+

+ùp>1>(p>2>(ùx>1>p>3>A>8>+x>1>p>3>A>13>+ùp>3>A>14>)+ùp>2>(ùx>1>ùp>3>A>1>+p>3>A>1>+x>1>ùx>2>ùp>3>A>2>+

+x>1>x>2>ùp>3>A>3­>))=p>1>(ùp>2>A>1>)+[p>1>p>2>A>1>]+ùp>1>(p>2>(p>3>(ùx>1>A>8>+x>1>A>13>)+ùp>3>A>14>)+

+ùp>2>(ùp>3>(ùx>1>A>1>+x>1>x>2>A>3>+x>1>ùx>2>A>2>­)+p>3>A>1>))= p>1>A>1>+ùp>1>(p>2>(p>3>( ùx>1>A>8>+

+x>1>A>13>)+ùp>3>A>14>)+ùp>2>(ùp>3>(ùx>1>A>1>+x>1>(x>2>A>3>+ùx>2>A>2>))+p>3>A>1­>))

A>1>=ùp>1­>(p>3>A>7>+ùp>3>A>2>)+p>1>ùp>3>A>6>+[p>1>p>3>A>6>]= ùp>1­>(p>3>A>7>+ùp>3>A>2>)+p>1>A>6>

A>2>=p>1>(ùp>2>p>3>A>21>)+ùp>1>(ùp>2>ùp>3>A>6>+p>2>p>3>A>18>)= p>1>(ùp>2>p>3>A>21>)+[p>1>ùp>2>p>3>A>21>]+

+ùp>1­>(ùp>2>ùp>3>A>6>+[p>2>ùp>3>A>6>]+p>2>­p>3>A>18>+[p>3>ùp>2>A>18>])=p>1>(ùp>2>A>21>)+ùp>1>(ùp>3>A>6>+

+p>3>A>18>)=p>1>(ùp>2>A>21>)+[p>1>p>2>A>21>]+ùp>1>(ùp>3>A>6>+p>3>A>18>)=p>1>A>21>+ùp>1>(ùp>3>A>6>+

+p>3>A>18>)

A>6>=p>1>(ùp>2>ùp>3>A>19>)+[p>1>ùp>2>p>3>A>19>]+ùp>1>(p>2>p>3>A>2>+ùp>2>ùp>3>A>7>+ùp>2>p>3>A>12>+p>2>ùp>3>A>k>)=

=p>1>ùp>2>A>19>+[p>1>p>2>A>19>]+ùp>1>(p>2>(p>3>A>2>+ùp>3>A>k>)+ùp>2>(ùp>3>A>7>+p>3>A>12>­))=p>1>A>19>+

+ùp>1>(p>2>(p>3>A>2>+ùp>3>A>k>­)+ùp>2>(ùp>3>A>7>+p>3>A>12>))

A>7>=p>3>(x>3>A>6>+ùx>3>A>9>)+ùp>3>A>8>

A>8>=p>3>(x>2>p>2>A>17>+ùx>2>p>2>A>k>)+ùp>3>ùp>2>A>k>=p>3>p>2>(x>2>A>17>+ùx>2>A>k>)+ùp>3>ùp>2>A>k>=

=[ùp>3>p>2>(x>2>A>17>+ùx>2>A>k>)]+p>3>p>2>(x>2>A>17>+ùx>2>A>k>)+ùp>3>ùp>2>A>k>+[p>3>ùp>2>A>k>]=ùp>2>A>k>+

+p>2>(x>2>A>17>+ùx>2>A>k>)

A>12>=ùp>2>p>3>A>22>+p>2>ùp>3>A>13>+[p>2>p>3>A>22>]+[ùp>2>ùp>3>A>13>]=p>3>A>22>+ùp>3>A>13>

A>17>=p>1>ùp>2>ùp>3>A>2>+[p>1>ùp>2>p>3>A>2>]+ùp>1>p>2>p>3>A>6>+[ùp>1>ùp>2>p>3>A>6­>]=p>1>ùp>2>A>2>+[p>1>p>2>A>2>]+

+ùp>1>p>3>A>6>+[ùp>1>ùp>3>A>6>]=p>1>A>2>+ùp>1>A>6>­

A>19>=x>1>(ùx>2>A>2>+x>2>A>20>)+ùx>1>A>21>

Об'єднану ГСА Г>0> (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку А>i> відповідною операторною вершиною Y>t>, а кожний вираз X>i> і P>j> відповідними умовними вершинами.

TYPE=RANDOM FORMAT=PAGE>29


2.СИНТЕЗ АВТОМАТА З ПРИМУСОВОЮ АДРЕСАЦІЄЮ М²КРОКОМАНД.

2.1. Принцип роботи автомата.

При примусовій адресації адреса наступної м³крокоманди задається в полі поточної м³крокоманди. Формат МК в такому випадку сл³дуючий (мал. 2.1.).

>1> Y >m 1> X >l 1> A>0> >k> >1> A>1 k>

Мал. 2.1 Формат команди автомата з ПА.

Тут у полі Y міститься код, що задаº набір м³крооперац³й, у пол³ X-код логічної умови, що перевіряється, у полях A>0> і A>1>- адреси переходу при невиконанн³ логічної умови, що перевіряється або безумовному переході і при істинності логічної умови відповідно. Розрядн³сть полів визначається таким чином:

m=]log>2>T[ Т- число наборів м³крооперац³й, що використовуються в ГСА, в нашому випадку Т=17, m=5

l=]log>2> (L+1)[ L-число логічних умов у ГСА, в нашому випадку L=6, l=3

k=]log>2> Q[ Q -кількість м³крокоманд.

Структурна схема автомата приведена на мал. 2.2. Автомат функціонує таким чином. Схема запуску складається з RS -тригера і схеми “&", яка блокує надходження синхро³мпульс³в на РАМК і РМК. За сигналом “Пуск" тригер встановлюється в одиницю і відбувається запис м³крокоманд до регістру. Поле Y надходить на схему формування МО і перетворюºться в деякий набір м³крооперац³й. Поле X надходить до схеми формування адреси, яка формує сигнал Z>2>, якщо перехід безумовний (X=0) або ЛУ , що перевіряється, дор³внюº 0, або сигнал Z>1> у випадку істинності ЛУ. За сигналом Z>1>(Z>2>) до адресного входу ПЗП надходить значення поля A>1>(A>0>). За сигналу y>0> тригер встановлюється в нуль і автомат зупиняє свою роботу. За сигналом "Пуск" до РАМК заноситься адреса початкової МК (А=0).

2.2. Перетворення початкової ГСА.

Перетворення буде полягати в тому, що у всі операторн³ вершини, пов'язані з кінцевою, вводиться сигнал y>0>, а між всіма умовними вершинами, які пов'язані з кінцевою, вводиться операторна вершина, що містить сигнал y>0>. Причому, ця вершина буде загальною для всіх умовних. З урахуванням вищесказаного отримаємо перетворену ГСА (мал. 2.3). У перетворен³й ГСА ми зберігаємо позначення Y>i>, але при цьому пам'ятаємо, що кожна м³крокоманда Y>i>

РАМК

Z>1> Z>2>

S T & ПЗП

“Пуск”

С² R РМК Y X A>0> A>1> СФМО Z>1> y­>0 >.... y>i> СФА до ОА Z>2>

Мал.2.2. Структурна схема автомата з ПА

розбиваºться на м³крооперац³¿ y>i..>y>j> зг³дно з табл. 2.1.

Таблиця 2.1.

Розподіл МО по м³крокомандам.

МК

М³крооперац³¿

МК

М³крооперац³¿

Y>1>

y>1>y>2>y>9>y>10>

Y>12>

y>5>y>6>y>12>y>17>y>19>

Y>2>

y>1>y>5>y>12>y>19>

Y>13>

y>4>y>6>y>20>y>21>

Y>3>

y>1>y>6>y>11>y>20>

Y>14>

y>3>y>11>y>17>y>18>y>22>

Y>5>

y>3>y>4>y>13>y>30>

Y>15>

y>4>y>5>y>6>y>18>y>19>y>23>

Y>7>

y>2>y>6>y>7>y>16>

Y>16>

y>12>y>14>y>16>y>24>

Y>8>

y>5>y>13>y>15>y>29>

Y>17>

y>2>y>13>y>25>

Y>9>

y>6>y>17>

Y>18>

y>5>

Y>10>

y>3>y>4>y>5>y>18>y>19>

Y>20>

y>3>y>27>y>28>

Y>11>

y>7>y>8>y>17>y>20>

2.3.Формування вмісту керуючої пам'яті.

Перший етап - виділення м³крокоманд заданого формату. В автоматі з ПА в одному такті можуть виконуватися МО і перевірятися логічна умова. Тому м³крокоманда відповідає парі ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА. Виходячи з цього, отримаємо, що можливими є пари: ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА, ОПЕРАТОРНА ВЕРШИНА - БЕЗУМОВНИЙ ПЕРЕХІД, ПОРОЖНЯ ОПЕРАТОРНА - УМОВНА ВЕРШИНА. При цьому потрібно враховувати, що при виборі пари ОПЕРАТОРНА ВЕРШИНА - УМОВНА ВЕРШИНА недопустим перехід ззовні в точку між операторною і умовною вершинами, крім ситуації, коли умовна вершина входить до складу іншо¿ м³крокоманди. У результаті ми отримаємо сл³дуюче разбиття на м³крокоманди (мал. 2.3.). Ми отримали 38 допустимих МК. Закодуємо їх в природному порядку, привласнивши початков³й МК нульову адресу (табл.2.2). Для цього необхідно q=]log>2>N[ розрядів, де N- кількість МК заданого формату. У нашому випадку N=38, q=6.

Таблиця 2.2

Кодування МК

МК

А>1>А>2>А>3>А>4> А>5>А>6>

О>1>

0 0 0 0 0 0> >

О>2>

0 0 0 0 0 1

......

........................

О>38>

1 0 0 1 0 1

Аналогічним чином закодуємо оператори Y>i>, надавши нульовий код порожньому операторному полю (табл. 2.3).

Таблиця 2.3

Кодування Y

Y>i>

T>2>T>3>T>4>T>5>T>6>

Æ

00000

Y>1>

00001

Y>2>

00010

Y>3>

00011

Y>5>

00100

Y>7>

00101

Y>8 >

00110

Y>9>

00111

Y>10>

01000

Y>11>

01001

Y>12>

01010

Y>13>

01011

Y>14>

01100

Y>15>

01101

Y>16>

01110

Y>17>

01111

Y>18>

10000

Y>20>

10001

Таблиця 2.5

Вм³ст керуючо¿ пам`ят³.

№

A

FY

FX

FA>0>

FA>1>

Оп.

A>1>A>2>A>3>A>4>A>5>A>6>

T>1>T>2>T>3>T>4>T>5>T>6>

T>7>T>8>T>9>

T>10>T>11>T>12>T>13>T>14>T>15>

T>16>T>17>T>18>T>19>T>20>T>21>

1

000000

000000

100

000001

001100

2

000001

000000

101

000010

011001

3

000010

000000

110

000011

001100

4

000011

000000

001

001100

000100

5

000100

000000

010

001001

000101

6

000101

000110

110

000111

000110

7

000110

101100

000

000000

000000

8

000111

000111

000

001000

000000

9

001000

001001

000

001110

000000

10

001001

001000

100

001010

011000

11

001010

000000

110

001110

001011

12

001011

100111

000

000000

000000

13

001100

000001

100

001101

001110

14

001101

000000

110

001001

010010

15

001110

000100

100

001111

010111

16

001111

000000

101

010001

010000

17

010000

000000

110

010100

010101

18

010001

000000

110

010010

011110

19

010010

000110

110

011111

010011

20

010011

000000

011

100011

001110

21

010100

100000

000

000000

000000

22

010101

000000

010

001001

010110

23

010110

000001

000

100101

000000

24

010111

001010

001

011000

010101

25

011000

101010

000

000000

000000

26

011001

000000

110

011011

011010

27

011010

000000

001

011111

100001

28

011011

001101

001

011100

011101

29

011100

001110

011

010100

001110

30

011101

000101

000

011110

000000

31

011110

001111

010

100001

100000

32

011111

000111

101

010100

100010

33

100000

100011

000

000000

000000

34

100001

010000

110

010100

100011

35

100010

000000

010

010100

100101

36

100011

000001

101

100100

011111

37

100100

001011

000

000101

000000

38

100101

010001

100

001110

001001

2.4. Синтез схеми автомата.

Схема СФА являє собою мультиплексор, який в залежності від коду логічної умови, що перевіряється, передає на вихід Z>1> значення відповідно¿ ЛУ. При цьому сигнал Z>2> завжди є інверсією сигналу Z>1>. Таким чином, отримаємо сл³дуюч³ вирази для Z>1> і Z>­2>:

Z>1>=X>1>ùT>7>ùT>8>T>9>+X>2>ùT>7>T>8>ùT>9>+X>3>ùT>7>T>8>T>9>+P>1>T>7>ùT>8>ùT>9>+P>2>T>7>ùT>8>T>9>+P>3>T>7>T>8>ùT>9>

> >Z>2>=ùZ>1 >

або, звівши до заданого базису (4 АБО-Н²), отримаємо

Z>1>=ù ù(ù ù(A+B+C+D)+E+F), де

A=ù ù( X>1>ùT>7>ùT>8>T>9>)=ù(ùX>1>+T>7>+T>8>+ùT>9>)

B=ù ù( X>2>ùT>7>T>8>ùT>9>)=ù(ùX>2>+T>7>+ùT>8>+T>9>)

C=ù ù( X>3>ùT>7>T>8>T>9>)=ù(ùX>3>+T>7>+ùT>8>+ùT>9>)

D=ù ù( P>1>T>7>ùT>8>ùT>9>)=ù(ùP>1>+ùT>7>+T>8>+T>9>)

E=ù ù( P>2>T>7>ùT>8>T>9>)=ù(ùP>2>+ùT>7>+T>8>+ùT>9>)

F=ù ù( P>3>T>7>T>8>ùT>9>)=ù(ùP>3>+ùT>7>+ùT>8>+T>9>)

Інформація, що надходить на адресні входи ПЗП формується таким чином: A>i>=A>0i>Z>1>+A>1i>Z>2> або, приводячи до заданого базису, отримуємо A>i>=ùù(ù(ùA>0i>+ùZ>1>)+ù(ùA>1i>+ùZ>2>)).

Синтезуємо тепер схему дешифратора, що формує сигнали м³крооперац³й y>i>. Поява одиниці, відповідної кожному Y, відбувається при появі на вході дешифратора коду даного Y, тобто Y>i>=T>2>eÙT>3>eÙT>4>еÙT>5>еÙT>6>е, де еÎ{0,1} T0=ùT, T1=T. Або приводячи до заданого базису, отримаємо: Y>i>=ù(ù ù(T>2>ùe+T>3>ùe+T>4>ùе+T>5>ùе)+T>6>ùе). Таким чином, схема, що формує сигнал Y з п`ятирозрядного коду виглядає таким чином(мал. 2.4)

T>6>ùe

1 1 1 Y>i>

T>2>ùe

Мал. 2.4. Схема формування сигналу Yi.

Враховуючи, що розряд T>2> рівний “1" при формуванні тільки двох сигналів Y>18> і Y>20>, то схему(мал. 2.4) будемо використовувати для формування Y>1>, Y>20>, для яких співпадають молодші чотири розряди та для Y>18>, для якого молодш³ чотири розряди сп³впадають з кодом порожньо¿ операторно¿ вершини. А для всіх інших Y схему можна спростити (мал.2.5.).

T>6>ùe

1 Y>i>

T>3>ùe

Мал.2.5. Спрощена схема формування сигналу Y>i>.

Зг³дно з наведеними схемами запишемо формули для вс³х Y>i>.

Y>1>=ù (ù ù(T>2>+T>3>+T>4>+T>5>)+ùT>6>)

Y>2>= ù(T>3>+T>4>+ùT>5>+T>6>)

Y>3>= ù(T>3>+T>4>+ùT>5>+ùT>6>)

Y>5>= ù(T>3>+ùT>4>+T>5>+T>6>)

Y>7>= ù(T>3>+ùT>4>+T>5>+ùT>6>)

Y>8>= ù(T>3>+ùT>4>+ùT>5>+T>6>)

Y>9>= ù(T>3>+ùT>4>+ùT>5>+ùT>6>)

Y>10>=ù(ùT>3>+T>4>+T>5>+T>6>)

Сигнали м³крооперац³й y>j> отримаємо, об'єднуючи по “або" виходи відповідні операторам Y>i>, в яких зустрічається МО y>j>. При цьому будемо користуватися таблицею

Таблиця 2.5.

Розпод³л МО за м³кро-

командами

МО

номери МК

y>1>

1,2,3

y>2>

1,7,17

y>3>

5,10,14,20

y>4>

5,10,13,15

y>5>

2,8,10,12,15,18

y>6>

3,7,9,12,13,15

y>7>

7,11

y>8>

11

y>9>

1

y>10>

1

y>11>

3,14

y>12>

2,12,16

y>13>

5,8,17

y>14>

16

y>15>

8

y>16>

7,16

y>17>

9,11,12,14

y>18>

10,14,15

y>19>

2,10,12,15

y>20>

3,11,13

y>21>

13

y>22>

14

y>23>

15

y>24>

16

y>25>

17

y>27>

20

y>28>

20

y>29>

8

y>30>

5

На наступному етапі синтезуємо схеми РАМК і РМК, використовуючи ùRùS тригери. Скористаємося класичним методом синтезу регістрів і заповнимо сл³дуючу таблицю (табл. 2.6.).

Таблиця 2.6.

Синтез РАМК та РМК

С

A>i>

Qt

Qt+1

C>t>

ùR

ùS

0

0

0

0

0

*

*

0

0

1

1

0

*

*

0

1

0

0

0

*

*

0

1

1

1

0

*

*

1

0

0

0

1

*

1

1

0

1

0

1

0

1

1

1

0

1

1

1

0

1

1

1

1

1

1

*

У результат³ отримаºмо сл³дуючу схему для базового елементу РАМК та РМК (мал.2.6).

A>i>

1 S TT Q

С² C

R

“Reset” R ùQ

Мал. 2.6. Базовий елемент регістра.

Схема РАМК містить 6 таких елемент³в, а схема РМК - 21. При побудові схеми сигнали ùT>1>..ùT>21> будемо знімати з ³нверсних виходів елемент³в регістрів. Кількість мікросхем ПЗП визначимо за формулою: N>ПЗП>­=]R/3[, де R - розрядн³сть м³крокоманди R=21, N>ПЗП>=7. Для зберігання м³кропрограми досить однієї лінійки ПЗП, оскільки Q>ПЗП>=8, тобто одна мікросхема розрахована на зберігання 256 трьохб³тових комбінацій, а в нашому випадку потрібно тільки 38. При побудові схеми будемо записувати в РАМК інверсію адреси, а до ПЗП будемо подавати адресу з ³нверсних виходів елемент³в регістра, таким чином, ми заощадимо 6 елементів-³нвертор³в у СФА. З врахуванням вищесказаного побудуємо схему автомата з примусовою адресацією м³крокоманд(мал. 2.7).


TYPE=RANDOM FORMAT=PAGE>41


3.СИНТЕЗ АВТОМАТА З ПРИРОДНОЮ АДРЕСАЦІЄЮ М²КРОКОМАНД

3.1. Принцип роботи автомата.

При природній адресації микрокоманд існує три формата МК (мал. 3.1.).

П >1> FY >m> ОМК

П >1> FX >l> >1> FA >r> УМК1 П >1 >Æ >l> >1> FA >r > УМК2

Мал.3.1. Формати м³крокоманд автомата з природною адресац³ºю..

Тут формат ОМК відповідає операторн³й вершині, УМК1-умовній, а УМК2-вершині безумовного переходу. При подачі сигналу “пуск" лічильник ЛАМК обнуляється, і за сигналом СІ відбувається запис МК до регістра. СФМО формує відповідні МО при П=1 або видає на всіх виходах нулі при П=0. СФА в залежності від П і вм³сту поля FX, формує сигнали Z>1> і Z>2>. Сигнал Z>1> дозволяє проходження синхро³мпульс³в на л³чильний вхід ЛАМК, а Z>2> дозволяє запис до лічильника адреси наступної МК з приходом синхро³мпульсу.

Визначимо розрядн³сть полів. l=]log>2>(L+1)[, де L-число умовних вершин. L=6, l=3

m=]log>2>T[ Т- число наборів м³крооперац³й, що використовуються в ГСА, в нашому випадку Т=17, m=5

r=]log>2> Q[, Q - кількість м³крокоманд.

3.2.Перетворення початкової ГСА.

Перетворення буде полягати в тому, що до всіх операторних вершин, пов'язаних з кінцевою, вводиться сигнал y>0>, а між всіма умовними вершинами, які пов'язані з кінцевою, вводиться операторна вершина, що містить сигнал y>0>. Крім цього, в ГСА вводяться спеціальні вершини безумовного переходу X>0>, відповідні формату УМК2. Введення таких вершин необхідне для виключення конфліктів адресації м³крокоманд. У автоматі з природною адресац³ºю (рис3.2.) при істинності(помилковість) логічної умови перехід здійснюється до вершини з адресою на одиницю великим, а при (помилковість)істинності ЛУ перехід відбувається за адресою, записаною в полі FA. У нашому випадку будемо додавати одиницю при істинності ЛУ або при переході з операторной вершини. Якщо в одній точці сходиться декілька переходів по “1" або з операторно¿ вершини, то всі вершини з яких здійснювався перехід, повинні були б мати однакову (на одиницю меншу ) адресу, н³ж наступна команда. Але це неможливо.

Z>1 >+1

с³ Z>2 > А ЛАМК

“Пуск”

1 ПЗП

РМК

FY П FX FA

СФМО

СФА Z>1>

y>0>.....y>i> к ОА

Z>2>

Мал.3.2. Структурна схема автомата з природною адресац³ºю.

Для виключення подібних ситуацій вводять спеціальну вершину безумовного перходу (мал. 3.3). Дані вершини додаºмо таким чином, щоб в одній точці сходилася будь-яка кількість переходів по “0" і тільки один по “1" або з операторно¿ вершини. З врахуванням вказаних перетворень отримаємо перетворену ГСА (мал. 3.4).

X>0> 0

1

Мал. 3.3. Вершина безумовного переходу.

3.3.Формування вмісту керуючої пам'яті.

На перетворен³й ГСА виділимо м³крокоманди форматів ОМК, УМК1, УМК2. У результаті отримаємо 63 МК. Виконаємо їх адресацію. Для цього запишемо всі природні послідовності команд (ланцюжки вершин, перехід між якими здійснюється по “1" або через операторну вершину). У результаті отримаємо:

a>1>=[O>1>,O>5>]

a>2>=[ O>2> ,O>6> ,O>7> ,O>36> ,O>48> ,O>51> ,O>55> ,O>34> ,O>47> ,O>49> ,O>56> ,O>59> ,O>12> ,O>16> ,O>45>]

a>3>=[ O>3> ,O>9> ,O>13 >,O>18>]

a>4>=[ O>4> ,O>10> ,O>11>]

a>5>=[ O>8> ,O>14> ,O>20> ,O>30> ,O>32> ,O>35>]

a>6>=[ O>60> ,O>15> ,O>21> ,O>22>]

a>7>=[ O>17> ,O>52> ,O>57> ,O>61> ,O>62>]

a>8>=[ O>19> ,O>28> ,O>29>]

a>9>=[ O>23> ,O>25> ,O>27> ,O>31> ,O>37> ,O>44> ,O>43> ,O>53> ,O>54>]

a>10>=[ O>24> ,O>26>]

a>11>=[ O>33>]

a>12>=[ O>38> ,O>41> ,O>42>]

a>13>=[ O>39> ,O>40>]

a>14>=[ O>46>]

a>15>=[ O>50>]

a>16>=[ O>58>]

a>17>=[ O>63>]>­>

Перерахуємо в таблиці адресації (табл. 3.1) підряд всі послідовності a>1>-a>17 >і закодуємо їх R-розрядним кодом. R=]log>2>N[, N-кількість м³крокоманд (N=63, R=6). Закодуємо також оператори Y>i>, поставивши їм у відповідність п`ятирозрядний код. Будемо використовувати те ж кодування, що і в автоматі з ПА.(табл. 2.3., 2.4). У таблиці 3.2 відобразимо вміст керуючої пам'яті, заповнивши поля FX, FY, FA.

Таблиця 3.1. Таблиця 3.1.

(продовження)

Адресац³я МК.

мк

А>1>А>2>А>3>А>4>А>5>А>6>

O>1>

000000

O>5>

000001

O>2>

000010

O>6>

000011

O>7>

000100

O>36>

000101

O>48>

000110

O>51>

000111

O>55>

001000

O>34>

001001

O>47>

001010

O>49>

001011

O>56>

001100

O>59>

001101

O>12>

001110

O>16>

001111

O>45>

010000

O>3>

010001

O>9>

010010

O>13>

010011

O>18>

010100

O>4>

010101

O>10>

010110

O>11>

010111

O>8>

011000

O>14>

011001

O>20>

011010

O>30>

011011

O>32>

011100

O>35>

011101

O>60>

011110

O>15>

011111

O>21>

100000

O>22>

100001

O>17>

100010

O>52>

100011

O>57>

100100

O>61>

100101

O>62>

100110

Таблиця 3.2.

Вм³ст керуючо¿ пам`ят³ автомата з природною адресац³ºю.

МК

Адреса

П

FY

Формула переходу

FX

FA

А>1>А>2>А>3>А>4>А>5>А>6>

T>1>

T>2>T>3>T>4>

T>5>T>6>T>7>T>8>T>9>T>10>

O>1>

000000

1

100

000010

O>1>®ùP>1>O>2>+P>1>O>5>

O>5>

000001

1

000

010010

O>5>®O>9>

O>2>

000010

1

101

010001

O>2>®ùP>2>O>3­>+P>2>O>6>

O>6>

000011

1

110

011000

O>6>®ùP>3>O>8>+P>3>O>7>

O>7>

000100

1

001

001001

O>7>®ùX>1>O>34>+X>1>O>36>

O>36>

000101

0

010

000000

O>36>®O>48>

O>48>

000110

1

110

111110

O>48>®ùP>3>O>63>+P>3>O>51>

O>51>

000111

0

000

010000

O>51>®O>55>

O>55>

001000

1

101

011110

O>55>®ùP>2>O>60>+P>2>O>34>

O>34>

001001

0

000

111000

O>34>®O>47>

O>47>

001010

1

101

111011

O>47>®ùP>2>O>46>+P>2>O>49>

O>49>

001011

1

010

111100

O>49>®ùX>2>O>50>+X>2>O>56>

O>56>

001100

0

010

001000

O>56>®O>59>

O>59>

001101

1

100

101100

O>59>®ùP>1>O>27>+P>1>O>12>

O>12>

001110

0

001

000000

O>12>®O>16>

O>16>

001111

1

100

110011

O>16>®ùP>1>O>24>+P>1>O>45>

O>45>

010000

0

101

010000

O>45>®K

O>3>

010001

1

110

010101

O>3>®ùP>3>O>4>+P>3>O>9>

O>9>

010010

0

000

001000

O>9>®O>13>

O>13>

010011

1

100

100010

O>13>®ùP>1>O>17>+P>1>O>18>

O>18>

010100

1

000

101100

O>18>®ùO>27>

O>4>

010101

1

001

010010

O>4>®ùX>1>O>9>+X>1>O>10>

O>10>

010110

1

010

001110

O>10>®ùX>2>O>12>+X>2>O>11>

O>11>

010111

1

000

011111

O>11>®O>15>

O>8>

011000

0

001

101000

O>8>®O>14>

O>14>

011001

1

001

100111

O>14>®ùX>1>O>19>+X>1>O>20>

O>20>

011010

0

000

101000

O>20>®O>30>

O>30>

011011

0

001

111000

O>30>®O>32>

O>32>

011100

1

110

000101

O>32>®ùP>3>O>36>+P>3>O>35>

O>35>

011101

0

100

011000

O>35>®K

O>60>

011110

0

001

011000

O>60>®ùO>15>

O>15>

011111

0

000

110000

O>15>®O>21>

O>21>

100000

1

110

101010

O>21>®ùP>3>O>23>+P>3>O>22>

O>22>

100001

0

101

100000

O>22>®K

O>17>

100010

1

110

001110

O>17>®ùP>3>O>12>+P>3>O>52>

O>52>

100011

0

000

110000

O>52>®O>57>

O>57>

100100

1

110

001001

O>57>®ùP>3>O>34>+P>3>O>61>

O>61>

100101

1

011

000111

O>61>®ùX>3>O>51>+X>3>O>62>

O>62>

100110

1

000

101100

O>62>®O>27>

O>19>

100111

0

001

110000

O>19>®O>28>

Таблица 3.2.

(продовження)

O>28>

101000

1

011

110101

O>28>®ùX>3>O>33>+X>3>O>29>

O>29>

101001

1

000

101100

O>29>®O>27>

O>23>

101010

0

000

111000

O>23>®O>25>

O>25>

101011

0

001

001000

O>25>®O>27>

O>27>

101100

0

000

100000

O>27>®O>31>

O>31>

101101

1

100

110110

O>31>®ùP>1>O>38>+P>1>O>37>

O>37>

101110

0

001

010000

O>37>®O>44>

O>44>

101111

1

001

010000

O>44>®ùX>1>O>45>+X>1>O>43>

O>43>

110000

1

010

001110

O>43>®ùX>2>O>12>+X>2>O>53>

O>53>

110001

0

000

001000

O>53>®O>54>

O>54>

110010

1

000

001100

O>54>®O>56>

O>24>

110011

1

110

101100

O>24>®ùP>3>O>27>+P>3>O>26>

O>26>

110100

0

100

111000

O>26>®K

O>33>

110101

0

100

000000

O>33>®K

O>38>

110110

1

101

111001

O>38>®ùP>2>O>39>+P>2>O>41>

O>41>

110111

1

110

111101

O>41>®ùP>3>O>58>+P>3>O>42>

O>42>

111000

1

000

001110

O>42>®ùO>12>

O>39>

111001

1

110

100011

O>39>®ùP>3>O>52>+P>3>O>40>

O>40>

111010

1

000

011011

O>40>®O>30>

O>46>

111011

0

100

000000

O>46>®K

O>50>

111100

0

100

000000

O>50>®K

O>58>

111101

0

100

000000

O>58>®K

O>63>

111110

0

100

000000

O>63>®K

3.4. Синтез схеми автомата.

Синтезуємо схему, що формує сигнал Z>1>. Сигнал Z>1> рівний 1, якщо ознака П=0 або П=1 і при цьому логічна умова, що перевіряється, істинна. Скористаємося формулою Z>1> для автомата з ПА, яка в залежності від коду умови передає на вихід Z>1> значення відповідного ЛУ.

Z>1>=X>1>ùT>2>ùT>3>T>4>+X>2>ùT>2>T>3>ùT>4>+X>3>ùT>2>T>3>T>4>+P>1>T>2>ùT>3>ùT>4>+P>2>T>2>ùT>3>T>4>+P>3>T>2>T>3>ùT>4>

З врахуванням вищенаведених вимог запишемо формули для сигналів Z>1> ³ Z>2> в автоматі з природною адресац³ºю.

Z>1>=ùT>1>+T>1>(X>1>ùT>2>ùT>3>T>4>+X>2>ùT>2>T>3>ùT>4>+X>3>ùT>2>T>3>T>4>+P>1>T>2>ùT>3>ùT>4>+P>2>T>2>ùT>3>T>4>+P>3>T>2>T>3>ùT>4>)

Z>2>=ùZ>1>

Або , зв³вши до заданого базису отримаºмо:

Z>1>=ù ù(ù(ù(ù ù(A+B+C+D)+E+F)+ùT>1>)+ùT>1>), где

A=ù ù( X>1>ùT>7>ùT>8>T>9>)=ù(ùX>1>+T>2>+T>3>+ùT>4>)

B=ù ù( X>2>ùT>7>T>8>ùT>9>)=ù(ùX>2>+T>2>+ùT>3>+T>4>)

C=ù ù( X>3>ùT>7>T>8>T>9>)=ù(ùX>3>+T>2>+ùT>3>+ùT>4>)

D=ù ù( P>1>T>7>ùT>8>ùT>9>)=ù(ùP>1>+ùT>2>+T>3>+T>4>)

E=ù ù( P>2>T>7>ùT>8>T>9>)=ù(ùP>2>+ùT>2>+T>3>+ùT>4>)

F=ù ù( P>3>T>7>T>8>ùT>9>)=ù(ùP>3>+ùT>2>+ùT>3>+T>4>)

Схема формування МО подібна СФМО автомата з ПА, але поява сигналів на виходах y>i> можлива тільки при П=0, тобто коли поточна м³крокоманда відповідає операторн³й вершині. Тому схему формування Y>i> змінимо таким чином: сигнал ùT>1>(ùП) кон`юнктивно об'єднаємо з кожним сигналом T>3>...T>7>,ùT>3>...ùT>7> (мал. 3.5). При цьому відсутність цих сигналів приведе до відсутності сигналів y>i, >бо комб³нац³я з ус³х нул³в на вход³ дншифратора в³дпов³даº порожн³й операторн³й вершин³. Виняток складає сигнал y>0>, для якого передбачений окремий розряд, тому його ми кон`юнктивно об'єднаємо з сигналом ùT>1>(ùП) (мал. 3.6.)

ùT>3>...ùT>7> T>3>..T>7>

1 T>3>...T>7 > 1 ùT>3>...ùT>7>

T>1> T>1 >

> >Мал.3.5. Схеми п³дключення ùП.

ùT>2>

1 y>0>

T>1>

Рис.3.6.Схема формування y>0>.

Схема базового елементу РМК аналогічна відповідній схемі в автоматі з ПА(мал2.6). У якості ЛАМК будемо використовувати лічильник, що має сл³дуючу функціональну схему(мал. 3.7.). Вхід V відповідає сигналу Z>1>, якщо він рівний 1, то ЛАМК збільшує свій вміст на 1, в протилежному випадку, на вихід передається інформація з входів A>1>...A>i>. Синтезуємо лічильник з кр³зним перенесенням. Для цього складемо сл³дуючу таблицю(табл.3.3).Таблиця складена для одного розряду.

A>1> CT

A>2> A>1>

A>3 >A>2>

A>4> A>3>

A>5 >A>4>

A>6 >A>5>

A>6>

V

C

R

Мал.3.7. Функц³ональне зображення

л³чильника.

Таблиця.3.3

Синтез схеми ЛАМК.

V

T

A>i>

Qt

Qt+1

ùR

ùS

0

0

0

0

0

*

1

0

0

0

1

0

0

1

0

0

1

0

1

1

0

0

0

1

1

1

1

*

0

1

0

0

0

*

1

0

1

0

1

1

1

*

0

1

1

0

1

1

0

0

1

1

1

1

1

*

1

0

0

0

0

*

1

1

0

0

1

1

1

*

1

0

1

0

0

*

1

1

0

1

1

1

1

*

1

1

0

0

1

1

0

1

1

0

1

0

0

1

1

1

1

0

1

1

0

1

1

1

1

0

0

1

Схема РМК містить 10 базових елемент³в. При побудові схеми сигнали ùT>1>...ùT>10> будемо знімати з ³нверсних виходів елемент³в регістра. Кількість мікросхем ПЗП визначимо за формулою: N>ПЗП>=]R/3[, де R - розрядн³сть м³крокоманди R=10, N>ПЗП>=4 Для зберігання м³кропрограми досить однієї лінійки ПЗП, оскільки Q>ПЗП>=8, тобто одна мікросхема розрахована на зберігання 256 трьохб³тових комбінацій, а в нашому випадку потрібно тільки 63. З урахуванням вищесказаного побудуємо схему автомата з природною адресацією м³крокоманд(мал. 3.8).


V

1 1

T>0>

1 1 1 Q>0 > S TT C

A>i> 1 1 R 1 1 R

C

“Reset”

T>1>

Q>1>

ùT>1> T>2>

1 Q>2>

ùQ>1>

ùT>2 >T>3>

1 Q>3>

ùQ>2>

........................................................................

Мал.3.8.Схема ЛАМК (усього 6 елемент³в, сигнали V,C,”Reset”,A>i> для вс³х, окр³м першого, не показан³).

TYPE=RANDOM FORMAT=PAGE>48


4.СИНТЕЗ АВТОМАТА З КОМБІНОВАНОЮ АДРЕСАЦІЄЮ М²КРОКОМАНД.

4.1.Принцип роботи автомата.

Автомат з комбінованою адресацією є комбінацією з автомат³в з примусовою і природною адресац³ºю . У даному автоматі адреса наступної МК задається в полі поточної м³крокоманди, при цьому при невиконанн³ ЛУ, що перевіряється, або при безумовному переході перехід здійснюється за заданою адресою, а при істинності - за адресою на одиницю більшу, ніж поточна. Формат команди автомата з КА наступний(мал. 4.1).


>1 >Y >m 1 >Х >k 1 > A > l >

Мал. 4.1.Формат команди автомата з КА.

Тут у полі Y міститься код, що задаº набір м³крооперац³й, у пол³ X-код логічної умови, що перевіряється, в полі А - адреса переходу при невиконанн³ логічної умови або при безумовному переході. Розрядн³сть полів визначається таким чином:

m=]log>2>T[ Т- число наборів м³крооперац³й, що використовуються в ГСА, в нашому випадку Т=17, m=5

k=]log>2>­(L+1)[ L-число логічних умов в ГСА, в нашому випадку L=6, l=3

l=]log>2>Q[ Q -кількість м³крокоманд.

Структурна схема автомата приведена на мал. 4.2. Автомат функціонує таким чином. Схема запуску складається з RS -тригера і схеми “&", яка блокує надходження синхро³мпульс³в на РМК. За сигналом “Пуск" тригер встановлюється в одиницю і відбувається запис м³крокоманди до регістру. Поле Y поступає на схему формування МО і перетворюºться в деякий набір м³крооперац³й. Поле X поступає на схему формування адреси, яка формує сигнал Z>2>, якщо перехід безумовний (X=0) або ЛУ, що перевіряється,дор³внюº нулю або сигнал Z>1> у випадку істинності ЛУ. За сигналом Z>2> вм³ст поля А надходить до л³чильника,а з нього - на адресний вхід ПЗП. А за сигналом Z>1> на адресний вхід також надходить вміст лічильника але тепер це адреса поточної м³крокоманди, збільшена на одиницю. За сигналом y>0> тригер скидається в нуль і автомат зупиняє свою роботу.

4.2. Перетворення початкової ГСА.

Перетворення будемо виконувати двома етапами. На першому - введемо сигнал y>0> до вершин, пов'язаних з кінцевою, якщо вершина умовна, то введемо

+1

Z>1>

СT

Z>2>

S T & ПЗП

“Пуск”

С² R РМК Y X A> > СФМО y­>0 >.... y>i> Z>1> СФА

до ОА Z>2>

Мал.4.2. Структурна схема автомата з КА.

додаткову операторну вершину з сигналом y>0>. Крім того, введемо додаткові вершини безумовного переходу, виходячи з тих же міркувань, що і для автомата з природною адресац³ºю. Будемо, однак, мати на уваз³, що для автомата з КА перехід з операторно¿ вершини прирівнюється до безумовного, тому в одній точці може сходитися будь-яка кількість безумовних переходів або переходів з операторних вершин і тільки один по істинності ЛУ, що перевіряється. На другому етапі виділимо м³крокоманди заданого формату, користуючись тими ж правилами, що і для автомата з ПА. З врахуванням вищесказаного отримаємо перетворену ГСА (мал. 4.3).

4.3.Формування вмісту керуючої пам'яті.

При формуванні вмісту керуючої пам'яті скористаємося тим же кодуванням наборів м³крооперац³й і ЛУ, що і для автоматів з ПА і природною адресац³ºю (табл. 2.3, 2.4). Для адресації м³крокоманд випишемо їх природні послідовності так само, як і для автомата з природною адресац³ºю, враховуючи, що природним вважається тільки перехід по істинності ЛУ.

a>1>=[O>1>,O>14>]

a>2>=[ O>2> ,O>19> ,O>18> ,O>46> ,O>6> ,O>42> ,O>43> ,O>44> ,O>9> ,O>38> ]

a>3>=[ O>3> ,O>15> ,O>17 >]

a>4>=[ O>4> ,O>5> ,O>7>,O>8>]

a>5>=[ O>10> ]

a>6>=[ O>11> ,O>13>]

a>7>=[ O>12>]

a>8>=[ O>16>,O>29>,O>30>,O>25>,O>37>,O>35>,O>36>]

a>9>=[ O>20> ,O>22> ]

a>10>=[ O>21>,O>23>]

a>11>=[ O>26>,O>32>,O>33>]

a>12>=[ O>27> ,O>24> ,O>45>]

a>13>=[ O>34>]

a>14>=[ O>39>]

a>15>=[ O>40>]

a>16>=[ O>41>]

a>17>=[ O>28>]>­>

a>18>=[O>31>]

Перерахуємо в таблиці адресації (табл. 4.1) підряд всі послідовності a>1->a>18 >і закодуємо їх R-розрядним кодом. R=]log>2>N[, N-кількість м³крокоманд(N=46, R=6). Закодуємо також оператори Y>i>, поставивши їм у відповідність п`ятирозрядний код. У таблиці 4.2 відобразимо вміст керуючої пам'яті, заповнивши поля FX, FY, FA.

Таблиця 4.1.

Адресац³я МК.

мк

А>1>А>2>А>3>А>4>А>5>А>6>

O>1>

000000

O>14>

000001

O>2>

000010

O>19>

000011

O>18>

000100

O>46>

000101

O>6>

000110

O>42>

000111

O>43>

001000

O>44>

001001

O>9>

001010

O>38>

001011

O>3>

001100

O>15>

001101

O>17>

001110

O>4>

001111

O>5>

010000

O>7>

010001

O>8>

010010

O>10>

010011

O>11>

010100

O>13>

010101

O>12>

010110

O>16>

010111

O>29>

011000

O>30>

011001

O>25>

011010

O>37>

011011

O>35>

011100

O>36>

011101

O>20>

011110

O>22>

011111

O>21>

100000

O>23>

100001

O>26>

100010

O>32>

100011

O>33>

100100

O>27>

100101

O>24>

100110

O>45>

100111

O>34>

101000

O>39>

101001

O>40>

101010

O>41>

101011

O>28>

101100

O>31>

101101

Таблиця 4.2

Вм³ст керуючо¿ пам`ят³.

№

A

FY

FX

FA

Оп.

A>1>A>2>A>3>A>4>A>5>А>6>

T>1>T>2>T>3>T>4>T>5>T>6>

T>7>T>8>T>9>

T>10>T>11>T>12>T>13>T>14>T>15>

O>1>

000000

000000

100

000010

O>14>

000001

000000

000

001101

O>2>

000010

000000

101

001100

O>19>

000011

000000

110

011110

O>18>

000100

000000

001

000111

O>46>

000101

010000

110

101101

O>6>

000110

000010

101

101100

O>42>

000111

000111

101

101010

O>43>

001000

000000

010

101011

O>44>

001001

010001

100

011010

O>9>

001010

001000

100

010100

O>38>

001011

101010

000

000000

O>3>

001100

000000

110

001111

O>15>

001101

000001

100

010111

O>17>

001110

000000

000

011010

O>4>

001111

000000

001

001101

O>5>

010000

000000

010

001010

O>7>

010001

000110

110

010011

O>8>

010010

101100

000

000000

O>10>

010011

000111

000

010110

O>11>

010100

000000

110

011010

O>13>

010101

100111

000

000000

O>12>

010110

001001

000

011010

O>16>

010111

000000

110

001010

O>29>

011000

000110

110

000111

O>30>

011001

000000

011

000110

O>25>

011010

000100

100

100010

O>37>

011011

001010

001

001011

O>35>

011100

000000

010

001010

O>36>

011101

000001

000

001001

O>20>

011110

001101

001

100000

O>22>

011111

000101

000

100110

O>21>

100000

001110

011

101001

O>23>

100001

000000

000

011010

O>26>

100010

000000

101

100101

O>32>

100011

000000

110

101000

O>33>

100100

000000

000

001010

O>27>

100101

000000

110

011000

O>24>

100110

001111

110

000101

O>45 >

100111

100011

000

000000

O>34>

101000

100000

000

000000

Таблиця 4.2.

(продовження)

O>39>

101001

100000

000

000000

O>40>

101010

100000

000

000000

O>41>

101011

100000

000

000000

O>28>

101100

001011

000

010001

O>31>

101101

100000

000

000000

4.4.Синтез схеми автомата.

При синтезі схеми скористаємося вже розробленими вузлами для автоматів з ПА і природною адресац³ºю. СФА автомата з КА аналогічна СФА автомата з природною адресац³ºю. Схеми СФМО, РМК аналогічні відповідним вузлам автомата з ПА (розд.2.4), а схема ЛАМК запозичена з автомата з природною адресац³ºю (розд.3.4). Відмінність полягає лише в тому, що для РМК буде потрібно 15 базових елемент³в. Враховуючи вищесказане, побудуємо схему автомата з комбінованою адресацією м³крокоманд(мал. 4.4).

TYPE=RANDOM FORMAT=PAGE>51


5. ПОРІВНЯЛЬНА ХАРАКТЕРИСТИКА АВТОМАТІВ.

5.1. Підрахунок апаратурних витрат.

Визначимо апаратурн³ витрати на кожний з автоматів. Оскільки синтез лічильника не був обов'язковим, то при визначенні апаратурних витрат будемо вважати його єдиним вузлом.

1. У автоматі з примусовою адресацією схема СФА містить 28 логічних елементів, СФМО - 57 ЛЕ, вузол запуску і схема “&" - 4 ЛЕ і, крім того, необхідно 6 елементів-³нвертор³в для отримання сигналів ùX>1>...ùX>3>,ùP>1>...ùP>3 >Також потр³бно 27 елементів для РАМК і РМК. Таким чином, сумарне число ЛЕ дорівнює 122. Для побудови РАМК і РМК також буде потрібно 27 тригер³в. Кількість ПЗП- 7.

2. У автоматі з природною адресацією схема СФА містить 12 логічних елементів, СФМО - 68 ЛЕ, вузол скидання - 2 ЛЕ і, крім того, необхідно 6 елементів-³нвертор³в для отримання сигналівùX>1>...ùX>3>,ùP>1>...ùP>3> і 10 елементів для РМК. Таким чином, сумарне число ЛЕ дорівнює 98. Для побудови РМК також буде потрібно 10 тригер³в. Кількість ПЗП- 4. Схема також містить один лічильник.

3. У автоматі з комбінованою адресацією схема СФА містить 10 логічних елементів, СФМО - 57 ЛЕ, вузол запуску і схема “&" - 4 ЛЕ і, крім того, необхідно 6 елементів-³нвертор³в для отримання сигналів ùX>1>...ùX>3>,ùP>1>...ùP>3> і 15 елементів для РМК. Таким чином, сумарне число ЛЕ дорівнює 92. Для побудови РМК також буде потрібно 15 тригер³в. Кількість ПЗУ- 5. Схема також містить один лічильник.

Складемо зведену таблицю витрат на синтезован³ автомати.(табл. 5.1.)

Таблиця 5.1.

Апаратурн³ витрати для синтезованих автоматів.

Тип автомата

Лог³чн³ елементи

Тригери

ПЗП

Л³чильники

ПА

122

27

7

0

ПрА

98

10

4

1

КА

92

15

5

1

5.2. Визначення автомата з мінімальними апаратурними витратами.

Заповнимо таблицю, де для кожного автомата знаком “+" відмітимо мінімальні витрати на даний тип елементів, а знаком “-" -нем³н³мальн³ (табл. 5.2.).

Таблиця 5.2.

Тип автомата

Лог³чн³ елементи

Тригери

ПЗП

Л³чильники

ПА

-

-

-

+

ПрА

-

+

+

-

КА

+

-

-

-

Як видно з таблиці 5.2., автомат з природною адресацією виграє по двом параметрам: по кількості тригер³в і ПЗП.

Для підтвердження правильності вибору автомата застосуємо також оцінку за Квайном (за сумарною кільк³стю входів елемент³в). Будемо вважати кількість входів у ЛЕ - 4, у тригера - 4, у ПЗП -9 і у лічильника - 9. З врахуванням вищенаведених значень, для автомата з ПА показник оцінки складе - 659, для автомата з ПрА - 477, для автомата з КА- 482.

Як видно з приведених оцінок, автомат з примусовою адресацією далеко не оптимальний, а автомати з природною і комбінованою адресацією по витратах практично однакові, але все ж автомат з ПрА має деяку перевагу перед автоматом з КА. Таким чином, результатом проектування буде схема автомата з природною адресацією м³крокоманд.