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

Изобретение относится к вычислии связи и может быть использовано в стохастических вычислительных машинах в качестве датчиков случайных чи сел для ЦВМ, а также для имитаторов случайных процессов при испытании различной аппаратуры и каналов связи Известно устройство, состоящее из генератора обобщенного телеграфного сигнала, подключенного через логичес кие схе;мы к выходному триггеру, и ге нерирующее как асинхронную так и син хронную случайные последовательности. 1 Однако в работе такого устройства возможны сбои, так как на триггер генератора обобщенного телеграфного сигнала воздействуют случайные процессы со спектром, не согласованным с частотньфш возможностями Т-трйггера и остальной части устройства. Воз никающие при этом сбои в работе отдельных элементов (в первую очередь триггера генератора обобщенного телеграфного сигнала) приводят к погрешностям статистических характеристик выходной синхронной случайной последовательности. Известно устройство, представляющее собой соединенные в кольцо асинхронный элемент задержки .с отводами, многовходовый сумматор по модулю два и инвертируюпщй усилитель 2. Уст.ройство постоянно использует естественные флуктуации временных задержек асинхронного элемента задержки для цели формирования случайной последовательности типа обобщенного телеграфного сигнала. Это затрудняет контроль работоспособности устройства, что усложняет технологию наладки и ухудшает ремонтопригодность, следовательно снижает надежность его эксплуатации. Кроме этого, устройство позволяет генерировать только .асинхронную случайную последовательность, что также является еге недостатком. Наиболее близким техническим решением к предлагаемому является генератор случайной последовательности представляющий собой соединенные в кольцо многовходовый сумматор по модулю два, состоящий из последователь но соединенных двухвходовьпс суммато;ров по модулю два, элемента И, элемента НЕ, двух коммутаторов, а также 4 выходного формирователя и специального триггера - посредника 3. Недостатком известного технического решения является относительно невысокая равновероятность и высокий уровень автокорреляции случайных символов в последовательности. Целью изобретения является повышение качества статистических характеристик случайных символов. Поставленная цель достигается тем, что в генератор случайной последовательности, содержащий элемент НЕ, элемент И, RS-триггер, три элемента И-НЕ, первый сумматор по модулю два, Т-триггер, группу из 2п-1 (п 2, 3, 4.,,) сумматоров по модулю два, выход каждого i-ro (i--l, 2,..., 2n-2) сумматора по модулю два группы соединен с первым входом (i+l) сумматора по модулю два группы, вторые входы первых т (, 2...) сумматоров по модулю два группы подключены к выходу элемента НЕ, вход которого соединен с вторыми входами последующих 2n-2-m сумматоров по модулю два и группы и с выходом элемента И, первый вход которого является первым входом Контроль - генератора, тактовый вход которого соединен с R-входом RS-триггера, первыми входами первого и второго элементов И-НЕ, второй вход Контроль генератора соединен с вторым входом первого элемента И-НЕ, выход которого подключен к S-входу RS-триггера, S-выход которого соединен с первым входом первого сумматора по модулю два, второй вход которого подключен к йыходу второго элемента И-НЕ, дополнительно введены элемент задержки, второй сумматор по модулю два, блок памяти., счетчик адреса, выходы разрядов которого подключены к соответствующим адресным входам блока памяти, информационный вход которого соединен с первым входом первого сумматора по модулю два из группы, с R-входом RS-триггера и с первым входом второго сумматора по модулю два, второй вход которого подключен к инверсному выходу Т-триггера, счетный вход которого соединен с выходом блока памяти, управляющий вход которого соединен со счетным входом счетчика адреса и выходом первого элемента И-НЕ, а инверсный вход Ттриггера подключен к входу Опрос генератора, при этом выход (2п-1)-го сумматора по модулю два из группы соединен с вторым входом третьего элемента И-НЕ и через элемент задержки - с вторым входом третьего элемента И-НЕ, выход второго сумматора по модулю два является выходом генератора. На чертеже представлена схема устройства (согласно требованиям, предъявляемым к изображению схем циф ровой вычислительной техники, стрелки на связях отсутствуют, но при этом необходимо полагагь, что связь слева элемента означает вход, а связ . справа - выход). Генератор случайной последовательности состоит из группы сумматоров 1,, 1,..., , по мо дулю два, элемента НЕ 2, элемента И-НЕ 3, элемента И-НЕ 4, элемента И-НЕ 5, элемента 6 задержки, BS-триг гер 7, первого сумматора 8 по модулю два, счетчика 9 адреса, блока 10 памяти, Т-триггера П, второго сумматора 12 по модулю два, элемента И 13 Вход 14 является входом тактовых импульсов, вход 15 - входом Опрос. Устройство имеет также вход 16 обратной связи, выход 17 обратной связи, входы 18 и 19 контроля и выход 20 генератора. Элемент НЕ 2 используется для уве личения нагрузочной способности (коэф циента разветвления по выходу) элемента И 13. В качестве него может быть использован инвертор или группа инверторов, обеспечивающих надежное формирование логических уровней напряжения с выхода элемента И 13, подаваемых на необходимое (достаточно большое) количество входов групп сумматоров 1 по модулю два. В качестве блока 10 памяти может быть использована матрица-накопитель ОЗУ с организацией г«1 (т.е. в памяти ячеек по одному биту каждая). При этом коэффициент пересчета счетчика 9 адреса должен составлять г. Элемент-повторитель 6 служит для сохранения неизменным числа задержек элементов в контуре генерации асинхронной случайной последовательности при логическом О или 1 на выходе 14 тактовых импульсов. В качеств элемента-повторителя 6 может быть применен, например, элемент ИЛИ. Генератор работоспособен при любом способе (в том числе и при способе, показанном на чертеже) подключения вторых входов сумматора 1 по модулю два группы к .выходу и входу элемента НЕ 2. Однако более предпочтительно подключение входов сумматоров 1 группы в соответствии с таблицей неприводимых полиномов 4 . Состояние элемента И 13 определяет режим работы устройства. Когда ка вход 18 подана логическая 1, то это соответствует состоянию, т.е. состоянию генерирования случайных последовательностей. При гюдаче логического О на контрольный вход 18 устройство переходит в режим кон-. троля, когда есть возможность проверить устройство как детерминированный автомат (без генерации случайного процесса). В рабочем режиме при действии по входу 14 тактового сигнала образуется контур обратной связи, сосТОЯПЦ1Й из блоков 1, 4, 7, 8, 13и 2. При образуется также контур обратной связи, но уже из блоков , 6,5,8, 13и2.В обоих случаях в контур обратной связи входят блоки 1, 8, 13 и 2, но при в этот контур включаются блоки 4 и 7 вместо блоков 6 и 5, которые входят в контур при . Аналогично, как и в известном устройстве 3, под действием даже малых естественных флуктуации временных задержек блоков 13, 2, 4, 5, 6 и 7 и блока 1 по каждому из 2п-1 его входу устанавливается режим генерирования широкополосного асинхронного случайного процесса, представляющего собой временную совокупность отрезков псевдослучайных последовательностей различной структуры, случайной длительностг с, случайного масштаба по времени и со случайной фазой. Однако в целях создания устойчивого режима генерирования контура должно быть обязательно выполнено следующее условие К 1 У III ©( A©Y) n 1 © (A®Y )@В) Т@( AQY 0C) , (1) где - сигнал свыхода суккато pa 1; ,1 - операторинверсии элемента НЕ2; S - оператор инверсии после довательно соединенных элементов 6, 5, и 8 (при ); ,1 - оператор инверсии после довательно соединеншлх элементов 4, 7 и 8 (при ); ,1 - сигнал настройки, подаваемый на вход первого сумматор по модулю.два группы 1; К и 1 - соответственно объем первой и второй групп входов группы сумматора I, причем , Оператор инверсии какого-либо бло ка обозначает следующее: если он равен О, то данный блок не инвертирует сигнал, поданный на его вход, а если равен 1, то - инвертирует. Формула (1) справедлива, когда сунматор 12 имеет оператор инверсии, равный О, Упрощая вьфажение (1) и разрешая его относительно X, получаем более удобную формулу для вычисления сигна ла настройки, подаваемого на вход пер вого сумматора по модулю два группы 1+1 X Ali;;i©BT@cf®l.(2) Например, пусть элемент НЕ 2 инвертирует сигнал () блоки 4, 7 и 8 не инвертируют (), а 1 четное число, тогда получаем (дпя любого ,1). При таком X в . контуре всегда будет стремиться выполняться логически противоречивое условие (т.е. ), благодаря чему будет поддерживаться устойчивый процесс генерации асинхронной случайной последовательности, В паузе мезеду тактовыми импульсами (при ) RS-триггер 7 включается в контур, а в момент действия тактовых имп шьсов (при ) выключается из него устанавливаясь при этом в случайное состояние, и формирует с помощью выравнивающего устройства, включармцёго блоки 9-12, элементы выходной последовательности - случайные символы. Такая организация работа устройства исключает сбои RS-триг fepa 7 по причине конечного его быст родействия, так как скорость протекания процессов в контуре всегда сог ласована с минимальным быстродейст344 . вием входящих в него блоков, в том числе и RS-триггера 7. Элемент-повторитель 6 с временем задержки примерно равным времени задержки RS-триггера 7 по асинхронным входам способствует устронению корреляции, вносимой тактовыми импульсами в асинхронную случайную последовательность. Элементу повторитель 6 обеспечивает примерное равенство суммарного времени задержки блоков 4, 7 и 8 (при ) и сзтмарного времени задержки блоков 6, 5 и 8 (при ). Блоки 9-12 образуют выравнивающее и декоррелирующее устройство. Счетчик 9 пересчитывает тактовые импульсы, поступаишще с входа тактовых импульсов 14 и задает последовательные адреса ячеек блока 10 памяти. Тактовые импульсы, проинвертированные элементом И-НЕ 3, поступая иа управляющий вход 10 памяти, задают режиьа 1 чтения (при ) либо записи (при ). Случайные символы, сформированные на выходе RS-триггера 7 (при Т 1), записываются в блок 10 памяти и затем считываются из него через г тактов. Задержанная на г тактов случайная последовательность с выхода блока 10 памяти поступает на счетный вход Т-триггера 11. Т-триггер 11 осуществляет пересчет задержанной последовательности случайных символом, дополнительно выравнивая вероятность появления символа I в случайной последовательности до 0,5. На первый вход сумматора 12 по модулю два поступает последовательность случайных символов с выхода RS-триггера 7, а на второй вход блока 12 поступает с выхода блока II та же последовательность, но задержанная на г тактов и пересчитанная гю модулю два. При условии, что число ячеек в блоке 10 памяти больше интервала автокорреляции последовательности случайных символов, формируемых на быходе RS-триггера 7, на выходе генератора 20 будет развертываться декоррелированная последовательность случайных символ лов. Устройство работает следующим образом. Пусть в рабочем режиме по входу 14 тактовых импульсов проходит сигнал . Он переключает сигнал с выхода (2п-)-го сумматора 1 по модулю два группы на последовательно соединенные элемент И-НЕ 4, RS-триггер 7, сумматор 8 по модулю два. На вход первого сумматора 1 по модулю два группь: подан сигнал X, рассчитанный по формуле (2) для , благодаря чему выполняется условие (1) и в соответствующем контуре развивается асинхронный случайный процесс. RS-триггер 7 при этом также беспрерывно случайным образом переключается . Формирование выходного элемента синхронной случайной последовательности на инверсном выходе RSтриггера 7 при этом не происходит. Блок памяти при этом находится в режиме чтения из ячейки с адресом, равным состоянию счетчика 9 адреса. В момент действия сигнала из контура генерации выключаются элемент И-НЕ 4 и RS-триггер 7, но генерация в контуре продолжается, так как контур остается замкнутым с выхода {2п-1)-го сумматора 1 по модулю два группы через последовательно соединенные элемент-повторитель 6, элемент И-НЕ 5 и сумматор 8 по модулю два, на вход элемента И 13. При этом выполняется условие 1, благодаря подаче на вход первого сумматора 1 по модулю два группы сигнала настройки X, рассчитанного по .формуле (2) для . После выключения RS-три гера 7 из контура генерации, он (RSтриггер) хранит случайное состояние Q, инверсия которого Q поступает в рассматриваемый полутакт (Т 1) на вход блока 10 памяти. Блок 10 памяти при находится в режиме записи в ячейку, из которой перед этим (в момент ) была считана инфорЯация. При подаче сигнала опроса на вход 15 сигнала опроса, на выходе 20 генератора формируется элемент выходной синхронной случайной последовательности. Генерирующий без RS-триггера 7 контур () подготавливает случайную фазу для следующего цикла работь). В следующий такт состояние счетчика 9 адреса увеличится на 1. При происходит чтение из ячейки блока 10 памяти с новым адресом, а при запись случайного символа, сформированного на выходе RS-триггера 7, в эту же ячейку блока 10 памяти. Процесс повторяется. Через г тактов счетчик 9 установится в то же состояние, что и в момент включения генератора. В первый полутакт (при ) на выходе блока 10 памяти считывает ся случайный символ с задержкой на г тактов по сравнению с символами на выходе RS-триггера 7. Во второй полутакт (при ) в ячейку блока 10 памяти с этим же адресом запишется новый случайный символ. Таким образом, на выходе блока 10 памяти будет разворачиваться последователЪность случайных символов, заре держанных по сравнению с инверсным входом RS-триггера 7 на г тактов, В каждый второй полутакт (при ) на выходе 20 устройства формируется случайный символ вида Z X ©Xi-m-10Xi., где 7i- - случайный символ на выходе 20 генератора в i-ii такт; Х- - случайный символ на инверсном выходе RS-триггера -7. В каждый первьй полутакт (при ) на выходе 20 будет случайный символ равный X. ФХ., так как на инверсном выходе RS-триггера 7 при 1 0 уровень логической 1. В режиме контроля (при наладке или ремонте устройства) цепь обратной связи контура генер ацйи необходимо разорвать, подав на вход 18 логический О. Тогда рассматриваемое устройство превращается в детерминированный автомат, контроль работоспособности которого можно осуществить обычными средствами, пользуясь входами 14, 15, 16, 18 и 19, выходами 17 и 20, а также выходами с остальных промежуточных точек cxeh&i (не показаны). Предлагаемое устройство мЬжет быть полностью реализовано на цифровых интегральных микросхемах. Б качестве блока 10 памяти.могут быть использованы, например, vsiKpocxeMbi 134РУ6, 155РУ5, 5001У148, 500РУ4106, 500РУ415 и т.д. При работе известного генератора 3 , генерируется последовательность случайных символов с относительно невысокой равновероятностью и высоким уровнем автокорреляции. По сравнению с известным устройством, предлагаемое позволяет достаточно просто получить некоррелированную последовательность случайных символов с вероятностью появления символа 1 равной 0,5 с высокой точностью. Кроме тогоО предлагаемое устройство позволяет работать при 912754 значительно более высоких тактовых частотах и частотах опроса, чем известное устройство, что обусловлено, во-первых, введением в предлагаемое устройство элемента-повторителя 6, вследствие чего снижается корреляция вносимая тактовыми импульсами в асин хронную последовательность и, вовторых, введением выравнивающего устройства, включающего в себя счетчик 9 адреса, блок 10 памяти, Т-триггер 11 и сумматор 12 по модулю два. Это позволяет на выходе устройства 20 получать синхронную последовательность случайных символов с приемле5fO 15 4 мыми статистическими характеристиками даже тогда, когда на выходе RSтриггера 7 (а следовательно на выходе известного объекта) генерируется последовательность случайных символов с совершенно неприемлемыми статистическими характеристиками. Предлагаемое техническое решение намечено использовать при модернизации устройства ввода случайных чисел ЕС 6903, что позволит получить экономический эффект за счет повышения точности генерирования и повышения быстродействия устройства.

ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕн ДРВАТЕЛЬНОСТИ, содержащий элемент НЕ, элемент И, RS-триггер, три элемента И-НЕ, первый сумматор по модулю два, Т-триггер, группу из 2п-1 (,3...) сумматоров по модулю два, выход каж-дого i-ro ( ,2,...,2п-2) сумматора по модулю два группы соединен с первым входом (i+l)-ro сумматора по модулю два группы, вторые входы первых m (, 2) сумматоров по модулю два группы подключены к выходу элемента НЕ, вход которого соединен с вторыми входами последующих 2n-2-m сумматоров по модулю два группы и с выходом элемента И, первый вход которого является первым входом Контроль генератора, тактовый вход которого соединен с R-входом RS-триггера, первыми входами первого и второго элементов И-НЕ, второй вход Контроль генератора соединен с -вторым входом первого элемента И-НЕ, которого соединен с первым входом третьего элемента И-НЕ, выход которого подключен к S-входу RS-триггера, S-выход которого соеданен с первым входом первого сумматора по модулю два, второй вход которого подключен к выходу второго элемента И-НЕ, отличающийся тем, что, с целью повышения точности, он содержит элемент задержки, второй сумматор по модулю два, блок памяти, счетчик ад(Л реса, выходы разрядов которого подключены к соответствую1 м адресным входам блока памяти, информационный вход которого соединен с первым входом первого сумматора по модулю два группы, с В-выходом RS-триггера и первьм входом второго сумматора по го ел модулю два, второй вход которого подключен к инверсному выходуоТ-триггера, счетный вход которого соединен 4ik СО 4ih с выходом блока памяти, управляющий вход которого соединен со счетным входом счетчика адреса к выходом первого элемента И-НЕ, а инверсный вход Т-триггера подключен к входу Опрос генератора, при этом выход 2п-1-го сумматора по модулю два группы соединен с вторым входом третьего элемента И-НЕ и через элемент задержки с вторым входом второго элемента ИНЕ, выход второго сумматора по модулю два является выходом генератора.