Проектирование микропрограммного автомата

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

6

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

Содержание

Расчет задания

Часть 1.

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

2. Построение таблицы переходов по отображениям

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

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

5. Кодирование входных и выходных букв

6. Синтез автомата на элементах задержки

7. Синтез автомата на триггерах

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

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

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

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

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

Часть 2.

1. Описание команды

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

3. Построение кодированной ГСА и ее разметка

4. Построение графа микропрограммного автомата

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

6. Построение матрицы прошивки ПЛМ

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

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

Расчет задания

Определяем тип автомата (остаток по модулю 2):

903 : 2 = 451, остаток 1 - автомат Мура

Определим отображение информации, осуществляемое автоматом (остаток по модулю 13 и 23):

903 : 13 = 69, остаток 6 - входные буквы

903 : 23 = 39, остаток 6 - выходные буквы

a₃ > b₃

a₂ a₃ а> b₁b₂ b₃

a₁ a₁ a₂> b₁ b₁ b₂

a₂ a₁ > b b₂

a₁ a₂ a₁ > b b₃b₂

a₃ a₂ a₁ > b₂ b₂ b₂

Определим тип логических элементов (остаток по модулю 5):

903 : 5 = 900, остаток 3 - базис {&, V, -}

Определим типы триггеров (остаток по модулю 17):

903 : 17 = 901, остаток 2 - триггеры D, S, T типов

Часть 1

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

микропрограммный автомат триггер информация

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

Будем выравнивать каждое отображение вводом минимально необходимого количества пустых букв:

1.a₃ a> bb₃

2.a₂ a₃ аa>b b₁b₂ b₃

3.a₁ a₁ a₂ a > bb₁ b₁ b₂

4.a₂ a₁ a> bb b₂

5.a₁ a₂ a₁ a> bb b₃b₂

6.a₃ a₂ a₁ a> bb₂ b₂ b₂

2. Построение таблицы переходов по отображениям

Входной алфавит автомата А = {a₁, a₂, a₃, a}

Выходной алфавит В = {b₁, b₂, b₃, b}

Первоначально автомат находится в состоянии С₀. Пусть на вход автомата подается буква a₃. Автомат перейдет в новое состояние (С₁), выдавая на выходе b. Следующей подается буква а₂ (слово 6). Под действием этой буквы автомат перейдет в состояние С₂ и выдаст b₂. С приходом последней буквы (a) автомат вернется в состояние С₂ и на выходе выдаст b₂. К этому слову будем пристраивать другие слова.

Окончательная таблица переходов:

Таблица 2.1

	а1	а2	а3	a
С0	С3	C1	C1
С1	C5	C2	C7	C4	B
С2	C2			C2	b2
С3	C6				B
С4				C2	b3
С5	C4			C2	B
С6				C2	b1
С7				C8	b1
С8				C4	b2

Таблица 2.1 - таблица переходов автомата Мура, реализующего заданные отображения. По этой таблице построим граф (рис. 1).

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

Рис.1

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

a3

a

a2

a3

a

a

a1

a1

a2

a

a2

a1

a

a1

a2

a1

a

a3

a2

a1

a

C0

C1

C4

C1

C7

C8

C4

C3

C6

C6

C2

C1

C5

C2

C3

C5

C4

C2

C1

C2

C2

C2

b

b3

b

b1

b2

b3

b

b1

b1

b2

b

b

b2

b

b

b3

b2

b

b2

b2

b2

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

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

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

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

	С1С3 C5	С6С7	С2С8	С4
а1	5 6 4	- -	С2 -	-

Под действием а₁ ни одна из групп не расщепилась. Рассмотрим переходы под действием букв а₂ и а₃.

	С6С7	С2С8
а2	6 -	- -
а3	- -	- -

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

	С6С7	С2С8
a	2 8	2 4

Под действием буквы a происходит расщепление групп. Рассмотрим группу С₆С₇. Под действием a происходит переход в С₆ и С_7. Состояния С₆ и С₇ принадлежат разным группам, поэтому группа С₆С₇ разбивается на две - С₆ и С₇.

