Лемма 5.11. Для автомата А и системных множеств щ, т, определенных на множестве состояний А, (яь яг) является Mm парой тогда и только тогда, когда (C(Vi), С(я2)) и {C- (щ), С-1 (яг)) являются Mm парами.

Доказательство. Выполните в качестве упражнения.

Таким образом, если для каждой полученной ранее Mm пары (яь Я2) вычислить Mm пару {С{щ), С(я2)), то получим полное множество Mm пар. Тогда вся процедура выполняется следующим образом.

Процедура 5.1. (вычисление всех Mm пар)

1. Для каждой отличной друг от друга пары элементов qi, qj из Q найти m{nij) и Mm пару {Мт{пц), т{пц)).

2. Определить все возможные суммы системных множеств m{nij), полученных в шаге I. Для каждого полученного таким образом системного множества яа определить Л1(яй) для получения Mm пары (М(яа), я).

3. Для каждой Mm пары {щ, щ), полученной в шаге 2, вычислить Mm пару (С(яг), С{щ)).

Даже относительно небольшие таблицы состояний могут иметь большое количество Mm пар (и соответствующих пар множеств). При использовании пар множеств для получения кодирования состояний с уменьшенной зависимостью часто необходимо рассматривать только подмножество всех Mm пар (или пар множеств). Можно ограничить рассмотрение системными множествами я, для которых С(я) = (я), называемыми правильными системными множествами. Мы можем также ограничить рассматриваемые пары множеств Р(я1, Я2) теми множествами, где Я2 имеет только два блока и, следовательно, определяет одну переменную состояний, или случаем, когда Я2 является разбиением. Следующий пример иллюстрирует использование Mm пар для получения кодирования состояний с уменьшенной зависимостью.

Пример 5.6. Для таблицы, представленной на рис. 5.11, Mm пары могут быть получены с помощью процедуры 5.1. Так как имеется большое количество Mm пар, ограничим себя такими парами (яь Я2), в которых яг является разбиением.

Первые представленные ниже девять Mm пар получаются иа шаге 1 процедуры 5.1. Например, Я12 = (12,3,4,5)

т(я,2) = 15, 234) и Л1т(я,2) = (123, 45).

Рис. 5.11. Таблица со> стояний из примера 5.6.

Для получения кодирования состояний с уменьшенной зависимостью вначале выберем Mm пару, которая имеет относительно малое количество блоков в М-разбиении. Например, М-разбиение (123,45) имеет только два блока. Следовательно, если мы определим переменные г/ь г/г так, что % = (123,45) и % = (234,15), то Уг = f (i/i, л:). Мы должны определить г/з таким образом, чтобы Tj/, Ху, - о (для того чтобы использовать только три переменные) и, следовательно, 2 3 (ху). Если необходимо узнать, можно ли получить уменьшенную зависимость для Уи то вычислим M(Tj ) = (15, 2, 3, 4) При уменьшенной зависимости необходимо иметь такое двухблоковое разбиение Ху что Ху, Ху,М{Ху) или Ту, Ту, М (ту,). Поскольку ни одно из этих неравенств невозможно удовлетворить, мы не можем получить для г/i уменьшенную зависимость. Поэтому попытаемся определить г/з таким образом, чтобы получить уменьшенную зависимость для г/з. Наиболее подходящим системным множеством т, которое обладает таким свойством, что Ху Ху, Ху, - 0, является Tyj = (1245, 1345). (Мы рассматриваем наибольшее т для того, чтобы М(т) было бы по возможности наибольшим). Так как М(ту,) = (14, 15,234, 235) то Уз является независимым от г/i и г/з. Результирующее кодирование

На втором шаге 2 процедуры 5.1 получаются Mm пары (10) и (11). Например, из Mm пар (2) и (3) получаем

(12, 35, 4)+ (123, 4, 5,) = (1235, 4), Л1(1235, 4) = (2, 3, 145)

и приходим к Mm паре (2,3, 145), (1235,4).

Реализации последовательностных автоматов 307 СОСТОЯНИЙ показано ниже.

