Абстрактный автомат Мили

Размещено на http://www.allbest.ru/

Содержание

1. Абстрактные автоматы

1.1 Задание на первую часть курсового проекта

1.2 Минимизация абстрактного автомата Мили

1.3 Синтез схемы конечного автомата

1.4 Проверка по первой части курсового проекта

1.5 Моделирование работы абстрактного автомата

2. Микропрограммные автоматы на базе логических матриц

2.1 Задание на вторую часть курсового проекта

2.2 Синтез микропрограммного автомата

2.3 Синтез счётчика числа микрокоманд

2.4 Разработка цифровой линии задержки (таймера)

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

1. Абстрактные автоматы

1.1 Задание на первую часть курсового проекта

1.2 Минимизация абстрактного автомата Мили

Автомат Мили задан таблицами переходов (табл.1.1) и выходов (табл.1.2).

Таблица. 1.1.

	s1	s2	s3	s4	s5	s6	s7	s8
х1	s3	s4	s2	s7	s3	s4	s5	s5
х2	s2	s8	s4	s1	s6	s8	s3	s3
х3	s4	s1	s7	s3	s4	s5	s6	s2

Таблица. 1.2.

	s1	s2	s3	s4	s5	s6	s7	s8
х1	y3	y1	y3	y1	y3	y1	y3	y3
х2	y2	y3	y2	y3	y2	y3	y2	y2
х3	y1	y2	y1	y2	y1	y2	y1	y1
	B1	B2	B1	B2	B1	B2	B1	B1

Разбиение на 1-классы эквивалентности осуществляется путём выявления одинаковых столбцов таблицы 1.2 , при этом получаем:

Строим таблицу 1-разбиения (табл. 1.3.) и из неё находим разбиение на 2-классы.

Таблица. 1.3.

1	B1	B2
	s1	s3	s5	s7	s8	s2	s4	s6
х1	B1	B2	B1	B1	B1	B2	B1	B2
х2	B2	B2	B2	B1	B1	B1	B1	B1
х3	B2	B1	B2	B2	B2	B1	B1	B1
	C1	C2	C1	C3	C3	C4	C5	C4

Строим таблицу 2-разбиения (табл. 1.4.) и из неё находим разбиение на 3-классы.

абстрактный автомат микрокоманда цифровой

Таблица. 1.4.

2	C1	C2	C3	C4	C5
	s1	s5	s3	s7	s8	s2	s6	s4
x1	C2	C2	C4	C1	C1	C5	C5	C3
x2	C4	C4	C5	C2	C2	C3	C3	C1
x3	C5	C5	C3	C4	C4	C1	C1	C2
	D1	D1	D2	D3	D3	D4	D4	D5

Дальнейшее разбиение невозможно. Таким образом, найдены ? - классы, которым соответствует автомат Мили, описываемый таблицами переходов (табл. 1.5.) и выходов (табл. 1.6.).

Таблица 1.5.

	s1	s2	s3	s4	s7
х1	s3	s4	s2	s7	s1
х2	s2	s7	s4	s1	s3
х3	s4	s1	s7	s3	s2

Таблица 1.6.

	s1	s2	s3	s4	s7
х1	y3	y1	y3	y1	y3
х2	y2	y3	y2	y3	y2
х3	y1	y2	y1	y2	y1

Построим реакции исходного и оптимизированного автоматов на входное воздействие x2x1x3x1x3x3x1x2, при начальном состоянии автомата s[0]=s1(табл. 1.7.).

Таблица 1.7.

Входное воздействие	x2	x1	x3	x1	x3	x3	x1	x2
Реакция исходного автомата	y2	y1	y2	y3	y2	y1	y1	y2
Реакция минимизированного автомата	y2	y1	y2	y3	y2	y1	y1	y2

Построим граф-схемы исходного (рис. 1.1) и оптимизированного (рис. 1.2.) автоматов.

Размещено на http://www.allbest.ru/

Рис. 1.1. Граф-схема исходного автомата.

Размещено на http://www.allbest.ru/

Рис. 1.2. Граф-схема минимизированного автомата.

1.3 Синтез схемы конечного автомата

Абстрактный синтез

