2014-02-09
826
Рассмотрим построение графа переходов линейного (последовательностного) сумматора (рис. 5.7). В отличие от последовательного сумматора одноименные разряды последовательных слагаемых А и В поступают на вход не одновременно, а поочередно – сначала, например, ai, затем bi. При этом входная последовательность будет следующей: a0 b0 a1 b1 a2 b2... Выходная последовательность:
- c0 -c1- c2 -... Черточка (тире) обозначает, что выход не определен, т.е. не имеет значения.
 |
Рис. 5.7. Автомат линейного сумматора
Состояние S0 – начальное состояние. В это состояние автомат попадает после введения четного числа знаков ai, bi, если при вычислении ci не произошел перенос.
В S1 автомат попадает из S0 при аi=0, выходной сигнал еще не определен. При переходе из этого состояния ci=bi и переноса нет.
В состояние S3 автомат попадает после подачи на вход bi, если при вычислении ci произошел перенос в следующий разряд.
В S2 автомат переходит из S0 при ai=1 и из S3 при ai=0. При переходе из этого состояния ci=bi.
В состояние S4 автомат попадает из S3 при ai=1, выходной сигнал еще не определен (введено нечетное число знаков). При переходе из этого состояния ci=bi и перенос есть.
|
|
|
По состоянию, в которое автомат переходит после введения последовательности длины 2k, можно установить, является ли выходная последовательность в точности суммой C=А+B или нет. Если последним оказывается состояние S 0, то выходная последовательность представляет число С; если последним оказывается состояние S3, то выходная последовательность представляет число A+B+2k.
Рассмотренный в данном примере автомат не полностью определен: не имеющие значения выходы отмечены тире.
Автомат называется полностью определенным автоматом, если для любой пары “состояние-вход” известны следующее состояние автомата и выход.
В противном случае автомат является не полностью определенным.
