Генератор случайной последовательности Советский патент 1983 года по МПК G06F7/58 G07C15/00 

X

Изобретение относится к вычислительной технике, тохнике измерения и связи, может быть использовано в стохастических вычислительных машинах, при построении генераторов случайных чисел для ЦВМ, а также для имитаторов случайных помех при испытании различной аппаратуры и каналов связи. Известен генератор случайной последовательности, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи . Недостатком этого генератора явля ется наличие детерминизма в формируе мой последовательности, свойственного всем псевдослучайным сигналам. Известен также генератор случайной последовательности, содержгодий регистр сдвига с сумматору по модулю два в цепи обратной связи. В этом генераторе частота тактовых импульсов, осуществляющих сдвиг информации в регистре, изменяется по случайному закону 2. Символы в выходной последовательиости такого генератора изменяются в случайные моменты времени, но поря док смены этих символов детерминированный, что составляет основной недостаток известного устройства. Наиболее близким по технической сущности к предлагаемому является {генератор случайной последовательное ти, содержащий регистр сдвига с сум матором по модулю два в цепи обрат ной связи. На одном из выходов сумматора по модулю два действует случайный сигнал, благодаря чему на выходах генератора формируются случайные последовательности с достаточно хорошими статистическими характернотиками 3. однако быстродействие этого генератора- ограничено максимальной часто той импульсов сдвига регистра. Обычно для надежной работы таких синхрон ных цифровых устройств тактовая частота должна выбираться примерно с 5-10-кратным запасом по отношению к реальным частотным возможностям схемы 3, Цель изобретения - повышение быст родействия устройства. Поставленная цель достигается тем что в генератор, содержащий блок задержки, сумматор по модулю два, до полнительно введен элемент НЕ, вход которого подключен к выходу -суммато ра по модулю два, а выход элемента НК соединен с входом асинхронного . блока задержки, выходы которого сое динены с входами сумматора по модулю два соответственно. На чертеже представлена структурная схема генератора. Генератор случайной последователь ности содержит асинхронный блок 1 за держки, который нечетным количеством выходов 1, Ij .. . , 1 подсоединен к входам сумматора по модулю два. Выход сумматора 2 подключен через элемент НЕ 3 к входу асинхронного блока 1 задержки. В качестве асинхронного блока задержки 1 могут быть использованы, например, линия Эс1держки или асинхронный регистр сдвига, т.е. такой блок задержки, у которого время задержки есть величина непрерывная и флуктуирующая во времени. Необходимо также, Чтобы время задержки выло значительно .больше величины, обратной верхней граничной частоте асинхронного блока задержки. Обозначим через ,,,.Т временные задержки по соответствующим выходам асинхронного блока 1 задержки. Тогда флуктуации этих задержек можно оценить через с ;еднеквадратические отклрнения сортветственно .З..-. Для работы устройства в качестве генератора случайной последовательности необходимо, чтобы отношения математических ожиданий времени задержки М , М fTg ,.,,, М СТ„ 3 между собой выражались иррацибнальными числами или практически равнялись взаимно несократимым отношением достаточно больших целых чисел , где К, К2.., целые взаимно несократимые числа; v i - единая мера измерения Mfr.Jdel, п) В идеальном случае, когда отнетдёния Mff,,.,, М Г„ между собой, выражаются иррациональными числами, Н. air- e. Чем больше относительные величины флуктуации . , тем слабее требования к иррациональности отношений математических ожиданий времен задержки. Работу предлагаемого устройства удобнее описывать при помощи сопоставлений и аналогии с работой известного генератора псевдослучайных: последовательностей на. основе синхронного регистра сдвига с линейной обратной связью. Предположим, что флуктуации вр «ен-1 ных.задержек отсутствуют, T,e,eCf| rO, следовательно,.., Тогда функцисгнирование устройства можно описать как работу генератора псевдослучайных после(довательностей, основанного на регистре сдвига с линей ной обратной связью, т,е, можно условно считать, что блок 1 заяоуаккн выполнен в виде синхронного регистра сдвига, являющегося синхронным бло-ком задержки, с числом разрядов . .rnwxj y.j С разрядов k- сигналы поступают на входы сумматора по моду лю два. Частоту импульсов сдвига рег .гистра F 1/C. В этом случае устройство буде.т формировать псевдослуча йную последовательность с периодом, rndXr 1 t() / (гМ. Структура и длина этойпоследова тельности определяется конкретными значениями k(, kg, ;,.Г k,, т.е. могут быть как последовательности Makсимальной длины (М - последовательности), так и последовательности частных циклов. В идеальном случае условие иррациональности выполняется полностью и , так как . ,« практически же Т , tg ,..., Т впрерывно флуктуируют во времени. В этом случае устройство будет вырабатывать случайную йоследовательно ть. Так как в течении времени k и f будут постоянно изменяться, следовательно будет изменяться случайным образом и структура выходной последовательности, т.е, последовательность на выходе будет состоять из случайных по длительности отрезков псевдослучайных .последовательностей различных структур с различными (случайными) масштабами по времени 7 Такая ситуация также аналогична применению генератора псевдослучайной последовательности, но с постоянно перестраиваемой структурой по случайному закону, т.е. регистр сдвига в . этси случае должен иметь бесконечно большое число раэрящов, и п входов сумматора по модулю два случайным рб:разом подключаются к этому регистру. При этом частота сдвиговых импульсов регистра также должна изменяться согласно формуле . . , N jr -WcTT.Таким образЪм, путем предельного: перехода от синхронной модели reHepiaтора псевдослучайной последовательнос ти получается асинхронная модель прео лагаемого устройства. Функции такого бесконечно длинного регистра со случайно изменяющейся частотой сдвига и случайными подключениями к сумматб ру по модулю два может выполнить асинхронный блок задержки/ например широкополосная линия задержки с отводами. В рабочем диапазоне температур линия задержки.небольшими флуктуациями времени задержки jfr,- /Mrt- J поряд ка тысячных долей единицы, при реальиой возможности выбора степени иррациональности отношений мСГ /MpTj,, , . .у -М Г пJмеладу собой с помощью отводов и различных номинальных значений линий задержки эти флуктуации вполне достаточны для нормальнойработы генератора случайной последовательности, С учетом вышеприведенного анализа можно представить. работ:у устройства следующим образом. . Пусть на выходе сумматора 2 сформировался сигнал х(,1 - логическая переменная), тогда сигнал х с выхода элемента НЕ 3 поступает на вход асинхронного блока 1 задержки, С. выходов 1 блока данный сигнал х будет поступать на входы сумматора 2 последовательно, через соответствующие отводам 1, ,..., Ij, промежутки времени. В любой момент времени на входах сумматора 2 дейс.твуют логические сигналы, соответствующие сигналам, сформщюванным в разные моменты времени элементом НЕ 3. Если количество сигналов i на входах сумматора по модулю два 2 четное, то на выходе элемента НЕ 3 формируется сигнал , если нечетное, то . Порядок смены логичессигналких уровней и длительность каждого элемента выходной последовательности определяется на каждый момент времени соотношениями времен задержки по выходам 1, 12,..., Ij, блока 1 задержки. Следовательно; в каждый момент времени выходная последовательность будет иметь псевдослучайный характер. Но, так как соотношения этих времен задержки в силу их флук туаций постоянно изменяются случайным образом, то каждому последующему моменту времени б.удет соответствовать другая псевдослучайная последовательность, и в те рвние всего, времени выходная последовательность устройства будет представляться уже случайной. . Минимальная длительность действия логического сигнала, определяющая ширину спектра выходной последова тельности, определяется реальньм быстродействием элементов схемы. Чем больше п, тем легче добиться высокой степени иррациональнос.ти от«Лшений мСг,,..., мС1р,ежду собой и тем эффективнее действуют малые временные флуктуации асинхронного блока 1 задержки йа процесс формирования случайной последовательности. Но, если п четное, то генератор может перейти в устойчивое состояние СО на выходе и Ч на всех входах сумматора 2) и генерация случайной последовательности прекратится. Благодаря выбору нечетного п и наличию элемента НЕ 3 схема генератора устойчивого состояния не имеет. Действительно, если на выходе сумматора 2 установится О, то на всех ВТО входах в устойчивом состоянии (

5.10404866 .

должны сформироваться , но таквлиять малым флуктуациям временных

как п нечетное число, это потребует параметров элементов схемы на формиуса-ановлвния -А на выходе сумма-рование выходной последовательности

тора 2. Пусть на выходе сумматора 2без участия дополнительного источниустановилась Ч, тогда в- устойчи-ка случайного процесса , что упрощавом состоянии на его входах должны ет устройство, во-вторых, нгщежно

сформироваться О, что привело быработать элементам схемы с предельк изменению сигнала н-а О на вы-ным быстродействием, что, в конечном

ходе сумматора 2 и т.д. Таким обра-итоге, увеличивает быстродействие

эом, подобная схема при нечетном пвсего генератора примерно в 5-10 раз

не может списываться статическими ло-Юпо сравнению с быстродействием протогическими уравнениями, что докаэыва-типа. Увеличение быстродействия устет невозможность существования устой-ройства в данном случае аначивых состояний схемы.логично расширению спектра форАсинхронный режим работы устройст-мируемой случайной последовательва позволяет, во-первых, эффективно 15ности. /

ГЕНЕРАТОР СЛУЧАЙВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, содержащий блок задержки, сумматор по модулю два, отличающийся тем, что, с целью повышения ef о быстродействия, он содержит -элемент НЕ, вход которого подключен к выходу сумматора по модулю два, а выход элемента НЕ соединен с входом асинхронного блока задержки, выходы которого соединены с входами сумматора по модулю два соответственно.