Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§5.10. Семантическое проектирование нейронных сетей 491

Таблица 5.61

Х1Х2Хзфтт Г4Г5Г6

1 2 4

3 3' = 0 • Фил

0 0

з" = о-^шт

1 1 0

Если первый способ основан на разложении исходного про

странства Р(Х) в виде

Р{Х) = Р{Ха) х Р{ХЬ)

и расширении одного подпространства с помощью заема перемен

ных в сопряженном ему подпространстве, то второй способ основан

на представлении Р(Х) в виде

Р(Х) С Р(Ха) X Р{Хь) х Р{Хпр)

и расширении подпространств Р{Ха) и Р{Хь) в случае повторной

декомпозиции переменными штриховки хшт G Р (Х ШТ), опреде

ленными отношением противоречивости Unp между подпростран

ствами Р(Ха) и Р(Хь). Реализуем найденные функции г), щ , <р2,

F в виде соответствующих нейронов гексагональной структуры.

Рассмотрим функцию

Г](х4, *5, Хб)^ = V (l, 3, 7).

Системы уравнений для определения синаптических весов и ква

зипорогов имеют соответственно вид

we = Ti, Pq = 0,

wb + Wb = Г2, w5 = Pi,

w4 + w5 -f w6 = T3; w4 — P2,

w4 + w6 = P3,

w4 + w5 = P4.

Решая уравнения, определяем синаптические веса и квазипороги

нейрона (табл. 5.62), реализующего т)(х4, xs, хв) (рис. 5.78, а); при

,.i ,.i ,.i , . i Д.»

I' Г Г Г I' I’ JT Г Т Г Г Г Т Ч '1

1 ,1 г ф ,1 .1 .1 .1 .1 .1 .r ig

1 X 1 1 X 1 X г

0 © 2 3 ® 5 © 7

Рис. 5.78

этом используем граф неравенства весов (рис. 5.78,6).

492

Гл. 5. Прикладная теория алгоритмов

Рассмотрим функцию

, ч _ f 1 на 0001, O il-, 101-, 111-,

1 Ь 12, хз, х4) - \ 0 на, 0000) 001-) 010_^ 100_^ 110

Системы уравнений, определяющие синаптические веса и квази

пороги, имеют соответственно вид

W4 = Ti,

Ро = 0,

w3 + w4 = Pi,

го3 = Pi,

w2 = Рз,

W2 + W4 = P4,

Wl = Ps,

Wi + W4 = Ps,

wx+w 2 = Pt,

Wi + W2 + W 4 = Pg.

Используя граф неравенства синаптических весов (рис. 5.79, а),

определяем веса и квазипороги (табл. 5.63). Соответствующий

нейрон имеет вид, представленный на рис. 5.79,5.

Таблица 5.62 Таблица 5.63

W2 + W3 = Т2,

W2 + W3 + W4 = Т3,

W i+ W 3 = Т4,

Wi -f W3 -f W4 = T5,

wi + w2 + w3 = Te,

wi + w2 -f w3 -f w4 = Tj;

2 3 1 1, 4,6

ИЦ

U12

«4

2 4

3, 4, 7, 8

T T

S x

X I

.'‘ ■■'. б -1. ..

I .,1

0 1 2 (| ) 0 5 б 0 ® 9

Рнс. 5.79

Рассмотрим функцию

U>i(z, Хо X t Ха ) — НЯ

<p2{xi, 12, хз, х4) - j о на о -, 1 -, 3", 7 - .

Системы уравнений, определяющие синаптические веса и квази

пороги, имеют вид

w2 = Ti,

w2 + w4 = Т2,

w2 + w3 + w4 = Т3,

wi = Т4,

wi + w4 = Т5,

wx + w3 = Тб,

W l+ W 3 + W4 = Tj,

Wi +w2 = T8,

Wi + w2 + w4 = T9;

PQ = 0,

W4 = Pi,

W3 = P2,

