Синтез цифрового автомата

Переход от одной формы задания автомата к другой

Задание цифрового автомата с помощью графа

Цифровой автомат может быть задан графом, количество вершин которого равно количеству состояний цифрового автомата. Вершины графа соединены дугами, указывающие возможный переход из одного состояния в другое, помеченных входными сигналами, при которых имеет место представляемый дугой переход. В автоматах Мили дуги также помечаются выходными сигналами, которые вырабатываются цифровым автоматом при переходе. В автоматах Мура выходными сигналами помечаются вершины графа. На Рис. 3.3‑3 представлен графы, соответствующие автомата Мили, заданному таблицей на рис. 3.3‑2(а), а на рис. 3.3‑4 приведен граф автомата Мура, заданного таблицей на рис. 3.3‑2 b).

Автомат Мили

Рис. 3.3‑3

Рис. 3.3‑4

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

На приведенном графе автомата Мили переход из вершины «а₁» в вершину «а₃» имеет место при входном сигнале z₃ с выработкой выходного сигнала v₅ и при входном сигнале z₂ с выработкой выходного сигнала v₃. Поэтому стрелка перехода из вершины «а₁» в вершину «а₃» помечена логическим условием:

z₃ v₅+z₂ v₃.

Любой автомат можно представить или в виде автомата Мура, или в виде автомата Мили.

Переход от автомата Мура автомату Мили.

Процедуру рассматриваемого перехода иллюстрирует следующий пример.

Пример

Имеется цифровой автомат Мура, заданный в виде таблицы, приведенной на рис. 3.3‑5 а).

Найти задание автомата Мили, эквивалентного заданному автомату Мура.

Решение

Из множества состояний автомата Мура составим подмножества, каждое из которых включает состояния, имеющие одинаковые переходы. Каждому полученному подмножеству поставим в соответствие состояние C_i искомого автомата Мили.

{ А₁, А₂} - C₁,

{ А₃, А₄} - C₂,

{ А₅} - C₃.

Таким образом, искомый автомат Мили будет иметь три состояния, что позволяет разметить колонки и строки таблицы задания искомого автомата Мили. Таблица имеет вид, приведенный на Рис. 3.3‑5 b). Заполнение клеток таблицы выполняется следующим образом.

Для того чтобы найти переход из С₁ при поступлении Z_,1, рассмотрим переходы, которые имеют место для любого из состояний автомата Мура, объединенных в подмножество, обозначенное С₁. Из элементов {А₁, А₂} возьмем, например, А₂. В таблице автомата Мура для этого состояния при входном сигнале z₁ имеет место переход в состояние А₃, которое входит в подмножество, обозначенное как С₂. Кроме того, состоянию А₃, как видно в той же таблице, соответствует выходной сигнал v ₂. Из этого следует, что в клетку, соответствующую переходу из С₁ по входному сигналу Z₁ нужно поставить C2 и указать в качестве вырабатываемого выходного сигнала v ₂.

Рассмотрим заполнение клетки перехода из состояния С₃ при входном сигнале Z₂. Из подмножества {А₅,}, соответствующего С₃, берем состояние автомата Мура А₅. В таблице автомата Мура для этого состояния при входном сигнале z₂ имеет место переход в состояние А₄, которое входит в подмножество, обозначенное как С₂. Кроме того, состоянию А₄, как видно в той же таблице, соответствует выходной сигнал v ₄. Из этого следует, что в клетку, соответствующую переходу из С₃ по входному сигналу Z₂ нужно поставить C2 и указать в качестве вырабатываемого выходного сигнала v₄. Аналогичным образом заполняются все клетки приведенной таблицы.

Переход от автомата Мили к автомату Мура.

Процедуру рассматриваемого перехода иллюстрирует следующий пример.

Пример

Имеется цифровой автомат Мили, заданный в виде таблицы, приведенной на Рис. 2.3‑4 b).

Найти задание автомата Мили, эквивалентного заданному автомату Мура

Решение

