3.11. Програмна реалізація логічних функцій і автоматів

Представлення автомата схемою з елементів - це історично перший і найбільше досліджуваний вид структурної реалізації автомата. Інший її вид - реалізація автомата програмою. Тут ми обмежимося питаннями програмної реалізації комбінаційних логічних автоматів, тобто систем логічних функцій.

Під програмою будемо розуміти пронумеровану послідовність команд k_{1, …} , k_s, узятих із деякого фіксованого набору (системи команд). Програма працює над скінченною множиною пронумерованих (або пойменованих ) двійкових елементів. Номер (або ім'я ) елемента називається його адресою ; ім'ям елемента часто буде служити ім'я логічної змінної, значення якої зберігаються в цьому елементі.

Система команд містить команди-оператори вигляду b:=f(a_{1, …} , a_p) (виконати операцію над вмістом елементів a_{1, …} , a_p і результат покласти в елемент b ) і двоадресні умовні переходи двох видів: 1) “якщо а, то i, інакше j ”( якщо a = 1, то перейти до виконання команди k_ί, інакше перейти до k_j ) ; 2 ) ” якщо ā ( a = 0 ) , то i , інакше j ”. Операція f ( a₁ , . . ., a_p ) - це логічна функція p змінних , зокрема, вона може бути константою 0 або 1. Якщо j - номер такої команди, то перехід можна вважати одноадресним : ” якщо a, то i, ( інакше перейти до наступної команди ) ”, а якщо i = j, то, безумовно, ” перейти до i “. Довільна з команд зазначених типів може бути заключною, що вказується словом ” кінець “.

Процесом обчислення програми k₁, . . ., k_s називається послідовність кроків k ( 1 ), k ( 2 ), . . ., k ( t ), на кожному з яких виконується одна команда програми. Ця послідовність визначається так : 1) k ( 1) = k1; 2) якщо k (1) = kr - оператор, то k ( i + 1 ) = k_r+1 ; 3) якщо k ( 1) - умовний перехід, то номер команди k ( i + 1 ) вказується цим переходом; 4) якщо k ( i ) - заключна команда, то процес обчислення зупиняється після її виконання. Число t називається часом її виконання.

Програма П обчислює (або реалізує) логічну функцію f ( х₁ , … , х_n )= у, якщо для будь-якого двійкового набору σ = ( σ ₁ , . . . , σ _n ) при початковому стані пам'яті х₁ = σ ₁ , х₂ = σ ₂, . . ., х_n = σ _n (стан інших елементів несуттєвий ) програма через скінченне число кроків зупиняється, і при цьому в елементі у лежить величина f ( σ ₁ , . . . , σ _n).

Якщо під складністю схеми, що реалізує автомат, звичайно розуміється число елементів у схемі, то складність програми можна розуміти в різноманітних змістах: 1) число команд у тексті програми; 2) обсяг проміжної пам'яті, тобто число елементів для збереження проміжних результатів обчислень; 3) час обчислення, що буде характеризуватися двома величинами: середнім часом t_ср (П) =1/2ⁿ τ_р(σ) і максимальним часом t_макс(П) = max_ τ_р(σ), де сума і максимум беруться по всіх 2ⁿ двійковим набором σ, а τ_р - час роботи програми П на наборі σ.

Будь-якій схемі, що реалізує функцію f і містить N елементів, неважко поставити у відповідність програму, яка реалізує f і складається з N команд, у такий спосіб. Занумеруємо елементи схеми числами 1, 2, . . ., n так, щоб на будь-якому шляху від входу до виходу номери елементів зростали; при цьому номер 1 одержить один із вхідних елементів, а номер n - вихідний елемент. Нехай елемент е_ί схеми реалізує функцію φ _ί і до його входів приєднані виходи елементів е_j1, . . ., е_jp ( деякі з них, можливо, є входами схеми). Поставимо елементу е_ί у відповідність або елемент а_ί і команду а_ί = φ_ί ( а_j1 , . . ., а_jp ), якщо ί ≠ N; або елемент у і команду << у : = φ N( а_j1, . . ., а_jp ) кінець >>, якщо ί = N. Одержимо програму, що не містить умовних переходів ( такі програми будемо називати операторними ), в якій порядок команд точно відповідає нумерації елементів у схемі, а система команд - базису схеми.

