Тема: Синтез структурного автомата МИЛИ и эквивалентного автомата МУРА и реализация алгоритма умножения на языке VHDL

Курсовая работа по теории автоматов

«Синтез структурного автомата МИЛИ и эквивалентного автомата МУРА и реализация алгоритма умножения на языке VHDL»

2012

Построение автомата МИЛИ

Базис «И-НЕ» Триггеры JK и D Вариант 11

Таблицы переходов и выходов автомата Мили

S1 S2 S3 S4     S1 S2 S3 S4  X1 S3 S2 - S2    X1 Y4 Y2 - Y2  X2 S4 S3 - S2    X2 Y6 Y4 - Y2  X3 S3 - S2 S3    X3 Y3 - Y1 Y5  X4 - S1 S1 S3    X4 - Y3 Y3 Y6  

X={ X1, X2, X3, X4} множество входных сигналов, входной алфавит

S={ S1, S2, S3, S4} множество внутренних состояний, алфавит состояний

Y={ Y1, Y2, Y3, Y4, Y5, Y6} множество выходных сигналов, выходной алфавит

1ЭП: JK - триггер

Табл. пер. JK 0 1  00 0 1   01 0 0  10 1 1  11 1 0  

Табл. возб. Si JK Sp  0 0_ 0  0 1_ 1  1 _1 0  1 _0 1  

2ЭП: D - триггер

Табл. пер. D 0 1  0 0 0  1 1 1  

Табл. возб. Si D Sp  0 0 0  0 1 1  1 0 0  1 1 1  

1)Кодируем входные и выходные сигналы и состояния: 

 X1 0 0  X2 0 1  X3 1 0  X4 1 1  




 Y1 0 0 0  Y2 0 0 1  Y3 0 1 0  Y4 0 1 1  Y5 1 0 0  Y6 1 0 1   

 S1 0 0  S2 0 1  S3 1 0  S4 1 1  

2)Таблицы переходов и выходов и таблица возбуждения структурного автомата

Табл. пер. 00 01 10 11  00 10 01 - 01  01 11 10 - 01  10 10 - 01 10  11 - 00 00 10  

Табл. вых. 00 01 10 11  00 011 001 - 001  01 101 011 - 001  10 010  - 000 100  11 - 010 010 101  Табл. возб. 00 01 10 11   JKD JKD JKD JKD  00 1_0 0_1 - _11  01 1_1 1_0 - _11  10 1_0 - _11 _00  11 - 0_0 _10 _00  

3)Строим и минимизируем логические функции

J: 







  
X X X 1 
 
0 X X 1 
 
X X X 0 
 
1 X X 1 
  



   K: 









 
X 1 X X 
 
X 0 1 X 
 
X 0 1 X 
 
X 1 X X 
  



  

D: 







  
X 0 X 1 
 
0 0 1 0 
 
X 0 1 1 
 
0 1 X 0 
  



  









  
X 0 X 1 
 
0 1 0 0 
 
X 1 0 0 
 
0 0 X 0 
  



  








  
X 0 X 1 
 
0 1 1 1 
 
X 0 1 1 
 
0 0 X 1 
  



  








  
X 1 X 0 
 
1 0 0 1 
 
X 0 0 0 
 
1 0 X 1 
  



  

J = nt2 V (nx1&x2) = t2|((x1|x1)|x2)

S = nt2 V nx1 = t2|x1

T = (nx1&t1) V (nx1&x2&nt2) V (nx1&nx2&t2) V (nx2&t1&nt2) = ((x1|x1)|t1)|((x1|x1)|x2|(t2|t2))|((x1|x1)|(x2|x2)|t2)|((x2|x2)|t1|(t2|t2))

= (x1&t1&t2) V (nx1&x2nt2) = (x1|t1|t2)|((x1|x1)|x2|(t2|t2)

= (x1&nt1) V (x2&t1&nt2) V (x2&nt1&t2) V (nx1&nx2&nt2) = (x1|(t1|t1))|(x2|t1|(t2|t2))|(x2|(t1|t1)|t2)|((x1|x1)|(x2|x2)|(t2|t2)

= nx1 V (x2&t1&t2) = x1|(x2|t1|t2)

4) Строим схему, используя Quartus II

Построение эквивалентного автомата МУРА

1)Строим граф переходов автомата МИЛИ

