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

(59 40 ОПИСАНИЕ ИЗОБРЕТЕН СТВ АВТОРСКОМУ СВ(21) 36 ( 22) 31 (46) 07 4-2 а Трудовогордена Дружбы наститут им. М. Кузнецов Далин, И,. К. Га В. Л. Садюнов етельство СССРК 5/08, 1971,ельство СССРГ 7/58, 1979,ельство СССР7/58, 1982.ковлев В. В.,тические преобраЛ.: Маииностроотделение, 1978. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРГО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ 4(71) Казанский орденКрасного Знамени и ородов авиационный инА. Н. Туполева(54)(57) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕн ДОВАТЕЛЬНОСТИ, содержащий элемент НЕ, элемент И, ВБ-триггер, три элемента И-НЕ, первый сумматор по модулю два, Т-триггер, группу из 2 п- (п=2,3) сумматоров по модулю два, выход каж-. дого -го (3.=1,22 п) сумматора по модулю два группы соединен с первым входом (+)-го сумматора по модулю два группы, вторые входы первых ш (ш=1, 2) сумматоров по модулю два группы подключены к выходу элемента НЕ, вход которого соединен с вторыми входами последующих 2 п-ш сумматоров по модулю два группы и с выходом элемента И, первый вход которого11 11 является первым входом Контроль генератора, тактовый вход которого соединен с В-входом ВБ-триггера, первыми входами первого и второго элементов И-НЕ, второй вход "Контроль"генератора соединен с вторым входом первого элемента И-НЕ, выход которого соединен с первым входом третьего элемента И-НЕ, выход которого под- ключен к Б-входу ВБ-триггера, Б-выход которого соединен с первым входом первого сумматора по модулю два, второй вход которого подключен к выходу второго элемента И-НЕ, о т л ич а ю щ и й с я тем, что, с целью повышения точности, он содерхит элемент задержки, второй сумматор по модулю два 1 блок памяти, счетчик адреса, выходы разрядов которого подключены к соответствующим адресным входам блока памяти, информационный вход которого соединен с первым входом первого сумматора по модулю два группы, с В-выходом ВБ-триггера и первьвч входом второго сумматора по модулю два, второй вход которого подключен к инверсному выходуоТ-триггера, счетный вход которого соединен с выходом блока памяти, управляющий вход которого соединен со счетным входом счетчика адреса и выходом первого элемента И-НЕ, а инверсный вход Т-триггера подключен к входу "Опрос" генератора, при этом выход 2 п-го сумматора по модулю два группы соединен с вторым входом третьего элемента И-НЕ и через элемент задержки с вторым входом второго элемента ИНЕ, выход второго сумматора по модулю два является выходом генератора.1 12Изобретение относится к вычислительной технике, технике измеренияи связи и может быть использовано встохастических вычислительных машинах в качестве датчиков случайных чисел для ЦВМ а также для имитаторовслучайных процессов при испытанииразличной аппаратуры и каналов связи.Известно устройство, состоящее изгенератора обобщенного телеграфногосигнала, подключенного через логические схемы к выходному триггеру, и генерирующее как асинхронную так и синхронную случайные последовательнос"ти. 13Однако в работе такого устройствавозможны сбои, так как на триггергенератора обобщенного телеграфногосигнала воздействуют случайные процессы со спектром, не согласованнымс частотными возможностями Т-триггера и остальной части устройства. Возникающие при этом сбои в работе отдельных элементов (в первую очередьтриггера генератора обобщенного телеграфного сигнала) прчводят к погрешностям статистических характеристик выходной синхронной случайнойпоследовательности.Известно устройство, представляющее собой соединенные в кольцо асинхронный элемент задержки с отводами,многовходовый сумматор по модулю дваи инвертирующий усилитель23. Устройство постоянно использует естественные флуктуации временных задержекасинхронного элемента задержки для цели формирования случайной последовательности типа обобщенного телеграфного сигнала. Это затрудняетконтроль работоспособности устройства, что усложняет технологию наладки и ухудшает ремонтопригодность следовательно снижает надежность егоэксплуатации. Кроме этого, устройство позволяет генерировать только .асинхронную случайную последовательность что также является еге недостатком.Наиболее близким техническим решением к предлагаемому является генератор случайной последовательности, представляющий собой соединенные в кольцо многовходовый сумматор по модулю два, состоящий из последовательно соединенных двухвходовых сумматоров по модулю два, элемента И, элемента НЕ, двух коммутаторов, а также75434 выходного формирователя и специтриггера впосредника 3Недостатком известного технического решения является относительно невысокая равновероятность и высокий уровень автокорреляции случайных символов в последовательности.Целью изобретения является повышение качества статистических характеристик случайных символов. 51 О Поставленная цель достигается темчто в генератор случайной последовательности, содержащий элемент НЕ,элемент И, ВБ-триггер, три элемента И-НЕ, первый сумматор по модулюдва, Т-триггер, группу из 2 п(и==2, 3, 4) сумматоров по модулюдва, выход каждого 5.-го (х=1, 22 п) сумматора по модулю два группысоединен с первым входом (+1)-госумматора по модулю два группы, вторые входы первых ш (ш=1 2) сумматоров по модулю два группы подключены к выходу элемента НЕ, вход которого соединен с вторыми входамипоследующих 2 п-ш сумматоров по модулю два и группы и с выходом элемента И, первый вход которого является первым входом "Контроль генератора, тактовый вход которого соединен с В-входом ВБ-триггера, первыми входами первого и второго элементов И-НЕ, второй вход "Контроль" генератора соединен с вторым входом 35первого элемента И-НЕ, выход которого подключен к Б-входу ВБ-триггера,Б-выход которого соединен с первымвходом первого сумматора по модулюдва, второй вход которого подключен 40к выходу второго элемента И-НЕ, дополнительно введены элемент задержки, второй сумматор по модулю два,блок памяти, счетчик адреса, выходыразрядов которого подключены к соответствующим адресным входам блокапамяти, информационный вход которогосоединен с первым входом первого сумматора по модулю два из группы, сВ-входом ВБ-триггера и с первым входом второго сумматора по модулю два,второй вход которого подключен к инверсному выходу Т-триггера, счетныйвход которого соединен с выходомблока памяти, управляющий вход которого соединен со счетным входомсчетчика адреса и выходом первогоэлемента И-НЕ, а инверсный вход Т1275434 зтриггера подключен к входу Опрос"генератора, при этом выход (2 п)-госумматора по модулю два иэ группысоединен с вторым входом третьегоэлемента И-НЕ и через элемент задержки - с вторым входом третьего элемента И-НЕ, выход второго сумматорапо модулю два является выходом генератора,На чертеже представлена схемаустройства (согласно требованиям,предъявляемым к изображению схем цифровой вычислительной техники, стрелки на связях отсутствуют, но приэтом необходимо полагать, что связьслева элемента означает вход, а связь,справа - выход).Генератор случайной последовательности состоит из группы сумматоров 1 , 1, 1 1 по модулю два, элемента НЕ 2, элементаИ-НЕ 3, элемента И-НЕ 4, элементаИ-НЕ 5, элемента 6 задержки, РЯ-триггер 7, первого сумматора 8 по модулюдва, счетчика 9 адреса, блока 10 памяти, Т-триггера 11, второго сумматора 12 по модулю два, элемента И 13.Вход 14 является входом тактовых импульсов, вход 15 - входом "Опрос",Устройство имеет также вход 16 обратной связи, выход 17 обратной связи, входы 18 и 19 контроля и выход20 генератора.Элемент НЕ 2 используется для увеличения нагрузочной способности (ко 35эфйициента разветвления по выходу)элемента И 13, В качестве него можетбыть использован инвертор или группаинверторов, обеспечивающих надежноедюрмирование логических уровней напряжения с выхода элемента И 13, подаваемых на необходимое (достаточнобольшое) количество входов группсумматоров 1 по модулю два.В качестве блока 10 памяти можетбыть использована матрица-накопительОЗУ с организацией г (т.е. в памяти ячеек по одному биту каждая). Приэтом коэсЯициент пересчета счетчика9 адреса должен составлять г,50Элемент-повторитель 6 служит длясохранения неизменным числа задержекэлементов в контуре генерации асинхронной случайной последовательностипри логическом "0" или "1" на вьхо 55де 14 тактовых импульсов. В качествеэлемента-повторителя 6 может бытьприменен, например, элемент ИЛИ,Ген ер атор р або то способен при любом способе (в том числе и при спо-собе, показанном на чертеже) подключения вторых входов сумматора 1 по модулю два группы к выходу и входу элемента НЕ 2, Однако более предпочтительно подключение входов сумматоров 1 группы в соответствии с таблицей непривоцимых полиномов 4Состояние элемента И 13 определяет режим работы устройства, Ксгда га вход 8 подана логическая "1", то это соответствует рабо е.".", состоянию, т.е, состоянию генерирования случайных последовательностей. При подаче логического 110" на контрольный вход 18 устройство переходит в режим кон-. троля, когда есть возможность проверить устройство как детерминированжш автомат (без генерации случайного процесса).В рабочем режиме при действии по входу 14 тактового сигнала Т=О образуется контур обратной связи, состоящий из блоков 1, 4, 7, 8, 13 и 2,При Т=1 образуется также контур обратной связи, но уже из блоков 1, 6, 5, 8, 13 и 2. В обоих случаях в контур обратной связи входят блоки 1, 8, 13 и 2, но при Т=О в этот кон тур включаются блоки 4 и 7 вместо блоков 6 и 5, которые входят в контур при Т=1. Аналогично, как и в известном устройстве (3), под действием даже малых естественных Флуктуаций временных задержек блоков 13, 2, 4, 5, 6 и 7 и блока 1 по каждому из 2 пего входу устанавливается режим генерирования широкополосного асинхронного случайного процесса, представляющего собой временную совокупность отрезков псевдослучайных последовательностей различной структуры, случайной длительности, случайного масштаба по времени и со слу" чайной Фазой. Однако в целях создания устойчивого режима генерирования контура должно быть обязательно выполнено следующее условиеК 1.Е 1 О(Аж) 1 О(АЕЧ)ЕВ) МАО.=0 =ЭС)ТО=У (1) где 1=0,1 - сигнал с выхода сумматора 1;А.=0,1 - оператор инверсии элемента НЕ 2;С=О;1 Х О,К и Х 5275 оператор инверсии последовательно соединенных элементов 6, 5, и 8 (при Т= );оператор инверсии после довательн соединенных элементов 4, 7.и 8 (при Т=О);сигнал настройки, подаваемый на вход первого 10 сумматор по модулю.два группы 1;соответственно объем первой и второй групп входов группы суммато ра 1, причем К+1 2 п,Оператор инверсии какого-либо блока обозначает следующее: если он равен О, то данный блок не инвертирует сигнал, поданный на его вход, аесли равен 1, то - инвертирует. Формула (1 ) справедлива, когда сумматор 12 имеет оператор инверсии, равный О, 25Упрощая выражение (1) и разрешаяего относительно Х, получаем более удобную ФОРмулу для вычисления сигнала настройки, подаваемого на вход пер-.вого сумматора по модулю два группы 1 З 03.+1Х=А 16 ВТЮСТ 91 .( 2 )еНапример, пусть элемент НЕ 2 инвертирует сигнал (А 1), блоки 4, 7 и 8 не инвертируит (В С=О), а 1 - четное число, тогда получаем Х 0 (для любого Т=0,1). При таком Х в . контуре всегда будет стремиться выполняться логически противоречивое условие У=У (т.е. Т 0), благодаря чему будет поддерэяваться устойчивый нроцесс генерации асинхронной случайной последовательности.В паузе между тактовыми импульса ми (при Т=О) ВБ-триггер 7 включается в контур, а в момент действия тактовых импульсов (при Т=1) выключается из него, устанавливаясь при этом в случайное состояние, и формирует с помощью выравнивающего устройства, включающего блоки 9-12, элементы выходной последовательности - случайные символы. Такая организация работы устройства исключает сбои ВБ-триг 5 ъ гера 7 по причине конечного его быстродействия, так как скорость протекания процессов в контуре всегда согласована с минимальным быстродейст 434Ьвием входящих в него блоков, в том числе и ВБ-триггера 7.Элемент-повторитель 6 с временем задержки примерно равным времени задержки ВБ-триггера 7 по асинхронным входам способствует устранении корреляции, вносимой тактовыми импульсами в асинхронную случайную последовательность. Элементу повторитель 6 обеспечивает примерное равенство суммарного времени задержки блоков 4, 7 и 8 (при Т 0) и суммарного времени задержки блоков б, 5 и 8 (при Т 1 ) .Блоки 9-12 образуют выравнивающее и декоррелируищее устройство, Счетчик 9 пересчитывает тактовые импульсы, поступающие с входа тактовых импульсов 14 и задает последовательные адреса ячеек блока 1 О памяти. Тактовые импульсы, проинвертированные элементом И-НЕ 3, поступая на управляющий вход 10 памяти, задают режимычтения (при Т=О) либо записи (при Т=1). Случайные символы, сФормированные на выходе ВЯ-триггера 7 (при Т=1) записываются в блок 10 памятии затем считываются из него через гтактов. Задержанная на г тактов случайная последовательность с выхода блока 10 памяти поступает на счетный вход Т-триггера 11. Т-триггер 11 осуществляет пересчет задержанной последовательности случайных символом, дополнительно выравнивая вероятность появления символа "1" в случайной последовательности до 0,5. На первый вход сумматора 12 по модулю два поступает последовательность случайных символов с выхода ВБ-триггера 7, а на второй вход блока 12 поступает с выхода блока 1 та же последовательность, но задержанная на г тактов и пересчитанная по модулю два. При условии, что число ячеек в блоке 10 памяти больше интервала автокорреляции последовательности случайных символов, формируемых на выходе ВБ-триггера 7, на выходе генератора 20 будет развертываться декоррелированная последовательность случайных символов.Устройство работает следующим образом.Пусть в рабочем режиме по входу 14 тактовых импульсов проходит сигнал Т=О. Он переключает сигнал с выхода (2 п)-го сумматорапо модулю два группы на последовательно соеди 7 12754ненные элемент И-НЕ 4, ВЯ-триггер 7,сумматор 8 по модулю два, На входпервого сумматора 1 по модулю двагруппы подан сигнал Х, рассчитанныйпо формуле (2) для Т=О, благодарячему выполняется условие (1) и в соответствующем контуре развиваетсяасинхронный случайный процесс.ВБ-триггер 7 при этом также беспрерывно случайным образом переклю Очается. Формирование выходного элемента синхронной случайной последовательности на инверсном выходе ВБтриггера 7 при этом не происходит.Блок памяти при этом находится в режиме чтения из ячейки с адресом,равным состоянию счетчика 9 адреса.В момент действия сигнала Т=1 изконтура генерации выключаются элемент И-НЕ 4 и ВБ-триггер 7, но генерация в контуре продолжается, таккак контур остается замкнутым с выхода (2 п)-го сумматора 1 по модулю два группы через последовательносоединенные элемент-повторитель 6, 25элемент И-НЕ 5 и сумматор 8 по модулю два, на вход элемента И 13, Приэтом выполняется условие 1, благодаря подаче на вход первого сумматора" 1 по модулю два группы сигнала настройки Х, рассчитанного по .формуле(2) для Т=1, После выключения ВБ-триггера 7 из контура генерации, он (ВБтриггер) хранит случайное состояниеЯ, инверсия которого Ц поступает врассматриваемый полутакт (Т=1) навход блока 10 памяти. Блок 1 О памятипри Т=1 находится в режиме записи вячейку, из которой перед этим (в момент Т=О) быпа считана инфорйация. 40При подаче сигнала опроса на вход 15сигнала опроса, на выходе 20 генера-тора формируется элемент выходнойсинхронной случайной последовательности. Генерирующий без ВБ-триггера7 контур (Т=1) подготавливает случайную фазу для следующего цикла работы. В следующий такт состояниесчетчика 9 адреса увеличится на 1.При Т=1 происходит чтение из ячейкиблока 10 памяти с новым адресом, апри Т=О запись случайного символа,сформированного на выходе ВБ-триггера 7, в эту же ячейку блока 10 памяти. Процесс повторяется. Через гтактов счетчик 9 установится в то жесостояние, что и в момент включениягенератора. В первый полутакт (при 34 8Т=О) на выходе блока 10 памяти считывается случайный символ с задержкой на г тактов по сравнению с символами на выходе ВБ-триггера 7. Вовторой полутакт (при Т=О) в ячейкублока 10 памяти с этим же адресомзапинется новый случайный символ. Таким образом, на выходе блока 10 памяти будет разворачиваться последователЪность случайных символов, задедержанных по сравнению с инверснымвходом ВЯ-триггера 7 на г тактов. Вкаждый второй полутакт при Т=) навыходе 20 устройства формируется случайный символ видаЕ=Х,О+Х; -п 1-1 ЗХ; ,где Х, - случайный символ на выходе120 генератора в д-и такт;Х - случайный символ на инверс 1ном выходе ВБ-триггера 7;В каждый первый полутакт (приТ=О) на выходе 20 будет случайныйсимвол равный Х, (+)Х. , так какна инверсном выходе ВЯ-триггера 7при Т=О"уровень логической "1".В режиме контроля (при наладкеили ремонте устройства) цепь обратной связи контура генерации необходимо разорвать, подав на вход 18 логический "0". Тогда рассматриваемоеустройство превращается в детерминированный автомат, контроль работоспособности которого можно осуществить обычными средствами, пользуясьвходами 14, 15, 16, 18 и 19, выходами 17 и 20, а также выходами с остальных промежуточных точек схемы(не показаны)Предлагаемое устройство может бытьполностью реализовано на цифровыхинтегральных микросхемах. В качествеблока 10 памяти .могут быть использованы, например, жкросхемы 134 РУ 6,155 РУ 5, 500 РУ 148, 500 РУ 4106, 500 РУ 415и т.д.При работе известного генератора3 , генерируется последовательностьслучайных символов с относительно невысокой равновероятностью и высокимуровнем автокорфеляции.По сравнению с известным устройством, предлагаемое позволяет достаточно просто получить некоррелированную последовательность случайныхсимволов с вероятностью появлениясимвола 1 равной 0,5 с высокой точностью. Кроме тогоО предлагаемоеустройство позволяет работать приСоставитель А, КарасовТехред Н, Глущенко рректор А. Тяско В. Ивано писное Тираж 671 сударственного изобретений а, Ж, Раув6561/40ВНИИПИ Гопо делам13035, Москв Зака комит и отк ская н/5 тие, г. Ужгород, ул. Проек ческое пр оизводственно-пол 9 1275434 10 значительно более высоких тактовых мыми статистическими характеристика- частотах и частотах опроса, чем из- ,ми даже тогда, когда на выходе ВЯ вестное устройство, что обусловлено, триггера 7 (а следовательно на выхо во-первых, введением в предлагаемое де известного объекта) генерируется устройство элемента-повторителя 6,последовательность случайных симвовследствие чего снижается корреляция, лов с совершенно неприемпеьыми ста" вносимая тактовыми импульсами в асин- тистическими характеристиками. хронную последовательность и, вовторых, введением выравнивающего уст- Предлагаемое техническое решение ройства, включающего в себя счетчик 1 О намечено использовать при модерни адреса, блок 1 О памяти, Т-триггер зации устройства ввода случайных чи и сумматор 12 по модулю два. Это сел ЕС 6903, что позволит получить позволяет на выходе устройства 20 экономический эект за счет повыполучать синхронную последователь- шения точности генерирования и повыность случайных символов с приемпе шения быстродействия устройства,