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

(19 (И) 51 у 5 С 06 Р 7/ ЕННЫЙ КОМИТЕТ НИЯМ И ОТНРЫТИЯМСССР ГОСУДАРСПО ИЗОЬРЕТЕПРИ ГКНТ ПИСАНИЕ ИЗОБРЕТЕНИАВТОБУСНОМУ СВИДВТЙЛЬСТВУ одер- ЕТ 5,677694/241.04.893.04.91. Бюл. Р(54) БОРА (57) тоПел тике и изобре выравни ре п раз СТРОйстВО ДЛЯ СЛУЧАЙНОГОЕРЕСТАИОВОКзобретение относится к аввычислительной технике.тения - повышение точноствания вероятностей и дек Изобретение относится к автоматике и вычислительной технике,Пелью изобретения является повышение точности выравнивания вероятностей и декорреляции перестановок.На чертеже приведена структурнаясхема устройства для нести переставляемьи элементов.Устройство содержит генератор 1тактовых импульсов, генератор 2 случайного кода, дешифратор 3, группублоков элементов И 4- 46, группыблоков элементов ЗАЛРЕТ 5 - 5, групну блоков элементов ИЛИ 6- б,группу блоков элементов ЗАПРЕТ 7 - 7,выходы элементов перестановок 8 -8 устройства, группу регистров 996 памяти, элемент ЮП 1 10, группублоков элементов И 11 - 11, груп ублоков элементов ИЛИ 12- 12.Устройство работает следующим обляции перестановок. Устройство сжит группы блоков элементов ЗАПР7, группы блоков элементов И 4, 11,группы блоков элементов ИЛИ 6, 12,элемент ИЛИ 10, группу регистров 9памяти, генератор 1 тактовых импульсов, генератор 2 случайного кода идешифратор 3. Каждая последующая перестановка получается из предыдущейпутем циклического сдвига по двумциклам одновременно. При этом всясовокупность регистров информациислучайным образом разбивается надве группы. 1 ил .,Пусть в позициях 1-6 зафиксирована следующая последовательность дво" ичных кодов: 1, 2, 3, 4, 5, б..Случайным образом выбирается номер К циклического сдвига (например, номер 1 с = 3).Это приводит к сдвигу двоичных кодов из третьей позиции в четвертую, из четвертой в пятую, из пятой в шестую, из шестой в третью, Одновременно это приводит к сдвигу двоичных кодов из первой позиции во вторую, из второй в первую.В результате в позициях 1-6 будет зафиксирована следующая последовательность двоичных кодов: 2, 1, 6, 3, 4, 5.При Е = 5 происходит циклический сдвиг двоичных кодов из пятой позиции в шестую, из шестой в пятую и одновременно из первой во вторую, из второй в третью, из третьей в четвертую, из четвертой в первую.В результате в. позициях 1-6 будетзафиксирована следующая последовательность двоичных кодов; 3, 2, 1,6, 5, 4.5При Е = 6 в позициях 1-6 будетзафиксирована следующая последовательность двоичных кодов: 5, 3, 2, 1,6, 4.При 1 = 2 позициях 1-6 будет зафиксирована следующая последовательность: 5, 4,3, 2, 1, 6.При= 1 в позициях 1-6 будет зафиксирована следующая последовательность: 6, 5, 4, 3, 2, 1.15В исходном состоянии в регистры9 - 9 записываются двоичные кодычисел 1-6 соответственно. Формируемыйгенератором 2 случайный двоичныйкод преобразуется дешифратором 3 вслучайный унитарный код, Предположим,что этот единичный сигнал появилсяна третьем выходе дешифратора Ос =- 3). Этот единичный сигнал попадает на первый вход элемента И 4изакрывает элемент ЗАПРЕТ 5 и 7,Этот единичный сигнал через элементИЛИ 10 одновременно поступает на первый вход элемента И 4 1 и, поступая насинхронизирующие входы регистров памяти 9 1 - 9 , вызывает сдвиг содержибфмого регистров: из 9 в 9, из 9 в91, из 9 в 9 из 94 в 9,иэ 9 в9,из 9 в 9. В результате на выходах 8- 8 устройства получают следующую последовательность двоичныхкодов: 2, 1, 6, 3, 4, 5,Далее предположим, что следующий. единичный сигнал появился на втором 40выходе дешифратора ( = 2). Этот единичный сигнал поступает на второйвход элемента И 11 и первый входэлемента И 4, он яе закрывает элементы ЗАПРЕТ 7 и 5поступая на их 45инверсные входы. Через элемент ИЛИ 10этот яе сигнал появляется на первомвходе элемента И 4 и на синхронизирующих входах регистров памяти9- 9, вызывая сдвиг содержимогорегистров из 9 в 9, из 9в 94;,из 9 в 9, из 9 в 9, из 9 в 9,Через элементы П 11, ИЛИ 12 , И 4информация с выхода регистра 91 переэаписывается в него же и поступает55на выход 81. В результате на выходах8 - 8 получают следующую после 1довательность двоичных кодов: 2, 5,1,6,3,4,Далее допустим, что следующий единичный сигнал появился на шестом выходе дещифратора Ь = 6). Этот единичный сигнал закрывает элементы ЗА -ПРЕТ 7 -и 5, поступает на первыйвход элемента И 46, через элементИЛИ 10 этот же единичный сигнал по"ступает на первый вход элемента И 4на синхронизирующие входы регистровпамят 91 - 9, вызывая сдвиг содержимого регистров из 9 в 9,из 9,вЪ,из 9в, 94., из 94 в 9, из9 в 91. Через элементы И 4, ИЛИ6 информация с выхода регистра 9перезаписывается в него же и поступает на выход 8. В результате навыходах 81 - 8 получают следующуюпоследовательность двоичных кодов:3, 2, 5, 1, 6, 4.Пусть следующий единичный сигналпоявился на первом выходе дешифратора Ь = 1). Этот сигнал поступаетна первый вход элемента И 41 и синхронизирующие входы регистров памяти 9 - 9, вызывая сдвиг содержимого регистров из 9 1 в 9, из 9в 9, из 9 в 94., из 9 в 9-, из9 - 9 б, из 96 в 91. Так как приэтом открыты элементы ЗАПРЕТ 7 - 7и 5- 5, закрыты элементы И 1111 - и элементы И 4 - 46, то открывается только элемент И 4 В результате на выходах 8- 8 устройства получают следующую последовательность двоичных кодов: 4, 3, 2,5,1,6,В устройстве каждая последующаяперестановка получается из предыдущей путем циклического сдвига информации вправо по двум циклам одновременно. Вся совокупность регистровинформации случайным образом разбивается на две группы, В группе регистров памяти с 1-го по и-й регистрпроисходит циклический сдвиг информации и одновременно в группе регистров памяти с 1-го по %-1)-й регистр происходит также циклическийсдвиг информации, При этом число 1выбирается случайно и вероятности изменения содержимого всех регистроввыравниваются, Поэтому устройствоулучшает качество случайного перебора перестановок за счет выравниваниявероятностей изменения содержимоговсех разрядов устройства и одновременного уменьшения корреляционныхсвязей,516441 формула изобретения Устройство для случайного перебора перестановок, содержащее генератор тактовых импульсов, дешифратор, генератор случайного кода, первую группу блоков элементов И, первую группу блоков элементов ЗАПРЕТ, две группы блоков элементов ИЛИ, группу 10 регистров памяти, причем выход генератора тактовых импульсов соединен с тактовым входом генератора случайного кода, выход которого соединен с входом дешиФратора, выход пер вого блока элементов И первой группы соединен с инАормационным входом первого регистра памяти группы, выход -го ( = 1,п), где 4 - число элементов перестановок) регистра памяти группы соединен с прямым входом х-го блока элементов ЗАПРЕТ первой группы и является выходом -го элемента перестановки устройства, выход иго регистра памяти является выходом 25 и-го элемента перестановки устройства, вьиод (х+1)-го блока элементов И первой группы соединен с первым входом -го блока элементов ИЛИ первой группы, вьиод д-го блока элемен- ЗО тов ИЛИ первой группы соединен с информационным входом Я+1)-го регистра памяти группы, второй вход х-го блока элементовИЛИ первой группы соединен с выходом х-го блока элементов ЗАПРЕТ первой группы, инверсный вход которого соединен с первым входом Я+1)-го блока элементов И пер 37 6вой группы и с 1-м выходом дешиФратора, о т л и ч а ю щ е е с я тем, что,с целью повышения точности выравнивания вероятностей и декорреляции перестановок, в него дополнительно вве 4дена вторая группа блоков элементов И,вторая группа блоков элементов ЗАПРЕТи элемент ИЛИ, причем выходы дешифратора соединены с соответствующимивходами элемента ИЛИ, выход которогосоединен с первым входом первого блока элементов И первой группы и синхрониэирующими входами регистров группы,ь-й вход деширатора соединен с инуверсным входом д-го блока элементовЗАПРЕТ второй группы и первым входом1"го блока элементов И второй группы,второй вход которого соединен с выходом -го регистра памяти группы, авыход - с первым входом ь-го блокаэлементов ИЛИ второй группы, второйвход которого соединен с выходом х-гоблока элементов ЗАПРЕТ второй группы, прямой вход 1-го Ц = 1п)блока элементов ЗАПРЕТ второй группысоединен с вторым входом Я+1)-гоблока элементов И второй группы ис выходом Ц+1)-го блока элементовЦ 1 И второй группы, прямой вход (и -1)-го блока элементов ЗАПРЕТ второй группы соединен с вторым входоми-го блока элементов И второй группыи с выходом и-го регистра памятигруппы, выход первого блока элементов ИЛИ второй группы соединен свторым входом первого блока элементов И первой группы,1644 137 орректор П.Ревская Редактор Т.Иванова Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 Заказ 1462ВНИИПИ Госуда С ос тавител ъ В. Орлов Техред Д.Сердюкова Тираж 400 Птвенного комитета по изобретения 113035) Иосква, Ж, Раушская одписное м и открытиям при ГКНТ СССР наб., д, 4/5