Таким образом, после минимизации автомата сохранилось то же количество внутренних состояний, что и до минимизации. Автомат не минимизировался, и у него остались те же состояния - С₀, С₁, С₂, С₃, С₄, С₅, С₆, С₇, С₈.

	а1	а2	а3	a
С0	W3	W1	W1
С1	W5	W2	W7	W4	B
С2	W2			W2	b2
С3	W6				B
С4				W2	b3
С5	W4			W2	B
С6				W2	b1
С7				W8	b1
С8				W4	b2

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

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

Построим матрицу пар переходов, имеющих место в кодируемом автомате (таблица 4.1).

Далее вместо W будем обозначать C для удобства.

Таблица 4.1

	С0С3
М =	С0С1
	С1С5
	С1С2
	С1С7
	С1С4
	С3С6
	С3С5
	С4С2
	С5С4
	С5С2
	С6С2
	С7С8
	С8С4

Таблица 4.2

Таблица 4.3

М1 =	С0С1
	С1С5
	С1С2
	С1С7
	С1С4

Таблица 4.4

М5 =	С1С5
	С3С5
	С5С4
	С5С2

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

Автомат имеет 8 внутренних состояний, поэтому необходимы 4 элемента памяти и код состояний будет иметь 4 разряда.

Закодируем С₀ как 0000, а С₃. как 0001. Нанесем эти значения на карту Вейтча (таб. 4.2).

Во второй строке не закодировано состояние С₁. Построим подматрицу М₂ (таблица 4.3). В ней ранее закодировано только состояние С₀, код которой 0000. Тогда множество уже закодированных состояний Е = {С₀}. Найдем по карте Вейтча соседние незанятые клетки для этих состояний. Коды этих клеток запишем в множества F₀.

F₀ = {0100, 1000, 0010}

Из этих множеств составим множество G.

G = {0100, 1000, 0010}

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

D₀₁₀₀ = 2d(0100, 0000) = 2

D₁₀₀₀ = 2d(1000, 0000) = 2

D₀₀₁₀ = 2d(0010, 0000) = 2

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

Выберем следующую строку из матрицы М. В этой строке не закодировано состояние С₅. Составим подматрицу М₅ (таблица 4.4). В ней ранее закодированы состояния С₁ и С₃, т.е. Е = {C₀, C₁}, их коды 0000 и 0001 соответственно.

F₁ = {1100, 0101, 0110}

F₃ = {0101, 0011, 1001}

G = {1100, 0101, 0110, 0011, 1001}

Таблица 4.5

М2 =	С1С2
	С4С2
	С5С2
	С6С2

Таблица 4.6

М7 =	С1С7
	С7С8

Таблица 4.7

М4 =	С1С4
	С4С2
	С5С4
	С8С4

Таблица 4.8

М8 =	С4С8
	С8С3
	С8С1

Таблица 4.9

М6 =	С3С6
	С6С2

М8 =	С8С4

Найдем кодовые расстояния между множеством G и кодами С₀, С₁.

D₁₁₀₀ = 2d(1100, 0000) + d(1100, 0001) = 7

D₀₁₀₁ = 2d(0101, 0000) + d(0101, 0001) = 5

D₀₁₁₀ = 2d(0110, 0000) + d(0110, 0001) = 7

D₀₀₁₁ = 2d(0011, 0000) + d(0011, 0001) = 5

D₁₀₀₁ = 2d(1001, 0000) + d(1001, 0001) = 5

Минимальные кодовые расстояния соответствуют кодам 0110, 1001 и 0010. Состояние С₅ можно закодировать любым из этих кодов. Выберем, например, код 0011 и нанесем С₅ на карту Вейтча.

Возьмем следующую строку матрицы М, в которой есть незакодированные состояния. Составим подматрицу М₂ (таблица 4.5). В ней ранее закодированы состояния С₁ и С₅. Поэтому Е = {С₁,С₅}.

F₁ = {1100, 0101,0110}

F₅ = {0010, 1011,0111}

G = {1100, 0101, 0110, 0010, 1011, 0111}

