Число переменных, требуемых для ОВП-кодирования, может быть значительно уменьшено, если допустить одновременное изменение более чем одной переменной, но так, чтобы при этом не происходили критические состязания. Рассмотрим ОБП-ко-дирование с одним кодом на состояние, обычно рассматриваемое как однозначное кодирование. Такое кодирование было впервые предложено Лю [13] ив дальнейшем было разработано Трэйси [21]. Если несколько переменных при ОВП-кодировании изменяются в течение перехода, то точный порядок изменения не может быть заранее указан. Поэтому полезно определить подкуб перехода T{qi,qj), связанный с состояниями qi и q, как множество всех точек, через которые можно пройти в течение перехода между qi и qj (включая qi и qj) при предположении, что переменные, которые изменяются во время перехода, могут изменять свое состояние в произвольном порядке. Подкуб перехода Т {qi, qj) состоит из всех точек, которые являются идентичными с qi и qj в переменных, в которых qi и qj совпадают. Например, если состояния qi и q кодируются соответственно как i /2i/3i/4 = 0110 и 1100, то цепь может проходить через состояния 0100 нли 1110. Подкуб перехода T{Si, Sj) содержит четыре точки 0100, ОНО, 1100 и 1110 и обозначается как Г {qi,qj) - - -1 - О или T{qi, qj)=y2y4, указывая, что у\ и уз могут получать любое значение в течение перехода.

Пересечение T{qi, qj) и T{qm, qn), обозначаемое как T{qi, qj) П T{q,ri, qn), состоит из всех точек, содержащихся в обоих подкубах. Если в столбце таблицы переходов имеются переходы от qi к q, и qm к q, где ф qj, то происходит критическое состязание (при предположении, что все переменные изменяются одновременно), если не имеет место T{qi, qj) [] {] Т {qm, q-n) = Ф (т.е. не имеется точек, содержащихся в обоих подкубах.) (Это требование сравнимо с требованием непересекающихся траекторий при многошаговом кодировании состояний с помощью множества разделяемых строк.) Для того чтобы T{qi,qj)V\T{qm,qn) = 4>, должна существовать некоторая переменная Уу, которая принимает значение О для обоих qi и qj и значение 1 для (jm и (7 и наоборот (выполните в качестве упражнения).

Лю [13] была разработана простая процедура кодирования состояний, обладающих этим свойством. Метод состоит в том, что кодирование множества переменных состояния, связанных с каждым столбцом таблицы переходов, производится таким образом, чтобы различать устойчивые состояния в этом столбце от других состояний, а каждое такое устойчивое состояние было бы однозначно закодировано связанными с ним переменными. Неустойчивым состояиием в столбце присваиваются те же самые значения, что и устойчивым состояниям, к которым

8 Зак, 641

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

Процедура 4.1. (однозначное ОВП-кодирование) Допустим, что таблица переходов нормального режима имеет m столбцов, II, /2, .. -, /т и ЧТО столбец Ij имеет устойчивые состояния, 1

/ /п. Для каждого столбца Ij определено riog2ajl переменных у, , у., ..., у. , таких, что

1 2 ai

а) каждое устойчивое состояние в столбце имеет однозначный код, построенный из этих переменных;

б) если N {qu Ij) =z qf qi, то состояния qi и q закодированы одинаково.

Рис. 4.24. Кодирование состояний типа Лю для таб.тацы переходов (пример 4.10).

Пример 4.11. Рассмотрим таблицу переходов, показанную на рис. 4.24. Столбец 00 имеет два устойчивых состояния 2 и 5, которые различаются в yi.

Состояниям 1, 3 и 6, каждое из которых приводит к состоянию 2 в столбце 00, и самому состоянию 2 присваивается yi - Q). Состояниям 4 и 5 присваивается yi = \, так как состояние 4 приводит к устойчивому состоянию 5 в столбце 00. Аналогичным образом, переменные у2 и у^ используются для того, чтобы обеспечить различия между четырьмя устойчивыми состояниями в столбце 01. Неустойчивым состояниям 2 и 5 присваиваются те же значения переменных у2 и у^, что и состояниям 6 и 3 соответственно. Столбец И имеет три состояния и требует двух переменных состояния.

