Синтез цифровых автоматов

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

Министерство Образования Российской Федерации

Ижевский Государственный Технический Университет

Кафедра Вычислительной техники

Курсовая работа

по курсу «Теория цифровых автоматов»

Выполнил: студент группы 462

Шестаков И. В.

Проверил: преподаватель,

к.т.н. Кропачев Л.А.

Ижевск

2003

Содержание

Часть 1:

1. Расчет вариантов исходного задания

2. Преобразование алфавитного отображения к автоматному

3. Построение формализованного описания работы автомата

4. Минимизация числа внутренних состояний автомата

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

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

7. Синтез структурного автомата на элементах задержки

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

9. Определение функций выходов

10. Обоснование выбора элементов памяти

11. Введение синхронизации и установки автомата в начальное состояние

12. Получение функций автомата в требуемом базисе

13. Построение функциональной схемы автомата

14. Построение временных диаграмм работы автомата

Часть 2:

ВСТR

1. Построение содержательной ГСА

2. Кодирование ГСА

3. Разметка ГСА

4. Построение графа по ГСА

5. Кодирование состояний

6. Получение функций возбуждения и выходов

7. Синтез на ПЛМ

О

1. Построение содержательной ГСА

2. Кодирование ГСА

3. Разметка ГСА

4. Построение графа по ГСА

5. Кодирование состояний

6. Получение функций возбуждения и выходов

7. Синтез на ПЛМ

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

Часть 1

1. Расчет вариантов исходного задания

ь 1023 mod 2 = 1, будет производиться синтез автомата Мура;

ь 1023 mod 13 = 9, восемь входных слов начинаются со 9-ой строчки;

ь 1023 mod 23 = 11, восемь выходных слов начинаются с 11-ой строчки;

ь 1023 mod 5 = 3, синтез будет выполняться на логических элементах Шеффера;

ь 1023 mod 17 = 3, типы триггеров DV, RT, JK;

ь 1023 mod 73 = 1, будут синтезироваться микропрограммные автоматы для управления операциями: 06 BCTR

2. Преобразование алфавитного изображения к автоматному

Для выполнения 2-го требования автоматности выравниваем длины слов, вводя минимальное количество пустых букв.



Проверяем требование детерминированности. Рассмотрим начальные отрезки длиной 1. В 1-м, 4-м, 8-м словах на вход поступает буква .

Увеличим длину 1, 4, 8-го слов введением пустой буквы и получим:

Проверяем следующую входную букву. Во 2-м и 5-м словах на вход поступает .

Увеличим длину 2, 5, 6, 7-го слов введением пустой буквы и получим:

Рассмотрим начальные отрезки длиной 2 .

В 1-м, 4-м, 8-м на вход поступает отрезок .

Увеличим длину 1,7,8-го слов введением пустой буквы и получим.

В 6-м и 7-м словах на вход поступает начальный отрезок .

Увеличим длину 2-го слова введением пустой буквы и получим:

Остальные 2-у буквенные сочетания встречаются по одному разу. Начальные отрезки длиной 3,4,5 также не повторяются.

Окончательный вид автоматных отображений:

3. Построение формализованного описания работы автомата

автомат выход синхронизация кодированный

В начальном состоянии автомат находится в состоянии С0 . Пусть на вход поступает а1. Она переведет автомат в состояние С1. Проведем дугу из С0 в С1 и на дуге приписываем а1. Отметим вершину выходным сигналом В 2-ом отображении во 2-м такте поступает а2. Она переведет автомат в С2. Проводим дугу из С1 в С2, отмечаем вершину С2 буквой b1. В следующий такт на вход поступает а1 Выходная буква b3. Автомат перейдет в С3. В следующий такт на вход поступает. Выходная буква b2. Автомат перейдет в С4. 2-е отображение реализовано.

С буквы а1 начинается 5-е отображение. Аналогично со 2-м отображением переход из С0 в С1 под действием а1. В следующий такт в этом отображении поступит а3. Т.к. на выходе должна быть буква b1 , то автомат можно перевести в состояние С2. В следующий такт на входе ?. Автомат перейдет в С4. В следующий такт в этом отображении поступит также ?. Т.к. на выходе должна быть b1 , автомат можно перевести в состояние С2. 5-е отображение реализовано.