Найдем кодовые расстояния.

D₁₁₀₀ = 2d(1100, 0000)+d(1100,0011) = 8

D₀₁₀₁ = 2d(0101, 0000)+d(0101,0011) = 6

D₀₁₁₀ = 2d(0110, 0000)+d(0110,0011) = 6

D₀₀₁₀ = 2d(0010, 0000)+d(0000,0011) = 3

D₁₁₀₀ = 2d(1011, 0000)+d(1011,0011) = 7

D₁₁₀₀ = 2d(0111, 0000)+d(0111,0011) = 7

C₂ можно закодировать как 0010. Нанесем С₂ (0010) на карту Вейтча.

Возьмем следующую строку матрицы М с незакодированным состоянием. Выпишем подматрицу М₇ (таблица 4.6). В ней ранее закодировано С₀(0000).

F₁ = {1100,0110, 0101}

G = {1100, 0110, 0101}

Найдем кодовые расстояния.

D₁₁₀₀ = 2d(1100, 0000) = 4

D₀₁₁₀ = 2d(0110, 0000) = 4

D₀₁₀₁ = 2d(0101, 0000) = 4

С₇ можно закодировать как 1100, 0101 или 0110. Выберем код 1100 и нанесем это состояние на карту Вейтча.

Из матрицы М возьмем следующую строчку. В ней не закодировано состояние С₄. Составим и напишем подматрицу М₄ (таблица 4.7). В ней ранее закодировано 3 состояния С₂ (0010), С₅ (0011), С₁ (0000). Выпишем множества F_i.

G = {0101, 0110, 1010, 0111, 1011}

Рассчитаем кодовые расстояния:

D₀₁₀₁ = d(0101, 0000) + d(0101, 0010) + d(0101, 0011) = 7

D₀₁₁₀ = d(0110, 0000) + d(0110, 0010) + d(0110, 0011) = 5

D₁₀₁₀ = d(1010, 0000) + d(1010, 0010) + d(1010, 0011) = 5

D₀₁₁₁ = d(0111, 0000) + d(0111, 0010) + d(0111, 0011) = 6

D₁₀₁₁ = d(1011, 0000) + d(1011, 0010) + d(1011, 0011) = 6

Минимальное кодовое расстояние соответствует кодам 0110 и 1010. С₄ закодируем как 1001. Нанесем это значение на карту Вейтча.

Возьмем следующую строка матрицы М. В этой строке не закодировано состояние С₆. Поэтому составим подматрицу М₆ (таблица 4.8). В ней ранее закодированы состояния С₂ (0010), С₃ (0001). Запишем множества F и их объединенное множество G:

F₂ = {0110}

F₃ = {0101, 1001}

G = {0101, 1001, 1100, 0110}

Найдем кодовые расстояния:

D₀₁₀₁ = 2d(0101, 0001) + d(0101, 0010) = 5

D₁₀₀₁ = 2d(1001, 0001) + d(1001, 0001) = 5

D₀₁₁₀ = 2d(0110, 0001) + d(0110, 0010) = 7

C₆ можно закодировать как 0101 или 1001. Закодируем С₆ кодом 1001.

В матрице М осталось одно не закодированное состояние - С₈. Матрица М₈ выглядит следующим образом (таблица 4.9). В ней закодировано состояние С₄ (1010). Запишем множества F и G.

F₄ = {1000, 1011, 1110}

G = {1000, 1011, 1110}

Найдем кодовые расстояния:

D₁₀₀₀ = 2d(1000, 1010) = 2

D₁₀₁₁ = 2d(1011, 1010) = 2

D₁₁₁₀ = 2d(1110, 1010) = 2

Закодируем С₈ как 1110.

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

	Z1	Z2	Z3	Z4
С0	0	0	0	0
С1	0	1	0	0
С2	0	0	1	0
С3	0	0	0	1
С4	1	0	1	0
С5	0	0	1	1
С6	1	0	0	1
С7	1	1	0	0
С8	1	1	1	0

5. Кодирование входных и выходных букв

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

	х1	х2
