Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сибирский Государственный Университет Телекоммуникаций и Информатики

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

502_KHramova_T._V._Diskretnaja_matematika_proektirovanie_konechnykh_avtomatov_v_primerakh_i_zadachakh_

.pdf

Скачиваний:

Добавлен:

12.11.2022

Размер:

2.43 Mб

Скачать

☆

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>

Построим диаграмму Мура (рисунок 7). Следуя диаграмме Мура, составим таблицу переходов-выходов:

Поставим в соответствие состояниям последовательности «0» и «1»:

S	S1S2S				3	000,	S S1S			2S3		001,		S	2	S1S		2S		3	010,
0	0		0		0		1	1	1		1				2	2		2		2
S	S1S2S				3	011,	S	S1S		2S3		100,		S	5	S1S		2S		3	101, S		S1S		2S3		110.
3	3		3	3			4	4		4	4				5	5	5		5		6		6		6	6
Составим каноническую таблицу:
		Si1(t)				Si2(t)	Si3(t)			x(t)			y(t)			Si1(t 1)						Si2(t 1)		Si3(t 1)
		0				0		0			0		0			0						0			1
													0			0						1			0
		0				0		0			1		0			0						1			0
													0			0						1			1
		0				0		1			0		0			0						1			1
													0			1						0			0
		0				0		1			1		0			1						0			0
													0			1						0			1
		0				1		0			0		0			1						0			1
		0				1		0			1		0			1						1			0
													1			0						1			1
		0				1		1			0		1			0						1			1
													0			1						0			0
		0				1		1			1		0			1						0			0
													0			1						0			1
		1				0		0			0		0			1						0			1
													0			1						1			0
		1				0		0			1		0			1						1			0
													0			0						1			1
		1				0		1			0		0			0						1			1
		1				0		1			1		1			1						0			0
													1			1						0			1
		1				1		0			0		1			1						0			1
													1			1						1			0
		1				1		0			1		1			1						1			0
													—			—						—		—
		1				1		1			0		—			—						—		—
													—			—						—		—
		1				1		1			1		—			—						—		—
													21

Составим канонические уравнения. Для y(t) составим и упростим СДНФ: y(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)

Si1(t) Si2(t) Si3(t) x(t) Si3(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) Si3(t).

Для Si1(t 1) составим и упростим СКНФ:

Si1(t 1) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)

Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t)

Si1(t) Si2(t) Si3(t) Si1(t) Si3(t) x(t) Si1(t) Si2(t) Si3(t) x(t) .

Заметим, что значения Si2(t 1) можно представить как неравнозначность переменных в третьем и четвертом столбце, следовательно

S2(t 1) S

3(t) x(t) S

3(t)

x(t)

S3(t) x(t).

Столбец значений переменных Si3(t 1)

является отрицанием столбца

Составим систему канонических уравнений:

y(t) Si

(t) Si (t) Si

(t) x(t) Si

(t) Si

(t) x(t) Si

(t) Si (t) Si (t),

(t) S

(t) x(t) ,

S (t 1) S (t) S

(t) S

(t) S (t) S

(t) x(t) S

(t) S

(t 1) S3(t)

S3(t)

x(t),

x(t)

(t 1) x(t),

t 3,4,...,

y(1) y(2) 0.

x(t)

(11)

В соответствие с равенствами (11), доопределим каноническую таблицу:

Si1(t)	Si2(t)	Si3(t)	x(t)	y(t)	Si1(t 1)	Si2(t 1)	Si3(t 1)
0	0	0	0	0	0	0	1
0	0	0	1	0	0	1	0
0	0	1	0	0	0	1	1
0	0	1	1	0	1	0	0
0	1	0	0	0	1	0	1
0	1	0	1	0	1	1	0
0	1	1	0	1	0	1	1
0	1	1	1	0	1	0	0
1	0	0	0	0	1	0	1
1	0	0	1	0	1	1	0
1	0	1	0	0	0	1	1
1	0	1	1	1	1	0	0
1	1	0	0	1	1	0	1
1	1	0	1	1	1	1	0
1	1	1	0	0	1	1	1
1	1	1	1	0	1	0	0
				22

