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

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

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

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

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

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

1) однакові вершини Y_i в різних ГСА відмічаємо однаковими мітками A_j;

2) однакові вершини Y_i в межах однієї ГСА відмічаємо різними мітками A_j;

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

На наступному етапі кожній ГСА поставимо у відповідність набір змінних P_nО {P₁...P_q}, де q=]log₂N[, N -кількість ГСА. Означувальною для ГСА Г_n ми будемо називати кон`юнкцию P_n=p₁^eЩ...Щp_qⁿ еО{0,1}, причому p⁰=щр, p¹=р. Об'єднана ГСА повинна задовольняти слідуючим вимогам:

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

2) при підстановці набору значень (е₁...e_n), на якому P_q=1 ГСА Г₀ перетворюється в ГСА, рівносильну частковій ГСА Г_q.

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

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

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

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

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

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

Часткові МСА М₁-М₅ побудуємо по ГСА Г₁-Г₅ (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками A_i, що входять до ГСА, крім кінцевої A_k.

ПОЧАТОК A₀

1

0 X₁ 1

2

A₁

3

0

4 X₂ A₂ 1

5

A₃

6

A₄

7

A₅

8

A₆

9

A₇

10

A₈

КіНЕЦь A_k

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

ПОЧАТОК A₀

1

A₁

2

A₇

0 3 1

X₃

4 5

A₉ A₆

6 7

A₁₀ A₁₂

8 9

A₃ A₂₂

10

A₁₁

КіНЕЦЬ A_k

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

ПОЧАТОК A₀

1

A₁₁

0 2 1

X₁

3 4

A₁₅ A₁₆

6

5 1

X₃ A₁₂

0

7 8

A₆ A₁₃

КіНЕЦЬ А_k

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

ПОЧАТОК A₀

1

0 1

X₁

2

A₁₃

3

A₉

4

A₈

5

1 X₂

6 0

A₁₇

7

A₆

8

A₂

9

A₁₈

КіНЕЦЬ A_k

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

ПОЧАТОК A₀

1

A₁

2

A₆

3

A₁₉

4

0 1

X₁

5

0 X₂

1

6

A₂₀

7

A₁₇

8

A₂

9

A₂₁

КіНЕЦЬ A_k

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

Стовпці МСА відмітимо всіма мітками A_i­, що входять до ГСА, крім початкової A₀. На перетині рядка A_i і стовпця A_j запишемо формулу переходу f_ij від оператора A_i до оператора A_j. Ця функція дорівнює 1 для безумовного переходу або кон`юнкції логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з міткою A_i у вершину з міткою Aj.

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

Таблиця 1.1

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

Часткові МСА М₁-М₅ наведені в табл.1.2-1.6

Таблиця 1.2

Часткова МСА М₁

Таблиця 1.3

Часткова МСА М₂

Таблиця 1.4

Часткова МСА М₃

Таблиця 1.5

Часткова МСА М₄

Таблиця 1.6

Часткова МСА М₅

На наступному етапі побудуємо об'єднану МСА М₀, в якій рядки відмічені всіма мітками А_i, крім А_k, а стовпці - всіма, крім А₀. На перетині рядка А_i і стовпця А_j запишемо формулу переходу, яка формується таким чином: F_ij=P₁f_ij¹+...+P_nf_ijⁿ (n=1...N). Де f_ijⁿ-формула переходу з вершини А_i у вершину А_j для n-ої ГСА. Наприклад, формула переходу А₀®А₁ буде мати вигляд F_0,1=щx₁щp₁щp₂щp₃+ щp₁щp₂p₃+ +p₁щp₂щp₃. У результаті ми отримаємо об'єднану МСА М₀ (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г₀ як ГСА Г_n, ми підставляємо певний набір P_n=1, при цьому змінні p₁..p_q не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину А_i перехід завжди здійснюється при незмінному значенні p_q, то це значення p_q в рядку А_i замінимо на “1", а його інверсію на “0". Наприклад, у вершину А₃ перехід здійснюється при незмінному значенні щp₁ і щp₂, отже в рядку А₃ щp₁ і щp₂ замінимо на “1", а p₁ і p₂ на “0". У результаті отримаємо формули F_3,4=щp₃, F_3,11=p₃. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М₀ (табл.1.8).

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

A₀®щx₁щp₁щp₂щp₃A₁+щp₁щp₂p₃A₁+p₁щp₂щp₃A₁+x₁щx₂щp₁щp₂щp₃A₂+x₁x₂щp₁щp₂щp₃A₃+

+щx₁щp₁p₂p_3­A₈+x₁щp₁p₂p₃A₁₃+щp₁p₂щp₃A₁₄

A₁®щp₁щp₃A_2­+p₁щp₃A₆+щp₁p₃A₇

A₂®щp₁щp₂щp₃A₆+щp₁p₂p₃A₁₈+p₁щp₂p₃A₂₁

A₃®щp₃A₄+p₃A₁₁

A₄®A₅

A₅®А₆

Таблиця 1.7

Об`єднана МСА М_o

Таблиця 1.8

Об`єднана мінімізована МСА М_o

A₆®щp₁p₂p₃A₂+щp₁щp₂щp₃A₇+щp₁щp₂p₃A₁₂­+p₁щp₂щp₃A₁₉+щp₁p₂щp₃A_k

A₇®x₃p₃A₆+щp₃A₈+щx₃p₃A₉

A₈®x₂p₂p₃A₁₇+щp₂щp₃A_k+щx₂p₂p₃A_k

A₉®p_2­A₈+щp₂A₁₀

A₁₀®A₃

A₁₁®A_k

A₁₂®щp₂p₃A₂₂+p₂щp₃A₁₃

A₁₃®p₃A₉+щp₃A_k

A_14­®щx₁A₁₅+x₁A₁₆

A₁₅®x₃A₆+щx₃A_k

A₁₆®A₁₂

A₁₇®p₁щp₂щp₃A_2­+щp₁p₂p₃A₆

A₁₈®A_k

A₁₉®x₁щx₂A₂+x₁x₂A₂₀+щx₁A₂₁

A₂₀­®A₁₇

A₂₁®A_k

A₂₂®A_k

При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx₁+Вщx₁, де А і В -деякі вирази, а x₁ і щx₁-логічні умови переходу. Формули переходу для вершин А₃, А₄, А₅, А₉, А₁₀, А₁₁, А₁₃, А₁₄, А₁₅, А₁₆, А₁₈, А₂₀, А₂₁, А₂₂ вже є елементарними (розкладеними), а в інших є вирази виду А_n®x_j(А) +щx_jp_i(В). Тут p_i відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднаній ГСА бути не повинно. Для їх усунення скористаємося слідуючим правилом: додавання виразу [P_qА_n] не змінить формулу, якщо набір P_q не використовується для кодування ГСА або вершина А_n відсутня в ГСА з кодом P_q. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A₈®x₂p₂p₃A₁₇+щp₂щp₃A_k+щx₂p₂p₃A спрощується таким чином A₈=p₃(x₂p₂A₁₇+щx₂p₂A_k)+щp₃щp₂A_k=p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k=

1 X_j 0

P_i 0

1

Мал.1.6 Приклад чекаючої вершини P_i

=[щp₃p₂(x₂A₁₇+щx₂A_k)]+p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k+[p₃щp₂A_k]=щp₂A_k+p₂(x₂A₁₇+щx₂A_k). Тут вершина А₈ не зустрічається у ГСА ,в кодах яких присутні комбінації щp₃p₂ іp₃щp₂. Нижче наведено розклад усіх неелементарних формул переходу.

A₀=p₁(щp₂щp₃A₁)+щp₁(щx₁щp₂щp₃A₁+щp₂p₃A₁+x₁щx₂щp₂щp_3­A₂+x₁x₂щp₂щp₃A_3­+

+щx₁p₂p₃A₈+x₁p₂p₃A₁₃+p₂щp₃A₁₄)=p₁(щp₂щp₃A₁)+[p₁щp₂щp₃A₁]+

+щp₁(p₂(щx₁p₃A₈+x₁p₃A₁₃+щp₃A₁₄)+щp₂(щx₁щp₃A₁+p₃A₁+x₁щx₂щp₃A₂+

+x₁x₂щp₃A_3­))=p₁(щp₂A₁)+[p₁p₂A₁]+щp₁(p₂(p₃(щx₁A₈+x₁A₁₃)+щp₃A₁₄)+

+щp₂(щp₃(щx₁A₁+x₁x₂A₃+x₁щx₂A₂­)+p₃A₁))= p₁A₁+щp₁(p₂(p₃( щx₁A₈+

+x₁A₁₃)+щp₃A₁₄)+щp₂(щp₃(щx₁A₁+x₁(x₂A₃+щx₂A₂))+p₃A_1­))

A₁=щp_1­(p₃A₇+щp₃A₂)+p₁щp₃A₆+[p₁p₃A₆]= щp_1­(p₃A₇+щp₃A₂)+p₁A₆

A₂=p₁(щp₂p₃A₂₁)+щp₁(щp₂щp₃A₆+p₂p₃A₁₈)= p₁(щp₂p₃A₂₁)+[p₁щp₂p₃A₂₁]+

+щp_1­(щp₂щp₃A₆+[p₂щp₃A₆]+p₂­p₃A₁₈+[p₃щp₂A₁₈])=p₁(щp₂A₂₁)+щp₁(щp₃A₆+

+p₃A₁₈)=p₁(щp₂A₂₁)+[p₁p₂A₂₁]+щp₁(щp₃A₆+p₃A₁₈)=p₁A₂₁+щp₁(щp₃A₆+

+p₃A₁₈)

A₆=p₁(щp₂щp₃A₁₉)+[p₁щp₂p₃A₁₉]+щp₁(p₂p₃A₂+щp₂щp₃A₇+щp₂p₃A₁₂+p₂щp₃A_k)=

=p₁щp₂A₁₉+[p₁p₂A₁₉]+щp₁(p₂(p₃A₂+щp₃A_k)+щp₂(щp₃A₇+p₃A₁₂­))=p₁A₁₉+

+щp₁(p₂(p₃A₂+щp₃A_k­)+щp₂(щp₃A₇+p₃A₁₂))

A₇=p₃(x₃A₆+щx₃A₉)+щp₃A₈

A₈=p₃(x₂p₂A₁₇+щx₂p₂A_k)+щp₃щp₂A_k=p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k=

=[щp₃p₂(x₂A₁₇+щx₂A_k)]+p₃p₂(x₂A₁₇+щx₂A_k)+щp₃щp₂A_k+[p₃щp₂A_k]=щp₂A_k+

+p₂(x₂A₁₇+щx₂A_k)

A₁₂=щp₂p₃A₂₂+p₂щp₃A₁₃+[p₂p₃A₂₂]+[щp₂щp₃A₁₃]=p₃A₂₂+щp₃A₁₃

A₁₇=p₁щp₂щp₃A₂+[p₁щp₂p₃A₂]+щp₁p₂p₃A₆+[щp₁щp₂p₃A_6­]=p₁щp₂A₂+[p₁p₂A₂]+

+щp₁p₃A₆+[щp₁щp₃A₆]=p₁A₂+щp₁A₆­

A₁₉=x₁(щx₂A₂+x₂A₂₀)+щx₁A₂₁

Об'єднану ГСА Г₀ (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку А_i відповідною операторною вершиною Y_t, а кожний вираз X_i і P_j відповідними умовними вершинами.

30

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

Похожие работы

Аналіз теорії цифрових автоматів

Скачать

39975

7

1

... булевої алгебри. Аналітичний спосіб задання булевих функцій займає особливе місце в проектуванні цифрових машин. Фактично, всі перетворення над булевими ф-ціями, необхідні для побудови цифрових машин, ведуться на аналітичному рівні. Розглянемо області визначення булевоі ф-ції. Як уже відмічалось, між двійковими наборами і двійковими числами існує взаємнооднозначна відповідність. Отже, існує 2n рі ...

Абстрактные цифровые автоматы

Скачать

28503

20

4

... определенным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены для всех пар переходов (xi,aj). Частичным называется абстрактный цифровой автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар переходов (xi,aj). Абстрактный цифровой автомат называется инициальным, если на ...

Прикладна теорія цифрових автоматів

Скачать

10828

9

6

... a24(Y8) 10100 X5X6 X1D1 D1 D3 D3 R S a21 a25(Y3) 11001 X5X6 D1 D2 D5 T 2.2.3. Кодування станів Кодування станів буде проводитися за таким алгоритмом: 1.   Кожному стану автомата аm (m = 1,2,...,M) ставиться у відповідність ціле число Nm, рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ). 2.   Числа N1, N2, ..., ...

ПТЦА - Прикладная теория цифровых автоматов

Скачать

113094

120

81

... состоянии am. Рассмотренные выше абстрактные автоматы можно разделить на: 1)  полностью определенные и частичные; 2)  детерминированные и вероятностные; 3)  синхронные и асинхронные; Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( ai, zj). Частичным называется абстрактный автомат, у которого функция ...