W3 + W4 = P3,

W2 + W3 = P4,

W l+ W 2 + W3 = Ps.

§5.10. Семантическое проектирование нейронных сетей 493

Граф неравенства синаптических весов является полным

(рис. 5.80, а), следовательно, веса попарно не равны друг другу.

Решая эти системы, получаем табл. 5.64. Нейрон, реализующий

функцию <pi(xi, Х2, хз. х4), имеет вид, представленный на

рис. 5.80,5.

Таблица 5.64

U)3

6 1, 3, 4, 7, 9, 10, 11

1 . I 1 . I 1 л 1 и 1

Ч>2

д а

W ?

д а

I I I I I I ^

Хх2

Т^з

Т?

г г т

r W

т а

цхд

ГЙ С

№

т*«

T*1

О (Г )2 ( | ) 0 5 б 0 8 0 1 0 (П)

Рис. 5.80

1 !■ 'I.'I ' ? t w

о 0 0 з

Рис. 5.81

Рассмотрим функцию

П<РиЧ>2, »?)|х = V"(l, 2, 4, 6).

Граф неравенства синаптических весов G„ep имеет вид

(рис. 5.81, а). Решая системы равенств

w7 = Ti, w6 + w7 = Pi,

we = T2, w s+w 7 = P2\

Ws = T3,

w5 +w6 = T4;

ws = w(ip3), we = w(y>4), w7 = w(Tfy),

494 Гл. 5. Прикладная теория алгоритмов

1о—о

№5

tue

ui7

1 2

1, 2

Таблица 5.65 и зная, что w5 = we, получаем

табл. 5.65, определяющую ней

ронную реализацию функции F

(рис. 5.81,6). Окончательно по

лучаем нейронную сеть, представленную на рис. 5.82.

§5.1 1. Оценка динамики логических структур

Для описания функционирования автомата во времени с по

мощью булевых функций положим, что все поступающие сигналы

могут изменяться во времени только дискретно. Выбрав доста

точно короткие интервалы времени, считаем, что сигнал изменя

ется только на границе временных интервалов и не изменяется

внутри самого интервала.

Длительность интервала выбираем, исходя из следующих со

ображений. Разложим временной бу

лев ряд х(£) в сумму эталонных функ

ций вида

x(t) = V а,а,(£).

Наиболее простые эталонные

функции Оо, a j, 02, ... приведены на

рис. 5.83, где То — время, в течение

которого анализируется работа авто

мата; при этом

«1

а 2

x(t)

i %

Y/Л 1

Ii i

Рис. 5.83

Ti = Го/2*', (5.15)

где Г, — период эталонной функции а,. Согласно (4.7) длитель

§5.11. Оценка динамики логических структур

495

ность минимального интервала

Т к = То/27+1,

где 7 — глубина временного квантования.

Для любого автомата существует минимальное время Тмин

между двумя соседними переходами. Для того чтобы описать ра

боту автомата во времени с достаточной степенью точности, необ

ходимо, чтобы выполнялось соотношение Тмин 3> Тк, или

7 [Iog2 (7о/7мин)]- (5.16)

Таким образом, для аналитического задания временных буле

вых рядов с данной степенью точности необходима глубина вре

менного квантирования 7 > [Iog2 (7о/ГМИи)]-

Минимальный временной интервал Тк будем называть вре

менным квантом. Тогда каждому кванту соответствует консти

туента единицы булевой временной функции ip(a0, ai, а2, ..., ау),

переменными которой являются эталонные функции а0, a j, а2, ...

..., ау. Следовательно, любой временной булев ряд с заданной сте

пенью точности можно задавать как булеву функцию от do, a i, ...

..., a7 и применять ее как обычную булеву функцию. Например,

временной булев ряд x(t) (см. рис. 5.83) можно представить в виде

х(t) = a0(ai V a2) V ao(aia2 V 0102).

Каждый реальный элемент, входящий в синтезируемую логи