а1	0	0
а2	0	1
а3	1	0
a	1	1

	у1	у2
b1	0	0
b2	0	1
b3	1	0
b	1	1

Синтез автомата на элементах задержки

Автомат имеет два физических входа х₁ и х₂, и два физических выхода у₁ и у₂, четыре элемента памяти. Тогда левая часть кодированной таблицы (таблица 6.1) будет иметь 2 + 4 = 6 столбцов, и правая также будет иметь 2 + 4 = 6 столбцов. Число строк равняется 18.

Возьмем первую клетку таблицы 2.1 с координатами <а₁, С₀>. По таблице кодирования находим а₁ - 00, С₀ - 0000. Значит, в первую строку кодированной таблицы запишем

х₁ х₂ z₁ z₂ z₃ z₄

0 0 0 0 0 0

В клетке <а₁, С₀> таблицы 2.1 записан переход в С₃ с выдачей b. С₃ закодировано как 0001, а b как 11, поэтому в правой части таблицы 6.1 в первой строке записываем

z₁ z₂ z₃ z₄ y₁ y₂

0 0 0 1 1 1

По такому же правилу заполняем остальные строчки таблицы. В результате получим:

Таблица 6.1

х1	х2	z1	z2	z3	z4	z1	z2	z3	z4	у1	y2
0	0	0	0	0	0	0	0	0	1	1	1
0	1	0	0	0	0	0	1	0	0	1	1
1	0	0	0	0	0	0	1	0	0	1	1
0	0	0	1	0	0	0	0	1	1	1	1
0	1	0	1	0	0	0	0	1	0	0	1
1	0	0	1	0	0	1	1	0	0	0	0
1	1	0	1	0	0	1	0	1	0	1	0
0	0	0	0	1	0	0	0	1	0	0	1
1	1	0	0	1	0	0	0	1	0	0	1
0	0	0	0	0	1	1	0	0	1	0	0
0	1	0	0	0	1	0	0	1	1	1	1
1	1	1	0	1	0	0	0	1	0	0	1
0	0	0	0	1	1	1	0	1	0	1	0
1	1	0	0	1	1	0	0	1	0	0	1
0	1	1	0	0	1	1	0	0	1	0	0
1	1	1	0	0	1	0	0	1	0	0	1
1	1	1	1	0	0	1	1	1	0	0	1
1	1	1	1	1	0	1	0	1	0	1	0

Заполним по этой таблице карты Вейтча. Число карт для автомата Мили определяется числом столбцов в правой части таблицы 6.1, а число переменных - числом столбцов в левой части таблицы. Тогда будем иметь 6 карт на 6 переменных.

Заполнение карт трудности не представляет. Левую часть таблицы будем рассматривать как координаты клетки, а правую - как значение, подставляемое в соответствующую карту, в указанную клетку. Так, например, для первой строки - координата клетки 000000, в карту для z₁ подставим 0, для z₂ - 0, для z₃ - 0, для z₄ - 1, для у₁ - 1, для у₂ - 1. Остальные клетки заполняем точно также.



По картам Вейтча проводим совместную минимизацию функций z_i; y_j. Получаем систему уравнений автомата.

Функции переходов автомата

Функции выходов автомата

7. Синтез автомата на триггерах

Возьмем сначала первый тип триггера из предложенных в задании - D-триггер. Ниже приведены его матрица переходов и матрица входов.

D	Q	Q(t+1)
0	0	0
0	1	0
1	0	1
1	1	1

Q(t)	Q(t+1)	D
0	0	0
0	1	0
1	0	1
1	1	1

По таблице 6заполним карты Вейтча для D-триггераНа этих картах внутренние состояния обозначаются не как Z, а как Q, так как выходы триггеров обычно обозначают Q и Q. В остальном карты для Q полностью соответствуют картам для Z. Карты для выходов у совпадают полностью.

Если клетка лежит на половине Q_i, то для всей этой половины предыдущее состояние Q_i(t) = 0, если клетка лежит на половине Q_i, то предыдущее состояние Q_i(t) = 1. В самой клетке записано последующее состояние, то есть, если в клетке 0, то Q_i(t+1) = 0, если 1 - Q_i(t+1) = 1. По матрице входов триггера определяем R_i и S_i и записываем в соответствующие таблицы.



