Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 87
Текст из файла (страница 87)
5.77,6) сх, = ((О, 1, 2, 4, 7), (У,,ц, Х)), абзац = (СО, 4) (2з 4)э (1> 7) Э. Двоичный логарифм хроматического числа графа зацепления определяет минимальное значение размерности вектора штрихов- ки Х, значение которого для кь равно 2: !Хвт! = [1обз Ь(бзац(к1))] = [1одт 3) = 2, а для кз — 1. Выбираем второе покрытие. Минимальная раскраска вершин графа сз „(кз) имеет вид а = 10, 2, 7), 6 = 11, 4). Кодируя краски а — О, 5 — 1, получаем значение вектора штри- ховки Х , задаваемого функцией (1 на 1,4, 1' -(х»хв) зс),0 о'2 7.
Векторы О, 1, 3 пространства Р(хь, хз, хз), определяющие зацеп- ления векторов О, 1, 2, 4, 7 пространства Р(х4, хб, хв), штри- хуются согласно раскраске сз„ц(кз), как показано а табл. 5.60, табл. 5.61). 15.10. Семантическое ароектирование нейронных сетей 491 Если первый способ основан на разложении исходного пространства Р(Х) в виде Р(Х) = Р(Х,) х Р(Хь) и расширении одного надпространства с помощью заема переменных в сопряженном ему подпространстве, то второй способ основан на представлении Р(Х) в виде Р(Х) С Р(Ха) х Р(Хь) 14 Р(Хар) и расширении надпространств Р(Х,) и Р(Хь) в случае повторной декомпозиции переменными штриховки х 6 Р(Х ), определенными отношением противоречивости Ц,р между подпространствами Р(Х,) и Р(Хь).
Реализуем найденные функции 41, у1, сот, Р в виде соответствующих нейронов гексагональной структуры. Рассмотрим функцию 0(х4, хб, хб) ~ = У(1, 3, 7). Системы уравнений для определения синаптических весов и квазипорогов имеют соответственно вид зов = 7'11 Ро = О, зоб+ зов = 77 зоб = Рь, о4+ 1об+ зов —— лз, 'зо4 —— Рз, за4 + сов Рз~ 1е4 + зоь Р4. Решая уравнения, определяем синаптические веса и квазипороги нейрона (табл.
5.62), реализующего 41(х4, хб, хв) (рис. 5,78, а); при ч Юз зтом используем граф неравенства весов (рис. 5.78, 6). 492 6012СзК44)5 5 Отз((»)»ов б Рис. 5.30 Ег Хг хг и>(ч» Хг Хг Х4 Х4 Х4 О 1 2(3 ®5 6(,7.»(,В.»О б Рцс. 5.79 (4>г» и>(>33 о(1)ф 3 б Рис. 5.51 2-,4-,3',5 —,6 —, синаптические веса и квази- Ро = юа = юз = таз + Юг+ ю1 + О, Р„ Рг, и14 РЗ > юз — Р4 > и»2+ вз — Р5. Гл.5. Прикла>гнал творил алеориогмов Рассмотрим функпию ( 1 на 0001, 011-, 101-, 111-, 0 на' 0000, 001-, 010-, 100-, 110. Системы уравнений, определяющие синаптические веса и квази- пороги, имеют соответственно вид Ю4 = Т1 Ро=О, Ю2 + ЮЗ = Т2> юз+ Ю4 — Р1, ю2 + и13 + ю4 = ТЗ> тоз = Рю то»+ вз =Та, юг = Рз Ю1+ЮЗ+Ю4=Т5, юг+ ю4 Р4> Ю1+Ю2+ЮЗ Тб> Ю1 Р5, Ю1 + юг+ тоз + ю4 = Тт, в1 + Ю4 —— Ре, Ю1+ юг — — Рт, Ю1+ Ю2+ Ю4 = Ра.
Исполъзуя граф неравенства синаптических весов (рис. 5.79,а), определяем веса и квазипороги (табл. 5.63), Соответствующий нейрон имеет вид, представленный на рис. 5.79, б. Таблица 5.62 Таблица 5.63 Рассмотрим функцию 11 на (р2(х»> хз, хз, х4) = '(О на Системы уравнений, определяющие пороги, имеют вид Ю2 = Т1> Ю2+Ю4 Т2 Ю2+ юз+ ю4 — — Тю ю» =Т4, ю» + Ю4 = Тб, Ю1 + Юз — — Тб, ю1 + юз + го4 — — Тт, ю»+ Ю2 — — Та, ю»+ ют+ Ю4 — — ТЫ 15.10. Семантическое ороекти ование неброннагх сеа>ео 493 Граф неравенства синаптических весов является полным рис. 5.80, а), следовательно, веса попарно не равны друг другу. ешая эти системы, получаем табл.
5.64. Нейрон, реализующий функпию >рг(х», хг, хз, х4), имеет вид, представленный на рис. 5.80, 6. Таблица 5.64 Хг хг Х2 хг ХЗ Хг Х4 Х3 Х4 Х4 х, Х4 Рассмотрим функцию Р(р„ р„ 9)~ = ~(1, 2, 4, 6). Н Граф неравенства синаптических весов С„ар имеет вид (рис. 5.81, а). Решая системы равенств ют = Тм Юб+Ю7=Р1> Юб Тг> 305 + Ю7 Р2, ю5 = Тз> ЮБ + Юб = Т4( Ю5 и>(>рз) > юе ю(>>34) > ют — и»(т»3) > Гл. 5. )Уриклоднол творил алгоритмов 494 55Л1. Оценка динамики логингских структур 495 Рнс.
5.52 3 5.11. Оценка динамики логических структур Для описания функционирования автомата во времени с помощью булевых функций положим, что все поступающие сигналы могут изменяться во времени только дискретно. Выбрав достаточно короткие интервалы времени, считаем, что сигнал изменяется только на границе временных интервалов и не изменяется внутри самого интерввла. Длительность интервала выбираем, исходя из следующих соображений.
Разложим временной булев ряд х(1) в сумму эталонных функаа ций вида х(1) = Ч сага;(1). а» Наиболее простые эталонные функции ао, а1, а2, ... приведены на рис. 5.83, где То — время, в течение которого анализируется работа автот, мата; при этом аг хоз О Рнс. 5ЯЗ Т' = То(2, (5 15) где Т; — период эталонной функции аг. Согласно (4.7) длитель- Табяняа 5.бб и зная, что шв — — вв, получаем табл, 5.65, определяющую нейронную реализацию функции Г (рис. 5.81, б).
Окончательно получаем нейронную сеть, представленную на рис. 5.82. ность минимального интервала Ть = То/2"+ где 7 — глубина временного квантования. Для любого автомата существует минимальное время Т„„„ между двумя соседними переходами. Для того чтобы описать работу автомата во времени с достаточной степенью точности, необходимо, чтобы выполнялось соотношение Т„„„'.2» Ть, или 7 ~ [)обз (2о/Тмня)) (5.16) Таким образом, для аналитического задания временных булевых рядов с данной степенью точности необходима глубина временного квантирования у з [!опз (То/Т, )). Минимальный временной интервал Ть будем называть временным квантом.
Тогда каждому кванту соответствует конституента единицы булевой временной функции ~р(ао, а1, аз, ..., ач), переменными которой являются эталонные функции ао, а1, аэ, ... ..., а . Следовательно, любой временной булев ряд с заданной степейью точности можно задавать как булеву функцию от ао, а1, ... ..., ач и применять ее как обычную булеву функцию. Например, временной булев ряд х(1) (см. рис. 5.83) можно представить в виде х(1) = ао(а1 ч аз) ч ао(атаэ ч а1аз).
Каждый реальный элемент, входящий в синтезируемую логическую схему, обладает постоянной времени. Следовательно, в практических логических схемах имеют место переходные процессы, которые необходимо учитывать. Рассмотрим применение понятия производной для исследования переходных процессов в схемах. Временной производной дх/д1 от булевой переменной х(1) называется выражение дх(д1 = х(1) Е х(1 ~ 1), (5.17) где х(1) — временная булева последовательность, принимающая значения О, 1 в моменты времени О, 1, 2 ...
Для определенности возьмем в (5.17) знак минус. Временная производная показывает изменение сигнала во времени. Будем рассматривать периодические булевы ряды. Пронлаюстрнрусм игнатие временной нронавоаной на саеауюшем гримера. Если асременная х(1) ио враманн 1 м О, 1, 2, 3, 4, 5 имеет соохвсгствешю анааеннн х(1) = О, 1, О, 1, 1, 1, то временная нрснавоанаянамеиясгся ваа дх/д1 = = 1, 1, 1, 1, О, О. Рассмотрим логическую схему с двумя входами, которые одновременно переключаются. Для определенности будем рассматривать переход (О, О) -+ (1, 1). Условие одновременного переключения входных каналов х1 и хэ является идеальным. На самом деле $5,11, Оценка динамики ловическив сн> ук>оур 497 Гл.5. Лрикладнол а>сорил олго ио>мое 496 с вероятностью, близкой к 1, изменяется сначала один, а через некоторое время другой вход. В зависимости от порядка их переключения путь от (О, 0) к (1, 1) может пройти через (1, 0) или через (О, 1).
Рассмотрим два случая. 1. Функции У(0, 0) и У(1, 1) не равны. Выходные сигналы до и после перехода различны. Тогда в промежуточных состояниях может иметь место либо "старое" значение сигнала, либо "новое". Если в схеме отсутствуют всплески, то никаких ложных сигналов не может быть. 2. Функции У(0, 0) и У(1, 1) равны. Выходные сигналы до и после пеуехода одинаковы, т. е. переход на выходе "пе чувствуется".
Но если выходной сигнал во время промежуточных состояний отличается от У(0, 0) и У(1, 1), то во время переключения может появиться ложный сигнал, и переход критический. Зто явление будем называть риском в логической схеме. Путь, по которому сигнал перейдет из состояния (О, 0) в состояние (1, 1), зависит от физических параметров сигналов и имеет статистический характер. Следуя Бохману, приведем необходимые и достаточные условия критического перехода. Для того чтобы переход из состояния (аь аг) в состояние (сть стг) (оь аг —— О, 1) был критическим, необходимо и достаточно, чтобы: а) У(ть аз) =У(оь т,); 6) У(~ь аг) Ф У(аытг) или У(аь> а'г) Ф У(аь> стг) Зги условия легко сформулировать с помощью производных.
В случае критического перехода имеем: а) одновременное переключение обоих входов, т. е. дхь дхг — — =1 дь дь' 6) значения выходного сигнала до и после переходов одинаковые, т. е. дг у =0; д(хь хг) в) переключение только одного иэ входов ведет к переключению выхода, т. е. дУ дУ вЂ” Ч вЂ” = 1. дх> дхг Следовательно, ошибка выражается следующим образом: дх дх /дУ дУ~ дгУ сьУ = — — ~ — '>т — /, (5.18) дЬ дь ~дх~ дхг/ д(хьхг)' где ЬУ вЂ” функяил ошибки. В выражении (5.18) конъюнкция (дхь(дь)(дхг(дь) определяет свойства сигнала; в дальнейшем будем называть ее сигнальной частью. Конъюнкция (дУ/дхь 'и' дУ/дхг) дгУ(д(хь хг) определяет свойства реализуемой функции; далее будем называть ее функииональноб частью формулы, определяющей ошибку.
Одним из способов повышения производительности ЗВМ является увеличение рабочей частоты применяемых элементов. Современные молектронические элементы имеют рабочую частоту тысячи мегагерц. При работе логических схем задержка в цепи элементов становится сравнимой с периодом функционирования схемы, что приводит к необходимости учитывать ложные сигналы, определяемые выражением (5.18). Ошибки не возникает, если сьУ = 0; для этого необходимо наложить ограничения на сигнальную или на функциональную часть формулы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
