Пример 4. Рассмотрим построение графа переходов линейного (последовательностного) сумматора (рис

Рассмотрим построение графа переходов линейного (последовательностного) сумматора (рис. 5.7). В отличие от последовательного сумматора одноименные разряды последовательных слагаемых А и В поступают на вход не одновременно, а поочередно – сначала, например, ai, затем bi. При этом входная последовательность будет следующей: a₀ b₀ a₁ b₁ a₂ b₂... Выходная последовательность:

- c₀ -c₁- c₂ -... Черточка (тире) обозначает, что выход не определен, т.е. не имеет значения.

Рис. 5.7. Автомат линейного сумматора

Состояние S₀ – начальное состояние. В это состояние автомат попадает после введения четного числа знаков ai, bi, если при вычислении ci не произошел перенос.

В S₁ автомат попадает из S₀ при аi=0, выходной сигнал еще не определен. При переходе из этого состояния ci=bi и переноса нет.

В состояние S₃ автомат попадает после подачи на вход bi, если при вычислении ci произошел перенос в следующий разряд.

В S₂ автомат переходит из S₀ при ai=1 и из S₃ при ai=0. При переходе из этого состояния ci=bi.

В состояние S₄ автомат попадает из S₃ при ai=1, выходной сигнал еще не определен (введено нечетное число знаков). При переходе из этого состояния ci=bi и перенос есть.

По состоянию, в которое автомат переходит после введения последовательности длины 2k, можно установить, является ли выходная последовательность в точности суммой C=А+B или нет. Если последним оказывается состояние S ₀, то выходная последовательность представляет число С; если последним оказывается состояние S₃, то выходная последовательность представляет число A+B+2^k.

Рассмотренный в данном примере автомат не полностью определен: не имеющие значения выходы отмечены тире.

Автомат называется полностью определенным автоматом, если для любой пары “состояние-вход” известны следующее состояние автомата и выход.

В противном случае автомат является не полностью определенным.

Дата добавления: 2014-01-05