Склеивая на картах Вейтча, получаем следующие функции:

Следующий тип триггера - T. Ниже приведены таблица переходов и матрица входов этого триггера.



Получаем следующие функции:

Следующий тип триггера - S. Ниже приведены таблица переходов и матрица входов этого триггера.

R	S	Q
0	0	Q
0	1	1
1	0	0
1	1	1

Q(t)	Q(t+1)	R	S
0	0	-	0
0	1	-	1
1	0	1	0
1	1	b0	B1

Заполним карты Вейтча для S-триггера.

Получаем следующие функции для S-триггера:

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

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

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

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

Для D-триггера С = 29

Для T-триггера С = 56

Для S-триггера С = 63

Автомат можно реализовать на D-триггерах. Итак, реализуем автомат на D-триггерах.

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

Чтобы ввести синхронизацию искусственно, нужно во все функции возбуждения конъюктивно ввести сигнал синхронизации Си.

Сигнал <Уст> подается на функции возбуждения дезъюнктивно. Начальное состояние С₀ закодировано как 0000, поэтому все 4 триггера нужно установить в 0.

R	S	Q
0	0	Q
0	1	1
1	0	0
1	1	1

Тогда получаем следующие функции:



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

Переведём в нужный базис(Шеффера)

Построим функциональную схему автомата на элементах задержки и триггерах



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

Часть II

1. Описание команды

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

Умножение двух чисел с плавающей точкой заключается в сложении порядков и умножении мантисс. Операнды предварительно нормализуются, и сумма их характеристик, уменьшенная на 64, используется в качестве характеристики промежуточного произведения.

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

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

Если характеристика нормализованного произведения превышает 127 и мантисса произведения не равна 0, то фиксируется переполнение порядка. Операция завершается уменьшением характеристики на 128 по сравнению с её действительным значением. Если в случае расширенных результатов характеристика младшей части также превышает 127, то и она уменьшается на 128. Результат является нормализованным числом, а знак и мантисса сохраняют правильные значения. После этого происходит программное прерывание из-за переполнения.

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

Если характеристика нормализованного произведения меньше 0, то имеет место исчезновение порядка. Операция завершается формированием характеристики, которая на 128 больше по сравнению с действительным значением.

Признак результата остается без изменения.

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

Построим в соответствии с алгоритмом содержательную граф-схему.

Закодируем микрооперации и логические условия:

y₁: РгМх(0:55): = Х(0, 8:63) - загрузка знака и мантиссы множимого

у₂: РгМу(0:55): = У(0, 8:63) - загрузка знака и мантиссы множителя

у₃: СмХ(1:7) - загрузка характеристики множимого

у₄: РгУ(0:6) - загрузка характеристики множителя

у₅: РгМу(56, 57) - обнуление признаков умножения

у₆: СчТ: = 56 - занесение числа разрядов в счетчик

у₇: См: = 0 - обнуление сумматора

у₈: См(1:55): = L1(См(1:55)) - арифметический сдвиг сумматора влево

у₉: РгМу: = R1(РгМу) - сдвиг вправо мантиссы множителя

у₁₀: РгМу(1): = См(55) - передача младшего разряда сумматора в регистр РгМу

у₁₁: См(1:55): = См(1:55) + (РгМх(1:55) + 1) - вычитание множимого

у₁₂: См(1:55): = См(1:55) + РгМх(1:55) - прибавление множимого

у₁₃: СчТ: = СчТ - 1 - уменьшение счетчика на 1

у₁₄: См(1:55): = L4(См(1:55)) - сдвиг мантиссы промежуточного произведения на одну цифровую позицию

у₁₅: СмХ: = СмХ - 1 - уменьшение характеристики на 1

у₁₆: СмХ(1:7): = СмХ(1:7) + РгУ(0:6) - 64 - получение характеристики промежуточного произведения

