Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 56
Текст из файла (страница 56)
Для учета переходов, соответствующих неустойчивым состояниям, необходимо проанализировать в упрощенном логическом выражении конъюнкции, состоящие только из внутренних переменных х+, и если эта конъюнкция обращает на неустойчивых переходах логическое выражение в 1, то приписываем отрицания внутренних переменных, кодируюших неустойчивые состояния, с целью устранения истинности на этой конъюнкции. В нашем случае необходимо к конъюнкции х+х+ приписать отрицание внутренней переменной хеЬ, так как уг — — 1 при неустойчивом переходе нз состояния Я». Если относить входные векторы, соответствующие неустойчивым состояниям, в запрещенные области до покрытия таблиц различий, та в общем случае, как нетрудно показать, будет усложнение окончательного логического выражения.
В рассматриваемом случае итоговое выражение для рэ(Х, Я+) имеет вид Ут(Х, Я Ь) хе Хз (ХЗ Ч Хт Х,+) Ч Хэ*з Определение упрощенного вида первой выходной функции оставляем читателю в качестве упражнения. 34.Т. Синтез логических структур в топологических базисах Рассмотрим проектирование логической схемы как синтез соответствующего булеза графа. Разобьем все множество базисов на три класса: топологические, функциональные, нейронные. В топологических базисах полнота используемых при синтезе функций достигается соответствующим физическим моделированием двоичных переменных и определенным соединением заданных элементов. Такие базисы образуют все ключевые элементы, токовые ключи, криотроны, переключатели света, спейсисторы, деплисторы, унитроны и другие вентильные элементы, которые используются в вычислительной технике как элементы с высоким быстродействием. В функциональных базисах элементы независимо от их соединения и физического моделирования двоичных переменных реализуют функции, образующие полную систему булевых функций.
К таким базисам относятся, например, элементы, которые реализуют функции Шеффера, Вебба, импликации и др. Нейронные элементы обеспечивают полноту путем их индивидуализации. 14 7. Синтез логических структнур е типологических базисах 311 Множество топологических базисов в свою очередь разобьем ка четыре класса. Первый и второй классы образуют элементы, пропускающие информационный сигнал в одном направлении при совпадении значения управляющего сигнала с буквой, взвешивающей этот элемент.
Но в элементах первого класса прошедший сигнал распространяется по каналам с односторонней проводимостью, а в элементах второго класса — по каналам с двусторонней проводимостью. К первому классу относятся днодно-вентильные элементы, в случае оптической обработки информации с использованием волоконной техники — переключатели света, ко второму — вентильные элементы (например, спейсистор-триод). На входах схемы, составленной из рассматриваемых элементов, как и на входах системы, построенной из элементов любого топалогического базиса, используется парафазное представление двоичной информации. Третий и четвертый классы образуют элементы, пропускающие информационный сигнал в обоих направлениях при совпадении значения управляющего сигнала с буквой, взвешивающей этот элемент. В элементах третьего класса прошедщий сигнал распространяется по каналам с односторонней проводимостью, а в элементах четвертого класса — по каналам с двусторонней проводимостью.
К элементам третьего класса относятся, например, туннель- троны и диодно-контактные элементы; к элементам четвертого— ключевые элементы с двусторонней проводимостью (криотроны, контакты). Таким образом, все множество топологических базисов разбита на четыре класса по двум призна«ам: по проводимости элемента и сннеас по проводимости соединительного канала. Рнс.
4.33 Основой элементов третьего класса является нейрон, формальная модель которого предложена американскими учеными У. Мак-Каллоком и У. Питсом и развита С.Клини, Д.Калбертсоном, Дж.фон Нейманом и другими. Условия возбуждения нейрона описываются функцией вида 1 р(хт, хю ..., хь) = ь 1, если ~,х;тг;>Р, О в противном случае, где х; = О, 1; тю; — вес т-го синапса (места контакта аксона и тела нейрона (рис. 4.33)); Р— порог возбуждения нейрона. 312 Гл.4. Теа ие фа малькых грамматик и аетоматае Фиксацией весов скнапсов и порога нейрон настраивается на реализацию любой булевой функции от 1е переменных. В качестве функционала качества проектируемой схемы возь- мем количество переключательных элементов, содержащихся в ней. Этот функционал в дальнейшем будем называть слож- ностью Х (Я) схемы Я.
Рассмотрим проектирование логических схем в топологиче- ских базисах первого класса на примере булевой функции 1(хд, хг,..., хи), заданной своей дизъюнктивной нормальной формой (ДНФ): 1(хд! хг, ..., хи) = хехвхвЧ хдхвхдо Ч хдхгхзхехв Ч Ч хвхэхдд Ч хдхгхв Ч хахвхдд Ч хтхвхи Ч хгхзхт Ч Ч х1хвхи Ч х3хеха Ч хдхвхдд Ч хдхгхи. Каждая простая имплнканта реализуемой булевой функции взаимно однозначно соответствует пути в структурном графе. При этом первичные термы х, входящие в простую импликанту, взве- шивают вершины соответствующего пути. Реализуемая булеза функция 1 определяется моделью дР,(1): )р,(~) = (У, Я~, 5~), Я~ С Уз, Я~ С Ув, У = (хд.хг хз х4 хв хв х» хв хв хдо хидх! ~3 = ((Х4> Х5> Х9)> (Х1! Х5! Х10)! (Х5! Х9! Х11 ! (Х1> Хг! Хв > 1 2 4 5 (хв, хэ, хдддд (х» хэ хи), (хг! хз> хт)! (хи хв! хи)! в 2 в 9 (хз, х4, хв, (хд, хв, хдд, (хд, х» хи) ) ! ю 11 12 Зададим модель дР (1) в виде мографа, при этом роль букв играют первичные термы, слов — простые импликанты.
Задание булевой функции в виде мографа позволяет наряду с чисто логическими свойствами функции исследовать ее частотные и топологические свойства, что позволяет естественным образом рассматривать проектирование булеза графа как преобразование мографа в диаграмму Хассе, задающую частично у~орядочениое множество. Вершина о называехся разделяющей в структурном графе, ес- ли любой путь графа содержит ее. Подграф Г структурного графа называется гамаком, если лю- бой его (подграфа) путь содержит две разделяющиеся вершины, являющиеся соотвехственно минимальным и максимальным эле- ментами этого подграфа.
54.7. Синтез логических структур е типологические базисак 313 Замена минимального элемента гамака Г на максимальный н наоборот с одновременным изменением ориентации всех дуг гда противоположное называется операцией взятии двойственной содруктурьд от гамака Г. Синтезируем структурный граф последовательным построением путей, соответствующих рассматриваемым простым импликан'там. При этом построении выполнением операции взятии двойственной структуры будем сопоставлять общим частям в простых импликантах общие части в структурном графе.
Если такое сопо:ставление выполнить нельзя, так как в графе возникают лишние пути (т. е. пути, взвешенные конъюнкциями, не содержащимисн ;в заданной ДНФ булевой функции), то производим расщепление ;первичного герма, т. е. сопоставление первичному терму более :одной вершины в структурном графе. Естественно, что при одном расщеплении сложность схемы возрастает на единицу. Далее, очевидно, что сложность схемы не может быть меньше мощности :;носителя мографа, определяющего реализуемую булеву функцию, так как носитель состоит из существенных переменных. Будем рассматривать простые импликанты в порядке их напи,сания в ДНФ. В мографе они помечены соответствующими иден)тификаторами. Последовательное построение структурного графа изобразим на рис.
4.34 на котором числа 1-И обозначают присое:динение очередного пути, соответствующего следующей простой нмпликанте, идентификатор которой совпадает с номером, указанным под графом. 1) Задаем отношение упорядоченности в первой простой импликанте хехвхэ. и(х4) < о(х5) < о„. Здесь и ниже запись и(х; ') 'означает вершину диаграммы, взвешенную термам х,.'. 2) Присоединнем вторую простую импликанту. Чтобы не рас;,щеплять первичный терм хв в построенной на первом шаге диа'драмме, выполняем операцию взятин двойственной струкхуры от ;:Гамака Гд —— (Уг„с)г!), Уг) = (хе, хв), 11г! = ((х4, хв)). В результате получаем диаграмму Нг = (1'г, (12) Уг —— (хи х4, х5, хв, хдо) Уг = ((хв, х4), (х4, хэ), (хь, хд), (хд, хдо)), соответствующую первым двум простым импликантам.
3) Аналогично цри построении третьего пути, соответствую'йцего простой импликанте хдхгхзх4хв, выполняем операцию взя.'пия двойственной структуры от гамака Гг — — (Угд! 1)г,)! Уг, = К. "(Х4, Х9)> с)Г) = ((Х4! Х9)). Окончательно получаем диаграмму 03 — (13! с)3)! 13 — (х1! 32>хз>х4)х5>х9>х!0)) к)3 = 1(Х5> Х9), (Х5) Хд)) (Х9! Х4)! (Х1) Х10)! (х1) хз) ) (*3! х2) > (х2! х4) ) ' 314 Гл.4. Теория формалъмык грамматик и аетома>пое 34.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
