5. Блок-схемы алгоритмов работы устройств управления

Рис 1. Блок-схема алгоритма сложения чисел с фиксированной точкой

Рис.2. Блок-схема алгоритма сложения чисел с плавающей точкой

Рис.3. Блок-схема алгоритма выравнивания порядков

Рис.4. Блок-схема алгоритма нормализации

Рис.5. Блок-схема алгоритма

умножения

)^* - действия и условия

зависят от метода

умножения.

Рис.6. Блок-схема алгоритма деления с восстановлением остатка

Рис.7. Блок-схема алгоритма деления без восстановления остатка

Методика и примеры синтеза автомата

1. Абстрактный синтез

1.1 Постановка задачи

Абстрактный синтез включает в себя разработку алгоритма работы автомата и составление его формального описания в виде автоматных таблиц или в виде графа переходов. Алгоритм наиболее удобно и наглядно представлять в виде блок-схем. Разработка алгоритмов и блок-схем является наиболее творческой частью работы и плохо поддаётся формализации. Примеры блок-схем алгоритмов приведены на рис. 1 – 5. Их можно пытаться усовершенствовать.

По разработанной блок-схеме описание работы автомата проще всего составлять в виде графа переходов. Вид графа зависит от того, проектируется автомат Мура или автомат Мили:

Автомат Мили Автомат Мура

x_t

y_t+1

y_t

f₁

f₁

z_t+1

z_t+1

x_t

f₂

f₂

y_t = f₁(x_t, z_t) y_t+1 = f_t(z_t+1)

z_t+1 = f₂(x_t, z_t) z_t+1 = f₂(x_t, z_t)

Рис. 8. Структуры автоматов Мили и Мура

Метод построения графа переходов наглядней продемонстрировать на примере. Рассмотрим синтез автомата сложения двоичных чисел с фиксированной точкой (см. рис. 1).

1.2. Автомат Мура

Синтез автомата Мура несколько проще, так как для этого автомата выходной сигнал зависит только от внутреннего состояния, поэтому можно внутренние состояния кодировать так, что y_t = z_t .Тогда внутренние состояния совпадают с операциями или действиями по алгоритму (они закодированы значениями ₀ … ₅). Состояния автомата представляются на графе узлами, а переходы – дугами. Всего шесть узлов (см. рис. 9.).

Переходы определяются условиями, т.е. условными блоками на блок-схеме. Из начального состояния ₀ автомат при различных условиях может переходить в состояния ₁, ₂, ₃. Как видно из рис.1, переход ₀  ₁ происходит при условии х₁, переход ₀  ₂ – при условии х₁ х₂ и переход ₀  ₃ – при условии х₁ х₂. Из состояния ₃ возможны переходы в состояния ₄ и ₅. Переход ₃  ₄ происходит при условии х₃, а переход ₃  ₅ – при условии х₃. Из состояний ₁, ₂, ₄, ₅ возможны только по одному переходу, причём без всяких условий (условие «1»), просто на следующем пакте.

Рис. 9. Граф автомата Мура для управления сложением чисел с фиксированной тачкой