у₁₇: СмХ(1:7): = СмХ(1:7) - 128 - уменьшение характеристики на 128

у₁₈: ТПП: = 1 - установка триггера, регистрирующего переполнение, в 1

у₁₉: См(0): = РгМу(0) РгМх(0) - получение знака произведения

у₂₀: Х(0, 8:63): = См(0:55) - запись в Х мантиссы и знака

у₂₁: Х(1:7): = СмХ(1:7) - запись характеристики

y₂₂: СмХ(0): = СмХ(0) + 128 - увеличение характеристики на 128

у₂₃: ТИП: = 1 - установка триггера, регистрирующего исчезновение порядка, в 1

х₁: РгМу(57) = 0 - анализ разряда регистра РгМу

х₂: РгМу(56) = 0 - анализ разряда регистра РгМу

х₃: СчТ = 0 - проверка состояния счетчика

х₄: См(1) = 0 - проверка сумматора

х₅: См(1:55) = 0 - проверка мантиссы

х₆: СмХ(0) = 1 - проверка на переполнение



Операционная схема устройства умножения длинных чисел с управляющими сигналами у_i и осведомительными сигналами х_j показана на рисунке 3.1.

3. Построение кодированной ГСА и ее разметка

Каждую операторную вершину можно рассматривать как некоторую микрокоманду Y_К. записывая в каждую операторную вершину закодированные микрооперации y_i, а в условные вершины - логические условия, получим кодированную ГСА умножения. Дальнейший синтез управляющего автомата ведется по кодированной ГСА.



4. Построение графа микропрограммного автомата

По кодированной ГСА построим граф. Для этого исследуем пути переходов от одного состояния к другому. Проводим дуги от вершины к вершине и записываем конъюкции логических условий на данном пути, если на пути нет никаких условий, то на дуге пишется 1.

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

Для кодирования внутренних состояний применим кодирование по минимуму Хемингова расстояния.

Построим матрицу М - матрицу пар переходов, имеющих место в данном автомате (таблица 6.1). Матрица составлена таким образом, что хотя бы одно состояние в каждой строке, встречается в какой-нибудь строке, расположенной выше.

Автомат имеет 10 внутренних состояний, поэтому необходимо 4 элемента памяти и код состояний будет иметь 4 разряда.

Закодируем С₀ как 0000 и С₁ - как 0001. Нанесем эти значения на карту Вейтча (таблица 6.2).

Во второй строке матрицы М не закодировано состояние С₂. Составим подматрицу М₂ (таблица 6.3). В ней ранее закодировано состояние С₁ (0001). Составим множеств F₁ незанятых соседних клеток для состояние С₁:

F₁ = {1001, 0101, 0011}

Таблица 6.1

М =	С0С1
	С1С2
	С2С3
	С2С4
	С2С5
	С3С5
	С4С5
	С5С2
	С5С6
	С5С7
	С6С6
	С6С7 C6C10
	С7С8
	С7С9
	С8С9
	С9С0 C10C6 C10C7

Таблица 6.2

Таблица 6.3

М2 =	С1С2
	С2С3
	С2С4
	С2С5
	С5С2

Таблица 6.4

М3 =	С2С3
	С3С5

Таблица 6.5

М4 =	С2С4
	С4С5

Множество G будет объединять все множества F. В данном случае множество G равняется:

G = {1001, 0101, 0011}

Рассчитаем кодовые расстояния:

D₀₀₁₁ = d(0011, 0001) = 1

D₀₁₀₁ = d(0101, 0001) = 1

D₀₀₁₁ = d(1001, 0001) = 1

Состояние С₂ можно закодировать любым кодом из множества G. Выберем 0101. Нанесем С₂(0101) на карту Вейтча.

Следующая строка матрицы М - С₂С₃. В ней незакодированно состояние С₃. Составим подматрицу М₃ (таблица 6.4). В ней ранее закодировано С₂(0101).

F₂ = {0100, 1101, 0111}

G = {0100, 1101, 0111}

D₀₁₀₀ = d(0100, 0101) = 1

D₁₁₀₁ = d(1101, 0101) = 1