Переменные у\, у2 могут быть также получены при исходном рассмотрении всех пар множества вида {М{т), (nt), где щ является двухблоковым разбиением (вместо всех Mm пар разбиения) .

Представляется возможным определить переменные состояний таким образом, чтобы получить уменьшенную зависимость выходных функций. Для двоичной выходной функции Zi автомата А для каждого входного столбца 4 из Л, Zi определяет двухблоковое системное множество тГг^.

Если существует множество переменных состояний Т, таких, что П т„.<Тг, где Гг = Т[т:г. ТО Zi зависит только от

входных переменных и переменных состояний yiT.

Может оказаться также возможным получить кодирование состояний, в котором некоторое множество переменных состояний (или выходных переменных) является независимым от некоторых или всех входных переменных. Для автомата Л с входными столбцами /[, /2, Ik двоичная входная переменная Xi определяет системное множество п^ следующим образом: для любого состояния Qj и любой пары входных столбцов /], А которые отличаются между собой только в переменной xi, N (Q], /1) = N (2, 2) iXf). Переменная состояний у^ является независимой от Xi тогда и только тогда, когда Xynx. Для г/, которая должна быть независимой от всех входных переменных ТуЛ;, где п, является таким системным множеством, что N{qi, I{) = N{qj, /2)= ... =N(q 4) (Я/) для всех состояний q/.

Пример 5.7. Для показанной на рис. 5.12 таблицы я, = = (12, 34). Так как для показанного здесь кодирования тгу, = = Пх, то Yl является независимым от Xi. Поскольку Я] = 1, то не имеется переменной, которая могла бы быть определена как независимая от Xi и Хг- Аналогичным образом, г^ = {Ы, 23). Следовательно, z является независимой от г/i, так как Хг = Ху.

Как было показано в примере 5.6, процесс кодирования состояний с уменьшенной зависимостью из Mm пар не является полностью определенным процессом вследствие большого числа Mm пар. Однако использование системных множеств, обладающих свойствами подстановки (СП), является значительно более доступным и прямым способом. Все системные множества, обладающие свойством подстановки, могут быть получены из Mm пар на основе следующей леммы.

Рис. 5.12. Таблица состояний из примера 5.7.

Лемма 5.12. Заданное системное множество п определено на множестве состояний Q автомата А, 8{л) тогда и только тогда, когда М (л) > л; > m (л).

Доказательство. Достаточность. Допустим, что п имеет свойство, подстановки. Тогда Р (п, п). Но, по определению М (Р), Р{М{л), п). Следовательно, М{л)л. Кроме того, Р (я, m (я)). Следовательно, я>т(я) и М (я) >я> ал (я).

Необходимость. Предположим, что М(я)ят(я). Так как Р{М(я), я) и М(я)я по лемме 5.46, то Р(я, я). Следовательно, я обладает свойством подстановки.

По лемме 5.12 каждому системному множеству, обладающему свойством подстановки, соответствует Mm пара (Я], Яз), в которой Я1Я2. Рассмотрим системное множество я, которое имеет свойство подстановки. Если (?г = г( ). то на основе леммы 5.12 qi = qj{m{n)). Следовательно, п'т{пц), где Щ/ является разбиением, в котором qt и q/ находятся в одном и том же блоке, а все другие блоки содержат одиночные состояния. Таким образом, если я обладает свойством подстановки, то для любой пары состояний qi, q/, которые определены в я, т{яг;)я. Следовательно, можно образовать такое наименьшее системное множество, обладающее свойством подстановки, что qi = qji), которое получается следующим образом.

Положим f-, = + m (яи

4=4 + (4 )-

Если т^у = т^/ , тогда т^ обладает свойством подстановки (лемма 5.12). Затем может быть использована следующая процедура для нахождения всех системных множеств, обладающих свойством подстановки, без получения всех М/п пар.

Процедура 5.2

1. Рассмотрим системное множество л^, qi, QiQ для каждой пары элементов.

2. Вычисляем x\j = п. + m (jij)-

3. Вычисляем т*. = т*г- -- т при k = 2, 3, ... до тех пор, пока rj = т'г' = т..

4. Образуем все возможные суммы системных множеств Гц, сформированные в шаге 3.

5. Для каждого системного множества п; полученного в шаге 4, образуем С{п). Оно генерирует все возможные системные множества, которые обладают свойством подстановки.

Лемма 5.13. Для автомата А процедура 5.2 генерирует все системные множества, которые обладают свойством подстановки, и только такие системные множества.

Доказательство. Вначале докажем, что все генерируемые системные множества обладают свойством подстановки. Предположим, что системное множество хц, генерируемое на шаге 3 процедуры 5.2, не обладает свойством подстановки. Тогда т {xij) Хц- Но это противоречит шагу 3. Следовательно, все генерируемые на шаге 3 системные множества обладают свойством подстановки.

Для того чтобы доказать справедливость шага 4, мы должны доказать, что и (лз) означает 5(1-1-2). Если S{ni),

то Р(я1, Я]), а если 5(я2), то Р {щ щ)- Следовательно, на основании леммы 5.5а Р {щ-\-П2, щ-\-, которое подразумевает 5(я1-1-Я2). Доказательство справедливости шага 5 оставляется в качестве упражнения.

Теперь предположим, что имеется системное множество я, обладающее свойством подстановки, которое не генерируется

г

С помощью этой процедуры. Положим, что С' (я) = X

Так как я обладает свойством подстановки, то каждое системное множество i, обладает свойством подстановки и

hik)hh . Д^ательно, я = т^, которое генерируется на шаге 4 процедуры 5.2 для некоторых т, п, что является противоречием.

Пример 5.8. Будем использовать процедуру 5.2 для генерации всех собственных системных множеств я (т.е. таких, что

Рис. 5.13. Таблица состояний нз примера 5.8.

5.4. ДЕКОМПОЗИЦИЯ

ПОСЛЕДОВАТЕЛЬНОСТНЫХ АВТОМАТОВ

Важным типом уменьшенной зависимости является декомпозиция последовательностного автомата М на два или более составляющих его автомата. Можно рассматривать автомат М как реализуемый с помощью соответствующих соединений составляющих его субавтоматов. Мы будем рассматривать только такие соединения, которые не имеют контуров, а именно не имеется обратной связи, охватывающей два или более автомата-компонента, хотя сами реализации этих составляющих его автоматов могут содержать обратную связь. На рис. 5.14, с и б показаны параллельная и последовательная декомпозиции соответственно автомата М на составляющие его автоматы-компоненты Ml и Мг.

С (я) =я), обладающих свойством подстановки, на основе таблицы, представленной на рис. 5.13.

Начнем с разбиения Я12.

т(я12) = (12, 23, 46, 5), г;2 = я + т(я ) = (12, 23, 46, 5), х^ = х\, + т{х\) = {12, 23, 46, 45, 13), ?2 = fL + K2) = (12. 23, 46, 45, 13, 56),

