Студопедия — Композиция автоматов
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Композиция автоматов






К операциям композиции (объединению) относятся известные три соединения: последовательное, параллельное, соединение с обратной связью и соединение в сеть.

Располагая совмещенными таблицами переходов, выходов исходных цифровых автоматов А1 и А2, нужно при старте из любого предыдущего состояния определить новое состояние объединенного автомата А и его выходной сигнал соединения.

 

Последовательное соединение автоматов

Последовательное соединение автоматов рассмотрим на примере схемы, представленной на рисунке 2.

 

 

Рисунок 2 Последовательная схема соединения

 

Исходные автоматы - это автоматы А1 и А2, а результирующий – автомат А, которые описываются множествами

 

А1 = {Х1, Y1, S1, d1, l1},

А2 = {Х2, Y2, S2, d2, l2}, (1.7)

А = {Х, Y, S, d, l}.

 

Из рисунка 2 следует следующее равенство входных и выходных слов (сигналов):

 

Х1 = Х; Y1 = X2; Y2 = Y,

 

где Х1 – входной алфавит автомата А1;

Х2 – входной алфавит автомата А2;

Х – входной алфавит объединенного автомата А;

Y1 - выходной алфавит автомата А1;

Y2 - выходной алфавит автомата А2;

Y - выходной алфавит объединенного автомата А.

Алфавитом состояний объединенного автомата S будет произведение алфавитов состояний первого S1 и второго S2 автоматов S = S1 × S2.

Тогда для любого состояния объединенного автомата S {(s1i × s2j) Î S, где s1i Î S1 а s2j Î S2} должно выполняться условие:

 

d((s1i × s2j), х) = (d1(s1i, х 1) × d2(s2j, l1(s1i, х 1), х)), (1.8)

 

l ((s1i × s2j), х) = l2(s2j, l1(s1i, х 1)), (1.9)

 

где d1, d2 и d функции перехода первого автомата, второго автомата и объединенного автомата соответственно;

l1, l2 и l - функции выхода первого автомата, второго автомата и объединенного автомата соответственно.

Докажем справедливость вышеприведенных равенств.

Состояние объединенного автомата будет определяться функцией перехода d

sк = d((s × s), х). (1.10)

 

Состояние автомата А1 определяется функцией перехода d1

 

s = d1(s1i, х 1). (1.11)

 

Состояние автомата А2 определяется функцией перехода d2

 

s = d1(s2j, х 2). (1.12)

 

При условии, что х 2 = y1 и с учетом равенства y1 = l1(s1i, х 1) выражение (1.11) примет вид

 

……… s = d1(s2j, l1(s1i, х 1)). (1.13)

 

Подставив выражения (1.10), (1.11) и (1.13) в уравнение (1.8) получим выражение функции переходов объединенного автомата.

Аналогично проведем доказательства для функции выхода объединенного автомата.

yк = l ((s1i × s2j), х).

y1к = l1(s1i, х 1), y2к = l2(s2j, х 2).

При условии, что х 2 = y1 получим y = l2(s2j, l1(s1i, х 1)).

Исходя из схемы последовательного соединения видно, что yк = y, отсюда l ((s1i × s2j), х) = l2(s2j, l1(s1i, х 1)), что соответствует выражению (1.8) функции выхода объединенного автомата.

Изложенные теоретические положения проиллюстрируем на примере автоматов Мили.

Совмещенные таблицы переходов и выходов для А1, А2 представлены в таблицах13 и 14 соответственно.

Таблица 13 Таблица 14

  s11 s12 s13
х 11 s11/ y 11 s12/ y 12 s13/ y 12
х 12 s13/ y 11 s13/ y 11 s12/ y 11
  s21 s22
х 21 s21/ y 21 s21/ y 22
х 22 s22/ y 22 s21/ y 21

 

Пусть для последовательного соединения заданы предыдущие состояния объединенного автомата s1 (s11, s21) при входном сигнале х 12.

Алгоритм последовательного соединения автоматов можно сформулировать следующим образом:

- начать;

