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

Изобретение относится к вычислительной технике, технике измерения и связи и может быть использовано в стохастических вычислительных машинах, в качестве датчиков случайных чисел для ЦВМ, а также для имитаторов случайных процессов при испытании различной аппаратуры и каналов связи Известно устройство, состоящее из генератора обобщенного телеграфного сигнала, подключенного через ло гические схемы к выходному триггеру, и -генерирующее как асинхронную, так и синхронную случайные последователь ности Однако в работе этого устройства возможны сбои, так как на триггер генератора обобщенного телеграфного сигнала воздействуют случайные процессы со спектром, несогласованным с частотньоми возможностями триггера и остальной части устройства. Возникающие при этом сбои в работе отдель ных элементов (в первую очередь триг гера генератора обобщенного телегра ного сигнала) приводят к погрешностям статистических характеристик выходно синхронной случайной последовательно ти. Наиболее близким к предлагаемому является генератор случайной последовательности, представляющий собой со-, единенные в кольцо асинхронный элемент задержки с отводами, многовходовой сумматор по модулю два и инвертирующий усилитель (2j. Устройство постоянно использует естественные флуктуации временных задержек асинхронного элемента, задержки для цели формирования случайной последовательности типа обобщенного телеграфного сигнала. Это затрудняет контроль работоспособности устройства, что усложняет технологию наладки и ухудшает ремонтопригодность, следовательно, снижает надежность его эксплуатации. Кроме этого, устройство позволяет генерировать только асинхронную случайную последовательность, что также является его недостатком. Цель изобретения - повышение надежности работы и расширение функциональных возможностей генератора за счет дополнительного формирования синхронной случайной последовательности . Поставленная цель достигается тем, что генератор случайной последовательности, содержащий элемент -НЕ, группу;

ИЗ 2n-1 (n 2, 3, 4 ...J сумматороы .по модулю два, выход каждого i-ro (i 1, 2 , ..., 2n-2) сумматора по модулю два группы соединен с первым входом (i+1)-ro сумматора по модулю два группы, введены три элемента И-НЕ, сумматор по модулю два, RS риггер, Тгг риггер и элемент И, пер-; вый вход которого является первым управляющим входом генератора, выход (2п-1)-го сумматора по модулю два группы соединен с вторым входом элемента И, выход которого соединен с входом элемента НЕ, выход которого соединен с вторыми входами первых m(m 1, 2, ...) сумматоров по модулю два группы, вторые входы последующих 2n-2-m сумматоров по модулю два группы подключены к выходу элемента И, второй вход 2п-1)-го сумматора по модулю два группы соединен с иноверсным выходом RS-триггера и со счетным входом Т-триггера, выход которого является выходом генератора, а синхронизирующий вход Т-триггера является входом Опрос гелератора, тактовый вход которого соединен . с первыми входами первого и второго элементов И-НЕ и с инверсным входом RS-триггера, выход которого соединен с первым входом сумматора по модулю два, выход которого соединен с первым входом первого сумматора по модулю два группы второй управляющий вход генератора соединен с вторым входом второго элемента И-НЕ, выход которого соединен с первым входом третьего элемента-И-НЕ, выход которого соединен с прямым входом RS-триггера, выход .элемента НЕ соединен с вторыми входами первого и третьего элементов И-НЕ.

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

Генератор случайной последовательности состоит из 2П-ВХОДОВОГО сумматора 1 по модулю два,.усилителя-формирователя 2, коммутатора-селектора 3 коммутатора-мультиплексора 4, триггера 5 и выходного фор1ЙЬователя .6 . Вход 7 является входом тактовых импульсов, вход 8 - входом сигнала опроса, а вход 9 - входом сигнала настройки. Коммутатор-селектор 3 выполнен на . основе элементов 3j и 3, И-НВ кс ммутатор-мультиплексор; 4 - на осно вв элемента 4 И-НБ и Дйухвходового ci iMaTopa 4 по модулю два, а сумматор 1 по модулю два - на основе двухвходовых сумматоров 1 , 1, ..-, 1, 1, Ig, ..., 1.J4/ модулю два. Устройство имеет также вход 10 Обратной связи, выход 11 обратной связи, ключ 12 обратной свяэи и входы 13 и 14 контроля.

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

. 2п-входрвый сумматор 1 по модулю два состоит из 2п-1 последовательно соединенных суГ маторов 1; , 1,,

ly в

, 1 по модулю

6

два на два входа (где n 8). Коммутатор-селектор 3 выполнен на двух последовательно соединённых элементах 3 и За. И-НЕ. Вход коммутатораселектора 3 подсоединен к одному из входов элемента и является одним из его выходов, подсоединяемых к коммутатору-мультиплексору 4. Управляющий вход коммутатора-селектора 3 является входом элемента 3 И-НЕ. Второй вход элемента 3 И-НЕ является входом 14 контроля. Коммутатормультиплексор 4 состоит из последовательно соединенных элемента 4 И-НЕ и двухвходового сумматора 4 по модулю два. Один вход элемента 4 И-НЕ и один вход двухвходового сумматора 0 4,2 по модулю два являются входами коммутатора-мультиплексора 4, а другой вход элемента 4 И-НЕ является управляющим входом коммутатора-мультиплексора 4. Соедийение выхода двухвходового .сумматора 1 модулю два через ключ 12 с выходами соответствующих блоков образует цепь обратной .связи. Вход 9 настройки подсоединен к инверсному выходу триггера 5.

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

1и на вход коммутатора-селектора 3.

Коммутатор-селектор 3 осуществляет переключение сигнала с одного входа на один из двух вькодов, а ко№ утатормультиплекстор 4 обеспечивает обратную коммутацию, т.е. переключение сигнала с одного из двух входов на выход. Управление работой обоих коммутаторо 3 и 4 осуществляется посредством так товых импульсов со входа 7. . В качестве триггера 5 используетс асинхронный триггер с установочными входами (асинхронный RS-триггер). Выходной формирователь 6 осуществляет формирование выходной случайно синхронной последовательности, В дан ном качестве можно применить, например коньюнктор или синхронный D-трй ер. Однако лучшие результаты получа ются при использовании в качестве ВЁР ходного формирователя 6 Т-триггера (счетного триггера). В этом случав статистические характеристики выходного процесса дополнительно улучшаются операцией суммирования по модулю два, осуществляемой Т-триггером. Генератор работоспособен при любом способе построения 2п- цхрдового сумматора 1 по модулю два, но -последовательное соединение 2п-1 двухвходовых сумматоров по модулю два для этой цели более предпочтительно (где п ,2, 3, 4, ...) Данный вариант реализации сумматора 1 представлен на чертеже для случая п 8. Такая организация схемы обеспечивает лучшие характеристики и более надежную работу всего устройства. 2п-1 (нечет ное число) входов сумматора 1 исполь зуются для образования обратной связи, а вход 9 служит для настройки всего контура обратной связи на режим устойчивого генерирования первич ной асинхронной случайной последова тельности. В качестве ключа 12 используют, например коньюктор, управляемый от сигнала контроля по входу 13, или обычную монтажную перемычку. Состояние ключа 12 определяет режим работы устройства. Когда ключ 12 открыт, следовательно контур обратной связи замкнут (например, подана логическая 1 на вход 13 коньюктура или реализована перемычка), то это соответствует рабочему состоянию, т.е. состоянию генерирования случайных последо вательностей. Запретное состояние ключа 12, т.е. разорванный контур обратной связи (например, подачей ло гического О на вход 13 коньюнктора или изъятием перемычки) соответствует режиму контроля, когда устройство проверяется как детерминированный автомат (без генерации случайного процесса). В рабочем режиме при действии по входу 7 тактового сигнала Т О образуется контур обратной связи« состоящий из блоков 1, 12,2, 2, 3, 5 и 4. При Т 1 образуется также контур обратной связи из блоков 1, 12, 2, 3 и 4. В обоих случаях сущест вует контур обратной связи, состоящий из сумматора 1 по модулю два с нечетным количеством входов (.2п-1, где п 2, 3, 4, ..., не учитывая входа 9), блоков 12, 2, 3, 4 и при Т О блока 5, осуществляощих вместе со всеми отдельными 2п-1 входами сумматора 1 по модулю два операцию непрерывной (асинхронной) задержки логических сигналов. Аналогично, как и в известном устройстве под действием даже малых естественных флуктуации временных задержек блоков 12, 2, 3, 4, 5 и блока 1 по каждому из 2п-1 его входу, устанавливается режимгеНерирования широкополосного асинхронр ного случайного процесса, представляющего собой временную совокупность отрезков псевдослучайных последовательностей различной структуры, случаной длительности, случайного масштаба по времени и со случайной фазой. При достаточно большой величине п и ощутимой разнице средних временных задержек, приведенных по каждому входу cvMMaTooa 1 по модулю два (поэтому последовательная схема данного сумматора 1 и является более предпочтительной) , требование к иррациональности соотношений этих задержек значительно , снижается, а на этапе инженерной практики не учитывается вообще. Однако в целях создания устойчивого режима генерирования контура, должно быть обязательно выполнено следующее условие (аналогично присутствию инвертора в известной схемеj .ii©(A®Y;,li© -1--I 1-1 ©(A©Y®B)T®(A®4®C)T®x-7 . (1) где Y 0,1 -сигнал с выхода сумматора 1; А oTi-оператор инверсии усилителя-формирователя 2 ; В oTl-оператор инверсии последовательно соединенных коммутаторов 3 и 4 (при Т 1) J С o 7iоператор инверсии последовательно соединенных коммутатора 3, триггера 5 и кол1мутатора- 4 (при Т 0) ; X 0,1 сигнал настройки, подаваемь:й на вход 9; к и t соответственно объем первой и второй групп, входов сумматора 1, причем К С 2п-2. Оператор инверсии какого-либо блока обозначает следующее, если он равен О, то данный блок не инвертирует сигнал, подаваемый на его вход а если равен 1, то - инвертирует. Формула (1) справедлива, когда ключ 12 имеет оператор инверсии, равный 0. Упрощая выражение (1) и разрешая его относительно X, получаем более

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

X AE;-feBT©Ct©-( i (2)

Например, пусть усилитель-формирователь 2 инвертирует сигнал (А 1), -5 блоки 3-5 не инвертируют (В С 0), а С - четное числоj получаем X О (для любого Т 0,1).

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

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

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

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

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

Аналогичным образом описывается работа устройства и по более подробной схеме, изображенной на чертеже (с учетом конкретной реализации его блоков). В качестве триггера 5 применяется асинхронный RS-триггер с инверсными .установочными входами. Формирователь б выполнен на Т-триггере, счетный вход которого подключен к инверсному выходу триггера 5. В качестве ключа 12 используется перемычка. В рабочем режиме на вход 14 контроля необходимо подать 1. При Т О со входа 7 элемент 4 И-НЕ закрывается и сигнал с выхода инвертора 3 (в качестве усилителя-формирователя) проходит через элемент 3, единичное плечо триггера 5 и двухвходовой сумматор 42. на вход двухвходового сумматора 1. Случайный про- цесс, действующий в контуре, заставляет случайным образом переключаться и единичное плечо триггера 5, при этом нулевое плечо под действием . Т О находится в единичном (детерминированном) состоянии. Сигнал Т 1 запирает элемент 3 И-НБ и открывает элемент 4 И-ЙЕ, пропуская тем самым сигнал с выхода инвертора 2 мимо триггера 5 на вход сумматора 1 И; сохраняя рабочий режим контура. В этот момент триггер 5 устанавливается в устойчивое (случайное) состояние Q ОД. Сигнал Q действует на счетный вход Т-триггера 6, формируя таким образом выходной сигнал при условии действия по входу 8 разрешакяцего сигнала опроса, равного 1. Заметим, что на инверсном выходе триггера 5 формируется тактированная последовател ьность случайных символов вида Т V Q TQ, обеспечивая тем самым возможность применения в качестве формирователя б простого асинхронного Т-триггера, тогда на вход 8 необходимо подать постоянный разрешающий сигнал опроса, равный 1. Кроме того, сигнал с инверсного выхода триггера 5 используют в качестве сигнала .настройки, подаваемого на вход 9. 5

Анализируя инвертирую яие свойства блоков 2, 3 4 и 5 можно записать А 1, В Q и С 1. В данной схеме б.. Подставляя эти значения в формулу (2), получаем X QT, что и О требовалось доказать. В режиме контроля (при наладке или .ремонте устройства) цель обратной связи контура необходимо разорвать ключом 12 (в данном случае перемыч- 15 кой), Тогда рассматриваемое устройство превращается в детерминированный автомат, контроль работоспособности кохорого осуществляют обычными тестовыЬ ми средствами, пользуясь входами 7, 8 20 10 и 14, выходом 11, выходом яригге-ра 6, а также- выходами с остальных промежуточных точек схемы. Подавая определенные двоичные комбинации на входа 7, 8, 10 и 14 обеспечивают для jS данной конкретной схемы устройства все возможные переходы автомата. Неисправность , выявленная на данном этапе контроля, соответствует неисправности и генератора случайной по- ,,. спедовательности (с замкнутой цепью обратной связи) уже как вероятностного автомата.

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

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

Кроме того, использование в качестве выходного формирователя счетного триггера улучшает статистические ха- 4S

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

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

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

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

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

1.Авторское свидетельство СССР 306558, кл. Н 03 К 5/08, 1971.

2.Авторское свидетельство СССР по заявке 2822848/18-24,

кл. G Об F .7/58, 1979 (прототип).