1. Выбор количества триггеров. Так как автомат имеет 5 состояний, то требуется q=]log25[=3 триггера.

2. Кодирование внутренних состояний входных, выходных сигналов:

	Q1	Q2	Q3
S1	0	0	0
S2	0	0	1
S3	0	1	0
S4	0	1	1
S7	1	0	0

Qn	Qn+1	д
0	0	0
1	1	1
1	0	-
0	1	+

	X
	V1	V2
Х1	0	0
Х2	0	1
Х3	1	0

	Y
	W1	W2
Y1	0	0
Y2	0	1
Y3	1	0

3. Составление таблицы переходов. На основании графа переходов составляем таблицу переходов (табл. 1.8.), указывая текущие и будущие состояния триггеров, а также значения операторов перехода.

Таблица 1.8.

N	sn	sn+1	входные	выходные	v1	v2	K(Sn)	K(Sn+1)	д
			xi	v1	v2	yi	w1	w2			Q1	Q2	Q3	Q1	Q2	Q3	Q1	Q2	Q3
1	s1	s3	x1	0	0	y3	1	0	0	0	0	0	0	0	1	0	0	+	0
2	s1	s2	x2	0	1	y2	0	1	0	1	0	0	0	0	0	1	0	0	+
3	s1	s4	x3	1	0	y1	0	0	1	0	0	0	0	0	1	1	0	+	+
4	s2	s4	x1	0	0	y1	0	0	0	0	0	0	1	0	1	0	0	+	1
5	s2	s7	x2	0	1	y3	1	0	0	1	0	0	1	1	1	0	+	0	-
6	s2	s1	x3	1	0	y2	0	1	1	0	0	0	1	0	1	1	0	0	-
7	s3	s2	x1	0	0	y3	1	0	0	0	0	1	0	1	1	0	0	-	+
8	s3	s4	x2	0	1	y2	0	1	0	1	0	1	0	0	0	0	0	1	+
9	s3	s7	x3	1	0	y1	0	0	1	0	0	1	0	0	1	0	+	-	0
10	s4	s2	x1	0	0	y1	0	0	0	0	0	1	1	0	0	0	+	-	-
11	s4	s1	x2	0	1	y3	1	0	0	1	0	1	1	0	0	1	0	-	-
12	s4	s3	x3	1	0	y2	0	1	1	0	0	1	1	1	1	0	0	1	-
13	s7	s1	x1	0	0	y3	1	0	0	0	1	0	0	0	0	1	-	0	0
14	s7	s3	x2	0	1	y2	0	1	0	1	1	0	0	0	1	1	-	+	0
15	s7	s2	x3	1	0	y1	0	0	1	0	1	0	0	0	0	0	-	0	+

Структурный синтез

Составление обобщенных карт Карно. Так как автомат содержит три триггера, то составляем три обобщенных карты Карно (содержат в клетках значения оператора переходов) и две карты Карно для получения логического выражения для функции выхода.

1. Синтез на базе Т-триггеров в базисе ИЛИ-НЕ.

Для того чтобы составить логическое выражение для сигнала возбуждения Т, с помощью операции пересечения, необходимо на обобщенной карте Карно охватить контурами все клетки, помеченные знаками «1» и «0», и пустые клетки, т. е. функция возбуждения Т-триггера определяется выражением:

Т=? {1,0,(Ш)}.

Нахождение функций выходов.

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	1	0	0	1				1
01	0	1	1	0				0
11
10	0	0	0	0				0

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	0	0	0				0
01	1	0	0	1				1
11
10	0	1	1	0				0

Нахождение функций переходов:

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	0	+	0				-
01	0	+	0	0				-
11
10	0	0	0	+				-

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	+	+	-	-				0
01	0	0	-	1				+
11
10	+	0	1	-				0

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	1	-	+				0
01	+	-	-	+				0
11
10	+	-	-	0				+

Схемная реализация. На основании полученных выше выражений составляем схему абстрактного автомата. На количество входов логических элементов ограничения не налагаем.



Рис. 1.3. Схема автомата на Т-триггерах.

2. Синтез на базе JK-триггеров в базисе И-НЕ.

Для того чтобы составить логическое выражение для сигнала J, необходимо на обобщенной карте Карно охватить контурами все клетки, помеченные знаком «+» (причем для его минимизации разрешается включать в контуры единичные и пустые клетки и клетки, помеченные знаком «-»), а для сигнала К - все клетки, помеченные знаком «-» (для минимизации разрешается включать нулевые и пустые клетки и клетки, помеченные «+»), т. е. функции возбуждения .JK-триггера определяются выражениями:

J=U{+, (-), (1), (Ш)}; K= U {-, (+), (0), (Ш)};

Нахождение функций выходов.

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	1	0	0	1				1
01	0	1	1	0				0
11
10	0	0	0	0				0

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	0	0	0				0
01	1	0	0	1				1
11
10	0	1	1	0				0

Нахождение функций переходов.

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	0	+	0				-
01	0	+	0	0				-
11
10	0	0	0	+				-

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	0	+	0				-
01	0	+	0	0				-
11
10	0	0	0	+				-

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	+	+	-	-				0
01	0	0	-	1				+
11
10	+	0	1	-				0

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	+	+	-	-				0
01	0	0	-	1				+
11
10	+	0	1	-				0

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	1	-	+				0
01	+	-	-	+				0
11
10	+	-	-	0				+

v1v2	Q1 Q2 Q3
	000	001	011	010	110	111	101	100
00	0	1	-	+				0
01	+	-	-	+				0
11
10	+	-	-	0				+

Схемная реализация. На основании полученных выше выражений составляем схему абстрактного автомата. На количество входов логических элементов ограничения не налагаем.



Рис. 1.4. Схема автомата на JK-триггерах.

1.4 Проверка по первой части курсового проекта

97 ЛапинРИ 5430200097

classes=1,5/2,6/3/4/7,8;

Yout=y2y1y2y3y2y1y1y2;

end;

Var#97 Fio:ЛапинРИ Chiffr:5430200097

Check results:

Automaton equivalence classes: Correct!

Automaton output sequence: Correct!

******END******

1.5 Моделирование работы абстрактного автомата

1. Листинг программы на языке С++:

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

#include <iomanip.h>

const int cAC=15; //цвет активного меню

const int cNOTAC=0; //цвет не активного меню

const int cDISP=1; //цвет дисплея

int arrs1[3][8]={{3,4,2,7,3,4,5,5},{2,8,4,1,6,8,3,3},{4,1,7,3,4,5,6,2}};

int arry1[3][8]={{3,1,3,1,3,1,3,3},{2,3,2,3,2,3,2,2},{1,2,1,2,1,2,1,1}};

int arrs2[3][8]={{3,4,2,7,0,0,1,0},{2,7,4,1,0,0,3,0},{4,1,7,3,0,0,2,0}};

int arry2[3][8]={{3,1,3,1,0,0,3,0},{2,3,2,3,0,0,2,0},{1,2,1,2,0,0,1,0}};

void calc(int);

void tabl(int);

void obtabl(char,char,char,char,char,char,int);

void PrintMenu(int,int,int,int);

void main()

{

int i,c;

int flag=0;

int sScr[4000];

struct

{

char name[51];

int x;

int y;

}

menu[3]={

{ " 1. Исходные данные ",2, 5 },

{ " 2. Минимизированный автомат ",2, 7 },

{ " 3. Выход ",2, 9 }

};

textcolor(7);

textbackground(cDISP);

clrscr();

window(16,15,64,26);

PrintMenu(16,15,64,26);

textcolor(4);

textbackground(15);

gotoxy(2,2);

cprintf(" ГЛАВНОЕ МЕНЮ ");

textcolor(cNOTAC);

textbackground(2);

for(i=0; i<3; i++)

{

gotoxy(menu[i].x,menu[i].y);

cprintf("%s",menu[i].name);

}

textcolor(cAC); //изменение цвета активной строки меню

gotoxy(menu[flag].x,menu[flag].y);

cprintf("%s",menu[flag].name);

gotoxy(3,5);

while (1)

{

c=getch();

window(16,15,64,26);

textbackground(2);

switch(c)

{

case 72 : //движение по меню вверх

textcolor(cNOTAC);

gotoxy(menu[flag].x,menu[flag].y);

cprintf("%s",menu[flag].name);

gotoxy(3,menu[flag].y);

flag--; //переменная, определяющая № подсвеченной строки

if(flag<0)

flag=2;

textcolor(cAC);

gotoxy(menu[flag].x,menu[flag].y);

cprintf("%s",menu[flag].name);

gotoxy(3,menu[flag].y);

break;

case 80 : //движение по меню вниз

textcolor(cNOTAC);

gotoxy(menu[flag].x,menu[flag].y);

cprintf("%s",menu[flag].name);

gotoxy(3,menu[flag].y);

flag++;

if(flag>2)

flag=0;

textcolor(cAC);

gotoxy(menu[flag].x,menu[flag].y);

cprintf("%s",menu[flag].name);

gotoxy(3,menu[flag].y);

break;

case 13:

gettext(1,1,80,50,&sScr);

textbackground(cDISP);

window(1,1,80,50);

clrscr();

switch (flag)

{

case 0:

case 1:

calc(flag);

break;

case 2:

return;

}

clrscr();

puttext(1,1,80,50,sScr);

window(16,15,64,26);

gotoxy(3,menu[flag].y);

default:

gotoxy(3,menu[flag].y);

}

}

}

//определение функции вывода главного меню на экран

void PrintMenu(int x1,int y1,int x2,int y2)

{

int i,j;

window(x1,y1,x2+1,y2+1);

gotoxy(1,1);

cout<<"\311"; // верхний левый угол

for(i=2; i<x2-x1+1; i++)

{

gotoxy(i,1);

cout<<"\315"; // верхняя горизонтальная линия

gotoxy(i,y2-y1+1);

cout<<"\315"; // нижняя горизонтальная линия

}

gotoxy(x2-x1+1,1);

cout<<"\273"; // верхний правый угол

for(j=2; j<y2-y1+1; j++)

{

gotoxy(1,j);

cout<<"\272"; // левая вертикальная линия

gotoxy(x2-x1+1,j);

cout<<"\272"; // правая вертикальная линия

}

gotoxy(1,y2-y1+1);

cout<<"\310"; // левый нижний угол

gotoxy(x2-x1+1,y2-y1+1);

cout<<"\274"; // правый нижний угол

}

void calc(int flag)

{

int s[9],x[8],y[8],i;

do

{

clrscr();

if(flag==0)

{

cout<<"\n\n Абстрактный автомат Мили задан таблицей переходов/выходов\n\n";

tabl(8);

cout<<"\n\nЭта таблица определяет функцию переходов автомата s(t+1) =

П[x(t),s(t)] и функцию выходов y(t)=B[x(t),s(t)].";

cout<<"Здесь: s(t) - состояние, x(t) - входной, y(t) - выходной символ автомата в

момент времени t";

}

else

{

cout<<"\n\n Минимизированное число состояний абстрактного

автомата\n\n";

cout<<" Таблица переходов минимизируемого автомата\n\n";

tabl(5);

}

for(i=0;i<8;i++)

s[i]=y[i]=0;

cout<<"\n\nВведите x через пробел (8 значений) и 0

(если введено меньше 8 значений):\nx = ";

for(i=0;i<8;i++)

{

cin>>x[i];

if(x[i]==0)

break;

}

cout<<"\nВведите начальное состояние автомата s0: ";

cin>>s[0];

for(i=0;i<8;i++)

{

if(x[i]==0)

break;

if(flag==0)

{

y[i]=arry1[x[i]-1][s[i]-1];

s[i+1]=arrs1[x[i]-1][s[i]-1];

}

else

{

y[i]=arry2[x[i]-1][s[i]-1];

s[i+1]=arrs2[x[i]-1][s[i]-1];

}

}

cout<<"\n\nФункция выходов y: ";

for(i=0;i<8;i++)

{

if(y[i]==0)

break;

cout<<"y"<<y[i];

}

cout<<"\n\nЦепочка состояний s: ";

for(i=0;i<8;i++)

{

if(s[i+1]==0)

break;

cout<<"s"<<s[i];

}

cout<<"\n\n\nПродолжение - Enter. ESC - Выход в главное меню.";

}

while(getch()!=27);

}

void tabl(int c)

{

obtabl('\311','\315','\313','\315','\315','\273',c);

cout<<" \272 x(t) \272";

if(c==5)

cout<<" s(t) \272";

else

cout<<" s(t) \272";

obtabl('\272',' ','\314','\313','\315','\271',c);

cout<<" \272 \272";

for(int i=0;i<c;i++)

{

if(c==5&&i==4)

cout<<" s7 \272";

else

cout<<" s"<<i+1<<" \272";

}

for(i=0;i<3;i++)

{

obtabl('\314','\315','\316','\316','\315','\271',c);

cout<<" \272 x"<<i+1<<" \272";

for(int j=0;j<c;j++)

{

if(c==5)

{

if(j==4)

cout<<" s"<<arrs2[i][6]<<"/y"<<arry2[i][6]<<" \272";

else

cout<<" s"<<arrs2[i][j]<<"/y"<<arry2[i][j]<<" \272";

}

else

cout<<" s"<<arrs1[i][j]<<"/y"<<arry1[i][j]<<" \272";

}

}

obtabl('\310','\315','\312','\312','\315','\274',c);

}

void obtabl(char a,char b,char c,char d,char e,char f,int k)

{

cout<<"\n "<<a;

for(int i=0;i<6;i++)

cout<<b;

cout<<c;

for(int j=0;j<k;j++)

{

for(i=0;i<7;i++)

cout<<e;

cout<<d;

}

cout<<"\b"<<f<<"\n";

}

2. Интерфейс программы

Рис. 1.5. Вид главного меню программы.

Рис. 1.6. Реакция исходного автомата на входное воздействие x2x1x3x1x3x3x1x2.



Рис. 1.7. Реакция минимизированного автомата на входное воздействие x2x1x3x1x3x3x1x2.

2. Микропрограммные автоматы на базе логических матриц

2.1 Задание на вторую часть курсового проекта

2.2 Синтез микропрограммного автомата

Абстрактный синтез МПА

1. Составление графа функционирования по ТМА.

Состояниям Yi, в ТМА сопоставляются операторные вершины в графе функционирования ГФ. Связи между вершинами в ГФ, т. е. его ветви находятся по ТМА следующим образом.

1). Задаемся некоторой вершиной Yi и находим в ТМА строку Yi.

