Устройство для исследования характеристик сетевых графов Советский патент 1987 года по МПК G06F15/173 

М.«)п|)(.ччмп1с о ппк иь я к иычш :;). 1Ы1ой технике 1 МО/КС г Г),ГП) ис1|(), П):я)11 111п ис- с. к дивания гггеных rpa(j)oi и в системах iiocTpoeiuin 10;Г() л.тя цифровых сгр(1Йстн, iipi;, lC7 ав.тениых с с тс в Ь1 ми гр:и)|ами.

UC.TI.K) 1 их рстения является расширение функциональных возможное гей устройства ля счег оиреле.тения ие,1ичннь максима.1Ь- HOio множества , покрывающих сете иой граф.

На чс|чежс иривелена cTpVKTVpiiaH I xcMa устройсIва.

VcipoiiciBo для исс.к лования харакге- рисщк i OTt Hijix rpatJHii; солержит матрицу I 4)орми|1овате.1е|1 lyr. )И11еры 2 (()ормир()ва- нич лу: . 1.и мен1ы 11 Л, .тсменты H. lll 1, ) -лК ментои .) а.и )жки. i-pyniiy регист- p.i ih MiiHia. rpviiiibi 7 9 . ieментов И, ) 10, ле|:|И1|)рат)р II. ieHe)a-io) 12 I ак roi .i.ix им11.11.с(1В. элемент 11 l. i, счетчик 11. .темен) 1 Г) ча;1е|1жки. нерв1 1Й мецт ИЛИ 1Г), иго(1()й :1. 1емент И, 1И 17. вто- loii ).1смеи1 И IS. счегчик И) pe-iy.ibTara. : лемснт 111- 20. вхол 21 (инуска устройства, информационные вхолы 22 xci-fnuici ва. вхо- Л1)| 2. 5 Ч таиовки нача.1ЬН1,1х хтломи сгрой- V I иа.

ai iiiina 1 фпрмирюиания с ночклцыо i })И1 1 c(K)ii 2 ф()рми) луч П|1елна:и1аче- :;:i Л.1Я молелирования сетеио1) i)a(})a.

1-). ы И . 5 (месгнг) с (.тементами 1|. 1И 1 и 4.|емен1 ами И liiDpoii ,i 8 П)с л на..нач1.Ч1ы ;1. 1Я не 1елачи солержимого pt44iv i ра (i ) 1 -:оименп()|Т eh rifuia чере ( вто- ioi i jieMcHT И. Ill 17 на нгоро) BXO.I cvM- 1ать|)а П.

л) К менть i (алержки но ( HiHa.iy с вы- ола .. leMtMii; И. Ill I BijipaGaTi.uiaioi 4e|)ei время lai : Г(ыхол1 1)й (.Ч1гна. 1. который HocT :ia; i на Ч1 ))авляюнип вхол :i. ieMeiiTa И первой , олноименного сто.тбца и ис- и().:||,чуе|-ся лля ;ани(.л1 солержимого сумма- гора Ht н |)е1Ис:|1 () олноименно|о cTo/ifnui

Регис1р1)1 () ipeлfla счачены л. я Х|1ансч1ия величины максимально 114) хмюжсства iiyreii, кото|)ые неоохо.тимы л. 1Я лосгн/кения вершины patjvri

лЛтеменгы И r(yiiiibi 9 Н) Ч1М11,1 л.тя нерсл;1чи со1е)жнмого регистра (i олноименного сго.тоца чере нервьн .темент И, 111 И) на Hepniiiii вхол ечммагора 10.

Глмма11)|1 |0 г)Г|сенечивает получение и.е.тичин макси .-1. п,1иго множества иугей. нокрываюших cei cBoii ip.aij). л.тя ;-й (;-.- - 1. М Be|).i paiji; ..

Ле:нн|(.)|)атор 1 I с )|цьк) генератора 12 HMHViisCDB -.темента И Л и счет- 1И|-.а М HMiiyi 1,1. . ,:. |.. вои Зужлает 1);| хол1п,1е 1ИИ1Н.1. 1 мво.1яег Л.1Я ограи- )oBaiiHoru I вычис.тить максимальное .4: С riio . кого()ые неоохолимы л. 1Я .U ; и ,-;;енчч BCfiHiUHbi графа.

. II j.:H ,i 1 TJ (але)жки матрицы (})орми:-ова1е.и й IKJ (во.чяют |1о.тучить розу. гонр. к) величину максима.Т1;Ного мно0

5

0

5

0

5

0

5

0

5