S1={S1 Y3}={b1}

S2={S2 Y1; S2 Y2}={b2 b3}

S3={S3 Y3;S3 Y4;S3 Y5;S3 Y6}={ b4 b5 b6 b7}

S4={S4 Y6}={ b8}

2)Строим граф автомата МУРА

3)Заполняем таблицу переходов автомата МУРА Yi Y3 Y1 Y2 Y3 Y4 Y5 Y6 Y6  xii b1 b2 b3 b4 b5 b6 b7 b8  x1 b5 b3 b3 - - - - b3  x2 b8 b5 b5 - - - - b3  x3 b4 - - b2 b2 b2 b2 b6  x4 - b1 b1 b1 b1 b1 b1 b7  

4)Кодируем состояния и выходные сигналы, добавляем D-триггер

 u1 u2 u3  Y1 0 0 0  Y2 0 0 1  Y3 0 1 0  Y4 0 1 1  Y5 1 0 0  Y6 1 0 1   ?1 ?2 ?3  b1 0 0 0  b2 0 0 1  b3 0 1 0  b4 0 1 1  b5 1 0 0  b6 1 0 1  3) ЭП: T - триггер

Таблицы возбуждения: Si JK Sp  Si T Si  Si D Sp  0 0_ 0  0 0 0  0 0 0   0 1_ 1  0 1 1  0 1 1  1 _1 0  1 1 0  1 0 0  1 _0 1  1 0 1  1 1 1  

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

Y 010 000 001 010 011 100 101 101  xii 000 001 010 011 100 101 110 111  00 100 010 010 - - - - 010  01 111 100 100 - - - - 010  10 011 - - 001 001 001 001 101  11 - 000 000 000 000 000 000 110  

Таблица возбуждений структурного автомата: bi 000 001 010 011 100 101 110 111   JKDT JKDT JKDT JKDT JKDT JKDT JKDT JKDT  00 1_00 0_11 0_10 - - - - _111  01  1_11 1_00 1_00 - - - - _111  10 0_11 - - 0_00 _101 _100 _101 _000  11 - 0_01 0_00 0_01 _100 _101 _100 _011  5)Минимизируем сигналы используя карты Карно

J: 















  
X X 0 1 0 X X X 
 
X X 0 X X 0 X X 
 
X X 0 1 0 X X X 
 
X X X 1 1 0 X X 
  







   K: 















  
X 1 X X X X 1 X 
 
1 0 X X X X 0 1 
 
X 1 X X X X 1 X 
 
X 1 X X X X 1 X 
  







  

D: 















  
X 0 0 0 1 X 0 X 
 
1 1 0 X X 0 0 1 
 
X 0 0 0 1 X 0 X 
 
X 0 X 1 0 1 0 X 
  







  

T: 















  
X 0 0 0 0 X 1 X 
 
1 1 1 X X 0 0 1 
 
X 1 1 1 1 X 0 X 
 
X 0 X 1 0 1 1 X 
  







  Минимизация функций:

J=(nx1&x2) V (nt2&nt3&nx1) = ((x1|x1)|x2)|((t2|t2)|(t3|t3)|(x1|x1))

K=nt3&nx1&nt2 = t3|x1|t2

D=(t1&t2&t3&x2) V (nt1&nt2&nt3&x2) V (t2&nx1&nx2) V (nt1&nt2&t3&nx2) V (nt1&nt3&x1&nx2) = (t1|t2|t3|x2)|((t1|t1)|(t2|t2)|(t3|t3)|x2)|(t2|(x1|x1)|(x2|x2))|((t1|t1)|(t2|t2)|t3|(x2|x2))|((t1|t1)|(t3|t3)|x1|(x2|x2)

T=(t3&x2) V (nt1&nt2&x2) V (t3&nx1) V (nt3&x1&nx2) = (t3|x2)|((t1|t1)|(t2|t2)|x2)|(t3|(x1|x1))|((t3|t3)|x1|(x2|x2))









 
1 1 0 0  
0 1 0 0   



 








 
0 0 1 0  
1 0 0 1   



 








 
1 1 0 1  
1 0 0 0   



 

u1= (t1&t3) V (t1&t2) = (t1|t3)|(t1|t2)

u2= (nt2&nt3) V (nt1&t2Vt3) = ((t2vt2)|(t3|t3))v((t1|t1)|t2|t3)

u3= (t1&nt3) V (t1&t2) V (t2&nt3) = (t1|(t3|t3))|(t1|t2)|(t2|(t3|t3))

5) Строим схему, используя Quartus II

