Приемный модуль модели начального узла графа

Приемный модуль модели начального узла графа

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано а моделирующих устройствах, предназначенных для решения на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет определения дополнительных путей коммивояжера, ближайших к минимальному . Устройство содержит блок 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 >(» ?Я На !". )Г?3 УС ", СИ ; I BB ДЛЯ Ре залечи „с > Воях:ера (>?од ля), ° е)(ОГ > . .; Г>)М э I ОГО »510 > Ba Я ВЛ >?» Tr

0i 1>3»>1 i<) ?)>.><>,?>ИО>> >пьных BO:3

» 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 II >рн из ,:О! .-;;. ОДРПИРУЕ!>Юй>-,сти. -4< >

:>: г .>;>ПЕНС Г>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) за><?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>лт, л ьil t! > ей kо>лм>ле(.ч.:-:, бп (3<л<(><1..

"4 lt r!<ЗЛлу

"аяаt<><ач >РЛ>- дГ. стlll 3е I< >I i M, <т" .<ол> и,,:.Ог».;и >>1ТРЛ>, io ее< д»-;,- C><?»nt-.i > ?

Ф>;), », ..)I331< r i i. Iif » - IOB (.!" r fС>< t >j>n»,: i> ri

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<.fllefPd СДВИ10 га, информационные выходы которого до.ОП>IIITCT? >,»!0 ПОДКПЮЧЕНЬ! К ОД»ОН..?Е>!НЫМ

>?нформационным входам се> цио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, . >)>лационных выходов II, llepe(>l? и

ВтОрОй уираеПЯЮ<цИЕ ВХОДЫ СЕ> ц.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$Ppni. iol1 секции ре<истрэ б

>э нымодь> 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зех р» ;в рэ боты: ожидания. приемэ, анализ . и рэн;киронэн<ля, 1134 .. 50 по ис<ечении допустимого чремен>< приема

Всех кодогрэмм настуг<эе! ре;ким, <и<ынэ ния.

В режиме ох(дания .«Одуль ожид:<а) 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 лмь>, cooTBpTcт<)у>ощи; ветвям моделируемой сети. Вхоля>><:«м н оДин и тот w<) узел 3Bri "<сэнэ единиц,). В сi>ализа >од7ль <.рем;->дит н f)B>v«M ожидания, м<>нуя

i<1. . -; рэ» ирснэ<<ия.. случае г>ол«жиепьного результэтB эн:->ли3а блок 1 срэвне> ия п«0 (Н 1)->;у ТИ формирует единичный си. Нал, пос упэющии нэ формирователь 5 сигнэлон. В .) poqeccp осуществления р<>жим", энэлизэ:<э и«форме«ионных входэх элоrB 10 р,,нжировэния формиру(тся

I-разр;Дны;. обрэ<ого пугн) очереднои кодогpBMr1bi, Форм<)рг)пэ 4<нс этого кода осушестнп ;тся -;оэт«)г<нî H блоке 7 зэд;>ния

<(пологии 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