?2 = ?2 + К2) = 12-

Следовательно, Tig ==(12, 23, 46, 45, 13, 56). Аналогично видно, что Т13 = тгз = Т45 =

Т56 = Т12.

Ап(ян) = (25, 36, 1, 4),

т14==я, + т(я ) = (14, 25, 36),

Оставшиеся Хц системные множества являются тривиальными. Набором собственных системных множеств, обладающих свойством подстановки, является

С (Tig) = (123, 456),

C(i:i4)-(14, 25, 36),

C(i:i2 + Ti4)=(123, 456, 14, 25, 36).

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

Рис. 5.14 Параллельная декомпозиция (а); последовательная декомпозиция (б).

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

Теорема 5.2. Если задана полностью определенная таблица состояний М, то а) существует нетривиальная ) параллельная декомпозиция М тогда и только тогда, когда существуют два нетривиальных системных множества щ и П2, определенные на состояниях М, таких, что л;1-л;2 = 0 и S{ni) и 5(я2); и б) существует нетривиальная последовательная декомпозиция М тогда и только тогда, когда существует нетривиальное системное множество Яь такое, что (Я]).

Доказательство, а). Допустим, что существует параллельная декомпозиция М, как показано на рис. 5.14, а. Положим, что А и В представляют собой множества переменных состояния автоматов М] и М2 соответственно. Положим что я, = 111:,

- П у; где Ху, является двухблоковым системным множе-

ством, создаваемым переменной состояния Так как значения следующих состояний из Л и В являются независимыми друг от друга, то (я]) и 5(я2) (по теореме 5.1). Поскольку переменные в Л и 6 однозначно определяют состояние автомата М, то Я1 -Яг = 0.

) Декомпозиция является тривиальной, если один из составляющих автоматов идентичен автомату М. Тривиальными системамп множеств являются О и 1.

При параллельной декомпозиции следующее состояние каждого автомата зависит только от входных сигналов и от состояния, в котором автоматы находятся в данный момент. Выход проектируемого автомата М будет, вообще говоря, зависеть от входных сигналов и текущих состояний обоих автоматов Mj а М2. При последовательной декомпозиции следующее состояние автомата Mi не зависит от состояния автомата М2, но следующее состояние автомата М2 зависит от текущих состояний и автомата Mj, и автомата М2. Выход зависит от входных ситца-

Положим S (лО и S {щ) и щ- щ = 0. Определим перемен-ные Уи, l</<fe и г/2/, 1</<Й2, так, что Jlryu = ni,

Г1 тг/2/ = 2. Это определяет параллельную декомпозицию, поскольку по теореме 5.1 переменные yi должны быть независимыми от У21 и наоборот.

б) Доказательство необходимости части б) аналогично доказательству части а). Предположим, что существует системное

