«…лишь недалекие люди боятся конкуренции, а люди подлинного творчества ценят общение с каждым талантом…» А. Бек, Талант.

ПЦУСБ/Лабораторная работа 3

Материал из Wiki
Перейти к: навигация, поиск
Лекции ПЦУСБ
Лекции
Практические
Тесты
Лабораторные
Доп. материалы

Содержание

Задание

Название работы: Описание и моделирование конечных автоматов

  1. По заданному табличному описанию автомата:
    • Построить граф переходов (для этого удобно использовать Graphviz и on-line сервис)
    • Определить бинарные значения (коды) для входных состояний, внутренних состояний и выходных состояний. Использовать для этого тип кода, заданный по «собственному произволу».
    • Описать два варианта VHDL-модели автомата:
      • реализовать внутренние состояния через пользовательский перечислимый тип
      • реализовать внутренние состояния через выбранный бинарный код
    при этом использовать для описания таблицы переходов в модели разные операторы (if, case, when..else).
  2. Реализовать тесбенч, проверяющий эквивалентность работы двух моделей. При этом тестбенч должен проверять все возможные состояния и переходы автомата. Проконтролировать это позволяют средства ModelSim.
    • Перед компиляцией исходной модели автомата задать в свойствах компилятора (Compile Options...) на вкладке Coverage все пункты в группе Source code coveage и пункт Enable Finite State Mashine Coverage в группе Other coverage.
    • При запуске моделирования (Start Simulation...) задать сбор покрытия (Coverage).
  3. Подготовить отчет, включающий:
    1. Титульный лист
    2. Задание
    3. Графическую форму задания автомата (в виде графа)
    4. Таблицы с выбранными кодами для входных состояний, внутренних состояний и выходных состояний
    5. Исходные тексты двух VHDL моделей и тестбенча
    6. Отчет о покрытии кода и автомата (граф и текстовый отчет о покрытии состояний и переходов, полученный в ModelSim)
      • Выбрать в меню Tools → Coverage Report → Text Report...
    7. Временные диаграммы, включающие входные воздействия, внутренние состояния обоих автоматов, выходы двух автоматов и сигнал Ok (результат сравнения выходов двух моделей).

Варианты заданий

Информация

Вариант заданий соответствует номеру по списку.

Вариант 1

Конечный автомат Мили.

Алфавит внутренних состояний A = {a1, a2, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z3}. Выходной алфавит W = {w1, w2 ,w3 ,w4, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a1 a2 a3 a4
z1 a2/w1 a2/w1 a1/w2 a1/w4
z2 a4/w5 a3/w3 a4/w4 a3/w5
z3 a3/w2 a3/w3 a1/w4 a3/w5

Вариант 2

Конечный автомат Мура.

Алфавит состояний A = {a11, a2, a3}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z22, z3}. Выходной алфавит W = {w11, w22 ,w33}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
a11 a2 a3
z1 a3 a2 a11
z22 a11 a2 a3
z3 a3 a11 a3

w33 w11 w22 Выходные сигналы


Вариант 3

Конечный автомат Мили.

Алфавит внутренних состояний A = {a1, a2, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z3}. Выходной алфавит W = {w1, w2 ,w3 ,w4, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a1 a2 a3 a4
z1 a3/w4 a2/w1 a1/w2 a1/w4
z2 a4/w5 a2/w3 a2/w3 a3/w3
z3 a3/w5 a3/w4 a1/w4 a3/w1

Вариант 4

Конечный автомат Мура.

Алфавит состояний B = {b1, b22, b3}. Начальное состояние автомата b1. Входной алфавит Q = {q1, q22, q3}. Выходной алфавит Y = {y1, y2 ,y3}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
b1 b22 b3
q1 b22 b1 b1
q22 b3 b22 b22
q3 b1 b3 b3

y2 y3 y1 Выходные сигналы


Вариант 5

Конечный автомат Мили.

Алфавит внутренних состояний A = {a1, a2, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z3}. Выходной алфавит W = {w1, w2 ,w3 ,w4, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a1 a2 a3 a4
z1 a1/w4 a3/w1 a1/w3 a1/w4
z2 a2/w5 a1/w3 a4/w3 a3/w3
z3 a3/w5 a4/w5 a1/w4 a4/w1


Вариант 6

Конечный автомат Мура.

Алфавит состояний C = {c1, c2, c33}. Начальное состояние автомата c1. Входной алфавит Q = {q1, q2, q3}. Выходной алфавит Y = {y11, y2 ,y3}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
c1 c2 c33
q1 c2 c2 c1
q2 c2 c1 c2
q3 c33 c33 c33

y11 y3 y2 Выходные сигналы


Вариант 7

Конечный автомат Мили.

Алфавит внутренних состояний A = {a11, a2, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z3}. Выходной алфавит W = {w1, w2 ,w3 ,w44, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a11 a2 a3 a4
z1 a3/w5 a2/w1 a2/w2 a11/w5
z2 a4/w44 a2/w5 a4/w3 a3/w3
z3 a3/w5 a11/w44 a11/w44 a11/w5


Вариант 8

Конечный автомат Мура.

Алфавит состояний R = {r1, r2, r3}. Начальное состояние автомата r1. Входной алфавит Q = {q1, q2, q3}. Выходной алфавит W = {w1, w2 ,w3}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
r1 r2 r3
q1 r1 r3 r1
q2 r3 r2 r3
q3 r2 r2 r2

w3 w1 w2 Выходные сигналы


Вариант 9

Конечный автомат Мили.

Алфавит состояний A = {a1, a22, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1 , z2 , z3}. Выходной алфавит W = {w1, w2 ,w33 ,w4, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a1 a22 a3 a4
z1 a3/w4 a22/w1 a1/w2 a1/w4
z2 a4/w4 a22/w33 a4/w33 a22/w33
z3 a3/w5 a1/w4 a1/w4 a3/w1


Вариант 10

Конечный автомат Мура.

Алфавит состояний T = {t1, t22, t3}. Начальное состояние автомата t1. Входной алфавит Q = {q11, q2, q3}. Выходной алфавит Y = {y1, y2 ,y3}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
t1 t22 t3
q11 t3 t22 t1
q2 t22 t1 t22
q3 t1 t22 t3

y3 y2 y1 Выходные сигналы


Вариант 11

Конечный автомат Мили.

Алфавит состояний A = {a1, a22, a3, a4}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z33}. Выходной алфавит W = {w1, w22 ,w3 ,w45, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a1 a22 a3 a4
z1 a3/w22 a22/w1 a1/w1 a1/w45
z2 a4/w5 a4/w3 a4/w22 a3/w3
z33 a3/w22 a3/w45 a22/w45 a3/w1


Вариант 12

Конечный автомат Мура.

Алфавит состояний C = {c1, c2, c33}. Начальное состояние автомата c1. Входной алфавит Q = {q1, q2, q3}. Выходной алфавит Y = {y11, y2 ,y3}.

Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
c1 c2 c33
q1 c2 c2 c1
q2 c2 c1 c2
q3 c33 c33 c33

y11 y3 y2 Выходные сигналы


Вариант 13

Конечный автомат Мили.

Алфавит состояний A = {a11, a2, a3, a44}. Начальное состояние автомата a1. Входной алфавит Z = {z1, z2, z3}. Выходной алфавит W = {w1, w2 ,w3 ,w44, w5}.

Таблица функционирования конечного автомата Мили
Входные сигналы Состояния
a11 a2 a3 a44
z1 a3/w44 a2/w1 a11/w2 a11/w44
z2 a44/w5 a2/w5 a44/w3 a3/w2
z3 a3/w2 a44/w3 a11/w44 a3/w1


Вариант 14

Конечный автомат Мура.

Алфавит состояний S = {s11, s22, s3}. Начальное состояние автомата s1. Входной алфавит Z = {q1, q2, q33}. Выходной алфавит Y = {y1, y2 ,y3}.


Таблица функционирования конечного автомата Мура
Входные сигналы Состояния
s11 s22 s3
q1 s11 s11 s22
q2 s3 s11 s22
q33 s22 s22 s3

y2 y3 y1 Выходные сигналы


Вариант 15

Конечный автомат Мили.

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a4
z1 a2/w1 a2/w1 a1/w2 a1/w4
z2 a4/w5 a3/w3 a4/w4 a3/w5
z3 a3/w2 a3/w3 a1/w4 a3/w5


Вариант 16

Конечный автомат Мили.

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a4
z1 a3/w4 a2/w1 a1/w2 a1/w4
z2 a4/w5 a2/w3 a4/w3 a3/w3
z3 a3/w5 a3/w4 a1/w4 a3/w1


Вариант 17

Конечный автомат Мили.

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a4
z1 a4/w4 a2/w1 a1/w2 a4/w4
z2 a4/w5 a1/w3 a3/w4 a3/w3
z3 a1/w2 a2/w4 a1/w4 a4/w1


Вариант 18

Конечный автомат Мили.

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .


Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a4
z1 a1/w4 a3/w1 a1/w3 a1/w4
z2 a2/w5 a1/w3 a4/w3 a3/w3
z3 a3/w5 a4/w5 a1/w4 a4/w1


Вариант 19

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a11, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы: W = {w1, w2 ,w3 ,w44, w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a11 a2 a3 a4
z1 a3/w5 a2/w1 a2/w2 a11/w5
z2 a4/w5 a2/w5 a4/w3 a3/w3
z3 a3/w5 a1/w44 a1/w44 a11/w5


Вариант 20

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a22, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w33 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a22 a3 a4
z1 a3/w4 a22/w1 a1/w2 a1/w4
z2 a4/w4 a22/w33 a4/w33 a22/w33
z3 a3/w5 a1/w4 a1/w4 a3/w1


Вариант 21

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z33, т.е. Z = {z1 , z2 , z33}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w22 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a4
z1 a3/w22 a2/w1 a1/w22 a1/w4
z2 a4/w5 a2/w3 a4/w22 a3/w3
z33 a3/w22 a3/w4 a1/w4 a3/w1


Вариант 22

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a2, a3, a44}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a2 a3 a44
z1 a3/w4 a2/w1 a2/w2 a1/w4
z2 a44/w1 a2/w3 a44/w3 a3/w3
z3 a3/w5 a44/w1 a1/w4 a44/w1


Вариант 23

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a1, a22, a3, a4}. Начальное состояние автомата - a1. Входной алфавит Z образуют сигналы z1, z22, z3, т.е. Z = {z1 , z22 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a1 a22 a3 a4
z1 a22/w4 a22/w1 a1/w2 a1/w3
z22 a4/w5 a22/w3 a4/w3 a3/w3
z3 a3/w5 a4/w4 a1/w4 a22/w1


Вариант 24

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a11, a2, a33, a4}. Начальное состояние автомата - a11. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a11 a2 a33 a4
z1 a33/w4 a2/w1 a11/w2 a33/w4
z2 a4/w5 a33/w3 a4/w4 a33/w3
z3 a11/w5 a33/w2 a11/w4 a11/w1


Вариант 25

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a12, a20, a3, a4}. Начальное состояние автомата - a12. Входной алфавит Z образуют сигналы z11, z22, z33, т.е. Z = {z11 , z22 , z33}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a12 a20 a3 a4
z11 a3/w3 a20/w1 a12/w2 a12/w1
z22 a4/w5 a20/w3 a4/w1 a3/w3
z33 a12/w3 a20/w4 a12/w4 a20/w2


Вариант 26

Составить VHDL-описание конечного автомата Мили, заданного совмещенной таблицей переходов.

Алфавит состояний A = {a13, a23, a3, a4}. Начальное состояние автомата - a13. Входной алфавит Z образуют сигналы z1, z2, z3, т.е. Z = {z1 , z2 , z3}. Выходной алфавит W образуют сигналы w1, ..., w5, т.е. W = {w1, w2 ,w3 ,w4,w5}. На пересечении строки zn и столбца aq в таблице находится состояние as , в которое должен перейти автомат из состояния aq под воздействием сигнала zn. После косой черты в этой же графе таблицы указывается выходной сигнал, выдаваемый автоматом в состоянии aq при поступлении на его вход сигнала zn .

Таблица задания функционирования конечного автомата
Входные сигналы Состояния
a13 a23 a3 a4
z1 a3/w4 a2/w13 a1/w23 a23/w5
z2 a4/w1 a23/w1 a4/w3 a13/w3
z3 a3/w5 a3/w1 a1/w4 a3/w3

Получение отчета о покрытии

Для сбора покрытия при моделировании в ModelSim и получении отчета о покрытии (для вставки в отчет по лаб. работе) необходимо:

  1. Перед компиляцией исходных VHDL-моделей задать свойства компиляции: на вкладке Coverage указать необходимые виды покрытия кода.
  2. Запускать моделирование с опцией покрытия ("Simulation with Coverage").
  3. После проведения моделирования выбрать Tools → Coverage Report → Text... для получения текстового отчета о покрытии.
  4. Для получения графа покрытых состояний и переходов необходимо:
    • либо левой кнопкой кликнуть на изображении значка конечного автомата рядом с именем сигнала на временной диаграмме,
    • либо выбрать список автоматически определённых конечных автоматов в меню View → FSM list, и в списке выбрать нужный автомат.


Пример описания графа в Graphviz 

digraph g {

 a1 -> a2 [label="X1"]
 a2 -> a3 [label="X2"]
 a3 -> a1 [label="X3"]

 a1 [label="a1",shape=box,fillcolor="palegreen",style="filled,rounded"];
}

Результат:

[svg]

Источник — «http://simhard.com/wiki/index.php?title=ПЦУСБ/Лабораторная_работа_3&oldid=4050»