2). Если клетка YiYi не пуста, то вершина Yi должна иметь петлю. (Однако, на ГФ петли изображать не принято, но они подразумеваются. В этом случае на ГСА вслед за операторной вершиной Yi должна следовать ждущая вершина.)

Если в клетке YiYi указано временное условие , задающее выдержку времени, то символ ti указывается в скобках в вершине Yi. Это означает, что микрокоманда должна отрабатываться в течение временного интервала ti.

Если в клетке YiYi указано логическое условие то микрокоманда Yi должна выполняться до тех пор, пока не станет zi=1. Следовательно, ветвь, выходящая из вершины Yi, помечается символом zi. Наконец, если клетка YiYi пустая, то непосредственно за микрокомандой Yi, должна отрабатываться следующая микрокоманда, определяемая информацией, записанной в другие клетки строки Yi. (При этом на ГСА вслед за операторной вершиной Yj ждущая вершина уже не включается).

3). Если в строке Yi некоторая клетка YiYj не пуста и в ней записано некоторое условие zi, то на ГФ проводится ветвь из вершины Yi в вершину Yj, эта ветвь помечается символом zi и т. д.



Рис. 2.1. Граф функционирования МПА.

2. Составление граф-схемы алгоритма ГСА по графу функционирования.

Если на ГСА отметить некоторыми символами состояния автомата, то будет получена так называемая отмеченная ГСА. Отметка осуществляется согласно следующим правилам:

