Последовательностные схемы

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

Устройства, реализованные на последовательностных логических элементах, называются цифровыми (конечными) автоматами (ЦА). Автомат, в отличие от комбинационной схемы, «помнит» прошлые воздействия, то есть имеет «память». Содержимое «памяти» определяет число внутренних состояний автомата или просто состояний.

Формально под определение ЦА подходит любое цифровое устройство, имеющее хотя бы один триггер. При этом триггер, регистр, счетчик, процессор (контроллер, микропроцессор) и целая ЭВМ – это все автоматы. Однако синтез триггера или регистра с позиций теории автоматов имеет скорее академический интерес. Практически разработчики пользуются типовыми ЦФУ, правила функционирования которых известны.

В среде разработчиков о синтезе автоматов начинают говорить, когда нужно разработать последовательностную схему цифрового блока, алгоритм работы которого, с одной стороны, не очевидно прост, то есть не воспроизводится каким-либо стандартным ЦФУ, с другой стороны, еще не очень сложен.

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

Несмотря на расплывчатость этого положения именно фактор обозримости имеет решающее значение. Если сложность устройства выходит за рамки обозримости, то его уже нецелесообразно проектировать как единый ЦА. Его или разбивают на систему отдельных автоматов или разрабатывают подобно структуре процессора. Построить же процессор по методике синтеза автоматов теоретически возможно, но практически не осуществимо.

Структура ЦА может быть реализована в виде автомата Мили, автомата Мура или автомата Хаффмана, эквивалентность которых доказана. Обобщенная структурная схема ЦА Хаффмана представлена на рис. 1.

Рис. 1. Структурная схема цифрового автомата Хаффмана

Триггерная подсистема ЦА образована элементами памяти (триггерами), которые хранят информацию о предистории (прошлых воздействиях). Комбинационная подсистема служит для преобразования кода входных сигналов Х и кода информации о состоянии автомата (триггерной подсистемы) Q в код выходных сигналов автомата Z и код сигналов Y, необходимых для изменения состояния автомата. Для функционирования ЦА необходимы сигналы синхронизации С, инициирующие переключение триггеров триггерной подсистемы.

Объем памяти триггерной подсистемы, необходимой для реализации алгоритма работы ЦА, определяется числом триггеров. Выходной сигнал одиночного триггера может принимать только два значения – 0 или 1, следовательно триггер может находится согласно постулату триггера в одном из двух состояниях. Для N триггеров триггерной подсистемы ЦА число возможных состояний равно 2 ^N. Тогда, если число необходимых состояний для работы ЦА равно М, то триггерная подсистема должна содержать k триггеров,

k ³ log₂ M,

где k – ближайшее целое число.

ЦА можно рассматривать как дискретный преобразователь информации, в котором в ответ на один из входных сигналов Х выдается один из выходных сигналов Z.

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

Граф переходов представляет собой графическую интерпретацию работы ЦА. Он удобен, если при первичном описании до конца не определен алгоритм работы ЦА. При числе состояний, большем 16, граф нагляднее таблицы состояний. При построении графа переходов каждое состояние ЦА отображается в виде окружности, в которой указывается номер или код соответствующего состояния. Переход из одного состояния в другое изображается в виде стрелки, соединяющей соответствующие состояния. При этом над каждой стрелкой записывается дробь, в числителе которой указывается код входного сигнала, под действием которого при очередном импульсе синхронизации произойдет указанный переход. В знаменателе дроби записывается текущий код выходного сигнала, соответствующий указанным состоянию и коду входного сигнала. Пример построения графа переходов приведен в [4, рис. 17.18, c. 575].

Таблица состояний содержит G + 1 столбец, где G – число различных входных сигналов, которые могут действовать на входе автомата, и 2 ^N строк, где N – число триггеров триггерной подсистемы. В первом столбце таблицы перечисляются все 2 ^N возможные состояния, в которых может находиться ЦА. На пересечении j -го столбца и i -й строки записывается дробь. В числителе дроби указывается состояние, в которое попадает ЦА после прихода очередного импульса синхронизации, если он находился в i -м состоянии и на его входе действует j -й входной сигнал. В знаменателе дроби указывается текущее значение выходного сигнала, существующее в автомате до прихода очередного импульса синхронизации при нахождении его в i -м состоянии при действии j -го входного сигнала. Пример построения таблицы состояний приведен в [4, таблица 17.7, c. 575].