Методические указания к заданию №1

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

 

Умножение двоич­ных чисел проводится по существу так же, как и умножение деся­тичных. Умножение выполняется по шагам. Число шагов равно разрядности множителя. На каждом шаге множимое умножается на одну цифру множителя и получается частичное произведение (ЧП). Сумма всех ЧП, предварительно сдвинутых относительно ДРУГ друга, образует полное произведение. При этом направление сдвига зависит от используемого метода умножения. Разрядность произведения равна 2п при разрядности сомножителей, равной п.

Умножение целых и дробных чисел с ФТ выполняется по оди­наковым алгоритмам. Отличие заключается только в том, что при Умножении целых чисел для правильного расположения произве­дения иногда в разрядной сетке необходим дополнительный сдвиг суммы ЧП вправо.

Так как цифры множителя могут принимать только значения «О» и «1», ЧП могут быть равны либо нулю, либо множимому, поэтому умножение двоичных чисел сводится к повторяющимся микрооперациям сложения и сдвига. Сложение ЧП производится в сумматоре с двумя входами, поэтому их сумма накапливается постепенно, на каждом шаге.

а) Различают следующие методы умножения:

1) начиная с младших разрядов множителя и сдвигом множи­мого влево;

2)начиная с младших разрядов множителя и сдвигом суммы ЧП вправо;

3)начиная со старших разрядов множителя и сдвигом множи­мого вправо;

4)начиная со старших разрядов множителя и сдвигом суммы ЧП влево.

Для реализации любого метода схема включает в себя регистр множимого Мм, регистр множителя Мт, сумматор с регистром сумматора для накопления суммы ЧП и блок управления БУ. При разрядности сомножителей, равной п, разрядность регистра мно­жимого и сумматора зависит от метода умножения.При умножении чисел со знаками отдельно определяются мо­дуль произведения и его знак. Знак произведения определяется сумми­рованием по модулю 2 знаков сомножителей. Вычисление модуля про­изведения может выполняться в прямом или дополнительном коде.

Умножение в ПК требует преобразования кодов, если числа хранятся в памяти в ДК, поэтому чаще умножение выполняется непосредственно в ДК. При этом произведение ДК не всегда рав­но ДК произведения. В зависимости от сочетания знаков сомно­жителей необходимо определенным образом корректировать ре­зультат. Далее приводятся значения поправок при умножении дроб­ных чисел с ФТ

 

1. Если Мм > 0 и Мт > 0, то Мм^дк = |Мм| и Мт^дк = |Мт|.

Тогда Мм^дк х Мт^дк = |Мм| х |Мт| = |Мм х Мт| = (Мм х Мт)^дк.

Коррекция не нужна.

 

2.Если Мм > 0 и Мт < 0, то Мм^дк = |Мм| и Мт^дк = 1 - |Мт|.

Тогда Мм^дк х Мт^дк = |Мм| х (1 - |Мт|) = |Мм| - |Мм| х |Мт|.

Так как (Мм х Мт)^дк= 1 - |Мм х Мт| = 1 - |Мм| х |Мт|, то нужна

коррекция и величина корректирующей поправки Δ = 1 - |Мм|, т.е. дополнению множимого, взятого со знаком минус.

 

3. Если Мм < 0 и Мт > 0, то Мм^дк = 1 - |Мм| и Мт^дк = |Мт|.

Тогда Мм^дк х Мт^дк = (1 - |Мм|) х |Мт| = |Мт| - |Мм х Мт|.

Так как (Мм х Мт)^дк= 1 - |Мм х Мт| = 1 - |Мм| х |Мт|, то нужна

коррекция и величина корректирующей поправки Δ = 1 - |Мт|, т.е. дополнению множителя, взятого со знаком минус.

4. Если Мм < 0 и Мт < 0, то Мм^дк = 1 - |Мм| и Мт^дк = 1 - |Мт|.

Тогда Мм^дк х Мт^дк= (1 - |Мм|)(1 - |Мт|) = 1 - |Мт| - |Мм| +

|Мм х Мт|.