1) Вход вершины, следующей за начальной операторной вершиной, обозначается некоторым символом, например а0.

2) Этим же символом отмечается вход конечной вершины, если она существует (в данном случае такой вершины нет, так как заданный граф циклический, т. е. замкнутый).

3) Входы всех вершин, следующих за операторными, помечаются различными символами, например а1, а2, а3 ...



Рис. 2.2. Граф-схема алгоритма ГСА.

3. Построение абстрактной таблицы переходов.

В абстрактной таблице переходов пять столбцов: номер строки N, текущее аn и будущее аn+1 состояния, входные {Z} и выходные {Y} сигналы. Каждая строка таблицы соответствует одному пути перехода автомата. Если необходимо сохранить некоторое состояние МПА неизменным, то аn и аn+1 принимаются равными.

Таблица. 2.1.

N	an	an+1	{Z}	{Y}
1	a0	a0		y0
2	a0	a1	z0	y3(t3)
3	a1	a2	1	y1(t1)
4	a2	a3	1	y6(t6)
5	a3	a4	1	y4 (t4,z4)
6	a4	a4	z4	y4 (t4,z4)
7	a4	a5		y11
8	a5	a3	1	y6(t6)

Структурный синтез МПА

1. Рациональное кодирование состояний автомата.

Максимальный индекс аi равен 5, следовательно, необходимо не менее трех двоичных разрядов (Q4, Q2, Q1) для кодирования всех аi.

