SU1119023A1

SU1119023A1 - Device for simulating propabilistic graph

Info

Publication number: SU1119023A1
Application number: SU823527988A
Authority: SU
Inventors: Николай Федорович Морозов; Виктор Дмитриевич Трусов
Original assignee: Институт Технической Кибернетики Ан Бсср
Priority date: 1982-12-23
Filing date: 1982-12-23
Publication date: 1984-10-15

Abstract

УСТРОПСТВО ДЛЯ МОДЕЛИРОВАНИЯ ВЕРОЯТНОСТНОГО ГРАФА, содержащее генератор случайных чисел, коммутатор , первую, вторую и третью группы элементов И, первую и вторую группы счетчиков, первые входы и выходы элементов И первой группы вл ютс .соответственно группой информационных входов и группой информационных выходов устройства, первый выход коммутатора вл етс управл ющим выходом устройства, выходы элементов И .второй группы соединены с входами счетчиков первой группы о тличающеес тем, что, с целью сокращени аппаратурных затрат; в устройство введены m-разр дный регистр сдвига (т - максимальное число ребер моделируемых граф), (т+1)-разр дный регистр сдвига, триггер, три элемента И, элемент задержки и элемент НЕ, причем второй .выход коммутатора соединен с единичными входами первых разр дов, нулевыми вхбдами 2,3,... ,к разр дов п разр дного регистра сдвига, 2,3,..., ..., (т+1) разр дов () -разр дного регистра сдвига и нулевым входом триггера, тактовый выход генератора случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (т+1)-разр дного регистра сдвига, выходы которого, кроме (т+1)-го, соединены с вторыми входами элементов И первой группы, (т+1)-й выход (т+1)разр дного регистра сдвига соединен о ® через элемент задержки с вторым входом первого элемента И и входом л элемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу третьего элемента И, выходы которых соединены соответственно со сдвиговыми №-раз р дного и ()-разр дного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий со выход которого соединен с первыми о входами элементов И второй группы, Кд . вторые входы которых соединены с со выходами tn-разр дного регистра сдвига, а выходы - с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы а вторые входы объединены и соединены с выходом триггера, единичный вход которого вл етс управл ющим .входом устройства.A DEVICE FOR MODELING A PROBABLE GRAPH containing a random number generator, a switch, the first, second and third groups of elements AND, the first and second groups of counters, the first inputs and outputs of elements AND of the first group are respectively a group of information inputs and a group of information outputs of the device, the first the switch output is the device controlling output, the outputs of the elements AND of the second group are connected to the inputs of the counters of the first group, which are characterized in that, in order to reduce the hardware costs t; an m-bit shift register is entered into the device (t is the maximum number of edges of the simulated graph), (t + 1) is a shift register, trigger, three AND elements, delay element, and NOT element, the second output of the switch is connected to the unit inputs of the first bits, zero bits 2.3, ..., to bits n of the bit shift register, 2,3, ..., ..., (t + 1) bits ()-bit bit shift register and the zero input of the trigger, the clock output of the random number generator is connected to the first inputs of the AND elements, the stochastic output of the random number generator with dinene with the second input of the second element I and with the information input of (t + 1) -discharge shift register, the outputs of which, except for (t + 1) -th, are connected to the second inputs of the elements of the first group, (t + 1) -th the output (t + 1) of the bit shift register is connected via ® via a delay element with the second input of the first element AND and the input of the element NE, the output of which is connected to the third input of the second element And and the second input of the third element And, the outputs of which are connected respectively to the shear No. of times the regular and () -discharge shift registers, the output of the first element And connected to the input of the switch, the third with the output of which is connected to the first about the inputs of the elements And the second group, Cd. the second inputs of which are connected to the outputs of the tn-bit shift register, and the outputs to the first inputs of elements AND of the third group, the outputs of which are connected to the inputs of counters of the second group and the second inputs are combined and connected to the output of the trigger, the single input of which is controlling device input.

Description

