Устройство для случайного перебора перестановок

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 504 С 06 Г 7/58 рого ству ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.М. Глушань, М.И. Пупков и Л.И. Щербаков(56) Авторское свидетельство СССР У 922737, кл. С 06 Р 7/58, 1980.Авторское свидетельство СССР 9 997036, кл. С Об Г 7/58, 1981.Авторское свидетельство СССР В 1101820, кл. С 06 Р 7/58, 1982. (54) УСТРОЙСТВО ДЛЯ СЛУЧАЙНОГО ПЕРЕБОРА ПЕРЕСТАНОВОК(57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей устройства. Оно содержит генератор тактовых импульсов, генератор случайного кода, дешифратор, первый и второй блоки элементов ИЛИ, блок элементов "ЗАПРЕТ", блок элементов И, блок регистров, информационные входы которых, кроме первого и ш-го регистров, соединены с выходами соответствующих элементов ИЛИ первого блока. Первые входы элементов ИЛИ соединены с выходами соответствующих элементов И, а вторве входы - с выходами соответствующих элементов ЗАПРЕТ. Неинвертированные входы элементов ЗАПРЕТ соединены с информационными входами соответствующих регистров, а инверсные входы - с первыми входами элементов ИЛИ втоблока, первыми входами соответющих элементов И и соответствующими выходами дешифратора. Синхрони 801269128 зирующие входы регистров соединены с выходами соответствующих элементов ИЛИ второго блока и вторыми входами элементов ИЛИ второго блока последующих разрядов, Информационные входы первого регистра соединены с выходами первого элемента И, а информационные входы ш-го регистра - с выходами предыдущего регистра. Выход ш - го регистра соединен с вторыми входами элементов И. Синхронизирующий вход ш-го регистра соединен с вторым входом первого элемента, ИЛИ второго блока, первым входом первого элемента И и первым выходом дешифратора. Выходы ре- д гистров являются информационными выходами устройства. Предлагаемое устройство представляет собой, практически, однородную структуру, так как С все разряды строятся по одному и тому же принципу, Если возникает необходимость увеличить число элементов н а случайных перестановках (сочетаниях), Я то необходимо добавить соответствую- р щее число разрядов. Каждый разряд содержит регистр, элемент И, элемент ЗАПРЕТ, элементы ИЛИ первого и вто пей рого блока. Число разрядов в регист- К) ре должно быть равно, Устройство поз- ЯО воляет получать случайные перестановки кодов и случайные сочетания кодов. При этом. степень корреляции будет не хуже, так как в самом плохом случае за один такт генератора тактовыхимпульсов обмен происходит между и-м и (т)-м регистрами. В среднем же при равновероятном законе появления сигналов на выходе дешифратора обмен кодами происходит между ш/2 регистрами. 1 ил.1269128 1 2 3 4 30 35 40 45 50 Изобретение относится к автомати ке и вычислительной технике и может быть использовано для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры.Цель изобретения - расширениефункциональных возможностей генератора за счет обеспечения воэможности получения сочетаний. 1 ОНа чертеже приведена структурная схема устройства для случайного перебора перестановок для шести переставляемых элементов.Устройство содержит генератор 1 15 тактовых импульсов, генератор 2 случайного кода, дешифратор 3, блоки элементов И 4, -4 , блоки элементов ЗАПРЕТ 5, - 5 блоки элементов ИЛИ 6, - 6 , блоки элементов ИЛИ 7, -7, 20 информационные выходы 8, -8 устройства,группу регистров 9, -96 памяти,В предлагаемом устройстве каждая последующая перестановка получается иэ предыдущей путем циклического сдвига информации иэ предыдущего регистра в последующий по разным циклам, выбираемым случайным образом. Рассмотрим этот принцип на примере шести переставляемых элементов. Пронумеруем позиции 1 - 6 слева направо и запишем в них двоичные коды переставляемых элементов, например 1 - 6 соответственно, причем код с шестой позиции может попасть на любую другую позицию, кроме шестой, а коды со всех предыдущих позиций могут сдвигаться в соседние справа. Обозначим циклический сдвиг кодов с шестой позиции в пятую, из пятой в шестую - номер 1, циклический сдвиг кодов из шестой позиции в четвертую, из четвертой в пятую, из пятой в шестую - номер 2, циклический сдвиг кодов иэ шестой позиции в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую номер 3, циклический сдвиг кодов из шестой позиции во вторую, иэ второй в третью, из третьей в четвертую, из четвертой в пятую, из Пятой в шестуюномер 4, циклический сдвиг кодов из шестой позиции в первую, из первой позиции во вторую, из второй в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую - номер 5. 1 - 2-3-4 5 6 В позициях 1 - б будет зафиксирована такая последовательность двоичных кодов: 1 2 3 4 5 Ь. Случайным образом выбирается номер циклического сдвига (например, номер четыре), это приводит к сдвигу двоичных кодов иэ шестой позиции во вторую, из второй в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую одновременно ГТ(-Д 2 31-45 ) - Д 6 В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: 1 6 2 3 4 5,Если сигнал случайного циклического сдвига выпадет на номер 2, то это приведет к сдвигу двоичных кодов из шестой позиции в четвертую, из четверток в пятую, из пятой в шестую одновременно- 2 - 1 1 6 2-3 - 4- 5В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: 1 6 2 5 3 4. Если сигнал случайного циклического сдвига выпадет на номер 5, то это приведет к сдвигу двоичных кодов из шестой позиции в первую, из первой во вторую, из второй в третью, иэ третьей в четвертую иэ четвертой в пятую, из пятой в шестую3 1269128 45Формула изобретения1 2 3 4 5 6 Я Д 6.Д 2. 5=3 Д 4 В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: 1 О 4 1 6 2 5 3. дом первого блока элементов И группыи с первым выходом дешифратора Устройство работает в трех режимах:получения случайных перестановок двоичных кодов;случайных сочетаний двоичных кодов;получения случайных сочетаний, когда на в позициях расположены "1",а на (в-и) позициях "О".Рассмотрим работу устройства в режиме получения случайных перестановок двоичных кодов в течение одного20такта. В исходном состоянии в регистры 9, - 9. записываются двоичные коды чисел 1 - 6 соответственно. Формируемый генератором 2 случайный двоичный код преобразуется дешифратором 3 в случайный унитарный код (случайным является норме внхопа дешифратора с единичным сигналом), который подается на первые входы элементов И 4, -4 .Предположим, что этот единичный сигнал попадает на первый вход элемента И 4. Этот сигнал закрывает элемент 5, запрета и, пройдя через элементы ИЛИ 7 -7 второго блока, вызывает сдвиг содержимого регистров; из 9 - в 9, из 9 - в 9,из 9 - 35 в 9, из 9- в 9 . В результате на выходах 8 - 8 устройства получают такую последовательность двоичных кодов: 1, 2, 6, 3, 4, 5. Устройство работает аналогично и в режиме соче таний кодов. В этом случае выходные последовательности кодов снимаются с крайних справа выходов устройства, т.е. для С " с выходов 8 и 8, для С - с выходов 8 - 8, для С - с 45 выходов 8 з б, для С - с выходов 8 - 8, для С - с выходов 8, - 8. В режиме случайных сочетаний, когда на в позициях расположены "1", а на (в-и) позициях "О", в регистры 9, -9 И записываются единицы и нули, количество которых равно в и (в-и) соответственно. Динамика работы устройства аналогична описанной. 1 строиство для случаиного перебора перестановок, содержащее дешифратор, генератор тактовых импульсов, выход11 11 которого соединен с входом Опрос генератора случайного кода, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей генератора за счет обеспечения воэможности получения сочетаний, оно содержит группу блоков элементов И, группу блцков элементов ЗАПРЕТ, две группы блоков элементов ИЛИ и группу регистров памяти, информационные входы которых, кроме первого и последнего, соединены с выходами соответствующих блоков элементов ИЛИ первой группы, первые входы которых соединены с выходами соответствующих блоков элементов И группы, - а вторые входы блоков элементов ИЛИ первой группы соединены с выходами соответствующих блоков элементов "ЗАПРЕТ" группы, прямые входы которых соединены с информационными выходами соответствующих регистров памяти группы, а инверсные входы блоков элементов "ЗАПРЕТ" группы соединены с первыми входами соответствующих блоков-элементов ИЛИ второй группы, первыми входами соответСтвующих блоков элементов И группы и с соответствующими выходами дешифратора, синхронизирующие входы регистров памяти группы, кроме первого и последнего, соединены с выходами соответствующих блоков элементов ИЛИ второй группы и вторыми входами последующих блоков элементов ИЛИ второй группы, информационный вход первого регистра памяти группы соединен с выходом первого блока элементов И группы, а информационный входпоследнего регистра памяти группысоединен с выходом предпоследнего ререгистра памяти группы, выход последнего регистра памяти группы соединенс вторыми входами блоков элементов И группы, синхронизирующий вход перФвого регистра памяти группы соединен с вторым входом второго блока элементов ИЛИ второй группы, с первым вхотавитель А. Карасовр ед Н, Глуще нк о Корректор Л. Пилипенк ак тр Заказ 6037/51 Тираж 671 ВНИИПИ Государственног по делам изобретений 113035, Москва, Ж, Раушодписно комитета СС открытий