Правило кодирования состояний аi с целью минимизации величины У К: чем чаще встречается ai в столбце аn+1 абстрактной таблицы переходов, тем с меньшим числом единиц должна использоваться комбинация для кодирования этого состояния.

Таблица. 2.2.

Состояние ai	Число повторений	K(an+1)
		Q4	Q2	Q1
a0	1	0	1	1
a1	1	0	0	1
a2	1	0	1	0
a3	2	0	0	0
a4	2	1	0	0
a5	1	1	0	1

2. Построение структурной таблицы переходов (табл. 2.3.).

Сравнивая текущее значение Qi в кодовой комбинации k(an) с будущим значением Qi в комбинации k(an+1), находим сигналы переходов д.

Таблица. 2.3.

N	an	an+1	{Z}	{Y}	K(an)	K(an+1)	д
					Q4	Q2	Q1	Q4	Q2	Q1	Q4	Q2	Q1
1	a0	a0		y0	0	1	1	0	1	1	0	1	1
2	a0	a1	z0	y3(t3)	0	1	1	0	0	1	0	-	1
3	a1	a2	1	y1(t1)	0	0	1	0	1	0	0	+	-
4	a2	a3	1	y6(t6)	0	1	0	0	0	0	0	-	0
5	a3	a4	1	y4 (t4,z4)	0	0	0	1	0	0	+	0	0
6	a4	a4	z4	y4 (t4,z4)	1	0	0	1	0	0	1	0	0
7	a4	a5		y11	1	0	0	1	0	1	1	0	+
8	a5	a3	1	y6(t6)	1	0	1	0	0	0	-	0	-