Изобретение относитс к вычислительной технике и может быть использовано при статическом моделировании сложных систем, представленных в вид веро тностного графа, с целью определени качественных характеристик, в частности показателей надежности систем. Известно устройство дл моделировани веро тностного графа, содержащее блок кодировани и декодировани команд, поступающих от ЭВМ, электронный коммутатор с т+3 выходными шинами , тп триггеров пам ти, п управл емых ключевых схем, m вентилей, логическ схему и триггер результата. Функцио нирование устройства происходит по циклам. Каждый цикл содержит тактовые моменты tu -сброс триггеров пам ти и триггера результата f ,; i .. . ,С -вьщача импульсов на вс Т -испытание схемы отображающей раф на проводимость, t съем информации с триггера результата . Недостатком данного устройства вл етс необходимость использовани ЭВМ. Наиболее близким к предлагаемому устройству вл етс устройство дл статистического моделировани веро тностного графа, содержащее генератор случайных чисел, тактовый и.стохасти ческий выходы которого соединены соответственно с входом коммутатора и с первыми входами элементов И первой группы, вторые входы которых под ключены соответственно к группе выходов коммутатора, первый выход которого соединен с нулевыми входами триггеров первой группы, единичные входы которых подключены соответственно к выходам элементов И первой группы, а выходы триггеров первой группы подключены соответственно к первым входам элементов И второй группы, вторые входы и выходы которых вл ютс соответственно группой входов и группой выходов устройства, выходом которого вл етс второй выход коммутатора, элемент ИЛИ, входы которого подключены к выходам элементов И первой группы, а выход соединен с входом с 1етчика, соединен ного выходом с входом дешифратора, управл ющий вход которого подключен к третьему выходу дешифратора,первый выход которого соединен со входом Сброс счетчика и с нулевыми входам триггеров второй группы, единичные входы которых подключены к выходам дешифратора и к счетным входам счетчиков первой группы, выходы триггеров второй группы соединены с первыми входами элементов И третьей группы , вторые входы которых объединены и вл ютс входом устройства, а выходы соединены с входами счетчиков второй группы 2. Недостаток устройства заключаетс в большом количестве оборудовани . Кроме того, наличие дешифратора затрудн ет расширение устройства. Цель изобретени - сокращение аппаратурных затрат устройства. Поставленна цель достигаетс тем, что в устройство дл моделировани веро тностного графа, содержащее генератор случайных чисел, коммутатор, первую, вторую и третью группу элементов И, первую и вторую группу счетчиков, первые входы и выходы элементов И первой группы вл ютс соответственно группой информационных входов и группой информационных выходом устройства, выходы элементов И второй группы соединены с входами счетчиков первой группы, дополнительно введеным-разр дный регистр сдвига, (|п+1)-разр дный регистр сдвига , триггер, три элемента И, элемент задержки, элемент НЕ-, причем второй выход коммутатора соединен с единичными входами первых разр дов, нулевыми входами 2,3,...,w, разр дов т-разр дного регистра сдвига, 2,3,..., ..., (т+1) разр дов (т+1)-разр дного регистра сдвига и нулевым входом триггера, тактовый выход генератора случайных чисел соединен с первыми входами элементов И, стохастический выход генератора случайных чисел соединен с вторым входом второго элемента И и с информационным входом (т+1)-разр дного регистра сдвига, выходы которого, кроме (т+1)-го, соединены с вторыми входами элементов И первой группы, (т+1)-и выход (т+1) разр дного регистра сдвига соединен через элемент задержки с вторым входом первого элемента И и входом элемента НЕ, выход которого подключен к третьему входу второго элемента И и второму входу Третьего элемента И, выходы которых соединены соответственно с сдвиговыми входами пт-разр дного и (гг+1) разр дного регистров сдвига, выход первого элемента И соединен с входом коммутатора, третий выход которого соединен с первыми входами элементов И второй группы, вторые входы которых соединены с выходами т-разр дного регистра сдвига, а выходы - с первыми входами элементов И третьей группы, выходы которых подключены к входам счетчиков второй группы, а вторые входы объединены и соединены с выходом триггера, единич ный вход которого вл етс управл ющим входом устройства. На фиг.1 изображена структурна схема устройства; на фиг.2 - вариант набора схемы графа; на фиг.З - граф. Устройство содержит генератор 1 случайных чисел, элементы И 2 - 4, (т+1)-разр дный регистр 5 сдвига, первую группу элементов И 6,6 ,... ..,,6, элемент 7 задержки, элемент НЕ 8,m-разр дный регистр 9 сдвига, коммутатор 10, триггер 11, вторую группу элементов И 12 , 122,...,12, первую группу счетчиков 13,13 ,... ...,13, третью группу элементов И 14-,, ,..., 14, вторую группу . счетчиков 15 ,15 ,...,15fn, элемент И 16 (фиг.2.) . Устройство работает следующим образом. В исходном состо нии (т+1)-й разр д регистра 5 сдвига установлен в единичное состо ние. В результате подготовлен к работе элемент И2.Импульс с тактового выхода генератора случайных чисел проходит через элемент И2 на вход коммутатора 10, и по вл ющийс на первом выходе коммутатора 10 импульс устанавливает в нулевое cocfо ние триггер 11, устанавливает в единичное состо ние первые разр ды и сбрасывае г остальные разр ды регистров 5 и 9 сдвига. На выходе (т+1)-го разр да регистра,3 сдвига по вл етс нулевой сигнал, который, пройд через элемент 7 задержки , запрещает прохождение следую щих импульсов на вход коммутатора 10 и разрешает, пройд через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И4. Следующий импуль с тактового выхода генератора проходит через элемент И4 на вход регистра 5 сдвига, сдвига содержимое на один разр д и одновременно занос в первый разр д информацию о состо нии стохастич1еского выхода генератора 1 b то же врем импульс с тактового выхода через элемент ИЗ попадает на вход сдвига регистра 9 сдвига только 1 3 тогда, когда на стохастическом выходе генератора присутствует единица. Каждый прошедший импульс сдвигает информацию (единицу в первом разр де) на один разр д и заносит в первый разр д регистра 9 нуль, так как информационный вход регистра 9 соединен с входом сигнала логического О. Последующие импульсы действуют аналогично . После прохождени тт импульсов на вход регистра 5 сдвига единица попадает в (т+1)-ый разр д и единичный сигнал, задержанный на элементе 7 задержки на врем , достаточное дл прохождени заднего фронта импульса, сдвинувшего единицу Вд(т+1)-ый разр д регистра 5, разрешает прохождение последующих импульсов на вход коммутатора 10 и запрещает, пройд через элемент НЕ 8, прохождение импульсов через элементы ИЗ и И4 на входы регистров 5 и 9 сдвига. Таким образом, в регистре 5 сдвига в первых m разр дах формируетс информаци о наличии или отсутствии ребер графа (1-е ребро присутствует, О ребро отсутствует ), а в регистре 9 сдвига единица устанавливаетс только на выходе первого разр да, если в текущей реализации отсутствуют ребра графа (отказ m ребер графа) на выходе второго разр да, если в текущей реализации присутствует одно ребро (отказ т-1 ребер),..., на выходе m-го разр да , если в текущей реализации присутствует одно ребро (отказ т-1 ребер ) ,..., на выходеm-го разр да, если присутствует m-l ребер (отказ одного ребра). Последующие импульсы с тактового выхода генератора 1 проход т через элемент И2 на вход коммутатора 10, в результате по вл етс импульс на втором выходе коммутатора 10, котррьй поступает на вход схемы, граф набранной из элементов И6. Если в данной реализации граф оказываетс св занным, то импульс проходит на выход схемы граф, к которому подключен единичный вход триггера 11, устанавлива его в единицу. Если же граф оказываетс несв занным, то импульса на выходе схемы не будет,и триггер 11 останетс в нулевом состо нии . По вл ющийс затем на третьем выходе коммутатора 10 импульс опрашивает состо ние разр дов регистра 9 сдвига, и в зависимостиThe invention relates to computing and can be used in static modeling of complex systems represented in the form of a probabilistic graph, with the aim of determining the quality characteristics, in particular the system reliability indicators. A device for modeling a probabilistic graph is known, which contains a coding and decoding unit for commands from a computer, an electronic switchboard with t + 3 output buses, a memory trigger, n controlled key circuits, m gates, a logic circuit, and a result trigger. Functioning of the device occurs in cycles. Each cycle contains clock moments tu - reset of memory and trigger triggers of the result f,; i .. , C-pulses to the sun T-test circuit displaying raf on conductivity, t removing information from the result trigger. The disadvantage of this device is the need to use a computer. Closest to the proposed device is a device for statistical modeling of a probabilistic graph containing a random number generator, clock and stochastic outputs of which are connected respectively to the input of the switch and the first inputs of the AND elements of the first group, the second inputs of which are connected respectively to the output group the switch, the first output of which is connected to the zero inputs of the triggers of the first group, the single inputs of which are connected respectively to the outputs of the AND elements of the first group, and the outputs of the first group of flip-flops are connected respectively to the first inputs of the elements of the second group, the second inputs and outputs of which are respectively a group of inputs and a group of outputs of the device whose output is the second output of the switch, the OR element whose inputs are connected to the outputs of the elements of the first group and the output is connected to the input from 1 detector connected to the output of the decoder, the control input of which is connected to the third output of the decoder, the first output of which is connected to the Reset input of the counter and with zero the inputs of the second group of flip-flops, the unit inputs of which are connected to the outputs of the decoder and the counting inputs of the counters of the first group, the outputs of the second group of flip-flops are connected to the first inputs of the AND elements of the third group, the second inputs of which are combined and the device's inputs the second group 2. The drawback of the device is a large amount of equipment. In addition, the presence of a decoder makes it difficult to expand the device. The purpose of the invention is to reduce the hardware cost of the device. The goal is achieved in that a device for modeling a probabilistic graph containing a random number generator, a switch, a first, second, and third group of elements AND, a first and second group of counters, first inputs and outputs of elements AND of the first group are respectively a group of information inputs and a group of information output devices, the outputs of the elements And the second group are connected to the inputs of the counters of the first group, additionally entered-bit shift register, (| n + 1) -bit shift register, trigger, three the element And, the delay element, the element is NOT-, and the second output of the switch is connected to the single inputs of the first bits, zero inputs 2,3, ..., w, bits of the t-bit shift register, 2,3, ... , ..., (t + 1) bits (t + 1) -discharge shift register and zero trigger input, clock output of a random number generator connected to the first inputs of the And elements, stochastic output of a random number generator connected to the second input of the second element Both with the information input of the (t + 1) -discharge shift register, the outputs of which, except for (t + 1) -th, are connected to w by the inputs of the elements of the first group, (t + 1) -and the output (t + 1) of the bit shift register is connected through a delay element to the second input of the first element and the input of the element NO, the output of which is connected to the third input of the second element and the second the input of the Third element And, the outputs of which are connected respectively to the shift inputs of the PT-bit and (yy + 1) bit shift registers, the output of the first element And is connected to the input of the switch, the third output of which is connected to the first inputs of the elements of the second group, the second inputs which connect The outputs are with the outputs of the t-bit shift register, and the outputs are with the first inputs of elements of the third group, the outputs of which are connected to the inputs of counters of the second group, and the second inputs are combined and connected to the output of the trigger, the single input of which is the control input of the device . 1 shows a block diagram of the device; figure 2 is a variant of the set of graph schemes; on fig.Z - graph. The device contains a generator of 1 random numbers, the elements And 2 - 4, (t + 1) -digit register 5 shift, the first group of elements And 6,6, ... .. ,, 6, the delay element 7, the element NO 8, m-bit register 9 shift, switch 10, trigger 11, the second group of elements And 12, 122, ..., 12, the first group of counters 13,13, ... ..., 13, the third group of elements And 14- ,,, ..., 14, the second group. counters 15, 15, ..., 15fn, the element And 16 (figure 2.). The device works as follows. In the initial state, the (t + 1) -th digit of the shift register 5 is set to one. As a result, the I2 element is prepared for operation. An impulse from the clock output of the random number generator passes through the I2 element to the input of the switch 10, and the pulse appearing at the first output of the switch 10 sets the trigger 11 to zero zero, sets the first bits to 1 and reset the remaining bits of the 5th and 9th shift registers. At the output of the (t + 1) th register bit, a 3 shift appears a zero signal, which, having passed through delay element 7, prohibits the passage of the following pulses to the input of switch 10 and permits, passing through HE element 8, the passage of pulses through elements of iz and i4. The next pulse from the clock output of the generator passes through the element I4 to the input of the register 5 shift, shifting the contents by one bit and simultaneously bringing to the first bit the information about the state of the stochastic output of the generator 1 b at the same time the pulse from the clock output goes through the element IZ the shift input of the shift register 9 is only 1 3 when a unit is present at the stochastic generator output. Each transmitted pulse shifts the information (one in the first bit) by one bit and writes 9 bits to the first bit of the register, since the information input of register 9 is connected to the input of the logical O signal. Subsequent pulses act in a similar way. After the passage of the pulses to the input of the shift register 5, the unit enters the (t + 1) -th bit and the single signal delayed by the delay element 7 for a time sufficient to pass the trailing edge of the pulse that shifted the unit Hc (t + 1) -th register bit 5, allows the passage of subsequent pulses to the input of switch 10 and prohibits the passage through the element NOT 8, the passage of pulses through the elements IZ and I4 to the inputs of the registers 5 and 9 of the shift. Thus, information on the presence or absence of graph edges (1st edge is present, O edge is absent) is generated in the first 5 bits in shift register 5, and in the shift register 9, the unit is set only at the output of the first bit, if in the current implementation there are no edges of the graph (failure of m edges of the graph) at the output of the second bit, if there is one edge in the current implementation (failure of t-1 edges), ..., at the output of the mth digit, if there is one edge in the current implementation ( failure of t-1 edges), ..., at the output of the m-th digit, if ml is present ber (failure of one rib). Subsequent pulses from the clock output of the generator 1 pass through the element I2 to the input of the switch 10, as a result, a pulse appears at the second output of the switch 10, which is fed to the input of the circuit, a graph dialed from the elements I6. If in this implementation the graph is connected, then the pulse passes to the output of the graph circuit to which the single input of the trigger 11 is connected, set it to one. If the graph is not connected, then there will be no pulse at the output of the circuit, and trigger 11 will remain in the zero state. A pulse then appearing at the third output of the switch 10 polls the state of the bits of the shift register 9, and depending on

