Пред.Страница След.Страница Раздел Содержание

---

9.2.3.1 УНИВЕРСАЛЬНЫЙ СПОСОБ КОДИРОВАНИЯ

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

Для пояснения описанного способа рассмотрим кодирование состояний автомата А1, заданного табл. 2. Диаграмма этого автомата изображена на рис. 9.33.а. Чтобы сделать процедуру кодирования нагляднее, обычно используют граф связей автомата. Такой граф строят следующим образом. Каждому состоянию автомата ставят в соответствие узел графа, а затем каждую пару узлов соединяют ребром, если между состояниями, соответствующими этим узлам, определен хотя бы один переход. Граф связей автомата А1 приведен на рис. 9.33.б.

а) б)

в) г)

Рис. 9.33. Диаграмма переходов (а), граф связей (б), граф связей с дополнительными состояниями при универсальном способе кодирования (в) и диаграмма, соответствующая этому графу (г) автомата А1

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

Таблица 3. Кодированная таблица переходов автомата А1

si	pk
	00	01	11	10
001	(001)	(001)	001	101
010	011	(010)	(010)	(010)
100	101	110	110	(100)
011	001	-	010	-
101	001	-	-	100
110	-	010	010	-

Заканчивая описание универсального способа кодирования, следует отметить, что он позволяет значительно упростить процедуру построения функций возбуждения. Нетрудно показать, что в силу большого числа используемых кодовых комбинаций, каждое состояние при построении функций возбуждения определяется не элементарной конъюнкцией, а одной внутренней переменной. При этом, в случае использования в качестве элемента памяти триггера типа D (элемента задержки), для каждого перехода из состояния, определяемого переменной y_i, под действием входного сигнала x_k в состояние, определяемое переменной y_j, соответствующий дизъюнктивный член функции возбуждения y_j’ имеет вид:

y_ix_k V y_iy_jx_k V x_jx_k = y_ix_k V y_ix_k.

Следовательно, если в автомате определены переходы в состояние y_j из состояний y_i1, y_i2, ...,y_il, соответственно под действием входных сигналов х₁, x₂, ..., x_l, то функция возбуждения y_j’ может быть записана так:

y_j’ = V ^l_k=1x_k(y_jk V y_j).

В последнем выражении не учитывается ситуации, в которых автомат должен оставаться в том же самом устойчивом состоянии при изменении входных сигналов. Построение функций возбуждения для рассматриваемого способа удобно выполнять непосредственно по диаграмме переходов автомата. Например, для диаграммы переходов, приведенной на  рис. 9.33.г, после преобразования имеем:

y₁'=x₁y₁ V x₁x₂(y₂ V y₃) ;    y₂'=x₁x₂y₁ V (x₁ V x₂)y₂ V x₂y₃ ;    y₃'=x₁x₂(y₁ V y₃)

---

Пред.Страница След.Страница Раздел Содержание