3. Вывод логических выражений для функций выходов и переходов.

Для нахождения перечисленных функций целесообразно составить промежуточные контермы КN, где индекс N соответствует номеру строки. Контермы составляются по абстрактной и структурной таблицам переходов следующим образом: для N-й строки образуется конъюнкция из сигналов Qi (в текущий момент времени) и входных сигналов zi, взятых со знаками инверсии либо без них.

Функции возбуждения будем искать для D - триггеров, объединяя контермы, для которых операторы д помечены знаками «1» и «+».

Таблица. 2.4.

Kn	Контермы	Функции выходов
K1		y0=K1; y1= K3 ;y3 =K2 ; y4= K5 v K6 ;y6= K4 v K8 ; y11= K7 ;
K2
K3
K4
K5		Функции возбуждения
K6		D4= K5 v K6 v K7; D2= K1 v K3; D1= K1 v K2 v K7;
K7
K8

Схемная реализация МПА

Обратимся к табл.2.4, где приведены функции выходов МПА и функции возбуждения триггеров. Из этой таблицы видно, что произвольная функция уi, Tj может быть представлена как дизъюнкция ряда контермов. Таким образом, матричная схема МПА должна содержать две матрицы (рис.2.3): M1 - для формирования контермов и M2 - для выработки выходных величин в виде дизтермов.

Кроме того, структурная схема на рис.2.3 содержит триггерный регистр Рг, объект управления ОУ, цифровую линию задержки ЦЛЗ (таймер), генератор прямоугольных импульсов ГПИ и счетчик числа микрокоманд СТМ.

Матрица M2 вырабатывает микрокоманды {У}, управляющие ОУ, и функции возбуждения {А} - триггерами Рг. Совокупность сигналов {Z} характеризует состояние ОУ, а совокупность сигналов {Q} - состояние элементов памяти МП А. Из перечисленных сигналов матрица М1 формирует контермы {К}. ЦЛЗ управляется кодами {В}, соответствующими отрабатываемой в данный момент микрокоманде, так что импульсы f от ГПИ проходят на вход синхронизации С регистра с требуемой задержкой ti.



