Xreferat.com » Рефераты по информатике и программированию » Синтез микропрограммного управляющего автомата

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

BORDERCOLOR="#000000" CELLPADDING=8 CELLSPACING=0>

As

a0

a1

a2

a3

a4

a5

a6

a7

a8

A9

K{as}

0001

0011

0010

0110

1100

0100

0101

1001

1000

0000


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


7.4 Получение логических выражений для функций возбуждения D-триггеров


Логические выражения для каждой функции возбуждения D-триггера получают по таблице как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения.

D1= a3x2va6va7x6va8x7

D2= a2x1va3x2va4va5va7x6

D3= a0x1va1x2va2

D4= a0va5va6va8x7x8va9x9

Аналогично составляются логические выражения для функций выходов.

y1= a0x1va1x2va3x2

y2= a0x1va2x1

y3= a0x1va1x2va3x2x3va3x2

y4= a1x2va4x4va5x5

y5= a6

y6= a1x2va4x4

y7= a8x7

y8=a9x9

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

m=a1x2va4x4

n=a0x1

k=nva1x2va3x2

p=a8x7

q=a2x1

r=a3x2


D1= r v y5 v a7x6 v y7

D2= q v r v a4 v a5 v a7x6

D3= n v y6 v a2

D4= a0 v a5 v y5 v a8x7x8 v a9x9

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

y1= k

y2= n v q

y3= k v rx3

y4= m v a5x5

y5= a6

y6= m

y7= p

y8=a9x9

Цена комбинационной схемы по Квайну для автомата Мили, с использованием в качестве элементов памяти D-триггеров, равна С=59, причем в схеме предполагается использовать 4-входовой дешифратор.

7.5 Кодирование на RS- триггерах


Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Но при использовании RS-триггеров придется перекодировать состояния автомата, кодирование осуществим способом минимизирующим число переключений элементов памяти.


Для этого сначала выпишем матрицу M - матрицу всех возможных переходов автомата. Состояниям автомата a0 и a1 присвоим коды: К(a0)=0000, К(a1)=0001. Далее из матрицы М составим подматрицу M2, в которую запишем переходы из 2 состояния. В множество В2 выпишем коды уже закодированных состояний, а в множество C1 коды с кодовым расстоянием "1" от кодов В2. Закодировав состояние a2, выпишем матрицу М3 для кодирования следующего состояния автомата. Кодирование состояния a3 аналогично a2, причем для определения наиболее выгодного кода будем находить суммы кодовых расстояний между множествами Вi и Di. Код с наименьшей суммой и является наиболее оптимальным, когда все суммы получились одинаковыми выбираем любой код и кодируем это состояние.


00 k0=0000

01 k1=0001

12

19 12 B2 ={0001}

22 M2= 22 C1={0011,0101,1001}

M= 23 23 D2={0011,0101,1001}

34 W0011=1

39 W0101=1

45 W1001=1

56 k2=0011

67

78

80

88

89

99

23 B3={0011}

M3= 34 C2={0010,0111,1011}

39 D3={0010,0111,1011}

W0010=1

W0111=1

W1011=1

k3=0010



34 B4={0 010}

M4= 45 C3={0110,1010}

D4={0110,1010}

W0110=1

W1010=1

k4=0110


45 B5={0110}

M5= 56 C4={0100,0111,1110}

75 D5={0100,0111,1110}

W0100=1

W0111=1

W1110=1

k5=0111

56 B6={0111}

M6= 67 C5={0101,1111)}

D6={0101,1111)}

W0101=1

W1111=1

k6=0101


67 B7={0111,0101}

M7= 75 C5={1111}

78 C6={0100,1101}

D7={1111,0100,1101}

W1111=1111-01112+1111-01012=1+2=3

W0100=0100-01112+0100-01012=2+1=3

W1101=1101-01112+1101-01012=2+1=3

k7=0100


78 B8={0000,0100}

M8= 80 C0={1000}

88 C7={1100}

89 D8={1000,1100}

W1100=1100-00002+1100-01002=2+1=3

W1000=1000-00002+1000-01002=1+2=3

k8=0100


19 B9={0000,0001,0010,1100}

39 C0={1000}

M9= 89 C1={1001} C3={1010}

90 C8={1000,1101,1110}

99 D9={1000,1001,1010,1101,1110}


DB

0000

0001

0010

1100

W

1000

1

2

2

1

6

1001

2

1

3

2

8

1010

2

3

1

2

8

1101

3

2

4

1

10

1110

3

4

2

1

10

k9=1000


Кодирования для RS-триггеров изображены в таблице 10.

Таблица 10

As

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

K{as}

0000

0001

0011

0010

0110

0111

0101

0100

