Случайно изменяющихся длительностей временных интервалов

Включается ключ 15 и импульс «Пуск», с шины 16 разрешается работа генератора 2. Генератор 2 работает на той же тактовой частоте, что и генератор 1. Далее работа формирователя происходит аналогичным образом, как и при реализации нескольких последовательностей временных интервалов, за исключением того, что длительности выходных временных интерва­лов изменяются случайно в пределах периода тактовой частоты. Формирователь [25] отличается расширенными функциональными возможностями и повышенной надежностью.

Синтез автоматов по декомпозированной

Схеме алгоритма

Устройства управления в информационно-измерительных и управляющих системах в немалой степени определяют быстродействие и достигаемую точность обработки информации. Поэтому выбор структурной организации автомата управления для информационно-управляющих систем является определяющим при достижении предельных характеристик в системах реального времени.

В системах проектирования управляющих автоматов ориентация идет либо на элементный базис средней интеграции, либо на ПЛМ, но с заданной структурной организацией самого автомата, представленной на рис. 83.

И в том и в другом случае стремятся упростить реализацию комбина­ционной схемы F₁ перехода автомата из одного состояния a(t) в другое a(t + l). Это достигается различными способами минимизации систем буле­вых функций или декомпозицией систем булевых функций для их вложе­ния в ПЛМ. Не отвергая последнего пути, заметим, что подчас снижения объема ПЛМ можно добиться на более ранних этапах проектирования, т.е. еще до получения самой системы булевых функций.

Как известно, объем ПЛМ определяет число его входов (m) в первую очередь, т.к. число термов (k) лишь в редких случаях является ограничивающим фактором, а число выходов (n) обычно равно m. При синтезе ко­нечных автоматов с заметным числом (q ~ 8–10) логических условий (α₁, α₁, …, α _q) и числом внутренних состояний ≤2 ^r, представленных двоичны­ми ко­дами (x ₁, x ₂, …, x_r), общая разрядность на входе ПЛМ (ПЗУ или ПЛИС) опреде­лится как сумма (r + q).

На рисунке 83 обозначено:

- a(t) и a(t + 1) – регистры памяти состояний;

- { α } – регистр памяти внешних логических условий α;

- F₁ – программируемая логическая матрица (ПЛМ), постоянное запоминающее уст­ройство (ПЗУ) или программируемая логическая интегральная схема (ПЛИС);

- ГИ – генератор тактовых импульсов;

- ДС – статический (без синхронизации) дешифратор;

- F₂ – схема формирования выходных управляющих сигналов А₁, А₂,..., А _z.

При r = (7÷5) даже для q = (5÷8) величина (r + q) в 1,5 раза превосходит число входов наиболее распространенных ПЛМ (m = 8), а переход к ПЛМ с m = 16 может оказаться неоправданным по экономическим сообра­жениям.

Приступим к синтезу автомата, начиная с анализа алгоритма управ­ления. Рас­смотрим подход к синтезу, основанный на декомпозиции исход­ного алгоритма. Излагаемый ниже подход определяет одну из стратегий декомпозиций и критерии для определения глубины декомпозиции.

Граф переходов автомата Мура для алгоритма на рисунке 84 пред­ставлен на ри­сунке 85. Даже для простого примера (рис. 84) r = 4, q = 5, т.е. n = r + q = 9.

Обобщающая информация по примеру рис. 84 приведена в табл. 31, 32, 33.

Рассмотрим предлагаемую процедуру декомпозиции:

1. Будем разделять алгоритм (декомпозировать) на части с приблизительно равным количеством управляющих операторов А _i. По методу дихотомий сначала исходный алгоритм разделим пополам, затем каждую половину еще раз пополам и т.д. В зависимости от сложности алгоритма количество дихотомий может оказаться равным 3–4, а для простых достаточно ограничиться двумя шагами.

2. Границу к разделению определим не только по количеству операто­ров, но учтем также логическую структуру алгоритма. Будем считать возможной границу раз­деления либо сразу после решающего (логического) оператора, либо после пер­вого последующего за или за управляю­щего оператора.

С учетом пункта 1 количество присоединенных управ­ляющих операторов может быть равно 2–3.

3. Рассматривая случай декомпозиции после с «присоединенным» оператором A _i, следует стремиться избегать декомпозиции перед оператором A _i, имеющим более одного входа.

