Устройство для моделирования случайного выбора элементов множества

 

"С А:Н И

ОП И,Е

ИЗОБРЕТЕНИЯ

<111 4774I5

Союз Советских

Социалистических

- Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 31.05.73 (21) 1923118/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 15.07.75. Бюллетень № 26

Дата опубликования описания 15.10.75 (51) M. Кл. G 061 15/20

Государственный комитет

Совета Министров СССР (53) УДК 681.325(088.8) по делам изобретении и открытий (72) Авторы изобретения

В. И. Зайков, Е. Н. Митичкин и А. Н. Свердлик (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЛУЧАЙНОГО

ВЫБОРА ЭЛЕМЕНТОВ МНОЖЕСТВА

Изобретение относится к области вычислительной техники.

Известны устройства для моделирования случайного выбора элементов множества, содержащие блок управления, входы которого подключены ко входам пуска и опроса устройства, первый выход соединен с первым входом счетчика, второй, третий и четвертый выходы соединены с управляющими входами первого, второго и третьего блоков передачи кода соответственно, а пятый выход соединен с управляющим входом сумматора и вторым входом счетчика, выходы которого через первый блок передачи кода соединены с информационными входами сумматора, выходы которого через дешифратор соединены с информационными входами второго и третьего блоков передачи кода, а выходы третьего блока передачи кода соединены с выходами устройства.

Все известные устройства не обеспечивают случайного выбора элементов множества без повторений.

iB предложенном устройстве указанный недостаток исключен.

Устройство отличается от известных тем, что оно содержит блок памяти, управляющий вход которого подключен к пятому выходу блока управления, а информационные входы подключены к соответствующим выходам третьего блока передачи кода, и блок сигналов приращения, входы которого подключены к соответствующим выходам блока памяти и второго блока передачи кода, а выход соединен с третьим входом счетчика.

Блок-схема устройства для моделирования случайного выбора элементов множества приведена на фиг. 1.

Устройство содержит блок управления 1, счетчик 2, сумматор 3, блок памяти 4, дешифратор 5, блок 6 сигналов приращения и блоки

7 — 9 передачи кода. На фиг. 2 приведена функциональная схема блока сигналов приращения. Блок 6 сигналов приращения содержит элементы «ИЛИ» 10> — 10,, и 11, элементы «И»

l2> — 12„,, выход 13, первую группу входов 14 от блока памяти 4 и вторую группу входов 15 от блока 8 передачи кода.

Устройство работает следующим образом.

Входными сигналами устройства являются сигнал пуска с1, которым устройство включается в работу, и сигнал опроса се. Номер выбранного элемента выдается в виде возбуждения одного из 2" выходов устройства во время

25 опроса.

Одновременно с выдачей выбранного номера элемента осуществляется его запоминание в блоке памяти 4. Блок памяти представляет собой объединение 2" одноразрядных элементов

30 памяти. Запоминание номера осуществляется

477415 переходом в единичное состояние соответствующего возбужденной шине элемента памяти блока памяти 4. Для этой цели входы блока памяти соединены с выходами устройства.

Формирование номера элемента множества происходит на сумматоре 3 путем суммирования по модулю 2 " номера предыдущего элемента множества с приращением очередного номера, формируемого на счетчике 2. Для передачи содержимого счетчика 2 в сумматор 3 выходы счетчика 2 через блок 7 передачи кода подключены ко входам сумматора 3.

Дешифрирование номера элемента осуществляется дешифратором 5, для чего его входы подключены к выходам сумматора 3.

Выходы дешифратора 5 подключены через блок 9 передачи кода к выходам устройства и через блок 8 передачи кода — ко входам блока 6 сигналов приращения. Другая группа входных шин блока сигналов приращения подключена к выходам блока памяти 4.

Блок 6 сигналов приращения под воздействием входных сигналов вырабатывает последовательность импульсов, число которых равно числу ранее выбранных номеров, непосредственно следующих за номером возбужденного выхода дешифратора 5. Например, если возбужден выход с номером i и среди старших номеров ближайший невыбранный номер i+2, то блок 6 сигналов приращения вырабатывает последовательность, состоящую из (k — 1) импульсов. Эта последовательность поступает на вход счетчика 2 и подсчитывается.

Согласованная работа блока устройства обеспечивается сигналами с2, с, с4, с5 и с, вырабатываемыми блоком управления 1. Сигнал с переводит в нулевое состояние счетчик 2, сумматор 3 и блок памяти 4. Сигнал сз осуществляет передачу содержимого счетчика 2 через блок 7 передачи кода на вход сумматора 3. Сигнал с4 поступает на счетчик 2 и переводит все его разряды, кроме младшего, в нулевое состояние, а младший разряд устанавливает в единичное состояние. Сигнал с осуществляет передачу сигнала возбужденного выхода дешифратора 5 через блок 8 передачи кода на вход блока 6 сигналов приращения. Сигнал с обеспечивает передачу сигнала возбужденного выхода дешифратора 5 через блок 9 передачи кода на выход устройства.

На вход устройства поступает сигнал пуска сп которым включается в работу блок управления 1. Блок управления вырабатывает сигнал с, которым переводятся в нулевое состояние счетчик 2, сумматор 3 и блок памяти 4.

Возбуждается первый выход дешифратора 5, соответствующий нулевому содержимому сумматора 3.

Так как все элементы памяти 4 находятся в нулевом состоянии, то сигналы на всех его выходах отсутствуют, вследствие чего все элементы «И» 12 — 12, блока 6 сигналов приращения закрыты.

10 г

После приведения устройства в исходное состояние блоком управления 1 вырабатывается сигнал сз. Источником сигнала с является генератор случайных сигналов (на чертеже не показан), который входит в состав блока управлсния 1.

Сигналом с> содержимое счетчика 2 прибавляется к содержимому сумматора 3. Так как их содержимое равно нулю, то состояние сумматора 3 не изменяется, и не изменяется номер возбужденного выхода дешифратора 5. Пересылка содержимого счетчика 2 на вход сумматора 3 осуществляется через блок 7 передачи кода.

После сигнала сз вырабатывается сигнал с4, которым на счетчике 2 устанавливается единичное приращение.

После сигнала с4 вырабатывается сигнал сь, которым сигнал с первого возбужденного выхода дешифратора 5 через блок 8 передачи кода передается на вход элемента «ИЛИ» 10 блока 6 сигналов приращения. Сигнал с выхода элемента «ИЛИ» 10 поступает на закрытый элемент «И» 12 и дальше не проходит.

B результате, на выходе блока 6 сигналов приращения импульсы отсутствуют и, следовательно, содержимое счетчика 2 не меняется.

Таким образом, после выработки первой последовательности сигналов сз, с4 и с содержимое сумматора 3 будет равно нулю, на выходе дешифратора 5 будет возбужден первый выход, содержимое счетчика 2 будет равно единице. После выработки блоком управления 1 второй последовательности этих сигналов содержимое сумматора 3 станет равным единице, будет возбужден второй выход дешифратора 5, а содержимое счетчика 2 останется равным единице. После выдачи третьей последовательности сигналов с, с4 и с содержимое сумматора 3 станет равным двум, будет возбужден третий выход дешифратора 5, а содержимое счетчика 2 по-прежнему останется ран пым единице и т. д.

Итак, сигналами сз, с4, с, вырабатываемы. ми блоком управления 1, осуществляется последовательный перебор выходов дешифрато-. ра 5. На сумматоре 3 выполняется суммирование по модулю 2", поэтому после выбора выхода с номером 2" следующим будет выбран первый выход, после чего процесс перебора выходов повторится. В таком режиме устройство работает до поступления в него сигнала опроса с .

После прихода сигнала опроса блок управления 1 прекращает вырабатывать сигналы с, с и с и по истечении времени окончания переходных процессов в дешифраторе 5, вызванных формированием текущего номера элемента, вырабатывает сигнал ñ . Этот сигнал поступает в блок 9 передачи кода и осуществляет выдачу сигнала возбужденного выхода дешифратора 5 на выход устройства в виде возбуждения одного из 2 выходов. 3а счет связи входов блока памяти 4 с выходами устройства осуществляется одновременно с выдачей зап0477415

I0

60 б5 минания номера возбужденного выхода в блок памяти 4. По окончании опроса в блоке управления 1 возобновляется выработка сигналов с3, с4, с5 и, следовательно, возобновляется процесс перебора выходов.

Пусть к моменту опроса возбужден второй выход дешифратора 5. В таком случае по сигналу с7 будет возбужден второй выход и будет переведен в единичное состояние элемент памяти, соответствующий второму выходу блока памяти 4. Вследствие этого на втором выходе блока памяти возникает сигнал, который поступает на вход элемснта «И» 12> блока 6 сигналов приращения. По окончании опроса процесс последовательного перебора выходов дсшифратора 5 возобновляется.

После возбуждения первого выхода дешифратора 5 (содержимое сумматора 3 равно нулю) сигналом с сигнал первого возбужденного выхода будет передан на вход элемента

«ИЛИ» 10> блока 6 сигналов приращения.

С выхода этого элемента сигнал поступает на вход элемента «И» 12>. Так как на втором входе элемента «И» 12> также присутствует сигнал, то на его выходе возникает сигнал, который поступает на элементы «ИЛИ» 10 и 11.

Сигнал с выхода элемента «ИЛИ» 10> поступает на вход закрытого элемента «И» 12> и дальше не проходит. Сигнал с выхода элемента «ИЛИ» 11 поступает на вход счетчика 2 и увеличивает его содержимое на единицу. Следовательно, приращение для формирования номера очередного выхода дешифратора 5 станет равным двум.

Очередным сигналом сз содержимое счетчика 2 добавляется к содержимому сумматора 3.

Результат суммирования станет равным двум, и будет избран третий выход дешифратора 5, а второй выход будет исключен. Дальнейший процесс возбуждения выходов ничем не отличается от вышеописанного. При этом после возбуждения первого выхода вновь будут возбуждаться последовательно выходы с номерами3,4, ... 2", 1.

Пусть теперь опрос производится в момент возбуждения первого выхода дешифратора 5.

По сигналу с7 будет возбужден первый выход и будет переведен в единичное состояние элемент памяти, соответствующий первому выходу блока памяти 4. Вследствие этого на первом выходе блока памяти 4 возникает сигнал, который поступает на вход элемента «И» 12 блока 6 сигналов приращения. По окончании опроса продолжится перебор выходов 3, 4, ...

2" дешифратора 5 аналогично тому, как это было описано ранее.

После возбуждения выхода 2" дешифратора 5 (содержимое сумматора 3 равно 2" — 1) сигнал возбужденного выхода по сигналу с„будет гн редан па вход элеме та «ИЛИ» 10 „ блока 6 сигналов приращения. С выхода этого элемента сигнал поступает на вход элемента

