Построение графа переходов и кодирование состояний памяти МПУ

На основании отмеченной ГСА строится граф переходов МПУ. Вершинами графа переходов являются отметки ГСА (отмеченные вершины ГСА). Рассматривая отмеченную граф-схему, определяем все пути переходов между отметками при различных значениях логических условий (входов). Полученные переходы отмечаем стрелками на графе переходов.

Над стрелками обозначаем значения логических условий *, при которых происходят эти переходы, а также микрокоманды (выходы) z_j, которые возбуждаются при этих переходах.

Граф переходов для примера 5.2 построенный по отмеченной ГСА (Рисунок 5.11), приведен на рисунке 5.12.

(00)

		(01)

	Рисунок 5.12

Далее необходимо провести кодирование состояний памяти. Прежде всего необходимо выбрать количество элементов памяти. Так как каждая вершина графа перехода (отметка ГСА) представляет собой одно из состояний элементов памяти МПУ, то число элементов памяти определяется из соотношения

2 ^{n -1} < N £ 2 ⁿ,

где N – количество вершин графа переходов (отметок ГСА);

n – количество элементов памяти.

Очевидно, что для примера 2 количество элементов памяти равно 2, так как N = 3.

Обозначим их y ₂ и y ₁.

Далее следует провести кодирование состояний элементов памяти (вершин графа переходов).

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

P

Задача обеспечения устойчивой без состязаний работы устройства стоит и при синтезе МПУ. Однако в настоящее время промышленность выпускает в сериях ИМС триггеры с двойной памятью, выполненные на одном кристалле в одном корпусе. Признаком двойной памяти является наличие на поле условного графического обозначения двух букв Т (Рисунок 5.13).

Рисунок 5.14

Рисунок 5.13

Функциональная схема элемента памяти с двойной памятью показана на рисунке 5.14. Входами элемента памяти являются входы первого триггера S₁ и R₁, выходами – выходы второго триггера Т₂. Сигналы с первого триггера на второй проходят только по сигналам со специального тактового генератора. Это приводит к тому, что хотя для разных элементов памяти состязания первых триггеров могут иметь место, состязания выходов элементов памяти, определяющих работу устройства, исключаются за счет разновременной подачи сигналов от тактового генератора.

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

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

Методику кодирования вершин графа переходов (состояний памяти) МПУ поясним на примере.

Пример 5.3 Пусть получен граф переходов МПУ (Рисунок 5.15). Для упрощения входные и выходные сигналы на графе не проставлены.

Рисунок 5.15

Произведем кодирование вершин графа. Так как вершин 5, то, очевидно, необходимо три элемента памяти – y ₃, y ₂, y ₁:

2² < 5 <2³.

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

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

Так, для графа (Рисунок 5.15) максимальное число переходов (3) связывает вершины

Y ₀ и Y ₁. Закодируем их при базе у ₃ у ₂ у ₁ соседними кодами (которые выбираются

произвольно):

Y ₀ 000, Y ₁ 001.

2. Присваиваются коды (по возможности соседние) тем вершинам, которые смежны с вершиной Y ₀. В примере это вершины Y ₃ и Y ₄. Присвоим им коды:

Y ₃ 100, Y ₄ 010.

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

В примере такой вершиной является вершина Y ₂. Ее код получим путем поразрядной

дизъюнкции кодов вершин Y ₁ и Y ₃, получим:

001 v 100 = 101.

Итак, Y ₂ 101 (при базе у ₃ у ₂ у ₁).

4. Указанная процедура выполняется, пока не будут закодированы все вершины графа переходов.

Закодируем состояния памяти МПУ для примера 5.2. Граф содержит 3 вершины, число элементов памяти равно 2. Действуя согласно изложенной методике, кодируем вершины графа переходов при базе (Рисунок 5.12):

Y ₀ 00, Y ₁ 01, Y ₂ 10.

Видим, что в этом случае обеспечено соседнее кодирование.