Рис. 2.3. Структурная схема МПА.

Функциональная схема МПА представлена на рис.2.4. В любом рабочем состоянии МПА лишь на одном выходе матрицы M1, и, следовательно, на одном входе матрицы M2 может действовать единичный сигнал. Поэтому первую из них назовем матрицей-дешифратором, а вторую - матрицей-шифратором. Регистр образован из трех D-триггеров. ЦЛЗ формирует временные интервалы заданной длительности ti, требуемой для отработки микрокоманд yi. ЦЛЗ управляется непосредственно сигналами у1, y3, y4, y6.

Совокупность сигналов {Z} оповещает о состоянии ОУ и поступает по цепи обратной связи, как и совокупность сигналов {Q} на входные (вертикальные) шины M1; из перечисленных сигналов {Q}, {Z} образуются контермы Ki на горизонтальных шинах матриц.



Рис. 2.4. Функциональная схема МПА на базе ПЛМ.

2.3 Синтез счётчика числа микрокоманд

Абстрактный синтез счётчика

1. Выбор количества триггеров. Т.к. N=10, то требуется y=]log210[=4 триггера. Обозначим их А, Б, В, Г.

2. Кодирование внутренних состояний.

Рис. 2.5. Граф переходов счетчика

С помощью четырёх триггеров можно получить Nmax=2q=16 внутренних состояний КА. В данном случае 6 из них являются лишними, поэтому возьмём только первые 10. Счетчик работает в коде Грея.

3. Составление таблиц переходов. На основании графа переходов составим таблицу переходов (табл. 2.5.), указывая текущие и будущие состояния триггеров, а также значение операторов перехода.

Таблица. 2.5.

N10	А	Б	В	Г	Текущие состояния в момент n	Будущие состояния в момент n+1	Операторы перехода д
					А	Б	В	Г	А	Б	В	Г	А	Б	В	Г
0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	+
1	0	0	0	1	0	0	0	1	0	0	1	0	0	0	+	-
2	0	0	1	0	0	0	1	0	0	1	0	0	0	+	-	0
3	0	1	0	0	0	1	0	0	0	1	0	1	0	1	0	+
4	0	1	0	1	0	1	0	1	1	0	0	0	+	-	0	-
5	1	0	0	0	1	0	0	0	1	0	0	1	1	0	0	+
6	1	0	0	1	1	0	0	1	1	0	1	0	1	0	+	-
7	1	0	1	0	1	0	1	0	1	1	0	0	1	+	-	0
8	1	1	0	0	1	1	0	0	1	1	0	1	1	1	0	+
9	1	1	0	1	1	1	0	1	0	0	0	0	-	-	0	-

4. Составляем обобщённые карты Карно. Так как счётчик содержит 4 разряда, то составляем четыре карты: А, Б, В и Г, в клетки которых заносим значения операторов перехода для соответствующих разрядов.

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	0
0 1	+	0	0	0
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	+	1	1
0 1	0	0	-	1
1 1	0	0
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	+
0 1	1	1	1	1
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	+	1	-	0
0 1	0	-	1	+
1 1	+	-
1 0

Структурный синтез счётчика.

1. Выбор элементной базы и типа триггеров. В качестве запоминающих устройств выбираем универсальные синхронные JK- триггеры, а элементная база - ИЛИ-НЕ.

2. Вывод логических выражений для сигналов возбуждения JK- триггеров.

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	0
0 1	+	0	0	0
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	0
0 1	+	0	0	0
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	+
0 1	1	1	1	1
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	0	0	+
0 1	1	1	1	1
1 1	1	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	+	1	1
0 1	0	0	-	1
1 1	0	0
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	0	+	1	1
0 1	0	0	-	1
1 1	0	0
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	+	1	-	0
0 1	0	-	1	+
1 1	+	-
1 0

АБ/ВГ	0 0	0 1	1 1	1 0
0 0	+	1	-	0
0 1	0	-	1	+
1 1	+	-
1 0

3. Схемная реализация счётчика. На основании полученных выше выражений составляем схему счетчика по модулю 10 на JK-триггерах (рис.2.6).

Рис. 2.6. Схема счетчика на JK-триггерах

Синтез преобразователя кода

Необходимо синтезировать преобразователь кода Грея в код управления семисегментным индикатором. Сам индикатор представляет собой полупроводниковый прибор, в котором имеются семь сегментов, выполненных из светодиодов. Включением и выключением отдельных сегментов можно получить светящееся изображение отдельных цифр. Расположение сегментов индикатора показаны на рис. 2.7.



Рис. 2.7. Расположение сегментов индикатора.

Для составления таблицы истинности возьмем последовательно числа от 0 до 5 в коде Грея (по числу микрокоманд yi).

1. Таблица истинности преобразователя кода.

Таблица 2.6.

N10	Код Грея	Сегменты
	Q1	Q2	Q3	a	b	c	d	e	f	g
0	0	0	0	1	1	1	1	1	1	0
1	0	0	0	1	1	0	0	0	0	0
2	0	1	1	1	0	1	1	0	1	1
3	0	1	0	1	1	1	0	0	1	1
4	1	1	0	1	1	0	0	1	0	1
5	1	1	1	0	1	1	0	1	1	1

2. Минимизированные логические выражения в базисе И-НЕ}