С буквы а1 начинается 6-е отображение. Аналогично со 2-м отображением переход из С0 в С1 под действием а1. В следующий такт в этом отображении поступает а1. На выходе. Автомат можно перевести в состояние С5 . В следующем такте автомат под действием перейдет в состояние С4, на выходе b2 Из С4 под действием в следующем такте автомат перейдет в С2, на выходе b1. 6-е отображение реализовано.

С буквы а1 начинается 7-е отображение. Первые два такта совпадают с 6-м отображением. В следующем такте автомат под действием а3 перейдет в состояние С3, на выходе b3 Из С3 под действием a2 в следующем такте автомат перейдет в С6, на выходе b3. Из С6 под действием ? в следующем такте автомат перейдет в С4, на выходе b2 . В следующем такте под действием автомат перейдет С2, на выходе b1. 7-е отображение реализовано.

С буквы а2 начинается 1-е отображение. В первый такт произойдет переход из С0 в С5 под действием а2, на выходе. В следующем такте автомат под действием а1 перейдет в состояние С7, на выходе ??Из С7 под действием ? в следующем такте автомат перейдет в С8, на выходе b2. Из С8 под действием ? в следующем такте автомат перейдет в С9, на выходе b2. В следующем такте автомат под действием перейдет в состояние С4, на выходе b2?1-е отображение реализовано.

С буквы а2 начинается 4-е отображение. Первые два такта совпадают с 1-м отображением. В следующем такте автомат под действием а3 перейдет в состояние С6, на выходе b3 Из С6 под действием а2 в следующем такте автомат перейдет в С10, на выходе b3. Из С10 под действием ? в следующем такте автомат перейдет в С2, на выходе b1 . В следующий такт автомат из С2 под действием перейдет в С4 , на выходе b2. 4-е отображение реализовано.

С буквы а2 начинается 8-е отображение. Первые два такта совпадают с 1-м отображением. В следующем такте автомат под действием а1 перейдет в состояние С11, на выходе b1 Из С11 под действием в следующем такте автомат перейдет в С12, на выходе b3. Т.к. выходная буква у состояния С0 не определена, то назначим этому состоянию b1 (переход из С12 в С0 под действием). Из состояния С0 под действием автомат переходит в С2 с выходной буквой b1. 8-е отображение реализовано.

С буквы а3 начинается 3-е отображение. Переход из С0 в С5 происходит под действием а3, на выходе ?. В следующий такт автомат из С5 под действием а2 перейдет в С8 , на выходе b2. В следующий такт автомат из С8 под действием а1 перейдет в С12, на выходе b3. 3-е отображение реализовано.

По графу составим таблицу переходов и выходов автомата (табл. 3.1).

Таблица 3.1:

	a1	a2	a3	?
C0	C1	C5	C5	C2	b1
C1	C5	C2	C2	-	?
C2	C3	-	-	C4	b1
C3	-	C6	-	C4	b3
C4	-	-	-	C2	b2
C5	C7	C8	C3	C4	?
C6	-	C10	-	C4	b3
C7	C11	-	C6	C8	?
C8	C12	-	-	C9	b2
C9	-		-	C4	b2
C10	-	-	-	C2	b3
C11	-	-	-	C12	b1
C12	-	-	-	C0	b3

Полученный граф автомата Мура изображен на рисунке 3.1.



Рисунок 3.1

Для проверки правильности построения графа автомата воспользуемся лентами отображения. Для этого будем подавать на автомат входные слова. Под действием каждой буквы автомат будет переходить в новое состояние и выдавать какую-то букву. Это состояние и букву запишем под проверяемой буквой. В результате под каждым входным словом получим выходное слово.

a2

a1

a3

a2

?

?

a3

a2

a1

a1

a1

a3

a2

?

?

a2

a1

a1

?

?

?

C0

C5

C7

C6

C10

C2

C4

C5

C8

C12

C1

C5

C3

C6

C4

C2

C5

C7

C11

C12

C0

C2

?

?

b3

b3

b1

b2

?

b2

b3

?

?

b3

b3

b2

b1

?

?

b1

b3

b1

b1

a1

a1

?

?

a1

a2

a1

?

a1

a3

?

?

a2

a1

?

?

?

С0

C1