путей лля ;-и ве()ил1Н1)1 ог|)анжиро- ванн(Я() rpaij)a нри на:1ичии связей с /-ми вершинами ирелылуших ранюв гра({)а (/ ---- . п).

Bropoii :1.еменг И 18 н)елна (мачен д.тя (аниси ре ty.TM ирук.)Н1.ей величнны макси- ма. 1ьно() множества нутей. нокрываюших сс тевой граф, в счетчик 19 результата.

Э.темент ИН 20 н)ед11азначеи лля блоки- р( иостун.1ения имнульсов на вхо.т счетчика 14 имнульсов л. 1я появ.чения унрав- .тякмцего сшнала на выходе элемента 15,,,, (эдержки.

Г1ервый вход 21 ус ijioiici ва яв.тяется входом запуска усгрсик тва.

Ин(|)о)мационные вхолы 22 устройства нре.тназначеиы д.чя .(анесення информации о топологии молелируемого r|)a(}ia.

Вхол1.| 2 Л yc ianoiiKii мача.11.н1)1х с.тови11 уст|1ойсг а нрелназнач Ч1:,1 л.тя И ння регие1 1(1В (i в исхолнос состояние.

Устроив гво paooiaer с.К луклцим .

Иер1)Онача. 11)Но в матрицу 1 заносится ин(})ормация о ТО110.ТО1ИИ моле.тир емог о 11))а С1Л11 При гри1гер1 1 2 (юрмиро- л И yCT aii. iB. иваются в елиннчно1 c(j стоянш с HoMomi H) ин1)1)|)мационных вхо- лов 21 с I poiic гва. (л)()твс i с гвуклцие Г)И1- ге|)ы формирования лу1 он)еле.тяются ие)е- сечеиием сгроки с номе)ом. )авным HoMefu начально верншшл моле.1И пч мой луги. и сто.тГ)ца с номе(К)м, номеру конеч ной вер|нины. Иос. le занесения исхолно11 ииформации на вьгходах триггеров 2 //. со(л- ветствуюнигх нача.тьным верн1инам моле.1н- г|1а(|)а, усганав.тинаюгся нижие но 1ч.м1циа.ты, так как в олнонаиравленном i ia фн без никлов и нетсрь нача.тьные ) не солержат вхоляших ветве11 и три1геры jи)pмиp(Jвaния луг. находяни1еся в атсш сго.тбне, будут к нулевом с(Я тоянии. Также булут обну.тены регистры Н сдвига кроме тех. которые соответс iFiyioi нача.1ьным вер- И1инам. В perHCTpiii, coonлк тствукиние нача.тьным верн1инам, запоен 1ся код чис.та 1. который соответствует «весу - нути. исхотя И1ему из данной начальной вернппИ).

С. нояв.ц нием пускового сигнала иа не)- вом входе 21 ycTpoiicTBa импульсы с выхода генератора 12 имнулГ)С()н через элемент И 13 ноетунают на вход счетчика 14. что нриводит к поочередному возбужд(Л1ИН) В1)1ходньгх 1НИН ден1ифратора I 1. ( иояв.те ние.м унрав.тяюнтего сигна.1а на не|1вой шине де|ниф|)агора содержимое нервог о регист ра t)i сдви1а г)у|1ны peiiicTpoii че)е( nepitbiii :.темент И rperbeii груш1ы 9; и :.е- мент И, 111 17 ностунает на ,iii BXOI сумматора 10. Иоскольку в сете1 ьг графах отсутствуют Н(т.ти, го три1чер1)1 2 ма1рицы I формироват е.тей дуг находятся в и левом состоянии, HO:(T( На вьгходе :.темента ИЛИ 4i нервого сто,тГч1а oi су тчл вовать уиравлян)Н1ий cuiHa. i. Через время / на вы- холе :(.теме11та 1Г)|| залержки матрицы форMMpoiuiK . icii лу появшся iipaB.iHKJinMii CHI на.I, который 11одгве 1лит ну.ювоо (-остпя- ние тршгера 2i. формирователей луг матрицы и поступит на управ,тнюшнй вхол .ic- меита И . 5|v матрицы формирователей луг и вхол -. 1емецта lii (алсржки матрицы ({формирователей лу1. 1-лми тригтер 2i2 матрицы (})ормировател1 й луг иахолится в ели иичиом состоянии, то управляющий сигиа, появится на выхоле элемента ИЛИ 4:- rpuifibi элементов ИЛИ и соле)жимое регистра fi- слвига груииы регл1стров мере второй si.ie- меит И второй riiyniibi 8j и второй элемент ИЛИ 16 поступит на BTopoii вхол сумматора 10. Кроме того, управ.1яюци1й сигна.1 с выхола элемента ИЛИ -}. группы .темеиюв ИЛИ поступит на вхол .leMciira Г). чалержки элементов залержки, в ре1у.тьтате чего на его выхоле мере время т. иоявится у||рав.1яюп1.ий сигна., по которому солержи мое сумматора 10 (речу. суммирования первого и BToptH o регисгрои слвига груины регистров) анишется во BTopoii ремп тр 6 СЛВИ1а.

В результате суммировгшия во вто|1ом регистре булет нахолигься величина мак сима.тьного множества нутей. кот()(1ая неоп- хо.чнма л, 1Я лостижения нл иача.тьно вер 111ин1)1 второй вершины i ра({)а. Чере время {/.т.) на выхоле .теме1гга 15и ;(а.1ержки матрицы фор 1ирователей лу| появится ун- рав.тяюнтий си1На.1, Koiopbiii г)бну.1Я(п три: гер 2 . ((юрмирователей луг мат1)ицы и ио сгунает иа управ.чяющий вхол j.ieMCHia И iiii матрицы формировате.тей луг и вхол лс меита I5i., : алержки матрицы формирова теле1( . Процесс суммирования солержи MOio первого регистра слвига с солержимым лругих регистров (ири елииичиом состоянии соответствующего триггера) цро- то.тжается ло тех нор, пока не появится унрав.тяюнтий сигнал на выхоле элемента 1Г)| 1але)жки матриць ({юрмирователей . Иос.те этого вокбужлается вторая выхолная Н1ина лешифратори I 1 н нроисхолит суммирование соле)жимого HTcjporo регист)а (Ь с солержимым регистров елнига тех столбцов и )ых с1)ответствук)И1ие триггер, ((юр- мир(|1и) лу иахолятся i ели 1ичцом состоянии. Такая )с)целура С1 равелл 1ва .т.Я 1 релварите.т,И() отрапжировап К)го гра(})а. , кото)()() рсле. ио пеубы- I pacfja. tljxMiecc вычие. н лич 1 И) максимальиого иножества 1утей, 1окрь вак)щих сетевой laifi, продолжается ло тех пор, U)Ka ie появится 1равляю 1ий СИ нал иа ыхол1 элемеита 15,,,.,, .чалержки