Так как (Мм х Мт)^дк = |Мм х Мт| = |Мм| х |Мт|, то нужна коррекция и величина корректирующей поправки Δ = |Мм| + |Мт| - 1. Так как вычитание единицы приводит только к изменению знакового разряда, а знак определяется отдельно, то величина поправки может быть принята равной сумме модулей множимого и множителя, т.е. Δ = |Мм| + |Мт|. Поправки вводятся на дополни­тельном шаге умножения.

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

Логические методы основаны на одновременном анализе нескольких цифр множителя и сокращении за счет этого числа микроопераций. Реализация логических методов приводит к усложнению БУ АЛУ. Аппаратные методы обеспечивают одновременное выполнение нескольких микроопераций за счет дополнительной аппаратуры. Часто используют комбинации логических и аппаратных методов.

 

 

Логические методы ускорения умножения. Самым простым ме­тодом ускорения является пропуск такта суммирования, если оче­редная цифра множителя равна нулю. В этом случае сокращается число микроопераций суммирования. Более эффективными явля­ются методы с одновременным анализом нескольких цифр мно­жителя. При этом уменьшается как число сложений, так и сдвигов.

В качестве примера рассмотрим модифицированный алгоритм Бута. Сущность метода заключается в том, что одновременно ана­лизируются три разряда множителя: два текущих и старший раз­ряд из предыдущей тройки. В зависимости от значения анализиру­емых разрядов выполняются действия, указанные в табл. 1.1

 

 

Таблица 1.1

Умножение по алгоритму Бута

Разряды множителя	Кратность множимому	Знак	Выполняемые действия
				+	Не выполнять действий
				+	Прибавить к сумме ЧП множимое
				+	То же
				+	Прибавить к сумме ЧП удвоенное множимое
				-	Вычесть из суммы ЧП удвоенное множимое
				-	Вычесть из суммы ЧП множимое
				-	То же
				-	Не выполнять действий

 

 