1100

1000

7.6 Получение логических выражений для функций возбуждения RS-триггеров


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


Таблица 11. Прямая структурная таблица переходов и выходов автомата Мили.

Исходное состояние


Код am

Состояние перехода as


Код as

Входной сигнал X(am,as)

Выходные сигналы Y(am,as)

Функции возбуждения триггеров

RS

T

a0

0000

a0

a1

0000

0001

X1

X1

-

Y1(y1,y2,y3)


S4


T4

a1

0001

a2

a9

0011

1000

X2

X2

Y6(y4,y6)

Y9(y1,y3)

S3

S1R4

T3

T1T4

a2

0011

a2

a3

0011

0010

X1

X1

-

Y2(y2)


R4


T4

a3

0010

a4

a4

a9

0110

0110

1000

X2X3

X2X3

X2

-

Y3(y3)

Y9(y1,y3)

S2

S2

S1R3

T2

T2

T1T3

a4

0110

a5

a5

0111

0111

X4

X4

-

Y6(y4,y6)

S4

S4

T4

T4

a5

0111

a6

a6

0101

0101

X5

X5

-

Y4(y4)

R3

R3

T3

T3

a6

0101

a7

0100

1

Y5(y5)

R4

T4

a7

0100

a5

a8

0111

1100

X6

X6

-

-

R3R4

S1

T3T4

T1

a8

1100

a0

a8

a9

0000

1100

1000

X7X8

X7

X7X8

-

Y7(y7)

-

R1R2


R2

T1T2


T2

a9

1000

a0

a9

0000

1000

X9

X9

-

Y8(y8)

R1

T1

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

S1= a1x2 v a3x2 v a7x6

S2= a3x2

S3= a1x2

S4= a0x1 v a4

R1= a8x7x8 v a9x9

R2= a8x7

R3= a3x2 v a5 v a7x6

R4= a1x2 v a2x1 v a6 v a7x6

После упрощения и выделения общих частей, получим:

f= a1x2

g= a3x2

k= a7x6

m= a8x7

p= a3x2

q= a1x2

r= a0x1

h= a2x1

e= r v a1x2 v g

n= q v a4x4

S1= f v g v a7x6

S2= p

S3= q

S4= r v a4

R1= mx8 v a9x9

R2= m

R3= g v a5 v k

R4= f v h v a6 v k


y1= e

y2= r v h

y3= e v px3

y4= n v a5x5

y5= a6

y6= n

y7= a8x7

y8=a9x9


С использованием в качестве элементов памяти RS-триггеров, цена комбинационной схемы по Квайну для автомата Мили равна C=59 причем в схеме предполагается использовать 4-входовой дешифратор.

7.7 Кодирование на T-триггерах


В качестве элементов памяти возможно использование не только D-триггеров и RS-триггеров, а также используются T-триггеры. При использовании T-триггеров используется такая же кодировка, как и для RS-триггеров. Кодирования для T-триггеров изображены в таблице 10.


7.8 Получение логических выражений для функций возбуждения T-триггеров


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


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

T1= a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9

T2= a3x2 v a8x7

T3= a1x2 v a3x2 v a5 v a7x6

T4= a0x1 v a4 v a1x2 v a2x1 v a6 v a7x6


После упрощения и выделения общих частей, получим:

f= a1x2

g= a3x2

k= a7x6

m= a8x7

p= a3x2

q= a1x2

r= a0x1

h= a2x1

e= r v a1x2 v g

n= q v a4x4

i= r v h

T1= f v g v a7x6 v mx8 v a9x9

T2= p v m

T3= q v g v a5 v k

T4= i v a4 v f v a6 v k


y1= e

y2= i

y3= e v px3

y4= n v a5x5

y5= a6

y6= n

y7= a8x7

y8=a9x9


С использованием в качестве элементов памяти T-триггеров, цена комбинационной схемы по Квайну для автомата Мили равна C=61 причем в схеме предполагается использовать 4-входовой дешифратор.

7.9 Кодирование на счетчике


Для кодирования состояний автомата на счётчике необходимо, чтобы разность кодов между соседними состояниями составляла единицу. Данная кодировка представлена в таблице 12.


Таблица 12

As

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

K{as}

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001


7.10 Получение уравнений для счетчика


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


Таблица 13. Прямая структурная таблица переходов и выходов автомата Мили.

Исходное состояние


Код am

Состояние перехода as


Код as

Входной сигнал X(am,as)

Выходные сигналы Y(am,as)

Функции возбуждения

a0

0000

a0

a1

0000

0001

X1

X1

-

Y1(y1,y2,y3)


E+1

a1

0001

a2

a9

0010

1001

X2

X2

Y6(y4,y6)

