Приемный модуль модели начального узла графа
Изобретение относится к вычислительной технике и может быть использовано а моделирующих устройствах, предназначенных для решения на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет определения дополнительных путей коммивояжера, ближайших к минимальному . Устройство содержит блок 1 сопряжения , элемент И 2, регистр 3 сдвига, блок 4 сравнения, формирователь 5 сигналов с инверсным динамическим входом, секционированный регистр б сдвига, блок 7 задания топологии, сумматор 8, группу 9 элементов НЕ, блок 10 ранжирования и группу 11 элементов НЕ. 2 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 4
С) (Л
l00 ! ()
00 (21) 4804788/24 (22) 20.03,90 (46) 15.01.92, Бюл, М 2 (72) Ю.В.Беликов и П,П.Жигора (53) 681.333(088.8) (56) Авторское свидетельство СССР
1Ф 1339579, кл. G 06 F 15/20, 1985, Авторское свидетельство СССР
f4 1374240, кл. 6 06 F 15/20, 1986. (54) ПРИЕМНЫЙ МОДУЛЬ МОДЕЛИ НАЧАЛЬНОГО УЗЛА ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано в моделирующих устройствах, предназначен„„. Ы „„1705838 А1 ных для решения на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет определения дополнительных путей коммивояжера, ближайших к минимальному. Устройство содержит блок 1 сопряжения, элемент И 2, регистр 3 сдвига, блок 4 сравнения, формирователь 5 сигналов с инверсным динамическим входом, секционированный регис1р 6 сдвига, блок 7 задания топологии, сумматор 8, группу 9 элементов НЕ, блок 10 ранжирования и группу 11 элементов НЕ. 2 ил.
> !1>зб)р те>!бlе относится к еычисп>л! зпьной технике и можРт быль испольaOBa>io в
КВЧРС ГЕЕ г<>С Га ВНОй <аСтИ >С ГРОйСтеа ДЛЯ ОПред< пения пу1еи:оммиеояжера. ()pox(>äti
iJt!n че1; . Вс< iiól>ктл. >уз<>:-I! 3>>ап<<зирнемоб? сe1 "
I 1 э eьт, l!)," )>! !?< тво, ко,!> ðîå I:10.".,> 1
:>0пс., ii 1,>»«» r хэ>i< стае п>3ием!!U о
t >(» ?Я На
0i 1>3»>1 i<)
» ii3)x НОстРИ > I >) >я епя ю! цаяся В .->? Осе>) >4 с><: rl i
Бы< ЕПЯТ» ИЗ )С, Bi! 3 1U:К»Ь>. IIУ<Ей K(J>1!n>1
>«)Я: 11Э )><Л»»..., 1!,?>r!nina!I>,,40I 01 Be(t!3l tdiltlJtл! 1 .р(3. > <о, и нем le9áõñ», о
Oi:.Цвг f I) f,a T; -,, "О> «1У 3:tl1>C СОРД»(? >Рп(>!1 ко .: I C>!3)>ef
:>: г .>;>ПЕНС Г>1» BB 3> л ДЛИНЫ flPllt И. ?ae .,С> - .<3)>ИЧЕ >:У В: —.?Рй Р
1)- 3У,.<.f т: г>1, :<
>Р, и : :1 (; Bi,rr i <>>гл< 1 Bi.it<< Ir>, г,>Г>>>! . i .i, ir i. rr yc<ÐUéÃ; >; В
OOi, 0 » lr: ИО I!i ÂÎÌó < ОРд!>Н.<
-.<" . Ц>;)ас!If<<.f!c l>? eïa с .-:,«..;дами гру»п.l
>() 1r r " rr? > Х> r . !> - ГИ(Тра < li;" 0>>ВМ» »»! - » < > Те . >;()(".; .) »" > ii > к i i Рдла Гae>40(ny r. r, „< явля(-:; ..><,л >":3<,:.
:-.„ьно: U .., po "с:ва для ре?)>е><и?i
«д - ri1 К> i > "! 1>)>:<>;»!r3>>d, (4 >, ОТОрОМ "Ofrt<ЧЕС I по ра:4! .:t> В пб.:»4 1) за>л ()(>ь 0 сп числа узлов Р r О > «1! <Р(4()и:;.. «Fl езупь-,ате при перехо одн(. > ...;:пи сети I(др, гоб с :, 1".На; )вым > <зм, злое Р отпадае< ;0>(>л>1(;От»»,,рен, - "ра i>1>1 ветвей >(о, " .г i, а З>:. . i » <1 (; (.В> Зан>,Ой С зтИ! пе(К(I;1 >>;»q!?rn К(. r Г>. Н> a,?eilei fir э 0>д!.>РКО: >., f>t >I>eb11!t tin МОдулt. ОПрЕд(-.>l:",el, >,1!>, !. fi, > Ь,,.? I>rtnf; -?>I»I!t l>1 ВЕ(.(,»1 ? р» e<> t:3 1liIi". l Г>сех Bo :. Ож;< .:. . <,» l>i r rt1i>! )<) . "I, t. < .В<<Я I<3! Г I 1,r »Е i>rn1. Мо 1 ..<.т ", м(.< .1 < . 443;ь ;;". НР;, с пь др> < >лх ri;;ei близ:! Ix ..ра Гчайше«у, «о бс>лее пре zr)O«Ttnxei?»>I»!X с других го«.—.>; зое НИОЧЕР >;: 3TI1X»>>r > Рй ИЗ t>3, >..М ) !)< > l<. Мсэже I . 3>. <1, >re . f ео >,е4, л»$37< tJi.ltle >1я загр:<>1» о» м>1ьояжера. ;1(пь >лзобб)<) ен.?Я вЂ” расширени фун« (.io!4; пь>>ых ес.. лож><г)с Te>n T?p!>>.w>>oc(1, . пя за Г"<пт lf? 0(дРлРния r> "4 lt r!<ЗЛлу "аяаt<><ач >РЛ>- дГ. стlll 3е I< >I i M, <т" .<ол> и,,:.Ог».;и >>1ТРЛ>, io ее< д»-;,- C> ? Ф>;), », ..)I331< r i i. Iif » - IOB (.!" r f B . и f? 3 < 4,: ! Ii () j I in p; > i, ":! > I р ь гиг)р сдв>л<3, дее группы по элементов НЕ, устройс Во ранжирования, нход измен(ния номера с Itnrt!Baetnctn кодограммы, третья . руопа из п и><формационных выходов моду5 fiB (г>=)0<1,(?й), причем второй уг>раеляю ций выход ".:>Ока сопря:кения через элемент И, f4 3,r t P У C 0!1 сд<)б гo< >?нформационным входам се> циоi«npoda>4но> 0 рег ис rpa сдвига и блока зг>да><ия т зпопогии ьi,ixоц схемы сравнения ч рез фо,">:«лр >ээ)<эп.. 0>лгналое подключен: )ep ВO>1У >(> РЗВЛ Я >0!!>(М" В rОД У x/С? РО «Т В т 03Н лроегп< ля к второму упраеп ющему Входу ; . Г(1>()(<3 li .)д<;л>очен вход из>л-.нения II(if le ра с !n?»>I)der>U>n кодограммы. каждый из вы>. д()В cyf>nматора через одноименный >ле><г >Ррвой группы 3)!»зк<Р.?4гое Н}=. »од I > i." " F > » (д Н 0 б1 f 1 е. Н Н 0 М у И»> ф О 1. < 1 3 ц б r Э . i t 0 М ;,;зд, с<()оисгеэ >Оанжи оез <ия Г ход!.l ;- реой Второй»? третьей > t)y»i> у >раг >як ц,?x BBI o«бoе устройстB:-! раllæt!p()еаhè.) подкп>оч<-í,i к одноименны(л вход;)и 1åpB И, Г)1<1г C)A б,,TÐÅ BÅé ГРУПП УПРВЕПЯ>ОЩИХ Bx:»f>oe <.0>;ц >нироеаннс; р ги: тра сд)ига (.UiDe ..-,, Выходы ру»пы >1»+01>мэ ц>лон><ых ьыходов которого подкпюче» ы к 0, CJrnVie Hilt. > .1 ВЫХОДЭ(Л f!BPBO>n P)rr? > I.I >>Ч 1, . >)>лационных выходов I ВтОрОй уираеПЯЮ<цИЕ ВХОДЫ СЕ> ц.lr»4>ip033!iного регистра сдвига подкл>о <е>>ы к о,т>40 :! .,менниf управлян)щим гlл хода> "Г > ройс Т Ва pj4 I I)K>npO Ba>4!" Я, I(3)> r > б1 tl i Bl>IX>"> (се первой руппы и> формэц:. Jtl»lго в>,>хо ДО>< xOTirPc) I O ПОДХ.» нз > :, le PB; )д <о1 neli>it элемент Втсрои гг ?>)ы зпе 1(! .лентов НЕ к одноименно"1у В! >.од, тс рои i р, ппы инфс)рмационных B Ix<3»!)и f >i л(>пя, !.>Ходы тре?»Рй группы управ IH>QUI>nx Bl,lx0 (б) .,;Ст! Рис r«a ранж npoe:.:ния дополн>л(ельГ>»;,; пюче><<; к од <с»менным выходам РЕ" . ГР > <1Од, . .. . Нэ флг.! представлена структурная схе..?3 Пр».-. <НОГО > Одупя, <43 фбЛГ.2 — фуНКЦИОIf3ËÜiir B СХЕ;?а СЕКЦ?ЛО:!>ЛРОВа»<»>ОГО РЕГИ<:ТРа .дви<3 этог3 модуля. Пр4ь>>л моду»ь со;;ержит блок 1 со,ря). ния. з>:еменг И 2 регистр 3 сдвига, >aîê 1> срав><ения, форглирователь 5 сигна,1оВ с 1HBepeiltlм дин мическим входом, сек>)!.3> роганный регистр б сдвига, бл(>к 7 э )>иIB тог?о" 0>. : I, cófI ляrop 8. группу 9 из I э",etnентое НЕ, при этом 1=1!О Р, Vf( :. 1 1705838 где VI — вес J-й в тви моделируемой сети; )X(— символ округления до ближайшего верхнего числа X. блок 10 ранжирования и группу 11 из I элементов НЕ, На фиг. 1 приняты обозначения: А!— AI,, — группа информационных входов модуля, !«==р-1 (р — число узлов в моделируемой сети); l3 — вход тактовых импульсов(ТИ); С— вход сдвинутых (во времени по отношению к ТИ) тактовых импульсов (СТИ); D)-D„— группа информационных выходов, Н =- р х х(р-1); Š— сигнальный выход; F — управляющий вход; G1-Gi — группа информационных выходов, !1-I группа информационных выходов, n = ) !о9;т(. Схема регистра сдвига приемного модуля состоит из элементов ИЛИ 121-12, 1; группы элементов 2И-ИЛИ 13>-1311, по Н элементов в каждой элементов И 14,- 14, Н вЂ” разрядных регистров 15!-15m с синхронизацией приема. коммутатора 16 с m IJразрядными группами информационных входов, и--разрядной группой управляющих входов и Н-разрядной группой выходов и H-ðà3ðÿäHûõ регистров 171 17„-! с синхронизацией приема, На фиг, 2 К обозначает группу из Н информационных входов, HC3 - группу из rn управляющих входов. НСС вЂ” группу из (m-1) управляющих входов, СС1, СС2 — управляющие входы и НСК вЂ” группу из и управляющих входов, Блок 1 сопряжения предназначен дгя приема и обработки кодограмм, последовательно по одной посгупающих по одному из входов A! — A, и может быть реал»зонан по известной схеме. Элемент И 2 служит для пропускания сдвинутых тактовых импульсов со входа С модуля в регистр 3 пои работе модуля толь ко в режиме приема. Один из входов этого элемента соединен с выходом триг ера блока 1 сопряжения. Регистр 3 сдвига преобразует очередную (Н+1)-разрядную кодограмму, поступившую в модуль. иэ последовательного кода в параллельный, Блок 4 сравнения предназначен для проверки того, побывала ли очередная кодограмма, принятая модулем, во всех узлах моделируемой сети. и выработки сигнала об этом, а также для формирования сигнала, указывающего на окончание приема очередной кодограммы и разрешающего считывание любой из m кодограмм, отобранных (сохраненных) модулем. Формирователь 5 сигналов используется для формирования синхрониэирующего сигнала. разрешающего обработку веса очередной кодограммы лишь по окончании времени, необходимого для форм»рован»я этого веса и представляет собой жду ций мультивибратор. 5 Секционированный регистр 6 сдвига предназначен для приема. хранения и Bl,läçчи кодограмм. отобранных модулем, Bp(которых входит на текущий момент нремени в число ITI наименьших весов принятых коцог10 рамм. Блок 7 задания топологии формирует вес ветвей, по которым прошла очередная принятая кодограмма. Сумматор 8 служит для формирования 15 веса очередной кодограммы, принятой модулем. Группа иэ I ýëåìåíòîâ НЕ 9 прсдсгааляет вес очередной принятой кодограмл ы в обратном коде. 20 Блок 10 предназначен ранжиров,ния совместно с группой элементов НГ 9 для отбора из всех кодограмм, поступивших в модуль, m кодограмм с наименьшим весом, для ранжирования, хранения и выдачи ве25 сов этих кодограмм в обратном коде и их рангов. Группа из I элементов НЕ 11 предсгавляет в прямом коде веса m кодограчл1, «ранимых в обратнол1 коде в уст р-. 1с1н< 10 30 ранжирования. По входам А — Al«ведется прием сдограмм, последовательно поступающ» ° п1 одной из !«входныx ветвей модчля, по ходам В и С в модуль подаются ТИ и СТИ, обе:г1е35 чива1)щие синхронизацию е1о работы по выходам DI-D, происходит выда1а m ксдогра 1М, считываемых по одной из регист! а 6, по вы:«оду Š— выдача сигнала, разреша: щего считывание одно» из г1 кпдограмм. со ра40 ненных модулем, по входу .— увеличива "ся на единицу номер кодограммы, подл .жащей считыванию из модуля, по выходам G1-Gl производится выдача кодов вес1 e m кодограмм. считываемых по однол. ° 1з ло45 ка 10 ранжирования, по выходам I I- > — выдача ранга кодограммы, считываеMoll из регистра б, Элементы или 121-1211-1 предназначены для снятия блокировки прохождения 50 синхронизирующего сигнала с входа "С2 при записи в у — ю (st =2, m-1) секцию регистра б очередной принятой кодограммы или содержимого()p1)-1 секции при прсведг нии сдвигов Элементы 2И вЂ” ИЛИ 13 1 — 13 7 „сл1жат для пропускания в у-ю секцию регистра 6 очередной кодограммы или содержимого (77-1)-й секции. 1705838 ЭЛЕМЕНТЫ И 141 14>л уПрЭВЛЯ>От ПрОхождением синхронизирующего сигнала с вхОДэ СС2 нэ /прэнпяющий вхОД ОДноик1е> I ного регистрэ 15; 15 <), ко!орые обрэзук<т основн«й ре>ис р одноименной ОР> öè<1 cEI(- 5 ционирснэнн(гп регистрэ б Ко>лмутатор 1б ИспользуеI<)s! Для выдэчи c0$Ppn >э нымодь> 1) ->.)«. Pfистры" 1 17<„ l обр;) <уют всг oмо<э- 1<0 )ельный регист р одноил«ен>;ой се :.ции pBI I! стра б, По входar1 Н(8 осущесгн,>чет<.я прие>1 из блока 10 рэн>кированич гп-разрядного унитэрного кода номера основной секции, 15 которая вь>брэн", дп зэпис>л очередной кодогрэммы, по: ..одам 4 - прием Н-рэзрчд ОЙ П > .: ЕДНГ ; )Д<3 РЭ М>Л <.! >! 3 РЕ< ИСТ !. Э nc!i, nЯ..;о н. („:,-.;м НСС - прием и; блока 10 анжиронэни (><- 1)-рэзрчдных кодов н«ме ?О < B СЕ >(l È < < Н < Э :. <У Ю И 3 К < )ТО РЫ Х ДП Л >К, H ,«" „,„ rRi<Я1hr. =, ГДВ<1! Из СРКЦИИ С НО<1ЕРОМ нэ Br«l><м ее но>лерэ, прэ<>л<>>о<ц<1Р входы СС1 и СС2 пред. э. ч внь! для синхронизации процессов 25 записи соотве!с>венно Во вспомогэтельные :n >снов><ые регистрьi секционировэнного -.!C1<).:i Р. пупс; сксдо>;СК преднэзначeiIO«; ><Одо НОМЕра CHÈòh За- 0 е>лой кодогр;;м, ы из блскэ 10 рэнжирог)аНИЯ. ГРУП<,Э .,Ь<мароа D1-0» - ДЛЯ НЫДЭЧИ Н разряд:>ого содержимого выбранной секц< и регистра F, Перед >>э <эли« работы в блоке 7 зада- 35 <ия топологии Rhl(; I BBiiÿ>oò весэ ветвей мод лируемои сети В начэльное сосТО >4<«Р модуль переводят c, гнэлом нэчэльной устэ нонки. Под во"-д..йствием этого сигнала r гистры 3 и 6 э r;I(; е Br.е триггеры блок(10 сопряжения и бл 3>..э 10 оэнжировэн>ля ус) э н- вливаются в "0". На входы В и С подаются состветственно 1И и СТИ, Нэ входах А)-h, и F прис, c>f)y>OT нулевые потенциэлы. Пр.«<=мн>, и <Г.q,(;<- р-"ботэет io i Г!Ив>.>их кодогрэмм. В каждом цикле Mод, ь нэходитсч B Одno>n из ч(:ты1зех р» ; Всех кодогрэмм настуг<эе! ре;ким, <и<ынэ ния. В режиме ох(дания .«Одуль ожид:<а) 00 <; гупле><ие Очер< ДнпЙ <ОДОГрэ>лмы Г и <>Дно 55 >ЛЧ ИЗ ВХОДОВ Г I %>i, >(- P О «и< м >д, ля в нэ-альном <.oñò )чь<и
Т Н ЫИ СЛУЧ < «Э Г>:;. I. !BI«I«Ч <>оступлэниР .! Мэр><е!!- черед»< "«; B ч,)с:n сти, первой1 (>-(I 1)-разрядной кодо! рэ>лмы по I-му (>=1,k) входу Af модуль переход«T в режим прин>лэ. Это сопровождается установкой единичного сигнала на нь>ходе бпокэ 1 сопряжения, соединенном с элемен<(м И ?. В результате снимается блок<<ронк;) для прохождения С)И нэ вход уп ранг>ения с)виfoM нэ один разряд влево B сторону ст<)р<>>их разрядов регистра 3. 0череднэя кодог1)BM ма по; эзрядно проходит через блок 1 сопряжения в регистр 3, по ТИ записывэе) я в >ллэдший разряд регистра 3, э по СТИ (дни lBB1csi нэ один разряд влево, Кроме «i 0. B J и разряд кодогрэммы (j = 1, Н н пер<<чне HГ)меров l>oTsåé Mоделируемой cBTi1 и соот ннтстнует номеру i-й негви в пг<ре fllå н<)мероэ Вет ней, нкодящих н .<дедуль). <<Ог, гупэющеи в ре истр 3. 3,) н(<(итс я "1" Т!)ким образом от;лечэе)сч фа>,т i ос)у->леия н модуль очередной кодогрэм<лы п<> )-й Bpт «и моделируемой cB«è, или»о I Й f« .тви модуля. В процессе зэписи к<>ДО! р "<>«мь> н ,")ОГистр 3 ВГО нымодныР си> н<>пы /<1)<". .1è ус>ройстнэми модуля не н<)<. Г>рин»1:- к )ся Нэ (Hi-1)-м ТИ режим приема зэкэнчинлс ся, При этом нэ выходе блока 1 сопрялке <ия, c<)päè>fål4>4oM с элементом И?, устэнанллвэе; я нулевои >)отенциал,;) через выход блоvэ i сопряжения, соединенныи с бл(>к<;м « срэннения, проходит (Н+1)-й ПИ. < onçð>>дам р Гисгрэ 3 с 1 ГО Ilo Н-й окэз,>на тся 3 )il>1 сэнноЙ инфopMэцион>4дя <эсTВ Г>риi iч Гоli vодогрэммы. Модуль переход>лт в ре;ким энэпиза. Содер>кэние режимэ э><элизе cостанляет э>>dëèç гого, побь>нэ<>э г« lipинч тая, т.е. запиг.эннэч в регистр 3. кодогрэммэ нс всех узлэх моделируемой сети. Пол(>ж!— ТЕЛЬНЫЙ РЕЗУЛЬтвт ЭНЭЛИ а ИМР«З< !«сетей ЕС<и B 0+Ho!1 из рэзрядон кэ>кдг<Й r;1 i<1. . -; рэ» ирснэ<<ия.. случае г>ол«жиепьного результэтB эн:->ли3а блок 1 срэвне> ия п«0 (Н 1)->;у ТИ формирует единичный си. Нал, пос упэющии нэ формирователь 5 сигнэлон. В .) poqeccp осуществления р<>жим", энэлизэ:<э и«форме«ионных входэх элоrB 10 р,,нжировэния формиру(тся I-разр;Дны;. обрэ <(пологии n(i мес- ол; жению единиц в р(<з()чдэ ре! <«c < !)B,! BG(:производятся ><«+bi янсон (,>при>лер, дг<ин, <ех ветвей, котсрые впн!)>! в пу;ь, пройден> .Й очередной кодог-! ..<«<;c<. R сум>ла<=>о :! !1 коды ариф>лРТИ1705838 5 55 чески суммиру1О1ся. Полученный реэуль тат инвертируется группой элементов НЕ 9. Кроме того, по заднему фронту выходного сигнала блока 4 сравнения срабатывает формирователь 5. Длигельность выходного си нала этого формирователя гарантированно бс льше времени окончания переходи мах пг1;1;ессов в бл13к 7 задания топологии, сум -»оре 8 и группе элементов НЕ 9. Pew,; Iì a,:àлиэа заканчивается к моменту форм!1рования заднего фрОнта выходнОГО сигнала формирователя 5. Одновременно с этим начинэ:.тся режим ранжирования. В начале режима ранжирования на информационных входах блока 10 ранжирования находится код веса очередной кодограммы в обратном к:Дс ран е сформированный в режиме aiian«.:;;. Использование обратно о кода позволяет Ог;уществлять отбор и ран.кирование кодограмм наименьшего веса на блок 10 ранжирования кодограмм, предназначенный для выполнения указанных операций над кодограммами на большего веса. Блок 10 ранжирования устанавливается по заднему фронту сигнала с выхода формирователя 5 в начально" состояние. При этом на группе входов К регистра 6 (см.фиг.2) продолжаег находиться информационн;,я Н-разрядная:1асть очереднои кодограммь, (бе:; маскера), постуn3Ioùeè с выходов регистра 3 и сформированнои в режиме rioi;eма, Кьждый разряд этой Н-разрядной ксдограммы поступает на одноименнье1 иí(|)орма 1иo÷nûé вход регистра 15 и и 111.,ормацисн11ыг . ход первой группы входов одноименнь,х 3 1ементов 2И l1.III,1 кажДой 13 Гpyп и 13 )- 13п, 1. П(заДн " му фронту выходного с 1 нала форм;1рователя 5 блок 10 ранжирования устанавливается в началь -,ор, состоя ivlp. При этом на управляющих вхп,ах НСЗ регистра б усганавливася 1 в п1-разряд11ом унитар» зм коде. С первого охода груп 1ы управляющих входов НСЗ подается единичныи сигнал на один из входов элемента И 14. С остальных входов этой группы подается нулевой потенциал. Единичный сигнал подается ча все m-1 входы группы управляющих входов НСС регистра 6 и далее на управляющий вход второй группы входов каждого элемента 2И-ИЛИ каждои из групп 131-13„-1, На каждом информационном входе второй группы входов каждого элемента 2И вЂ” ИЛИ каждой иэ групп 13i-13 11-1 устанавливается содержи ioe одноименного разряда вспомогательного регистра секции с номером. на единицу меньшим номера секции основного регистра. Этими сигналами регистр 6 подготавливается к записи очередной кодограммы с группы входов К в первую секцию регистра 6 и к приему содержимого секций с 1-й no (m 1)-ю в секции со 2-й по m-ю соответственно, На управляющих входах СС1 и СС2 устанавливается нулевои потенциал. не разрешающий ни проведение записей, ни проведение сдвигов в регистре 6. Ранжирование веса очередной кодограммы в обратном коде осуществляется блоком 10 ранжирования и заключается в определении того, должна ли быть сохранена очередная кодограмма и каково ее место (ранг) среди ранее отобранных кодограмм. 8 случае принятия решения о сохранении блок ранжирования размещает код вес;i сохраняемой кодограммы в соответствии с его величиной среди кодов весов ранее отобранных и отранжированных кодограмм в своих регистрах. а также осуществляет необходимые для этого размещения сдвиги. Кроме того, оно вырабатывает управляющие сигналы регистру б на точно таки» же размещение сохраняемой и сдвиг р; нее отобранных кодограмм соответственно, При этом кодограмма m-ro (нэибольы.его) ранга и ее вес в обратном коде исключаются из числа отобранных. 8 случае принятия отрицательного решения о сохранении никаких изменений среди ранее отобранных кодограмм не производи1ся. В ходе осуществления режима ранжирования в регистре б использу отся сигналы только на груг1пах входов НСЛ, НСС и входах СС.l и СС2, При этом на ° руппе входов НС3 устанавливается ранг r кода веса очереднои кодограммы (г=1 m), установленный бяоком 10 ранжирован.«. Ранг г посту11ает в уни1арном m-разрядном коде для указания номера секции r в реги"тре б. в которую необходимо осуществить запись очередной кэдограммы, подаваемой с выхода рсги<.тра 3 При э-ом единичный сигнал поступает на один из входов элемента И 141, если r=1, или на управляющий вход первой группы входов каждого элемента 2И-ИЛИ группы 13,, если 2 < r < m — 1. Это приводит с последнем случае к поступлению каждого разряда очередной кодограммы через информационный вход первой группы входов одноименного элемента 2И--ИЛИ гэуппы 13 -1 на одноименный информационный вход регистра 15о Кроме того, единичный сигнал с r-го входа группы входов HC3 ч11рез элемент ИЛИ 12,-) поступает на один из входов элемента И 14 . если 2 < r 5 in — 1, блокируя подачу сигнала с входа СС на управляющий вход регистра 15, через элемент И 14г. 1705838 На группу входов НСС в и-разрядном двоичном коде поданы номера секций регистра 6, s которые должен быть осуществлен сдвиг содержимого секций, номер каждой из которых на единицу больше номера секции. из когорой предусмотрено осуществление сдвига. При этом единичный сигнал подается на входы с r-го по (m — 1)-й группы входов НСС и далее на каждый из управляющих входов второй группы входов каждого из элементов 2И-ИЛИ групп 13г — 13m-1. B результате разрешается подача на информационные вхо ды каждого из основных регис1ров 15rI t — 15п содержимого одноименных разрядов вспомогательных регистров 17,-17mt соответственно, Кроме того, этот сигнал через каждый из элементов ИЛИ 12г — 12„-1 подается на один из входов одного из элементов И )4,-1 14m соответственно, блокируя подачу . игнала с входа СС2 на управляющий вход каждого из регистров 15 1 — 15m через одноименный элемент И из числа злеме Hl o B 14r+1--14 п. По уста овлении ранга веса очередной к >д раммы на входе СС1 регистра 6 появл ется единичный сигнал, который поступаoò la управляюц1ие входы вспомогательных регистров 17I 17 -ь При этом осуществляет.я запись содео>кимого каждого из основных регистров 151- 5г, е одноименные вспомогательные регистры 171-17 - ь По пкснчании действия сигнала с входа СС1 единичный сигнал появляется на входе СС2. По этому сигналу происходит запись очер..дной кодограммы в основной регистр 15, 1 запись содержимого каждого из вспомога1ел -,ных регистров 17, 17П1-1 в соответствующии из основных регистров 15-1 15„. На эт,"м работа модуля в режиме ранжирогзния, а вместе с: им и очередной цикл рабо; модуля заканчиваются. Режим считывания начинается по г>кон<ании последнего цикла работы модуля и :.осте ени! допустимого времени приема ло пулем кодограмм Этот момент сопровождаетсяя установлением единичного потенциала на выходе F модуля. При этом блок 10 ранжирования устанавливается в начальное состояние, э BHFшней нагрузкой с выходов 51 В, воспринимается содержимое кодограммы 1-го ранга. С выходов С 1 Gt u Shtxo дсв Ii-lt снимаю1 вес и ран. этой : одограммы соответственно. Нэ группе входов HCi, устанавливаешься единица в rl-разрядном двоичном коде, ко т рыи поступает на Группу чпрзвля -ощих LIõoäoa коммутагора 16 Это риводит к вы— даче содержимого основного регистра 5, ЧЕ ",.З КОММутатОр 6 .Ia ВЬ ХОдЫ Dt D,, Гi I 25 > p 45 налы на указанных выходах остаются неизменными до поступления единичного сигнала на входе F. увеличивающего на единицу номер считываемой кодограммы. При подаче нэ F-вход s единичных сигналов 1< S = m- 1 На ВЫХОДЫ DI-Он ВЫдаЕтея СОдержимое кодограммы (s+1)-ro ранга. л на выходах Gt-Gt u lt-(It — соответственно вес и ранг этой кодограммы. При этом на гр ппе входов НСК формируется п-разрядныи двоичный код числа s+1, который по аналогии с, указанным приводит к выдаче содержимого основного регистра 15s+1 на выходы Dt О,. В режиме считывания управляющие сигналы на входах СС1 и СС2 не выраба1ываются, а сигналы на группах входов НСЗ и НСС регистром 6 не воспринимаются При floступлении очередного единичного сигнала на вход F в момент выдачи кодогрэммы,п-го ранга происходит изменение номера считываемой кодограммы с m на 1 Режим считы вания производится до установки модуля в начальное состояние, осуществляемое оператором, Эффективность использования paHltoro приемного модуля состоит в обеспечс нии возможности определения с его помогцью дополнительно по отношению I; пут минимального веса. например, кратчайшему выявляемому прототипом, еще дг (rtt 11 путеи, ближайших к пути минимального веса Использование этой возможнос и може позволить принимать решения по зада taM, сводимым к задаче коммивояжера не только по одному показателю (например gt ине пути), но и с уче1ом некоторы других например порядка посещения нзиболее важных пунктов в начале пути, посещ ния максимального числа пунктов в начале пути за отведенный отрезок времени. Использование указанных показателей при эы(оре среди близких по длине путей явллегс существенным. например, при решении задачи по обслу киванию е условиях заражения с асэтельнпй бригадой пунктов разнои >битэемости. В згом -.лучае качество управ1енческих pELLIpний повышается, Формула изобретения Приемный модуль модели начального узла графа, содержащий блок сопряжения, регистр сдвига, блок сравнения, блок зэдания топологии и сумматор, причем информационные входы группы приемного модуля псдключены опноименным входам блока сопряжения, вход тактовых импульсов которого подключен к одноимен -ому входу приемного модуля, сигнальный выход 1705838 14., ока сравнения -- к одноименному входу приемного модуля, информационный выход I„первый управляющий выход блока сопряжения — к информационному входу регистра сдвига и к управляю дему входу блока срав- 5 нения соответственно, информационный выход:, егистра сдвига -- к информационноt .y вх-.,> блока сравнения, выходы группы бл.ка задания топологии — к одноименным вход" i ", су матора. отличающийся тем. 10 что, с целью расширения функциональных «озможнос ей модуля путем определения дополнительных путей коммивояжера, ближайшик к минимальному, в него введены элемент И, формирователь сигчалов с ин- 15 версньIM динамическим входом, секционированный реги<.тр сдвига, две группы элементов НЕ и блок ранжирования, причем второй управляющий выход блока сопряжения подключен к первому входу элемента И. 20 выход которого подключен к входу управления сдвигом регистра сдвига. разряды информационного выхода которого подключены к соответствующим информационным входам секционированного реги- 25 стра сдвига и соответствующим входам опрога блока задания топологии, второй вход.=:лемента И является входом сдвинутых гактовых импульсов приемного модуля, выход блока сравнъ ия через формирователь 30 сигналов с инверсным динамическим входом подключен к первому управляющему входу блока ранжирования, второй управляющий вход которого подключен к входу изменения номера считываемой кодограммы приемного модуля, разряды информационного выхола сумматора через соответствующие элементы Н Е первой группы подключены к соответствующим разрядам информационного входа блока ранжирэвания, управляющие выходы пЕрвой, второй и третьей групп которого подключены к управляющим входам первой, второй и третьей групп секционированного регистра сдвига соответственно, информационные выходы группы которого являются информационными выходами первой группы приемного модуля, первый и второй управляющие входы секционированного регистра сдвига подключены к одноименным управляющим выходам блока ранжирования соответственно, информационные выходы группы которого подключены через одноименный элемент НЕ второй группы к соответствующему информационному выходу второй группы приемного модуля, управляющие выходы третьей группы блока ранжирования подключены к информационным выходам третьей группы приемного модуля. 1705838 4Ъ2. Г Составитель Ю, Беликов Редактор Л. Пчолинская Техред М.Моргентал Корректор Л, Патай Заказ 195 Тираж Подписное ВНИИПИ ГосУдарственного комитета по изобретениям и открытиям при ГКНТ СССР 113035. Москва, Ж-35. Раушская наб., 4/5 Производственно-издательский комбинат "Ч1 атент", г. Ужгород. ул.Гагарина 101
