Генератор случайной последовательности

Номер патента: 1040486

Авторы: Дапин, Кузнецов, Песошин

ZIP архив

Текст

0486 19) (11) 6 07 С 15/О 06 Р ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ фф.,вг 1 ц ЙН бл 24 822848/183,10.79.7.09.83, Бюл, Р 33.А.Песошин, В.М.КузнецДапинаэанский ордена Трудовнамени авиационный инсН.Туполева81.325(0888)КорнГ,А. Моделировапроцессов на аналогово-цифровых машинах. М,(22)(54)(57) ГЕНЕРАТОР СЛУЧА ВАТЕЛЬНОСТИ, содержак(ий ки, сумматор по модулю два ч а ю щ и й с я тем, что, вышения его быстродействия жит элемент НЕ, вход котор чен к выходу сумматора по а выход элемента НЕ соедин асинхронного блока задержк которого соединены с входа ра по модулю два соответст ПОСЛЕДО- задерж- отлицелью по- он содеро подклюдулю двавходомодыммато.Изобретение относится к вычислительной технике, тохнике измеренияи связи, может быть использовано Встохастических вычислительных машинах, при построении генераторов случайных чисел для ЦВМ, а также дляимитаторовслучайных помех при испытании различной аппаратуры и каналовсвязиИзвестен генератор случайной последовательности, содержащий регистр 10сдвига с сумматором по модулю два вцепи обратной связи 1),Недостатком этого генератора является наличие детерминизма в формируемой последовательности, свойственного всем псевдослучайным сигналам.Известен также генератор случайной последовательности, содержащийрегистр сдвига с сумматором по моду-.лю два в цепи обратной связи. В этом 20генераторе частота тактовых импульсов, осуществляющих сдвиг информациив регистре, изменяется по случайному закону 21,Символы в выходной последовательности такого генератора изменяютсяв случайные моменты времени, но порядок смены этих символов детерминированный, что составляет основной недостаток известного устройства.Наиболее близким по техническойсущности к предлагаемому являетсягенератор случайной последовательности, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи. на одном из выходов сумматора по модулю два действует случайный сигнал, благодаря чему на выходах генератора Формируются случайные последовательности с достаточнохорошими статистическими характеристиками 3)Однако быстродействие этого гене"ратора ограничено максимальной частотой импульсов сдвига регистра, Обычно для надежной работы таких синхрон ных цифровых устройств тактовая .частота должна выбираться примерно с5-10-кратным запасом по отношению креальным частотным возможностям схемы 3).50Цель изобретения - повышение быстродействия устройства,Поставленная цель достигается тем,.что в генератор, содержащий блокзадержки, сумматор по модулю два, дополнительно введен элемент НЕ, входкоторого подключен к выходу .сумматора по модулю два, а выход элементаНЕ соединен с входом асинхронногоблока задержки, выходы которого соединены с входами сумматора по модулю 60два соответственно,На чертеже представлена структурная схема генератора.генератор случайной последователь..ности содержит асинхронный блок 1 за" 65 держки, который нечетным количествомВыхОДОВ 112р 1пОДООеДинен квходам сумматора по модулю два. Выход сумматора 2 подключен через элемент НЕ 3 к входу асинронного блока1 задержки.В качестве асинхронного блока задержки 1 могут быть использованы,например, линия задержки или асинхронный регистр сдвига, т.е. такойблок задержки, у которого время задержки есть величина непрерывная иФлуктуирующая во времени. Необходимо также, Чтобы время задержки былозначительно .больше величины, обратной верхней граничной частоте асинхронного блока задержки,Обозначим через с,Т, ь,временные задержки по соответствукщимвыходам асинхронного блока 1 задержки. Тогда Флуктуации этих задержекможно оценить через среднеквадратические отклонения соответственноУИ 3,4 Ч,. - , Чъ ТДля работы устройства в качествегенератора случайной последователь"ности необходимо, чтобы отношенияматематических ожиданий времени задержки М Д М1 , М Г междусобой выражались йрраци 6 нальными числами или практически равнялись взаимно несократимым отношением доста"точно больших целых чиселфЯЬ,фЮ "г "ф ф Еъ 3 фо "где К 1, К 2ф Ко целые взаимно несократимые числа- единая мера измерения МД(1 щ 1, и)1В идеальном случае, когда отношения М 1 С, МЯ МГмежду собой. выражаются иррациональньаки числами, 1 с; - сф, а -ъ 6.Чем больше относительные величины флуктуаций бМЩ, тем слабее требования к иррациональности отношений математических ожиданий времен задержки.Работу предлагаемого устройства удобнее описывать при помощи сопоставлений и аналогии с работой иэвест" ного генератора псевдослучайныхйоследовательностей на основе синхронного регистра сдвига.с линейной обратной связью.Предположим, что флуктуации времен. ных,задержек отсутствуют, т.е.4 Ф;О; следовательно,МФ; вь;. Тогда Функцио нирование данного устройства можно описать как работу генератора псевдослучайных последовательностей, основанного на регистре сдвига с линей ной обратной связью, т.е. можно ус- . ловно счиать, что блок 1 эадераки выполнен в виде синхронного регистрасдвига, являющегося синхронным блоком задержки, с числом разрядов Ф=",."1 с), С разрядов )с; сигналы поступают на входы сумматора по модулю два. Частота импульсов сдвига ре-. ,гистра Г 1/Г. В этом случае устрой ство будет формировать. псевдослучайную последовательность с периодом"щф" Г" 1с 2 ф, с (2 К,10Структура и длина этой последова тельности определяется конкретными значениями )с,1, )с , .,. )с 1 т,е. могут, быть как последовательности максимальной длины (М - последователь-. 15 ности), так и последовательности- частных циклов . В идеальном случае условие иррациональности выполняет-,ся полностью Ь-со и С-О, так как . )с.щ. ф 20Прахтически .жеие 6 прерывно флуктуируют во времени. В этом случае устройство будет вырабатывать случайную последовательность. Так как в течении времени )с и ь бу дут постоянно изменяться, следовательно будет изменяться случайным образом и структура выходной после, довательности, т,е, последователь" ность на выходе будет состоять из З 0 случайных по длительности отрезков псевдослучайных, последовательностей различных структур с различными (случайными) масштабами по времени Ф . Такая ситуация также аналогична применению генератора псевдослучайной последовательности, но с постоянно перестраиваемой структурой по случай- ному закону, т.е. регистр сдвига в этом случае должен иметь бесконечно большое число разрядов, и и входов фф сумматора по модулю два случайным об" разом подключаются к этому регистру. При этом частота сдвиговых импульсов . регистра также должна изменяться согласно формуле .45.Таким образом, путем предельного . щ перехода от синхронной модели генератора псевдослучайной последовательнос- тИ получается асинхронная модель предлагаемого устройства. Функции тако го бесконечно длинного регистра со случайно изменяющейся частотой сдвига и случайными подключениями к сумматор", ру по модулю два может выполнитьасинхронный блок задержки, напримерширокополосная линия задержки с отвд" дами. В рабочем диапазоне температурлиния задержки, небольшими Флуктуацйями времени задержки 8;/Мс,.) порядка тысячных долей единйцы. Ъ 1 ри реаль иой воэможности выбора степени иррациональности отношений МГ;,МС 3, б 5 Мдмежду собой с помощью отводов и различных номинальных значений линий задержки эти флуктуации вполне достаточны для нормальнойработы генератора случайной последовательности,С учетом вышеприведенного анализа можно представить, работу устройства следующим образомПусть на выходе сумматора 2 сформировался сигнал х(х=0,1 - логическая переменная), тогда сигнал х с выхода элемента НЕ 3 поступает на вход асинхронного блока 1 задержки. С,выходов 1 блока данный сигнал х будет поступать на входы сумматора 2 последовательно, через соответствуюЩие отводам 1 1211, промежутки времени. В любой момент времени на входах сумматора 2 действуют логические сигналы, соответствующие сигналам, сформированным в разные моментЫ времени элементом НЕ 3, Если количество сигналов 1 ф на входах сумматора по модулю два 2 четное, то на выходе элемента НЕ 3 формируется сигнал 1, если нечетное, тосигнал Оф, Порядок смены логических уровней и длительность каждого элемента выходной последовательности определяется на каждый момент времени соотношениями времен задержки по выходам 1., 12, 1 и блока 1 задержки. Следовательно; в каждый момент времени выходная последовательность будет иметь псевдослучайный характер. Но, так как соотношения этих времен задержки в силу их флуктуаций постоянно изменяются случайным образом, то каждому последущцему моменту времени будет соответствовать другая псевдослучайная последовательность, и в течение всего, времени выходная последовательность устройства будет представляться уже случайной..Минимальная длительность действия логического сигнала, определякщая ширину спектра выходной последовательности, определяется реальным быстродействием элементов схемы.Чем больше и, тем легче добиться высокой степени иррациональности отИЬШЕНИй МрС 3, МЪ,1 МГсМЕжду собой и тем эффективяее .действуют малые временные флуктуации асйнхронного блока 1 задержки на процесс формирования случайной последовательности. Но, если и четное, то генератор может перейти в устойчивое состояние (фОфф на выходе и ф 1 фе на всех входах сумматора 2) и генерация случай" ной последовательности прекратится,Благодаря выбору нечетного и и наличию элемента НЕ 3 схема генератора устойчивого состояния не имеет. Действительно, если на выходе сумма-, тора 2 установится фОфф,.то на всех вго входах в устойчивом состоянии, Редактор И . Ков альчук Техред М, Кузьма Корректор Ю.МакаренкоЗаказ 6930/53 Тираж 706 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5филиал ППП Патентф 1, г.ужгород, ул,Проектная, 4 должны сформироваться1 ф, но так как и нечетное число, это потребуетустановленияна выходе сумматора 2. Пусть на выходе сумматора 2 установилась ф 1, тогда в устойчивом состоянии на его входах должны сформироваться ффО, что привело бы к изменению сигнала на 0 ф на выходе сумматора 2 и т,д. Таким обра" зом, подобная схема при нечетном и не может списываться статическими логическими уравнениями, что доказывает невозможность существования устойчивых состояний схемы.Асинхронный режим работы устройства позволяет, во-первый, эффективно 15 влиять малым флуктуациям временныхпараметров элементов схемы на формирование выходной последовательностибез участия дополнительного источника случайного процесса что упрощает устройство, во-вторых, надежноработать элементам схемы с предельным быстродействием, что, в конечномитоге, увеличивает быстродействиевсего генератора примерно в 5-10 разпо сравнению с быстродействием прототипа. Увеличение быстродействияустройства в данном случае аналогично расширению спектра формируемой случайной последовательности,

Смотреть

Заявка

2822848, 03.10.1979

КАЗАНСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ АВИАЦИОННЫЙ ИНСТИТУТ ИМ. А. Н. ТУПОЛЕВА

ПЕСОШИН ВАЛЕРИЙ АНДРЕЕВИЧ, КУЗНЕЦОВ ВАЛЕРИЙ МИХАЙЛОВИЧ, ДАПИН ОЛЕГ ИОСИФОВИЧ

МПК / Метки

МПК: G06F 7/58

Метки: генератор, последовательности, случайной

Опубликовано: 07.09.1983

Код ссылки

<a href="https://patents.su/4-1040486-generator-sluchajjnojj-posledovatelnosti.html" target="_blank" rel="follow" title="База патентов СССР">Генератор случайной последовательности</a>

Похожие патенты