Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 55
Текст из файла (страница 55)
образуют полный попграф. В каждое ребро этого полного попграфа помещаем дополнительную вершину; б) имеется вершина и„которая смежна с т (тп ) хв, Л вЂ” ра- диус рассматриваемой окрестности) вершинами окрестности ра- диуса Я вЂ” 1. В этом случае на каждое из тп — В ребер, выбранных произвольным образом и соединяющих вершину иа с вершинами окрестности радиуса Й вЂ” 1, помещаем дополнительную вершину; 305 1Н 1!а е ГН1 б Рнс. 4.30 304 Гл.4. Теория фо мальных грамматик и аатомотае в) число вершин »чн рассматриваемой окрестности радиуса В больше числа сочетаний нз л(С) по В, (С) где ('(й)) — число вершин л(С)-мерного куба, коды которых отличаются в В разрядах от кода центра соседнего кодирования.
Тогда введением дополнительных вершин, смежных с одной стороны с вершннамн окрестности радиуса  — 1 н с другой стороны с вершинами, наличие которых обусловливает выполнение неравенства Фн- >О переводим избыток вершин в окрестность радиуса В+ 1 так, чтобы число вершин окрестности радиуса не превосходило ('( )).
14.6. Построение выходных функций После введения дополнительных вершин согласно пп. а)-в) производим соседнее кодирование вершин окрестности радиуса В. 3. Увеличиваем радиус рассматриваемой окрестности на 1 н переходим к и. 2), н так до тех пор, пока не получим искомое соседнее кодирование внутренних состояний автомата.
При выполнении и. 2) может возникнуть ситуация, когда размерности гиперкуба не хватает. В этом случае размерность увеличиваем на 1 и переходим к и. 1). Праиллюстрнруем этот алгоритм кодированием вершин графа переходов С (рнс. 4.28, а). Походим вершины максимальной степени. Таких вершин в ~рафе две, 51 и Яе, степень равна 4. За пеитр соседнего кодирования выбираем эти вершины по очереди. Сначала выбираем вершину 51 Н прнеааиааЕМ ей коД 0000.
Тогда вершины Яю Яе, ое, Яе образуют аарестность радяуса»т = 1 (рнс. 4.30,а). Условие пп. а)-в) для этой окрестности не выполняются, следовательно, имеется соседнее кодирование, Оно следующее: $7 — 0001, Я~ — 0010, Я~ — 0100, Яз — 1000. Окрестность радиуса Н = 2 образуют вершины Яз, Яе, Я». Прн кодировании вершин этой окрестности получаем противоречие, соответствующее переходу Яе -Ф Яе. Расстояние по Хеммннгу меиду подами этих вершин равна 3, следовательно, введением двух неустойчивых состояний, Яе н Яя, согласуют этот переход. ВваЛнмая вершияа Яя принадлеи»П окреетнаетп рзлиУса и = 3, в нее не входит и вершина ое В реаультате получаем коды остальных состояний Яз, Яе, Я» и вновь введенных Я и Яя» Я. — ОО11, Я, — О1О1, Я, — О11О, Я. — 11ОО, ля — 111О.
Прн выборе в качестве пеепра соседнего кодирования вершины Яе, действуя па этому алгоритму, иолу гаем (рнс. 4. 30, б) противоречие прн переходах 51 -е Яе и Ят -Е 81. Для устранения этих противоречий необходимо ввести четыре неустойчивых состояния: Я», Яь, о», Яя. Соседние коды этого способа кодирования ИМЕЮГ СЛЗДУпяинй ВНЛ1 ое 1001, оз 0101, сз — 0001 с» 0110, ае 0011, Яе — 0100, Ле — 0111, Ле — 1000, Йе — 0000, Я» — 1101, 8ь — 1111, 8, — 1010, Яя — 1011.
34.6. Построение выходных функций и функций возбуждения ийыяти автомата После абстрактной оптимизации и кодирования внутренних состояний автомата автоматный оператор задается системой функций возбуждения н выходных функций. Перед построением этой системы рассмотрим элементы памяти: триггер с раздельными входами н триггер со счетным входом. Триггером с раздельными входами называется автомат, таблица состояний н граф переходов которого имеют соответственно внд табл.
4.9. и рнс. 4.31, а. Рассмотрим реализацию триггера с раздельными входами в нмплнкатнвном базисе (-~, О). Используя метод прямого моделирования, получаем А+с = (Л» + *нуле) + Ход»» 307 Таблица 4.12 х и о 1 Хлул л а б Рис. 4.31 Л аул х, Рис. 4.32 306 Гл.4. Теорил формальиых грамматик и авуломатов и ее реализация в импликативном базисе представлена на рис. 4.32. Постоянная времени т определяется задержкой сигнала от входов к выходу в схеме триггера. Таблица 4.9 Триггером со счеуииым входом называется автомат, таблица состояний и граф переходов которого имеют соответственно вид Таблица 4.10 табл. 4.10 и рис.
4.31, б Согласно табл. 4.10 функция триггера со счетным входом имеет вид ву+т(хсчы вс) = хелуана 1у хсчсгы Возбуждение счетного входа переводит триггер в противоположное состояние. Читателю в качестве упражнения предлагается синтезировать схему триггера со счетным входом в коимпликатнвном базисе.
Рассмотрим построение выходных функций и функций возбуждения элементов памяти на примере закодированного автомата (рис. 4.27). Для определенности в качестве элементов памяти возьмем триггеры со счетным входом. Каждый элемент памяти своим значением разбивает все множество состояний на два класса (табл. 4.11). Т а блиц а 4.11 14.6. Построеиие выходных фуикчил Для уменьшения функциональной связности функций возбуждения, используя разбиение множества состояний на классы, построим таблицы, указывающие условия переключения элементов туамяти (табл. 4.12).
Анализ построенных таблиц показывает, что функция возбуждения первого элемента памяти зависит от входного вектора и ,состояния этого элемента. Таблица переходов второго элемента памяти противоречива, так как переходы 0 -у 0 и 0 -+ 1 происходят при одном и том же значении входного вектора, равном О, и переходы 1 — у '0 и 1 -+ 1 — при значении входного вектора, 'равном 5. Недетерминированность переходов имеет место в таблицах, соответствующих третьему и четвертому элементам памяти: в третьей таблице переходы 0 -+ 0 и 0 -+ 1 происходят при одном и том же ;значении входного вектора, равном 4, в четвертой таблице — переходы 0 ~ 0 и 0 -+ 1 — прп векторе, равном О.
Условия переходов, 'обозначенные в таблицах прочерком, соответствуют переходам из Йеустойчивых состояний Я, ЯЛ, Я„, и для устранения недетерми,леированности при этих переходах необходимо учитывать состоя,',пия всех элементов памяти. Для определения минимального коЛичества элементов памяти, состояния которых необходимо учитывать при ликвидации противоречивых переходов, вызванных одним и тем же значением входного вектора в строках таблиц, построим табл. 4.13. 309 Твблиив 4.13 овин рьбоиеа ебааеен 1000100 1010101 МЯО1ОО НПЮЩ1 0000000 0ЫОООО шщщ 308 Гл.4. Тео ил формальных г амматик и автоматов Первые два столбца таблицы соответствуют противоречивым переходам при переключении второго элемента памяти, остальные два — при переключении третьего и четвертого элементов. Для устранения этих противоречий достаточно входной вектор 0 расширить внутренней переменной хз+ (так как этой переменной различаются коды состояний Я2, Яз), векторы 4 н б расширить внутренней переменной х+ (так как коды состояний 54, Яб различаются переменной х+).
Окончательно функции возбуждения элементов памяти имеют следующий вид: 1о1(Х! 31 ) = 21 х1х2х31 + + ф2(Х, 21, 32, хз, хе ) = 32 х1Утхз Ч У2 (хгхтхзхз Ч У1+хз 24+), 9~3(Х> хз ~ хе ) = хз х1хтхз Ч гз х1х2хзхе ~ 'ре(Х1 31 ~ 32 у 33 ) 34 ) — 34 (х1х2хз Ч 31 32 33 ) Ч хе х1х2хзхз Полученная система функций возбуждения может быть еще более упрощена, если учесть, что булевы функции, описывающие работу рассматриваемого автомата, являются частйчно определенными. Рассмотрим это упрощение на примере второй выходной функции.
Рабочая и запрещенная область булевых функций автомата определяются его переходами. В рассматриваемом автомате имеем 14 переходов, которые определяют табл. 4.14. Твблиив 4.14 4.8. Построение выходных функций Из 128 тачек 7-мерного куба выходная функция У2 определена иа 11 тачках, из них на 4 она принимает единичное значение рабочая область функции), на остальных 7 — нулевое значение запрещенная область функции). Используя таблицу различий (табл. 4.15), выделим пучки максимальных интервалов для каждой точки рабочей области. Твблиив 413 В результате сжатия таблиц различий и их покрытия получаем, что первая рабочая точка 1101010 содержится в максимальных интервалах --01---, --0 — 1-, вторая тачка 0100000 содержится в -10 — --, третья точка 0000010 — в — 0--1-, четвертая точка 1110110 — в — — — -11-.
Следовательно, выходная функция у2(Х, Я+) имеет следующий вид: ут(Х, Я+) = хз+(хт Ч 32+) Ч хтУз. Минимизация булевой функции была проведена без учета переходов из неустойчивых состояний. В зависимости от назначения управляющего автомата и физического представления 1 и 0 входные векторы 2+, соответствующие неустойчивым состояниям, от- 310 Гл.4. Теорие фо мальньтх г амматик и аетоматое носят в запрещенную область при минимизации логического выражения, описывающего условия истинности единичнога значения минимизируемой булевой функции, или в запрещенные области при минимизации логических выражений, описывающих условия истинности единичнога и нулевого значения булевой функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