Однако можно провести различие между ними даже в том случае, если одна переменная не полностью определена. Поскольку для состояний 1 и 3 г/4=0, то у^=\ будет выделять из них состояние 4, а уь для состояния 4 может оставаться неопределенным. В дальнейшем будет показано, как такие неопределенные параметры могут оказаться полезными при сокращении требуемого количества переменных состояний. Столбец 10 необходим для выделения устойчивых состояний 2 и 5. Для этой цели могут быть использованы ранее определенные переменные У1 или Уз-

Теорема 4.2. Процедура 4.1 приводит к ОВП-кодированию без критических состязаний.

Доказательство. Рассмотрим переход от Qi к в столбце 1.-При присваивании кодов состояний все переменные у^и определенные для столбца Ik, остаются постоянными в течение этого перехода, и подкуб перехода T{qi, q) определяется этими переменными. Для любого другого перехода из qm в qn, qn Ф qj, это множество переменных отличает qm и 9 от qi и q. Следовательно, T{qi, 9з)П T{qm, (7п) = и во время перехода от qi к q не может быть достигнута точка, внешняя в T{qi, qj). Таким образом, состояние qn Ф qj не может быть достигнуто в течение перехода и при переходе не возникает критического состязания. Два состояния будут иметь один и тот же код только в том случае, если таблица переходов может быть сокращена.

Представляется возможным сократить число переменных состояния при кодировании состояния, получаемого с помощью процедуры 4.1 без введения каких-либо критических состязаний. С этой целью удобно рассматривать табллщу кодирования, строки которой состоят из кодов, присваиваемых состояниям таблицы переходов. Таким образом, каждый столбец будет представлять значения, допускаемые для переменной состояния при различных состояниях. Столбец yi включает столбец yj, что обозначается угЗэуз, если yj согласуется с у, всюду, где бы ни было определено yi. Столбец yi покрывает столбец yj, если yj =з yi или Уз =э yi, где yi получается инверсией нулей и единиц в г/,. Пересечение двух столбцов yi и yj существует тогда и только тогда, когда два столбца согласуются всюду, где бы они оба ни были определены. Пересечение согласуется с обоими столбцами, когда оба они определены, и когда оно равно одному из них, в то время как другой является неопределенным.

Теорема 4.3. Количество переменных состояний в таблице кодирования может быть сокращено а) исключением столбцов, покрываемых другими столбцами, б) заменой столбцов yi и yj их пересечением или пересечением yi и yj, если какое-либо из них существует, без введения критических состязаний.

Рис. 4.25. Сокращение переменных состояния при кодировании типа Лю

(пример 4.11).

У1 и у2 определяются столбцом 00, й и 4 -столбцом 01, а 5 и 6 -столбцом 11. Исключая переменную уь, которая покрывается переменной у^, мы получаем кодирование пятью переменными,- показанное на рис. 4.25, в. Заметим, что даже если столбцы Уз или 6 имели бы вначале обратный код, то Уь все равно покрывалось бы переменной г/з и могло быть исключено.

Другой тип однозначного ОВП-кодирования, требующий зачастую меньшего числа переменных, чем кодирование Лю, которое было рассмотрено выше, был разработан Трэйси [21]. Од-

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

Пример 4.12. Рассмотрим таблицу переходов, представленную на рис. 4.25, с. Таблица кодирования на рис. 4.25,6 получается при использовании процедуры 4.1. Переменные состояний

нако кодирование Лю является полезным при определенных специальных типах реализации [2].

Вместо выделения среди всех устойчивых состояний в столбце метод Трэйси рассматривает все пары переходов в каждом столбце. Определим частичную дихотомию (или простую дихотомию) состояний автомата как непересекающееся разделение на две части (блока) подмножества множества состояний. Затем можно связать диохтомию с любой парой переходов в столбце таблицы переходов. Дихотомия, связанная с переходами Qi -> qj и qh - qm, представляется как {qu qj-, qn, qm)

Говорят, что переменная состояний покрывает дихотомию, если эта переменная равняется О для всех состояний в одном блоке и равняется 1 для всех состояний в другом блоке. Например, переменная ур покрывает дихотомию (qi, qj, qn, Qm), если yp{qi) = yp(qj)=.Q и yp{qp) = yp{qm)= I, или наоборот, где z/p (<7n) - переменная состояний ур, связанная с состоянием qn-

