Синтез цифровых автоматов. Захаров Н.Г - 22 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

21
Со всяким преобразованием информации связывается представление о его
сложности.
По критерию сложности целесообразно выделить простейшие преобразова-
ния информации. Простейшими или побуквенными, будем называть преобразования,
заключающиеся в замене каждой буквы исходного алфавита некоторой определенной
комбинацией букв нового алфавита, имеющего заранее фиксированную, одинаковую
для всех букв длину.
Пример 3. Исходная информация – произвольное слово в русском алфавите.
Преобразование информации состоит в замене каждой буквы алфавита порядковым
номером, записанным в десятичной системе счисления. При этом для соблюдения ус-
ловия равенства длин комбинаций буквенного алфавита, представляющих буквы ста-
рого алфавита, необходимо первую букву обозначать комбинацией 01, вторую – 02 и
т. д. В результате такого преобразования слово «дом» преобразуется в слово
«051412». Это преобразование является не только простейшим, но и эквивалентным.
Пример 4. Исходная информация – произвольное целое десятичное число (сло-
во в алфавите, состоящем из десяти цифр 0, 1, 2, ..., 9). Преобразование информации
состоит в замене каждой четной цифры нулем, а нечетной – единицей. Слово «125»
при этом преобразуется в слово «101», слово «0342» – в слово 0100 и т. д.
Отсюда видно, что с помощью простейших преобразований, информацию, за-
данную в любом конечном алфавите, можно записать в алфавите, содержащем только
две буквы. Такой алфавит называют «двоичным алфавитом», а две его буквы будем
обозначать нулем и единицей. Эти преобразования носят специальное название дво-
ичного кодирования исходной информации.
Таким образом, при различных преобразованиях информации можно, не нару-
шая общности, предполагать, что как исходная, так и заключительная информация
задана в некотором стандартном (например, двоичном) алфавите.
1.5.3. Способы задания автоматов
Абстрактные автоматы задаются с помощью таблиц переходов (выходов), гра-
фов, матриц переходов.
Таблица переходов (таблица выходов) автомата Мили представляет собой таб-
лицу, в которой левый столбец обозначается входными сигналами, а верхняя строка –
состояниями, начиная с начального состояния. На пересечении строки и столбца ука-
зывается следующее состояние, в которое переходит автомат (в таблице переходов)
или выходной сигнал, выдаваемый им (в таблице выходов).
Представим автоматы Мили и Мура табличным способом.
Описание работы автомата Мили таблицами переходов и выходов иллюстриру-
ется на примере автомата А1 (рис. 1.5): Х – алфавит входных сигналов; Y – алфавит
выходных сигналов; Q – алфавит состояний; δ – функция переходов; λ – функция вы-
ходов.

Страницы