ческую схему, обладает постоянной времени. Следовательно, в

практических логических схемах имеют место переходные про

цессы, которце необходимо учитывать. Рассмотрим применение

понятия производной для исследования переходных процессов в

схемах.

Временной производной dx/dt от булевой переменной x(t) на

зывается выражение

dx/dt = x (t)® x (t^ l), (5.17)

где x(t) — временная булева последовательность, принимающая

значения 0, 1 в моменты времени 0, 1,2 ... Для определенности

возьмем в (5.17) знак минус. Временная производная показывает

изменение сигнала во времени. Будем рассматривать периодиче

ские булевы ряды.

Проиллюстрируем понятие временной производной иа следующем примере.

Если переменная x(t) по времени t = 0, 1, 2, 3, 4, 5 имеет соответственно зна

чения x(t) = 0, 1, 0, 1, 1, 1, то временная производная изменяется как Эх/dt =

= 1, 1, 1, 1, 0, 0.

Рассмотрим логическую схему с двумя входами, которые одно

временно переключаются. Для определенности будем рассматри

вать переход (0, 0) -¥ (1, 1). Условие одновременного переключе

ния входных каналов xi и х2 является идеальным. На самом деле

496

Гл. 5. Прикладная теория алгоритмов

с вероятностью, близкой к 1, изменяется сначала один, а через

некоторое время другой вход. В зависимости от порядка их пе

реключения путь от (0, 0) к (1, 1) может пройти через (1, 0) или

через (0, 1). Рассмотрим два случая.

1. Функции /(0, 0) и /(1, 1) не равны. Выходные сигналы до

и после перехода различны. Тогда в промежуточных состояниях

может иметь место либо “старое” значение сигнала, либо “новое” .

Если в схеме отсутствуют всплески, то никаких ложных сигналов

не может быть.

2. Функции /(0, 0) и /(1, 1) равны. Выходные сигналы до и

после перехода одинаковы, т. е. переход на выходе “не чувству

ется”. Но если выходной сигнал во время промежуточных состо

яний отличается от /(0, 0) и /(1, 1), то во время переключения

может появиться ложный сигнал, и переход критический. Это

явление будем называть риском в логической схеме. Путь, по ко

торому сигнал перейдет из состояния (0, 0) в состояние (1, 1), за

висит от физических параметров сигналов и имеет статистический

характер.

Следуя Бохману, приведем необходимые и достаточные усло

вия критического перехода. Для того чтобы переход из состояния

(ст-!, а2) в состояние (ffi, cr2) (<7i, 02 = 0, 1) был критическим, не

обходимо и достаточно, чтобы:

а) °2) = fi? 1, ^2);

б) f{tr 1, а2) Ф / К , ° 2) или /(<7Ь <Т2) ф f{ai, <т2).

Эти условия легко сформулировать с помощью производных.

В случае критического перехода имеем:

а) одновременное переключение обоих входов, т. е.

9хг 0X2 _ ,

~дГ~дГ ~ ’

б) значения выходного сигнала до и после переходов одинако

вые, т. е.

»(* !,* ») ’

в) переключение только одного из входов ведет к переключению

выхода, т. е.

d f 8 f

dxi V дх2

Следовательно, ошибка выражается следующим образом:

dxl dxa ( d f d f\ W f

dt dt \9 xi 8x2) d(xi,x2)'

где Д/ — функция ошибки.

§5.11. Оценка динамики логических структур 497

В выражении (5.18) конъюнкция (dxi/dt)(dx2/dt) определяет

свойства сигнала; в дальнейшем будем называть ее сигнальной

частью. Конъюнкция (df/dxi\/df/dx2)d2f/d(xi,x2) определяет

свойства реализуемой функции; далее будем называть ее функ

циональной частью формулы, определяющей ошибку.

Одним из способов повышения производительности ЭВМ явля

ется увеличение рабочей частоты применяемых элементов. Сов

