Выберем в качестве элементов памяти D-триггер, функция входов которого представлена в таблице стр. 33

1. Выберем в качестве элементов памяти D-триггер, функция входов которого представлена в таблице стр. 33.

2. Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналов L= ]log₂F [ = ]log₂3[ = 2, т.е. х₁, х₂.

Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log₂G[ = ]log₂4[ = 2, т.е. у₁, у₂. Количество внутренних состояний абстрактного автомата M = 4, следовательно количество двоичных элементов памяти (триггеров) R = ] log₂M [ = ]log₂4[ = 2.

Следовательно, структура ЦА с учетом того, что исходный автомат является автоматом Мили, в качестве элементов памяти используется D-триггер, может быть представлена в виде(рис. 29):

Кодирование входных, выходных сигналов и внутренних состояний представлена в таблицах:

Кодирование, в общем случае, осуществляется произвольно. Поэтому, например, каждому из сигналов Z_i можно поставить в соответствие любую двухразрядную комбинацию х₁, х₂. Необходимо только, чтобы разные выходные сигналы Z_i кодировались разными комбинациями х₁, х₂. Аналогично для W_i и a_i.

3. Получим кодированные таблицы переходов и выходов структурного автомата. Для этого в таблицах переходов и выходов исходного абстрактного автомата вместо Z_i, W_i, a_i cтавим соответствующие коды. Получим таблицы:

В кодированной таблице переходов заданы функции

В кодированной таблице выходов заданны функции:

4. При каноническом методе синтез сводится к получению функций:

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

Функции у₁ и у₂ могут быть непосредственно получены из таблицы выходов, например, в виде :

Однако выражения для у₁ и у₂ можно существенно упростить в результате минимизации, например, с помощью карт Карно:

В результате минимизации имеем:

Для получения выражений для D₁ и D₂ необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код

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

В результате минимизации получаем:

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

Функциональная схема автомата представлена на странице 41:

Дополнительно на функциональной схеме показан сигнал , устанавливающий автомат в начальное состояние (в данном случае 00).

Особенности синтеза автоматов на базе T, RS, JK триггеров.

Необходимо отметить, что синтез на базе указанных типов триггеров осуществляется аналогично выполненному синтезу на базе D-триггеров. В частности, п. 1¸3 (см. предыдущий параграф) абсолютно аналогичны. Кроме того, как следует из п.4 (см. предыдущий параграф) выходные сигналы не зависят от типа триггеров, поэтому выражение для y_i будут одинаковыми для любого типа триггеров. Однако функции возбуждения будут различны для разных типов триггеров и получаются на основании таблицы переходов исходного автомата и функции входов выбранного триггера. Без особых пояснений ниже приведены таблицы функций входов, функций возбуждений и карты Карно для минимизации функций возбуждения при использовании для синтеза автомата предыдущего параграфа T-, RS-, JK-триггеров.

T-триггер.

RS-триггер.

JK-триггер.

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

Кодирование внутренних состояний ЦА.

Гонки в автомате.

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

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Если автомат переходит из состояния с кодом 010 в состояние с кодом 100, то это означает, что триггер V₁ переходит из состояния 0 в состояние 1, V₂ – из 1 в 0, V₃ – сохраняет свое состояние.

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

Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т.е. изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие, участвующие в состязаниях элементы, изменят свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния a_m в состояние a_s под действием входного сигнала Z_f автомат может оказаться в состоянии a_k или a_l: (рис.36.).

Если затем при том же входном сигнале Z_f автомат из а_k и а_l перейдет в а_s, то такие состязания являются допустимыми или некритическими.

Если же в этом автомате есть переход, например, из а_k в а_j ¹ а_s под действием того же сигнала Z_f, то автомат может перейти в а_j, а не в а_s и правильность его работы будет нарушена (рис.37.).

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

Устранить гонки можно аппаратными средствами либо используя специальные методы кодирования. Один из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов х₁, ..., х_l имеется еще канал С от генератора синхроимпульсов, по которому поступает сигнал С = 1 в момент прихода импульса и С = 0 при его отсутствии. В связи с этим входным сигналом на переходе (a_m, a_s) будет не Z_f, а CZ_f. Тогда, если длительность импульса t_c меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние a_k сигнал C = 0, CZ_f=0, что исключает гонки. Канал С – это фактически синхровход триггера. Недостаток метода – в трудности подбора требуемой длительности импульса, т.к. она зависит от многих факторов, не поддающихся строгому учету.

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

Сигналы обратной связи для получения функций возбуждения и функций выходов автомата снимаются с выхода второго триггера. Таким образом состязания могут возникнуть только между первыми триггерами, сигналы ОС (выходы вторых триггеров) не могут измениться до тех пор, пока С не станет равным 0. Но тогда CZ_f = 0, первый триггер перестанет воспринимать информацию, и гонок не будет.

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

Соседнее кодирование не всегда возможно. Граф автомата, допускающее соседнее кодирование, должен удовлетворять ряду требований, а именно:

1) в графе автомата не должно быть циклов с нечетным числом вершин;

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

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

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

Легко видеть, что при соседнем кодировании на каждом переходе переключается только один триггер, что принципиально устраняет гонки.

 
Кодирование состояний и сложность комбинационной схемы автомата.

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

1) алгоритм кодирования для D-триггеров;

2) эвристический алгоритм кодирования.

 Алгоритм кодирования для D-триггеров.

Согласно рассматриваемому алгоритму при кодировании необходимо выполнить следующее:

1.   Каждому состоянию автомата а_m (m = 1,2,...,M) ставится в соответствие целое число N_m, равное числу переходов в состояние а_m (N_m равно числу появлений а_m в поле таблицы переходов или числу дуг, входящих в а_m при графическом способе задания автомата).

2.   Числа N₁, N₂, ..., N_m упорядочиваются по убыванию.

3.   Состояние а_s с наибольшим N_s кодируется кодом:, где R-количество элементов памяти.