Пример 7. y(t) x(t) x(t 2),

y(1) 1,

y(2) 1.

Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется символом, введенным два такта назад и символом, вводимым на текущем такте. Необходимо четыре состояния,

соответствующих всевозможным комбинациям x(t 2) x(t 1).	Помнить
оба символа x(t 2) x(t 1) необходимо, поскольку с введением	x(t) эта

последовательность сдвигается: текущий символ становится прошлым, а прошлый — позапрошлым. Кроме этого, необходимо начальное состояние и два состояния (невозвратных), в которые автомат переходит на первом такте, пока последовательность x(t 2) x(t 1) еще не сформировалась. Уточним формулы для вычисления выходного значения:

S3 00: y(t) x(t) x(t 2) x(t) 0 x(t) 0 x(t), S4 01: y(t) x(t) x(t 2) x(t) 1 x(t) 1 1, S5 10: y(t) x(t) x(t 2) x(t) 1 x(t) 1 1, S6 11: y(t) x(t) x(t 2) x(t) 1 x(t) 1 1.

Построим диаграмму Мура (рисунок 8).

Рисунок 8.

Следуя диаграмме Мура, составим таблицу переходов-выходов:

В таблице имеются состояния с одинаковыми переходами и выходами: S1,

S5 и S2, S4, S6. Отождествим одинаковые состояния, для этого заменим в таблице все вхождения S5на S1, а S4, S6 на S2:

Из новой таблицы можно удалить состояние — S2, оно идентично S0:

Составим каноническую таблицу, предварительно поставив в соответствие каждому состоянию последовательность «0» и «1» длины 2:

S S1S2 00,			S S1S2			01,		S S1S2			10.
0	0	0	1	1	1			3	3	3
Si1(t)	Si2(t)		x(t)	y(t)			Si1(t 1)		Si2(t 1)
0		0	0		1			0			1
0		0	1		1			0			0
0		1	0		1			1			0
0		1	1		1			0			0
1		0	0		1			1			0
1		0	1		0			0			0
1		1	0		—			—			—
1		1	1		—			—			—
				24

Составим канонические уравнения. Для y(t) составим СКНФ: y(t) Si1(t) Si2(t) x(t).

Для Si1(t 1) составим и упростим СДНФ:

Si1(t 1) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) Si1(t) Si2(t) x(t).

Для S2

(t 1)

составим СДНФ: S2(t 1) S1(t) S2

(t)

x(t)

Составим систему канонических уравнений:

y(t)

S2(t)

S1(t)

x(t),

(12)

Si1(t 1) Si1(t) Si2(t) Si1(t) Si2(t) x(t),

t 3,4,...,

y(1) y(2) 1.

Si (t 1) Si (t) Si (t) x(t),

В соответствии с равенствами (12), доопределим каноническую таблицу:

Si1(t)	Si2(t)	x(t)	y(t)	Si1(t 1)	Si2(t 1)
0	0	0	1	0	1
			1	0	0
0	0	1	1	0	0
			1	1	0
0	1	0	1	1	0
			1	0	0
0	1	1	1	0	0
			1	1	0
1	0	0	1	1	0
			0	0	0
1	0	1	0	0	0
			1	0	0
1	1	0	1	0	0
			1	0	0
1	1	1	1	0	0

Пример 8. y(t) x(t) x(t 1) x(t 2) ... x(1).

Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется всеми символами, введенными ранее. Если вдуматься, автомату необходимы только два состояния: «ноль на входе еще не появился» (на выходе — единица) и «появился ноль на входе» (после этого выходное значение уже не изменится и будет равно нулю). Построим диаграмму Мура (рисунок 9).

Рисунок 9.

Следуя диаграмме Мура, составим таблицу переходов-выходов:

	x(t)	0	1
