Зміст
1. Завдання
2. Введення
3. Абстрактний синтез автомата
4. Структурний синтез автомата
5. Функціональна схема автомата
6. Елементи фізичного синтезу
7. Опис автомата на мові VHD
8. Моделювання на ПК з використанням симулятора ModelSim
9. Висновок
10. Список літератури
1. Завдання
Спроектувати керуючий цифровий автомат типу Мура, що функціонує відповідно до заданої ДСА. ДСА будується з'єднанням фрагментів (рис. 1) в заданій послідовності (2, 1, 3, 4). Кожна операторна вершина визначає певний вихідний сигнал. Кількість умовних вершин у ГСА визначає вхідний алфавіт автомата. Тип використовуваних тригерів JK.
2. Введення
Курсова робота полягає у вирішенні комплексного завдання синтезу дискретного пристрою з пам'яттю за заданими умовами роботи на заданій елементної бази. Рішення повинне бути доведене до функціональної схеми пристрою (автомата).
Термін автомат, як правило, використовується в двох аспектах. З одного боку, автомат - пристрій, що виконує деякі функції без безпосередньої участі людини. У цьому сенсі ми говоримо, що ЕОМ автомат, так як після завантаження програми і вихідних даних ЕОМ вирішує задану завдання без участі людини. З іншого боку, термін «автомат» як математичне поняття означає математичну модель реальних технічних автоматів. У цьому аспекті автомат представляється як «чорний ящик», що має кінцеве число входів і виходів і деякий безліч внутрішніх станів Q = {q 1 (t), q 2 (t ),..., q n (t)}, в які він під впливом вхідних сигналів переходить стрибкоподібно, тобто практично миттєво, минаючи проміжний стан. Звичайно, ця умова не виконується в реальності, так як будь-який перехідний процес триває кінцевий час.
Цифровий автомат - пристрій, призначений для перетворення цифрової інформації. Вхідні сигнали в цифрових автоматах представляються у вигляді кінцевого безлічі миттєвих сигналів. Теоретично це означає, що вхідні сигнали не мають тривалості, хоча практично це не так. Таке припущення спрощує розгляд процесів, що відбуваються в автоматах, так як всі події (стану) повинні ставитися до фіксованого моменту часу t. Умовно також приймається, що кількість вихідних сигналів y (t) звичайно і вони виникають в результаті дії вхідних сигналів. При цьому слід враховувати, що одночасно з появою вихідного сигналу відбувається стрибкоподібний перехід автомата зі стану q i (t) в стан q j (t).
Поняття стану автомата використовується для опису систем, виходи яких залежать не тільки від вхідних сигналів у даний момент часу, але і від деякої передісторії, тобто сигналів, які надійшли на входи системи раніше. Стан автомата є певною пам'яті про минуле, дозволяючи усунути час як явну зміну і висловити вихідні сигнали як функцію станів і вхідних сигналів.
Час для цифрового автомата має також важливе значення. Для вирішення завдань аналізу і синтезу цифрових автоматів звичайно вводиться автоматне час. Функціонування автомата розглядається через дискретні інтервали часу кінцевої тривалості (інтервал дискретності).
Загальна теорія автоматів розбивається на дві великі частини - абстрактну теорію автоматів і структурну теорію автоматів. Різниця між ними полягає в тому, що в абстрактній теорії ми відволікаємося від структури як самого автомата, так і його вхідних і вихідних сигналів. Не цікавлячись способом побудови автомата, абстрактна теорія вивчає лише ті переходи, які зазнає автомат під впливом вхідних сигналів, і ті вихідні сигнали, які він при цьому видає. Абстрактна теорія автоматів близька теорії алгоритмів, є її подальшої деталізації.
На противагу абстрактної теорії, у структурній теорії автоматів розглядаються насамперед структури як самого автомата, так і його вхідних і вихідних сигналів. У структурній теорії вивчаються способи побудови автоматів з елементарних автоматів, способи кодування вхідних і вихідних сигналів елементарними сигналами і т.п.
3. Абстрактний синтез автомата
Однією з різновидів мови, що дозволяє описувати логічні схеми алгоритмів, є мова граф-схем алгоритмів (ГСА).
Граф-схема алгоритму - орієнтований зв'язний граф, що містить одну початкову вершину, довільне число умовних і операторних вершин і одну кінцеву вершину.
Кінцева, операторна і умовна вершини мають по одному входу, початкова вершина входів не має. Початкова і операторна вершини мають по одному виходу, кінцева вершина виходів не має, умовна вершина має два виходи, помічених символами 1 і 0. Граф-схема алгоритму задовольняє таким умовам:
1) входи і виходи вершин з'єднуються один з одним за допомогою дуг, спрямованих завжди від виходу до входу;
2) кожен вихід з'єднаний тільки з одним входом;
3) будь-який вхід з'єднується, принаймні, з одним виходом;
4) будь-яка вершина графа лежить, принаймні, на одній колії з початкової до кінцевої вершини;
5) в кожній умовної вершині записується один з елементів множини логічних умов A = {A 1, A 2, ,..., A k}, дозволяється в різних умовних вершинах запис однакових елементів множини A;
6) в кожній операторної вершині записується один з елементів множини операторів V = {v 1, v 2 ,..., v N }., Дозволяється в різних операторних вершинах запис однакових елементів множини V.
Мова ДСА використовується дуже часто при описі алгоритмів функціонування як самого цифрового автомата, так і програм, що виконують ту чи іншу дію.
Щоб побудувати схему керуючого автомата Мура, потрібно задати мікропрограму роботи операційного пристрою. Мікропрограма операційного блоку має вигляд, представлений на рис.2. Мікропрограма виконується при початковому умови Н = 1. Блок виробляє вироблення керуючих функціональних сигналів в певній послідовності, яка залежить від значень сигналів A 0 - 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. Довідник - М., Радіо і зв'язок