D₀₁₁₁ = d(0111, 0101) = 1

С₃ можно закодировать, например, как 0100.

Следующее незакодированное состояние матрицы М - С₄. Составим подматрицу М₄ (таблица 6.5). В ней ранее закодировано только С₂(0101).

F₂ = {1101, 0111}

G = {1101, 0111}

D₁₁₀₁ = d(1101, 0101) = 1

D₀₁₁₁ = d(0111, 0101) = 1

Закодируем С₄ как 1101.

Следующее состояние - С₅. В подматрице М₅ (таблица 6.6) закодированы состояния С₂(0101), С₃(0100), С₄(1101).

F₂ = {0111}

F₃ = {1100, 0110}

F₄ = {1100, 1001, 1111}

G = {0111, 1100, 0110, 1001, 1111}

D₀₁₁₁ = 2d(0111, 0101) + d(0111, 0100) + d(0111, 1101)=6

Таблица 6.6

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

Таблица 6.7

М6 =	С5С6 С6С6 С6С7 С6С10 С10С6

Таблица 6.8

М7 =	С5С7 С6С7 С7С8 С7С9 С10С7

Таблица 6.9

М10 =	С6С10 С10С6 С10С7

Таблица 6.10

М8 =	С7С8 С8С9

Таблица 6.11

М9 =	С8С9 С7С9 С9С0

D₁₁₀₀ = 2d(1100, 0101) + d(1100, 0100) + d(1100, 1101)= 6

D₀₁₁₀ = 2d(0110, 0101) + d(0110, 0100) + d(0110, 1101)= 8

D₁₀₀₁ = 2d(1001, 0101) + d(1001, 0100) + d(1001, 1101)= 8

D₁₁₁₁ = 2d(1111, 0101) + d(1111, 0100) + d(1111, 1101)= 8

Закодируем С₅ как 1100.

Закодируем следующее состояние - С₆. В подматрице М₆ (таблица 6.7) уже закодировано состояние С₅(1100}.

F₅ = {1000, 1110}

G = {1000, 1110}

D₁₀₀₀ = d(1000, 1100) = 1

D₁₁₁₀ = d(1110, 1100) = 1

C₆ закодируем как 1000.

Следующее состояние - С₇. В подматрице М₇ (таблица 6.8) закодированы состояния С₅(1100) и С₆(1000).

F₅ = {1110}

F₆ = {1001, 1010}

G = {1110, 1001, 1010}

D₁₁₁₀ = d(1110, 1100) + d(1110, 1000) = 3

D₁₀₀₁ = d(1001, 1100) + d(1001, 1000) = 3

D₁₀₁₀ = d(1010, 1100) + d(1010, 1000) = 3

Закодируем С₇ как 1001.

Закодируем следующее состояние - С₁₀. В подматрице М₁₀ (таблица 6.9) закодированы состояния С₆(1000) и С₇(1001).

F₆ = {1010}

F₇ = {1011}

G = {1010, 1011}

D₁₀₁₀ = 2d(1010, 1000) + d(1010, 1001) = 4

D₁₀₁₁ = 2d(1011, 1000) + d(1011, 1000) = 6

C₁₀ закодируем как 1010.

Следующее состояние - С₈. В подматрице М₈ (таблица 6.1) закодировано состояние С₇. Для состояния С₇ осталась только одна незанятая соседняя клетка - 1011. Этим кодом и закодируем состояние С₈.

В подматрице М₉ закодированы состояния С₀(0000), С₇(1001) и С₈(1011).

F₀ = {0010}

F₇ = {-}

F₈ = {1111, 0011}

G = {0010, 1111, 0011}

D₀₀₁₀ = d(0010, 0000) + d(0010, 1001) + d(0010, 1011) = 6

D₁₁₁₁ = d(1111, 0000) + d(1111, 1001) + d(1111, 1011) = 7

D₀₀₁₁ = d(0011, 0000) + d(0011, 1001) + d(0011, 1011) = 5

C₉ закодируем как 0011.

В итоге получаем следующие коды состояний:

	Q1	Q2	Q3	Q4