МаТ|1И и) форМИрО аТСМеЙ лу . Ио ЭТОМЧ СЛ на.1 солерж 1М()е 6., слви| а )у ре И1 1 ров 1 ЛВИ| 1 череч iTopoii элеме И 18 ()(. в счетчик I J результата, кроме то(), .) сигиал И)С унает через элемен Ht. 2(1 на вход второго э,-|еме па И ,. что приволит к б.юкировке импульсов, НОС1 у 1аю1цнх с ецератора 12 тактов1,|х им- нчмьсов на вхол счетчика 14.

0

5

0

5

0

5

0

5

0

5

Формула инопретсния

Устройст 1() л.тя 1сслеловапия ха 1акте- ристик сетевых )О), солержа цее iX формировате.тей луг, элеме гго ИЛИ, 1ервую и вторую э.(Л И, ерв)1Й э.темеит И, 1И, цервый и второй э, мецт)1 It, енерат()р TaKTOBiiix имну.тьсов, счетчик, ле 1 и4|рат()р, кажлая ячейка матри- U формирователей соле| )жит и э.К меит И, триггера 1одк, 1ючен к ервому вхолу э,темента И, вход установки в . 1 является соответствующим 1холом и 1формациоцных входов устройства, этом выход э,теме1тта И ( -и ячейки /-1Ч) столбца матрицы формировате- .ей луг полключен к /-му входу /-го элемента