от установленного в единицу разр да по вл етс импульс на выходе k-го элемента И второй группы элементов И12, поступа на счетный вход J(-го счетчика первой группы элементов И14 Если триггер 11 установлен в единицу , то импульс поступает на счетный вход k -го счетчика второй группы счетчиков 15. Затем цикл работы устройства повтор етс .a pulse at the output of the k-th element And the second group of elements I12, arriving at the counting input J (th counter of the first group of elements I14, appears from the unit one, if trigger 11 is set to one, then the pulse goes to the counting input k - first counter of the second group of counters 15. Then the operation cycle of the device is repeated.

Таким образом, по окончании процесса статистических испытаний ,в счетчиках 13 ,. .., 1 3 .,.. ., 13 Thus, at the end of the process of statistical tests, in the counters 13,. .., 1 3., ...., 13

подсчитьшаютс реализации вьшавшие с 1п ,..., i , ..., 1 разомкнутыми ребрами м, а в счетчиках 15 ,..., 15,,.. ...,15 только те из них, при которых граф св зан riycni Оценка веро тности получаетс из частного .the implementations that entered from 1n, ..., i, ..., 1 are open edges m, and in counters 15, ..., 15 ,, .. ..., 15, only those of which the graph is associated are counted riycni The likelihood estimate is derived from the quotient.

YcTpojiCTBo дл статистического моделировани веро тностного графа легко расшир етс при увеличении количества звеньев моделируемой системы путем добавлени разр дов регистров сдвига, элементов И и счетчиков .YcTpojiCTBo for statistical modeling of a probabilistic graph is easily expanded with an increase in the number of links of the simulated system by adding bits of shift registers, AND elements and counters.

cpue.fcpue.f

Claims

. DEVICE FOR SIMULATING A PROBABLE GRAPH, containing a random number generator, a switch, a first, second and third group of AND elements, a first and second group of counters, first inputs and outputs of an AND element of the first group are respectively a group of information inputs and a group of information outputs of the device, the first output of the switch is the control output of the device, the outputs of the elements And the second group are connected to the inputs of the counters of the first group, characterized in that, in order to reduce hardware costs; an rn-bit shift register (m is the maximum number of edges of the simulated graphs), a (m + 1) -digit shift register, a trigger, three AND elements, a delay element and a NOT element are entered into the device, the second output of the switch connected to the unit inputs of the first bits, zero input inputs of 2,3, ... bits of the m-bit shift register, 2,3, ..., ..., (m + 1) bits of the (m + 1) -digit shift register and zero trigger input, generator clock output random numbers connected to the first inputs of AND elements, the stochastic output of the random number generator is connected to the second input of the second AND element and with the information input of the (th + 1) -digit shift register, the outputs of which, in addition to the (t + 1) th, are connected to the second inputs of the And elements of the first group, (t + 1) -th output (t +1) ~ of the bit shift register is connected through the delay element to the second input of the first element AND and the input of the element NOT, the output of which is connected to the third input of the second element And and the second input of the third element And, the outputs of which are connected respectively to the shift inputs of the first-digit and ( th + 1) -bit shift registers, the output of the first element And connected to the input of the switch, the third output of which is connected to the first inputs of the AND elements of the second group, the second inputs of which are connected to the outputs of the m-bit shift register, and the outputs are connected to the first inputs of the AND elements of the third group, whose outputs are connected to the inputs of the counters of the second group , and the second inputs are combined and connected to the output of the trigger, a single input of which is the control input of the device.