C5

C4

C2

C1

C2

C3

C4

C1

C2

C4

C2

C5

C7

C8

C9

C4

?

?

b2

b1

?

b1

b3

b2

?

b1

b2

b1

?

?

b2

b2

b2

Как видно из лент отображения, автомат функционирует правильно.

4. Минимизация числа внутренних состояний автомата

Произведем разбиение состояний на группы. Автомат имеет 4 выходных состояния.

Подадим на вход a1:

b₁ b₂ b₃ b

С₀С₂С₁₁ С₄С₈С₉ С₃С₆С₁₀С₁₂ С₁С₅С₇

a₁ 1 3 - - 12 - - - - - 5 7 11

= = ===

~~~~ ~~

Первая и четвертая группы расщепляются на две.

Подадим на вход a2:



С₀С₁₁ С₂С₁₁ С₄С₈С₉ С₃С₆С₁₀С₁₂ С₁С₅ С₇

a₂ 5 - - - - - - 6 10 - - 2 8 -

=

~

Пятая группа расщепляется на две.

Подадим на вход а3 и:

С₀С₁₁ С₂С₁₁ С₄С₈С₉ С₃С₆С₁₀С₁₂ С₁ С₅ С₇

а₃ 5 - - - - - - - - - - 2 3 6

a 2 0 4 12 2 9 4 4 4 2 0 - 4 8

= = === ===

~ ~ ~ ~

Первые четыре группы расщепились.

С₀ С₁₁ С₂ С₁₁ С₄ С₈С₉ С₃С₆ С₁₀ С₁₂ С₁ С₅ С₇

a₁ 12 9 - -

a₂ - - 6 10

= ~~

a₃ - - - -

a 9 4

= ~

Пятая и шестая группы расщепляются на две. Группа С11 поглощается, так как уже такая есть. Больше расщеплений нет. Получилось 13 групп.

С₀ С₁₁ С₂ С₁₁ С₄ С₈С₉ С₃С₆ С₁₀ С₁₂ С₁ С₅ С₇

Таким образом, после минимизации автомата сохранилось то же количество внутренних состояний, что и до минимизации. Автомат не минимизировался, и у него остались те же состояния - С0, С1, С2, С3, С4, С5, С6, С7, С8, С9, С10, С11, С12.

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

Воспользуемся способом кодирования состояний по минимуму Хемингова расстояния. Построим матрицу пар переходов, имеющих место в кодируемом автомате.

Таблица 5.1

М =	С0С1
	С0С5
	С0С2
	С1С2
	С1С5
	С2С3
	С2С4
	С3С4
	С3С6
	С4С2
	С5С4
	С5С3
	С5С8
	С5С7
	С7С11
	С7С6
	С6С10
	С6С4
	С7С8
	С8С12
	С8С9
	С9С4
	С10С2
	С11С12
	С12С0

Матрица составлена таким образом, что хотя бы один индекс состояния в каждой строке встречался в какой-нибудь строке, расположенной выше. Автомат имеет 13 внутренних состояний, поэтому необходимы 4 элемента памяти и код состояний будет иметь 4 разряда. Закодируем С0 как 0000, а С1 как 0001. Нанесем эти значения на карту Вейча (таб. 5.2).

Таблица 5.2

C0	C1	C8	C5
C6	C2	C4	C3
	C10	С9	С11
С12			С7

Таблица 5.3:

М5 =	С0С5
	С1С5
	С5С4
	С5С3
	С5С3
	С5С3

Во второй строке не закодировано состояние С5.

Построим подматрицу М5 (таблица 5.3). В ней ранее закодировано только состояния С0 и С1, код которых 0000 и 0001 соответственно. Тогда множество уже закодированных состояний D = {0000, 0001}. Найдем по карте Вейча соседние незанятые клетки для этих состояний. Коды этих клеток запишем в множества E0000 и E0001 соответственно.

E0000 = {1000, 0100, 0010}

E0001 = {1001, 0101, 0011}

Из этих множеств составим множество F = {1000, 0100, 0010, 1001, 0101, 0011}

Найдем кодовые расстояния между каждым элементом G и элементами 0000 и 0001.

W0100 = {0100, 0000} + {0100, 0001} = 1+2=3

