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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6t) Дополнительное к авт. свид-ву— (22) Заявлено01.04.81 (21) 3267200/18-24

Р1 М К з

G 06 F 7/58 с присоединением заявки №,Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет (531 УДК681. 325 (088 ° 8) Опубликовано. 3Q0982 ° Бюллетень ¹ 36

Дата опубликования описания 30.09.82

В. A. Песошин, В. Ф. Гусев, И. К. Галеев.,: О. Й. Датйпт;

Г. Н. Иванов, В. И. Кузнецов и Г. И. Кренгель (72) Авторы изобретения

Казанский ордена Трудового Красного Зн авиационный институт им. A.Н. Туполе (71) Заявитель (54) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛГДОВАТЕЛЬНОСТИ

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

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

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

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

Устройство постоянно использует

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

2О позволяет генерировать только асинхронную случайную последовательность, что также является его недостатком.

Цель изобретения — повышение надежности работы и расширение функциональных возможностей генератора за счет дополнительного формирования синхронной случайной последовательности

Поставленная цель достигается тем, что генератор случайной последовательности, содержащий элемент .НЕ, группу

962933 из 2п-1 (n = 2, 3, 4 ...) сумматоров ,пО модулю два, выход каждого i-го (i = 1, 2, ..., Zn-2) сумматора по модулю два группы соединен с первым входом (i+1)-го сумматора по модулю два группы, введены три элемента S

И-HE сумматор п о модулю два, RS1триггер, T-.iiðèããåð и элемент И, пер-„ вый вход zoòoðaão является первым управляющим входом генератора, выход ; (Zn-1)-го сумматора по модулю дна 10 группы соединен с вторым нходом элемента И, выход которого соединен с входом элемента НЕ, выход которого соединен с вторыми входами первых

m(m = 1, 2, ...) сумматоров по модулю дна группы, вторые входы последующих 2п-2-m сумматоров по модулю два группы подключены к выходу элемента

И, второй вход (2п-1) -ro сумматора по модулю дна группы соединен с инфнерсным выходом RS-триггера и со счетным входом Т-триггера, выход которого является выходом генератора, а синхронизирующий вход Т-триггера является входом "Опрос" генератора, тактовый вход которого соединен, с первыми входами первого и второго элементон И-НЕ и с инверсным входом

RS-триггера, выход которого соединен с первым входом сумматора по модулю два, выход которого соединен с первым входом первого сумматора по модулю два группы; второй управляющий вход генератора соединен с вторым входом второго элемента И-НЕ, выход которого соединен с первым входом 35 третьего элемента И-HE выход которо го соединен с прямым входом RS-триггера„ выход элемента НЕ соединен с вторыми входами первого и третьего элементов И-НЕ. 40

На чертеже приведена блок-схема предлагаемого генератора.

Генератор случайной последовательности состоит из 2п-входового сумматора 1 по модулю два,.усилителя-формирователя 2, коммутатора-селектора 3, коммутатора-мультиплексора 4, триггера 5 и выходного формирователя.б.

Вход 7 является входом тактовых им.пульсов, вход 8 — входом сигнала опроса, а вход 9 — входом сигнала настройки. Коммутатор-селектор 3 выполнен на . основе элементов 3, и 3 И-НН, коммутатор-мультиплексор. 4 — на основе элемента 4„ И-НЕ и Двухвходового сфмматора 4 по модулю два, а сумматор 1 по модулю два — на основе двухвходовых сумматоров Ъ, 1

1 ) 1, 1S ° ° ° ф 1 4ф 1 -по модулю два. Устройство имеет .также вход 10 обратной связи, выход 11 обратной - бО связи, ключ 12 обратной связи и входы

13 и 14 контроля.

Выход сумматора 1 через ключ 12

-соединен с одной, а дополнительно через усилитель-формирователь 2 —,,б5 с другой группой своих входов. Выход усилителя-формирователя 2 соединен также со входом коммутатора-селектора 3. Один выход коммутатора-селектора 3 соединен непосредственно с одним входом коммутатора-мультиплексора 4, а другой выход через единичное плечо триггера 5 — с соотнетствующим входом коммутатора-мультиплексора 4. Генера тор тактовых импульсов через вход 7 подсоединяется к управляющим входам коммутатора-селектора 3, коммутатора,мультиплексора 4 и к нулевому входу триггера 5. Источник сигнала опроса .подсоединяется через нход 8 к соот-, ветствующему входу выходного формирователя б. На вход 9 подают сигнал настройки. Выход выходного формирователя 6 является выходом всего устройства.

