Схема с памет

Досега изходът зависеше само от входовете в момента. Последователностната схема помни: изходът ѝ зависи и от това какво е било преди. Като асансьор: какво ще направи при натискане на бутон зависи и от това на кой етаж е. Онова, което помни, е състоянието, а схемата е комбинационна логика плюс тригери (тема 21).

Математическият модел е крайният автомат S = {A, Z, W, δ, λ, a₁}:

• A – състоянията (етажите);
• Z и W – възможните входове и изходи;
• δ (функция на преходите) – „къде отивам след такта“;
• λ (функция на изходите) – „какво показвам“;
• a₁ – началното състояние, в което автоматът се нулира при включване.

Автоматът е краен, ако A, Z и W са крайни. Ако входовете действат само по такт, е синхронен, иначе е асинхронен. Записва се с таблица на преходите и на изходите, или нагледно с граф: кръгчетата са състоянията, а стрелките са преходите с условието си. Състоянието е устойчиво, ако няма вход, по който автоматът влиза в него и веднага излиза.

Светофарът като граф

Светофарът има четири състояния. В началното колите имат зелено и автоматът стои, докато някой не натисне бутона b. После по едно състояние на всеки такт: жълто за колите → зелено човече → всички спират → пак зелено за колите. Светлините зависят само от състоянието. Това е автомат на Мур: като светофар, цветът показва къде е автоматът.

Четири състояния искат два тригера (k ≥ log₂4). Кодовете не са избрани наслуки: 00 → 01 → 11 → 10. При всеки преход се сменя само един тригер (съседно кодиране, като кода на Грей). Ако два тригера се сменят наведнъж, например 01 → 10, за миг автоматът може да мине през 00 или 11. Това е състезание. Ако е критично, автоматът заседва в грешно устойчиво състояние.

Сега автоматът е в 00 – колите минават.

Светофар за пешеходци

Фигура 1.

Натисни „такт“ няколко пъти: автоматът стои в 00. Натисни бутона, после пак „такт“: тръгва по кръга и след четири такта се връща в 00. Жълтата стрелка е последният преход. Пусни часовника и натискай бутона когато искаш: светофарът го запомня, но пешеходците изчакват своя ред.

Мур – изходът е от състоянието: w = λ(a). В графа изходът е в кръгчето.

Мили – изходът е и от входа: w = λ(a, z). В графа е на стрелката: „вход/изход“.

🧒 Мур – светофар. Мили – автомат за напитки: реагира веднага на това какво си натиснал.

От графа до схемата

Синтезът е по рецепта:

1. граф и таблица на преходите;
2. кодиране на състоянията (тук съседно);
3. за всеки тригер – формулата на следващото му състояние. От таблицата: Q1' = Q0 и Q0' = Q̄1·(Q0 + b);
4. схема – D-тригери с тази логика на входовете, плюс логиката на изходите (зелено за колите = Q̄1·Q̄0, човече = Q1·Q0…);
5. проверка за състезания и времедиаграма.

Светофарът като схема

C b Q1 Q0 човек

Фигура 2.

Чертежът е със състоянието от фигура 1 – щракни там и гледай кои жици светят тук. Отдолу е един запис: бутонът е натиснат между 1,6 и 2,7 s. Схемата го забелязва чак при фронта на такта в 2,5 s. Оттам Q1Q0 минават 01 → 11 → 10 → 00 и при всеки преход се сменя само един бит. Човечето светва в състояние 11.

Мур или Мили: кой отговаря по-бързо

Да направим автомат, който казва w = 1, щом във входа z са дошли две единици подред.

• Като Мур трябват три състояния: A (няма единица), B (една единица), C (поне две). Изходът е 1 в C, т.е. едва след такта, в който е дошла втората единица.
• Като Мили стигат две състояния: A и B. Изходът е z·(в B): той е 1 още докато втората единица е на входа, без да се чака такт.

Мили е с по-малко състояния и отговаря с един такт по-рано. Затова пък изходът му следва входа направо и всяко трепване на z минава до w. Мур е по-спокоен. Входът тук е:

Детектор на „11“

C z Мур Мили

Фигура 3.

Бутоните горе са битовете на z един по един – щракни, за да ги смениш. При всяко „11“ розовото (Мили) светва в същия такт като втората единица, а жълтото (Мур) – един такт по-късно. При три единици подред и двата държат 1 и за третата. Виж и късия розов импулс около 6,5 s: точно след фронта Мили вече е в B, а z още не е паднал. Изходът на Мили следва входа без такт, затова се чете чак при следващия фронт.

Самопроверка

1. Каква е разликата между автомат на Мур и на Мили?

При Мур изходът зависи само от състоянието (w = λ(a)), при Мили – и от входа (w = λ(a, z)). Мили отговаря по-бързо и често с по-малко състояния; Мур е по-устойчив на смущения на входа.

2. Колко тригера трябват за автомат с 5 състояния?

k ≥ log₂5 ≈ 2,3 → 3 тригера.

3. Какво е съседно кодиране и защо се ползва?

Кодовете се избират така, че при всеки преход да се сменя само един тригер. Тогава няма междинни грешни състояния – няма състезания.

4. Кога не може съседно кодиране без допълнителни състояния?

Ако в графа има контур с нечетен брой състояния или състояние има повече съседи от броя на тригерите. Тогава се добавят „излишни“ състояния, пренасочват се дъги или се взимат повече тригери.

5. Как се записва изходът в графа на Мур и в графа на Мили?

Мур – в кръгчето на състоянието; Мили – върху стрелката, заедно с входа (z/w).