S
	S0	S1	S0
		0	1

	S1	S1	S1
		0	0

Составим каноническую таблицу, предварительно поставив в соответствие

состояниям кодовые последовательности:						S0 0,		S1 1.
		Si (t)	x(t)		y(t)		Si (t 1)
		0	0		0		1
					1		0
		0	1		1		0
					0		1
		1	0		0		1
					0		1
		1	1		0		1
Составим канонические уравнения. Заметим, что Si								(t 1) это импликация:
				а y(t)
Si (t 1) Si	(t) x(t) Si (t) x(t),			а y(t)		ее отрицание. Таким образом:

y(t) Si (t) x(t),

Si1(t 1) Si (t) x(t).

Пример 9.	x(1) x(3)	x(5)	... x(t), t	нечетный,
Пример 9.	y(t)	x(5)	... x(t 1),	.
	x(1) x(3)	x(5)	... x(t 1),	t четный.

Решение. Входной и выходной алфавиты автомата {0;1}. Выходное значение определяется всеми символами, введенными ранее на нечетных тактах времени. Количество состояний определяется необходимостью помнить, какой идет такт – четный или нечетный, и, какое к этому моменту «накопилось» значение функции — 0 или 1. Пусть

S1 — «четный такт, значение функции равно 0»;

S2 — «четный такт, значение функции равно 1»;

S3 — «нечетный такт, значение функции равно 0»;

S4 — «нечетный такт, значение функции равно 1». Построим диаграмму Мура (рисунок 10).

Рисунок 10.

Следуя диаграмме Мура, составим таблицу переходов-выходов:

Состояние S3 отождествим с S0(у них одинаковые переходы и выходы):

	S	S1S2 00,							S S1S2							01,		S	2	S1S2			10,		S	4		S1S2				11.
0				0			0		1			1		1					2	2		2				4		4			4
							Si1(t)		Si2(t)					x(t)			y(t)				Si1(t 1)				Si2(t 1)
							0		0					0			0					0				1
							0		0					1			1					1				0
							0		1					0			0					0				0
							0		1					1			0					0				0
							1		0					0			1					1				1
							1		0					1			1					1				1
							1		1					0			1					1				0
							1		1					1			0					0				1
Составим
Составим					канонические уравнения. Для y(t) составим и упростим СДНФ:
						x(t) S1(t)									S1(t)					x(t) S1(t) S2(t)
y(t)	S1(t)		S2	(t)						S2	(t)							S2(t)											)	S2(t)		x(t) S1(t)		.
y(t)	S1(t)		S2	(t)						S2	(t)		x(t)					S2(t)									x(t		)	S2(t)		x(t) S1(t)	x(t)	.
	i		i					i		i						i		i				i		i						i		i

Значения Si1(t 1) совпадают с y(t).

Запишем и упростим СДНФ для Si2(t 1):

Si2(t 1) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si1(t) Si2(t) x(t) Si2(t) x(t) Si1(t) x(t).

Запишем систему канонических уравнений:

y(t) Si2(t) x(t)

Si1(t 1) Si2(t)

Si2(t 1) Si2(t)

Si1(t) x(t),

x(t) Si1(t) x(t),

x(t) Si1(t) x(t).

Пример 10.	x(t) 1,	t нечетный,
	y(t)		.
	x(t) x(t 1),		t четный.

Решение. Входной и выходной алфавиты автомата {0;1}. Автомат выдает различные значения в зависимости от четности такта, следовательно, необходимо помнить четность такта и последний входной символ:

S1 — «0, четный такт», y(t) x(t) 0 x(t); S2 — «1, четный такт», y(t) x(t) 1 x(t); S3 — «0, нечетный такт», y(t) x(t) 1 x(t);

S4 — «1, нечетный такт», y(t) x(t) 1 x(t). Построим диаграмму Мура (рисунок 11).

Рисунок 11.

Следуя диаграмме Мура, составим таблицу переходов-выходов:

Состояния S3 и S4 идентичны S0 (у них одинаковые переходы и выходы):

Поставим в соответствие состояниям последовательности «0» и «1»:

		S	S1S2					00,				S		S1S2 01,												S	2		S1S2 10.
	0		0		0						1			1					1								2		2			2
Составим каноническую таблицу
		Si1(t)		Si2(t)					x(t)					y(t)							Si1(t 1)									Si2(t 1)
		0		0					0					1						0									1
		0		0					1					0						1									0
														0						0									0
		0		1					0					0						0									0

		0		1					1					1						0									0
														1						0									0
		1		0					0					1						0									0
		1		0					1					0						0									0
		1		0					1					0						0									0
	1		1						0						—							—									—
Составим	1		1						1						—							—									—			получить как
Составим	канонические уравнения. Значения																								y(t)				можно					получить как
эквивалентность S2			(t) и x(t)
									: y(t) S2(t) x(t)													S2			(t)						.
									: y(t) S2(t) x(t)													S2			(t)			x(t)			.
		i												i									i
Для Si1(t 1)	и Si2(t 1) запишем СДНФ:

S	1(t 1)			S1(t)		S2			(t)	x(t), S2(t 1)														S1(t)						S2(t)					.
S	1(t 1)			S1(t)		S2			(t)	x(t), S2(t 1)														S1(t)						S2(t)			x(t)		.
	i			i				i								i									i						i
Запишем систему канонических уравнений:
				y(t) S2
											(t) x(t)							S2(t)
											(t) x(t)							S2(t)					x(t),
										i									i
					1
					1							1				2		(t) x(t),														(13)
				Si			(t 1) Si (t) Si											(t) x(t),														(13)
					2
													1				2
								(t					1				2		(t) x(t).
				Si				(t	1) Si					(t) Si					(t) x(t).

Доопределим каноническую таблицу согласно уравнениям (13):

		Si1(t)		Si2(t)					x(t)					y(t)							Si1(t 1)									Si2(t 1)
		0		0					0					1						0									1
		0		0					1					0						1									0
		0		1					0					0						0									0
		0		1					1					1						0									0
		1		0					0					1						0									0
		1		0					1					0						0									0
	1		1						0					0						0									0
														1						0									0
	1		1						1					1						0									0

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
12.11.2022341.2 Кб0493_Tevljukova_O._JU._Sotsiologija_organizatsij_.pdf
#
12.11.2022466.74 Кб4496_ZHaravina_M.S._Metodicheskie_rekomendatsii_po_izucheniju_distsipliny_Anglijskij_jazyk_.pdf
#
12.11.2022950.84 Кб3497_Kachalov_L._K.Sotsiologija_.pdf
#
12.11.20227.41 Mб11500_Goncharov_S._A._Informatsionnye_tekhnologii_v_mediaindustrii_Upravlenie_dannymi_.pdf
#
12.11.2022589.15 Кб2501_Borisova__A._A._Upravlenie_chelovecheskimi_resursami_.pdf
#
12.11.20222.43 Mб5502_KHramova_T._V._Diskretnaja_matematika_proektirovanie_konechnykh_avtomatov_v_primerakh_i_zadachakh_.pdf
#
12.11.20222.22 Mб5505_Il'inykh_S._A._Psikhologija_massovykh_kommunikatsij_.pdf
#
12.11.2022359.78 Кб3506_Stroganov_A._K._Ispol'zovanie_sredstv_professional'no-prikladnoj_fizicheskoj_.pdf
#
12.11.2022304.28 Кб8507_Istorija_i_filosofija_nauki_sost._V._SH._Sabirov_.pdf
#
12.11.20222.57 Mб15508_Kokoreva_E._V.Osnovy_besprovodnoj_svjazi__.pdf
#
12.11.20221.19 Mб2509_Merzljakova_E.JU._CHeloveko-mashinnoe_vzaimodejstvie_.pdf