«И» 12ь Так как на втором входе элемента «И»

121 также прнсутствует сигнал, то íà etn n . ходе возникает сигнал, который поступает на элементы «ИЛИ» 101 и 11. Сигнал с выхода элемента «ИЛИ» 11 поступает на вход счетчика 2 и увеличивает его содержимое на единицу. Сигнал с выхода элемента «ИЛИ» 10 поступает на вход элемента «И» 12>, который открыт по второму входу сигналом со второго выхода блока памяти 4. Сигнал с выхода элемента «И» 12 поступает на входы элементов

«ИЛИ» 10. п 11. Элемент «ИЛИ» 101 и элемент «И» 12 обеспечивают задержку сигнала на время окончания переходных процессов в младшем разряде счетчика, поэтому выходным сигналом элемента «ИЛИ» 11 содержимое счетчика 2 еще раз будет увеличено на единицу. Сигнал с выхода элемента «ИЛИ» 10 поступает на вход закрытого элемента «И» 12> и дальше не проходит. Таким образом, для формирования очередного номера на счетчике 2 будет сформировано приращение, равное трем.

Очередным сигналом сз содержимое счетчика 2 добавляется к содержимому сумматора 3.

В результате суммирования возбуждается третий выход дешифратора 5, а первый и второй пропускаются. Далее процесс перебора выходов 3, 4, ..., 2" продолжается до поступления следующего сигнала опроса.