W0010 = {0010, 0000} + {0010, 0001} = 1+2=3

W0101 = {0101, 0000} + {0101, 0001} = 2+1=3

W1000 = {1000, 0000} + {1000, 0001} = 1+2=3

W0011 = {0011, 0000} + {0011, 0001} = 2+1=3

W1001 = {1001, 0000} + {1001, 0001} = 2+1=3

Все кодовые расстояния равны, поэтому С5 можно закодировать любым из представленных шести кодов. Пусть код С5 равен 0010. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С0С2. В этой строке не закодировано состояние С2. Составим подматрицу М2 (таблица 5.4). В ней ранее закодированы состояния С0 и С1, т.е. D = {0000, 0001}.

E0000 = {0100, 1000}

E0001 = {0101, 1001, 0011}

F = {0100, 1000, 1001, 0011, 0101}

W0100 = {0100, 0000} + {0100, 0001} = 1+2=3

W0101 = {0101, 0000} + {0101, 0001} = 2+1=3

W1000 = {1000, 0000} + {1000, 0001} = 1+2=3

W0011 = {0011, 0000} + {0011, 0001} = 2+1=3

W1001 = {1001, 0000} + {1001, 0001} = 2+1=3

Таблица 5.4

М2 =	С0С2
	С1С2
	С2С4
	С2С3

Все кодовые расстояния равны, поэтому С2 можно закодировать любым из представленных пяти кодов. Пусть код С2 равен 0101. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С2С3. В этой строке не закодировано состояние С3. Составим подматрицу М3 (таблица 5.5). В ней ранее закодированы состояния С2 и С5, т.е. D = {0101, 0010}.

E0101 = {0100, 1101, 0111}

E0010 = {0011, 0110, 1010}

F = {0011, 0110, 1010, 0100, 1101, 0111}

W0011 = {0011, 0101} + {0011, 0010} = 2+1=3

W0100 = {0100, 0101} + {0100, 0010} = 1+2=3

W0110 = {0110, 0101} + {0110, 0010} = 2+1=3

W0111 = {0111, 0101} + {0111, 0010} = 1+2=3

W1010 = {1010, 0101} + {1010, 0010} = 4+1=5

W1101 = {1101, 0101} + {1101, 0010} = 1+4=5

Таблица 5.5:

М3 =	С2С3
	С3С4
	С3С6
	С5С3

С3 нужно закодировать минимальным из представленных пяти кодов. Пусть код С3 равен 0110. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С2С4. В этой строке не закодировано состояние С4. Составим подматрицу М4 (таблица 5.6). В ней ранее закодированы состояния С2, С3 и С5, т.е. D = {0101, 0110, 0010}.

E0101 = {0100, 1101, 0111}

E0110 = {0100, 1110, 0111}

E0010 = {0011, 1010}

F = {0011, 0100, 0111, 1010, 1101, 1110}

W0011 = 2·{0011, 0101} + {0011, 0110} + {0011, 0010} = 4+2+1=7

W0100 = 2·{0100, 0101} + {0100, 0110} + {0100, 0010} = 2+1+2=5

W0111 = 2·{0111, 0101} + {0111, 0110} + {0111, 0010} = 2+1+2=5

W1010 = 2·{1010, 0101} + {1010, 0110} + {1010, 0010} = 8+2+1=11

W1101 = 2·{1101, 0101} + {1101, 0110} + {1101, 0010} = 2+3+4=9

W1110 = 2·{1110, 0101} + {1110, 0110} + {1110, 0010} = 6+1+2=9

Таблица 5.6:

М4 =	С2С4
	С3С4
	С4С2
	С5С4
	С9С4

С4 нужно закодировать минимальным из представленных пяти кодов. Пусть код С4 равен 0111. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С3С6. В этой строке не закодировано состояние С6. Составим подматрицу М6 (таблица 5.7). В ней ранее закодированы состояния С3 и С4, т.е. D = {0110, 0111}.

E0110 = {0100, 1110}

E0111 = {0011, 1111}

F = {0011, 0100, 1110, 1111}

W0011 = {0011, 0110} + {0011, 0111} = 2+1=3

W0100 = {0100, 0110} + {0100, 0111} = 1+2=3

W1110 = {1110, 0110} + {1110, 0111} = 1+2=3