Составим множество неповторяющихся пар С_i v _j. Каждому элементу этого множества поставим в соответствие одно из состояний искомого автомата Мура.

С₂ v ₂ - B₁;

С₁ v ₂ - B₂;

С₃ v ₃ - B₃;

С₂ v ₄ - B₄;

С₁ v ₁ - B₅.

Для пяти состояний и трех входов таблица задания искомого автомата Мура будет иметь вид, приведенный на рис. 3.3‑5 с). Колонки таблицы помечены пятью найденными состояниями автомата и выходными сигналами (см. пары С_i v _j).

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

Переход из B₁ по входному сигналу Z₁ будет соответствовать переходу из С₂ по сигналу Z₁. Из таблицы на рис. 3.3‑5 b) видно, что при текущем состоянии С₂ по сигналу Z₁ будет переход в состояние С₁ и вырабатывается выходной сигнал v ₂, что соответствует состоянию B₂. Поэтому в клетку, указывающую переход из B₁ по входному сигналу Z₁ записывается B₂.

Аналогично заполняются все остальные клетки таблицы.

Рис. 3.3‑5

Полученный автомат Мили должен быть эквивалентен автомату Мили, заданному в таблице на рис. 3.3‑5 b) и автомату Мура, заданному в таблице на рис. 3.3‑5 a). Проверим это на одном входном слове при одном начальном состоянии. Возьмем в качестве начального состояния для автомата Мура, заданного в на в таблице на рис. 3.3‑5 a)

А_н = А₃,

а в качестве входного слова

- Z₂ Z₁ Z₁ Z₃ Z₂.

Основываясь на таблице, приведенной на рис. 3.3‑5 a), составим для выбранного входного слова последовательность состояний и формируемых выходных сигналов. Эта последовательность будет иметь вид:

A(t) - A₃, A₅ A₅ A₅ A₂

X(t) - Z₂ Z₁ Z₁ Z₃ Z₂.

A(t+1) - A₅ A₅ A₅ A₂ A₅

w(t+1) - v ₃ v ₃ v ₃ v ₂ v ₃

Таким образом, рассмотренный автомат на заданное входное слово выработал выходное слово «v ₃ v ₃ v ₃ v ₂ v ₃» и оказался в состоянии A₅. Найдем реакцию на то же входное слово автомата Милипредставленного в таблице на рис. 3.3‑5 b).

Основываясь на данной таблице, составим для заданного входного слова последовательность состояний и формируемых выходных сигналов. При этом в качестве исходного состояния возьмем C₂, так как оно отражает подмножество состояний { A₃, A₃}, в которое входит начальное состояние ранее рассмотренного цифрового автомата Мура.

Эта последовательность будет иметь вид:

C(t) - C₂, C₃ C₃ C₃ C₁

X(t) - Z₂ Z₁ Z₁ Z₃ Z₂.

C(t+1) - C₃ C₃ C₃ C₁ C₃

w(t+1) - v ₃ v ₃ v ₃ v ₂ v ₃.

Таким образом, рассмотренный автомат на заданное входное слово выработал выходное слово «v ₃ v ₃ v ₃ v ₂ v ₃» и оказался в состоянии C₁.

Найдем реакцию на тоже входное слово автомата Мили представленного в таблице на рис.

Основываясь на таблице, приведенной на рис. 3.3‑5 c), составим для заданного входного слова последовательность состояний и формируемых выходных сигналов. При этом в качестве исходного состояния используем В₁, которое отражает пару C ₂v ₂, где C ₂ используется в качестве исходного состояния ранее рассмотренного цифрового автомата Мили (с таким же успехом можно взять в качестве начального состояние B ₄).

Эта последовательность будет иметь вид:

B(t) - B₁, B₃ B₃ B₃ B₂

X(t) - Z₂ Z₁ Z₁ Z₃ Z₂.

C(t+1) - B₃ B₃ B₃ B₂ B₃

w(t+1) - v ₃ v ₃ v ₃ v ₂ v ₃