ИЛИ гру П Ы (, 2п (, 2п

(п число вер HI и и исс. о графа), выхо;1 кажлого элемента ИЛИ иол- ключе к ер)ому вхол од 1оимеин()го э,те- И 1 ерво11 -)уппы. и)1хол i-ro э,1емеита И ерв()й гру11 Ь олклк)чен к /-МУ входу )() э, И, 111, выхол генератора ()в И)лк.чк)че1 К с рвому вхолу iep- э. И, в 11хол которого 1олключен к холу счетчика. U4xo,i счетчика 1олк.) к холу (f)pa ора, огличан)- щеесч тем. что, с це.,К) |)ас1 иреиия (()уик- ., (о:(М()ж OCTeii стройства за счет (.е)ии ве, максима, М1 ожества 1утей, ()крываЮ цих ра(}), в им о э. ИН, суммато}). счетчик ре- ,)ита, второй э.емепт И,1И, третья а э,()в И. ре истров . элеме 1тов (алержки, в кажлую ячейку матри 1ы (j1op иpoвaтeлe i луг ввелен э,1е- залержки. 11ичем хол (аиуска генератора акТОВ,1Х ИМ 1уЛЬСОВ ЯВ,ЯеТСЯ ВХОЛОМ

ycTpoiicT ia, второй вхол 1ервого э.темента И подключеп к выходу э,темеита ИЕ, вход элемента ИН об) с ерв)м ВХОЛОМ второго э. И иолк.чючен к выхолу э. залержк яче11ки, .тежа- щей ia 1ересечеци 1 «-го сто.тбца и ;(-й строки ) (})орм 1ровате,ей луг, 1 ервьп1 выхол ({)ратора нолк.иоче к 1ервому Bxo.iy перво () э. И третьей rpyiuibi, к второму вхолу элемента И 1ервой яче11ки ie)iO() сто, матри 1Ь формирователей луг. )U)ii вхол ле 1 ифрат()ра гюдк.тюче) к вхолу э.темеита задержки первой ячейк 1ерво о сто. матриць (формирователе , кажлый /г-й выхо;1 ле пифратора (1 ле

/г 2, 3 п) иолключеи к второму вхолу

э,емента И /-Й ячейки нерво Ч) сто. 1бца матрицы формирователей луг и входу элемента задержки этой же ячейки иервого етолб та матрицы формирователей ду, элеме - та задержки каждой яче1жи формирователей луг олключе1 к холу ки в «О этой же ячейки матрицы ({формировате.тей лу, выхол э.темента залерж- ки (-Й ячейки, кроме п-н, каждой стрежи мат- (}1ормировате, 1ей дуг подк.тючен к второму входу элемеита И и э. задержки (/-|-1)-й ячейки этой же строки

матрицы формирователей дуг, первый вход каждого /;-го элеме)1та И третьей г-руппы подк, 1ючен к выходу :(демента задержки ячейки, лежащей на пересечении /г-й строки и ( - 1)-го столбца матрицы формирователей дуг, выход каждого элемента ИЛИ группы подключен к входу одноименного элемента : адержки грунны, выход которого подключен к первому входу oднoимeннoг(J элемента И второй группы, вторые входы всех элементов И второй групны объединены и подключены к выходу сумматора, выход каждого /-ГО элемента И второй группы под- к;1ючен к ннформацпонному входу одноименного регистра сдвига г руппы, вход установки нача. 1Ы1ых ус.ювий которого является соответствующим входом группы, входом установки начальных условий устройства, выход каждого /-ГО регистра сдвига группы подключен к второму входу одноименного эле- мента И первой группы и второму входу одноименного элемента И третьей группы, выход каждого /-го элемента И третьей группы подключен к /-му входу второго элемента ИЛИ, выход первого элемента ИЛИ подключен к первому входу сумматора, выход вто- рого элемента ИЛИ подключен к второму входу сумматора, выход п-го элемента И второй группы подключен к второму входу второго элемента И, выход которого подключен к информа1;ионному входу счетчика ре- :1ультата.

Изобретение относится к вычислительной технике и может быть использовано при исследовании характеристик сетевых графов и построении проверяющих тестов для цифровых устройств. Устройство позволяет определять величину максима. и.ного множества путей, покрывающих сетевой граф. Такая задача возникает, например, при исследова- пии характеристик сетевых графов или оценке величины таблицы неисправностей при построении диагностических тестов для цифровых устройств, представленных моделью сетевого графа. Поско.льку задачей диагностических тестон является локализация каждой неисправности, то естественно стрем- .1ение строить диагностические тесты на основе полной таблицы неисправностей, однако ее размеры стремительно возрастают с ростом числа дуг и вершин сетевого графа. Поэтому для выбора стратегии построения диагностически.х тестов целесообразно оцепить число строк таблицы неисправностей. Нсли величина лежит в заданных пределах, то диагностические тесты можно строить на основе полной таб,1ицы неисправностей, в противном случае выбирается другая стратегия построения диагностических тестов. Целью изобретения является рас1нире- ние функциональных возможностей устройства за счет определения величины максимального множества путей, покр,1ваю1цих |раф. Устройство содержит матрицу ггХ формирователей дуг, группу элементов ИЛИ, первую и вторую группы элементов И, первый элемент ИЛИ, первый и второй элементы И, генератор тактовых импульсов, счетчик, де1пифратор. Каждая ячейка матрицы формирователей дуг содержит трип ер и элемент И. В устройство введены элемент НЕ, сумматор, счетчик результата, второй элемент ИЛИ, третья группа элемептов И, группа регистров сдвига, группа элементов задержки. В каждую ячейку матрицы формирователей дуг введен элемент задержки. Введение дополнительных элементов в устройство позволяет получить качественпо новое свойство - определять максимальное множество путей, 1К)крываюп1их сетевой граф. 1 ил. i (Л со го Ci о ю

Составитель Т. Сапунова

Редактор С. ПекарьТехред И. ВересКорректор Н. Король

Заказ 1845/49Тираж 673Подписное

Е ИИИПИ Государстнонного комитета ((.(Р по делам изобретений и открытий

I 130. i,S, Москва. Ж 35, Раушская иаб., д. 4/5 (1р)1г(водствсннг)ч1().чиграфическ()е предприятие, г. Ужгород, ул. Проектная. 4