Автор: Пользователь скрыл имя, 04 Марта 2013 в 13:55, курсовая работа
Потребность в вычислениях возникла у людей на самых ранних стадиях развития человеческого общества. Причем с самого начала для облегчения счета люди использовали различные приспособления. Многие из них были весьма интересными и остроумными по принципу действия, но все они обязательно требовали, чтобы в процессе вычислений активно участвовал человек-оператор. Качественно новый этап развития вычислительной техники наступил с изобретением и созданием электронных вычислительных машин, которые работают автоматически, без участия человека, в соответствии с заранее заданной программой.
2. Упорядочим строки матрицы , для чего построим матрицу следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим весом р(a,b). В нашем случаи все пары имеют одинаковый для всех пар вес р(a,b)=1. Из всех пар, имеющих общий компонент с парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицы . Ясно, что {a,b}×{g,d}¹0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д.. В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(a) компонента a называется число появлений a в матрице ) и в матрицу заносится пара с наибольшей суммой весов.
Для определения того, какая пара займет второе место в матрице находим веса компонентов пар
1 |
2 |
1 |
р( |
1 |
)= |
3 |
р( |
2 |
)= |
3 |
р(1)+р(2)= |
6 | |||||
2 |
5 |
1 |
р( |
2 |
)= |
3 |
р( |
5 |
)= |
3 |
р(2)+р(5)= |
6 | |||||
2 |
7 |
1 |
р( |
2 |
)= |
3 |
р( |
7 |
)= |
2 |
р(2)+р(7)= |
5 | |||||
3 |
4 |
1 |
р( |
3 |
)= |
2 |
р( |
4 |
)= |
4 |
р(3)+р(4)= |
6 | |||||
4 |
5 |
1 |
р( |
4 |
)= |
4 |
р( |
5 |
)= |
3 |
р(4)+р(5)= |
7 | |||||
4 |
6 |
1 |
р( |
4 |
)= |
4 |
р( |
6 |
)= |
4 |
р(4)+р(6)= |
8 | |||||
5 |
6 |
1 |
р( |
5 |
)= |
3 |
р( |
6 |
)= |
4 |
р(5)+р(6)= |
7 | |||||
6 |
8 |
1 |
р( |
6 |
)= |
4 |
р( |
8 |
)= |
2 |
р(6)+р(8)= |
6 | |||||
6 |
9 |
1 |
р( |
6 |
)= |
4 |
р( |
9 |
)= |
3 |
р(6)+р(9)= |
7 | |||||
7 |
9 |
1 |
р( |
7 |
)= |
2 |
р( |
9 |
)= |
3 |
р(7)+р(9)= |
5 | |||||
8 |
10 |
1 |
р( |
8 |
)= |
2 |
р( |
10 |
)= |
4 |
р(8)+р(10)= |
6 | |||||
9 |
11 |
1 |
р( |
9 |
)= |
3 |
р( |
11 |
)= |
4 |
р(9)+р(11)= |
7 | |||||
10 |
3 |
1 |
р( |
10 |
)= |
4 |
р( |
3 |
)= |
2 |
р(10)+р(3)= |
6 | |||||
10 |
11 |
1 |
р( |
10 |
)= |
4 |
р( |
11 |
)= |
4 |
р(10)+р(11)= |
8 | |||||
10 |
12 |
1 |
р( |
10 |
)= |
4 |
р( |
12 |
)= |
4 |
р(10)+р(12)= |
8 | |||||
11 |
12 |
1 |
р( |
11 |
)= |
4 |
р( |
12 |
)= |
4 |
р(11)+р(12)= |
8 | |||||
T |
= |
11 |
13 |
1 |
р( |
11 |
)= |
4 |
р( |
13 |
)= |
2 |
р(11)+р(13)= |
6 | |||
12 |
4 |
1 |
р( |
12 |
)= |
4 |
р( |
4 |
)= |
4 |
р(12)+р(4)= |
8 | |||||
12 |
16 |
1 |
р( |
12 |
)= |
4 |
р( |
16 |
)= |
3 |
р(12)+р(16)= |
7 | |||||
13 |
16 |
1 |
р( |
13 |
)= |
2 |
р( |
16 |
)= |
3 |
р(13)+р(16)= |
5 | |||||
14 |
15 |
1 |
р( |
14 |
)= |
2 |
р( |
15 |
)= |
5 |
р(14)+р(15)= |
7 | |||||
15 |
17 |
1 |
р( |
15 |
)= |
5 |
р( |
17 |
)= |
4 |
р(15)+р(17)= |
9 | |||||
15 |
18 |
1 |
р( |
15 |
)= |
5 |
р( |
18 |
)= |
4 |
р(15)+р(18)= |
9 | |||||
15 |
20 |
1 |
р( |
15 |
)= |
5 |
р( |
20 |
)= |
2 |
р(15)+р(20)= |
7 | |||||
16 |
17 |
1 |
р( |
16 |
)= |
3 |
р( |
17 |
)= |
4 |
р(16)+р(17)= |
7 | |||||
17 |
18 |
1 |
р( |
17 |
)= |
4 |
р( |
18 |
)= |
4 |
р(17)+р(18)= |
8 | |||||
17 |
19 |
1 |
р( |
17 |
)= |
4 |
р( |
19 |
)= |
2 |
р(17)+р(19)= |
6 | |||||
18 |
21 |
1 |
р( |
18 |
)= |
4 |
р( |
21 |
)= |
3 |
р(18)+р(21)= |
7 | |||||
18 |
22 |
1 |
р( |
18 |
)= |
4 |
р( |
22 |
)= |
5 |
р(18)+р(22)= |
9 | |||||
19 |
21 |
1 |
р( |
19 |
)= |
2 |
р( |
21 |
)= |
3 |
р(19)+р(21)= |
5 | |||||
20 |
22 |
1 |
р( |
20 |
)= |
2 |
р( |
22 |
)= |
5 |
р(20)+р(22)= |
7 | |||||
21 |
23 |
1 |
р( |
21 |
)= |
3 |
р( |
23 |
)= |
3 |
р(21)+р(23)= |
6 | |||||
22 |
1 |
1 |
р( |
22 |
)= |
5 |
р( |
1 |
)= |
4 |
р(22)+р(1)= |
9 | |||||
22 |
14 |
1 |
р( |
22 |
)= |
5 |
р( |
14 |
)= |
2 |
р(22)+р(14)= |
7 | |||||
22 |
24 |
1 |
р( |
22 |
)= |
5 |
р( |
24 |
)= |
4 |
р(22)+р(24)= |
9 | |||||
23 |
1 |
1 |
р( |
23 |
)= |
3 |
р( |
1 |
)= |
4 |
р(23)+р(1)= |
7 | |||||
23 |
24 |
1 |
р( |
23 |
)= |
3 |
р( |
24 |
)= |
4 |
р(23)+р(24)= |
7 | |||||
24 |
15 |
1 |
р( |
24 |
)= |
4 |
р( |
15 |
)= |
5 |
р(24)+р(15)= |
9 | |||||
24 |
1 |
1 |
р( |
24 |
)= |
4 |
р( |
1 |
)= |
4 |
р(24)+р(1)= |
8 |
Исходя из весов компонентов пар строим матрицу ||M|| и матрицу ||M’|| для кодирования.
15 |
17 |
1 |
9 |
15 |
17 |
1 |
9 | |||||
15 |
18 |
1 |
9 |
15 |
18 |
1 |
9 | |||||
18 |
22 |
1 |
9 |
18 |
22 |
1 |
9 | |||||
22 |
1 |
1 |
9 |
22 |
1 |
1 |
9 | |||||
22 |
24 |
1 |
9 |
22 |
24 |
1 |
9 | |||||
24 |
15 |
1 |
9 |
24 |
15 |
1 |
9 | |||||
17 |
18 |
1 |
8 |
17 |
18 |
1 |
8 | |||||
24 |
1 |
1 |
8 |
24 |
1 |
1 |
8 | |||||
4 |
6 |
1 |
8 |
14 |
15 |
1 |
7 | |||||
12 |
4 |
1 |
8 |
15 |
20 |
1 |
7 | |||||
10 |
12 |
1 |
8 |
16 |
17 |
1 |
7 | |||||
10 |
11 |
1 |
8 |
18 |
21 |
1 |
7 | |||||
11 |
12 |
1 |
8 |
20 |
22 |
1 |
7 | |||||
14 |
15 |
1 |
7 |
22 |
14 |
1 |
7 | |||||
15 |
20 |
1 |
7 |
23 |
1 |
1 |
7 | |||||
16 |
17 |
1 |
7 |
23 |
24 |
1 |
7 | |||||
M |
= |
18 |
21 |
1 |
7 |
M' |
= |
1 |
2 |
1 |
6 | |
20 |
22 |
1 |
7 |
2 |
5 |
1 |
6 | |||||
22 |
14 |
1 |
7 |
4 |
5 |
1 |
7 | |||||
23 |
1 |
1 |
7 |
4 |
6 |
1 |
8 | |||||
23 |
24 |
1 |
7 |
12 |
4 |
1 |
8 | |||||
4 |
5 |
1 |
7 |
10 |
12 |
1 |
8 | |||||
5 |
6 |
1 |
7 |
10 |
11 |
1 |
8 | |||||
6 |
9 |
1 |
7 |
11 |
12 |
1 |
8 | |||||
9 |
11 |
1 |
7 |
5 |
6 |
1 |
7 | |||||
12 |
16 |
1 |
7 |
6 |
9 |
1 |
7 | |||||
1 |
2 |
1 |
6 |
9 |
11 |
1 |
7 | |||||
2 |
5 |
1 |
6 |
12 |
16 |
1 |
7 | |||||
3 |
4 |
1 |
6 |
3 |
4 |
1 |
6 | |||||
6 |
8 |
1 |
6 |
6 |
8 |
1 |
6 | |||||
8 |
10 |
1 |
6 |
8 |
10 |
1 |
6 | |||||
10 |
3 |
1 |
6 |
10 |
3 |
1 |
6 | |||||
11 |
13 |
1 |
6 |
11 |
13 |
1 |
6 | |||||
17 |
19 |
1 |
6 |
17 |
19 |
1 |
6 | |||||
21 |
23 |
1 |
6 |
21 |
23 |
1 |
6 | |||||
2 |
7 |
1 |
5 |
2 |
7 |
1 |
5 | |||||
7 |
9 |
1 |
5 |
7 |
9 |
1 |
5 | |||||
13 |
16 |
1 |
5 |
13 |
16 |
1 |
5 | |||||
19 |
21 |
1 |
5 |
19 |
21 |
1 |
5 |
3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=24. Тогда
R = ]log2M[ = ]log224[ =5.
Закодируем состояния начиная из первой строки матрицы ||M'||. Кодируем внутренние состояния автомата, используя для этого карту Карно (рис.5) и по возможности метод соседнего кодирования.
|
000 |
001 |
010 |
011 |
110 |
111 |
100 |
101 | |||||||
00 |
a15 |
a18 |
a22 |
a12 |
a10 |
a11 |
|||||||||
01 |
a17 |
a24 |
a1 |
a2 |
a4 |
a9 |
a19 | ||||||||
11 |
a20 |
a14 |
a23 |
a5 |
a6 |
a8 |
|||||||||
10 |
a16 |
a21 |
a13 |
a7 |
a3 |
||||||||||
a1 |
- |
01010 |
a13 |
- |
10010 | ||||||||||
a2 |
- |
01011 |
a14 |
- |
11001 | ||||||||||
a3 |
- |
10110 |
a15 |
- |
00000 | ||||||||||
a4 |
- |
01110 |
a16 |
- |
10000 | ||||||||||
a5 |
- |
11011 |
a17 |
- |
01000 | ||||||||||
a6 |
- |
11110 |
a18 |
- |
00001 | ||||||||||
a7 |
- |
10011 |
a19 |
- |
01101 | ||||||||||
a8 |
- |
11111 |
a20 |
- |
11000 | ||||||||||
a9 |
- |
01111 |
a21 |
- |
10001 | ||||||||||
a10 |
- |
00110 |
a22 |
- |
00010 | ||||||||||
a11 |
- |
00111 |
a23 |
- |
11010 | ||||||||||
a12 |
- |
00011 |
a24 |
- |
01001 | ||||||||||
Строим прямую структурную таблицу переходов-выходов автомата Мили (табл.15 ). В данной таблице в столбцах k(am) и k(as) указывается код исходного состояния и состояния перехода соответственно. В столбце функций возбуждения ФВ указывается те значения функций возбуждения, которые на данном переходе обязательно равны 1. Остальные (т.е. равные 0 или принимающие неопределенные значения) не указываются. Это эквивалентно тому, что всем неопределенным значениям функций возбуждения приписывается значение 0, что в общем случае не дает минимальной функции, однако в реальных автоматах минимизация обычно не делается в виду ее неэффективности. Предлагается самостоятельно построить структурную таблицу переходов с указанием всех значений функций возбуждения (в том числе и неопределенных), выполнить минимизацию и сравнить результаты с приведенными ниже.
Таблица 15
Прямая структурная таблица переходов-выходов автомата Мили.
Am |
К(Am) |
As |
К(As) |
X |
Y |
ФВ |
а1 |
01010 |
а2 |
01011 |
1 |
S5 | |
а2 |
01011 |
а5 |
11011 |
S1 | ||
01011 |
а7 |
10011 |
S1,R2 | |||
а3 |
10110 |
а4 |
01110 |
1 |
R1,S2 | |
а4 |
01110 |
а5 |
11011 |
S1,R3,S5 | ||
01110 |
а6 |
11110 |
S1 | |||
а5 |
11011 |
а6 |
11110 |
1 |
S3 | |
а6 |
11110 |
а8 |
11111 |
S5 | ||
11110 |
а9 |
01111 |
R1,S5 | |||
а7 |
10011 |
а9 |
01111 |
1 |
R1,S2,S3 | |
а8 |
11111 |
а10 |
00110 |
1 |
R1,R2,R5 | |
а9 |
01111 |
а11 |
00111 |
1 |
S2 | |
а10 |
00110 |
а3 |
10110 |
S1 | ||
00110 |
а11 |
00111 |
S5 | |||
00110 |
а12 |
00011 |
R3,S5 | |||
а11 |
00111 |
а12 |
00011 |
R3 | ||
00111 |
а13 |
10010 |
S1,R3,R5 | |||
а12 |
00011 |
а4 |
01110 |
S2,S3,R5 | ||
00011 |
а16 |
10000 |
S1,R4,R5 | |||
а13 |
10010 |
а16 |
10000 |
1 |
R4 | |
а14 |
11001 |
а15 |
00000 |
1 |
R1,R2,R5 | |
а15 |
00000 |
а17 |
01000 |
S2 | ||
00000 |
а18 |
00001 |
S5 | |||
00000 |
а20 |
11000 |
S1,S2 | |||
а16 |
10000 |
а17 |
01000 |
1 |
R1,S2 | |
а17 |
01000 |
а18 |
00001 |
R2,S5 | ||
01000 |
а19 |
01101 |
S3,S5 | |||
а18 |
00001 |
а21 |
10001 |
S1 | ||
00001 |
а22 |
00010 |
S4,R5 | |||
а19 |
01101 |
а21 |
10001 |
1 |
S1,R2,R3 | |
а20 |
11000 |
а22 |
00010 |
1 |
R1,R2,S4 | |
а21 |
10001 |
а23 |
11010 |
1 |
S2,S4,R5 | |
а22 |
00010 |
а1 |
01010 |
S2 | ||
00010 |
а14 |
11001 |
S1,S2,R4,S5 | |||
00010 |
а24 |
01001 |
S2,R4,S5 | |||
а23 |
11010 |
а1 |
01010 |
R1 | ||
11010 |
а24 |
01001 |
R1,R4,S5 | |||
а24 |
01001 |
а15 |
00000 |
R2,R5 | ||
01001 |
а1 |
01010 |
- |
S4,R5 |
Для получения функций возбуждения
поступаем следующим образом.
Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:
Для получения функций выходов поступаем аналогично:
Для упрощения полученных выражений выполняем все возможные операции склеивания и поглощения:
Для построения функциональной схемы автомата по полученным выражениям необходимо либо заменить ai его значениями через Q1Q2Q3 либо получить сигнал, соответствующий ai. Обычно используют второй способ и для получения сигнала ai применяют так называемый дешифратор состояний, на вход которого поступают сигналы с выходов элементов памяти Q1Q2Q3. Кроме того, при построении схемы стараются выделить общие части, встречающиеся в функциях возбуждения или выходных сигналах. В этом случае окончательная система уравнений, по которым строится схема, будет иметь вид:
Подадим полученные выражения согласно с заданным базисом ИЛИ-НЕ.
Принципиальная схема автомата Мили построенная на основании полученных уравнений, представлена на листе формата А1 шифр ТОП.00.00.01.
СИНТЕЗ АВТОМАТА МУРА.
Для автомата Мура на этапе получения отмеченной ГСА разметка производится согласно следующим правилам:
1) символом а1 отмечается начальная и конечная вершины;
2) различные операторные вершины отмечаются различными символами;
3) все операторные вершины должны быть отмечены;
ГСА, отмеченной для автомата Мура, представлен на рис. 5 (Приложение 3).
Таблица переходов-выходов автомата Мура представлены в табл. 16 (прямая). Обычно для автомата Мура в таблице переходов-выходов дополнительный столбец для выходных сигналов не используется и выходной сигнал записывается в столбце, где указывается исходное состояние am или состояния перехода aS.