Диаграммы Вейча

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

Схема конечного автомата

Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе других схем ЭВМ. Например, в схеме регистра сдвига информации добавляется цепь «установка в 0». Другие изменения связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов.

Лекция 7. Технические особенности конечных автоматов

В схемах ЭВМ все сигналы изменяются и воспринимаются, как правило, в дискретные моменты времени, обозначаемые числами натурального ряда t=0, 1,…. Для отметки моментов дискретного времени ЭВМ содержит специальный блок, вырабатывающий синхронизирующие импульсы (СИ), следующие через равные интервалы времени Т. Этот интервал времени Т определяет такт работы устройства.

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

Под действием СИ₁ формируются выходные сигналы Z_l(t) = g[a(t),x(t)], а под действием СИ₂ автомат переводится в новое состояние a(t+1). В результате структурная схема автомата имеет следующий вид:

Здесь U – сигналы возбуждения триггеров. Согласно приведенной схеме на входах каждого из триггеров стоят двухвходовые элементы И. На практике триггера часто выполняются в синхронном варианте (синхронные триггера), когда упомянутые элементы И включают в схему триггера. Например, схему синхронного RS-триггера можно рассматривать как состоящую из асинхронного RS-триггера, ко входам R и S которого подключены двухвходовые элементы И. На эти элементы кроме входных сигналов поступает синхронизирующий сигнал, обозначаемый буквой C.

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

Вторая техническая особенность конечного автомата связана с возможностью возникновения неустойчивых состояний и так называемых «гонок» в автомате. Понятие устойчивости заключается в следующем. Пусть в графе автомата мы имеем такой участок:

  Здесь оба перехода (a_i --> a_s) и (a_s --> a_f) выполняются под действием одного и того же входного сигнала x_j. Если длительность синхронизирующего сигнала СИ₂ больше времени перехода автомата из состояния a_i в состояние a_s, то сразу после перехода автомата в a_s может начаться переход в следующие состояния a_f под действием того же входного сигнала x_j. Таким образом, автомат может перескочить состояние a_s и к моменту времени t+1 оказаться не в a_s, как это требуется по графу, а в a_f. Состояние a_s в данном случае будет неустойчивым.

Другой неприятный момент заключается в том, что при работе автомата могут возникать так называемые «гонки» (состязания). Дело в том, что триггера в схеме имеют различные времена срабатывания, а также различные времена задержек сигналов обратной связи, которые поступают с выходов триггеров на их входы через комбинационную схему II. По этим причинам, если при переходе автомата из состояния a_i в a_s должны измениться состояния нескольких триггеров, то между выходными сигналами этих триггеров начинаются гонки. Тот триггер, который выиграет гонки, то есть изменит свое состояние раньше других триггеров, может через цепь обратной связи изменить сигналы возбуждения на входах других триггеров до того момента, как они изменят свои состояния. Это, очевидно, может вызвать переход автомата совсем не в то состояние, которое нужно графу. Например. Пусть a_i=101, a_s=010. Тогда при переходе из a_i в a_s под действием входного сигнала x_j меняются состояния всех триггеров. Допустим, что первый триггер изменил свое состояние раньше других. В этом случае автомат окажется в некотором промежуточном состоянии a_h=001, и если из этого состояния есть переход под действием сигнала x_j в a_l=011, то автомат в момент времени t+1может оказаться в a_l, а не в a_s.

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

Здесь под действием синхронизирующего сигнала СИ₁ формируются выходные сигналы Z_l(t) и переключаются триггера первого ряда. Под действием СИ₂ состояния триггеров первого ряда переписываются в соответствующие триггера второго ряда. Поскольку СИ₂ сдвинуты относительно СИ₁, а сигнал обратной связи о состоянии автомата снимается с триггеров второго ряда, то в момент поступления входного сигнала, то есть в СИ₁, состояние автомата не изменяется и продолжает оставаться прежним до СИ₂. Поэтому в такой схеме полностью обеспечивается устойчивость состояний и устраняется влияние гонок. Действительно, гонки сигналов с выходов триггеров второго ряда возможны в момент СИ₂, то есть в момент переключения этих триггеров. Но в момент СИ₂=1, СИ₁=0 и следовательно эти гонки никак не могут повлиять на состояния триггеров первого ряда, которые переключаются в момент СИ₁=1. Также не будет и неустойчивых состояний, поскольку автомат не может проскочить за один такт через одно состояние и перейти в следующее, ибо в момент перехода триггеров первого ряда в новое состояние, то есть в СИ₁, состояние триггеров второго ряда не меняется (СИ₂=0) и, следовательно, не могут измениться и сигналы возбуждения триггеров первого ряда, которые зависят от состояния триггеров второго ряда. Поэтому автомат не может проскочить состояние.

С целью упрощения построения схем автоматов, имеющих двойную память, промышленность выпускает специальные двухступенчатые триггера. Рассмотрим работу такого триггера на примере двухступенчатого JK-триггера.

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