Y9(y1,y3)

E+1

D1D8 M

a2

0010

a2

a3

0010

0011

X1

X1

-

Y2(y2)


E+1

a3

0011

a4

a4

a9

0100

0100

1001

X2X3

X2X3

X2

-

Y3(y3)

Y9(y1,y3)

E+1

E+1

D1D8 M

a4

0100

a5

a5

0101

0101

X4

X4

-

Y6(y4,y6)

E+1

E+1

a5

0101

a6

a6

0110

0110

X5

X5

-

Y4(y4)

E+1

E+1

a6

0110

a7

0111

1

Y5(y5)

E+1

a7

0111

a5

a8

0101

1000

X6

X6

-

-

D1D4 M

E+1

a8

1000

a0

a8

a9

0000

1000

1001

X7X8

X7

X7X8

-

Y7(y7)

-

M


E+1

a9

1001

a0

a9

0000

1001

X9

X9

-

Y8(y8)

M



M – вход управления записью / счётом в счётчике;

E+1 - вход управления прямым счётом;


Работа счётчика производится в соответствии с таблицей 14.

Таблица 14

М E+1 Режим

0

1

1

1

0

1

0

0

Запись в счётчик

Прямой счёт

Обратный счёт

Хранение


Из таблицы 13 получаются логические выражения для каждой функции возбуждения управляющего входа счётчика, а также для функций выходов как конъюнкции соответствующих исходных состояний am и входных сигналов, которые объединены знаками дизъюнкции для всех строк, содержащих данную функцию возбуждения или соответственно функцию выхода.


M = a1x2 v a3x2 v a7x6 v a8x7x8 v a9x9

E+1 = a0x1 v a1x2 v a2x1 v a3x2 v a4 v a5 v a6 v a7x6 v a8x7x8

D1 = a1x2 v a3x2 v a7x6

D4 = a7x6

D8 = a1x2 v a3x2


y1 = a0x1 v a1x2 v a3x2

y2 = a0x1 v a2x1

y3 = a0x1 v a1x2 v a3x2x3 v a3x2

y4 = a1x2 v a4x4 v a5x5

y5 = a6

y6 = a1x2 v a4x4

y7 = a8x7

y8 =a9x9


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


e=a1 v a3 d=x1(a0 v a2) f=a0x1

h=x2e g=a1x2 v a4x4 p=a8x7

r=f v h q=a7x6 n=h v q


M = n v px8 v a9x9

E+1 = d v x2e v a4 v a5 v a6 v a7x6 v px8

D1 = n

D4 = q

D8 = h


y1 = r

y2 = d

y3 = r v a3x2x3

y4 = g v a5x5

y5 = a6

y6 = g

y7 = a8x7

y8 =a9x9

Цена комбинационной схемы по Квайну составляет С=57.

Унитарный способ кодирования не может быть использован, так как n намного меньше N , где N наибольшее число ЭП (N=10), а n наименьшее число ЭП (n=log2 16).

Сравнивая относительно аппаратурных затрат варианты построения автомата Мили на RS, D, T- триггерах и на счетчике можно убедиться что цена логических выражений для функций возбуждения оказывается приблизительно равной: для RS цена - 59, для D цена – 59, для T цена 61, а для счетчика 57.


8 Синтез МПА в соответствии с моделью Мура


8.1 Построение графа автомата.


На основе отмеченной ГСА построен граф автомата Мура (рисунок 5).Граф автомата Мура имеет 11 вершин, соответствующих состояниям автомата b0,b1,...,b10, каждое из которых определяет наборы выходных сигналов, управляющего автомата, а дуги графа отмечены входными сигналами, действующими на данном переходе.


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


Из приведенного рисунка видно, что с увеличением количества состояний автомата наглядность графа теряется и больше удобств представляет табличный способ задания автомата.


Таблица 15. Прямая структурная таблица переходов и выходов автомата Мура.

Исходное состояние bm

Выходные сигналы

Код

bm

Состояние перехода bs

Код

bs

Входной сигнал

Функции возбуждения D-триггеров

b0

-


0001

b0

b1

0001

0111

X1

X1

D4

D2D3D4

b1

y1,y2,y3


0111

b2

b12

1110

0011

X2

X2

D1D2D3

D3D4

b2

y4,y6


1110

b3

b4

1010

0110

X1

X1

D1D3

D2D3

b3

-


1010

b3

b4

1010

0110

X1

X1

D1D3

D2D3

b4

y2


0110

b5

b6

b7

b8

b12

1100

0101

0010

0000

0011

X2X3

X2X3X4

X2X3X4X5

X2X3X4X5

X2

D1D2

D2D4

D3


D3D4

b5

y3


