Часть 2.

Раздел 2. Синтез микропрограммных автоматов

ЛЕКЦИЯ 5.

5.1. Объединение алгоритмов

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

Рассмотрим одну из методик построения объединенного алгоритма, которая может быть использована в случае, если задан жесткий порядок выполнения частных алгоритмов, т.е. после L₁ всегда должен выполняться L₂ , затем L₃ и т.д.

Чтобы определить какой из частных алгоритмов должен выполняться в заданный момент времени вводятся дополнительные ЛУ r_l, которые, по сути, являются признаками выполнения того или иного частного алгоритма. Если имеется s частных алгоритмов, то вводится и s дополнительных ЛУ r_l (l=1, 2, ... , s). В качестве генератора дополнительных ЛУ r_l используется счетчик номеров выполняемых алгоритмов с дешифратором на s выходов. На каждом l-ом выходе дешифратора формируется значение дополнительного ЛУ таким образом, что при выполнении l-го частного алгоритма на l-ом выходе будет ноль, а на остальных выходах единицы.

Кроме того, вводится дополнительный оператор R, который означает запись единицы в счетчик номеров выполняемых алгоритмов.

Методику построения объединенного алгоритма рассмотрим на примере логического устройства, имеющего следующие условия функционирования.

Пример 4.4. Получить объединенную ЛСА функционирования устройства, которое должно подавать сигнал на включение аппаратуры при наборе на клавиатуре шифра «1262».

Решение.

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

Для составления алгоритма введем следующие операторы.

А_о – оператор начала, подачи питания на устройства;

А – нажатие кнопки;

Н – фиксация неправильного нажатия;

В – включение аппаратуры;

Т – сигнализация неправильного нажатия;

R – переход к выполнению следующего алгоритма, запись единицы в счетчик.

К роме этих операторов необходимо ввести логические операторы:

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

Результатом выполнения последнего алгоритма является срабатывание исполнительных устройств. Поэтому он несколько отличается от предыдущих пяти. Кроме того, необходимо ввести еще одно логическое условие

Объединение алгоритмов проводится по следующей методике:

1. Определяется порядок выполнения алгоритмов (В рассматриваемом примере порядок жестко определен изначально)

2. Каждому алгоритму ставится в соответствие дополнительное логическое условие r₁, r₂, r₃, r₄

3. Составляется таблица, имеющая s столбцов (где s – количество алгоритмов) и n + 2k строк, где n – количество функциональных операторов, от которых возможен переход, k – количество основных логических условий (табл.9.2.).

4. В каждой строке, соответствующей оператору А_i в столбцах, соответствующих l-му алгоритму, ставится оператор, выполняемый в l-м алгоритме после А_i. Если в частных алгоритмах оператор R не использовался, то он ставится вместо оператора А_к в случаях, если предполагается выполнение следующего алгоритма.

5. В каждой строке оператор, встречающийся чаще всего, помечается (перечеркивается). Если два или несколько операторов встречаются одинаково часто, то помечается любой из них. Если в строке один оператор, то он помечается.

6. После того, как будут рассмотрены все строки таблицы, записывается объединенная ЛСА. Для этого выполняются следующие действия.

Таблица 4.2 - Таблица переходов

	r1	r2	r3	r4	r5	r6
А0	А	А	А	А	А	А
А
Н	R	R	R	R	R
В						Ак
Т						Ак
р1	R
	Н
р2		R		R
		Н		Н
р3			R		R
			Н		Н
р4						В
						Т
р5						Т
						р4

После записи оператора А_i рассматривается строка оператора А_i (небольшая особенность – после А₀ записывается оператор R, но рассматривается строка А₀).

Если в строке есть непомеченные операторы, то после оператора записываются дополнительные логические условия r_l, соответствующие столбцам, в которых есть не вычеркнутые операторы, при этом стрелки от логических условий показывают переход именно к непомеченным операторам.

После дополнительных логических условий записывается помеченный оператор А_j. Затем рассматривается строка оператора А_j и все повторяется, пока не будут рассмотрены все строки.

Если вычеркнутый оператор уже есть в записанной части ЛСА, то второй раз он не записывается, а переход к нему осуществляется с помощью оператора безусловного перехода ω↑ⁱ. После оператора ω выбирается любой еще не записанный оператор, к которому был указан переход по стрелке от какого-нибудь логического условия. То есть, после ω ставится нижняя стрелка, записывается оператор А_j и рассматривается его строка.

В результате применения этих правил в рассматриваемом примере будет получена следующая объединенная ЛСА.

При первоначальном составлении ЛСА, чтобы избежать ошибок, в качестве индексов верхних и нижних стрелок рекомендуется использовать обозначения операторов. Затем индексы нумеруются.

(4.12)

После получения объединенной ЛСА (L_) проводится проверка на детерминированность. Кроме того, L_ должна обеспечивать выполнение следующих условий:

любой оператор А_i (i = 0,1,….к), входящий хотя бы в одну частную ЛСА, входит ровно один раз в L_;

если в L_ подставить фиксированные значения r₁, r₂, …,r_s, соответствующие l-ой частной ЛСА L_l, то L_ превратится в L_l.