close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
УДК 62.52
Канд. техн. наук, доц. ДЕДЕГКАЕВА А. А.
СУПЕРПОЗИЦИОННАЯ РЕАЛИЗАЦИЯ
СИСТЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ
Статья посвящена построению последовательной декомпозиции систем логического
управления, при их конечно-автоматной интерпретации. Предложен способ разложения
системы по операции суперпозиции.
При конечно-автоматной интерпретации сложных систем логического управления для их
реализации часто бывает целесообразным блочный подход, при котором функционирование целого
представляется совместным функционированием некоторым образом взаимодействующих
составляющих (подавтоматов). Наиболее универсальным способом такого взаимодействия является
суперпозиция, которой соответствует последовательное соединение подавтоматов (рис. 1).
Универсальность такой реализации обусловлена тем, что системы управления, для которых
существуют другие способы реализации (параллельная одновременная работа подавтоматов с
раздельными входами, параллельная одновременная работа подавтоматов с общим входом и
параллельная неодновременная работа подавтоматов с раздельными входами), могут быть
реализованы суперпозицией, тогда как обратное неверно.
X
A
Y

X
A1
Z1
A2
Z2
…
Zn
An
Y
Рис. 1. Представление автомата последовательной работой подавтоматов.
Пусть задан автомат  = (, , , 1 ∈ , ( ∈ ⁄ ∈ )), где  – входной алфавит,  –
выходной
алфавит,

–
множество
состояний
автомата,
1 ∈  – начальное состояние, ( ∈ ⁄ ∈ ) – отображение множества  в себя, которое любому
состоянию  ∈  и каждой входной букве  ∈  сопоставляет состояние  ∈ , определяющее
функцию переходов φ(, ) и выходную букву  ∈ , определяющую функцию выходов (, ).
Требуется
представить
автомат
А
последовательной
работой
автоматов
1 = (, , , 1 ∈ , ( ∈ ⁄ ∈ )) и 2 = (, , , 1 ∈ , ( ∈  ⁄ ∈ )), что соответствует
разложению автомата по операции суперпозиции. Автоматы 1 и 2 будем называть
компонентными автоматами или компонентами разложения.
Для построения 1 предлагается использовать аппарат разбиений со свойством подстановки
̅̅̅2 , … , 
̅̅̅
(СП-разбиений) [1]. Разбиение π = {̅1 , 
 } на множестве  состояний автомата А обладает
