Глава 3. Синтез асинхронных потенциальных автоматов

3.1. Основная модель цифровых автоматов

Цифровые автоматы (последовательностные схемы), элементарные примеры которых были рассмотрены в § 2.4, по способу воздействия на них входных информационных сигналов подразделяются на три основных класса: асинхронные потенциальные автоматы, синхронные автоматы и асинхронные импульсные автоматы. Каждый, из классов автоматов можно разделить на несколько типов по другим признакам.

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

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

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

Так как воздействия активных уровней входных сигналов на асинхронный потенциальный автомат происходят

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

Для проектирования цифровых автоматов используются не только ЛЭ, но и элементы памяти (ЭП), в качестве которых чаще всего используются триггеры (анализ работы двух типов триггеров был выполнен в § 2.4). Элементы памяти и триггеры являются элементарными автоматами, поэтому они, как и цифровые автоматы, делятся на те же три класса. Классы автоматов различаются только типом используемых в них ЭП: с потенциальным воздействием входных сигналов, импульсным воздействием только одного тактового сигнала или с импульсным воздействием нескольких входных сигналов (может быть и одного).

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

В отличие от КС значения выходных сигналов автомата в данный момент времени зависят не только от значений входных сигналов в этот же момент времени, но и от предыдущих их значений. Из этого следует, что цифровые автоматы реализуют функциональную связь уже не между отдельными значениями входных и выходных сигналов, а между их последовательностями. Таким образом, в отличие от КС работу автоматов следует

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

Рис. 3.1

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

В общем случае автомат содержит и имеет физических входов, на которые подаются сигналы и к физических выходов, с которых снимаются сигналы При фиксированных значениях внутренних сигналов автомат ведет себя подобно некоторой КС, т. е. реализует однозначное соответствие между значениями входных и выходных сигналов. Однако при изменении входных сигналов его реакция может выразиться в изменении внутренних сигналов. Если затем подать прежние значения входных сигналов, то соответствие между значениями входных и выходных сигналов может оказаться совсем другим.

На основании основной модели автомата его внутренние и выходные сигналы можно задать некоторыми системами переключательных функций:

где

Система функций (3.1) называется функцией переходов автомата, а система функций (3.2) — функцией выхода. Эти системы функций можно представить в векторной форме:

где

Введем основные определения. Состоянием входа автомата называется n-мерный вектор где или 1 — значение входного сигнала автомата Всего может быть различных состояний входа т. е. множество возможных состояний входа состоит из элементов:

Внутренним состоянием автомата называется m-мерный вектор где или 1 — значение выходного сигнала Всего может быть различных внутренних состояний т. е. множество возможных внутренних состояний состоит из элементов:

В дальнейшем внутреннее состояние часто будем называть просто состоянием автомата.

Состоянием выхода автомата называется -мерный вектор где или 1 — значение выходного сигнала автомата Всего может быть 2 различных состояний выхода т.е. множество возможных состояний выхода состоит из элементов:

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

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

паре необходимо поставить в соответствие определенные значения необходимо задать соотношения

где

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

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

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

Два состояния входа (два внутренних состояния и называются соседними, если они различаются значением только одного входного сигнала (выходного сигнала Соседним изменением состояний входа называется изменение некоторого состояния входа на любое соседнее состояние входа При соседних изменениях состояний входа изменяется только один входной сигнал автомата Изменения внутренних состояний называются переходами. Переходы являются соседними, если при этом внутреннее состояние изменяется на соседнее состояние

Все приведенные выше определения в равной степени относятся как к асинхронным потенциальным автоматам, так и к синхронным, а в большей своей части — и к асинхронным импульсным автоматам. Для краткости цифровые автоматы,

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

Теории автоматов посвящена обширная литература различного уровня сложности. Абстрактная теория автоматов достаточно полно изложена в [5, 7, 18, 19], а практические вопросы ее реализации — в [8, 20]. В указанной литературе рассматриваются в основном синхронные и асинхронные потенциальные автоматы. Основы теории асинхронных импульсных автоматов приведены в [21]. Аналитическая теория этих автоматов разработана в [10, 22, 23].