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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей устройства. Оно содержит генератор тактовых импульсов , генератор случайного кода, дешифратор , первый и второй блоки элементов ИЛИ, блок элементов ЗАПРЕТ, блок элементов И, блок регистров, информационные входы которых, кроме первого и т-го регистров, соединены с выходами соответствующих элементов ИЛИ первого блока. Первые входы элементов ИЛИ соединены с выходами соответствующих элементов И, а вторые входы - с выходами соответствующих элементов ЗАПРЕТ. Неинвертированные входы элементов ЗАПРЕТ соединены с информационными входами соответствующих регистров, а инверсные входы с первыми входами элементов ИЛИ второго блока, первыми входами соответствующих элементов И и соответствующими выходами деишфратора. Синхронизирующие входы регистров соединены с выходами соответствующих элементов ИЛИ второго блока и вторыми входами элементов ИЛИ второго блока последующих разрядов. Информационные входы первого регистра соединены с выходами первого элемента И, а информационные входы т-го регистра - с выходами предыдущего регистра. Выход т-го регистра соединен с вторыми входами элементов И. Синхронизирующий вход т-го регистра соединен с вторым входом первого элемента, ИЛИ второго блока, первым входом первого элемента И и первым выходом дешифратора. Выходы ре1C гистров являются информационными вы (Л ходами устройства. Предлагаемое устройство представляет собой, практически , однородную структуру, так как все разряды строятся по одному и тому же принципу. Если возникает необходимость увеличить число элементов в случайных перестановках (сочетаниях), ю то необходимо добавить соответствуюS щее число разрядов. Каждый разряд содержит регистр, элемент И, элемент ЗАПРЕТ, элементы ИЛИ первого и втою рого блока. Число разрядов в регист00 ре должно быть равно. Устройство позволяет получать случайные перестановки кодов и случайные сочетания кодов. При этом.степень корреляции будет не хуже, так как в самом плохом случае за один такт генератора тактовых импульсов обмен происходит между т-м и (m-l)-M регистрами. В среднем же при равновероятном законе появления сигналов на выходе дешифратора обмен кодами происходит между т/2 регистрами . 1 ил.

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

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

РЕСПУБЛИК (50 4 С 06 F 7/58

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3879696/24-24 (22) 03.04.85 (46) 07. 11.86 . Бюл . N - 4 1 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.M. Глушань, M.È. Пупков и Л.И. Щербаков (53) 681.325(088..8) (56) Авторское свидетельство СССР

N - 922737, кл. G 06 F 7/58, 1980.

Авторское свидетельство СССР

У 997036, кл. G 06 F 7/58, 1981.

Авторское свидетельство СССР

Ф 1101820, кл. С 06 F 7/58, 1982. (54) УСТРОЙСТВО ДЛЯ СЛУЧАЙНОГО

ПЕРЕБОРА ПЕРЕСТАНОВОК (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — расширение функциональных возможностей устройства. Оно содержит генератор тактовых импульсов, генератор случайного кода, дешифратор, первый и второй блоки элементов ИЛИ, блок элементов "ЗАПРЕТ", блок элементов И, блок регистров, информационные входы которых, кроме первого и m-го регистров, соединены с выходами соответствующих элементов

ИЛИ первого блока. Первые входы элементов ИЛИ соединены с выходами соответствующих элементов И, а вторв|е входы — с выходами соответствующих элементов ЗАПРЕТ. Неинвертированные входы элементов ЗАПРЕТ соединены с информационными входами соответствующих регистров, а инверсные входы— с первыми входами элементов ИЛИ второго блока, первыми входами соответ— ствующих элементов И и соответствующими выходами дешифратора. Синхрони„„SU„,, 1269128 А 1 зирующие входы регистров соединены с выходами соответствующих элементов

ИЛИ второго блока и вторыми входами элементов ИЛИ второго блока последующих разрядов. Информационные входы первого регистра соединены с выходами первого элемента И, а информационные входы ш-го регистра — с выходами предыдущего регистра. Выход m — го регистра соединен с вторыми входами элементов И. Синхронизирующий вход m-ro регистра соединен с вторым входом первого элемента, ИЛИ второго блока, первым входом первого элемента И и первым выходом дешифратора. Выходы реС> гистров являются информационными выходами устройства. Предлагаемое устройство представляет собой, практически, однородную структуру, так как С все разряды строятся по одному и тому же принципу, Если возникает необходи- 2 мость увеличить число элементов н случайных перестановках (сочетаниях), Я то необходимо добавить соответствую- р щее число разрядов. Каждый разряд содержит регистр, элемент И, элемент

ЗАПРЕТ, элементы ИЛИ первого и второго блока. Число разрядов в регист- Х) ре должно быть равно. Устройство поз- QQ воляет получать случайные перестановки кодов и случайные сочетания кодов.

При этом. степень корреляции будет не хуже, так как в самом плохом случае за один такт генератора тактовых импульсов обмен происходит между m-м и (m-1)-м регистрами. В среднем же при равновероятном законе появления сигналов на выходе дешифратора обмен кодами происходит между m/2 регистрами. 1 ил.

1269128

1 2 3 4

35

45

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

Цель изобретения — расширение < функциональных возможностей генератора за счет обеспечения возможности получения сочетаний. 10

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

Устройство содержит генератор 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 Ь.

Случайным образом выбирается номер циклического сдвига (например, номер четыре), это приводит к сдвигу двоичных кодов иэ шестой позиции во вторую, из второй в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую одновременно

В позициях 1 — 6 будет зафиксирована такая последовательность двоичных кодов:

1 6 2 3 4 5.

Если сигнал случайного циклического сдвига выпадет на номер 2, то это приведет к сдвигу двоичных кодов из шестой позиции в четвертую, из четверток з пятую, из пятой в шестую одновременно

1 6 2-3 -- 4- 5

В позициях 1 — 6 будет зафиксирована такая последовательность двоичных кодов:

1 6 2 5 3 4.

Если сигнал случайного циклического сдвига выпадет на номер 5, то это приведет к сдвигу двоичных кодов из шестой позиции в первую, из первой во вторую, из второй в третью, иэ третьей в четвертую,, иэ четвертой в пятую, из пятой в шестую з 1269128 4 ! 5

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

1 2 3 4 5 (1) Д6 - Z l-Q l=$3(Ä4

В позициях 1 — 6 будет зафиксирована такая последовательность двоичных кодов:

1О

4 1 6 2 5 3 ° дом первого блока элементов И группы и с первым выходом дешифратора.

Устройство работает в трех режимах:получения случайных перестановок двоичных кодов;случайных сочетаний двоичных кодов;получения случайных сочетаний, когда на m позициях расположены "1",а íà (m-n) позициях "0".

Рассмотрим работу устройства в режиме получения случайных перестановок двоичных кодов в течение одного

20 такта. В исходном состоянии в регистры 9, — 9- записываются двоичные коды чисел 1 — 6 соответственно. Формируемый генератором 2 случайный двоичный код преобразуется дешифратором 3 в случайный унитарный код (случайным является норме внхопа дешифратора с единичным сигналом), который подается на первые входы элементов И 4, -4 .

Предположим, что этот единичный сигнал попадает на первый вход элемента И 4>. Этот сигнал закрывает элемент 5, запрета и, пройдя через элементы ИЛИ 7 -7 второго блока, вызывает сдвиг содержимого регистров: из 9 — в 9, из 9 — в 9, из 9s — 35 в 9, из 9 — в 9з . В результате на выходах 8„— 8 устройства получают такую последовательность двоичных кодов: 1, 2, 6, 3, 4, 5. Устройство работает аналогично и в режиме соче- 40 таний кодов. В этом случае выходные последовательности кодов снимаются с крайних справа выходов устройства, т.е. для С - с выходов 8 и 8„, для

С вЂ” с выходов 8 — 86, для С вЂ” с

ВЫХОДОВ 83 в 8, для СБ — С ВЫХОДОВ

8 — 8, для Cee — с выходов 8, — 8 . В режиме случайных сочетаний, когда на

m позициях расположены "1", а на (m-n) позициях "0", в регистры 9, -9 0 записываются единицы и нули, количество которых равно m и (m-и) соответственно. Динамика работы устройства аналогична описанной.

1строиство для случаиного перебора перестановок, содержащее дешифратор, генератор тактовых импульсов, выход

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

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

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

И группы, синхронизирующий вход первого регистра памяти группы соединен с вторым входом второго блока элементов ИЛИ второй группы, с первым вхоСоставитель А. Карасов

Текр ед Н, Глуще нк о

Корректор Л. Пилипенко

Редактор В. Петраш

Заказ 6037/51

Тираж 671

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

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

Подписное

Производственно-полиграфическое предприятие, r. Ужгород, ул„ Проектная, 4