W1111 = {1111, 0110} + {1111, 0111} = 2+3=5

Таблица 5.7

М3 =	С3С6
	С6С10
	С6С4
	С7С6

С6 нужно закодировать минимальным из представленных четырех кодов. Пусть код С6 равен 0100. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С6С10. В этой строке не закодировано состояние С10. Составим подматрицу М10 (таблица 5.8). В ней ранее закодированы состояния С6 и С2, т.е. D = {0100, 0101}.

E0100 = {1100}

E0101 = {1101}

F = {1100, 1101}

W1100 = {1100, 0100} + {1100, 0101} = 1+2=3

W1101 = {1101, 0100} + {1101, 0101} = 2+1=3

Таблица 5.8:

М10 =	С6С10
	С10С2

Все кодовые расстояния равны, поэтому С10 можно закодировать любым из представленных двух кодов. Пусть код С5 равен 1101. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С5С8. В этой строке не закодировано состояние С8. Составим подматрицу М8 (таблица 5.9). В ней ранее закодированы состояния С5, т.е. D = {0010}.

E0010 = {0011, 1010}

F = {0011, 1010}

W0011 = {0011, 0010} = 1

W1010 = {1010, 0010} = 1

Таблица 5.9:

М8 =	С5С8
	С7С8
	С8С12
	С8С12

Все кодовые расстояния равны, поэтому С8 можно закодировать любым из представленных двух кодов. Пусть код С8 равен 0011. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С5C7. В этой строке не закодировано состояние С7. Составим подматрицу М7 (таблица 5.10). В ней ранее закодированы состояния С5, C6 и С8, т.е. D = {0010, 0100, 0011}.

E0010 = {1010}

E0100 = {1100}

E0011 = {1011}

F = {1010, 1100, 1011}

W1010 = {1010, 0010} + {1010, 0011} + {1010, 0100} = 1+2+3=6

W1100 = {1100, 0010} + {1100, 0011} + {1100, 0100} = 2+1+4=7

W1011 = {1011, 0010} + {1011, 0011} + {1011, 0100} = 3+4+1=8

Таблица 5.10

М7 =	С5С7
	С7С11
	С7С6
	С7С8

С7 нужно закодировать минимальным из представленных трех кодов. Пусть код С7 равен 1010. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С7C11. В этой строке не закодировано состояние С11. Составим подматрицу М11 (таблица 5.11). В ней ранее закодированы состояния С7, т.е. D = {1010}.

E1010 = {1010}

F = {1011, 1110, 1000}

W1011 = {1011, 1010} = 1

W1110 = {1110, 1010} = 1

W1000 = {1000, 1010} = 1

Таблица 5.11:

М11 =	С7С11
	С11С12

С11 нужно закодировать минимальным из представленных трех кодов. Пусть код С11 равен 1110. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С8C12. В этой строке не закодировано состояние С12. Составим подматрицу М12 (таблица 5.12). В ней ранее закодированы состояния С8, С11, С0, т.е. D = {0000, 0011, 1110}.

E0000 = {1000}

E0011 = {1011}

E1110 = {1111, 1100}

F = {1000, 1011, 1111, 1100}

W1000 = {1000, 0000} + {1000, 0011} + {1000, 1110} = 1+3+2=6

W1011 = {1011, 0000} + {1011, 0011} + {1011, 1110} = 3+1+2=6

W1111 = {1111, 0000} + {1111, 0011} + {1111, 1110} = 4+2+1=7

W1100 = {1100, 0000} + {1100, 0011} + {1100, 1110} = 2+4+1=7

Таблица 5.12

М12 =	С8С12
	С11С12
	С12С0

С12 нужно закодировать минимальным из представленных четырех кодов. Пусть код С12 равен 1000. Нанесем это значение на карту Вейча.

Выберем следующую строку из матрицы М - С8С9. В этой строке не закодировано состояние С9. Составим подматрицу М9 (таблица 5.13). В ней ранее закодированы состояния С8 и С4, т.е. D = {0011, 0111}.

E0011 = {1011}

E0111 = {1111}

F = {1011, 1111}

W1011 = {1011, 0011} + {1011, 0111} = 1+2=3

W1111 = {1111, 0011} + {1111, 0111} = 2+1=3

Таблица 5.13:

М9 =	С8С9
	С9С4

Все кодовые расстояния равны, поэтому С9 можно закодировать любым из представленных двух кодов. Пусть код С9 равен 1111. Нанесем это значение на карту Вейча.

Кодирование состояний закончено. В результате состояния закодировали следующими кодами:

Таблица 5.14:

	Z1	Z2	Z3	Z4
С0	0	0	0	0
С1	0	0	0	1
С2	0	1	0	1
С3	0	1	1	0
С4	0	1	1	1
С5	0	0	1	0
С6	0	1	0	0
С7	1	0	1	0
С8	0	0	1	1
С9	1	1	1	1
С10	1	1	0	1
С11	1	1	1	0
С12	1	0	0	0

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

Так как входные и выходные буквы можно закодировать произвольной комбинацией, то закодируем их следующим образом (таблица 6.1 и таблица 6.2):

Таблица 6.1

	x1	x2
a1	0	0
a2	0	1
а3	1	0
?	1	1

Таблица 6.2:

	y1	y2
b1	0	0
b2	0	1
b3	1	0
?	1	1

При построении кодированной таблицы переходов и выходов автомата используется таблица 3.1. Рассмотрим клетку с координатами (а1, С0). По таблице кодирования находим а1 - 00, С0 - 0000. Следовательно, в первую строку левой части таблицы заносим координаты клетки. В этой же клетке записан переход в С1 с выходным сигналом. C1 закодировано как 0001, а как 11. В правую часть записываем: 000111. Так же заполняются остальные строки таблицы переходов и выходов автомата (таблица 6.3)

Таблица 6.3:

x1	x2	Z1	Z2	Z3	Z4	Z1	Z2	Z3	Z4	y1	y2
0	0	0	0	0	0	0	0	0	1	1	1
0	1	0	0	0	0	0	0	1	0	1	1
1	0	0	0	0	0	0	0	1	0	1	1
1	1	0	0	0	0	0	1	0	1	0	0
0	0	0	0	0	1	0	0	1	0	1	1
0	1	0	0	0	1	0	1	0	1	0	0
1	0	0	0	0	1	0	1	0	1	0	0
0	0	0	1	0	1	0	1	0	1	1	0
1	1	0	1	0	1	0	1	1	1	0	1
0	1	0	1	1	0	0	1	0	0	1	0
1	1	0	1	1	0	0	1	1	1	0	1
1	1	0	1	1	1	0	1	0	1	0	0
0	0	0	0	1	0	1	0	1	0	1	1
0	1	0	0	1	0	0	0	1	1	0	1
1	0	0	0	1	0	0	1	1	0	1	0
1	1	0	0	1	0	0	1	1	1	0	1
0	1	0	1	0	0	1	1	0	1	1	0
1	1	0	1	0	0	0	1	1	1	0	1
0	0	1	0	1	0	1	1	1	0	0	0
1	0	1	0	1	0	0	1	0	0	1	0
1	1	1	0	1	0	0	0	1	1	0	1
0	0	0	0	1	1	1	0	0	0	1	0
1	1	0	0	1	1	1	1	1	1	0	1
1	1	1	1	1	1	0	1	1	1	0	1
1	1	1	1	0	1	0	1	0	1	0	0
1	1	1	1	1	0	1	0	0	0	1	0
1	1	1	0	0	0	0	0	0	0	0	0

7. Синтез структурного автомата на элементах задержки

Строим 4 карты на 6 переменных для функций Z1-4 и две карты на 4 переменных для функций выходов у1-2 (автомат Мура и его выходное состояние не зависят от того, что на входе). Карты заполняются по таблице 6.3.

Z1(t+1)

0	0	1	1			0
			1
0	0		0	0			1
0		1	0	0	0	0	0
0			0	1	0	0
			0
0	0		0

Z2(t+1)

0	0	0	0			1
			1
0	1		0	1			1
1		1	1	1	1	1	1
0			0	0	1	1
			1
0	1		1

Z3(t+1)

0	1	0	1			1
			1
1	0		1	0			0
0		1	1	1	0	1	1
0			1	0	1	0
			0
1	0		1

Z4(t+1)

1	0	0	0			0
			0
0	1		1	0			1
1		1	1	1	1	1	1
0			1	0	1	1
			0		1