6) С помощью стенда для проверки, отлаживаем автомат, проверяем переключение в нужные состояния соответствующие им выходные сигналы

ТЕХHИЧЕСКОЕ ЗАДАHИЕ N11

на пpоектиpование пpоцессоpа с заданной системой команд

1. Система памяти

а) Опеpативная память (ОП) имеет емкость 16 четыpехpазpядных слов (ячейка РУ2).

б) Регистpовая память (РП) имеет емкость 4 четыpехpазpядных слов (ячейка РП1).

2. Фоpмат и пpедставление чисел

Дpобные числа с фиксиpованной запятой пpедставлены в пpямом коде. Под запись числа отводится четыpе pазpяда. Самый левый pазpяд используется для пpедставления знака.

3. Фоpмат команд

Команды двухадpесные и двух фоpматов: "pегистp-pегистp" (РР) и "непосpедственный опеpанд-память" (HП). В фоpмате РР записываются команды длинной опеpации, в фоpмате HП - команды коpоткой опеpации и пеpехода.

В фоpмате РР указываются пpямые адpеса 1-го и 2-го опеpандов, pасположенных в РП. В фоpмате HП 1-й опеpанд указывается с помощью непосредственной адpесации, 2-й опеpанд - пpединдексной косвенной адpесации (2-й опеpанд хpанится в ОП).

Результат опеpаций записывается по адpесу 2-го опеpанда.

Команды фоpмата РР хpанятся в 2-х, а кокманды фоpмата HП - в 3-х последовательных ячейках ОП.

Размещение командной инфоpмации в фоpматах выполнить самостоятельно.

4. Опеpации

а) УМHОЖЕHИЕ. Опеpация выполняется по алгоpитму умножения чисел в пpямом коде со стаpших pазpядов множителя и сдвигом суммы частичных пpоизведений влево [1-4, 6, 8]. Пpи нулевом значении анализиpуемого pазpяда множителя такт суммиpования пpопускается. Пеpвый опеpанд - множимое, втоpой - множитель.

б) УМЕHЬШЕHИЕ КОДА. Значение пеpвого опеpанда (двоичного кода) уменьшается на 1. Результат помещается по адресу втоpого опеpанда. Устанавливается пpизнак pезультата: 0-pезультат pавен нулю, 1-pезультат не pавен нулю.

в) ПЕРЕХОД ПО HЕРАВЕHСТВУ HУЛЮ. Адpес в счетчике команд (СК) замещается адpесом пеpехода, если значение признака результата не равно 0. В пpотивном случае (СК)=(СК)+2. В качестве адpеса пеpехода используется пpямой адpес. Команда пеpехода занимает 2 ячейки ОП.

Блок-схема алгоритма умножения:

01

0

1

Листинг программы:

library IEEE;

use IEEE.STD_LOGIC_1164.ALL;

use IEEE.STD_LOGIC_ARITH.ALL;

use IEEE.STD_LOGIC_UNSIGNED.ALL;

---- Uncomment the following library declaration if instantiating

---- any Xilinx primitives in this code.

--library UNISIM;

--use UNISIM.VComponents.all;

entity new_1 is

Port ( a : in STD_LOGIC_VECTOR (3 downto 0);

b : in STD_LOGIC_VECTOR (3 downto 0);

kop : in STD_LOGIC;

c : out STD_LOGIC_VECTOR (7 downto 0));

end new_1;

architecture Behavioral1 of new_1 is

begin

process (a,b)

variable rb: STD_LOGIC_VECTOR (3 downto 0);

variable ra,rr: STD_LOGIC_VECTOR (7 downto 0);

begin

ra:="00000"&a(2 downto 0);

rb:=0&b(2 downto 0);

rr:="00000000";

for i in 1 to 3 loop

if (rb(2)=1) then rr:=rr+ra;

end if;

rb:=rb(2 downto 0)&0;

rr:=rr(6 downto 0)&0;

end loop;

rr:=0&rr(7 downto 1);

rr(7):=a(3) xor b(3);

c<=rr(7 downto 0);

end process;

end Behavioral1;