Устройство для исследования характеристик сетевых графов

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 12 4 С 06 Г 15/20 ОПИСАН К АВТОРСКОМ Я Б ЕТ ЛЬСТ СВИД В ОСУДАРСТВЕННЫИ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(54) УСТРОЙСТВО ДЛЯ ИСС;1.,.СОВАНИЯ ХАРАКТЕРИСТИК СЕТЕВЫХ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано при исследовании характеристик сетевых графов и построении проверякнцих тестов для цифровых устройств. Устройство позволяет определять величину максимального множества путей, покрываннцих сетевой граф. Такая задача возникает, например, при исследовании харзктеристик сетевых графов или оценке величины таблицы неисправностей при построении диагностических тестов для цифровых устройств, представленных моделью сетевого графя. 1 икольку задачей диагностических естов является локализация каждой неисправности, то естсственно стремление строить диагностические тесты на основе полой таблицы неисправностей, однако ее размеры стремительно возрдстзют с ростом цислд дуг и вершин сетевого графа.Ноэтому для ивборз стратегии построения диагностических тсстов целесообразно оценить число строк тдблицы нисправностей.Если эта велицинз лежит в заданных пределах, то диагностические тесты можно строить на основе полной таблицы неисправностй, в противном случае выбирается другая стратсгия построения диагностических тестов 11 лыс изобретения является расширение функциональных возможностей устройства зд счет определения величины максимального множествд путей, покрывающих граф. Устройство содержит матрицу цХп формирователей дуг, группу элементов ИЛИ, первун и вторую группы элементов И, первый элмент ИЛИ, первый и второй элементы И, генератор тактовых импульсов, счет- ф чик, дешифратор. Каждая ячепка матрицы форимнронгнтлелей еее еооернене ернг еер н эне. (/) мент И. В устройство введены элемент НЕ, сумматор, счетчик результата, второй эле- Ъю мент ИЛИ, третья группа элементов И, группа регистров сдвига, группа элементов задержки. В каждую ячейку матрицы формирователей дуг введен элемент задержки.Введение дополнительных элементов в устройство позволяет полуеить качественно новое свойство - определять мдксимальное М множество путей, покрывакнцих сетевой граф. 1 ил. ( )11 с об р ( Гн и с и и о 1я к ь ч и с.и 1, 1 ь н о и 1( хни 1 1 Ок Г б), 1, иног ь ОВ 1 нц И 1)и и- с,илоднии еых грзфо и сисггчах Пц.Грцс(И 1, ц 5;1.1 ИИфрОВЫХ С ГРОИСТВ. пр.,с 1 3, иН 31 ых стВь ми ( рс(31))Елн), И)б )сИиси,и С р 3 спир(ние (1)х нкиицнд. ьных Водмож ес гси у л ройстд Д Д С Ч (. Г О П П Л Е,Е Н И Я Е,И Ч И и Ы Ч Д К ( И Ч с 1,ЬНОО ЧСОКЕСТВ 3 П)1 й, НКРЫВ;3 НИИХ ест 13 ЦИ 1 Раф.1 1 1(+ сП р и5 Е, 3Н д 1 )К Г у р Н д 51 ( Х ( Ч5" РОИС В;3ХСр(и 1 ВО Л.151 ИС(. И,Ос 1 НИя ХарКГЕ- ри Гик . ы хРефо .ерски Г м Гри(уорхРоес;3 т,1(. Й 31, ,)и 1 п 2 форчиро 3- и 1;у, .и х(Г и 1, 11:1, )Гхенть 11,111 1,1)1х111(, с;(.,Рк ки, ГРУ 11 х РГисГ - Р,;51311, руп;ы 7 Г) )Ге ченго 11,. с ); , и 13 фр:Ор. Ир;(ор 12 1;3 к:),3,х ихих,ьсо, злсн 1, (т - Нк 11, сл хе ны 1 с;.и ркки. и рыи ас- чн 11,1 1, гои)и злс ч ИГ 11,1 И 17, торопи ч н 1 15(,ч чик .) Ресу,ьгег .х( н11. 2), схо 2с;их ск 1 х стройлВ;с, 3 11) о Р 1, 1 о 1 1ы е 1 5 х о , 1 1с 1 цЙ (1 53 , 1 с х ( ) - , 11 5 ,311 К И НД 31,ЬП 1Ч сцСИИ 1 С Рои -1 1.Ч 13 ПИфОРЧИРС;Н 3 11 ПОЧОПГЬН) РигРо 2 Рорхирос;ни .3 пр,н;и;и,1 П(ифр,1)р ) с 3 омцИЬН ГЕНр;5 Ор(3 2ко(ых ихИх 1,(ц 51131; 11 1:1 и счл.,111 с1 ..сс. 31с о 5 б ч ж . 311 Ы Х.П ЫС Пи 11,1Сц, 1 И Г,3,Я Ц ГРДНРОВД 3 цХР)3 ВЬ ЧИСЛИТЬ Мс 3 К(ИМ 1 ЬНОЕс Ге .1 и, 3 огор,Г неохо,их(ь Лл1 1( 1151Ы 1)( )ы 1; си р кки ч;рины формиц(, (1,3 си (5 ог 51 н)т по, ить и зч;ь.,+,(сВ; Иуеи лля е-и ер(инны огрднжиро 1 ннооРд(1)с 3 ИРи ндсичии саянаЙ с (-чи 5 Е ) П 1 И Н с Ч И Н Р, 3 3,3 Х И Е 3 Х Р 3 Н Г О В 1 Р Д ( с 1( - ==1, н).5 Б (ирои 3,чен г 11 15 прел(д сндч 31 ЛГ 535 циси р(у,ь Иру оней величины максильни о ч носкетнз иу Г(Й, пок ры 3 н)пи х стеой граф, В с и Гчик ) Реультдтз.:-ЭГх(ент )1 Е. 20 преснад(зчи лля блоки Оронни н(ктчпсен и 51 и миС ьсо и 1 В хо. (чет.чика 43 п ус 3 сос ЛГ 5 Нос(ле 33 уп р;3- 15 К)и(.Го СИ Г Над 1 НзХОЛЕ ВЛРМГТс), салерж ки.11 ср(ЫИ 1(ХОЛ 21 чГс)о 311)с 1 ЯВ 15 иТС 51холом запуск устройГ г 53.15 Ин)Рм;1 ионны( Вхо.ь 22 хстн)Йстапре.нз сн;и нь л,5 ;и(ччия инфцрч;3 ии о тцнц 1 Ии ЧЦЛЕЛИРУ( МОГОРзф;3.В ХО;1 2 у 1 (1 иц 5 К И О С (с ПН Ь Х,1 цИРци( Г 13 13 Р(,н си 3 и п 1 .1,1 при В 1( ниР ИСРОВ ) И Хц.ПО(.ООНЬ20 У( гр 3(с пи р;бос с.и.ун)иим обрд соч() 1) 1 (31, 3 11 3) 1 5 М д 1) 1 13. 5 с1) С1 Гя31(форх(;иия о топил ии чол 1(р емиР;фд с( и ри згцчРи Г(ры 2 форчиро 5 Ч И 511ГП; , ПВОТ 5 В (ГИНИП(Н ( О 1 ни( с почпьн инфоч;Ииопных Вхц.о с срцИ ГЕС(. (.(ИГС ГВОпИ 1 ри(.(. Ио 5, и нссл пуск)ого си Идлд н; Иер.Вцч Вхол 2 устройст 53 импульсы с Выхода 45 ндОрз ичпсльсоес 1 То"имент И 15 полуп(н) нд хол с итчикдЕ.что принолит к пооере,нох( Вобхжл нин 13 ЬХО,31 Ы Х Н 1 И Н,3 ПИЧРДТОР 3. (. ПЦ 51, И нисм хпрдлян)пег сигна, и; Иере)и пине ,3(н(р;3 ордо.и р+ имк перого р и т 50 Р 3 )1 слВи 3 1 Рчпнь Р(1 истРц Р(. с и(Ри151 мент 11 рьЙ Групп 3 ) и перыЙ ,1- ч(нг 11,1 1; итупа Нд (и рый Вхосумм;(торе) О 1 Скольку В стеьх гр(3 фесх отсх геун)т и 1.и, (о Риг( Гры 2 ч;риныОМИРОс Т.1 и .33 13(ХОЛЯТСЯ В Н) ГЧсц 1 55 сгоянии, ноаОчу нд ь 1)ч);и ),ихе(гд1,"1)1 4, и рег) с 1) бид бу лс г о у г(ВВ Гь упрдвлянниий игнал (Рес Время Е пз Вы.хц.н ,еч(Гд 51 с;1,ир,+,ки чдтриы фор чировдт л( й луг (н)яви(ся )прав.)ян)ций С И 1 Н ( 3, 1, К) Т) Р Ы И П О, 1 Г В ( Р Л И Т 1 Ч,и Г) ( ( (К Т) 51- ни три(рз 23( )О)х(3(ров)3) е,33 лчГ мтр 1. 1 ц и п(ступи( и;3 упр;)в )яннпий вхол э,)с. чецтз И:53, х)дгр)311,3 форчировзтелей лу и в(ол элечнтз) лржки чатри 1 ы форчириятелей, х1.с.(и три гер 2, ) матрицы форх(3(ро 3) Гий Луг и)хоЛится в (.1 И Н И Ч Н 0 3 СОСТ О 53 Н И 3, ТО Ч П Р 3 13 Л 51 Ю П 1 И И С 3(13 Д,появится цд выхо.1 е элем( птд ИЛИ 4 грх ппы элечецтов ИЛИ и одер кичн р(гистрд 6 СЛВИГЗ Груииц рЕГИСтров Чр 3 ВтОрой э,цчент И второй группы )5 и второй элемент ИЛИ 16 поступит нд второй Вхол суччд(О- ра 10. Кроме того, упр)в 35 кщ)(й си цдс Выхода элех(снтз И,1 И 1 группы э,)еч( н(в И,1 И п(к"тупит нд Вхол ,3 чнг;3 6 здлер+,ки гру пи ь элем( Н 1 ОВ з;,(срж ки, н рзул в;)т( ч,ГО 13(3 (.ГО вь(хо.1 чР 3 ВР(.ч 53 Г( (ОЯВитс 53 ИРЗВС(ЯН)31 ИИ ИНЛ, 3 О К(ТОРОМ( С)ЛР,+(И ч(е счх(мтор 3( ре )х,)ьгт сх ччиров;3313(я 13 рцого и второго ре 3( гров сл)и д груп(ц р гис(ров) япиИется и 1)торои р(3 ис(р , С Л 3 3(315 р.)усьт 1 сх ччирвдния во цтороч р(Г(стрГ)члт н(ходи ь 5 и)Г и чин(3 х( к сичдльв)го чножстя:(утей, которая ио 6- ХО.1 ИЧД Л,3 Я ЛОСТ)К 31351 ИЗ Н;)ЧЛЬ)3 ОИ ВР и и н ь( Второй Ве)рп и 13 ц рдфз. 1 рс 3 вр3 3=.-т ) 1;1 Вьхоле эс(ех(тд о .3;1.1 р)кк матрицы форх)(ро 3;)те 3 й лхг появится р(333535(н 3(3 й сигнал, кп орый Обну.)(и т (ри 3 (р 2 ( (1)ор 3 и ров зт(.х 3)3 .(хчдтри 31 ь( и НО с х п(3 1(зИРЗ 3)Г 5(н)п 113 и В ХО;1 э, 3."(3(и Г(3 И,53 )дгри 1 ц форчирВате.ий лу и ВХО.1 э.и х 33(д 6( зал ржки матрицы форчииид т(,35 й лу ро 1 сс (х х)х(3(ровд)33(я солр ки х)О 3 ирворг)3 грд слвига с содержимцч .(ругих р (стро(3 сл(33;3 (при л)3333)33(ОХ Ос) Оя 31333 соог(и Т(у Ош О ) р)(ггер 3 цро.1 О,)ж(3 т 53 л Гех пор, пока не появит я управ (янщий си ндл цд выходэлечентд 63 д,и р кки матрицы форчировзтелеи лхО(ГГ)с этОГГ) вОГ) )ж,1(3. тся 3 тор(1 я Вцх)Л 3я (пина леи)ифрдгор;3и происходит суччиро(я)33(с солер кичого вгор(ио регистрз 6 ( сол ржичцч р(гистров сдвига тех столбцовР в ко)орых нГ(иствую(пигриггсры форчиродния л)33;)хол(т(я н л)(ц)(чв)х) со(нянин рдкзя 3(ро)1,1 ур)3 пр;)неллина л,)я пр.Идритльно Отрднжирванв)го гр;фд, приНиц котониц рзспрл 5(ь( НО н(6 ь(- и (3 Н ) Н 1 (3 Р (3 133 3Р ( ф (3Р О 3 1(.). С ВЫ Ч И С СЦ 13 53 вличпны максималы(ого множествз путей, пкрыв;(нп(их сп вой 3 рзф, проло,(,кз(тся ло тх пор, пок;3 нпоявится упрзвлян)п(ии си 1(д. 1(а Выход эси)х(нт 3), ззлерж ни чтриц форчироят,)ей лу 11 о эгох) сиг;3,)х со.1 рж) чор(. Гис 1 р(3 6., слв)31;3рх пп) р ис грв слви 3,3 )3 р 3 Второи элемн 3 И8 НО 3) ит В (ч(тчик ,3 р(. х,(ьтдт;,ГОО, ЧПРДВ,153 ОПИй (ИГ 1)ЗС ПО" ЧП 1 Т ЧЕЗЕХ) э,)ехн Н. 20 нз вход вОрого элмензз И 1,5, цто приво.1 ит к 6 локировке импульсов, в)с)упзн)ших с 33(ердтор(3 12 тч)кгоь(х 3(х(- пульсов на ихо,1 счтчикз 4.29)2 5 1 О 15 20 25 30 35 40 45 50 55 4ФСР.(У ( .О 6)ГН(СТРОИСТВО,15151 ИССГ).(;1 ОВ(13 И 5 Х 3 Р(3 КТ(- ристик сп вьх гр;)фов, со:1. ржзи ч)трицх ц )(форч проя Гли луг, группу элч( н гоц ИЛИ, первун) и вгорую группы э.Х(3(ГО)11, првцй элч(нт И,1 И, первый и второи элеченпя И, нердтор тактовых ичпу,ьсов, с 3 (и к, л)п)ифрзтор, к(1 жлзя яч(икд х 13 трииы форчировзтл( й лчг солржит три 1 гер и э,)ечнт И, вых)л триггера полклкчец к первму входу элемента И, вхол устдновки и:Тр)(ггГ рд является соответствуюп(им 3)холох) гру ппы информационных вхолов у.тройсгвд, при эточ Выхол элемнга И -й я ники 3-го столби; чзтрицы формировате. .3 й лу 3)олкс)юч 3 к -му входу -го элемента И,1 И группы (гле 1=-1, 2 п) =1, 2, , и), (число вернИн (сслуел(ОО графа), 3)ыхол кзжц)го элем( цтд ИЛИ групим полк.)ю ин к прв)чу Входу олноичнного эл- чнтз И п(рвй 3 ру пц. Выхол -го э,мента И 33(рвои 1 рх и п ь НО.1 кл н)чен к . х Вхолч п.р)ОГ эл)3(нт;3 И,1 И, Выхо,1 г(незторд ичпульсов полклн)чн к (ирному вхолу пер- ВОГО э.1.ч.нз И, ВВ 1 ход которо 1 О п),1 клю 3н к счс)вму Вх.(у счтчикд. Вцхосчегчикд 31 ОЛК,1 ОЧ 13 К )ХОЛУ Л 33 ИфР(3ОР(, ГТ 33)К)- ("Гх. что, с И,(ьн рдсп(ирния фх)(кции(д,)ьнцх взчо,+ постй у трой(тв;3 з;3 С 33 ОИР.1, И НИЯ ВЕЛИЧИНЫ Х(;)К ИЧДЛЬНОГО множ( гв;3 нхтей, покрывающихрдф, В 33 го 13 В,1 н ь )Г 3 х(и Г Н 1:, сх м ч 3 Гор, счтчи к резу,(ь(;т;3, в(оро)3 элечент И,И, третья (руп- ПЗ ЭГх(СИЗОВ И, ГрЛП(д рИСтрОВ СЛВИГЗ, групп;эл(чнт(в ;шржк)3, в кажлук) яцейКу М;)трИПЫ форх)(рО)ТЕС)И ЛуГ ВВ(ЛЕН эЛЕ- х( нт д.(ержки, при м В,ол зхскд г(цердтора )зкговцх (х(3 ух 3 ьсо( я)(,)я( 3 я Вхолоч .)нхск(3 ч Гро)3(т 3;, второи вхо,1 3 рО элечентд И полклкчен к выходу эл чецтз НГ, вхол элемента Н 1; о 6 ьелинн с первыч молом Второго э,)(мента И и полклн)чен к вь(холу элч 3 та )длержки яцйки, .3 ж;3- щей нд пересечении -го стол 6 пз и п-й строки х)(1 Ри 11 ь (Н)РмиРОВт,3(й,1 У Г, Рвь)Й выхол л(ц(ифра)орд полклю ц н к первому )хо.1 х первого э,(ем(та И третьей группь), к второму входу элмента И первой ячейки прво О сто.36 пд л(зтри(1 ы формирователей луг. Нернцй вхол лешифрзторд полклкчен к вхолу э.Х(3(т(3 ззлржки первой ячейки првого стол 6 цд чатри(1 ы форчир(на телй луг, каждый /г-й выход лепифрдторз (гл. (=2, 3 )3) полклн)чен к второму вхолу э,мента И -и ячейки первНО стол 6 ш чзтрицы формирователей луг и входу э.3 мнтз залер кки этой же яцеики первого стол 6 пд чатрипы форчировдтелей луг, выхол элех(33- тд здлржк 3 кзжлой яв йки чд(рипц форчир(дателей луг по;1 клкии 3 к Вхлх установки в О триггера этой же ячейки мзтрипь( форчировдтлеи лу(, Выхол элемента ззлржки .и я инки, кроче п-й, каждой с(рок)3 матрицы формро)тес)сй луг полклн)чен к Второму Ва)лу элемента И и вхолу э.)ечентз длержки +)-й яцйки этой же строки1:312602 Г оста ви тел ь Техред И. Верее Тираж 673 ни о комитета (Л,С,Р н осква, Ж З 5, Рауш рафичеслн нрсднрият1 еда ктор (: П с к а р ьЗаказ 184549В 1111 ПП 11 1 ос 1 дарстнс11 ЗО;15, ХП 1 ни водствснно.воли матрицы формирователей луг, первый вход каждого /-го элемента И третьей группы подключен к выходу элемента задержки ячейки, лежащей ца пересечении 7 г-й строки и (Ф - 1) -го столбца матрицы формирователей луг, выход каждого элемента ИЛИ группы подключен к входу одноимецного элемента задержки группы, выод которого подключен к первому входу одноименного элемента И второй группы, вторые входы всех элементов И второй группы обьединены и подключень 1 к выходу сумматора, выход каждого -го элемента И второй группы подключен к информационному входу одноименного регистра сдвига группы, вход установки начальных условий которого является соответствующим входом группы, входом установки начальных условий устройства, выход каждого с-го регистра сдвига группы подключен к второму входу одноименного элемента И первой группы и второму входу одноименного элемента И третьей группы, выход каждого г.го элемента И третьей группы подключен к г.му входу второго элемента ИЛИ, выход первого элемента ИЛИ подключен к первому входу сумматора, выход второго элемента ИЛИ подключен к второму входу сумматора, выход и-го элемента И второй группы подключен к второму входу второго элемента И, выход которого подклю. чен к информационному входу счетчика результатаа. Т, С,ауноваКорректор Н КорольПодписноеделам иаобретений и открытийкая на 6., д 45е, г, Ужгород, 1 л Проектная, 4