2п-входоный сумматор 1 по модулю дна состоит йз 2п-1 последовательно соединенных сумматоров 1„, 1„, 16 к 17 г 1 gю i ° ф 1. 1, IIQ модулю дна на два входа (где п = 8). Коммутатор-селектор 3 выполнен на двух последовательно соединенных элементах 3 и 3 И-HE. Вход коммутатораселектора 3 подсоединен к одному из входов элемента 3 И-НЕ и является

2 одним из его выходов, подсоединяемых к коммутатору-мультиплексору 4. Управляющий вход коммутатора-селектора 3 является входом элемента 3> И-НЕ.

Второй вход элемента 34 И-HE является входом 14 контроля. Коммутатормультиплексор 4 состоит из последовательно соединенных элемента 4 И-HE и двухнходоногосумматора 4< по модулю два. Один вход элемента 4 И-HE и один вход двухвходового сумматора

4 по модулю два являются входами коммутатора-мультиплексора 4, а другой вход элемента 4А И-НЕ является управляющим входом коммутатора-мультиплексора 4. Соединение выхода двухвходового .сумматора 1., по модулю два через ключ 12 с выходами соответствующих блоков образует цель обратной .связи. Вход 9 настройки подсоединен к инверсному выходу триггера 5.

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

Коммутатор-селектор 3 Осуществляет переключение сигнала с одного входа на один из двух выходов, а комаутатсрмультиплекстор 4 обеспечивает обратную коммутацию, т.е. переключение сигнала с одного иэ двух входов на выход.

96 2933

С = 0,1

УпРавление работой обоих коммутаторов

3 и 4 осуществляется посредством тактовых импульсов со входа 7.

В качестве триггера 5 используется асинхронный триггер с установочными входами (асинхронный RS-триггер). 5

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

Генератор работоспособен при любом способе построения 2п-входового 20 сумматора 1 по модулю два, но последовательное соединение Zn-1 двухвходовых сумматоров по модулю два для этой цели более предпочтительно (где и =,2, 3, 4, ...). Данный вариант реализации сумматора 1 представлен на чертеже для случая n = 8. Такая организация схемы обеспечивает лучшие характеристики и более надежную работу всего устройства. 2п-1 (нечетное число) входов сумматора 1 используются для образования обратной связи, а вход 9 служит для настройки всего контура обратной связи на режим устойчивого генерирования первичной асинхронной случайной последова- З5 тельности.

В качестве ключа 12 используют, например коньюктор, управляемый от сигнала контроля по входу 13, или обычную монтажную перемычку. Состо- 40 яние ключа 12 определяет режим работы устройства. Когда ключ 12 открыт, следовательно контур обратной связи замкнут (например, подана лбгическая

"1" на вход 13 коньюктура или реализована перемычка), то это соответствует рабочему состоянию, т.е. состоянию генерирования случайных последовательностей. Запретное состояние ключа 12, т.е. Разорванный контур $g обратной связи (например, подачей логического "0" на вход 13 коньюнктора или изъятием перемычки) соответствует режиму контроля, когда устройство проверяется как детерминированный 55 автомат (без генерации случайного процесса) .

В рабочем режиме при действии по входу 7 тактового сигнала T = 0 образуется контур обратной связи, состоящий из блоков 1, 12, 2, 2, 3, 46

5 и 4. При Т = 1 образуется также контур обратной связи из блоков 1, 12, 2, 3 и 4. В обоих случаях сущест.вует контур обратной связи, состоящий из сумматора 1 по модулю два с нечетным количеством входов (2п-1, где n = 2, 3, 4, ..., не учитывая входа 9) блоков 12, 2, 3, 4 и при

Т 0 блока 5, осуществляющих вместе со всеми отдельными 2п-1 входами сумматора 1 по модулю два операцию непрерывной (асинхронной) задержки логических сигналов. Аналогично, как и в известном устройстве под действием даже малых естественных флуктуаций временных задержек блоков 12, 2, 3, 4, 5 и блока 1 по каждому из 2п-1

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

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