- перебирать все состояния S;

- по состоянию S определить пару состояний автоматов А1 и А2 (sa1, s a2);

- по входному сигналу x определить новое состояние автомата А1 sa1, и его выходной сигнал y a1;

- по выходному сигналу автомата А1 y a1, который является входным сигналом автомата А2, определить новое состояние автомата А2 s a2, и выходной сигнал автомата А2 y a2;

- по состояниям автоматов А1 и А2 (sa1, s a2) определить новое состояние объединенного автомата s;

- выходной сигнал автомата А2 считать выходным сигналом объединенного автомата А y;

- продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния;

- закончить.

По таблице 13 из состояния s11 по сигналу х 12 первый автомат А1 перейдет в состояние s13. На выходе автомата А1 будет сигнал y 11, который равен входному сигналу автомата А2, (). В соответствии с таблицей 14 по этому сигналу и исходному состоянию s21 автомат А2 перейдет в состояние s21 и на выходе выдаст сигнал y21, который будет являться выходным сигналом объединенного автомата y1 (y21 = y1).

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

Должно учитываться взаимно однозначное соответствие между номером выходного сигнала одного исходного автомата и номером входного сигнала другого автомата.

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

Состояния s13, s21 определяют новое состояние s5, выходной сигнал уже известен, и соответствует y1.

В результате последовательного соединения автоматов А1 и А2, заданных в таблицах 13 и 14 соответственно, получается результирующий автомат А. При необходимости следует составить совмещенную таблицу переходов и выходов объединенного автомата А, представленной табл. 15.

Таблица 15

d/l s1 (s11, s21) s2 (s11, s22) s3 (s12, s21) s4 (s12, s22) s5 (s13, s21) s6 (s13, s22)
х 1(х 11) s1(s11, s21) / y 1 s1(s11, s21) / y 2 s4(s12, s22) / y 2 s3(s12, s21) / y 2 s6(s13, s22) / y 2 s5(s13, s21) / y 1
х 2(х 12) s5(s13, s21) / y 1 s5(s13, s21) / y 2 s5(s13, s21) / y 1 s5(s13, s21) / y 1 s3(s12, s21) / y 1 s3(s12, s21) / y 2

 

Параллельное соединение автоматов

Параллельное соединение автоматов рассмотрим на примере схемы, представленной на рисунке 3.

 

 


Рисунок. 3 Параллельное соединение автоматов

Исходные автоматы - это автоматы А1 и А2, а результирующий – автомат А, которые описываются множествами (1.7).

Из рисунка 3 следует следующее равенство входных и выходных слов (сигналов) параллельного соединения автоматов:

 

Х1 = Х2 = Х; Y = F (Y1; Y2), S = S1 × S2. (1.14)

 

F – комбинационная логическая функция, реализованная на логических элементах, устанавливающая закон формирования выходного сигнала объединенного автомата А.

Тогда для любого состояния объединенного автомата А

S {(s1i × s2j) Î S, где s1i Î S1 а s2j Î S2}

должно выполняться условие

 

d((s1i × s2j), х) = (d1(s1i, х1), d2(s2j, х2)), (1.15)

 

l ((s1i × s2j), х) = F (l1(s1i, х1), l2(s2j, х2)), (1.16)

 

где d1, d2 и d функции перехода первого автомата, второго автомата и объединенного автомата соответственно;

l1, l2 и l - функции выхода первого автомата, второго автомата и объединенного автомата соответственно.

Изложенные теоретические положения проиллюстрируем на примере автоматов Мили. Совмещенные таблицы переходов и выходов для А1, А2 представлены в табл.13 и 14 соответственно.

Для параллельного соединения пусть будут заданы начальное состояние s5 (s13, s21) и входной сигнал х 2.

Оба автомата работают одновременно под действием одного и того же входного сигнала х 2. Преобразователь F преобразует выходные сигналы автоматов А1 и А2 во множество выходных сигналов итогового автомата А:

y = F (y а1, y а2).

 

Функция преобразования F отражена в табл. 16.

Таблица 16

