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

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

Иллюстрации

Показать все

Реферат

 

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

СО1ОЭ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1275434 А1 (59 4 О 06

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

Г1О ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblT

ОПИСАНИЕ ИЗОБРЕТЕНИЯ / " д/

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3658550/24-, 24 (22) 31. 10.83 (46) 07. l 2. 86. Вюл. 11 45 (71) Казанский ордена Трудового

Красного Знамени и ордена Дружбы народов авиационный институт ии.

А. Н. Туполева (72) В. А. Песонин, В. М. Кузнецов, Н. Н. Сергеев, О. И. Далин, И,. К. Галеев, Г. Н. Иванов и В. Л. Сафонов (53) 681.325(088.8) (56) Авторское свидетельство СССР

111 306558, кл. Н 03 К 5/08, 1971.

Авторское свидетельство СССР

1040486, кл. G 06 F 7/58, 1979.

Авторское свидетельство СССР

М 962933, кл. G ОЬ F 7/58, 1982.

Федоров Р. Ф., Яковлев В. В., Добрис Г. В. Отохастические преобразователи информации. Л.: Машиностроение, Ленинградское отделение, 1978. (54)(57) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕ11

ДОВАТЕЛЬНОСТИ, содержащий элемент hE, элемент И, HS-триггер, три элемента

И-НЕ, первый сумматор по модулю два, Т-триггер, группу из ?п-1 (n=2 3...) сумматоров по модулю два, выход каж-. дого i-ro (i=1, 2,...,2n-2) сумматора по модулю два пруппы соединен с первым входом (i+1)-го сумматора по модулю два группы, вторые входы первых ш (m=1, 2) сумматоров по модулю два группы подключены к выходу элемента

НЕ, вход которого соединен с вторыми входами последующих 2п-2-m сумматоров по модулю два группы и с выходом элемента И, первый вход которого

11 11 является первым входом Контроль генератора, тактовый вход которого соединен с R-входом RS-триггера, первыми входами первого и второго элементов -HE второй вход "Контроль" генератора соединен с вторым входом первого элемента И-HE выход которого соединен с первым входом третьего элемента И-НЕ, выход которого под- ключен к S-входу BS-триггера, S-выход которого соединен с первым входои первого сумматора по модулю два, второй вход которого подключен к выходу второго элемента И-НЕ, о т л ичающий с я теи, что, с целью повышения точности, он содерхит элемент задержки, второй сумматор по модулю два, блок памяти, счетчик адреса, выходы разрядов которого подключены к соответствующим адресным входам блока памяти, информационный вход которого соединен с первым входом первого сумматора по модулю два группы, с В-выходом BS-триггера и первым входом второго сумматора по модулю два, второй вход которого подключен к инверсному выходуоТ-триггера, счетный вход которого соединен с выходом блока памяти, управляющий вход которого соединен со счетныи входом счетчика адреса и выходом первого элемента И-НЕ, а инверсный вход

Т-триггера подключен к входу "Опрос" генератора, при этом выход 2п-1-ro сумматора по модулю два группы соединен с вторым входом третьего элемента И-НЕ и через элемент задержки с вторим входом второго элемента ИНЕ, выход второго сумматора по модулю два является выходом генератора.

1 12

Изобретение относится к вычислительной технике, технике измерения и связи и может быть использовано в стохастических вычислительных машинах в качестве датчиков случайных чисел для ЦВМ, а также для имитаторов случайных процессов при испытании различной аппаратуры и каналов связи.

Известно устройство, состоящее из генератора обобщенного телеграфного сигнала, подключенного через логические схемы к выходному триггеру, и генерирующее как асинхронную так и синхронную случайные последовательности. (1)

Однако в работе такого устройства возможны сбои, так как на триггер генератора обобщенного телеграфного сигнала воздействуют случайные процессы со спектром, не согласованным с частотными возможностями Т-триггера и остальной части устройства. Возникающие при этом сбои в работе отдельных элементов (в первую очередь триггера генератора обобщенного телеграфного сигнала) прчводят к погрешностям статистических характеристик выходной синхронной случайной последов а тельно ст и.

Известно устройство, представляющее собой соединенные в кольцо асинхронный элемент задержки с отводами, многовходовый сумматор по модулю два и инвертирующий усилитель (2). Устройство постоянно использует естественные флуктуации временных задержек асинхронного элемента задержки для цели формирования случайной последовательности типа обобщенного телеграфного сигнала. Это затрудняет контроль работоспособности устройства, что усложняет технологию наладки и ухудшает ремонтопригодность, следовательно снижает надежность его эксплуатации. Кроме этого, устройство позволяет генерировать только .асинхронную случайную последовательность» что также является еге недостатком.

Наиболее близким техническим решением к предлагаемому является генератор случайной последовательности, представляющий собой соединенные в кольцо многовходовый сумматор по мо.дулю два, состоящий из последовательно соединенных двухвходовых суммато ров по модулю два, элемента И, элемента НЕ, двух коммутаторов, а также

75434 выходного формирователя и специального триггера — посредника (3 1.

Недостатком известного технического решения является относительно невысокая равновероятность и высокий уровень автокорреляции случайных символов в последовательности.

Целью изобретения является повышение качества статистических характеристик случайных символов.

Поставленная цель достигается тем

t что в генератор случайной последовательности, содержащий элемент НЕ, элемент И, RS-триггер, три элемента И-НЕ, первый сумматор по модулю два, T-триггер, группу из 2п-1 (и=

=2, 3, 4...) сумматоров по модулю два, выход каждого i-го (i=1, 2...,, 2п-2) сумматора по модулю два группы соединен с первым входом (i+1)-го сумматора по модулю два группы, вторые входы первых m (mr=i 2...) сумматоров по модулю два группы подключены к выходу элемента НЕ, вход которого соединен с вторыми входами последующих 2п-2-m сумматоров по модулю два и группы и с выходом элемента И, первый вход которого является первым входом "Контроль < генератора, тактовый вход которого соединен с R-входом RS-триггера, первыми входами первого и второго элементов И-НЕ, второй вход "Контроль" генератора соединен с вторым входом

3S первого элемента И-НЕ, выход которого подключен к S-входу RS-триггера, S-выход которого соединен с первым входом первого сумматора по модулю два, второй вход которого подключен

40 к выходу второго элемента И-НЕ, дополнительно введены элемент задержки, второй сумматор по модулю два, блок памяти, счетчик адреса, выходы разрядов которого подключены к соот45 ветствующим адресным входам блока памяти, информационный вход которого соединен с первым входом первого сумматора по модулю два из группы, с

В-входом RS-триггера и с первым входом второго сумматора по модулю два, второй вход которого подключен к инверсному выходу T-триггера, счетный вход которого соединен с выходом блока памяти, управляющий вход которого соединен со счетным входом счетчика адреса и выходом первого элемента И-НЕ, а инверсный вход T1275434 з триггера подключен к входу Опрос" генератора, при этом выход (2n-1)-ro сумматора по модулю два иэ группы соединен с вторым входом третьего элемента И-НЕ и через элемент задержки — с вторым входом третьего элемента И-НЕ, выход второго сумматора по модулю два является выходом генератора, На чертеже представлена схема устройства (согласно требованиям, предъявляемым к изображению схем цифровой вычислительной техники, стрелки на связях отсутствуют, но при этом необходимо полагать, что связь слева элемента означает вход, а связь .справа — выход).

Генератор случайной последовательности состоит из группы сумматоров 1 и 12 е ° ° ° з 12 -1 по мо 20 дулю два, элемента HE 2 элемента

И-НЕ 3, элемента И-НЕ 4, элемента

И-НЕ 5, элементз 6 задержки, RS-триггер 7, первого сумматора 8 по модулю два, счетчика 9 адреса, блока 10 па- д мяти, Т-триггера 11, второго сумматора 12 по модулю два, элемента И 13.

Вход 14 является входом тактовых импульсов, вход 15 — входом "Опрос", Устройство имеет также вход 16 обратной связи, выход 17 обратной связи, входы 18 и 19 контроля и выход

20 генератора.

Элемент HE 2 используется для увеличения нагрузочной способности (ко35 эффициента разветвления по выходу) элемента И 13. В качестве него может быть использован инвертор или группа инверторов, обеспечивающих надежное формирование логических уровней напряжения с выхода элемента И 13, подаваемых на необходимое (достаточно большое) количество входов групп сумматоров 1 по модулю два.

В качестве блока 10 памяти может быть использована матрица-накопитель

ОЗУ с организацией r l (т.е. в памяти ячеек по одному биту каждая). При этом коэффициент пересчета счетчика

9 адреса должен составлять r, 50

Элемент-повторитель 6 служит для сохранения неизменным числа задержек элементов в контуре генерации асинхронной случайной последовательности при логическом "0" или "1" íà вь1хо55 де 14 тактовых импульсов. В качестве элемента-повторителя 6 может быть применен, например, элемент ИЛИ, Ген ер атор р або то способен при любом способе (в том числе и при спо- собе, показанном на чертеже) подключения вторых входов сумматора 1 по модулю два группы к выходу и входу элемент" HE 2, Однако более предпочтительно подключение входов сумматоров 1 группы в соответствии с табгпцей непривоцимых полиномов 4

Состояние элемента И 13 определяет режим работы устройства. Ксгда;=а вход 18 подана логическая "1", то это соответствует рабо ему состоянию, т.е. состоянию генерирования случайных последовательностей. При -. одаче логического "0" на контрольный вход

18 устройство переходит в режим кон-. троля, когда есть возможность проверить устройство как детерминированжш автомат (без генерации случайного процесса).

В рабочем режиме при действии по входу 14 тактового сигнала Т=О образуется контур обратной связи, состоящий из блоков 1, 4, 7, 8, 13 и 2, При T=l образуется также контур обратной связи, но уже из блоков 1, 6, 5, 8, 13 и 2. В обоих случаях в контур обратной связи входят блоки

l 8, 13 и 2, но при T=0 в этот кон тур включаются блоки 4 и 7 вместо блоков 6 и 5, которые входят в контур при T=l. Аналогично, как и в известном устройстве (3), под действием даже малых естественных флуктуаций временных задержек блоков 13, 2, 4, 5, 6 и 7 и блока l по каждому из

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

К 1

Y Q1Q+(ASY) 10+(A9Y)SH) 8(A8Y

i=0 i=1

8С) твх= (1) где Y=0 1 — сигнал с выхода сумматора 1;

A=0, 1 — опер атор инверсии элемента НЕ 2;

В=0 1

С=О,Ч

Хо,l

K H l э ! 275 оператор инверсии последовательно соединенных элементов 6, 5, и 8 (при T=l ); оператор инверсии после- 5 довательн соединенных элементов 4, 7 и 8 (при Т=О); сигнал настройки, подаваемый на вход первого Ip сумматор по модулю.два группы I; соответственно объем первой и второй групп входов группы сумматора 1, причем К+1 2п-2, Оператор инверсии какого-либо блока обозначает следующее: если он равен О, то данный блок не инвертиру- 20 ет сигнал, поданный на его вход, а если равен 1, то - инвертирует. Формула (1 ) справедлива, когда сумматор 12 имеет оператор инверсии, равный О. 25

Упрощая выражение (1) и разрешая

его относительно Х, получаем более удобную формулу для вычисления сигнала настройки, подаваемого на вход пер-. вого сумматора по модулю два группы l Ç0

1+1

Х=А 18ВТЮСТЭ1. (2)

i-=1

Например, пусть элемент HE 2 ин вертирует сигнал (А 1), блоки 4, 7 и 8 не инвертируит (В С=О), а 1— четное число, тогда получаем Х 0 (для любого T--О,I). При таком Х в . контуре всегда будет стремиться выполняться логически противоречивое 40 условие У=Y (т.е. ТО), благодаря чему будет поддер яваться устойчивый нроцесс генерации асинхронной случайной последовательности.

В паузе между тактовыми импульса- 45 ми (при Т=О} RS-триггер 7 включается в контур, а в момент действия тактовых импульсов (при Т=l) выключается из него, устанавливаясь при этом в случайное состояние, и формирует с помощью выравнивающего устройства, включающего блоки 9-12, элементы выходной последовательности — случайные символы. Такая организация работы устройства исключает сбои RS-тригЫ гера 7 по причине конечного его быстродействия, так как скорость протекания процессов в контуре всегда согласована с минимальным быстродейст434 Ь вием входящих в него блоков, в том числе и RS-триггера 7.

Элемент-повторитель 6 с временем задержки примерно равным времени задержки RS-триггера 7 по асинхронным входам способствует устранении корреляции, вносимой тактовыми импульсами в асинхронную случайную последовательность. Элементу повторитель

6 обеспечивает примерное равенство суммарного времени задержки блоков

4, 7 и 8 (при ТО) и суммарного времени задержки блоков 6, 5 и 8 (при

Т** l ) .

Блоки 9-12 образуют выравнивающее и декоррелируищее устройство. Счетчик 9 пересчитывает тактовые импульсы, поступающие с входа тактовых импульсов 14 и задает последовательные адреса ячеек блока 10 памяти. Тактовые импульсы, проинвертированные элементом И-HE 3, поступая на управляющий вход 10 памяти, задают режимы чтения (при T=Î) либо записи (при

T=l). Случайные символы, сформированные на выходе RS-триггера 7 (при Т

=1) записываются в блок 10 памяти и затем считываются из него через r тактов. Задержанная на г тактов случайная последовательность с выхода блока 10 памяти поступает на счетный вход Т-триггера 11. Т-триггер II осуществляет пересчет задержанной последовательности случайных символом, дополнительно выравнивая вероятность появления символа "I" в случайной последовательности до 0,5. На первый вход сумматора 12 по модулю два поступает последовательность случайных символов с выхода RS-триггера 7, а на второй вход блока 12 поступает с выхода блока ll та же последовательность, но задержанная íà r тактов и пересчитанная по модулю два. При условии, что число ячеек в блоке 10 памяти больше интервала автокорреляции последовательности случайных символов, формируемых на выходе НБ-триггера 7, на выходе генератора 20 будет развертываться декоррелированная последовательность случайных симво- лов.

Устройство работает следующим образом.

Пусть в рабочем режиме по входу

14 тактовых импульсов проходит сигнал T=O. Он переключает сигнал с выхода (2п-1)-ro сумматора I по модулю два группы на последовательно соеди7 12754 ненные элемент И-НЕ 4, RS-триггер 7, сумматор 8 по модулю два. На вход первого сумматора 1 по модулю два группы подан сигнал Х, рассчитанный по формуле (2) для Т=О, благодаря чему выполняется условие (1) и в соответствующем контуре развивается асинхронный случайный процесс.

RS-триггер 7 при этом также беспрерывно случайным образом переклю- 10 чается. Формирование выходного элемента синхронной случайной последовательности на инверсном выходе RSтриггера 7 при этом не происходит.

Блок памяти при этом находится в ре- 15 жиме чтения из ячейки с адресом, равным состоянию счетчика 9 адреса.

В момент действия сигнала T=l из контура генерации выключаются элемент И-НЕ 4 и RS-триггер 7, но гене- 20 рация в контуре продолжается, так как контур остается замкнутым с выхода (2n-1)-го сумматора 1 по модулю два группы через последовательно соединенные элемент-повторитель 6, элемент И-НЕ 5 и сумматор 8 по модулю два, на вход элемента И 13. При этом выполняется условие 1, благодаря подаче на вход первого сумматора

" 1 по модулю два группы сигнала на- 30 стройки Х, рассчитанного по .формуле (2) для T — 1. После выключения BS-триггера 7 из контура генерации, он (BSтриггер) хранит случайное состояние

Я, инверсия которого Ц поступает в рассматриваемый полутакт (Т=l) на вход блока 10 памяти. Блок 10 памяти при T=l находится в режиме записи в ячейку, из которой перед этим (в момент Т=О) быпа считана информация.

При подаче сигнала опроса на вход 15 сигнала опроса, на выходе 20 генера- тора формируется элемент выходной синхронной случайной последовательности. Генерирующий без RS-триггера

7 контур (T=l) подготавливает случайную фазу для следующего цикла работы. В следующий такт состояние счетчика 9 адреса увеличится на 1.

При Т=l происходит чтение из ячейки блока 10 памяти с новым адресом, а при Т=О запись случайного символа, сформированного на выходе RS-триггера 7, в эту же ячейку блока 10 памяти. Процесс повторяется. Через r тактов счетчик 9 установится в то же состояние, что и в момент включения генератора. В первый полутакт (при

34 8

Т=O) на выходе блока 10 памяти считывается случайный символ с задержкой íà r тактов по сравнению с символами на выходе RS-триггера 7. Во второй полутакт (при T=O) в ячейку блока 10 памяти с этим же адресом запинется новый случайный символ. Таким образом, на выходе блока 10 памяти будет разворачиваться последователЪность случайных символов, заде держанных по сравнению с инверсным входом BS-триггера 7 на r тактов. В каждый второй полутакт (при Т=!) на выходе 20 устройства формируется случайный символ вида

21=Х,ОХ; -m-la++X. где Х. †случайный символ на выходе

20 генератора в 1-и такт;

Х вЂ” случайный символ на инверс1 ном выходе RS-триггера 7;

В каждый первый полутакт (при

Т=О) на выходе 20 будет случайный символ равный Х, @+X., так как на инверсном выходе ВЯ-триггера 7 при Т=O уровень логической "1".

В режиме контроля (при наладке или ремонте устройства) цепь обратной связи контура генерации необходимо разорвать, подав на вход 18 логический "О". Тогда рассматриваемое устройство превращается в детерминированный автомат, контроль работоспособности которого можно осуществить обычными средствами, пользуясь входами 14, 15, 16, 18 и 19, выходами 17 и 20, а также выходами с остальных промежуточных точек схемы (не показаны)

Предлагаемое устройство может быть полностью реализовано на цифровых интегральных микросхемах. В качестве блока 10 памяти могут быть использованы, например, микросхемы 134РУ6, 155РУ5, 500РУ148, 500РУ4106, 500РУ415 и т.д.

При работе известного генератора

3, генерируется последовательность случайных символов с относительно невысокой равновероятностью и высоким уровнем автокорфеляции.

По сравнению с известным устройством, предлагаемое позволяет достаточно просто получить некоррелиро» ванную последовательность случайных символов с вероятностью появления символа 1 равной 0,5 с высокой точностью. Кроме тогоО предлагаемое устройство позволяет работать при

Составитель а. Карасов

Техред Н, Глущенко

Ф

Редактор В. Иванова

Корректор А. Тяско

Заказ 6561/40 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

ll303S, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

9 1275434 10 значительно более высоких тактовых мыми статистическими характеристикачастотах и частотах опроса, чем из-,ми даже тогда, когда на выходе RS1 вестное устройство, что обусловлено, триггера 7 (а следовательно на выхо во-первых, введением в предлагаемое де известного объекта) генерируется устройство элемента-повторителя 6, последовательность случайных симвовследствие чего снижается корреляция, лов с совершенно неприемпеьыми ставносимая тактовыми импульсами в асин- тистическими характеристиками. хронную последовательность и, вовторых, введением выравнивающего уст- Предлагаемое техническое решение ройства, включающего в себя счетчик 10 намечено использовать при модерни9 адреса, блок 10 памяти, Т-триггер зации устройства ввода случайных чи11 и сумматор 12 по модулю два. Это can EC 6903, что позволит получить позволяет на выходе устройства 20 экономический эффект за счет повыполучать синхронную последователь- шения точности генерирования и повыность случайных символов с приемпе- )S шения быстродействия устройства,