В . 1 ®(Д®Y) g g(g =1 s--1 .

Ж(А® (О+В)1®(ДО+ (9С) Т®Х=7 (1) где У = 0,1 — сигнал с выхода сумматора 1;

А = 0,1 — оператор инверсии уси- лителя-формирователя 2;

В = 0,1 - оператор инверсии последовательно соединенных коммутаторов

3 и 4 (при Т = 1); оператор инверсии госледовательно соединенных коммутатора 3, триггера 5 и коммутатора 4 (при Т = О);

Х = 0,1 — сигнал настройки, подаваемь и на вход 9;

К и :f - соответственно объем первой и второй групп входов сумматора 1, причем К + L = Zn-2.

Оператор инверсии какого-либо блока обозначает следующее если он ра) вен О, то данный блок не инвертирует сигнал, подаваемый на его вход„ а если равен 1, то — инвертирует. Формула (1) справедлива, когда ключ 12 имеет оператор инверсии, равный О.

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

его относительно Х, получаем более

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

М

X=A Е10+Втоет О+ i, (2)

1=1

Например, пусть усилитель-формирователь 2 инвертирует сигнал (А = 1), блоки 3-5 не инвертируют (В = С = 0), 1 а Ь вЂ” четное число, тогда получаем

Х = 0 (для любого Т = 0,1).

При таком Х в контуре всегда выполняется логически противоречивое усло- 10 вие Y = 7(т.е. 1 = О) благодаря чему . поддерживается устойчивый процесс генерации асинхронной случайной после,довательности.

Благодаря работе коммутаторов 3 15 и 4 триггер 5 осуществляет посредничество между генерирующим асинхронную случайную последовательность контуром и формирующим выходную синхронную слу-. чайную последовательность выходным, 7п формирователем 6, т.е, в паузе .между тактовыми импульсами (при Т = О) триггер 5 включается в контур, а в момент действия тактовых импульсов (при Т = 1) выключается из него, ус-танавливаясь при этом в случайное . ,,состояние и формирует с помощью выходного формирователя 6 элементы выходной последовательности. Такая организация работы устройства исключает сбои триггера 5 по причине конечности его быстродейстивя, так как скорость протекания процессов в контуре всегда согласована с,минимальным быстродействием входящих в него блоков. Например, если быстродействие триггера 5 оказывается меньше быстродействия блоков 1, 12, 2, 3 и 4, то при Т = О минимально возможные длительности элементов асинхронной последовательности в контуре возрас- 40 тают до величины, допустимой для нормального срабатывания данного триггера. A если триггер 5 просто подключается к контуру, то он не успевает переработать некоторые фрагменты 45 асинхронной последовательности, что: приводит к погрешностям формирования синхронной случайной последовательности.

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

Пусть в рабочем режиме по входу 7 от генератора тактовых импульс ив прихоцит сигнал Т = О. Он переводит работу коммутаторов 3 и 4 в такой режид, что сигнал с выхода усилителяформирователя 2 проходит последовательно через коммутатор 3, триггер 5 и коммутатор 4 на отдельный вход сумматора 1. На вход 9 подается сигнал

Х, рассчитанный по Формуле (2) для

Т = О, благоцаря чему выполняется условие (1) и в конутре развивается асинхронный случайный процесс (аналогично), как и в известном устройстве. Триггер 5 при этом также беспрерывно случайным образом переключается. Формирование выходного элемента синхронной случайной последовательности при этом не происходит. В момент действия Т = 1 триггер 5, со случайно установленным состоянием выключается из контура, но контур продолжает свою работу, так как сигнал с выхода усилителя-формирователя 2 проходит на отдельный вход сумматора 1 через последовательно соединенные коммутаторы 3 и 4, выполняется условие (1), благодаря подаче на вход 9 сигнала настройки Х, рассчитанного по формуле (2) для Т = 1. В этот же момент триггер 5 передает своим состоянием О случайный символ в выходной формирователь б. При подаче сигнала опроса на вход 8, формирователь б выдает элемент выходной синхронной 1глучайной последовательности. Генерй рующий без триггера 5 контур подго- таливает случайную фазу для следующвго цикла работы.

Аналогичным образом Описывается работа устройства и по более подробной схеме, изображенной на чертеже (с учетом конкретной реализации его блоков) . B качестве триггера 5 применяется асинхронный RS-триггер с инверсными .установочными входами.

Формирователь б выполнен на Т -триггере, счетный вход которого подключен к инверсному выходу триггера 5.

В качестве ключа 12 используется перемычка. В рабочем режиме на вход 14 контроля необходимо подать 1. При

T = 0 со входа 7 элемент 4 И-НЕ за4 крывается и сигнал с выхода инвертора 3 (в качестве усилителя-Формирователя) проходит через элемент 3, единичное плечо триггера 5 и двухвходовой сумматор 4 на вход двухвходового сумматора 1 . Случайный про"" цесс, действующий в контуре, заставляет случайным образом переключаться и единичное плечо триггера 5, при этом нулевое плечо под действием

Т = 0 находится в единичном (детерминированном) состоянии. Сигнал Т = 1 запирает элемент 3 И-НЕ и открывает элемент 4 И-НЕ, пропуская тем самым сигнал с выхода инвертора 2 мимо триггера 5 на вход сумматора 1 и сохраняя рабочий режим контура.

В этот момент триггер 5 Устанавливается в устойчивое (случайное) состояние Q = 01. Сигнал Q действует на счетный вход Т-триггера б формируя таким образом выходной сигнал при условии действия по входу 8 разрешающего сигнала опроса, равного 1. 3аметим, что на инверсном выходе триггера 5 Формируется тактированная последовательность случайных символов вида T V Q = Tg, обеспечивая тем самым возможность применения в качестве формирователя 6 простого асин962933

10 и хронного T-триггера, тогда на вход 8 необходимо подать постоянный разрешающий сигнал опроса, равный 1. Кроме того, сигнал с инверсного выхода триггера 5 используют в качестве сигнала ,настройки, подаваемого на вход 9. 5

Анализируя инвертирующие свойства, блоков 2, 3 4 и 5 можно записать

А = 1, В = Q и С = 1. В данной схеме

6 = б .. Подставляя эти значения в

Формулу (2), получаем Х = QT, что и требовалось доказать.

В режиме контроля (при.наладке или .ремонте устройства) цель обратной связи контура необходимо разорвать ключом 12 (a данном случае перемыч- . 15 кой). Тогда рассматриваемое устройство превращается в детерминированный автомат, контроль работоспособности ко.«торого осуществляют обычными тестовЯми средствами, пользуясь входами 7, 8 щ .10 и 14, выходом 11, выходом яригге-. ра б, а также выходами с остальных промежуточных точек схемы. Подавая определенные двоичные комбинации на входы 7, 8, .10 и 14 обеспечивают для данной конкретной схемы устройства все возможные переходы автомата. Неисправность, выявленная на данном этапе контроля, соответствует неисправности и генератора случайной последовательности (с замкнутой цепью обратной связи) уже как вероятностного автомата.

Описанное конкретное устройство хорошо реализуется на 6-и корпусах цифровых микросхем серии 155, т.е. в качестве блоков 4, 1„, 1 ..., 1 используют элементы четырех корпусов микросхем 155ЛП5, блоки 2, 3, 3 и Q легко реализуются на одном корпусе микросхемы ХЛБ553, в.качестве 40 триггера 5 используют асинхронную ,часть (выходной RS-триггер) D-триг.гера микросхемы 1ТК552, выходной формирователь 6 в этом случае. строят на основе второго D-триггера кор- 45 пуса микросхемы ITK552, т.е. соедицяя его инверсный выход с D-входом, получаем по.синхровходу T-триггер, на нулевой установочный вход (%) в рабочем режиме (по входу 8 устройства необходимо подать постоянный разрешающий сигнал опроса, равный 1.

Благодаря коммутируемой с помощью ключа 12 обратной связи и наличию входов KoHTpoJ1H устройство B режиме контроля допускает достаточно подроб" . ную проверку его работоспособности, а в рабочем режиме формирует как асинхронную, так и синхронную (посредством работы блоков 5 и 6) случайные последовательности, что выгодно отлиЧает предлагаемый генератор от известных.

Кроме того, использование в качестве выходного формирователя счетного триггера улучшает статистические ха- 6З рактеристики выходного процесса (за счет дополнительного суммирования по модулю два) .

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

Формула изобретения

Генератор случайной последователь- ности, содержащий элемент НЕ, группу из 2п-1 (n = 2, 3, 4 . ° .) сумматоров по модулю два, выход каждого 1-го (i = 1, 2, ..., Zn-Z) сумматора по модулю два группы соединен с первым входом (i+ 1) -го сумматора по модулю два группы, отличающийся тем, что, с целью повышения надежности генератора, он содержит три элемента И-НЕ, сумматор по модулю два, RS-триггер, Т-триггер и элемент И, первый вход которого является первым управляющим входом генератора, выход (2n- 1) -го сумматора по модулю два группы соединен с вторым входом элемента И, выход которого соединен с входом элемента НЕ, выход которого соединен с вторыми входами первых

m (m = 1, 2, ...) сумматоров по модулю два группы, вторые входы последующих 2п-2-m сумматоров по модулю два группы подключены к выходу элемента И, второй вход (Zn-1)-ro сумматора по модулю два группы соединен с инверсным выходом RS-триггера и со счетным входом Т-триггера, выход которого является выходом генератора, а синхронизирующий вход T-триггера является входом "Опрос" генератора, тактовый вход которого соединен с первыми входами первого и второго элементов И-НЕ и с инверсным входом

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

Источники информации, принятые во внимание при экспертизе

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

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

2. Авторское свидетельство СССР по заявке 9 2822848/18-24, кл. G 06 Р 7/58, 1979 (прототип).

962933

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

Редактор Ю. Середа Техред Т.Фанта Корректор Л. Бокшан

Заказ 7514/69 Тираж 731 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП ."Патент", r. Ужгород, ул. Проектная, 4