Для того, чтобы выборы элементов множества в каждом случае были равновероятными и независимыми, сигналы опроса должны поступать через промежутки времени Т. Период следования Т определяется соотношением

Т (2 —:3).2" />. где Х вЂ” интенсивность импульсов генератора . случайных сигналов блока управления 1.

В свою очередь, интенсивность Х должна удовлетворять условию где т — время формирования максимального приращения на счетчике 2.

Последовательность сигналов с, с, с вырабатывается блоком управления 1 после окончания формирования на счетчике 2 приращения очередного номера. С этой целью в блоке управления 1 из случайной последовательности импульсов генератора случайных сигналов выделяются только те, которые отстоят друг от друга на время, не меньше т. Выделенные импульсы являются источниками формирования последовательности сигналов с, с4» С5.

Предмет изобретения

Устройство для моделирования случайного выбора элементов множества, содержащее блок управления, входы которого подключены

Ко входам пуска и опроса устройства, первый вы.ход соединен с первым входом счетчика, второй, третий и четвертый выходы соединены с управляющими входами первого, второго и третьего блоков передачи кода соответственно, а пятый выход соединен с управляющим вхо477415 дом сумматора и вторым входом счетчика, выходы которого через первый блок передачи кода соединены с информационными входами сумматора, выходы которого через дешифратор соединены с информационными входами второго и третьего блоков передачи кода, а выходы третьего блока передачи кода соединены с выходами устройства, о т л и ч а ющ е е с я тем, что, с целью расширения области применения, оно содержит блок памяти, управляющий вход которого подключен к пятому выходу блока управления, а информационные входы подключены к соответствующим

5 выходам третьего блока передачи кода, и блок сигналов приращения, входы которого подключены к соответствующим выходам блока памяти и второго блока передачи кода, а выход соединен с третьим входом счетчика, 477415

Составитель Г. Сорокин

Техред М. Семенов

Корректор Л. Котова

Редактор Б. Нанкина

Типография, пр. Сапунова, 2

Заказ 2498/12 Изд. № 1591 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, )К-35, Раушская наб., д. 4/5