ременные молектронические элементы имеют рабочую частоту

тысячи мегагерц. При работе логических схем задержка в цепи

элементов становится сравнимой с периодом функционирования

схемы, что приводит к необходимости учитывать ложные сигналы,

определяемые выражением (5.18).

Ошибки не возникает, если А/ = 0; для этого необходимо

наложить ограничения на сигнальную или на функциональную

часть формулы.

Рассмотрим случай логических схем, у которых одновременно

переключаются три выходных канала. Согласно (5.18) ошибка

имеет место при переключении двух произвольных входов. Следо

вательно, в функции ошибок при переключении трех входов, ха,

хь, хс, содержатся следующие члены:

___

дха дхь ( d f d f \ d2f dxa dxc / d f d f \ d2f

dt dt \дх„ dxb) d(xa,xb)' dt dt \dxa dxc) d(xa,xc)'

d x b d x^ fd l d n W f

dt dt \c?X4 dxc) d(xb, xc) '

В формуле, определяющей условия возникновения ошибок при

переключении трех входов, содержится еще один член, который и

учитывает одновременное переключение трех входов:

___

dxa dxbdxc f d2f v d2f v a 2/ \ W f

dt dt dt \d(xa,x 4) d(xa,xc) d{xb, xc)J d(xa,xb,xc)'

Следовательно, функция ошибкй при переключении трех входов

имеет вид

а ^ Л 9 / у 9 П 9 4 ,v

dt dt \dxa dxь) d(xa,xb)

^dxadxcfdl yg/\_g7_y

dt dt \dxa dxcJ d{xa,xc)

dxbdxe ( d f d f\ W f

dt dt \dsf> dxc) d(xb,xc)

dxa dxbdxe f d2f d2f d2f \ W f

dt dt dt VdfaaiZb) d(xa,xc) d(xb,xc)J d(xa,xb,xc)'

(5.19)

498

Гл. 5. Прикладная теория алгоритмов

Обозначим функциональную часть функции ошибок, которая

входит в одну и ту же конъюнкцию с (dxai/dt)(dxa2/dt) ...

.. .(dxak/dt), как F(xai, ха2, ..., xak). Тогда (5.19) можно пере

писать в виде

Л , дха дхь . дха дхс

f ~ ~дГ~дГ (l“’ v ~дГ~дГ (la ’ Хс) v

V < ^ ^ F(x. x ) V ^ < ^ < b F (x XhX)

dt dt [ b, c) dt dt d t'y x<4xb>xc)-

Обобщая функцию ошибок на случай переключения п входов в

логической схеме, получаем

F ( l ai, Х„2, . . ., Ха„) =

= ( v

_____

V ^(1«1 , Х*2 I • • Ч *i„-l ) )

dnf

1 (5.20)

^(*ац ха2> • • ч ха„)

xh ) xt2, • • Ч ^ in -l = Х<4 I Хй21 ' • Ч З'Оп! *1 Ф *2) • ■ •) *П—2 ^ 1П—1)

и функция ошибок имеет вид

д/= v d- w a- w i t F ^ *'•>v ■ -

.........

I-»)- (521)

n , 12) • • • = A ll «2i • • -I On-

Из формулы (5.21) следует, что при увеличении числа перек

лючаемых входных каналов вероятность критического перехода

увеличивается. При переключении трех каналов на входе схемы

вероятность риска не меньше 75%. Функция ошибок Д/ носит

статистический характер.

Функция ошибок Д/ позволяет выяснить, возможна ли лож

ная информация, и в каких временных квантах при подаче на

входные каналы логической структуры заданной сигнальной ча

сти. Более сложной и важной задачей является синтез сигналь

ной части, гарантирующей 100-процентное выявление аномалий

динамического поведения логической структуры. Рассмотрим эту

задачу при реализации логической структуры в виде нейронной

сети из четырехсинаптических нейронов, используя при этом

теорию трасс.

В §2.10 было показано, что распределение трасс объективно