Если столбец имеет устойчивое состояние qj и переход qhqm, то можно связать вырожденную дихотомию {qi; qn, qm) с устойчивым состоянием и переходом. Аналогичным образом, дихотомия {qj] qm) может быть связана с парой устойчивых состояний в столбце. Следующая теорема, взятая из работы Трэйси [21], дает необходимые и достаточные условия для однозначного ОВП-кодирования для любой таблицы переходов нормального режима.

Теорема 4.4. Кодирование состояний для таблицы переходов нормального режима является ОВП-кодированием тогда и только тогда, когда для каждой пары переходов qtqj и qnqm, Qj Ф Qm, появляющейся в одном и том же столбце таблицы, дихотомия {qt, qj-, qn, qm) покрывается некоторой переменной у. Дихотомии должны также включать вырожденные (с двумя и тремя состояниями) дихотомии, которые могут потребоваться в каждом столбце.

Доказательство. Достаточность. Из определения покрытия дихотомии переменной состояний следует, что переменная, покрывающая дихотомию {qu qj] qn, qm), должна быть равна О в течение перехода qiqj и 1 в течение перехода qn-Qm или наоборот. Следовательно, подкубы переходов T{qi, qj) и T{qn, qm) являются непересекающимися, и при этих двух переходах не могут происходить критические состязания. Если для каждого устойчивого состояния qj и каждого перехода qn-*qm в одном и том же столбце сокращенная дихотомия {qj-, qn, qm) покрывается некоторой переменной у, то qjT{qn, qm), и со-состояние qi не может быть достигнуто в течение перехода QhQm независимо от порядка изменения переменных. Покрытие дихотомией типа {Qj; qm) гарантирует, что устойчивые состояния в любом столбце всегда различимы.

Рис. 4.26. Кодирование типа Трэйси для таблицы переходов (пример 4.13).

если допускается одновременное изменение переменных состояний в течение перехода. Аналогично если дихотомия {qj-, q, qm) не покрывается любой переменной, то подкуб перехода T{qn, qm) будет содержать состояние qj, и в течение перехода от q к qm может быть достигнуто устойчивое состояние qj. Покрытие дихотомии {qi; qj) необходимо для того, чтобы гарантировать, что состояния qi и qj могут быть различимы.