0	1		0

y1(t+1)

0	1	0	1
1	0	0	1
	1	0	0
1			1

y2(t+1)

0	1	1	1
0	0	1	0
	0	1	0
0			1

Получаем следующие функции переходов автомата:

И следующие функции выходов:

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

Q(t)	Q(t+1)	R	T
0	0	-	0
0	1	0	1
1	0	?	???
1	1	0	0

R₁

		0	0
			0
							0
		0
?			?	0	?	?
			?

T₁

0	0	1	1			0
			0
0	0		0	0			1
0		1	0	0	0	0	0
??			??	0	??	??
			??
0	0		0

0	0	0	0			0
			1
0	1		0	0			0
1		1	1	0	0	0	0
0			0	??	0	0
			1
0	1		1

						0
			0
	0			0			0
0		0	0	0	0	0	0
				?	0	0
			0
	0		0

R₂

б	1		б	1
			0		0
					?
	б	б	б	б		1
б	б	б	б	б	б	1	1
		0	?	0
					0
	б		б	б

T₂

б	1		б	1
			0		0
					?
	б	б	б	б		1
б	б	б	б	б	б	1	1
		0	?	0
					0
	б		б	б

D1

0	1	??	0			1
			0
1	0		0	??			0
0		0	0	0	??	1	1
0			0	??	0	0
			??
1	0		0

V1

	0	?	0			0
			0
0			0	?
		0	0	0	?	0	0
			0	?	0
			?
0			0

R3

Q(t)	Q(t+1)	D	V
0	0	б*?	б0
0	1	1	1
1	0	0	1
1	1	??	??

T3

1	0	??	1		0	??	1
				0
			1	0
0	??			0	??		0
1		0	0			0	1
0			0				0
0	??		1	0	??		0

	0	?	0			0
			0
0	?		0
		0	0	0	?	0	0
			0		0	?
0	?		0

R4

б0	б0	1	1			б0
			??
б0	б0		б0	б0			1
б0		1	б0	б0	б0	б0	б0
1			1	??	1	1
			1
б0	б0		б0

T4

б*	б*	1	1			б*
			??
б*	б*		б*	б*			1
б*		1	б*	б*	б*	б*	б*
0			0	??	0	0
			0
б*	б*		б*

D1

б0	1	1	?0			1
			?0
1	б0		?0	0			б0
б0		?0	?0	?0	1	1	1
б0			?0	1	?0	б0
			1
1	б0		?0

V1

б*	1	0	??			1
			??
1	б*		??	0			б*
б*		??	??	??	0	1	1
б*			??	0	??	б*
			0
1	б*		??

D3

б0	б0	б0	б0			?0
			1
б0	1		б0	?0			?0
1		1	1	?0	?0	?0	?0
б0			б0	1	?0	?0
			1
б0	1		1

V3

б*	б*	б*	б*			??
			1
б*	1		б*	??			??
1		1	1	??	??	??	??
б*			б*	0	??	??
			1
б*	1		1

D2

1	1	1	б0			1
			б0
б0	?0		1	б0			1
1		?0	1	1	?0	?0	1
б0			1	б0	?0	?0
			б0		?0
б0	?0		б0

V2

1	0	0	б*			0
			б*
б*	??		1	б*			1
1		??	1	1	??	??	1
б*			1	б*	??	??
			б*		??
б*	??		б*

D4

Q(t)	Q(t+1)	J	K
0	0	0	-
0	1	1	-
1	0	-	1
1	1	-	0

V4

			0
1			1	0	1	1
			1

0	0	1	1			0
0	0	1	1			0
0	0		0	0			1
0	0	1	1			0

J1

						0
				0			0
				0	0	0	0
				1	0	0

K1

0	0	0	0
			1
0	1		0
1		1	1
0			0
			1
0	1		1

J2

		1	0
			0
			0	1
		0	0	0	1
			0	1	0
			1
			0

0	1					0	1
1	0					1	0
0						0
0						0
1	0					1	0



J3

	1	1			1	1
	0				0
		0				0
	0				0

K3

1			1				1
				0
			1	0
0				0			0
1			0	0			1
0				1			0
			1	1
0			0	0			0

9. Определение функций выходов

Функции выходов такие же, как и при синтезе на элементах задержки.



