Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 81
Текст из файла (страница 81)
Для получения покрытия семантической таблицы состояния Яг, Яь необходимо расцепить расширением входного вектора Угзгхз состояния Яь Яв и Яз, Яв — расширением вектора хгУгУз. Первое расцецленйе можно осуществить двумя способами: приписать ко входному вектору УгУгхз либо первую внутреннюю переменную г~г, либо вторую гг+, т. е. переход иэ состояния Яг в Яз взвешивается соответственно вектором УгУгхзь+ либо вектором УдУгхз~гг .
Для определенности выберем первый способ расширения входного вектора УгУгхз. Обозначим УгУгхэе+ через 1', а УгУгхз7+ — через 1". Расцепление состояний Яь и Яв осуществляется приписыванием первой внутренней переменной е~+ ко входному вектору х1УгУэ. Переход из состояния Яь в Яь осушеспшяется цод воздействием хгУгУзл~~ (обозначим его 4'), переход иэ состояния Яв в Яь — под воздействием вектора хгУгУзл+ (обозначим его 4н). Расцепляемые пары внутренних состояний, пересечение которых не пусто, называются связными, если они сцеплены одним и тем же значением входного вектора.
Расцепление связных пар производится совместно. Коды состояний третьей сцепленной пары Яз, Яв отличаются двумя переменными, следовательно, расцепление этих состояний можно провести двумя способами, используя вторую или третью переменную. При первом способе переход иэ состояния Яз в Яь осушествля,Втся под воздействием вектора хгУгУзуг+, переход из Яв в Яе— под воздействием хгУгУзг+. При втором способе приращениями ,й>октара х1УгУз являются соответственно г+, г+э. Пары Яз, Яв и Яь, Яв связаны входным вектором х1Угхэ.
1ледовательно, необхо',Фимо произвести их совместное расцепленне, которое заключается :й логическом умножении условий расцепления для состояния, во:Шедшега в пересечение связных пар. В нашем случае таким со,'стоянием является 5в. Согласно условию расцепления связных пар внутренних состояЗ1ий переход из состояния Яв в Яе осуществляется под воздей;йтвием вектора хгУгхгУ+ г+: згхгхзгг 5ьхгхгхзлг хгхгхэгг Лг > цдба вектора хгУгУзл+Уз+: х1Угхэгг ос х1УгУзгз = хгзгУзгг Уз .
Для определенности выбираем первый способ расцепления, абойначив при этом вектор хгУгУзгт+г+ как 4". Окончательно попу- Гл.б. Прикладнал тео иа алгоритмов 446 15.6. Семантическое ослабление функциональной свлэности 447 чаем следующую систему функций возбуждения: Л(Х «1 «2 ) = «1 Х1ХЗХЗ Ч «1 (Х1ХЗХЗ«2 Ч хгхзхз«1 «2 Ч х1ХЗХЗ), 22(Х~ «1, «2 ) = «2 (х1хгхз ч «1«2«з ч х1«2хз«2 ) ч Ч «2 (Х1ХЗХЗ Ч х1х2хз Ч х1«2ХЗ«1 «2 ), 23(Х, «1, «2, «3) = «з(х1«2«3«, чхгх2хз«1 «2 ч«122«3 ч Ч У1«2ХЗ«1 ) Ч «3 (Х1ХЗХЗ Ч х1хзхэ Ч х1хзхз«2+), которой соответствует функционал ~р(С), равный 4.
Здесь и ниже для определенности в качестве элементов памяти взяты триггеры со счетным входом. Найденные запрещенные фигуры определяют достаточные условия функциональной несвязности элементов памяти. Следовательно, после кодирования возможно уменьшение значения 22(с) аз аида 5 13 пУтем анализа таблиц смены сос- тояний элементов памяти.
Каждый г+ О 1 элемент памяти своим значением *+ 51, Яь, Яь Яв, Яь, Яв разбивает все множество внутрен«+ 5, 5а .с, .с, .с, .св них состоаний нв два класса. Для рассматриваемого примера это разбиение представлено в виде табл. 5.19. Таблицы смены состояний для графов переходов элементов памяти приведены в табл.
5.20. Табдидв 5.20 В результате анализа таблиц смены состояний на детерминированность получаем, что штриховка входных векторов может быть снята везде, кроме векторов 4' и 4а', которые устраняют недетерминнрованность при переходе из единичного состояния второго элемента памяти и нулевого состояния третьего элемента памяти.
При этом для отличия вектора 4т от 4' достаточно взять его в виде Х1«2ХЗ«1. Теперь функции возбуждения памяти окончательно имеют вид 21(Х1 «1 ) = «1 х1хзхз ч «1 («1«233 ч х1«2«3) ~ уз(Х, «1, «2 ) = «2+(«1хзхз Ч х1хзхз Ч х1хзхз) Ч Ч «2 (хгхзхз Ч хгхзхз Ч хгхзхз«1 )~ 23(Х~ «1 1 «3 ) гз (х1х2хз Ч «1хзхз Ч х1ХЗХВ«1 ) Ч Ч «3 (х1«2«3 Ч х1хзх3 Ч хгхзхз) И <р 1Л) св 2. аким образом, минимизация перекрестных связей между элементами памяти сводится к выполнению трех этапов. 1. Устранение запрещенных фигур путем расширения входных векторов и противоположное кодирование внутренних состояний.
2. Анализ полученного кодирования с целью ликвидации избыточного расширения входных векторов. 3. Выписывание функций возбуждения элементов памяти и опрелеление значения 22(С). В случае автоматов, для которых коэффициент плотности соответствующего графа сцепления велик и которые имеют большую размерность, трудоемкость покрытия семантической таблицы увеличивается, и если для ее реализации проектировщик не обладает соответствующими вычислительными мощностями, то первый пункт можно выполнить с меньшими вычислительными затратами, для чего предложим следующий алгоритм реализации п. 1.
1. Выделяем в граф сцепления частичные подграфы, ребра каждого из которых взвешены одним н тем же входным вектором. 2. Производим раскраску вершин каждого из этих графов, нумеруя краски 1, 2, ..., и. При этом номер краски указывает количество штрихов у входного вектора на соответствующем переходе. 3.
Штриховка входных векторов физически реализуется различными состояниями элементов памяти. Раскраска (см. и. 2) цорождвет разбиение множества внутренних состояний, которое определяет коды внутренних состояний. Проиллюстрируем расширение входных векторов. Таблица переходов автомата — в табл. 5.21. Твблида 5.21 Таблида 5.22 Таблица переходов автомата определяет матрицу смежности графа сцепления (табл. 5.22) и матрицы смежности частичных Гл.б. 5Урикладнол озеорив еле изюмов 448 16.6.
Семанозическое ослаб.зение функциональной свлэносизи 449 подгРафоп сцеплениЯ Ссл, сзс6, сзсс (табл. 6.23, а, б, в) по входным пекторам а, Ь, с соотзетсткенно. Твблилв 5.23о Твблядв 5.23б Твблнлв 5.23в Кзазиплотность графов С„, С,4, 4з„раппа соотзетстзенно 3, 2, 2. Следопательно, их хроматические числа разны соотпетстзенно 3, 2, 2. Раскрашипая эти графы, получаем разбиение вершин графов Ссс — Кдв = (Яда 55) Кзс = (Яэа 54) Кзс = (Яз), Ссб К16 — (52а 54)а К26 (515 55)~ ~се К1с = (Яз)ь К2с — (Ядю 52~ 54~ 55). Раскраска дз„, С,4, сз„порождает разбиение множества зну- тренннх состояний, которому соотзетстзует кодирующее дерево (Яда 52, Яз, 54а 55) — + (55) (51 52а 54 55) — + (51 55) (52 54) з котором на ребрах указаны соотзетстпуюшие значения внутрен- них переменных.
Согласно кодируюшему дереву штриховка, соотэетстзующая полученной раскраске, будет реализована, если внутренние состоя- ния будут иметь коды Яз —, Осздсзз, Яд — 10сзз, 55 — 1042„ 52 — 11425, Я4 — 114зб, где ол = О, 1 (з = 1 — 6), причем для однозначности кодирования полагаем, что сзз = 424, сзб = сзе. Конкретизируя а;, окончательно получаем коды Яз — 011, 51 — 100, 55 — 101, Я,— ПО, Я,— Ш. После получения кодек переходим к и.
2 первого алгоритма: устраняем избыточную штриховку входных векторов. В резуль- тате получаем, что для расцепления остазшихся пар (Яз, 54), (Яз, 55), сцепленных пектором а, пар (Яд, Яэ), (Яд, 54), (Яэ, Яб), (54, 55), сцепленных зектором Ь, и пар (5ю Яз) (Яз, Я4), сцепленных вектором с, достаточно зектор а расширить переменной лд+ до а' = аУ+ и ал = аз+, так как краска Кз, отличается от красок Кд„К2, этой переменной; аналогично вектор Ь нужно расширить переменной лз~ до Ь' = Ьзз+, Ьв = Ьлэ~; вектор с расширить ПЕРЕМЕННОЙ Лд~ ДО С' = СУ+, С" = СЛ+. С учетом йрозеденных расширений входных пектороз первоначальная таблица переходов семантически зквизалентируется табл.
6.24, в которой около расширяемого зектора з круглых скоб- Твблилв 5.24 ках указан способ расширения при вычислении каждой внутренней переменной (лд, лэ, зз); при этом прочерк означает, что соотзетстзующая переменная вычисляется без учета расширения Твблнлв 5.25 входного зектора, т.
е. не зази- ,+ 1 сит от других внутренних пере- '+ з, лз 5 21 аа 5 менных. Полученные коды разбизают ПСЕ МНОжЕСтВО СОСтОЯНИй СОГЛаСНО ЗЗ+ Уз а 82 ЛЗ, Ла, 85 табл. 6.26. Эти разбиения определяют таблицу смены состояний элементов памяти (табл. 6.26). Твблялв 5.25 Табл. 6.26 задает функции возбуждения злементоп памяти вида уд(Х, л+, з2+) '= л+с У зд+Иэ+, дз(Х, л4, лз~, зз~) = лз (а ЧЬл24Ч с)Ч за алд, для которых ар(С) = 4. !5 З.
Л. Горба оа 55.6. Семантическое ослабление функциональной свлэносити 451 Гл.5. Прикладная теория алгоритмоа 450 Рассмотрим этот пример с учетом характера переходов, анализируя при этом возможность раскраски сцепленных состояний одной краской кри их переходах код воздействием сцепляюшего входного вектора в соцветные состояния. Граф сцепления (табл. 5.22) содержит циклы нечетной длины вида Ст = ((Яь 53), (Яз, 54),(Яь 54)), Сг = ((Яь Яз),(52, 53), (5ь Яг)), Сз = ((Яг~ Яз)~ (53155)т (Ягт 55))т С4 = ((53, 54), (54, 55), (Яз 55)).
Покрывая семантическую таблицу (табл. 5.27), отметим, что для получения первого разряда кодов внутренних состояний необ- Табяииа 5.27 ходимо расцепить внутренние состояния (Яь Яз) и (Яз, Яб). Перед тем как производить это расцепление путем расширения входных векторов, которыми эти состояния сцеплены, рассмотрим усло- виЯ их соцветной окРаски. ДлЯ того чтобы веРшины (Яь 531 были соцветны, необходима соцветность вершин (Я4, Яб) и (Яз, 55): тт(Яг) = тт(53) 4- (а(54) = ут(55)) 55 (ут(53) = 14(55)). Состояния (54, 551 сцеплены, следовательно, для того чтобы они были соцветны, необходима соцветность состояний (Яь Яг) н (Яз, 54): к(54) = тт(55) < — (к(Ят) = Ц52)) 55 (Ц53) = Ц54)). Состояния (Яь Яг) сцеплены, следовательно, для их соцветности необходима соцветносгь состояний (Яг, Яз) н (54, 55): ~(Яг) = тт(52) 4 — (тт(52) = 5(53)) 55 (тт(54) = тт(55)) То же самое имеем и для вершин (Яг, 53) и (Яз 54) соответственно: к(Яг) = тт(53) < — (к(54) = тс(55)) 55 (Ц5з) = ЦЯ4)), тт(Яз) = ут(54) 4- (ЦЯ4) = ЦЯ5)) 55 (ттт(Яг) = »1(53)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