определяет качество переходного процесса, а именно при пере

ключении логической структуры по трассе может возникнуть лож

ная информация в выходном канале логической структуры. Дру

гими словами, ложная информация проявляется на выходном ка

нале выходного элемента логической структуры из-за неодновре

менного переключения входных каналов этого элемента.

§5.11. Оценка динамики логических структур

499

С учетом вероятной фильтрации ошибок невыходными эле

ментами логической структуры предложим модель ИС (рис. 5.84),

представляющую собой граф Gm = (Ум, Um ), гомеоморфный гра-

дс10

*20

*30

Х„с

— 1—

* 1

a S

x 3

* ЧЭ

т12|

-----

н .

T22_p-""-j

Л,

g-e

-----

1 •

2 S

я *

Т*»х22

й »

• • •

I S

>У1

^Ут

Рис. 5.84

ФУ Ghc (каждая вершина Guc взаимно однозначно соответствует

элементу логической структуры, дуга — соответствующему

каналу) и отличающийся от него наличием вершин (г = 1,

2, ..., кВх', &вх — входной коэффициент выходного элемента),

(vyi, иВых.эл.) € Um - Каждая вершина и7,- соответствует минималь

ной задержке, “приведенной” к входным каналам j -го выходного

элемента:

Т ^ т* ■ ^

min — Ч — 'maxi

где

rmin — минимальное время задержки прохождения сигнала

(переключения) от входного канала ИС до i-ro входного канала

j -то выходного элемента, определяемой соответствующей активи

руемой цепью;

Ттах

максимальное время задержки аналогичного харак-

тера, что и r^ in.

Значение r,j носит статистический характер.

Разность Д(г,

Tmax

— Тт;п называется

временным деба

лансом i-ro входного канала j-ro выходного элемента. Пара вход

ных векторов, Х а, Хь, соответствующих трассе Т(Ха, Хь) для

выходного элемента, может быть нереализуема, если цикломати-

ческое число графа G h c = (VhCi Uh с) больше нуля и найдется

элемент va с квых(ьа ) > 2 (квых — выходной коэффициент эле

мента va) и ортогональными функциями возбуждения <pai, ipaj

входных каналов смежных с ним элементов и,-, vy.

(иа, vij е Uhc, (va, V j) е Uhc, vai&4>aj = о.

500

Гл. 5. Прикладная теория алгоритмов

Для построения распределения трасс для выходного канала

выходного элемента логической структуры, реализующего булеву

функцию /(х 1, Х2, . . Хк„), необходимо рассмотреть

(*“ )+( V )+•••+(£:)=£( * г ) =2‘- - 1

1=2

переключений входных векторов X = (х*, Х2, . . ®*„), где JkBX —

/(*1, *з, ДГ4)

V r V - r V r V - ^

iV iV r r г i‘*«

О 1 2 3 4 5

М11 о| 11 о| 11 of\

Рис. 5.85

входной .коэффициент элемента, равный

количеству его входных каналов.

Рассмотрим это распределение для ней

рона (рис. 5.85), реализующего булеву

функцию

f{x 1, х2, х3, *4)|j= V(0, 1, 2, 12, 13).

Дерево распределения трасс (рис. 5.86)

имеет 11 поддеревьев (24 — 4 — 1 = 11),

каждое и которых соответствует фиксиро

ванному переключению входных каналов.

Рис.' 5.86

В силу (2.24) справедливо условие (5.22) (М.В. Горбатова) поро

ждения всех трасс при переключении входных каналов х01,

иа2, • • ч ••'а**

a v . . в * -1/

. fc

a(® 6j, ®Ьг) ^ ( x jj , x j2, Xj3) 9 (x jj, Xj2 , . . ., Xj(

(bi, b2) • • *i bfc-i) С (bi, 62, . • •, bjt),

(bi, b2, • • bfc) G Р(аь а2, ..., ajb),

Л)'

(5.22)