Синтез микропрограммного управляющего автомата
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-триггеры. Для этого сначала выпишем матрицу М - матрицу всех возможных переходов автомата.