Устройство для случайного перебора перестановок Советский патент 1991 года по МПК G06F7/58 

(21)4677694/24

(22)11.04.89

(46) 23.04.91. Вил. 1 15

(72) К.М.Абдрашитов и А.А.Гармонов

(53)681.31(088.8)

(56)Авторское свидетельство СССР р 1269128, кл. G 06 F 7/58, 1985.

(54)УСТРОЙСТВО ДЛЯ СЛУЧАЙНОГО ПЕРЕВОРА ПЕРЕСТАНОВОК

(57)Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение точности выравнивания вероятностей и декорреляции перестановок. Устройство содержит группы блоков элементов ЗАПРЕТ 5, 7, группы блоков элементов И 4, 11, группы блоков элементов ИЛИ 6, 12, элемент ИЛИ 10, группу регистров 9 памяти, генератор 1 тактовых импульсов, генератор 2 случайного кода и дешифратор 3. Каждая последующая перестановка получается из предыдущей путем циклического сдвига по двум циклам одновременно. При этом вся совокупность регистров информации случайным образом разбивается на две группы. 1 ил.

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

Целью изобретения является повышение точности выравнивания вероятностей и декорреляции перестановок.

На чертеже приведена структурная схема устройства для шести переставляемых элементов.

Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайного кода, дешифратор 3, группу блоков элементов И 4 - 4g( группы блоков элементов ЗАПРЕТ 5 - 56, группу блоков элементов ИЛИ 6 - 65,группу блоков элементов ЗАПРЕТ 7 - 7f, выходы элементов перестановок 8 - 86 устройства, группу регистров 9, - 96 памяти, элемент ИЛИ 10, группу блоков элементов И 11 - 11 $-, группу блоков элементов ИЛИ 12 1 - 12§-.

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

Пусть в позициях 1-6 зафиксирована следующая последовательность двоичных кодов: 1, 2, 3, 4, 5, 6.

.Случайным образом выбирается номер k циклического сдвига (например,

1 номер k 3).Это приводит к сдвигу двоичных кодов из третьей позиции в четвертую, из четвертой в пятую, из пятой в шестую, из шестой в третью,

tОдновременно это приводит к сдвигу двоичных кодов из первой позиции во вторую, из второй в первую.

В результате в позициях 1-6 будет зафиксирована следующая последовательность двоичных кодов: 2, 1, 6, 3, 4, 5.

При k 5 происходит циклический сдвиг двоичных кодов из пятой позиции в шестую, из шестой в пятую и одновременно из первой во вторую, из второй в третью, из третьей в чет-

вертую, из четвертой в первую.

с&

и

4Ь

оо J

В результате п позициях 1-6 будет зафиксирована следующая последовательность двоичных кодов: 3f 2, 1, 6, 5, 4.

При k 6 в позициях 1-6-будет заЛиксирована следующая последовательность двоичных кодов: 5, 3, 2, 1, 6, 4.

При k 2 позициях 1-6 будет за- фиксирована следующая последовательность: 5, 4, 3, 2, 1, 6.

При k 1 в позициях 1-6 будет зафиксирована следующая последовательность: 6,5,4,3,2,1.

В исходном состоянии в регистры 9 - 9( записываются двоичные коды чисел 1-6 соответственно. Формируемый генератором 2 случайный двоичный код преобразуется дешифратором 3 в случайный унитарный код. Предположим, что этот единичный сигнал появился на третьем выходе дешифратора (k 3) . Этот единичный сигнал попадает на первый вход элемента И 4 $ и закрывает элемент ЗАПРЕТ 5 и 7. Этот единичный сигнал через элемент ИЛИ 10 одновременно поступает на первый вход элемента И 4,) и, поступая на синхронизирующие входы регистров па- мяти 9, - 9,, вызывает сдвиг содержимого регистров: из 9, в 92, из 9g в 9, из 93 в 94, из 94 в 9,из 9S в 9б,ия 9б в Уд. В результате на выходах 8 , - Bg устройства получают следующую последовательность двоичных кодов: 2, 1, 6, 3, 4, 5.

Далее предположим, что следующий . единичньй сигнал появился на втор-ом выходе дешифратора (k 2). Этот единичный сигнал поступает на второй вход элемента И 114 и первый вход элемента И 42, он же закрывает элементы ЗАПРЕТ 7 и 5 р поступая на их инверсные входы. Через элемент ИЛИ 10 этот же сигнал появляется на первом входе элемента И 4 и на синхрони- зирующих входах регистров памяти 9 - 9g, вызывая сдвиг содержимого регистров из 9г в 9з, из 9 в 9$, из 9Г в Уу, из 9 в 96, из 9Ј з 9.. Через элементы И 11, , ИЛИ 12,,, И 4, информация с выхода регистра 9 перезаписывается в него же и поступает на выход 8 . В результате на выходах 8,, - 8g получают следующую последовательность двоичных кодов: 2, 5, 1, 6, 3, 4. .

Далее допустим, что следующий единичный сигнал появился на шестом выходе дешифратора (k 6). Этот единичный сигнал закрывает элементы ЗАПРЕТ 7 g- и 5у, поступает на первый вход элемента И 46, через элемент ИЛИ 10 этот же единичный сигнал поступает на первый вход элемента И 4 на синхронизирующие входы регистров памяти Ч - 9g, вызывая сдвиг содержимого регистров из 9 в9а,из 91 в Uj , ия 9 з ., из 9$ в 9, из 9$- в 9. Через элементы И 4, ИЛИ бд- информация с выхода регистра 9g перезаписывается в него же и поступает на выход 8g. В результате на выходах 8{ - 8g получают следующую последовательность двоичных кодов: 3, 2, 5, 1, 6, 4.

Пусть следующий единичньй сигнал появился на первом выходе дешифратора (k 1). Этот сигнал поступает на первый вход элемента И 4 и синхронизирующие входы регистров памяти 94 - 9g, вызывая сдвиг содержимого регистров из 9 в 9, из 92 в 9, из 9 j в 94-, из 9 в 9, из 9g- - 9б, из 9б в 9. Так как при этом открыты элементы ЗАПРЕТ и 5 ц - 5у, закрыты элементы И 1 1 ,, - 11 Ј- и элементы И 4б, то открывается только элемент И 4 т. В результате на выходах устройства получают следующую последовательность двоичных кодов: 4, 3, 2, 5, 1, 6.

В устройстве каждая последующая перестановка получается из предыдущей путем циклического сдвига информации вправо по двум циклам одновременно. Вся совокупность регистров информации случайным образом разбивается на две группы. В группе регистров памяти с k-ro по n-й регист происходит циклический сдвиг информации и одновременно в группе регистров памяти с 1-го по (k-O-й регистр происходит также циклический сдвиг информации. При этом число k выбирается случайно и вероятности изменения содержимого всех регистров выравниваются. Поэтому устройство улучшает качество случайного перебора перестановок за счет выравнивания вероятностей изменения содержимого всех разрядов устройства и одновременного уменьшения корреляционных связей.

Лор мула изобретения

Устройство для случайного перебора перестановок, содержащее генератор тактовых импульсов, дешифратор, генератор случайного кода, первую группу блоков элементов И, первую группу блоков элементов ЗАПРЕТ, две группы блоков элементов ИЛИ, группу регистров памяти, причем выход генератора тактовых импульсов соединен с тактовым входом генератора случайного кода, выход которого соедивой группы и с i-м выходом дешифратора, отличающееся тем, что, с целью повышения точности выравнивания вероятностей и декорреляции перестановок, в него дополнительно введена вторая группа блоков элементов И, вторая группа блоков элементов ЗАПРЕТ и элемент ИЛИ, причем выходы дешиф- }д ратора соединены с соответствующими входами элемента ИЛИ, выход которого соединен с первым входом первого блока элементов И первой группы и синхронизирующими входами регистров группы,

нен с входом дешифратора, выход пер- 15 й вход дешифратора соединен с ин- вого блока элементов И первой группыверсным входом 1-го блока элементов

соединен с информационным входом пер- ЗАПРЕТ второй группы и первым входом

1-го блока элементов И второй группы, второй вход которого соединен с выхо- 20 дом 1-го регистра памяти группы, а выход - с первым входом 1-го блока элементов ИЛИ второй группы, второй вход которого соединен с. выходом 1-го

вого регистра памяти группы, выход i-го (i 1,..,п-1), где п - число элементов перестановок) регистра памяти группы соединен с прямым входом i-ro блока элементов ЗАПРЕТ первой группы и является выходом 1-го элемента перестановки устройства, выход п- го регистра памяти является выходом n-го элемента перестановки устройства, выход (1+1)-го блока элементов И первой группы соединен с первым входом 1-го блока элементов ИЛИ первой группы, выход 1-го блока элементов ИЛИ первой группы соединен с информационным входом (i-M)-ro регистра памяти группы, второй вход 1-го блока элементов ИЛИ первой группы

соединен с выходом i-ro блока элемен- 35 ГРУППЫ, вькод первого блока элементов ЗАПРЕТ первой группы, инверсный вход которого соединен с первым входом (i+O-ro блока элементов И пертов ИЛИ второй группы соединен с вторым входом первого блока элементов И первой группы.

6441376

вой группы и с i-м выходом дешифратора, отличающееся тем, что, с целью повышения точности выравнивания вероятностей и декорреляции перестановок, в него дополнительно введена вторая группа блоков элементов И, вторая группа блоков элементов ЗАПРЕТ и элемент ИЛИ, причем выходы дешиф- }д ратора соединены с соответствующими входами элемента ИЛИ, выход которого соединен с первым входом первого блока элементов И первой группы и синхронизирующими входами регистров группы,

блока элементов ЗАПРЕТ второй груп- пы, прямой вход j-го (j 1,...,n-2) блока элементов ЗАПРЕТ второй группы соединен с вторым входом (j-H)-ro блока элементов И второй группы и с выходом (j+1)-ro блока элементов ИШ1 второй группы, прямой вход (п - - 1)-го блока элементов ЗАПРЕТ второй группы соединен с вторым входом n-го блока элементов И второй группы и с выходом n-го регистра памяти

тов ИЛИ второй группы соединен с вторым входом первого блока элементов И первой группы.