Таким образом, рассмотренный автомат на заданное входное слово выработал выходное слово «v ₃ v ₃ v ₃ v ₂ v ₃» и оказался в состоянии C₂. Следовательно, все три рассмотренных автомата при соответствующих начальных состояниях одинаково преобразовали входное слово

Z₂ Z₁ Z₁ Z₃ Z₂.

в выходное слово

v ₃ v ₃ v ₃ v ₂ v ₃,

Кроме того, заметим, что после преобразования заданного входного слова три автомата перешли в соответствующие состояния A₅,C₃,B_3.

С точки зрения синтеза цифровой автомат удобно представить в виде структурной схемы, приведенной на рис. 3.3‑6.

Рис. 3.3‑6

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

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

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

Учитывая всё выше изложенное, можно выполнить синтез цифрового автомата следующим образом.

1. Кодирование входных сигналов в виде набора логических переменных.

2. Кодирование выходных сигналов в виде набора логических функций.

3. Кодирование состояний цифрового автомата.

4. Формирование кодированной таблицы переходов.

5. Выбор типа запоминающего элемента.

6. Составление логических выражений для логических функций, использованных для кодировки выходных сигналов.

7. Составление логических выражений для сигналов управления памятью.

8. Синтез логических схем для сформированных логических выражений.

9. Формирование выходных сигналов цифрового автомата на основании кодирующих их функций.

Рассмотрим реализацию перечисленных действий на конкретном примере.

Пример

Синтезировать цифровой автомат, заданный в виде таблиц, приведенных на рис. 3.3‑6.

Память автомата построить на Т-триггере.

Тип автомата - автомат Мили.

При синтезе логических выражений использовать логический базис И, ИЛИ, НЕ.

Решение

Кодирование входных сигналов выполним через набор логических переменных «х». Множество входных сигналов включает три элемента. Поэтому для представления каждого из них достаточно использовать комбинации из двух переменных х₁, х₂. Кодировка входных переменных представлена таблицей на рис. 3.3‑7 а).

Кодирование выходных сигналов выполним через набор логических функций «у». Множество выходных сигналов включает четыре элемента. Поэтому для представления каждой из них достаточно использовать комбинации из двух переменных у₁, у₂. Кодировка входных переменных представлена таблицей на рис. 3.3‑7 b).

Рис. 3.3‑7

Кодирование состояний выполним через набор логических переменных «Q». Множество состояний включает четыре элемента. Поэтому для представления каждой из них достаточно использовать комбинации из двух переменных Q₁, Q₂. Кодировка входных переменных представлена таблицей на рис. 3.3‑8 b).

Рис. 3.3‑8

Таблицы переходов (рис. 3.3‑6а) и выходных сигналов (рис. 3.3‑6 b) после замены переменных исходного задания цифрового автомата на их кодированные значения будут иметь вид, представленный на рис. 3.3‑9.

Рис. 3.3‑9

В таблице переходов на рис. 3.3‑9а) клетки заполнены двух разрядным кодом, первый разряд которого отображает значение переменной Q₁, а вторая - переменную Q₂(«1» - переменная имеет прямое значение, «0» - переменная имеет обратное значение).

В таблице выходов на рис. 3.3‑9b) клетки заполнены двухразрядным кодом, первый разряд которого отображает значение переменной у₁ , а вторая - переменную у₂(«1» - переменная имеет прямое значение, «0» - переменная имеет обратное значение).

Логические выражения для разрядов кода выходных сигналов составляются на основе таблицы на рис. 3.3‑9 b). Эти выражения имеют следующий вид:

Приведенные выражения составляются по следующему правилу.

При формировании y₁ в кодированной таблице выходных сигналов на рис. 3.3‑8 b) выбираются все случаи, когда y₁ имеет единичное значение, и для каждого из них формируется конъюнкция, отражающая начальное состояние и входные сигналы, при которых функция y₁ имеет единичное значение. На пример, первая конъюнкция в выражении для y₁ имеет вид:

и соответствует случаю, когда начальное состояние имеет значения

а на вход поступает сигнал

В этой клетке переменная y₁ (первый разряд двухразрядного кода выходного сигнала) имеет единичное значение.

Пятая конъюнкция выражения для y₁

соответствует клетке, расположенной на пересечении колонки, обозначенной как

и строчки, обозначенной как

,

где функция y₁ согласно таблицы на рис. 3.3‑9 b) имеет единичное значение.

Выражение для y₂ формируется аналогично, но рассматриваются значения второго разряда двухразрядного коду, соответствующего выходному сигналу цифрового автомата.

Логические выражения для функций управления памятью составляются на основе таблицы на рис. 3.3‑9а) с учетом особенностей используемого элемента памяти. В рассматриваемом случае в качестве элемента памяти используется Т-триггер, основной особенностью которого является то, что по каждому входному сигналу триггер меняет свое состояние на противоположное. Поэтому сигнал на вход Т-триггера надо подавать только в тех случаях, когда новое его состояние отличается от текущего. Логические выражения для сигналов управления памятью в рассматриваемом случае имеют вид:

Приведенные выражения формируются следующим образом.

В выражении для функции сигнала Т-входа первого разряда q_T1 в общей дизъюнктивной форме используются конъюнкции, отражающие все случаи, когда значение первого разряда кода нового состояния противоположно его начальному состоянию. На пример, первая конъюнкция в выражении для q_T1 имеет вид

и соответствует случаю, когда начальное состояние имеет значения

и на вход поступает сигнал

а код нового состояния

Q₁ Q₂ (1 1)

имеет в первом разряде значение, отличное от значения первого разряда кода начального состояния.

Пятая конъюнкция выражения для q_T1

соответствует клетке, расположенной на пересечении колонки, обозначенной как

Q₁ Q₂

и строчки, обозначенной как

где первый разряд кода нового состояния автомат согласно таблицы на рис. 3.3‑9 а) имеет значение Q₁, противоположное значению, которое имеет место в первом разряде кода начального состояния цифрового автомата.

Выражение для q_T2 формируется аналогично, но рассматриваются изменения значения второго разряда двухразрядного кода состояния после учета воздействия входного сигнала.

Для более компактного представления полученных логических выражений и обозначений на формируемой схеме цифрового автомата введем десятичную кодировку конъюнкций, используемых в полученных логических выражениях. Каждая конъюнкция представляет набор одних и тех же переменных Q₁, Q₂, x₁, x₂ , поэтому эти конъюнкций можно рассматривать как четырехразрядный двоичный код и кодировать конъюнкции десятичными эквивалентами этого двоичного кода. Таким образом, ранее полученные выражения можно представить в следующей компактной форме:

y₁=5+9+14+2+3; y₂=5+6+11+13+14+3; q_T1=5+6+7+11+13+15+3; q_T2 = 7+9+11+13+14+2+3.

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

{5, 9,14,2,3, 6, 11, 13, 7,15}.

Логическая схема, реализующая сформированные логические выражения для выходных сигналов и сигналов управления памятью цифрового автомата, осуществляющая кодировку входных и декодировку выходных сигналов, имеет вид, приведенный на рис. 3.3‑10.

Память цифрового автомата реализована на двух Т-триггерах, формирующих парафазные выходные cигналы

используемые для кодировки состояний A₁, A₂, A₃, A₄ цифрового

автомата. Кодер формирует парафазные сигналы

кодировки входных сигналов z₁, z₂, z₃ цифрового автомата. Вертикальные линии обозначены логическими переменными, которые на них подаются. Cхем «И» помечены десятичными числами, соответствующими кодам конъюнкций, которые они формируют. Выходы логических схем «ИЛИ» помечены

Рис. 3.3‑10

обозначениями логических функций, формируемых этими логическими схемами «ИЛИ». Выходные сигналы цифрового автомата формируются с помощью декодера.

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