a	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	1	1	1
1	x	x	0	1

b	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	1	0	1
1	x	x	1	1

c	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	0	1	1
1	x	x	1	0

d	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	0	1	0
1	x	x	0	0

e	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	0	0	0
1	x	x	1	1

f	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	1	0	1	1
1	x	x	1	0

g	Q2Q3
Q1	0 0	0 1	1 1	1 0
0	0	0	1	1
1	x	x	1	1

3. Схемная реализация

Рис. 2.8. Схема преобразователя кода Грея в семисегментный код

2.4 Разработка цифровой линии задержки (таймера)

Таймер выполняет функции управляемой кодом цифровой линии задержки (ЦЛЗ): задерживает импульс на временной интервал, пропорциональный заданному коду. Подобную ЦЛЗ можно построить на базе счетчика импульсов с принудительной установкой (рис.2.9).

Рис. 2.9. Цифровая линия задержки (таймер).

В момент подачи рабочего импульса на управляющий вход V счетчика СТ в него заносится число N0 по информационным входам D1, D2, D3, D4. Одновременно рабочий импульс f от генератора прямоугольных импульсов ГПИ в схеме на рис.2.4. взводит RS-триггер таким образом, что конъюнктор открывается и начинает пропускать высокочастотные импульсы F=1/T0 на счетный вход счетчика С. В момент переполнения последнего появляется сигнал t, который опрокидывает RSтриггер и запирает конъюнктор. Следовательно, на счетчик проходит число импульсов, равное (Nmax +1) - N0, где Nmax емкость счетчика (максимально набираемое им число). Таким образом, задержка сигнала (от момента подачи рабочего импульса на вход V до момента появления импульса t на выходе счетчика) зависит от исходного числа N0. Назначение шифратора CD -- трансформировать входную информацию (сигналы y1, y3, y4, y6) в соответствующее число N0, определяемое заданием. Для составления таблицы истинности шифратора возьмем последовательно числа N0 от 0 до 3 (по числу микрокоманд yi с временным условием ti).

1. Таблица истинности шифратора.

Таблица 2.7.

N0	Входы	Выходы
	x3	x2	x1	x0	К1	К0
0	0	0	0	1	0	0
1	0	0	1	0	0	1
2	0	1	0	0	1	0
3	1	0	0	0	1	1

Функции выходов шифратора:

K0=x0 v x1; K1=x2 v x3;

2. Схемная реализация.

Рис. 2.10. Схема шифратора.

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

1. Теория автоматов: учебно-методический комплекс / сост. Г.И. Анкудинов, И.В. Иванова. -- СПб.: Изд-во СЗТУ, 2008. -- 227 с.

2. Анкудинов Г.И., Анкудинов И.Г., Хамидуллин P.P. Теория автоматов: Учеб. пособие,- СПб.: СЗТУ. 2002. - 112 с.

3. ГОСТ 2.001-93 ЕСКД. Общие положения;

4. ГОСТ 2.051-2006 ЕСКД. Электронные документы. Общие положения;

Размещено на Allbest.ru