Введение в теорию автоматов

Графический метод синтеза структурного автомата на триггерах

Разбить на страницы
Показывать лекцию целиком

8.1 Этапы графического метода синтеза структурного автомата

Первые три этапа графического метода синтеза совпадают с табличным методом. Абстрактный автомат представлен в виде графа.

  • Находим количество элементов памяти $$R >=]Log_2M[$$, ( $$М$$ - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата.
  • Кодируем входные и выходные сигналы.
  • Структурный автомат представляем обобщенной схемой.
  • Составление уравнений выходных функций.

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

  • Составление уравнений функций возбуждения.

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

  • Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ} ).
    •

    8.2 Пример графического метода синтеза структурного автомата

    Пусть дан автомат Мили (рис.8.1). Выполним синтез структурного автомата на RS - триггерах.

    (рис 8.1)
  • количество триггеров равно $$2 (R>=]Log_23[)$$ ). Состояния абстрактного автомата закодируем так, как показано в табл.8.1.
    $$a_i \tau_1 \tau_2$$ $$\tau_1 \tau_2$$
    a100
    a201
    a311
  • Кодируем входные и выходные сигналы , например, так как показано в табл.8.2 и табл.8.3.
    zi\x 1 x 2 x 1 \x2
    z100
    z201
    z310
    wi\y 1y2 y1 \y2
    w110
    w200
    w311
    w401
  • Структурный автомат представляем обобщенной схемой (рис 8.2(рис 8.2)
  • Представляем закодированный граф абстрактного автомата (рис 8.3(рис 8.3) $$y_1=\bar\tau_1\bar\tau_2 \bar x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\ y_2=\bar\tau_1\bar\tau_2 \bar x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$
  • Составление уравнений функций возбуждения для (рис 8.4)

    Уравнения функций возбуждения будут иметь вид:

    $$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2 \\ \varphi_2=\tau_1 \tau_2 x_2 \vee \tau_1 \tau_2 x_2\\ \psi_1=\tau_1 \tau_2 \bar x_1 x_2 \\ \psi_2=\bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 \bar x_1 x_2$$
  • Последний этап минимизации уравнений, построение схемы выполняется как и в предыдущих случаях синтеза.
    •

    8.3 Пример графического метода синтеза структурного автомата Мура

    Пусть дан автомат Мура (рис.8.5). Выполним синтез структурного автомата на JK -триггерах.

    (рис 8.5)
  • количество триггеров равно $$2 (R >=]Log_24[)$$. Состояния абстрактного автомата закодируем так , как показано в таблица 8.4 $$\tau_1$$ $$\tau_2$$ a10 0 a20 1 a31 0 a41 1
  • Кодируем входные и выходные сигналы , например, так как показано в таблица 8.5 x1 x 2 z10 1 z21 0 z31 1
    r1 r2
    u10 0
    u20 1
    u31 0
  • Структурный автомат представляем обобщенной схемой (рис 8.6(рис 8.6)
  • Представляем закодированный граф абстрактного автомата (рис 8.7(рис 8.7) (рис 8.8) $$r_1= \tau_1 \tau_ 2 , \\ r_2= \tau_1 \tau_ 2$$.
  • Составление уравнений функций возбуждения для JK - триггера. На закодированном графе на дугах перехода указываем функции возбуждения: $$\varphi_1$$ если 1-ый триггер переключился из 0 в 1; $$\varphi_2$$ если 2-ой. триггер переключился из 0 в 1; $$\psi_1$$ если 1-ый триггер переключился из 1 в 0; $$\psi_2$$ если 2-ой триггер переключился из 1 в 0; (рис.8.4).

    Уравнения функций возбуждения будут иметь вид:

    $$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \\ \varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\ \psi_1=\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\ \psi_2=\bar\tau_1 \tau_2 x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2$$
  • Последний этап минимизации уравнений, построение схемы выполняется как и в предыдущих случаях синтеза.
    •
    Страницы:

    8.1 Этапы графического метода синтеза структурного автомата

    Первые три этапа графического метода синтеза совпадают с табличным методом. Абстрактный автомат представлен в виде графа.

  • Находим количество элементов памяти $$R >=]Log_2M[$$, ( $$М$$ - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата.
  • Кодируем входные и выходные сигналы.
  • Структурный автомат представляем обобщенной схемой.
  • Составление уравнений выходных функций.

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

  • Составление уравнений функций возбуждения.

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

  • Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ} ).
    •

    8.2 Пример графического метода синтеза структурного автомата

    Пусть дан автомат Мили (рис.8.1). Выполним синтез структурного автомата на RS - триггерах.

    (рис 8.1)
  • количество триггеров равно $$2 (R>=]Log_23[)$$ ). Состояния абстрактного автомата закодируем так, как показано в табл.8.1.
    $$a_i \tau_1 \tau_2$$ $$\tau_1 \tau_2$$
    a100
    a201
    a311
  • Кодируем входные и выходные сигналы , например, так как показано в табл.8.2 и табл.8.3.
    zi\x 1 x 2 x 1 \x2
    z100
    z201
    z310
    wi\y 1y2 y1 \y2
    w110
    w200
    w311
    w401
  • Структурный автомат представляем обобщенной схемой (рис 8.2(рис 8.2)
  • Представляем закодированный граф абстрактного автомата (рис 8.3(рис 8.3) $$y_1=\bar\tau_1\bar\tau_2 \bar x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\ y_2=\bar\tau_1\bar\tau_2 \bar x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$
  • Составление уравнений функций возбуждения для (рис 8.4)

    Уравнения функций возбуждения будут иметь вид:

    $$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2 \\ \varphi_2=\tau_1 \tau_2 x_2 \vee \tau_1 \tau_2 x_2\\ \psi_1=\tau_1 \tau_2 \bar x_1 x_2 \\ \psi_2=\bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 \bar x_1 x_2$$
  • Последний этап минимизации уравнений, построение схемы выполняется как и в предыдущих случаях синтеза.
    •

    8.3 Пример графического метода синтеза структурного автомата Мура

    Пусть дан автомат Мура (рис.8.5). Выполним синтез структурного автомата на JK -триггерах.

    (рис 8.5)
  • количество триггеров равно $$2 (R >=]Log_24[)$$. Состояния абстрактного автомата закодируем так , как показано в таблица 8.4 $$\tau_1$$ $$\tau_2$$ a10 0 a20 1 a31 0 a41 1
  • Кодируем входные и выходные сигналы , например, так как показано в таблица 8.5 x1 x 2 z10 1 z21 0 z31 1
    r1 r2
    u10 0
    u20 1
    u31 0
  • Структурный автомат представляем обобщенной схемой (рис 8.6(рис 8.6)
  • Представляем закодированный граф абстрактного автомата (рис 8.7(рис 8.7) (рис 8.8) $$r_1= \tau_1 \tau_ 2 , \\ r_2= \tau_1 \tau_ 2$$.
  • Составление уравнений функций возбуждения для JK - триггера. На закодированном графе на дугах перехода указываем функции возбуждения: $$\varphi_1$$ если 1-ый триггер переключился из 0 в 1; $$\varphi_2$$ если 2-ой. триггер переключился из 0 в 1; $$\psi_1$$ если 1-ый триггер переключился из 1 в 0; $$\psi_2$$ если 2-ой триггер переключился из 1 в 0; (рис.8.4).

    Уравнения функций возбуждения будут иметь вид:

    $$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \\ \varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\ \psi_1=\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\ \psi_2=\bar\tau_1 \tau_2 x_1 \bar x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2$$
  • Последний этап минимизации уравнений, построение схемы выполняется как и в предыдущих случаях синтеза.
    •
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^