свойством подстановки, если под действием любого входного сигнала автомат из состояний,
находящихся в одном блоке разбиения, переходит в состояния, также находящиеся в одном блоке.
(∀ ∈ )(∀ ,  ∈ )( ,  ∈ ̅̅̅
α )(φ( , ) ∈ ̅̅̅
β ) → (φ( , ) ∈ ̅̅̅
β )
Найти СП-разбиение можно с помощью графа условий соцветности вершин [2], который
строится путём преобразования квадрата графоида автомата, и позволяет находить подмножества
состояний автомата, совместное размещение которых в блоках разбиения возможно при
выполнении условий, накладываемых на размещение остальных состояний автомата.
Совокупность таких подмножеств с не противоречащими друг другу условиями задаёт СПразбиение на множестве вершин автомата. В основу этих процедур положено свойство
транзитивности отношения включения : (  )(  ) → (  ).
Пусть такое разбиение π1 найдено. Поставив блокам разбиения во взаимно-однозначное
соответствие состояния автомата А1 (̅ ↔  ), найдём множество переходов следующим образом:
(∀ ∈ )( ∈ ̅̅̅
α )(φ( , ) ∈ ̅̅̅
β ) → (φ1 (α , ) = β ),
где
φ1 (, ) – функция переходов автомата 1 .
x 1/
Каждому переходу назначим уникальную букву (выходной сигнал) из Z. Таким образом,
автомат А1 построен.
Далее строим автомат А2. Для этого на множестве состояний автомата А находим второе
разбиение π2 (не обязательно со свойством подстановки) такое, что пересечение любых двух
блоков разбиений π1 и π2 содержит не более одного элемента  ∈ . Каждому блоку разбиения π2
поставим во взаимно однозначное соответствие состояние автомата А2. В результате каждому
состоянию
∈
автомата
А
соответствует
пара
состояний
( ∈ ,  ∈ ), а каждому переходу автомата А соответствует пара переходов автоматов А1 и А2.
Для переходов автомата А2 входная буква  ∈  совпадает с выходной буквой соответствующего
перехода автомата А1, а выходная  ∈  с выходной буквой соответствующего перехода автомата
А, то есть: если  ↔ (α , δ ),  ↔ (β , σ ) и φ( , ) =  , γ( , ) = , φ1 (α , ) = β , γ1 (α , ) =
, то φ2 (δ , ) = σ , γ2 (δ , ) = .
Таким образом, автомат А2 построен.
Алфавит  может быть избыточным. Сократить алфавит можно обозначив те буквы, по
которым в А2 выполняется один и тот же переход с одним и тем же выходным сигналом, одной
буквой. Такое «переобозначение» возможно только в том случае, когда не приводит к
неоднозначности переходов в А2.
Рассмотрим, например, автомат  = (, , , 1 ∈ , ( ∈ ⁄ ∈ )), графоид которого
представлен на рис. 2. Требуется представить автомат А последовательной работой автоматов
1 = (, , , 1 ∈ , ( ∈ ⁄ ∈ ))
и
2 = (, , , 1 ∈
⁄
)).
,
(
∈


∈

x3 /y
y
1
/
x2
2
S1
x3/y1
Разбиение π1 = {̅̅̅̅̅̅̅,
2 , 6 , ̅̅̅̅̅̅̅}
3 , 5 на множестве состояний
1 , 4 ̅̅̅̅̅̅̅
автомата
S
обладает
свойством
подстановки. Каждому блоку
S2
S6
этого разбиения ставим в соответствие состояние автомата
x2 /y
1
1 : ̅̅̅̅̅̅̅
1 , 4 ↔ 1 ; ̅̅̅̅̅̅̅
2 , 6 ↔ 2 ; ̅̅̅̅̅̅̅
3 , 5 ↔ 3 .
x 2/
x4 /
y4
x 1/y 2
x4
/y
3
y2
x1/y1
S3
y3
S5
Множество переходов определяем следующим образом:
y1
x 4/
y3
x 4/
φ(1 , 3 ) = 2 → φ1 (1 , 3 ) = 2 ,
S4
φ(1 , 4 ) = 5 → φ1 (1 , 4 ) = 3 ,
x1/y2
φ(2 , 1 ) = 3 → φ1 (2 , 1 ) = 3
Рис. 2. Графоид автомата А.
/z
6
/z
3
x1
/z 5
1
∨x
/z 9
x4
Аналогично находятся остальные переходы.
x2
/z 2
x4
и т. д. каждому переходу назначаем выходной сигнал из Z.
Графоид, полученного в результате автомата 1 , представлен на рис. 3.
Далее находим разбиение
π2 на множестве S
x3/z1∨x2/z8
такое,
что
каждый
блок
x1/z7
x3/z11
содержит не более одного элемента
из каждого блока
разбиения π1 . Например π2 =
=
v1
v3
x2/z10∨x4/z4
{̅̅̅̅̅̅̅̅̅̅,
4 , 5 , 6 Отождествляем
блоки
этого
1 , 2 , 3 ̅̅̅̅̅̅̅̅̅̅}.
разбиения с состояниями автомата
A2 : ̅̅̅̅̅̅̅̅̅̅
1 , 2 , 3 ↔ 1 ,
4 , 5 , 6 ↔ 2 .
̅̅̅̅̅̅̅̅̅̅
Процесс
определения
множества
переходов поясним на примере
перехода
v2
φ(1 , 3 ) = 2 , γ(1 , 3 ) = 2 , ему
соответствует
переход
φ1 (1 , 3 ) = 2 ,
γ1 (1 , 3 ) = 1 и,
Рис. 3. Графоид автомата 1 .
следовательно,
φ2 (1 , 1 ) = 1 ,
γ2 (1 , 1 ) = 2 .
x3/z1∨x2/z8
x1/z7
x3/z11
x2/z10∨x4/z4
v3
x2
/z 2
x4
/z
6
v1
x1
/z
3
/z 5
1
∨x
/z 9
x4
v2
Графоид полученного таким образом автомата 2 , представлен на рис. 4.
z2/y3∨z4/y4
z1/y2∨z3/y2∨z5/y2∨z6/y1
z7/y2∨z8/y3∨z9/y1∨z3/y1∨z11/y2
w1
w2
z2/y3∨z10/y1
Рис. 4. Графоид автомата 2 .
Для сокращения алфавита Z воспользуемся следующими соображениями, т. к. φ2 (1 , 1 ) =
φ2 (1 , 3 ) = φ2 (1 , 5 ) = 1
и
γ2 (1 , 1 ) =
= γ2 (1 , 3 ) = γ2 (1 , 5 ) = 2 , а так же φ2 (2 , 3 ) = φ2 (2 , 9 ) = 2 и γ2 (2 , 3 ) = γ2 (2 , 9 ) =
1 , то обозначим 1 , 3 , 5 , 9, через 1 . Рассуждая аналогичным образом, обозначим 7 , 11 через
7 . Графоиды полученных в результате автоматов 1 и 2 представлены на рис. 5.
x3/z1∨x2/z8
x1/z7
x3/z7
x2/z10∨x4/z4
v3
z2/y3∨z4/y4
z1/y2∨z6/y1
z7/y2∨z8/y3∨z1/y1
w1
x1
/z 1
1
∨x
/z 1
x4
/z
1
x2
/z 2
x4
/z
6
v1
w2
v2
z2/y3∨z10/y1
Рис. 5. Графоиды компонентных автоматов.
Проиллюстрируем работу автомата  и последовательную работу автоматов 1 и 2 с
помощью табл. 1 и 2.
Таблица 1
Функционирование автомата А
3
1
2
4
2
4
1
4
2
2
4
3
2
6
1
4
1
3
…
5
…
…
…
…
Пусть на вход автомата , установленного в начальное состояние – 1, подаётся
последовательность букв, приведенная в первой строке табл. 1, тогда автомат последовательно
переходит в состояния, приведённые во второй строке. При этом на выходе появляется
последовательность букв, приведённая в третьей строке.
Пусть, теперь на вход автомата 1 , установленного в начальное состояние – 1 , поступает та
же последовательность букв (первая строка табл. 2), тогда автомат 1 последовательно переходит
в состояния, приведённые во второй строке. При этом на выходе появляется последовательность
букв, приведённая в третьей строке. Эта последовательность поступает на вход автомата 2 . В
результате чего автомат 2 переходит последовательно в состояния, приведённые в четвёртой
строке, а на выходе появляется последовательность букв, приведённая в пятой строке табл. 2.
Таблица 2
Функционирование автоматов  и 
3
1
1
1
2
4
3
4
1
4
1
1
7
2
2
2
1
8
2
3
2
3
10
2
1
4
1
2
1
3
…
2
…
2
…
…
…
…
…
…
Легко видеть, что подача на вход автоматов  и 1 одного и того же входного слова вызывает
появление одного и того же слова на выходе автоматов  и 2 . При этом пара состояний во второй
и четвёртой строках второй таблицы соответствует состоянию во второй строке первой таблицы.
Литература
1. Hartmanis J. Minimal feedback realization of sequential machines. IEEE Trans., EC-15, 1966. № 6.
2. Дзугкоева А. А., Дедегкаев А. Г. Размещение внутренних состояний автомата по компонентам
разложения при его параллельной декомпозиции / Известия высших учебных заведений. Северо-Кавказский
регион. Технические науки, 2010. № 1.
1/--страниц
Пожаловаться на содержимое документа