Фактически в методе Бута на каждом шаге выполняется умно­жение множимого одновременно на две цифры множителя. Суще­ствуют методы умножения с непосредственной расшифровкой нескольких разрядов множителя. Наиболее распространен метод умножения с расшифровкой двух разрядов множителя (табл.

 

 

Умножение с расшифровкой двух разрядов множителя

 

Значение пары разрядов	Перенос из предыдущей пары разрядов	Перенос в следующую пару разрядов	Знак частичного произведения	Кратность частичного произведения множимому
			+
			+
			+
			-
			+
			+
			-
И			-

 

 

Комбинация 11 = 100 - 1, поэтому прибавление утроенного множимого заменяется вычитанием множимого с прибавлением единицы к следующей паре разрядов. Вычитание множимого за­меняется прибавлением дополнения множимого. При наличии переноса из предыдущей пары следующая пара увеличивается на единицу. На каждом шаге после суммирования сумма ЧП сдвигается на два разряда вправо. Если возник перенос из последней пары, то на дополнительном шаге умножения к сумме ЧП добав­ляется множимое.

Пример 1.1 Выполнить умножение чисел, если Мм₁₀ = +27, Мт₁₀ = = -18, Мм₂ = +11011, Мт₂ = -10010.

Мм^пк = 0 11011 ->Мм^дк = 0 11011. Модуль множимого |Мм| = 11011.

Мт^пк = 1 10010 Мт^дк= 1 01110. Модуль множителя |Мт| = 10010.

(-Мм)^дк = 1 00101.

Последовательность формирования произведения с использо­ванием метода Бута (модифицированного) и расшифровкой пар разрядов множителя показана в табл. 4.5 и 4.6 соответственно.

 

Метод Бута

Слагаемые, микрооперации	Множитель (ЧП,)	Формирование суммы ЧП
Множитель
Сумма ЧП
Цифры Мт		+
ЧП,	-2Мм	10 01010
Сумма ЧП		10 0101000000
Сдвиг		—> —>
Цифры Мт		+
чп2		00 00000
Сумма ЧП		И 1001010000
Сдвиг		—> —>
		И 1110010100
Цифры Мт		+
ЧП3	-Мм
Сумма ЧП		11 0000110100
Дополнитель­ный сдвиг		—>
(МмхМт)мдк		11 1000011010
(Ммх Мт)пк		1 0111100110
(Ммх Мт)2		-0111100110
(МмхМт),0		-486

 

 

Таблица 4.6 Анализ пары разрядов

Слагаемые, микрооперации	Множитель (ЧП,)	Формирование суммы ЧП
Множитель
Сумма ЧП		00 0000000000
Цифры Мт		+
чп,	+2Мм	01 1011
Сумма ЧП		01 1011000000
Сдвиг		—>
		00 0110110000
Цифры Мт		+
ЧП2		00 00000
Сумма ЧП		00 0110110000
Сдвиг		—> —>
		00 0001101100
Цифры Мт		+
ЧП3	+ Мм	00 11011
Сумма ЧП		00 1111001100
Дополнитель­ный сдвиг		—>
(|Мм|х|Мт|)		00 0111100110
(МмхМт)2		-0111100110
(МмхМт)10		-486

 

 

При использовании метода Бута умножение выполняется в МДК. При этом знак произведения формируется автоматически, так как знаки сомножителей участвуют в формировании ЧП. Произведе­ние получается также в МДК.

При умножении с расшифровкой пар разрядов множителя со­множители представляются в ПК. Но вычитание в ходе умноже­ния выполняют в МДК. Модуль произведения и его знак опреде­ляются отдельно. Для правильного расположения произведения в разрядной сетке выполняется дополнительный сдвиг суммы ЧП на один разряд вправо.

 

 

Заполнить таблицу умножения чисел с ФТ по варианту

 

 

Слагаемые, микроопе­рации	Метод умножения
Сумма ЧП
Сдвиг
Сложение
ЧП,
Сумма ЧП
Сдвиг
Сложение
ЧП2
Сумма ЧП
Сдвиг
Сложение
ЧП3
Сумма ЧП
Сдвиг
Сложение
ЧП4
Сумма ЧП
Сдвиг
МмхМт

* Фиктивный сдвиг, выполняется для регулярности умножения.

** Первое ЧП равно множимому, сдвинутому на один разряд вправо.

*** Возможно временное переполнение.

 

Заполнить таблицу умножения в дополнительном кодепо варианту

 

 

Слагаемые, микроопера­ции	Знаки сомножителей
Мм > 0, Мт > 0	Мм > 0, Мт < 0	Мм < 0, Мт > 0	Мм< 0, Мт< 0
Сумма ЧП
Сложение
ЧП1
Сумма ЧП
Сдвиг
Сложение
Сложение
ЧП3
Сумма ЧП
Сдвиг
Сложение
ЧП4
Сумма ЧП
Сдвиг
Коррекция
Мм х Мт
(Мм х Мт)ДК

 

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

 

 

Пример1. Выполнить умножение чисел, если Мм₁₀ = +27, Мт = -18, Мм₂ = +11011, Мт₂ = -10010.

Мм^пк = 011011 Мм^дк = 011011. Модуль множимого |Мм| = 11011.

Мт^пк = 1 10010 Мт^дк = 1 01110. Модуль множителя |Мт| = 10010.

(-Мм) ^дк = 1 00101.

Таблица 4.6 Анализ пары разрядов

 

Слагаемые, микрооперации	Множитель (ЧП,.)	Формирование суммы ЧП
Множитель
Сумма ЧП
Цифры Мт
ЧП,
Сумма ЧП.
Сдвиг
Цифры Мт
ЧП2
Сумма ЧП
Сдвиг
Цифры Мт
ЧП3
Сумма ЧП
Дополнитель­ный сдвиг
(|Мм|х|Мг!)
(Мм х Мт)2
(МмхМт)10

 

 

Деление чисел с фиксированной точкой. Деление представлю собой более

сложную операцию, чем умножение. При делении двоичных чисел используется тот же способ, что и при делении десятичных чисел вручную. Частное вычисляется по шагам. Hа первом шаге подбирается одна цифра частного. Для этого из дели­мого вычитается произведение делителя на подобранную цифру частного. Подбор производится с учетом знака и величины полу­ченной разности (частичного остатка). На следующих шагах дели­тель вычитается из очередного частичного остатка. На каждом шаге производится сдвиг делителя вправо или остатка влево. В основном используется метод деления со сдвигом остатка влево. Деление про­должается до получения заданного числа разрядов частного.

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

При делении целых чисел делимое представляется обычно в формате двойного слова (2п разрядов), делитель и частное имеют формат слова (n разрядов). При делении дробных чисел делимое может иметь формат слова.

Частное может содержать более чем п разрядов. В этом случае возникает переполнение разрядной сетки. Переполнение не воз­никает, если число, содержащееся в п старших разрядов делимо­го, меньше делителя (для целых чисел) или делимое меньше де­лителя (для дробных чисел). Одно из этих условий проверяется перед делением.

При делении чисел со знаком возможно отдельное определе­ние модуля частного и его знака. В этом случае числа представля­ются в ПК. Возможно также выполнение деления непосредствен­но в ДК.

Известны два алгоритма деления: с восстановлением остатка и без его восстановления. Деление с восстановлением остатка вы­полняется в основном так же, как деление вручную. Общая после­довательность деления с восстановлением остатка содержит сле­дующие микрооперации:

1. Делитель размещается в старших п разрядах двойного слова.

2. Проверяется условие возможности деления (отсутствие пере­полнения). Для этого из делимого вычитается делитель и анализи­руется знак остатка.

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

4. Остаток сдвигается влево на один разряд.

5. Из сдвинутого остатка вычитается делитель и анализируется знак остатка.

 

Делимое А 10= +145						Делитель В 10= -13
Вычитание делителя	+					Частное	(A/B)w=-11
Остаток < 0	=				↑↑↑↑	Деление	корректно
Восстановление остатка	+				llll
Восстановленный остаток	=				| | | |
Сдвиг остатка влево					l l l l
Вычитание делителя	+				l l l l
Остаток > 0	=				-- ↑ l l l
Сдвиг остатка влево					III
Вычитание делителя	+				III
Остаток < 0	=				---↑ III
Восстановление остатка	+				II
Восстановленный остаток	=				II
Сдвиг остатка влево					II
Вычитание делителя	+				II
Остаток > 0	=				-----↑|
Сдвиг остатка влево					|
Вычитание делителя	+				|
Остаток > 0	=				------↑	Остаток	R 10 =+2

Рис. 4.12. Деление чисел с восстановлением остатка

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

7. Проверяется условие окончания деления. Если получены все цифры частного, то деление заканчивается, иначе выполняется переход к п. 4. Последний остаток восстанавливается, если он мень­ше нуля. Для этого к нему прибавляется делитель.

При вычитании делителя используется дополнительный или модифицированный дополнительный код.

Пример Выполнить деление чисел с восстановлением остатка, если

A ₁₀ = + 145; А ₂ = +10010001; | А |^ПК = 0 10010001; | А |^МДК = 00 10010001.

В ₁₀ = –13; В ₂ = –1101; | В |^ПК = 0 1101;

| В |^МДК = 00 1101; (–| В |)^МДК = 11 0011.

Процесс определения цифр частного показан на рис.

Если при делении с восстановлением остатка получен отрица­тельный остаток, то после восстановления остатка, сдвига вос­становленного остатка и последующего вычитания делителя на шаге i будет получен следующий результат:

R_i = 2 (R_{i- 1} + В)– В=2 R_{i- 1} + В,

где R_j — остаток на шаге i; R_{i- 1} — остаток на шаге i - 1; В — делитель.

Множитель 2 возникает при сдвиге данных влево на один раз­ряд.

Результат 2 R_{i- 1}+ В может быть получен более простым путем, что и используется при делении без восстановления остатка. Та­кой вид деления отличается тем, что при получении отрицатель­ного остатка он сдвигается влево и к нему прибавляется делитель для определения следующего остатка.

Делимое A 10= + 145 Вычитание делителя	00 1001 0001 + 11 0011		Делитель B10=–13
	Частное (A / B)10=–11
Остаток < 0	=				↑↑↑↑	Деление корректно
Сдвиг остатка влево					| | | |
Прибавление делителя	+				| | | |
Остаток > 0	=				-- ↑| | |
Сдвиг остатка влево					| | |
Вычитание делителя	+				| | |
Остаток < 0	=				---↑| | |
Сдвиг остатка влево					| |
Прибавление делителя	+				| |
Остаток > 0	=				----↑ |
Сдвиг остатка влево					|
Вычитание делителя	+				|
Остаток > 0	=				----- ↑	Остаток R 10= +2

Рис. 4.13. Деление чисел без восстановления остатка

 

Пример Выполнить деление чисел без восстановления остатка,

если A₁₀ = +145; А₂ = +10010001; | А |^ПК = 0 10010001; | А |^МДК = 00 10010001.

В ₁₀ = –13; В ₂ = –1101; | В |^ПК = 0 1101;

| В |^МДК = 00 1101; (–| В |)^МДК= 11 0011

Действия, выполняемые при делении, показаны на рис.

Деление без восстановления остатка может быть реализовано устройством деления (рис. 4.14). При анализе его схемы можно установить, что в ее состав входят те же узлы, которые составля­ют схему умножения (см.). Эти схемы отличаются лишь направлением сдвига содержимого регистра сумматора и регистра множителя (частного). Используя регистры со сдвигом в двух на­правлениях, можно построить комбинированную схему умноже­ния-деления (рис.).

Младшие разряды 2 n -разрядного регистра сумматора исполь­зуются в качестве регистра множителя-частного, что позволяет уменьшить аппаратные затраты.

Блок умножения-деления настраивается на выполнение задан­ной операции сигналом кода операции, поступающим из цент­рального устройства управления.

Ускорение деления. Деление, как и умножение, является длин­ной операцией, при этом время выполнения деления зависит от разрядности операндов. Для ускорения деления используются ло­гические или аппаратные методы.

Логические методы ускорения деления предполагают анализ не только знака, но и нескольких разрядов остатка. Это позволяет в среднем сократить число

 

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

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

Пример Выполнить деление чисел, применяя логический метод ускорения с использованием МДК,

если А ₁₀ = –117; А ₂ = – 01110101; | А |^ПК = = 0 01110101; | А |^МДК = 00 01110101.

В ₁₀ = + 13; В ₂ = + 1101; | В [^ПK = 0 1101; | В |^МДК = 00 1101; (–| В |)^МДК= 11 0011

Процесс ускорения деления чисел с использованием МДК поясняется на рис.. Значения разрядов, при которых выпол­няется ускорение, выделены подчеркиванием.

В примере ускорение можно выполнить только на шаге проверки корректности деления. Более эффективным является метод ускорения с анализом двух старших цифр остатка и делите­ля.

Пример Выполнить деление чисел, применяя логический метод ускорения анализа старших цифр, если А₁₀ = –117; А₂ = – 01110101; | А |^ПК = = 0 01110101; | А |^МДК = 00 01110101.

В₁₀= +13; В₂ = +1101; | В |^ПК = 0 1101; | В |^МДК = 00 1101; (–| В |)^МДК = 11 0011.

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

 

Контрольные вопросы

 

1. Каковы особенности АЛУ магистрального типа и АЛУ с «жёсткой» структурой?

2. Какие возможные методы умножения чисел вы знаете?

3. Почему при умножении чисел в ДК необходима коррекция результата?

4. В чем заключается сущность логических методов ускорения умножения?

5. Каковы особенности деления без восстановления остатка?

6. В чем состоит общая идея логических методов ускорения деления?

7. Почему при умножении и делении можно использовать одни и те же узлы АЛУ?

8. Для чего применяется счетчик циклов при умножении и делении?

 

 

Задание к РГР №2

Задание 1

Построить граф переход на основе таблицы перехода по варианту.

Цель работы: научиться выполнять процессы путем преобразования информаций в соответствии с заложенной в него программой.

Необходимо:

а) выбрать из варианта последовательность кодовых кнопок

б) внести ее в таблицу входа и выхода комбинационного автомата