F y 11 y 12
y 21 y 1 y 2
y 22 y 2 y 3

 

Алгоритм функционирования параллельного соединения автоматов А1 и А2 можно сформулировать следующим образом:

- начать;

- перебирать предыдущие состояния объединенного автомата А(s);

- по состоянию s определить предыдущие состояния s1i и s2j;

- по сигналу x определить данные состояния s1i и s2j, выходные сигналы y 1i и y 2j;

- по s1i и s2j определить данное состояние объединенного автомата si;

- по y 1i и y 2j определить данный выходной сигнал y i;

- продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния;

- закончить.

Первый автомат А1 из состояния s13 переходит в состояние s12, и на выходе выдает сигнал y11 (табл.13), второй автомат А2 из состояния s21 переходит в состояние s22, и на выходе выдает сигнал y22 (табл. 14). Объединенный автомат переходит в новое состояние s4 (s12, s22). В соответствии с табл. 16 на выходе формируется сигнал y2.

В результате параллельного соединения автоматов А1 и А2, заданных в табл. 13 и 14 соответственно, получается результирующий автомат А, совмещенная таблица переходов и выходов которого представлена в табл. 17.

Таблица 17

d/l s1(s11, s21) s2 (s11, s22) s3 (s12, s21) s4 (s12, s22) s5 (s13, s21) s6 (s13, s22)
х 1 s1(s11, s21) / y 1 s1(s11, s21) / y 2 s3(s12, s21) / y 2 s3(s12, s21) / y 3 s6(s13, s21) / y 2 s5(s13, s21) / y 3
х 2 s6(s13, s22) / y2 s5(s13, s21) / y1 s6(s13, s22) / y2 s5(s13, s21) / y 1 s3(s12, s22) / y 2 s3(s12, s21) / y 1

Соединение автоматов с обратной связью

Соединение автоматов с обратной связью рассмотрим на примере схемы, представленной на рисунке 4.

 

 

 

Рисунок 4 Соединение автоматов с обратной связью

Исходные автоматы А1 и А2 и объединенный автомат А описываются множествами (1.7).

Из рисунка 4 следует равенство входных и выходных слов (сигналов) при соединении автоматов с обратной связью:

 

Х1 = F (Х; Y2), X2 = Y1, Y = Y1.

 

Автоматы А1 и А2 заданы таблицами переходов и выходов, представленными в таблицами 18 и 19.

  s11 s12 s13     s21/ y 21 s22/ y 22
х 11 s13/ y 11 s12/ y 12 s11/ y 13   х 21 s21 s22
х 12 s12/ y 13 s13/ y 11 s12/ y 12   х 22 s22 s21
          х 23 s21 s22

Таблица 18 Таблица 19

 

В соответствии с приведенными равенствами и функций переходов и выходов автоматов А1 и А2 (табл. 13 и 14) входной сигнал автомата А1 будет определяться выражением

 

Х1 = F1 (Х, Y2) = F (Х, d2(s2j, х2)) = F (Х, d2(s2j, l1(s1i, х1))).

 

Алфавитом состояний объединенного автомата S будет произведение алфавитов состояний первого S1 и второго S2 автоматов

 

S = S1 × S2.

 

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

В результате соединения автоматов А1 и А2 с обратной связью, получается результирующий автомат А, совмещенную таблицу переходов и выходов которого следует составить по нижеприведенному алгоритму.

В данном соединении имеется некоторый функциональный преобразователь F1 (табл. 20), являющийся автоматом без памяти, который реализует F1 отображение входных сигналов автомата А1 ко входным сигналам объединенного автомата А и выходным сигналам автомата А2.

 

XA1= F1 (XА, YА2).

 

Таблица 20

F1 х 1 х 2 х 3
y 21 х 11 х 12 х 11
y 22 х 12 х 11 х 12

При соединении автоматов с обратной связью автомат А2, включенный в обратную связь, должен быть автоматом Мура.

Таблица 18 является совмещенной таблицей переходов и выходов автомата A1, а таблица 19 – отмеченной таблицей переходов автомата А2.

