Хороший материал для К.Р. и так почитать

Два перехода qi → qj и qk → ql, совершаемые автоматом при одном и том же входном сигнале в различные состояния (qj ≠ ql), назовем парой переходов. Тогда условие отсутствия опасных состязаний формулируется следующим образом.

У т в е р ж д е н и е 22.1. При одновременном возбуждении элементов памяти в процессе перехода опасные состязания отсутствуют тогда и только тогда, когда для каждой пары переходов qi → qj, qk → ql имеет место

U(qi, qj) ∩ U(qk, ql) = .

Множества U(qi, qj) и U(qk, ql) можно формально представить как множества кодов соответствующих состояний, а те, в свою очередь, представляются троичными векторами, полученными из кодов состояний qi, qj,

qk и ql. Обозначим эти векторы t(qi, qj) и t(qk, ql). Компоненты вектора t(qi, qj) принимают значения одноименных компонент кодов qi и qj, если они

совпадают, и принимают значение «–» в противном случае. Например, если коды состояний qi и qj соответственно (0 0 0 1) и (0 1 0 1), то t(qi, qj) = (0 – 0 1).

Необходимым и достаточным условием непересечения множеств U(qi, qj) и U(qk, ql) является ортогональность векторов t(qi, qj) и t(qk, ql). К этому условию надо добавить еще необходимое требование того, что для реализации различных состояний их коды должны быть ортогональными.

Для автомата, таблицей переходов которого является табл. 22.1, имеются следующие пары переходов:

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

171

Для автомата, таблицей переходов которого является табл. 22.1, условия отсутствия опасных состязаний, определяемых парами переходов q1 → q1,

q4 → q5; q1 → q1, q5 → q5 и q2 → q1, q4 → q5, могут быть представлены следующими строками:

q1 q2 q3 q4 q5

0 – – 1 1

0 – – – 1

0 0 – 1 1.

Здесь только последняя строка останется в матрице условий. Остальные строки имплицируются последней строкой и в матрицу условий не включаются.

Будем говорить, что троичная матрица R имплицирует троичную матрицу S, если для каждой строки матрицы S в матрице R найдется имплицирующая ее строка.

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

Множество строк матрицы условий называется совместимым, если существует вектор, имплицирующий каждую строку этого множества. Заметим, что множество строк, в котором каждая пара строк является совместимой, не всегда является совместимым множеством. Действительно, пусть имеется три троичных вектора: и = (0 1 – – 0 1), v = (– 1 0 – 0 –) и w = (– –1 – – 1). Для и и v

общим имплицирующим вектором является (0 1 0 – 0 1), для и и w – вектор (0 1 1 – 0 1), а для v и w – вектор (– 0 1 – 1 1). Любой имплицирующий вектор для двух векторов не является таковым для третьего. Совместимое множество называется максимальным, если оно не является собственным подмножеством другого совместимого множества.

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

Пусть табл. 22.2 представляет таблицу переходов заданного асинхронного автомата. Для того чтобы учесть требование ортогональности кодов для различных состояний, можно ввести в таблицу переходов еще один столбец, где присутствуют все состояния, которые являются устойчивыми. Тогда выполнение данного требования обеспечивается введением в матрицу условий строк, не имплицируемых другими строками и выражающих отсутствие опасных состязаний, которые соответствуют данному столбцу. При этом табл. 22.2 примет вид табл. 22.3. Заметим, что неортогональные коды могут оказаться у состояний, которым соответствуют одинаковые строки таблицы переходов, и введение дополнительного столбца делает все строки различными.

Таблица 22.2

173

Таблица переходов асинхронного автомата

Таблица 22.3 Таблица переходов с дополнительным столбцом

Анализируя табл. 22.3, нетрудно найти, в частности, что условия отсутствия опасных состязаний при входном сигнала а1 выражаются следующими тироичными векторами (справа показаны рассматриваемые при этом пары переходов)

00 1 1 – q2 → q1, q4 → q3.

Вданном случае строка (0 0 1 1 –) имплицирует каждую из трех остальных, которые, следовательно, не надо включать в матрицу условий. Рассматривая остальные пары переходов и формируя для них соответствующие троичные векторы, получим следующую матрицу условий, которая для удобства обозрения разбита на секции, соответствующие различным столбцам табл. 22.3:

174

Каждому совместимому множеству строк троичной матрицы согласно его определению соответствует вектор, имплицирующий все строки, являющиеся элементами этого множества. Для данной троичной матрицы S получим следующие максимальные совместимые множества и соответствующие им векторы:

Кратчайшее покрытие множества строк матрицы S составляют множества

{1, 6, 7, 9}, {2, 3, 4, 5, 8} и {2, 4, 7, 8, 10}. Соответствующие им векторы являются вектор-столбцами матрицы кодирования заданного асинхронного автомата:

175

Литература

1.Ангер С. Асинхронные последовательностные схемы. – М.: Наука, 1977. – 400 с.

2.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.

3.Баранов С.И. Синтез микропрограммных автоматов. – Л.: Энергия, 1979. – 232 с.

4.Вавилов Е.Н., Портной Г.П. Синтез схем электронных цифровых машин. – М.: Советское радио, 1964. - 440 с.

5.Глушков В.М. Синтез цифровых автоматов. – М.: ГИФМЛ, 1962. – 476 с.

6.Закревский А.Д. Логический синтез каскадных схем. – М.: Наука. 1981. –

414 с.

7.Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.1. Комбинаторные алгоритмы дискретной математики. – Мн.: ОИПИ НАН Беларуси, 2004. – 226 с.

8.Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.2. Оптимизация в булевом пространстве. – Мн.: ОИПИ НАН Беларуси, 2004. – 240 с.

9.Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. В 3 кн. Кн.3. Проектирование устройств логического управления. – Мн.: ОИПИ НАН Беларуси, 2006. – 254 с.

10.Зыков А.А. Основы теории графов. – М.: Наука, 1987.

11.Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.

12.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергия, 1988. – 480 с.

13.Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. – М.: Энергоатомиздат, 1989. – 328 с.

14.Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990. – 384 с.

15.Миллер Р. Теория переключательных схем, т.I. – М.: Наука, 1970. –

416 с.

16.Миллер Р. Теория переключательных схем, т.II. – М.: Наука, 1971. –

304 с.

17.Поспелов Д.А. Логические методы анализа и синтеза схем. – М.; Л.:

Энергия, 1964. – 320 с.

18.Скляров В.А. Синтез автоматов на матричных БИС. – Минск: Наука и техника, 1984. – 287 с.

19.Фридман А., Менон П. Теория и проектирование переключательных схем. – М.: Мир, 1978. – 580 с.

20.Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986. – 384 с.

176

177

178

схема комбинационная 135

Таблица выходов 138

–истинности 52

–переходов 138

–– и выходов 138 транзитивность 20

Факторизация 47.4 396 формула 55 функция 18

–булева 52

–– не полностью определенная 54

–– полностью определенная 54

–– слабо определенная 108

–– частичная 54

−возбуждения 172

−всюду определенная 18

– выходов 136

– переходов 136

Цепь 27 − порождаемая парой состояний 145 цикл 27

Число доминирования 29

−независимости 30

−хроматическое 36

Эквивалентность состояний 144 эквивалентные матрицы 78 эквиваленция 55

элемент определяющий 94

Ядро 98

179