1100

b6

b7

b8

0101

0010

0000

X4

X4X5

X4X5

D2D4

D3


b6

y4,y6


0101

b7

b8

0010

0000

X5

X5

D3


b7

y4

0010

b8

0000

1


b8

y5


0000

b0

b7

b8

b9

b10

b11

0001

0010

0000

1001

0100

1000

X6X7X8

X6X5

X6X5

X6X7

X6X7X8X9

X6X7X8X9

D4

D3


D1D4

D2

D1

b9

y7


1001

b0

b9

b10

b11

0001

1001

0100

1000

X7X8

X7

X7X8X9

X7X8X9

D4

D1D4

D2

D1

b10

-


0100

b10

b11

0100

1000

X9

X9

D2

D1

b11

y8

1000

b0

0001

1

D4

b12

y1,y3


0011

b10

b11

0100

1000

X9

X9

D2

D1


8.3 Кодирование на D-триггерах


В таблице 15 представлена прямая структурная таблица переходов и выходов автомата Мура. Так как каждому состоянию автомата Мура соответствует свой набор выходных сигналов, то столбец выходных сигналов в таблице помещен следом за столбцом исходных состояний автомата. Проанализируем синтез автомата Мура на D-триггерах.

При кодировании состояний автомата, в качестве элементов памяти которого выбраны D-триггеры, следует стремиться использовать коды с меньшим числом "1" в кодовом слове. Для кодирования 13 состояний (b0, b1, ... , b12) необходимо 4 элемента памяти и из множества 4-разрядных двоичных слов надо выбрать код каждого состояния, ориентируясь на граф и таблицу переходов: чем чаще в какое-либо состояние происходят переходы из других состояний, то есть чем чаще оно встречается в столбце bs таблицы, тем меньше в коде этого состояния следует иметь "1". Для этого построим таблицу, в первой строке которой перечислены состояния, в которые есть более одного перехода, а во второй - состояния, из которых осуществляются эти переходы.


Таблица 16

bs

b0

b1

b2

b3

b4

b5

b6

B7

{bm}

b0b8b9b11

b0

b1

b2b3

b2b3

b4

b4b5

b4b5b6b8

bs

b8

b9

b10

b11

b12

{bm}

b4b5b6b7b8

b8b9

b8b9b10b12

b8b9b10b12

b1b4


Коды состояний автомата определим по выше описанному методу кодирования состояний при использовании D-триггеров.

Таблица 17

b

b0

b1

b2

b3

b4

b5

b6

K(b)

0001

0111

1110

1010

0110

1100

0101

b

b7

b8

b9

b10

b11

b12


K(b)

0010

0000

1001

0100

1000

0011



8.4 Получение логических выражений для функций возбуждения D-триггеров и функций выходов.


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


D1= b1x2 v b2x1 v b3x1 v b4x2 v b8x6x7 v b8x6x7x8x9 v b9x7 v b10x9 v b12x9

D2= b0x1 v b1x2 v b2x1 v b3x1 v b4x2(x3 v x3x4) v b5x4 v b8x6x7x8x9 v b9x7x8x9 v b10x9 v

v b12x9

D3= b0x1 v b1 v b2 v b3 v b4x2x3x4x5 v b4x2 v b5x4x5 v b6x5 v b8x6x4

D4= b0 v b1x2 v b4x2x3x4 v b4x2 v b5x4 v b8x6(x7x8 v x7) v b9(x7x8 v x7) v b11


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

y1= b1 v b12

y2= b1 v b4

y3= b1 v b5 v b12

y4= b2 v b6 v b7

y5= b8

y6= b2 v b6

y7= b9

y8=b11

Выделив общие части получаем:

d=b2 v b6

g=b0x1

h=b1x2

i=b4x2

j=x4x5

k=b4x2x3

m=b8x6

n=x7x8

r=b2 v b3

q=mvb9

D1= h v x1r v k v m(x7 v nx9) v b9x7 v b10x9 v b12x9

D2= g v h v x1r v i(x3 v x3x4) v b5x4 v nx9q v x9(b10 v b12)

D3= g v b1 v r v j(k v b5) v x5(b6 v b8x6)

D4= b0 v x2(b1 v b4) v x4(k v b5) v (x7x8 v x7)q v b11


y4= d v b7

y6= d


Цена комбинационной схемы по Квайну для автомата Мура, построенного на D-триггерах, равна С =109, причем в схеме предполагается использовать 4-входовой дешифратор.

8.5 Кодирование на RS-триггерах


Однако в качестве элементов памяти возможно использование не только D-триггеров, также используются RS-триггеры. Для этого сначала выпишем матрицу М - матрицу всех возможных переходов автомата.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: