Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Проектирование автомата типа Мили

СОДЕРЖАНИЕ

1.Задание…………………………………………………..……………………...22.Введение………………………………………………………………………..3

3.Абстрактный синтез автомата…………………………..……………….……5

4.Структурный синтез автомата ……………………..…………………..……..7

5. Функциональная схема автомата…………………………………………….9

6.Элементы физического синтеза……………………………………………...10

7.Описание автомата на языке VHDL…………………………………………11

8.Моделирование на ПК с использованием симулятора ModelSim…………17

9.Заключение……………………………………………………………………18

10.Список литературы………………………………………………………….18

1. ЗАДАНИЕ

Спроектировать управляющий цифровой автомат типа Мили, функционирующий согласно заданной ГСА. ГСА строится соединением фрагментов (рис. 1) в заданной последовательности (2, 1, 3, 4). Каждая операторная вершина определяет некоторый выходной сигнал. Количество условных вершин в ГСА определяет входной алфавит автомата. Тип используемых триггеров RS.

2. ВВЕДЕНИЕ

Курсовая работа заключается в решении комплексной задачи синтеза дискретного устройства с памятью по заданным условиям работы на заданной элементной базе. Решение должно быть доведено до функциональной схемы устройства (автомата).

Термин автомат, как правило, используется в двух аспектах. С одной стороны, автомат — устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ — автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом аспекте автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q={q₁(t), q₂(t),..., q_n(t)}, в которые он под воздействием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.

Цифровой автомат - устройство, предназначенное для преобразования цифровой информации. Входные сигналы в цифровых автоматах представляются в виде конечного множества мгновенных сигналов. Теоретически это означает, что входные сигналы не имеют длительности, хотя практически это не так. Такое допущение упрощает рассмотрение процессов, происходящих в автоматах, так как все события (состояния) должны относиться к фиксированному моменту времени t. Условно также принимается, что число выходных сигналов y(t) конечно и они возникают в результате действия входных сигналов. При этом следует учитывать, что одновременно с появлением выходного сигнала происходит скачкообразный

переход автомата из состояния q_i(t) в состояние q_j(t).

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

Время для цифрового автомата имеет также важное значение. Для решения задач анализа и синтеза цифровых автоматов обычно вводится автоматное время. Функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности (интервал дискретности).

Общая теория автоматов разбивается на две большие части — абстрактную теорию автоматов и структурную теорию автоматов. Различие между ними заключается в том, что в абстрактной теории мы отвлекаемся от структуры как самого автомата, так и его входных и выходных сигналов. Не интересуясь способом построения автомата, абстрактная теория изучает лишь те переходы, которые претерпевает автомат под воздействием входных сигналов, и те выходные сигналы, которые он при этом выдает. Абстрактная теория автоматов близка теории алгоритмов, является ее дальнейшей детализацией.

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

3. АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТА

Одной из разновидностей языка, позволяющей описывать логические схемы алгоритмов, является язык граф-схем алгоритмов (ГСА).

Граф-схема алгоритма — ориентированный связный граф, содержащий одну начальную вершину, произвольное число условных и операторных вершин и одну конечную вершину.

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторная вершины имеют по одному выходу, конечная вершина выходов не имеет, условная вершина имеет два выхода, помеченных символами 1 и 0. Граф-схема алгоритма удовлетворяет следующим условиям:

1) входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода к входу;

2) каждый выход соединен только с одним входом;

3) любой вход соединяется, по крайней мере, с одним выходом;

4) любая вершина графа лежит, по крайней мере, на одном пути из начальной к конечной вершине;

5) в каждой условной вершине записывается один из элементов множества логических условий Z = {Z₁,Z₂, ,...,Z_k}, разрешается в различных условных вершинах запись одинаковых элементов множества A;

6) в каждой операторной вершине записывается один из элементов множества операторов V={v₁,v₂,..., v_N}., разрешается в различных операторных вершинах запись одинаковых элементов множества V.

Язык ГСА используется очень часто при описании алгоритмов функционирования как самого цифрового автомата, так и программ, выполняющих то или иное действие.

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

операционного блока имеет вид, представленный на рис.2. Микропрограмма выполняется при начальном условии Н = 1. Блок производит выработку управляющих функциональных сигналов в определённой последовательности, зависящей от значений сигналов A₀-A_3.

Граф - схема алгоритма (ГСА) Граф автомата Милли

4. СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА

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

Для построения автомата используем синхронные RS-триггеры, имеющие следующую таблицу переходов:

t		t+1	Примечания
R	S	Q	Примечания
0	0	Q(t)	Хранение
0	1	1	Установка 1
1	0	0	Установка 0
1	1	---	Запрещенное состояние

Определим количество элементов памяти (триггеров) структурного автомата:

2^R – количество различных внутренних состояний структурного автомата

М – мощность алфавита внутренних состояний абстрактного автомата

2^R ≥ М

2^R ≥ 8 => R = 3

А	Q1	Q2	Q3
a0	0	0	0
a1	0	0	1
a2	0	1	0
a3	0	1	1
a4	1	0	0
a5	1	0	1
a6	1	1	0
a7	1	1	1

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

Кодированная таблица переходов и выходов

H	z₁	z₂	z₃	z₄	исх. сост.	Q₁	Q₂	Q₃	след. сост.	Q₁	Q₂	Q₃	вых. сигн.	R₃	S₃	R₂	S₂	R₁	S₁
0	-	-	-	-	a0	0	0	0	a0	0	0	0	-	-	0	-	0	-	0
1	-	-	-	-	a0	0	0	0	a1	0	0	1	V1	-	0	-	0	0	1
-	0	-	-	-	a1	0	0	1	a2	0	1	0	-	-	0	0	1	1	0
-	1	-	-	-	a1	0	0	1	a2	0	1	0	V2	-	0	0	1	1	0
-	-	-	-	-	a2	0	1	0	a3	0	1	1	V3	-	0	0	-	0	1
-	-	0	-	-	a3	0	1	1	a3	0	1	1	V3	-	0	0	-	0	-
-	-	1	-	-	a3	0	1	1	a4	1	0	0	V4	0	1	1	0	1	0
-	-	-	-	-	a4	1	0	0	a5	1	0	1	V5	0	-	-	0	0	1
-	-	-	0	-	a5	1	0	1	a6	1	1	0	V6	0	-	0	1	1	0
-	-	-	1	-	a5	1	0	1	a6	1	1	0	V7	-	0	0	1	1	0
-	-	-	-	-	a6	1	1	0	a7	1	1	1	V8	-	0	-	0	0	1
-	-	-	-	0	a7	1	1	1	a7	1	1	1	V9	0	-	0	-	0	-
-	-	-	-	1	a7	1	1	1	a0	0	0	0	V10	1	0	1	0	1	0

Булевы функции описания выходов схемы и входов триггеров:

V₁=a₀H

V₂=a₁z₁

V₃=a₂+ a₃

V₄= a₃z₂

V₅= a₄

V₆=a₅

V₇=a₅z₃

V₈=a₆

V₉= a₇

V₁₀=a₇z₄

R₃= a₇z₄

S₃=a₃z₂

R₂= a₇z₄+a₃z₂

S₂= a₁+a₅

R₁=a₃z₂+a₅+a₇z₄+a₁

S₁=a₀H+a₂+a₄+a₆

5. ФУНКЦИОНАЛЬНАЯ СХЕМА АВТОМАТА

6. ЭЛЕМЕНТЫ ФИЗИЧЕСКОГО СИНТЕЗА

Модель	Функция
К155ИД12	Дешифратор на 3 входа и 8 выходов
К555ТМ10	RS-триггер
К155ЛЛ1	4 лог.эл-та 2ИЛИ х2
К155ИЛ1	4 лог.эл-та 2И х3
К155ЛН1	3 лог.эл-та НЕ

7. ОПИСАНИЕ АВТОМАТА НА ЯЗЫКЕ VHDL

library IEEE;

use IEEE.STD_LOGIC_1164.all;

-------------------------------------------------------------------

entity RS is

port ( R, S, CLK : in bit;

Q : out bit);

end RS;

-------------------------------------------------------------------

architecture functional of RS is

constant Delay : Time := 10 ns;

begin

process(CLK)

begin

if (CLK'event) and (CLK = '0') then

if (S = '1') and (R = '0') then Q <= '1' after Delay; end if;

if (S = '0') and (R = '1') then Q <= '0' after Delay; end if;

end if;

end process;

end functional;

-------------------------------------------------------------------

entity DC is

port (x0, x1, x2 : in Bit;

va : buffer bit_vector(0 to 7));

end DC;

-------------------------------------------------------------------

architecture functional of DC is

constant Delay : Time := 1 ns;

begin

process(x0, x1, x2)

begin

if (X0 = '0') and (X1 = '0') and (X2 = '0') then

va <= "10000000" after Delay; end if;

if (X0 = '1') and (X1 = '0') and (X2 = '0') then

va <= "01000000" after Delay; end if;

if (X0 = '0') and (X1 = '1') and (X2 = '0') then

va <= "00100000" after Delay; end if;

if (X0 = '1') and (X1 = '1') and (X2 = '0') then

va <= "00010000" after Delay; end if;

if (X0 = '0') and (X1 = '0') and (X2 = '1') then

va <= "00001000" after Delay; end if;

if (X0 = '1') and (X1 = '0') and (X2 = '1') then

va <= "00000100" after Delay; end if;

if (X0 = '0') and (X1 = '1') and (X2 = '1') then

va <= "00000010" after Delay; end if;

if (X0 = '1') and (X1 = '1') and (X2 = '1') then

va <= "00000001" after Delay; end if;

end process;

end functional;

-------------------------------------------------------------------

entity and2 is

port (x1, x2 : in Bit;

y : out Bit);

end and2;

-------------------------------------------------------------------

architecture functional of and2 is

constant Delay1 : Time := 2 ns;

constant Delay2 : Time := 1 ns;

begin

process(x1, x2)

begin

if (x1 = '0') or (x2 = '0') then y <= '0' after Delay2;

else y <= '1' after Delay1;

end if;

end process;

end functional;

-------------------------------------------------------------------

entity or2 is

port (x1, x2 : in Bit;

y : out Bit);

end or2;

-------------------------------------------------------------------

architecture functional of or2 is

constant Delay1 : Time := 2 ns;

constant Delay2 : Time := 1 ns;

begin

process(x1, x2)

begin

if (x1 = '1') or (x2 = '1') then y <= '1' after Delay1;

else y<='0' after Delay2;

end if;

end process;

end functional;

-------------------------------------------------------------------

entity not1 is

port (x : in Bit;

y : out Bit);

end not1;

-------------------------------------------------------------------

architecture functional of not1 is

constant Delay : Time := 1 ns;

begin

y <= not x after Delay;

end functional;

-------------------------------------------------------------------

entity Circuit is

port (CLK, h, z1, z2, z3, z4 : in Bit;

v1, v2, v3, v4, v5, v6, v7, v8, v9, v10 : out Bit);

end Circuit;

-------------------------------------------------------------------

architecture structure of Circuit is

component DC is

port (x0, x1, x2 : in Bit;

va : buffer bit_vector(0 to 7));

end component;

component RS is

port (R, S, CLK : in Bit;

Q : out Bit);

end component;

component and2 is

port (x1, x2 : in Bit;

y : out Bit);

end component;

component not1 is

port (x : in Bit;

y : out Bit);

end component;

component or2 is

port (x1, x2 : in Bit;

y : out Bit);

end component;

signal va : bit_vector(0 to 7);

signal Q1, Q2, Q3 : Bit;

signal R1, S1, R2, S2, R3, S3 : Bit;

signal nz2, nz3, nz4 : Bit;

signal a0H, a1z1, a3z2, a3nz2, a5nz3, a5z3, a7nz4, a7z4: Bit;

signal pr2, ps2, a0a2H, a4a6, a2a3nz2: Bit;

begin

DD1 : RS port map (R1, S1, CLK, Q1);

DD2 : RS port map (R2, S2, CLK, Q2);

DD3 : RS port map (R3, S3, CLK, Q3);

DD4: DC port map (Q1, Q2, Q3, va);

DD5 : not1 port map (z2, nz2);

DD6 : not1 port map (z3, nz3);

DD7 : not1 port map (z4, nz4);

DD8_1: and2 port map (nz4,va(7),a7nz4);

DD8_2: and2 port map (z1,va(1), a1z1);

DD8_3: and2 port map (va(0), H, a0H);

DD8_4: and2 port map (va(3), nz2, a3nz2);

DD9_1: and2 port map (va(3), z2, a3z2);

DD9_2: and2 port map (va(5), nz3, a5nz3);

DD9_3: and2 port map (va(5), z3, a5z3);

DD9_4: and2 port map (va(7), z4, a7z4);

R3 <= a7z4;

S3 <= a3z2;

DD10_1: or2 port map (a7z4, a3z2, pr2);

DD10_2: or2 port map (va(1), va(5), ps2);

R2 <= pr2;

S2 <= ps2;

DD10_3: or2 port map (pr2, ps2, R1);

DD10_4: or2 port map (a0H, va(2), a0a2H);

DD11_1: or2 port map (va(4), va(6), a4a6);

DD11_2: or2 port map (a0a2H, a4a6, S1);

DD11_3: or2 port map (va(2), a3nz2, a2a3nz2);

v1 <= a0H;

v2 <= a1z1;

v3 <= a2a3nz2;

v4 <= a3z2;

v5 <= va(4);

v6 <= a5nz3;

v7 <= a5z3;

v8 <= va(6);

v9 <= a7nz4;

v10 <= a7z4;

end structure;

-------------------------------------------------------------------

entity Test_Bench is

end Test_Bench;

-------------------------------------------------------------------

architecture Schema of Test_Bench is

component Circuit is

port (CLK, h, z1, z2, z3, z4 : in Bit;

v1, v2, v3, v4, v5, v6, v7, v8, v9, v10 : out Bit);

end component;

signal CLK, h, z1, z2, z3, z4 : Bit;

signal v1, v2, v3, v4, v5, v6, v7, v8, v9, v10 : Bit;

begin

process

begin

h <= '1' after 150 ns;

z1 <= '1' after 800 ns;

z2 <= '1' after 1600 ns;

z3 <= '1' after 2400 ns;

z4 <= '1' after 3200 ns;

for i in 0 to 10000 loop

CLK <= '0';

wait for 50 ns;

CLK <= '1';

wait for 50 ns;

end loop;

end process;

Avtomat : Circuit port map(CLK, h, z1, z2, z3, z4, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10);

end Schema;

-------------------------------------------------------------------

8. МОДЕЛИРОВАНИЕ НА ПК С ИСПОЛЬЗОВАНИЕМ СИМУЛЯТОРА MODELSIM

9. ЗАКЛЮЧЕНИЕ