- •1. Представление числовой информации в цифровых автоматах
- •1.1. Выбор системы счисления для представления числовой информации
- •1.2. Представление отрицательных чисел
- •1.3. Формы представления чисел
- •2. Арифметические основы цифровых автоматов
- •2.1. Формальные правила сложения и вычитания двоичных чисел
- •2.2. Сложение чисел, представленных в форме с фиксированной запятой
- •2.3.Переполнение разрядной сетки
- •2.4. Сложение чисел, представленных в форме с плавающей запятой
- •3. Умножение двоичных чисел
- •3.1. Методы умножения двоичных чисел
- •3.2. Умножение чисел, представленных в форме с фиксированной запятой в прямом коде
- •3.3. Умножение чисел, представленных в форме с фиксированной запятой в дополнительном коде
- •3.4. Умножение чисел, представленных в форме с фиксированной запятой в обратном коде
- •3.5. Умножение чисел, представленных в форме с плавающей запятой
- •3.6. Ускорение операции умножения
- •5. Цифровые автоматы
- •5.1. Основные понятия
- •5.2. Языки описания цифровых автоматов
- •5.3 Проектирование конечных автоматов
5.2. Языки описания цифровых автоматов
В зависимости от задания функций переходов и выходов ( и ) в настоящее время выделяют два класса языков – начальные языки и стандартные или автоматные языки. В начальных языках автомат описывается на поведенческом уровне, т.е. функции переходов и выходов обычно в явном виде не задаются. Функционирование автомата описывается в терминах входных и выходных последовательностей, реализуемых операторов или управляющих последовательностей сигналов, воздействующих на операционный автомат. В автоматных языках функционирование автомата задается путем явного задания функций переходов и выходов.
Начальные языки. Среди начальных языков следует выделить язык регулярных выражений алгебры событий, язык логических схем алгоритмов, язык граф-схем алгоритмов.
Язык регулярных выражений алгебры событий. Для заданного конечного множества входных букв при построении регулярного выражения используются три операции над событиями (две бинарные и одна унарная):
- объединение (дизъюнкция);
- умножение (конкатенация);
- итерация (обозначается также А*).
Выражение, построенное из букв алфавита X и из символов операций объединения, умножения и итерации с использованием соответствующим образом круглых скобок, называется регулярным выражением в алфавите X. Всякое регулярное выражение R определяет некоторое событие S. Регулярным событием S называется событие, полученное из элементарных событий (однобуквенных слов ) применением конечного числа раз операций дизъюнкции, умножения и итерации.
Пусть необходимо описать автомат, выдающий сигнал всякий раз, когда происходит изменение входной буквы с на , т.е. сигнал должен выдаваться в ответ на любые входные последовательности, кончающиеся последовательностью . Такое событие записывается как ( ). Тогда событие , в ответ на которое должен выдаваться сигнал , будет описываться регулярным выражением: .
Язык логических схем алгоритмов. В 1953 г. А.А. Ляпунов предложил записывать алгоритмы в виде конечной строчки, состоящей из символов операторов, логических условий и верхних и нижних стрелок, которым приписаны натуральные числа.
Выполненная таким образом запись алгоритма называется логической схемой алгоритма (ЛСА).
Логические схемы алгоритмов удовлетворяют следующим условиям:
содержат один начальный ( )и один конечный ( ) оператор;
перед оператором и после оператора стрелок быть не должно;
вслед за каждым логическим условием стоит верхняя стрелка;
не существует двух одинаковых (с одинаковыми цифрами) нижних стрелок;
для каждой нижней стрелки должна быть, по крайней мере, одна соответствующая ей (с одинаковой цифрой) верхняя стрелка;
для каждой верхней стрелки должна быть точно одна соответствующая ей (с одинаковой цифрой) нижняя стрелка.
Описание функционирования автомата с помощью ЛСА рассмотрим на следующем примере:
(5.4)
Эта ЛСА имеет оператора начала и конца ( и ), пять операторов ( ) и три логических условия ( ). Начальному оператору соответствует некоторое начальное состояние автомата, при котором никакие микрооперации не выполняются. Если в начальном состоянии на первый вход устройства придет сигнал, равный единице ( ), то устройство перейдет в новое состояние, в котором выполняется оператор - первый справа после логического условия , а затем проверяется логическое условие .
Если же , то выходим по верхней стрелке и входим по нижней стрелке с той же цифрой на проверку условия , минуя выполнения оператора .
Если , то переходим к выполнению оператора . Если же , то выполняются операторы и и проверяется условие . Если , то оператор не выполняется, происходит переход к оператору . После выполнения оператора происходит переход к конечному оператору, т.е. работа дискретного устройства заканчивается.
Язык граф-схем алгоритмов. Граф-схема алгоритма – ориентированный связный граф, содержащий одну начальную вершину, произвольное число условных и операторных вершин и одну конечную вершину.
Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет, условная вершина имеет два выхода, помеченных символами 1 и 0.
Граф-схема алгоритма удовлетворяет следующим условиям:
входы и выходы вершин соединяют друг с другом с помощью линий, направленных всегда от выхода ко входу;
каждый выход соединен только с одним входом;
любой вход соединяется, по крайней мере, с одним выходом;
любая вершина графа лежит, по крайней мере, на одном пути из начальной к конечной вершине;
в каждой условной вершине записывается один из элементов множества логических условий , разрешается в различных условных вершинах запись одинаковых элементов множества Z;
в каждой операторной вершине записывается один из элементов множества операторов , разрешается в различных операторных вершинах запись одинаковых элементов множества V.
На рис. 5.3 представлен граф-схема алгоритма, описанного выражением (5.4).
Рисунок 5.3 Граф схема алгоритма
Язык ГСА используется очень часто при описании алгоритмов функционирования, как самого цифрового автомата, так и программ, выполняющих то, или иное действие.
Автоматные языки. Среди автоматных языков наиболее распространены таблицы, графы и матрицы переходов и выходов.
Таблица переходов (выходов) представляет собой таблицу с двойным входом, строки которой пронумерованы входными буквами, а столбцы - состояниями. На пересечении указывается состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов).
Описание работы автомата Мили таблицами переходов и выходов показано в табл.5.1 и 5.2 соответственно.
Таблица 5.1 Таблица переходов Таблица 5.2. Таблица выходов
Входной сигнал |
Состояние автомата |
|
Входной сигнал |
Состояние автомата |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На пересечении столбца и строки в таблице переходов ставится состояние , в которое автомат переходит из состояния под действием сигнала , а в таблице выходов соответствующий этому переходу выходной сигнал
Иногда при задании автомата Мили используют одну совмещенную таблицу переходов и выходов, в которой на пересечении столбца и строки записывают в виде следующее состояние и выдаваемый выходной сигнал. Совмещенная таблица имеет вид (табл.5.3)
Таблица 5.3. Совмещенная таблица переходов и выходов
Входной сигнал |
Состояние автомата |
||
|
|
|
|
|
|
|
|
|
|
|
|
Часто автомат задают с помощью графа автомата. Этот язык удобен и нагляден. Граф автомата - ориентированный граф, вершины которого соответствуют состояниям, а дуги переходам между ними. Две вершины графа автомата и (исходное состояние и состояние перехода) соединяются дугой, направленной от к , если в автомате есть переход из в , т.е. если при некотором . Дуге ( , ) графа автомата приписывается входной сигнал и выходной сигнал . На рис.5.4 приведен граф автомата, описанный табличным способом.
Рисунок 5.4. Граф автомата Мили