Граф - автомат
Cтраница 3
Эти соотношения означают, что таблица переходов эквивалентного автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов составляется так, что в каждую ее клетку записывается сигнал, которым отмечено состояние в данной клетке. При этом граф автомата Мили отличается только тем, что выходные сигналы из узлов графа перенесены на все ветви, входящие в данный узел. [31]
 |
Граф автомата Мили ( а и граф автомата Мура ( б. [32] |
Переход от задания автомата с помощью таблиц к заданию с помощью графа и обратный переход выполняется вполне очевидным образом. На рис. 2.28, а изображен граф автомата Мили, ранее заданного табл. 2.9 и на рис. 2.28, б - граф автомата Мура, соответствующий табл. 2.11. Описание автоматов в виде графов обладает большей наглядностью по сравнению с табличными способами, однако при большом числе состояний автомата такой способ задания становится достаточно громоздким. [33]
В случае задания автомата А графом для получения графа автомата В достаточно обозначить выходными сигналами не вершины графа, а стрелки, входящие в соответствующие вершины. [34]
Переход от задания автомата с помощью таблиц к заданию с помощью графа и обратный переход выполняется вполне очевидным образом. На рис. 2.28, а изображен граф автомата Мили, ранее заданного табл. 2.9 и на рис. 2.28, б - граф автомата Мура, соответствующий табл. 2.11. Описание автоматов в виде графов обладает большей наглядностью по сравнению с табличными способами, однако при большом числе состояний автомата такой способ задания становится достаточно громоздким. [35]
Автомат с унитарным кодированием состояний может строиться по схеме автомата Мили или по схеме Мура. Триггеры соединяются между собой цепями передачи так же, как и в сдвигающих регистрах. Цепи передачи между триггерами соответствуют ребрам графа автомата. Цепи передачи управляются сигналами, представляющими значения конъюнкций, отмеченных на соответствующих ребрах графа автомата. [36]
 |
Скелет графа автомата, допускающего соседнее кодирование состояний. [37] |
При этом значение сигнала возбуждения не зависит от состояния переключаемого элемента Tt. Для некоторых автоматов соседнее кодирование оказывается невозможным. Например, соседнее кодирование невозможно, если граф автомата содержит циклы с нечетным числом входящих в цикл состояний. [38]
 |
Граф, допускающий соседнее кодирование. [39] |
Пример автомата с соседним кодированием состояний приведен на рис. 9.10. На каждом переходе в автомате вырабатывается только один сигнал возбуждения. Для некоторых автоматов соседнее кодирование оказывается невозможным. Например, соседнее кодирование невозможно, если граф автомата содержит циклы с нечетным числом входящих в цикл состояний. При введении пустых состояний увеличивается время выполнения операций, осуществляемых под управлением автомата. [40]
Рассмотрим еще один метод, называемый графическим методом структурного синтеза. Представим автомат в виде графа. Так как при получении (2.3) используются конъюнкции входных переменных, соответствующих кодам входных сигналов, договоримся в начале дуг графа автомата вместо входных сигналов записывать сразу эти конъюнкции. [41]
В случае автоматов Мура выходные сигналы связаны только с состояниями автомата, которым соответствуют вершины графа. Поэтому на графе автомата Мура выходными сигналами отмечаются не ребра, а вершины. При этом каждая вершина имеет два обозначения, например AtIYt. Легко видеть, что граф автомата, в котором отмечена начальная вершина, полностью задает закон функционирования автомата. [42]
 |
Граф цифрового ав-томата Мили. [43] |
Графическое представление закона функционирования автомата осуществляется с помощью графов. При этом узловыми окружностями ( вершинами графа) отображаются внутренние состояния автомата, а переход из одного состояния в другое - ветвями ( дугами) графа, на которых указываются также входные переменные в момент изменения его внутреннего состояния. Выходные переменные для автоматов Мура наносятся внутри вершин графа, а для автомата Мили - на дугах. На рис. 4.5 в качестве примера показаны в общем виде фрагменты графов автоматов Мура и Мили. [44]
Автомат с унитарным кодированием состояний может строиться по схеме автомата Мили или по схеме Мура. Триггеры соединяются между собой цепями передачи так же, как и в сдвигающих регистрах. Цепи передачи между триггерами соответствуют ребрам графа автомата. Цепи передачи управляются сигналами, представляющими значения конъюнкций, отмеченных на соответствующих ребрах графа автомата. [45]
Страницы: 1 2 3 4