Автомат с конечной памятью

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

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

(2)

где y^j- выход автомата в j-й такт зависит от состояния ав­томата в (j-1)-й такт, z^j-1 - состояние автомата в (j-1)-й такт.

(3)

x^j - вход автомата в j-й такт, F и G - некоторые логические функции состояния выхода и входа.

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

(4)

или, в частности

(5)

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

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

Рассмотрим в качестве примера автомата с конечной памятью схему электронного счетчика, применяемого в цифровых вычислительных устройствах (рис. 2). Задача этой схемы состоит в подсчете количества импульсов, поступивших на ее вход. т.е. в преобразовании количества импульсов в двоичный код числа, выра­жающего это количество.

Для этой цели образуем цепь из триггеров, показанную на ри­сунке. Здесь выход каждого предыдущего триггера соединен с вхо­дом последующего. Пусть сначала все триггеры находятся в нулевом состоянии, т.е. напряжение на их выходах равно U₀. При поступле­нии первого импульса на вход триггера Т₁, на его выходе появится напряжение U₁, и на входе триггера T₂, положительный импульс нап­ряжения, на который он не реагирует. Второй импульс заставит T₁ , вернуться в нулевое состояние, в результате чего напряжение на его выходе изменит свое значение с U₁ на U₀ , что вызовет отрица­тельный импульс на входе T₂ и его переход в единичное состояние. Таким образом, T₁ будет изменять свое состояние после каждого входного импульса, T₂, после каждого второго импульса, T₃ - после каждого четвертого и т.д., T_k - после каждого 2^k-1 импульса на входе схемы. Если теперь мы будем состояние каждого триггера рассматривать, как значение соответствующего разряда двоичного числа, то состояние всей цепи из r триггеров будет представлять собой число (в двоичной системе счисления) импульсов, поступивших на вход схемы.

Pис.2 Счетчик импульсов на триггерах

Емкость этой схемы - максимальное число R импульсов, кото­рые могут быть ею сосчитаны, определяется числом r триггеров и равно максимальному двоичному числу, состоящему из r разрядов, а именно R=2^r.