Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 80
Текст из файла (страница 80)
рис. 5.29,а). Граф сцепления С,иг для первой внутренней переменной г1, представленный на рис. 5.23,а, не содержит запрещенных фигур— циклов нечетной длины. Кодирование по первой переменной гт заключается в раскраске двумя цветами, 0 н 1, вершин графа сцепления Саит (рис. 5.36, а). Строим граф сцепления ьлаиг для второй переменной гг, для чего соединяем ребром соцветные вершины графа сцепления (рис. 5.36,5). 3 5.6. Семантическое ослабление функциональной свлэноспви 441 Гл.
5. Прикладнал »пеорил алгоритмов 440 Запрещенными фигурами в графе С,цт будут циклы нечетной длины, содержашие один путь, составленный из ребер графа боцг. Циклы нечетной длины, не содержащие таких ребер, не являюхся запрещенными фигурами, хак как эта цикличносхь образовалась Рис.' 3.36 из-за условия однозначного кодирования сосхояннй, а не из-за условия недехерминированности переходов. Запрещенными фигурами в графе в ',цт являюхся циклы нечетной длины с носителями: ввж1 4» (Я1»Яа» Яго)» ввж2 4» (Я1»Я6» Я11)» вгжз 4» (Я2» Яэ» Ях)» »Ожа С» (Яг ЯХ ЯЕ) »Ожв С» (ЯЫЯШ,ЯГт), вгже 4 ' (Я1» Яа»Я6)» вгж7 Со (Я1» ЯВ» Яв» Я10»Я12) Запрещенные фигуры вд; позволяют последовательным кодированием минимизировать функциональную связность элеменхов памяти.
Рассмотрим другой, более быстрый (параллельный) способ определения минимально связных кодов внутренних состояний, для чего введем понятие предквазиполных графов квазиплотности К+ 1. Граф Я, называется предкеаэиполным графом кваэиплотности К + 1, если после раскраски его в х цвехов и соединения одноцветных вершин он преобразуется в квазиполный граф квазиплотности К + 1; при этом К+ х является минимальной величиной при различных раскрасках еле и это преобразование не выполняется при удалении нз Св хотя бы одного ребра.
Т е о р е м а 5.6. Запрси4енной фигурой функциональной нссвяэности элеменгпов памяти 'является прсдкваэиполный граф кваэиплотности К + 1 в графе сцепления (К вЂ” эначность логики, в которой описываетса поведение автомата). Для случая булевой логики запрещенной фигурой являехся цепь длины 2, обозначим ее Яе.
Рассмохрим кодирование внутренних,сосхояний автомата на основе использования найденных зацрещенных фигур вдж и Я„ кохорые соотвехствуют последовательному и параллельному методам кодирования. Последовательный меход проиллюсхрируем кодированием графа переходов вл, предсхавленного на рис. 5.29, а. Выше было найдено кодирование по внутренней переменной г». Для определения кодов по вхорой переменной схроим семантическую хаблицу. Столбцам первой подтаблицы взаимно однозначно соохвехсхвуют запрешенные фигуры — циклы нечетной длины, строкам — пара сцепленных состояний (ребро графа сцепления С,цг) и на пересечении (о, у) ставится 1, если в-е ребро входих в у-й цикл, 0 — в противном случае.
Предсхавим эту подтаблицу в виде следующей матрицы: 4)ж» 4)же Яжв Ожв Яжв Ожа Яжв 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 О 1 0 О О О О 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 минимальным покрытием являехся ((Яо Яго) (Яг Яв), (Яз Яг)). Схрокам вхорой подтаблицы взаимно однозначно соохветсхвуюх пары сцепленных состояний, столбцам — входные векторы, кохорыми они сцеплены, и на пересечении (в, у) схавится 1, если в-я пара сцеплена у-м входным вектором, и 0 в противном случае. Предсхавим эту подтаблицу в виде следующей матрицы: 1 3 3 4 $ (Я, Я ) (Яв» Я»о) (Я», Яв) (Яв, Яп) ° (Яе» Яв) (Яе, Я») (Я~, Яе) (Я»о, Яи) Покрыхие ((Яа, Яго), (Ям Яв), (Ят, Ях) ) схолбцами элементов покрыхия первой цодхаблицы указывает, какие входные векхоры необходимо расширить для устранения недетерминированности при кодировании внутренних сосхояний по второй переменной.
Такими входными векторами являюхся 2, 3, 5. После их расширения, кохорое отметим шхриховкой, исходный граф сцепления С,ц~ 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 О 0 Яп Яв) Яв, Я»о) Яп Яв) Яа, Яп) ° Яе, Яв) Яе» ЯТ) Я», Яе) Я»о, Яво) 442 01 Рис.
5.37 Таблица 5.15 Гл. 5. Прикладнал творил алгоритмов преобразуехся в граф, представленный на рис. 5.37, а. Раскрашивая зтох граф двумя цветами, кодируем состояния по вхорой переменной (рис. 5.37, а). После соединения ребром вершин, имею- щих одинаковые спекхры красок, запрещенные фигуры в данном случае образоваться не могут. Следовахельно, сушествуех кодирование по третьей и четверхой переменным «з, «4 (рис.
5.37,6). Окончательно коды с минимальной функциональной связносхью элеменхов памяти имеют следующий вид: Яд — 0001, Яг — 0110, Яз — 0010, Я4 — 1110> Яб — 1001, Яв — 1010, Я7 — 1100 Яв — 1101, Яе — 0011, Яш — 0111, Ядд — 0101, Ядг — 1000. Построим функции возбуждения элементов памяти (для определенности — триггеров с раздельными входами) с соотвехствующей минимальной функциональной связностью. Разбиение всего множесхва внутренних сосхояний на два подмножества согласно значениям внутренних переменных сведем в табл. 5.15. Согласно построенной хаблице функции возбуждения единичных входов имеют вид уддд(Х, «1 ) = «1 (хдхгхз Ч хдхгхз Ч хдхгхз), 15.6.
Семантическое ослабление функциональной свлгности 443 уддг(Х, «,, «,) = -+ + = «г (хдхг*з Ч хдхгхз Ч хдхгхз Ч хдхгхз«1+ Ч хдхгхз), уддз(Х, «3 ) = «3 (хдхгхз Ч хд хгхз Ч хдхгхз Ч хдхгхз), 2214(Х «4 ) «4 (хдхгхз ч хдхгхз ч хдхгхз ч хдхгхз) Функции возбуждения нулевых входов имеют вид удод(Х) «1 ) «д (хдхгхз Ч хдхг«3 Ч хдхгхз Ч хдхгхз)) 9дог(Х~ «2, «1 ) = = «+(хдхгхз ч хдхгхз ч хдхгхз«+ ч хдхгхз ч хдхгхз), удоЗ(ХФ «3 ) «3 («1«2хз Ч хдхгхз Ч хдхгхз), дро4(Х, «4 ) = «4 (хдхгхз Ч хдхгхз Ч хдхгхз Ч хдхгхз).
Введем понятие пративополохеиых кодов. Два кода называются противоположными, если они отличны в каждом разряде. Очевидно, чхо если сцепленным состояниям соохветствуюх противоположные коды, хо элементы памяти являются функционально несвязными. Рассмотрим противоположное кодирование на следующих примерах. Пусхь граф переходов 0 задан своей хаблицей переходов (табл. 5.16), каждой схроке которой взаимно однозначно соохветствует входной вектор Х;, столб- Таблица 5.15 цу — внутреннее состояние Я и в клетке (1, у) указывается внутреннее состояние, в которое авхомат переходит при входном воздействии Х; из сосхояния Я.. Внутренние состояния Яд, ог, Яг, Я5, 'ЯЗ, Яб, 'ЯЗ, ЯО1 Я5, Яв Я4, Яв сцеплены соохвехственно входными векхорами 1, 1, 3, 4, 4 и 2.
Махрица смежности графа сцепления для заданного случая имеет вид, представленный в хабл. 5.17. Плетка (1, З) таблицы содержит значения входных векхоров, кохорыми соохветсхвующие состояния сцеплены. Таблица 5.17 Ь 5.5. Семантическое ослабление функаионольной солености 445 Гл.б. Приклоднол теорие олеори>имое 444 Строим семантическую таблицу, состояшую иэ двух подтаблиц. Столбцам первой подтаблицы взаимно однозначно соответствуют запрещенные фигуры Я, — пути длины 2 графа сцепления, строкам — ребра и в клетке (ь', у) стоит 1, если 4-е ребро содержится в у-м цути, и 0 в противном случае. Строкам второй подтаблицы взаимно однозначно соответствуют ребра, столбцам — входные векторы, взвешивающие эти ребра, и в клетке (ь, у) стоит 1, если у-й входной вектор взвешивает ье ребро, и 0 в противном случае.
Для устранения недетерминированиости переходов необходимо расширить входные векторы, вошедшие в покрытие семантической таблицы. Для этого необходимо покрыть столбцы строками в первой подтаблице н найденное покрытие покрыть столбцами во второй подтаблице. Таванив ьлэ Для рассматриваемого примера семантическая таблица (табл. 5.18) содержит запрещенные фигуры, имеюшие следуюший вид: Чы = ((Яг> Яг), (Яг> Яьу)> ьеег = 1(Яг Яь), (Яь, ЯвЦ, Язэ = ((Яг> Яь)> (Яь> Ю)> Юы = ((Яз> Яь), (Яь, Яв))> Яэь = ((Яь> Яэ)> (Яэ> Яву)» язв = ((Яь> Яв)> (Яз> Яву)> 4еы = ((Яь> Яв)> (Яв> Яе))> ага = ((Яз Яв) (Яв Яь)).
В данном случае покрытие первой подтаблицы образуют вторая, четвертая и пятая строки; покрытие этих строк во второй подтаблице образуют первый и четвертый столбцы. Следовательно, для противоположного кодирования внутренних состояний необходимо на графе сцепления удалить ребра (Яг, Яь), (Яь, Яв), (5э Яв). После такого сужения сигнатуры графа сцепления он не содержит запрещенных фигур и, следовательно, возможно противоположное кодирование: 51 011> Яг 100> Яз 101> Яь — 001, Яь — 010, Яв — 110. Ребра из графа сцепления удаляются путем расцепления соответствующих внутренних состояний расширением сцепляюшего их входного вектора. Расширение осуществляется приписыванием минимального количества внутренних переменных, которыми от- личаются расцепляемые состояния, соответствующему входному вектору.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