в) составить таблицу состояния переходов

г) построить наглядный способ описания автомата с помощью графа переходов

 

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

Для иллюстрации основных способов описания автоматов рассмотрим кодовый замок с 5 кнопками (А, Б, В, Г, Д), который открывается при наборе нужной последовательности кнопок, причем две кнопки одновременно нажать нельзя. Множество А входных сигналов содержит 6 сигналов: А, Б, В, Г, Д, *; сигнал, обозначенный буквой, означает, что соответствующая кнопка нажата, сигнал * означа­ет, что ни одна кнопка не нажата. Множество V выходных сигналов содержит два сигнала: 0, 1; 0 означает, что замок закрыт; 1 — что замок открыт. Число состояний зависит от длины и числа кодовых последовательностей, открывающих замок. Если замок открывается при нажатии одной определен­ной кнопки (скажем, кнопки Б), то выходной сиг­нал зависит только от текущего входного сигнала, и функция выходов λ задается таблицей:

 

Вход	А Б В Г Д *
Выход	0 1 0 0 1 1

 

Последовательность: Б, *, Д.

Состояния в таком автомате вообще не играют роли; поэтому принято считать, что он имеет только одно состояние, которое в процессе его функциони­рования не меняется. Автоматы с одним состоянием называются комбинационными. Если же замок от­крывается при нажатии определенной последова­тельности кнопок, то выход зависит не только от текущего, но и от предыдущих входных сигналов. Такой автомат называется последовательностным. Для обеспечения зависимости от прошлого необхо­димо "запоминать" предыдущие входные сигналы. С этой целью и вводятся состояния. Пусть замок открывается последовательностью Б, *, Д и открыт, пока нажата кнопка Д. Функции δ и λ такого авто­мата зададим одной объединенной таблицей:

 

 

