Гонки в автоматі

Кодування внутрішніх станів ЦА.

Кодування полягає в зіставленні кожному стану автомата набору (коду) станів елементів пам'яті. При цьому набори для вс ?? ех станів повинні мати однакову довжину, а різним станам автомата повинні відповідати різні набори. У разі якщо елементи пам'яті виконавчі, то їх число

.

Перехід автомата з одного стану в інший здійснюється за рахунок зміни станів елементів пам'яті. У разі якщо автомат переходить зі стану з кодом 010 в стан з кодом 100, то це означає, що тригер V1 переходить зі стану 0 в стан 1, V2 - з 1 в 0, V3 - зберігає свій стан.

При функціонуванні автомата можуть з'явитися так звані змагання. Це явище виникає внаслідок того, що елементи пам'яті мають різні, хоча і досить близькі, часи спрацьовування. Різні також затримки сигналів збудження, що надходять на вхідні канали елементарних автоматів по логічним ланцюгах неоднакової довжини.

У разі якщо при переході автомата з одного стану в інший повинні змінити свої статки відразу кілька запам'ятовуючих елементів, то між ними починаються змагання. Той елемент, який виграє ці змагання, ᴛ.ᴇ. змінить свій стан раніше, ніж інші елементи, може через ланцюг зворотного зв'язку змінювати сигнали на входах деяких запам'ятовуючих елементів до того, як інші, які беруть участь в змаганнях елементи, змінять свої статки. Це може привести до переходу автомата в стан, не передбачене його графом. З цієї причини в процесі переходу зі стану am в стан as під дією вхідного сигналу Zf автомат може виявитися в стані ak або al. (Рис.36.).

У разі якщо потім при тому ж вхідному сигналі Zf автомат з аk і аl перейде в аs. то такі змагання є допустимими або некритичними.

У разі якщо ж в даному автоматі є перехід, наприклад, з аk в аj ¹ аs під дією того ж сигналу Zf. то автомат може перейти в аj. а не в аs і правильність його роботи буде порушена (мал.37.).

Такі змагання називаються критичними змаганнями або гонками і вкрай важливо вживати заходів для їх усунення.

Усунути гонки можна апаратними засобами або використовуючи спеціальні методи кодування. Один із способів ліквідації гонок складається в Тактирование вхідних сигналів автомата імпульсами определ ?? енной тривалості. Передбачається, що крім вхідних каналів х1. ХL є ще канал З від генератора синхроімпульсів, за яким надходить сигнал С = 1 в момент приходу імпульсу і С = 0 при його відсутності. У зв'язку з цим вхідним сигналом на переході (am. As) буде не Zf. а CZf. Тоді, у разі якщо тривалість імпульсу tc менше найкоротшого шляху проходження тактірованного сигналу зворотного зв'язку по комбінаційної схемою, то до моменту переходу в проміжний стан ak сигнал C = 0, CZf = 0, що виключає гонки. Канал С - ϶ᴛᴏ фактично синхровхід тригера. Недолік методу - в труднощі підбору необхідної тривалості імпульсу, тому що вона залежить від багатьох факторів, які чинять спротив суворому обліку.

Інший спосіб ліквідації гонок полягає у введенні подвійний пам'яті. У цьому випадку кожен елемент пам'яті дублюється, причому перепис з першого елемента пам'яті в другій відбувається в момент С = 0 (мал.38.).

Сигнали зворотного зв'язку для отримання функцій збудження і функцій виходів автомата знімаються з виходу другого тригера. Таким чином змагання можуть виникнути тільки між першими тригерами, сигнали ОС (виходи друге тригерів) не можуть змінитися до тих пір, поки С не стане рівним 0. Але тоді CZf = 0, перший тригер перестане сприймати інформацію, і перегонів не буде.

Для усунення гонок використовуються спеціальні методи протівогоночного кодування, серед яких частіше нд ?? його застосовується так зване сос ?? еднее кодування станів автомата͵ при якому умова відсутності гонок нд ?? егда виконано. При сос ?? еднем кодуванні будь-які два, стану пов'язані дугою на графі автомата кодуються наборами, що відрізняються станами лише одного елемента пам'яті.

Сос ?? еднее кодування не вс ?? егда можливо. Граф автомата͵ допускає сос ?? еднее кодування, повинен задовольняти ряду вимог, а саме:

1) в графі автомата не повинно бути циклів з непарним числом вершин;

2) два сос ?? едніх стану другого порядку не повинні мати більше двох станів, що лежать між ними.

Під станами другого порядку прийнято розуміти такі два стану, шлях між якими по графу автомата складається з двох ребер (незалежно від орієнтації). Приклади графів автоматів допускають і не допускають сос ?? еднее кодування представлені на рис.39. і 39б. відповідно.

При сос ?? еднем кодуванні зазвичай користуються карткою Карно. В цьому випадку стану, пов'язані дугою, мають у своєму розпорядженні на сос ?? едніх клітинах карти (рис.40.).

Легко бачити, що при сос ?? еднем кодуванні на кожному переході перемикається тільки один тригер, що принципово усуває гонки.

Кодування станів і складність комбінаційної схеми автомата.

Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виразів функцій збудження пам'яті і функцій виходів, завдяки чому складність комбінаційної схеми істотно залежить від обраного кодування. Серед безлічі існуючих алгоритмів кодування розглянемо лише два найбільш часто зустрічаються:

1) алгоритм кодування для D -тригер;

2) евристичний алгоритм кодування.