Основные сведения о дискретных автоматах

Логические устройства могут быть классифицированы по разным признакам. По способу ввода/вывода (информации) логические устройства делятся на:

-последо­вательные,

-параллельные

-последовательно-параллельные.

Последовательным называется устройство, в котором входные переменные подаются на вход, а выходные переменные снимаются с выхода не одновре­менно, а последовательно, разряд за разрядом.

Параллельным называется устройство, в котором все разряды входных пере­менных подаются на вход, и все разряды выходных переменных снимаются с выхода одновременно.

В последовательно-параллельных устройствах входные и выходные пере­менные представлены в разных формах. Или переменные подаются последо­вательно символ за символом на вход, а с выхода они снимаются одновре­менно, или наоборот.

По принципу действия все логические устройства делятся на два класса:

-комбинационные (логические);

-последовательные (последовательностное).

Комбинационными устройствами или автоматами без памяти называют управляющие ло­гические устройства, выходные сигналы которых однозначно определяются только действующей в данный момент на входе комбинацией переменных и не зависят от значений переменных, которые действовали на входе ранее.

Последовательными устройствами, или автоматами с памятью, называют логические устройства, выходные сигналы которых определяются не только действующей в данный момент на входе комбинацией переменных, но и всей последовательностью входных переменных, которые действовали в предше­ствующие моменты времени.

Комбинационную схему можно представить в виде m – k -полюсного элемента (рис. 3.4). Входное слово (входной алфавит) комбинационной схемы задается набором символов (сигналов)

М = (m₁, т₂... m_i ), а выходное слово (выходной алфавит) принимает значения из выходных символов (сигналов) К = (k₁, k₂,... k_i)...

 

 

Рисунок 3.4 – Комбинационная схема

В дискретный момент времени совокупность выходных сигналов однозначно определяется набором входных сигналов, которые поступили на вход в данный момент времени. Каждая входная переменная и каждая выходная переменная принимают конечное число значений (0 или 1).

Комбинационная схема может характеризоваться:

-чис­лом входных сигналов,

-числом выходных сигналов,

-логической формулой

-таблицей истинности.

Для управления работой комбинационной схемы вводят управляющие тактовые сигналы, чтобы новый набор входных сигна­лов поступил после окончания переходных процессов.

Математической моделью управляющего логического устройства является дискретный автомат.

Если на выходные сигналы влияет не внутреннее состояние комбинационной схемы, а только изменение входных сигналов, то такая схема называется ав­томатом без памяти или примитивным автоматом.

Если на набор исходных сигналов K влияет не только набор входных сигналов, но и внутреннее состояние комбинационной схемы, то такая схема называется автоматом с памятью или полным автоматом. Автомат с памятью задается тремя наборами переменных: М; К; Q, где Q — набор переменных, которые отображают внутреннее состояние схемы (рис. 3.5).

 

 

Рисунок 3.5 – Полный автомат

В большинстве схем полных автоматов объединение комбинационных эле­ментов позволяет составить такое устройство, сигналы, на выходе которого, будут непосредственно зависеть не от входных сигналов, а лишь от объеди­нения входных сигналов и внутреннего состояния автомата в момент посту­пления сигналов на входе.

Поэтому для описания работы автомата в таблице истинности указывают:

-набор входных сигналов;

-набор соответствующих внутренних состояний;

-набор выходных сигналов.

Кроме того, обязательным является условие раз­деления всех наборов сигналов по временным интервалам. Специально ого­варивается внутреннее состояние автомата до прихода входного сигнала - Q₀, внутреннее состояние автомата, которое изменяется с приходом входного сигнала Q_i и внутреннее состояние автомата после нового изменения вход­ного сигнала Q_i+1.

В зависимости от способа определения выходов различают два типа автоматов.

Автомат, у которого выходная переменная в любом такте t_i, зависит от внутреннего состояния и от входной переменной, называется автоматом Мили и задается уравнением

K_i = f(Q_i, M_i). (3.1)

Автомат, у которого выходная переменная в момент t_i, зависит только от внутреннего состояния в t_i -м такте, называется автоматом Мура и задается уравнением

K_i = f(Q_i) (3.2)

 

 

Контрольные вопросы и задания

1. Что называется булевыми константами и переменными в алгебре логики?

2. Почему логическое высказывание называется сложным?

3. Разъясните понятие операция. Что относится к основным булевым операциям?

4. Что отображают теоремы булевой алгебры? Сформулируйте теоремы де Моргана, поглощения и склеивания.

5. Назовите основные операции булевой алгебры. Как они описываются с помощью таблиц истинности; с помощью алгебраических выражений?

6. Какие функции заданы формулами x y, х / у, х → у, х у?

7. Приведите примеры описаний функций алгебры логики в виде:

-словес­ной формы;

-таблицы истинности;

-алгебраического выражения; в дизъ­юнктивной и конъюнктивной нормальных формах;

-последовательности чисел;

-куба.

8. Составьте таблицу истинности для конъюнкции трех логических пере­менных.

9. Объясните понятие логический элемент и логическая схема.

 

10. Что такое функционально полные системы?

11. Приведите условное графическое обозначение ЛЭ: И, ИЛИ, НЕ.

12. В чем заключается принцип двойственности и какое его практическое значение для построения схем логических устройств?

13. Приведите классификацию логических устройств по способу ввода/ вывода переменных; по принципу действия.

14. Какие алфавиты характерны для КС и автоматов?

15. Что такое автомат без памяти и полный автомат.