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

 

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (1Ю (111

А1

»51)з (06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ILSTOPCNDMV СВИДаталватаи

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (?1) 4677694/24 (22) 11.04.89 (46) 23.04.91. Бюл. P- 15 (72) H.M.Àáäðàíèòîâ и А.А.Гармонов (53) 681.31(088.8) (56) Авторское свидетельство СССР

Р 12691?8, кл . С 06 F 7/58, 1985. (54) УСТРОЙСТВО ДЛЯ СЛУЧАЙНОГО ПЕРЕБОРА ПЕРЕСТАНОВОК (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — повышение точности ,выравнивания вероятностей и декорре-, Изобретение относится к автоматике и вычислительной технике.

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

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

Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайного кода, дешифратор 3, группу блоков элементов И 4 » — 4, группы блоков элементов ЗАПРЕТ 5» — 5, группу блоков элементов ИЛИ 6 » — б,группу блоков элементов ЗАПРЕТ 7» — 7, выходы элементов перестановок 8»вЂ”

8 устройства, группу регистров 9»

9 памяти, элемент KIH 10, группу блоков элементов И 11, — 11, группу блоков элементов ИЛИ 12 » — 12 .

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

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

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

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

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

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

1644137

В результате н. позициях 1-6 будет зафиксирована следующая последовательность двоичных кодов: 3, 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.

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

В исходном состоянии в регистры

9 — 9 записываются двоичные коды

» чисел 1-6 соответственно. Формируемый генератором 2 случайный двоичный код преобразуется дешифратором 3 в случайный унитарный код. Предположим, что этот единичный сигнал появился на третьем выходе дешифратора (k = — 3). Этот единичный сигнал попадает на первый вход элемента И 4 з и закрывает элемент ЗАПРЕТ 5> и 7>, Этот единичный сигнал через элемент

KIH 10 одновременно поступает на первый вход элемента И 4» и, поступая на синхронизирувщие входы регистров па- 3 мяти 9< — 9, вызывает сдвиг содержи6 мого регистров: из 9 в 9, из 9 в

9(, из 9 н 94, из 94 в 9,иэ 9 в

9,из 9 н 9g В результате на выходах 8» — 8 устройства получают следующую последовательность двоичных кодов: 2, 1, 6, 3, 4, 5, Далее предположим, что следующий . единичный сигнал появился на втором 40 выходе дешифратора (k = 2). Этот единичный сигнал поступает на второй вход элемента И 11» и первый вход элемента И 4, он яе закрынает элементы ЗАПРЕТ 7(и 5 (, поступая на их 45 инверсные входы. Через элемент HJIH 10 этот яе сигнал появляется на первом входе элемента И 4 и на синхрони» зирувщих входах регистров памяти

9 (— 9, вызывая сдвиг содержимого регистров из 9 н 9з, из 9 з н 94;, из 9 н 9<, из 9< н 9, из 9 н 9 .

Через элементы И 111, ИЛИ 12 (, И 4» информация с выхода регистра 9» переэаписынается н него же и поступает

55 на выход 8(. В результате на выходах

8 — 8 получают следующую после»

JlîâàòåëüHîñòü двоичных кодов: 2, 5, 1,6,3,4.

Далее допустим, что следующий единичный сигнал появился на шестом выходе дещифратора (k = 6). Этот единичный сигнал закрывает элементы ЗА—

ПРЕТ 7 -и 5, поступает на первый вход элемента И 46, через элемент

HJIH 10 этот же единичный сигнал по" ступает на первый вход элемента И 4( на синхронизирувщие входы регистров памяти 9» — 9, нызыная сдвиг содержимого регистров из 9» н 9<,из 9, н Jj, èç 9 н,94., из 94 н 9, из

9 н 9». Через элементы И 4, ИЛИ

6 информация с выхода регистра 9 перезаписынается в него же и поступает на выход 8 . В результате на выходах 8 — 8 получают следующую последовательность двоичных кодов:

3, ?, 5, 1, 6, 4.

Пусть следующий единичный сигнал появился на первом выходе дешифратора (k = 1). Этот сигнал поступает на первый вход элемента И 4» и синхронизирувщие входы регистров памяти 9» — 9, вызывая сдвиг содержимого регистров из 9» н 9, из 9 в 99, из 99 в 9+, из 91 в 9, из

9 — 9g, из 96 н 9(. Так как при этом открыты элементы ЗАПРЕТ 7» - 7

5 и 5» — 5, закрыты элементы И 11 „11 и элементы И 4 — 4, то открывается только элемент И 4,. В результате на выходах 8 (— 8 устройства. получавт следувщую последовательность двоичных кодов: 4, 3, 2, 5, 1, 6.

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

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

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

i-го (i = 1...,n-1), где n — число элементов перестановок) регистра памяти группы соединен с прямым входом

i-го блока элементов ЗАПРЕТ первой группы и является выходом i-го элемента перестановки устройства, выход иго регистра памяти является выходом 25 п-го элемента перестановки устройства, выход (х+1)-го блока элементов

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

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

3AIIPHT второй группы и первым входом

i"ãî блока элементов И второй группы, второй вход которого соединен с выходом i-го регистра памяти группы, а выход — с первым входом i-го блока элементов ИЛИ второй группы, второй вход которого соединен с. выходом i-го блока элементов ЗАПРЕТ второй группы, прямой вход I-го (j = 1,...,n-2) блока элементов ЗАПРЕТ второй группы соединен с вторым входом (j+1)-го блока элементов И второй группы и с выходом (j+1)-ãî блока элементов

HJIH второй группы, прямой вход (ив

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

1644137

С ос тавител ъ В. Орлов

Редактор Т.Иванова Техред Д.Сердюкова Корректор П.Ревская

Заказ 1462 Тираж 400 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101