2015-07-14
1431
Кодування полягає в зіставленні кожному стану автомата набору (коду) станів елементів пам'яті. При цьому набори для усіх станів повинні мати однакову довжину, а різним станам автомата повинні відповідати різні набори. Якщо елементи пам'яті двійкові, то їх число 
.
Перехід автомата з одного стану в інший здійснюється за рахунок зміни станів елементів пам'яті. Якщо автомат переходить із стану з кодом 010 в стан з кодом 100, то це означає, що тригер V1 переходить із стану 0 в стан 1, V2 - з 1 в 0, V3 - зберігає свій стан.
При функціонуванні автомата можуть з'явитися так звані змагання. Це явище виникає внаслідок того, що елементи пам'яті мають різні, хоча і досить близькі, часи спрацьовування. Різні також затримки сигналів збудження, елементарних автоматів, що поступають на вхідні канали, по логічних колах неоднакової довжини.
Якщо під час переходу автомата з одного стану в інше повинні змінити свої стани відразу декілька елементів, що запам'ятовують, то між ними починаються змагання. Той елемент, який виграє ці змагання, тобто змінить свій стан раніше, ніж інші елементи, може через ланцюг зворотного зв'язку змінити сигнали на входах деяких елементів, що запам'ятовують, до того, як інші, елементи, що беруть участь в змаганнях, змінять свої стани. Це може привести до переходу автомата в стан, не передбачений його графом. Тому в процесі переходу із стану qm в стан qs під дією вхідного сигналу xf автомат може виявитися в стані qk або ql: (рис. 2.11).
|
|
|
Рисунок 2.11 – Приклад перегонів
Якщо потім при тому ж вхідному сигналі xf автомат з qk і ql перейде в qs, то такі змагання є допустимими або некритичними.
Якщо ж в цьому автоматі є перехід, наприклад, з qk в qj ¹qs під дією того ж сигналу xf, то автомат може перейти в qj, а не в qs і правильність його роботи буде порушена (рис. 2.12.).
Рисунок 2.12 – Приклад порушення роботи автомату
Такі змагання називаються критичними змаганнями або перегонами і необхідно вживати заходи для їх усунення.
Усунути перегони можна апаратними засобами або використовуючи спеціальні методи кодування. Один із способів ліквідації перегонів полягає в тому, що виконується тактування вхідних сигналів автомата імпульсами певної тривалості. Передбачається, що окрім вхідних каналів х1,.., хl є ще канал С від генератора синхроімпульсів, по якому поступає сигнал С = 1 у момент приходу імпульсу і С = 0 при його відсутності. У зв'язку з цим вхідним сигналом на переході (qm, qs) буде не xf, а Cxf. Тоді, якщо тривалість імпульсу tc менше найкоротшого шляху проходження тактованого сигналу зворотного зв'язку за комбінаційною схемою, то до моменту переходу в проміжний стан qk сигнал C = 0, Cxf =0, що виключає перегони. Канал C - це фактично синхровхід тригера. Недолік методу - в трудності підбору необхідної тривалості імпульсу, оскільки вона залежить від багатьох чинників, непіддатливих строгому обліку.
|
|
|
Інший спосіб ліквідації перегонів полягає у введенні подвійної пам'яті. В цьому випадку кожен елемент пам'яті дублюється, причому перепис з першого елементу пам'яті в другій відбувається в момент С = 0(рис. 2.13).
Сигнали зворотного зв'язку для отримання функцій збудження та функцій виходів автомата знімаються з виходу другого тригера. Таким чином змагання можуть виникнути тільки між першими тригерами, сигнали зворотного зв'язку (виходи других тригерів) не можуть змінитися до тих пір, поки С не стане рівним 0. Але тоді Cхf = 0, перший тригер перестане сприймати інформацію, і гонок не буде.
Рисунок 2.13 - Елемент з подвійною пам'яттю.
Для усунення перегонів використовуються спеціальні методи протиперегонового кодування, серед яких найчастіше застосовується так зване сусіднє кодування станів автомата, при якому умова відсутності перегонів завжди виконана. При сусідньому кодуванні будь-які два, стани пов'язані дугою на графі автомата кодуються наборами, що відрізняються станами лише одного елементу пам'яті.
Сусіднє кодування не завжди можливе. Граф автомата, що допускає сусіднє кодування, повинен задовольняти ряду вимог, а саме:
- у графі автомата не повинно бути циклів з непарним числом вершин;
два сусідні стани другого порядку не повинні мати більше двох станів, що лежать між ними.
Під станами другого порядку розуміються такі два стани, шлях між якими по графові автомата складається з двох ребер (незалежно від орієнтації).
При сусідньому кодуванні зазвичай користуються картою Карно. В цьому випадку стани, пов'язані дугою, розташовують на сусідніх клітинах карти (рис. 2.14).
q1 ~ 000; q2 ~ 010; q3 ~110; q4 ~111; q5 ~101; q6 ~ 001; q7 ~100;
Рисунок 2.14 - Карта Карно для сусіднього кодування
Легко бачити, що при сусідньому кодуванні на кожному переході перемикається тільки один тригер, що принципово усуває перегони.
Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виразів функцій збудження пам'яті та функцій виходів, внаслідок чого складність комбінаційної схеми істотно залежить від вибраного кодування. Серед безлічі існуючих алгоритмів кодування розглянемо два що найчастіше зустрічаються:
алгоритм кодування для D - тригерів;
евристичний алгоритм кодування.
2.2.2 Алгоритм кодування для D -тригерів.
Згідно з даним алгоритмом при кодуванні необхідно виконати наступне:
1. Кожному стану автомата q m (m = 1,2,.., M) ставиться у відповідність ціле число Nm, яке дорівнює числу переходів в стан q m (Nm дорівнює числу появ q m в полі таблиці переходів або числу дуг, що входять в q m при графічному способі завдання автомата).
2. Числа N1, N2,.., Nm упорядковуються по убуванню.
3. Стан q s з найбільшим Ns кодується кодом: 
, де R - кількість елементів пам'яті.
4. Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1: 00.. 01, 00.. 10,.., 01.. 00, 10.. 00.
5. Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім з трьома і так далі доки не будуть закодовані усі стани.
В результаті виходить таке кодування, при якому чим більше є переходів в деякий стан, тим менше одиниць в його коді. Так як для D - тригерів функції збудження однозначно визначаються кодом стану переходу, то очевидно, що вираження для функцій збудження будуть простіше. Цей метод особливо ефективний за відсутності мінімізації функцій збудження, що має місце в реальних автоматах з великою кількістю внутрішніх станів і вхідних змінних.
|
|
|
Зокрема, для автомата, заданого своїми таблицями переходів і виходів (див. нижче) при кодуванні на базі D -тригерів.
Таблиця 2.10 - Таблиця переходів Таблиця 2.11 - Таблиця виходів
| q 1 | q 2 | q 3 | q 4 | q 5 | q 1 | q 2 | q 3 | q 4 | q 5 | |||
| X 1 | q 1 | q 1 | q 5 | q 3 | q 1 | X 1 | y 1 | y 2 | y 1 | y 1 | y 1 | |
| X 2 | q 2 | q 3 | q 2 | q 3 | q 3 | X 2 | y 1 | y 3 | y 4 | y 2 | y 2 | |
| X 3 | q 3 | q 4 | q 2 | q 4 | q 2 | X 3 | y 4 | y 2 | y 2 | y 1 | y 3 |
q 1 ~ N 1 = 3 N 3 ® q 3 = 000
q 2 ~ N 2 = 4 N 2 ® q 2 = 001
q 3 ~ N 3 = 5 N 1 ® q 1 = 010
q 4 ~ N 4 = 5 N 4 ® q 4 = 100
q 5 ~ N 5 = 1 N 5 ® q 5 = 011
Аналогічно кодуванню внутрішніх станів для D - тригерів можна кодувати вихідні сигнали для будь-якого типу тригерів, тобто чим частіше виробляється цей вихідний сигнал yi, тим менше одиниць в його коді. Так для автомата маємо:
y 1 ~ N 1 = 6 N 1 y 1 = 00
y 2 ~ N 2 = 5 N 2 y 2 = 01
y 3 ~ N 3 = 2 N 3 y 3 = 10
y 4 ~ N 4 = 2 N 4 y 4 = 11