4. Не декомпозируется алгоритм по связям от к .

5. В зависимости от вида алгоритма первоначальный шаг декомпозиции целесообразно начать с деления не на две, а на три части.

Рис. 83

Таблица 31

fi	F1	А i	F2
	τ a11
	τ a0		а1 + а5
			а2 + а6
			а3 + а9
			а4 + а11
	τ a4 + τ a13		а7 + а10 + a12
			а8 + а13
	τ a7
	τ a12

Таблица 32

			А	F2
a i	fi (F1)	a i	fi (F1)
		–		–
	τ a0
			τ a2
	τ a4 + τ a7
	τ a6	–		–

Таблица 33

		B1
		B2
		В3
		B4

На основе изложенной стратегии алгоритм рис. 84 на первом шаге декомпо­зиции будет представлен двумя частями алгоритма рис. 86 а, б, которым соответствуют графы переходов (рис. 86 а, б).

Количество состояний в автомате равно 8 на рис. 86 а, для рис. 86 б равно 7, следовательно, вместо r = 4 для графов рис. 85 величина r = 3. Для функций переходов и выходов получим табл. 32.

Таким образом, (r + q) для первого шага декомпозиции станет равным 3 + 3 = 6. Следует заметить, что здесь появилась дополнительная логическая переменная β, а затем это значение изменяется после реализации первого декомпозированного алгоритма. Т.е. уже первый шаг декомпозиции ока­зался результативным и снижает количество входов с 9 до 7.

Как для исходного, так и для декомпозированного алгоритма нет необходимости подсчитывать и сравнивать (табл. 31. и 32) число термов (в реализации количество элементов «И», «ИЛИ»), как это следовало бы делать при реализации на логике средней интеграции.

После второго шага декомпозиции получим четыре алгоритма В₁, В₂,..., В₄, выбор которых определяется двумя дополнительными логическими условиями (табл. 33). В таблице 31 представлены функции переходов, в табл. 32 указаны переходы к декомпозированным автоматам. Для оценки r и q по рис. 86 можно не строить графы, но сразу опре­делить таблицы переходов, т.к. мало число состояний. Легко видеть, что r + q = 2 + 2 = 4. Таким образом, если исходному графу соответст­вует автомат, для кото­рого число входных переменных в ПЛМ равно 9, то после второго шага декомпо­зиции число входных переменных уменьши­лось до 4. Фактически уменьшение числа входов будет меньше, т.к. необ­ходимо учесть появление двух логических условий и , которые не подлежат сокращению, как a _i. Но и с учетом число входящих перемен­ных уменьшилось с 9 до 6, т.е. число возможных комбинаций по входам ПЛМ умень­шилось в 8 раз с 512 до 64.

Рис. 84

Рис. 85

Рис. 86

Рис. 87

Рис. 88

Рис. 89

На рисунке 89 представлена схема автомата, исполненного по декомпозирован­ной схеме. Для наглядности индексы для X _i и α_j взяты кон­кретными из данного примера. Как видно из рисунка 89, появилась схема F₃, но это простейшее уст­ройство логического объединения (α ₁ α ₄), а также (α ₁ α ₅) по одному из условий и . Изменилась и схема F₂, т.к. в ней теперь учитываются значения , но поскольку убран дешифратор, схема F₂ осталась того же уровня сложности, что и для рисунка 83.

Число входов (m) и выходов (n) в новой ПЛМ для F₁ на рисунке 89 уменьшено по сравнению с рис. 83, как указано ранее, с 9 до 6, что при­водит к упрощению схемы F₁ в 8 раз (если оценивать по количеству воз­можных адресных комбинаций).

Для более сложных алгоритмов по срав­нению с алгоритмом рис. 84 предлагаемая методика позволяет получить больший эффект. Например, при реализации автомата управления стендом контроля ПЗУ с ультрафиолетовым старанием удается снизить количество входов ПЛМ в автомате с 18 до 11, т.е. уменьшить число комбинаций в 128 раз. Это дает возможность реализации автомата не на сложной ПЛИС, а на простой ПЛМ или ПЗУ небольшого объема. Такое решение обеспечивает более низкое электропотребление при увеличении надежности и экономических показателей. [23, 32].