Методические указания к заданию №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 Выполнить умножение чисел, если Мм10 = +27, Мт10 = = -18, Мм2 = +11011, Мт2 = -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.Выполнить умножение чисел, если Мм10 = +27, Мт = -18, Мм2 = +11011, Мт2 = -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 | = | ------↑ | Остаток | R10 =+2 |
Рис. 4.12. Деление чисел с восстановлением остатка
6. Если остаток положительный, то очередная цифра частного равна единице. Если остаток меньше нуля, то очередная цифра множителя равна нулю. При этом остаток восстанавливается путем прибавления делителя.
7. Проверяется условие окончания деления. Если получены все цифры частного, то деление заканчивается, иначе выполняется переход к п. 4. Последний остаток восстанавливается, если он меньше нуля. Для этого к нему прибавляется делитель.
При вычитании делителя используется дополнительный или модифицированный дополнительный код.
Пример Выполнить деление чисел с восстановлением остатка, если
A10 = + 145; А2 = +10010001; |А|ПК = 0 10010001; |А|МДК = 00 10010001.
В10 = –13; В2 = –1101; |В|ПК = 0 1101;
|В|МДК = 00 1101; (–|В|)МДК = 11 0011.
Процесс определения цифр частного показан на рис.
Если при делении с восстановлением остатка получен отрицательный остаток, то после восстановления остатка, сдвига восстановленного остатка и последующего вычитания делителя на шаге i будет получен следующий результат:
Ri = 2(Ri-1 + В)– В=2 Ri-1 + В,
где Rj — остаток на шаге i; Ri-1 — остаток на шаге i - 1; В — делитель.
Множитель 2 возникает при сдвиге данных влево на один разряд.
Результат 2 Ri-1+ В может быть получен более простым путем, что и используется при делении без восстановления остатка. Такой вид деления отличается тем, что при получении отрицательного остатка он сдвигается влево и к нему прибавляется делитель для определения следующего остатка.
| Делимое A10= + 145 Вычитание делителя | 00 1001 0001 + 11 0011 | Делитель B10=–13 | ||||
| Частное (A/B)10=–11 | ||||||
| Остаток < 0 | = | ↑↑↑↑ | Деление корректно | |||
| Сдвиг остатка влево | | | | | | |||||
| Прибавление делителя | + | | | | | | ||||
| Остаток > 0 | = | -- ↑| | | | ||||
| Сдвиг остатка влево | | | | | |||||
| Вычитание делителя | + | | | | | ||||
| Остаток < 0 | = | ---↑| | | | ||||
| Сдвиг остатка влево | | | | |||||
| Прибавление делителя | + | | | | ||||
| Остаток > 0 | = | ----↑ | | ||||
| Сдвиг остатка влево | | | |||||
| Вычитание делителя | + | | | ||||
| Остаток > 0 | = | ----- ↑ | Остаток R10= +2 |
Рис. 4.13. Деление чисел без восстановления остатка
Пример Выполнить деление чисел без восстановления остатка,
если A10 = +145; А2 = +10010001; |А|ПК = 0 10010001; |А|МДК = 00 10010001.
В10 = –13; В2 = –1101; |В|ПК = 0 1101;
|В|МДК = 00 1101; (–|В|)МДК= 11 0011
Действия, выполняемые при делении, показаны на рис.
Деление без восстановления остатка может быть реализовано устройством деления (рис. 4.14). При анализе его схемы можно установить, что в ее состав входят те же узлы, которые составляют схему умножения (см.). Эти схемы отличаются лишь направлением сдвига содержимого регистра сумматора и регистра множителя (частного). Используя регистры со сдвигом в двух направлениях, можно построить комбинированную схему умножения-деления (рис.).
Младшие разряды 2n-разрядного регистра сумматора используются в качестве регистра множителя-частного, что позволяет уменьшить аппаратные затраты.
Блок умножения-деления настраивается на выполнение заданной операции сигналом кода операции, поступающим из центрального устройства управления.
Ускорение деления. Деление, как и умножение, является длинной операцией, при этом время выполнения деления зависит от разрядности операндов. Для ускорения деления используются логические или аппаратные методы.
Логические методы ускорения деления предполагают анализ не только знака, но и нескольких разрядов остатка. Это позволяет в среднем сократить число
микроопераций за счет некоторого усложнения БУ. Наиболее естественным является метод, который может быть использован при делении дробных чисел с ФТ, в частности мантисс чисел с ПТ. Так как мантиссы операндов перед делением нормализованы, то старший разряд мантиссы делителя равен единице. Если при делении с использованием модулей старший разряд остатка равен нулю, то остаток заведомо меньше делителя, поэтому на данном шаге можно принять очередную цифру частного равной нулю и выполнить сдвиг остатка влево без вычитания.
Признаком ускорения является наличие нуля по обе стороны точки.
ПримерВыполнить деление чисел, применяя логический метод ускорения с использованием МДК,
если А10 = –117; А2 = – 01110101; |А|ПК = = 0 01110101; |А|МДК = 00 01110101.
В10 = + 13; В2 = + 1101; |В[ПK = 0 1101; |В|МДК = 00 1101; (–|В|)МДК= 11 0011
Процесс ускорения деления чисел с использованием МДК поясняется на рис.. Значения разрядов, при которых выполняется ускорение, выделены подчеркиванием.
В примере ускорение можно выполнить только на шаге проверки корректности деления. Более эффективным является метод ускорения с анализом двух старших цифр остатка и делителя.
Пример Выполнить деление чисел, применяя логический метод ускорения анализа старших цифр, если А10 = –117; А2 = – 01110101; |А|ПК = = 0 01110101; |А|МДК = 00 01110101.
В10= +13; В2 = +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 |
В этой таблице на пересечении строки qi и столбца aj указаны значения функций
δ (qi , aj) и λ(qi , aj ). Например:
δ (qз,*) = qз , λ(qз,*) = 0.
Такая таблица является стандартным описанием конечного автомата и называется таблицей переходов. Ее большое достоинство в том, что при ее заполнении приходится рассмотреть все ситуации, которые могут встретиться при работе автомата (т. е. все возможные пары "входной сигнал — состояние"), и определить поведение автомата в этих ситуациях. Главный недостаток — тот, что при большом числе состояний и входных сигналов эта таблица становится плохо обозримой и неудобной в работе.
Более компактный и наглядный способ описания автомата — с помощью графа (или диаграммы) переходов.Вершины графа q соответствуют состояниям автомата; стрелка (дуга), ведущая из вершины qi в вершину qj, обозначает переход автомата из состояния qj в состояние qj, на этой же стрелке указан входной сигнал, вызывающий данный пере ход, и — после вертикальной черты — выходной сигнал, который при этом выдается. Если несколько входных сигналов вызывают один и тот же переход и выходной сигнал, они перечисляются на одной стрелке через запятую.
*| 0
Б | 0 Д | 1
Г,Д,*| 0
В, * | 0
|
А, Д | 1
|
|
|
Б | 0  | |||
 | |||
А,В,Г,Д| 0
А,Б,В,Г | 0
А,Б,В,Г,*|0
Рис.2
Граф переходов для табл. 2 приведен на рис. 2. На этом рисунке наглядно видно, что отпирающей последовательности соответствует путь из q1 в q4, где и открывается замок.
Формальное определение автомата, проиллюстрированное табл. 2 и рис. 2, предполагает, что время действия входного сигнала примерно равно времени смены состояний и следующий входной сигнал автомат получает после перехода в следующее состояние. Однако на практике может оказаться, что согласовать эти длительности трудно, так как время смены состояний зависит от физической природы и устройства автомата и, как правило, ограничено долями секунды. Длительность же входного сигнала зависит от внешних источников и не всегда подвластна разработчику.
Задания по варианту:
| Вход | А | Б | В | Г | Д | * | ||||
| Вариант 1 | ||||||||||
| Вариант 2 | ||||||||||
| Вариант 3 | ||||||||||
| Вариант 4 | ||||||||||
| Вариант 5 | ||||||||||
| Вариант 6 | ||||||||||
| Вариант 7 | ||||||||||
| Вариант 8 | ||||||||||
| Вариант 9 | ||||||||||
| Вариант 10 | ||||||||||
| Вариант 11 | ||||||||||
| Вариант 12 | ||||||||||
| Вариант 13 | ||||||||||
| Вариант 14 | ||||||||||
| Вариант 15 | ||||||||||
| Вариант 16 | ||||||||||
| Вариант 17 | ||||||||||