Проблеми синтезу операторних програм, в основному, зводяться до проблем синтезу схем, зокрема, питання функціональної повноти системи команд і мінімізації власного тексту операторної програми збігаються відповідно з задачами функціональної повноти системи функцій і мінімізації схем. Оскільки операторна програма не містить умовних переходів, час її обчислення на будь-якому наборі той самий. Звідси t_max = = t_cp = N, тобто обидва види часової складності збігаються зі складністю тексту програми і, отже, при достатньо великих n майже для усіх функцій близькі до 2ⁿ ⁄ n. Навпаки, проблема мінімізації пам'яті ( за рахунок багатократного використання одного елемента для декількох проміжних результатів ) для операторних програм є нетривіальною комбінаторною задачею.

Інший ”крайній “ вид програм, що обчислює логічні функції, - програми, що складаються з команд виду в : = σ ( σ = 1 або σ = 0 ) і умовних переходів. Такі програми називаються бінарними програмами. Всяку булеву функцію F , що містить N букв, можна реалізувати бінарною програмою, що обчислює F за час t_max = N і що містить N команд умовних переходів ( а також дві команди у = 1 і у = 0, що в оцінках не беруть участі ). Для опису методу реалізації використовуємо представлення програми у вигляді графа, в якому вершини відповідають командам, а ребра - переходам. Нехай G₁ - граф програми для функції f₁ із початковою вершиною v₁₀ і двома заключними вершинами v_1z⁰ ( із командою у = 0 ) і v_1z¹ ( із командою у = 1 ) ; G₂ - граф програми для f₂ із початком v₂₀ і кінцями v_2z⁰ і v_2z¹. Тоді: 1) програма, граф G якої отриманий приєднанням G₂ до ”нуля“ G ₁, тобто ототожненням вершин v_1z⁰ і v₂₀¹ ; команда у : = 1 при цьому відкидається, обчислюють функцію f = f ₁ / f ₂; 2) програма, граф G якої отриманий приєднанням G ₂ до ”одиниці“ G ₁ ( ототожнюємо v_1z¹ і v₂₀ ), обчисляє f = f ₁  f₂; 3) програма, граф якої отриманий із G ₁ заміною команд v_1z⁰ і v_1z¹ на інверсні, обчислює f ₁. Зауважимо, що в графі G дві нульові заключні вершини. Їх необхідно ототожнювати.

Задачі

1. Чим відрізняється двозначна логіка від к-значної?

2. Дайте характеристику окремим компонентам таблиці істинності.

3. Побудуйте таблицю істинності для тризначної логіки.

4. Дайте визначення несуттєвої логічної змінної через таблицю істинності.

5. Побудуйте комбінаційну схему для наступних логічних функцій:

1. X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

2. X₁X₂X₃  X₂  X₁ X₂X₃  X₁X₃ ;

3. X₁X₂X₃ X₂X₃  X₁ X₂X₃  X₃ ;

4. X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

5. X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

6. X₁X₃ X₂  X₁ X₂X₃  X₁;

7. X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

8. X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ .

6. Виконайте мінімізації наступних логічних функцій аналітичним методом:

а)X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

б) X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

в)X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

г)X₁X₃ X₂  X₁ X₂X₃  X₁;

д)X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ ;

є)X₁X₂X₃  X₂  X₁ X₂X₃  X₁X₃ ;

з)X₁X₂X₃ X₂X₃  X₁ X₂X₃  X₃ ;

і)X₁X₂X₃ X₂  X₁ X₂X₃  X₁X₃ .

7. Виконайте мінімізацію логічних функцій задачі 6 з використанням карт Карно.

8. Сформулюйте відміни між автоматами Мілі і Мура.

9. У чому відміна між синхронними та асинхронними автоматами?

10. Побудуйте граф автомата, який заданий такими таблицями переходів- -виходів:

а)

x(n) (стан / вихід)

y(m) 0 1 2 3

0	1/0	2/0	0/0	0/1
1	1/1	2/0	2/1	1/1
2	1/0	0/1	0/1	0/0

б)

x(n) (стан / вихід)

y(m) 0 1 2 3

0	2/0	2/0	2/0	0/1
1	1/1	1/0	1/1	1/1
2	1/0	1/1	0/1	0/0

в)

x(n) (стан / вихід)

y(m) 0 1 2 3

0	1/0	2/0	0/0	0/1
1	0/1	1/0	0/1	1/1
2	2/0	0/1	2/1	0/0

г)

x(n) (стан / вихід)

y(m) 0 1 2 3

0	0/0	1/0	0/0	0/1
1	2/1	1/0	1/1	1/1
2	1/0	0/1	2/1	0/0

д)

x(n) (стан / вихід)

y(m) 0 1 2 3

0	2/0	0/0	2/0	0/1
1	1/1	1/0	0/1	1/1
2	0/0	1/1	2/1	0/0

69