Пример 4.13. Рассмотрим таблицу переходов, представленную на рис. 4.26, G. Кодирование Лю требует 4 переменных и представлено на рис. 4.26,6. Процедура кодирования Трэйси первоначально создает 5 переменных состояния (рис. 4.26, в), но у[ покрывается г/3, а у[ покрывается г/д, так что [3, у\, у'

Необходимость. Если столбец содержит переходы qiqj и qh-q-m, а дихотомия {qi, q{, qn, q,n) не покрывается какой-либо переменной, то подкубы переходов T{qi, qj) и T{qk, q,n) не являются непересекающимися. Поскольку одна или несколько точек будут содержаться в обоих подкубах, следующие состояния для этих переходных состояний не могут быть определены единственным образом так, чтобы устранить критические состязания.

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

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

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

Две дихотомии можно определить как совместимые, если они могут быть покрыты одной переменной состояния. Таким образом, дихотомии') (12,34) и (12,56) являются совместимыми. Хотя дихотомия (34,56) является совместимой с обеими из указанных дихотомий, не представляется возможным покрыть все три дихотомии одной переменной. Эту трудность можно преодолеть, если ввести определение пары упорядоченных дихотомий для каждой дихотомии, которая должна быть покрыта при кодировании состояний. Каждая дихотомия (л, В), где л и в являются множеством состояний, заменяется упорядоченными дихотомиями {А,В) и {В,А). Две упорядоченные дихотомии Я1з-ляются совместимыми, если нет состояния, которое, появившись в первом блоке одной дихотомии, оказалось бы во втором блоке другой дихотомии. Множество упорядоченных дихотомий является совместимым тогда и только тогда, когда упорядоченные дихотомии множества являются попарно совместимыми. Совместное множество дихотомий, которое не покрывается каким-либо другим совместимым множеством, называется максимально совместимым множеством. Минимальное число переменных при ОВП-кодировании может быть получено посредством нахождения минимального из максимально совместимых множеств, которое покрывает все (неупорядоченные) множества таблицы переходов. Заметим, что достаточно выбрать любую пару упорядоченных дихотомий для того, чтобы покрыть соответствующую неупорядоченную дихотомию. Минимальное число переменных при кодировании типа Трэйси может быть получено из следующей процедуры.

Процедура 4.2. (однозначное ОВП-кодирование)

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

2. Исключить дихотомии, покрытые другими дихотомиями.

>. )2 Уз

О О

О О

(45,12) (12,35) (35,12) (35,4) (4,35) (13,г5) (25,13) (13,45) (45,13)

(12,45) (45.12) (12,35) (35,12) (35,4) (4,35) (13,25) (25,13) (13,45) , б

Рис. 4.27. Сокращение переменных состояния при кодировании типа Трэйси

(пример 4.14).

(12,345) (123.45)

(124,35; (1-3,245)

Рис. 4.27 (продолжение)

3. Заменить каждую оставшуюся дихотомию парой упорядоченных дихотомий и определить максимально совместимые множества дихотомий, для этого можно воспользоваться процедурой 3.2.

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

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

Пример 4.14. Для таблицы переходов, представленной на рис. 4.27, а, покрываемыми дихотомиями являются дихотомии (12,3), (12,45) и (3,45) в столбце 00, дихотомии (13,2), (13,4), (2,35), (2,4) и (35,3) в столбце 01, дихотомии (12,35), (12,4) и (35,4) в столбце 11 и дихотомии (13,25) и (13,45) в столбце 10. Исключая дихотомии, покрываемые другими дихотомиями, находим, что кодирование состояний должно покрывать следующие дихотомии: (12,45), (12,35), (35,4), (13,25) и (13,45). Используя пару упорядоченных дихотомий для каждой из этих дихотомий, можно получить график пар, представленный на рис. 4.27, б. Совместимые пары дихотомий обозначаются символом V- Максимально совместимыми дихотомиями являются (12,345), (123,45), (124,35) и (13,245). Таблица переходов показана на рис. 4.27,6. Дихотомии (35,4) и (13,25) покрываются только (124,35) и (13,245) соответственно. Оставшиеся дихотомии покрываются (123,45). Эти максимальные совместимые дихотомии дают кодирование состояний с тремя переменными, показанное справа от таблицы переходов.

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

(12,45) (12,35) (15,4) (13,25) (13,45)

аналогичными дихотомиями или дихотомиями, не содержащими qi. При симметричных аргументах, соответствующих каждому максимально совместимому с qi состоянию в блоке 2, будет иметься эквивалентное максимально совместимое с qi состояние в блоке 1. Поскольку дихотомии, которые должны быть покрыты, являются неупорядоченными, можно исключить все дихотомии, в которых qi появляется в блоке 2. Минимальные покрытия для этой сокращенной таблицы должны быть эквивалентны таким же покрытиям для исходной таблицы. Этот процесс может быть выполнен для любого состояния qi, таким образом, можно выбрать такое состояние, которое появляется в наибольшем количестве дихотомий. Трэйси были также предложены некоторые методы для получения почти минимальных кодирований для более крупных по размерам таблиц переходов.

Представляется возможным определить универсальные однозначные ОВП-кодирования. Такие кодирования покрывают все возможные Дихотомии множества п состояний и поэтому являются имеющими силу ОБП-кодированиями для нормального режима последовательностного автомата с п состояниями. Следующая теорема дает верхнюю границу числа переменных состояния, требуемых для универсального однозначного ОБП-ко-дирования для таблицы переходов нормального режима с п состояниями [6].

Теорема 4.5. Существует универсальное однозначное ОБП-ко-дирование с п состояниями при т переменных, где

°g(4)

m>->>20[log2nl = 20So.

Доказательство. Рассмотрим класс пУ,т двоичных массивов, где строки представляют состояния, столбцы - переменные состояний, а содержимое массивов определяет однозначное кодирование состояний. Б этом классе имеются 2 массивов. Такой массив будет покрывать дихотомию (qi, qy, qk, qm) тогда и только тогда, когда qi = qj = I, qk = qm = О или = = О, qk - qm = I. Имеется 2* - 2= 14 других комбинаций значений этих четырех строк, которые не покрывают эту дихотомию. Таким образом, общее количество массивов, которые не покрывают эту дихотомию, равняется (14) , 2 * = 2 Общее количество дихотомий, которые должны быть Покрыты универсальным кодированием п состояний, равняется 3 Таким образом, имеется самое большее ( 4 ) (т!-) масси-