Алгоритм функционирования соединения автоматов с обратной связью можно сформулировать так:

- начать;

- перебирать предыдущие состояния объединенного автомата s;

- по состоянию sj определить предыдущие состояния s1i и s2j;

- по состоянию s2j определить выходной сигнал y 2j;

- по входному сигналу xi и выходному сигналу y 2j определить входной сигнал автомата А1 x 1i;

- по сигналу x 1i определить последующее состояние автомата А1 s1i и его выходной сигнал y 1j;

- по выходному сигналу y 1j, который равен входному сигналу х2j, определить новое состояние автомата А2 s2j;

- по данным состояниям s1i и s2j определить последующее состояние объединенного автомата sj;

- по выходному сигналу автомата А1 y 1j определить выходной сигнал объединенного автомата y i;

- продолжать алгоритм с п.2 до тех пор, пока будут перебраны все состояния;

- закончить.

Выбираем предыдущее состояние объединенного автомата s1 (s11, s21) при входном сигнале х 1. Предыдущее состояние автомата А2 соответствует состоянию s22 и на выходе будет сигнал y22 (табл.19). По сигналам х 1 и y22 преобразователь F1 (табл.20) формирует сигнал х 11. По этому сигналу автомат А1 из предыдущего состояния s11 переходит в состояние s13 (табл. 18) и на выходе формирует сигнал y11, который соответствует выходному сигналу объединенного автомата y1 (y11 = y1). По сигналу y1 = х 21 автомат А2 из состояния s21 переходит в состояние s21 (табл. 19). Следовательно, при воздействии входного сигнала х 1 автомат А1 перейдет в состояние s13, а автомат А2 в состояние s21, что соответствует состоянию s5 объединенного автомата и на выходе будет сформирован сигнал y1.

В соответствии с алгоритмом перебрав все состояния объединенного автомата А при водном воздействии Х определяется таблица переходов и выходов объединенного автомата А, которая представлена таблицей 21.

Таблица 21

d/l s1 (s11, s21) s2 (s11, s22) s3 (s12, s21) s4 (s12, s22) s5 (s13, s21) s6 (s13, s22)
х 1 s5(s13, s21) / y 1 s4(s12, s22) / y 3 s4(s12, s22) / y 2 s6(s13, s22) / y 1 s1(s11, s21) / y 3 s3(s12, s21) / y 2
х 2 s3(s12, s21) / y3 s6(s13, s22) / y1 s5(s13, s21) / y1 s3(s12, s21) / y 2 s4(s12, s22) / y 2 s2(s11, s22) / y 3
х 3 s5(s13, s21) / y 1 s4(s12, s22) / y 3 s4(s12, s22) / y 2 s6(s13, s22) / y 1 s1(s11, s21) / y 3 s3(s12, s21) / y 2

 

Соединение в сеть представляет собой комбинацию рассмотренных выше схем соединения выходы, которых связаны общей выходной функцией. Входы будут определяться входными функциями каждого автомата, устанавливающими связь между входными и выходными сигналами компонентных автоматов, образующих сеть.







Дата добавления: 2014-11-10; просмотров: 3420. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

В теории государства и права выделяют два пути возникновения государства: восточный и западный Восточный путь возникновения государства представляет собой плавный переход, перерастание первобытного общества в государство...

Закон Гука при растяжении и сжатии   Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Характерные черты официально-делового стиля Наиболее характерными чертами официально-делового стиля являются: • лаконичность...

Классификация холодных блюд и закусок. Урок №2 Тема: Холодные блюда и закуски. Значение холодных блюд и закусок. Классификация холодных блюд и закусок. Кулинарная обработка продуктов...

ТЕРМОДИНАМИКА БИОЛОГИЧЕСКИХ СИСТЕМ. 1. Особенности термодинамического метода изучения биологических систем. Основные понятия термодинамики. Термодинамикой называется раздел физики...

Травматическая окклюзия и ее клинические признаки При пародонтите и парадонтозе резистентность тканей пародонта падает...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия