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

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

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

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

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

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

3 стр., 1146 слов

Основные понятия теории автоматов. Входной и выходной алфавит. ...

... реферата считаю важной и актуальной на данном этапе обучения. Необходимо рассмотреть такие вопросы как: o Основные понятия теории автоматов o Входной алфавит и выходной алфавит o Представление событий в автоматах o Автоматы Мили и Мура ...

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

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

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

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

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

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

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

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

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

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

5) в каждой условной вершине записывается один из элементов множества логических условий A = { A 1 ,A2 , ,…, Ak }, разрешается в различных условных вершинах запись одинаковых элементов множества A;

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

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

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

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

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

Рисунок 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. Список литературы

[Электронный ресурс]//URL: https://drprom.ru/kursovaya/avtomat-mura/

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

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

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