С о с т о я н и е	Вход	А Б В Г Д *
q1 q2 q3 q4	q1, 0 q2,0 q1, 0 q1, 0 q1, 0 q1, 0 q1, 0 q2,0 q1, 0 q1, 0 q1, 0 q3, 0 q1, 0 q1, 0 q1, 0 q1, 0 q4, 1 q3, 0 q1, 0 q1, 0 q1, 0 q1, 0 q4, 1 q1, 0

 

 

В этой таблице на пересечении строки q_i и столбца a_j указаны значения функций

δ (q_i, a_j) и λ(q_i, a_j). Например:

δ (q_з,*) = q_з, λ(q_з,*) = 0.

Такая таблица является стандартным описани­ем конечного автомата и называется таблицей пе­реходов. Ее большое достоинство в том, что при ее заполнении приходится рассмотреть все ситуации, которые могут встретиться при работе автомата (т. е. все возможные пары "входной сигнал — со­стояние"), и определить поведение автомата в этих ситуациях. Главный недостаток — тот, что при большом числе состояний и входных сигналов эта таблица становится плохо обозримой и неудобной в работе.

Более компактный и наглядный способ описа­ния автомата — с помощью графа (или диаграммы) переходов. Вершины графа q соответствуют состоя­ниям автомата; стрелка (дуга), ведущая из верши­ны q_i в вершину q_j, обозначает переход автомата из состояния q_j в состояние q_j, на этой же стрелке указан входной сигнал, вызывающий данный пере ход, и — после вертикальной черты — выходной сигнал, который при этом выдается. Если несколько входных сигналов вызывают один и тот же переход и выходной сигнал, они перечисляются на одной стрелке через запятую.

*| 0

 

Б | 0 Д | 1

Г,Д,*| 0

В, * | 0

q3

А, Д | 1

q4

q2

q1

Б | 0

А,В,Г,Д| 0

 

А,Б,В,Г | 0

 

А,Б,В,Г,*|0

 

 

Рис.2

Граф переходов для табл. 2 приведен на рис. 2. На этом рисунке наглядно вид­но, что отпирающей последовательности соответст­вует путь из q₁ в q₄, где и открывается замок.

Формальное определение автомата, проиллю­стрированное табл. 2 и рис. 2, предполагает, что время действия входного сигнала примерно равно времени смены состояний и следующий входной сигнал автомат получает после перехода в следу­ющее состояние. Однако на практике может ока­заться, что согласовать эти длительности трудно, так как время смены состояний зависит от физиче­ской природы и устройства автомата и, как правило, ограничено долями секунды. Длительность же вход­ного сигнала зависит от внешних источников и не всегда подвластна разработчику.

Задания по варианту:

 

Вход	А	Б	В	Г	Д	*
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Вариант 11
Вариант 12
Вариант 13
Вариант 14
Вариант 15
Вариант 16
Вариант 17