Гонки в автоматі - студопедія

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

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

Перехід автомата з одного стану в інший здійснюється за рахунок зміни станів елементів пам'яті. Якщо автомат переходить зі стану з кодом 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) евристичний алгоритм кодування.