С0	0	0	0	0
С1	0	0	0	1
С2	0	1	0	1
С3	0	1	0	0
С4	1	1	0	1
С5	1	1	0	0
С6	1	0	0	0
С7	1	0	0	1
С8	1	0	1	1
С9	0	0	1	1
С10	1	0	1	0

6. Построение матрицы прошивки ПЛМ

Сi(y)	KCi	Cj	KCj	x(Ci, Cj)	f(Ci, Cj)
C0(-)	0000	C1	0001	1	S4
C1(y1y2y3y4y5y6y7)	0001	C2	0101	1	S2
C2(y8y9y10)	0101	C3 C4 C5	0100 1101 1100	x1x2 x1x2 x1x2 \/ x1x2	R4 S1 S1R4
C3(y11)	0100	C5	1100	1	S1
C4(y12)	1101	C5	1100	1	R4
C5(y13)	1100	C2 C6 C7	0101 1000 1001	x3 x3x4 x3x4	R1S4 R2 R2S4
C6(y14y15)	1000	C6 C7 C10	1000 1001 1010	x4x6 x4x6 x6	- S4 S3
C7(y16)	1001	C8 C9	1011 0011	x5x6 x5\/x5x6	S3 R1S3
C8(y17y18)	1011	C9	0011	1	R1
C9(y19y20y21)	0011	C0	0000	1	R3R4
C10(y22y23)	1010	C6 C7	1000 1001	x4 x4	R3 R3S4

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

_ _ _ _ _ _ _ _ _ _

R₁ = x₃Q₁Q₂Q₃Q₄ \/ x₅Q₁Q₂Q₃Q₄ \/ x₅x₆Q₁Q₂Q₃Q₄ \/ Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _

S₁ = x₁x₂Q₁Q₂Q₃Q₄ \/ Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄

_ _ _ _ _

R₂ = x₃x₄Q₁Q₂Q₃Q₄ \/ x₃x₄Q₁Q₂Q₃Q₄

_ _ _

S₂ = Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _

R₃ = Q₁Q₂Q₃Q₄ \/ x₄Q₁Q₂Q₃Q₄ \/ x₄Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _

S₃ = x₆Q₁Q₂Q₃Q₄ \/ x₅x₆Q₁Q₂Q₃Q₄ \/ x₅Q₁Q₂Q₃Q₄ \/ x₅x₆Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _

R₄ = x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄ \/ Q₁Q₂Q₃Q₄ \/ Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

S₄ = Q₁Q₂Q₃Q₄ \/ x₃Q₁Q₂Q₃Q₄ \/ x₃x₄Q₁Q₂Q₃Q₄ \/ x₄x₆Q₁Q₂Q₃Q₄ \/ x₄Q₁Q₂Q₃Q₄

_ _ _

y₁ y₂ y₃ y₄ y₅ y₆ y₇ = Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _

y₈ y₉ y₁₀ = x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄ \/ x₁x₂Q₁Q₂Q₃Q₄

_ _ _

y₁₁ = Q₁Q₂Q₃Q₄

_

y₁₂ = Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _

y₁₃ = x₃Q₁Q₂Q₃Q₄ \/ x₃x₄Q₁Q₂Q₃Q₄ \/ x₃x₄Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _ _ _ _

y₁₄ y₁₅ = x₄x₆Q₁Q₂Q₃Q₄ \/ x₄x₆Q₁Q₂Q₃Q₄ \/ x₆Q₁Q₂Q₃Q₄

_ _ _ _ _ _ _ _ _

y₁₆ = x₅x₆Q₁Q₂Q₃Q₄ \/ x₅Q₁Q₂Q₃Q₄ \/ x₅x₆Q₁Q₂Q₃Q₄

_

y₁₇ y₁₈ = Q₁Q₂Q₃Q₄

_ _

y₁₉ y₂₀ y₂₁ = Q₁Q₂Q₃Q₄

_ _ _ _ _

y₂₂ y₂₃ = x₄Q₁Q₂Q₃Q₄ \/ x₄Q₁Q₂Q₃Q₄

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

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