Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

І\п, ..., Im' — входы запоминающего элемента.

Первое уравнение указывает на то, при каких условиях выход запоминающего элемента в такт «?z+l» будет рав­ няться 1, а второе — запреты на входы. Таким образом, эти два уравнения являются общими характеристическими урав­ нениями запоминающего элемента.

Рассмотрим на примере одно из применений запоминаю­ щих элементов.

Пусть необходимо построить 4-разрядный счетчик на ди­ намических триггерах, который последовательно во време­ ни выдавал бы следующий ряд чисел: 0, 10, 9, 8, 4, 14, 15, 17, 13; 5; 12, 6, 2, 3, 11, 0, и т. д. [2], т. е. после того, как на счетчике установится значение 11, в следующий момент счет­ чик сбрасывается в нуль и начинает счет сначала.

Таблица разбита на две части. В левой части указано со­ стояние счетчика в такт времени «я», в правой — состояние,

24

в которое он должен перейти в такт «?г+ 1». Из этой таблицы мы можем выписать условия, при которых триггер А переходит из состояния «О» (такт «п») в состояние «1» (такт «п + 1»), Это будет в следующих случаях:

ÄBCD + ÄBCD + ÄBCD + ÄBCD + ÄBCD.

При этих условиях триггер должен устанавливаться в 1, т. е. на его вход 5 должен поступить сигнал. Поэтому

5 .л = Ä B C D Ä AB CD + AB CD + ABCD + Ä B C D =

= ACD + ÄCD + ABD.

Аналогично' мы можем выписать условия, при которых триггер А должен перейти из состояния «1» в состояние «О», и они дадут нам уравнение для входа R

R A = ÄBCD + A B CD + ABCD + ABCD + ÄBCD =

= ACD + ÄCD + ABD.

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

В нашем случае это не имеет места для триггера А, поэто­ му дальнейшая минимизация входных уравнений триггера не­ возможна.

5 л (CD + CD + BD);

R A = А (CD + CD + BD).

Аналогичную процедуру проделаем для триггера В и по­ лучим уравнения:

S B = В (Ä C D + Ä C D ) ;.

R B — В (ACD + ÄCD).

Но в этом случае

ÄCD {ACD + ÄCD) = 0;

ACD (ACD + ÄCD) —0

25

Поэтому значения состояний триггера можно опустить, и окончательно уравнения входов примут вид:

S B = ACD + ACD;

R B = ACD + ÄCD.

Для триггера С таким же образом получим:

Sc — AB + DB',

Rc = BD + AB.

Для триггера Д получим следующие уравнения:

S D = D (А С + ВС );

RD = D {AB + ABC).

Здесь AB {АС + ВС) ф 0;

А ВС {АС + ВС) = 0.

Поэтому при втором терме {АВС) можно опустить значение и окончательно получим:

S B = D {АС + ВС);

RD = ABD +~ÄBC .

Рассмотрим построение того же счетчика на статических триггерах.

Уравнения для входов 5 и R всех триггеров будут так же, как и в первом примере, поэтому не будем их выписывать.

Уравнения для входа Т запишем, выписывая тр условия, при которых триггер изменяет свое состояние в «п + 1» такт времени, т. е. переходит в состояние «1» из состояния «0» или в состояние «0» из состояния «1».

Эти уравнения после упрощения примут вид:

Та = BD + CD + CD;

Тв = ABCD + ÄBCD + ABCD + Ä B C D ;

Tc — ACD + ACD + A B C + ÄBC;

TB = ACD + BCD + ABD + ÄBC.

Учитывая специфику входа T, отметим, что если одни и те же значения подаются на вход R и S, то лучше подавать их один раз на вход Т.

26

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

Эквивалентными называются такие состояния, которые удовлетворяют следующим условиям:

1. Им соответствует одно и то же состояние входа авто­ мата. >

2. Им соответствует одно и то же состояние выхода ав­ томата.

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

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

Следовательно, если каждый класс эквивалентных состоя­ ний заменить одним состоянием путе(м склеивания соответ­ ствующих вершин, то полученный граф переходов будем за­ давать то же отображение X -*■ Y, что и первоначальный.

27

с

ЦУ — внутреннее состояние автомата, и на пересечении і-й строки с /-м столбцом — значение выходного вектора У, ко­ торый вырабатывается на выходе, когда автомат находится в /-м внутреннем состоянии и на входе подан г-й вектор

Очевидно, что если двумвнутренним состояниям автома­ та соответствуют различные значения столбцов в таблице

выходов, то эти состояния не эквивалентны, так как в этих со­ стояниях отображения X -> Y различные. Отсюда, предвари­ тельно разбиваем все множество состояний на классы услов­ ных эквивалентных состояний, а именно в один и тот же класс попадают те состояния, которым соответствуют одина­ ковые значения столбцов в таблице выходов:

Хг== {Si, S2, S5 ;

К.2 —■(S3, Si, S6> S7}.

I

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

при любом другом возможном переходе из этих состояний , соответственно отображение X -*■ Y было одним и тем же.

Для проверки этого условия строим таблицу переходов.

Каждым строке, столбцу в таблице переходов соответст­ вуют то же, что в таблице выходов, и на пересечении і-й строки с /-м столбцом ставится класс условных эквивалент­ ных состояний, в который переходит автомат из состояния Y>j под воздействием Х{.

Если класс условных эквивалентных состояний, выделен­ ный на предыдущем шаге, не является классом эквивалент­ ных состояний, то состояниям этого класса будут соответст­ вовать различные значения (столбцов, что означает, что при дальнейших переходах отображения X -*■ Y различны для этих состояний.

Каждый класс К, разбивается на новые классы условных эквивалентных состояний, причем в один и тот же класс

29