Проектирование управляющего автомата

Содержание

1. Задание

2. Введение

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

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

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

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

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

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

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

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

1. Задание

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

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) в каждой условной вершине записывается один из элементов множества логических условий A = { A₁,A₂, ,..., A_k}, разрешается в различных условных вершинах запись одинаковых элементов множества A;

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

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

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

Микропрограмма операционного блока

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

Рисунок 2

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

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

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

Условия перехода от микрокоманды к микрокоманде представляются в виде конъюнкции входных сигналов, влияющих на переход. Каждая конъюнкция выписывается так, чтобы набор значений входных переменных, обращающих конъюнкцию в 1, соответствовал условию перехода. При безусловном переходе конъюнкция заменяется на константу 1.

q(t) = ?( q(t-1), х(t))

y(t)=?(q(t-1),x(t)), t = 1,2

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

Таблица 2.

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 ? 4 => R = 4

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

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

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

R0=a1!z0+a3+a5+a7z2+a9z3;

S0=a0H+a4z1+a6!z2+a8;

R1=a2+a3+a6z2+a7z2

S1=a1+a4!z1+a5+a9z3;

R2=a6z2+a7z2;

S2=a2+a3;

R3=a10;

S3=a6z2+a7z2;

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

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

Модель	Функция
К155ИД3	4-х разрядный дешифратор
К555ЛИ1	4*2И
К555ЛЛ1	4*2ИЛИ
К155ЛН1	6*НЕ
CD4078BE+1 элемент НЕ	8ИЛИ
К555ТМ10	RS-триггерр

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, x3 : in Bit;

va : buffer bit_vector(0 to 15));

end DC;

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

architecture functional of DC is

constant Delay : Time := 1 ns;

begin

process(x0, x1, x2, x3)

begin

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

va <= "0000000000000001" 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 or8 is

port (x1, x2, x3, x4, x5, x6, x7, x8 : in Bit;

y : out Bit);

end or8;

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

architecture functional of or8 is

constant Delay1 : Time := 2 ns;

constant Delay2 : Time := 1 ns;

begin

process(x1, x2, x3, x4, x5, x6, x7, x8)

begin

if (x1 = '1') or (x2 = '1') or (x3 = '1') or (x4 = '1') or (x5 = '1') or (x6 = '1') or (x7 = '1') or (x8 = '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, z0, z1, z2, z3 : 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, x3 : in Bit;

va : buffer bit_vector(0 to 15));

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;

component or8 is

port (x1, x2, x3, x4, x5, x6, x7, x8 : in Bit;

y : out Bit);

end component;

signal va : bit_vector(0 to 15);

signal Q0, Q1, Q2, Q3 : Bit;

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

signal nz0, nz1, nz2 : Bit;

signal nz0a1,a7z2,a9z3,a0H,a4z1,a6nz2,a6z2,a4nz1,a7z2a9z3: Bit;

begin

DD8_1 : RS port map (R0 , S0 , CLK, Q0);

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

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

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

DD11_1 : not1 port map (z0, nz0);

DD11_2 : not1 port map (z1, nz1);

DD11_3 : not1 port map (z2, nz2);

DD5_1 : and2 port map (nz0, va(1), nz0a1);

DD5_2 : and2 port map (va(7), z2, a7z2);

DD5_3 : and2 port map (va(9), z3, a9z3);

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

DD6_1 : and2 port map (va(4), z1, a4z1);

DD6_2 : and2 port map (va(6), nz2, a6nz2);

DD6_3 : and2 port map (va(4), nz1, a4nz1);

DD6_4 : and2 port map (va(6), z2, a6z2);

DD7_1 : or2 port map (a7z2, a9z3, a7z2a9z3);

DD7_2 : or2 port map (va(2), va(3), S2);

DD7_3 : or2 port map (a6z2, a7z2, R2);

DD1 : or8 port map (nz0a1, va(3), va(5), a7z2, a9z3, '0', '0', '0', R0);

DD2 : or8 port map (a0H,a4z1,a6nz2,va(8),'0', '0', '0', '0', S0);

DD3 : or8 port map (va(2), va(3), a6z2, a7z2, va(10), '0', '0', '0', R1);

DD4 : or8 port map (a4nz1, a9z3, va(1), va(5), '0', '0', '0', '0', S1);

R3 <= va(10);

S3 <= R2;

v1 <= va(1);

v2 <= va(2);

v3 <= va(3);

v4 <= va(4);

v5 <= va(5);

v6 <= va(6);

v7 <= va(7);

v8 <= va(8);

v9 <= va(9);

v10 <= va(10);

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

end structure;

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

entity Test_Bench is

end Test_Bench;

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

architecture Schema of Test_Bench is

component Circuit is

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

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

end component;

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

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

begin

process

begin

h <= '1' after 150 ns;

z0 <= '1' after 800 ns;

z1 <= '1' after 1600 ns;

z2 <= '1' after 2400 ns;

z3 <= '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, z0, z1, z2, z3, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10);

end Schema;

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

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

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

В данной курсовой работе мы спроектировали управляющий цифровой автомат, функционирующий согласно заданной ГСА. В качестве элементной базы использовались интегральные микросхемы пяти различных типов. Был выполнен абстрактный и структурный синтез заданного автомата, получены функции выходов и возбуждения элементов памяти, а также построена функциональная схема. Также был произведен выбор элементов для физического синтеза схемы, составлено описание автомата на языке VHDL и выполнено моделирование на ПК с использованием симулятора ModelSim.

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

1. Методические указания по выполнению курсовой работы по дисциплине «Организация ЭВМ».

2. Лекции по предмету «Теория автоматов»

3. Справочник - М., Радио и связь