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

1 Изобретение относится к автоматике и вычислительной технике и может быть -использовано для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры. Цель изобретения - расширение ( функциональных возможностей генератора за счет обеспечения возможности получения сочетаний. На чертеже приведена структурная схема устройства для случайного перебора перестановок для шести переставляемых элементов. Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайного кода, дешифратор 3, блоки элементов И 4,-4, блоки элементов ЗАПРЕТ 5, - 5ц , блоки элементов IUIH 6,- блоки элементов ИЛИ 7, -7, информационные выходы устройства, группу регистров 9,-9g памяти. В предлагаемом устройстве каждая последующая перестановка получается из предыдущей путем циклического сдвига информации из предьщущего регистра в последующий по разньпч циклам, выбираемым случайным образом. Рассмотрим этот принцип на примере шести переставляемых элементов Пронумеруем позиции 1 - 6 слева направо и запишем в них двоичные коды переставляемых элементов, напри мер 1 - 6 соответственно, причем код с шестой позиции может попасть на любую другую позицию, кроме шестой, а коды со всех предьщущих позиций могут сдвигаться в соседние справа. Обозначим циклический сдвиг кодов с шестой позиции в пятую, из пятой в шестую - номер 1, циклический сдвиг кодов из шестой позиции в четвертую, из четвертой в пятую, из пятой в шестую - номер 2, циклический сдвиг кодов из шестой позиции в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую Номер 3, циклический сдвиг кодов из шестой позиции во вторую, из второй в третью, из третьей в четвертуто, из четвертой в пятую, из пятой в шестую номер 4, циклический сдвиг кодов из шестой позиции в первую, из первой позиции во вторую, из второй в третью, из третьей в четвертую, из четвертой в пятую, из пятой зз шестую - номер 5. 8 В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: Случайным образом выбирается номер циклического сдвига (например, номер четыре), это приводит к сдвигу двоичньк кодов из шестой позиции во вторую, из второй в третью, из -третьей в четвертую, из четвертой в пятую, из пятой в шестую одновременно I- 1 2345 В позициях 1-6 будет зафиксирована такая последовательность двоичных кодов: 4 5. Если сигнал случайного циклического сдвига выпадет на номер 2, то это приведет к сдвигу двоичных кодов из шестой позиции в четвертую, из четвертой в пятую, из пятой в шестую одновременно I-п 1234 56 В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: Если сигнал случайного циклического сдвига выпадет на номер 5, то это приведет к сдвигу двоичных кодов из шестой позиции в первую, из первой во вторую, из второй в третью, из третьей в четвертую, из четвертой в пятую, из пятой в шестую -0-ill-lIf-Cif В позициях 1 - 6 будет зафиксирована такая последовательность двоичных кодов: 416253. Устройство работает в трех режимах: получения случайных перестановок двоичных кодов;случайных сочетаний двоичных кодов,-получения случайных сочетаний,когда на m позициях расположены 1,а на (т-п) позициях О. Рассмотрим работу устройства в ре жиме получения случайных перестановок двоичных кодов в течение одного такта. В исходном состоянии в регист ры 9,- 9 записываются двоичные коды чисел 1 - 6 соответственно. Формируе мьй генератором 2 случайный двоичный код преобразуется дешифратором 3 в случайный унитарный код (случайным является норме вмхода дешифратора с единичным сигналом), которьй подается на первые входы элементов И 4, -4 Предположим, что этот единичный сигнал попадает на первый вход элемента И 4. Этот сигнал закрывает элемент 5 запрета и, пройдя через элементы ИЛИ 1 -7, второго блока, вызывает сдвиг содержимого регистров из 9 - в 9ц , из 9 - в 9 , из 9g , из 9g - в 9з . В результате на выходах 8g устройства получают такую последовательность двоичных ко дов: 1, 2, 6, 3, 4, 5. Устройство работаетаналогично и в режиме соче таний кодов. В этом случае выходные последовательности кодов снимаются с крайних справа выходов устройства, т.е. для С| - с выходов 85- и 8, , для Сд - с выходов 8ц - 8е, для С - с выходов 83- 8б , для С| - с выходов 8 - 8g , для С - с выходов 8, - 8g . В режиме случайных сочетаний, когда на m позициях расположены 1, а на (m-n) позициях О, в регистры 9,-9е записьшаются единицы и нули, количество которых равно m и (m-n) соответ ственно. Динамика работы устройства аналогична описанной. 284 Формула изобретения Устройство для случайного перебора перестановок, содержащее дешифратор, генератор тактовых импульсов, выход которого соединен с входом Опрос генератора случайного кода, отличающееся тем, что, с целью расширения функциональных возможностей генератора за счет обеспечения возможности получения сочетаний, оно содержит группу блоков элементов И, группу блоков элементов ЗАПРЕТ, две группы блоков элементов ИЛИ и группу регистров памяти, информационные входы которых, кроме первого и последнего, соединены с выходами соответствующих блоков элементов ИЛИ первой группы, первые входы которых соединены с выходами соответствующих блоков элементов И группы,а вторые входы блоков элементов ИЛИ первой группы соединены с выходами соответствующих блоков элементов ЗАПРЕТ группы, прямые входы которых соединены с информационными выходами соответствующих регистров памяти группы, а инверсные входы блоков элементов ЗАПРЕТ группы соединены с первыми входами соответствующих блоков-элементов ИЛИ второй группы, первыми входами соответствующих блоков элементов И группы и с соответствующими выходами дешифратора, синхронизируюш 1е входы регистров памяти группы, кроме первого и последнего, соединены с выходами соответствующих блоков элементов ИЛИ второй группы и вторыми входами последующих блоков элементов ИЛИ второй группы, информационный вход первого регистра памяти группы соединен с выходом первого блока элементов И группы, а информационный вход последнего регистра памяти группы соединен с выходом предпоследнего ререгистра памяти группы, выход последнего регистра памяти группы соединен с вторыми входами блоков элементов И группы, синхронизирующий вход первого регистра памяти группы соединен с вторым входом второго блока элементов ИЛИ второй группы, с первым входом первого блока элементов И группы и с первым выходом дешифратора.

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