множество щ с {S{n{)). Если определить набор переменных г/н, ft,

1<г<Й1, так, что Т1суи = Щ, и другой набор переменных г/2/, (=1

1 /2, так, что Г1тг/1г^ Г1 Уг/ == О, то эти переменные

определят последовательную декомпозицию, поскольку переменные Уи являются независимыми от г/,/ из-за

Для обоих типов декомпозиций переменные ун присваиваются для выделения блоков в щ. Отсюда количество состояний в М], равняется числу блоков в ль При параллельной декомпозиции переменные yzi присваиваются для выделения блоков влг и количество состояний в равняется числу блоков в Л2. При последовательной декомпозиции переменные присваиваются для того, чтобы выделить элементы в одном и том же блоке в л\. Если Втах прсдставляет собой максимальное число элементов в любом блоке из ль то Mz имеет по крайней мере Втах состояний.

Положим, что Л1 и Л2 являются двумя системными множествами состояний автомата М, такими, что 8{л.\) 5(л2) и Л1-Л2 - 0. Таблицы состояний подавтоматов Му и М2 при параллельной декомпозиции могут быть получены непосредственно из Л1-Л2 и М. (Идти по этому пути для того, чтобы получить параллельную декомпозицию, нет необходимости, поскольку декомпозиция неявным образом задается в закодированных состояниях. Но, вообще говоря, это может предоставить нам возможность найти более сложные декомпозиции автомата М за счет выполнения дальнейших декомпозиций Му и/или М^.)

Содержимое следующего состояния М/, /= 1, 2, получается следующим образом. Если блок Bi системного множества Л/ содержит состояния Qy, Qz, Qp автомата М, то N{Bi, 4) является множеством состояний {N (qy, 1), N (q, Ik), N{qp, 1)}. Если Л/ обладает свойством подстановки, то все состояния в N (Bi, 1) должны находиться в одном и том же блоке В^ из л/. Таким

образом, если блок из представляется состоянием q, а В^ состоянием q. из М^, то N (ql, I) = qj.

Пример 5.9. Для таблицы из примера 5.8, которая повторена на рис. 5.15, рассмотрим разбиения, обладающие свойством подстановки, Л1 == (123,456) и Л2= (14,25, 36). Так как Я1-Я2 = О, эти два разбиения могут быть использованы для определения

Рис. 5.15. Таблица состояний из примера 5.9.

параллельной декомпозиции автомата М на автомат Ми определяемый переменной г/i (т^, = Л]), и автомат М2, определяемый переменными j/j и у, (т;/, Ту. = Яг). Автомат Mi будет иметь два состояния А к В, соответствующие двум блокам из яь 123 и

з

Рис- 5.16. Таблица состояний подавтоматов из примера 5.9.

456 соответственно, и три входа h, h, /3 из М. Л/(Б,/2) = А, поскольку iV(456,/г) = 132. Аналогичным образом, автомат Мг будет иметь три состояния А', В', С, соответствующие блокам из Я2, и три входа /1, h, h- N (5, /3) = В', поскольку N(25, /3) = = 22 с: В'. Для яь Яг и таблицы М, таблицы состояний подавтоматов Ml и М2 показаны на рис. 5.16.

Положим, что я и т являются двумя системными множествами, такими, что S(n) и я-т = 0. Таблица состояния ведущего автомата Mi может быть получена непосредственно из я и М, как это выполняется при параллельной декомпозиции. Автомат

Мг получается непосредственно из т, Mi и М следующим образом. Состояния из iMg соответствуют блокам из т, а входы в Мг связаны с внешними входами и состояниями М\. Для состояния qj из Mg и входов (7., J, где Iu является входом, а является состоянием из Mj, содержимое следующего состояния N (ql (/j., у)) определяется так: <7 представляет блок Bi из т, qj представляет блок Bj из л. Так как т было определено таким образом, чтобы выделить элементы в одном и том же блоке из п, то Bi П Bj - qr (или Ф). Таким образом, комбинированное состояние Ml и М2 единственным образом представляет текущее состояние М (или неопределенное состояние, если п q. представляют собой непересекающиеся множества состояний из М),

а комбинированные следуюйще состояния Ml и Мг должны представлять следующее состояние М единственным образом. Если состояние qr содержится только в блоке Вг из т, то N(q.,(I,, q.))= В^. Однако, по-видимому, qr содержится в более чем одном блоке из т. Если л-т = О, то следующим состоянием для этого входа может быть любое состояние из Мг, которое представляет qr, так как составляемое следующее состояние для любой из этих возможностей будет представлять qr.

Пример 5.10. Для таблицы М, представленной на рис. 5.17, наименьшим правильным системным множеством, обладающим свойством подстановки, является л = = (123,345). Оно может быть использовано для получения последовательной декомпозиции на автомат (ведущий) Ми определяемый Л1 (рис. 5.18), и автомат Мг (ведомый), определяемый некоторым системным множеством т, которое осуществляет выделение среди элементов в рамках одного и того же блока л.

Если т= (14,25,3), то таблица Мг является полной, как показано на рис. 5.19. Содержимое столбца {В,) и строки В' определяется следующим образом. Так как В' = {25} и S = = {345}, то fi Л .6 = 5. Следовательно, содержимое следующего состояния должно представлять собой Л^(5,/2)=3 и 3 S С. Если системные множества используются для представления

Рис

м

5.17. Таблица состояний из примера 5.10.

Рис. 5.18. Ведущий автомат из последовательной декомпозиции, пример 5.10.