10. Обоснование выбора элементов памяти

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

Для DV - триггера: С = 112 входа

Для RT- триггера: С = 137 входов

Для JK - триггера: С = 137 входов

Автомат нужно реализовать на DV-триггерах.

11. Введение синхронизации и установки автомата в начальное состояние

Синхронизация:

Установка автомата в начальное состояние:

Начальное состояние С0 закодировано как 0000. Поэтому все триггеры устанавливаем в 0.

Начальная установка выполнена.

12. Получение функций автомата в требуемом базисе

Переведем уравнения в базис Шеффера.



14. Построение временных диаграмм работы автомата

			а3	а2	а1
х1
х2
Q1
Q2
Q3
Q4
D1
V1
D2
V2
D3
V3
D4
V4
y1
y2
Си
Уст
			?	b2	b3

			а1	а1	б	б
х1
х2
Q1
Q2
Q3
Q4
D1
V1
D2
V2
D3
V3
D4
V4
y1
y2
Си
Уст
			?	?	b2	b1

Часть 2:

ВСТR R1,R2 [RR]

06 R1 R2

0 8 12 15

Из содержимого общего регистра, заданного полем R1, алгебраически вычитается 1. Если результат равен 0, продолжается выполнение команд в обычной последовательности с использованием продвинутого адреса команды. Если результат отличен от 0, адрес команды в текущем PSW замещается адресом перехода.

В качестве адреса перехода в формате RR используется содержимое битов с 8 - 31 общего регистра, заданного полем R2.Однако если в поле R2 содержатся нули, то операция выполняется без перехода.

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

1. Построение содержательной ГCА

Построение производится в соответствии с алгоритмом.

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

2. Кодирование ГСА

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

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

3. Разметка ГСА

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

4. Построение графа по ГСА

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

5. Кодирование состояний

С0 - 00

С1 - 01

С2 - 10

Сi	KCi	Cj	KCj	x(Ci,Cj)	y(Ci,Cj)	?(Ci,Cj)
C0	00	C1	01	1	y1y2	S2
C1	01	C2	10	1	y3	S1R2
C2	10	C0 C0 C0	00 00 00	x1	- - y4	R1 R1 R1

6. Определение функций возбуждения и функций выходов

7. Синтез на ПЛМ

x₁

x₂

Q₁

Q₂

S₁

R₁

S₂

R₂

y₁

y₂

y₃

y₄

О R₁,D₂(X₂,B₂) [RX]

56 R₁ X₂ B₂ D₂

0 8 12 16 20 31

Поразрядная логическая сумма (или) первого и второго операндов помещается на место первого операнда. Операнды обрабатываются как логические величины, не имеющие структуры, и операция выполняется над соответствующими парами битов.

Бит результата устанавливается в 1, если соответствующий бит какого-нибудь одного или обоих операндов содержит 1, в противном случае этот бит результата устанавливается в 0.

Признак результата:

0-результат равен 0

1-результат не равен 0

2-

3-

1. Построение содержательной ГСА

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

2. Кодирование ГСА

x₁

у₃

0 31 y₄

y₁

y₂



Y₁

Y₂

Y₃ Y₄

3. Разметка ГСА

С₀

Y₁

С₁

Y₂

С₂

Y₃ Y₄

С₀

4. Построение графа по ГСА

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

5. Кодирование состояний

С0 - 00

С1 - 01

С2 - 10

Сi	KCi	Cj	KCj	x(Ci,Cj)	y(Ci,Cj)	?(Ci,Cj)
C0	00	C1	01	1	y1	S2
C1	01	C2	10	1	y2	S1R2
C2	10	C0 C0	00 00	x1	y3 y4	R1 R1

6. Определение функций возбуждения и функций выходов

7. Синтез на ПЛМ

x₁

Q₁

Q₂

S₁

R₁

S₂

R₂

y₁

y₂

y₃

y₄

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

Л.А. Кропачев «Структурный синтез цифровых автоматов». Методическое указание к курсовой работе. Ижевск , 1990 г.

Л.А. Кропачев «Абстрактный синтез цифровых автоматов». Методическое указание к курсовой работе. Ижевск , 1990 г.

Л. Д. Райков «Принципы организации системы IBM/370»

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