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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 01.04. 81 (21) 3267200/18-24 Р 1 М. К С 06 Р 7/58 с присоединением заявки М,Государственный комитет СССР но дедам изобретений и открытий(72) Авторыизобретения азанский ордена Трудового Красного Зн авиационный институт им. А.Н. Туполе 71) Заявите 4) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛГДОВАТЕЛЬНОСТ Известно устройство, состоящееиз генератора обобщенного телеграфного сигнала, подключенного через логические схемы к выходному триггеру,и генерирующее как асинхронную, таки синхронную случайные последовательности 1.Однако в работе этого устройствавозможны сбои, так как на триггергенератора обобщенного телеграфногосигнала воздействуют случайные процессы со спектром, несогласованнымс частотными возможностями триггераи остальной части устройства. Возникающие при этом сбои в работе отдельных элементов (в первую очередь триггера генератора обобщенного телеграфного сигнала) приводят к погрешностямстатистических характеристик выходнойсинхронной случайной последовательности,цель достигается тем, учайной последовательй элемент НЕ, группу Изобретение относится к вычислительной технике, технике измерения и связи и может быть использовано в стохастических вычислительных машинах, в качестве датчиков случайных чисел для ЦВМ, а также для имитаторов случайных процессов при испытании, различной аппаратуры и каналов связи. Наиболее близким к предлагаемомуявляется генератор случайной последовательности, представляющий собой со-.единенные в кольцо асинхронный элемент задержки с отводами, многовходовой сумматор по модулю два и инвертирующий усилитель 2.Устройство постоянно использует 0 естественные флуктуации временных задержек асинхронного элемента. задержки для цели формирования случайнойпоследовательности типа обобщенноготелеграфного сигнала, Это затрудняетконтроль работоспособности устюойствачто усложняет технологию наладки иухудшает ремонтопригодность, следовательно, снижает надежность его эксплуатации. Кроме этого, устройство 20 позволяет генерировать только асинхронную случайную последовательность,что также является его недостатком,Цель изобретения - повышение надежности работы и расширение функциональных возможностей генератора засчет дополнительного формированиясинхронной случайной последовательностиПоставленнаячто генератор сл30 ности, содержащи(1 = 1, 2, , 2 п) сумматора помодулю два группы соединен с первымвходом (1+1)-го сумматора по модулюдва группы, введены три элемента 5И-НЕ, сумматор п о модулю два, ЙБ 1 триггер, Т-,.триггер и элемент И, пер-вый вход которого является первымуправляющим входом генератора, выход,(2 п)-го сумматора по модулю два 10группы соединен с вторым входомэлемента И, выход которого соединенс входом элемента НЕ, выход которого соединен с вторыми входами первыхщ(щ = 1, 2, ) сумматоров по модулю два группы, вторые входы последующих 2 п-щ сумматоров по модулю двагруппы подключены к выходу элементаИ, второй вход (2 п) -го сумматорапо модулю два группы соединен с инфверсным выходом ЙЯ-триггера и сосчетным входом Т-триггера, выход которого является выходом генератора,а синхронизирующий вход Т-триггераявляется входом "Опрос" генератора,тактовый вход которого соединен,с первыми входами первого и второгоэлементов И-НЕ и с инверсным входомЙЯ-триггера, выход которого соединенс первым входом сумматора по модулюдва, выход которого соединен с первым входом первого сумматора по модулю два группы; второй управляющийвход генератора соединен с вторымвходом второго элемента И-НЕ, выходкоторого соединен с первым входом 35третьего элемента И-НЕ, выход которого соединен с прямым входом ЙЯ-триггера выход элемента НЕ соединен свторыми входами первого и третьегоэлементов И-НЕ. 40На чертеже приведена блок-схемапредлагаемого генератора.Генератор случайной последовательности состоит из 2 п-входового сумматора 1 по модулю два,.усилителя-формирователя 2, коммутатора-селектора 3,коммутатора-мультиплексора 4, триггера 5 и выходного формирователя.б.Вход 7 является входом тактовых им.пульсов, вход 8 - входом сигнала опроса, а вход 9 - входом сигнала настройки. Коммутатор-селектор 3 выполнен на . основе элементов 3, и 3 И-НЕ,коммутатор-мультиплексор. 4 - на основе элемента 4 И-НЕ и двухвходовогосумматора 4 по модулю два, а сумматор 1 по модулю два - на основе двухвходовых сумматоров, 114,) 1 рг 1 ргр Х 4 р 1 у по модулюдва. Устройство имеет .также вход 10обратной связи, выход 11 обратной бОсвязи, ключ 12 обратной связи и входы13 и 14 контроля.Выход сумматора 1 через ключ 12соединен с одной, а дополнительночерез усилитель-формирователь 2 - , б 5 с другой группой своих входов. Выход усилителя-формирователя 2 соединен также со входом коммутатора-селектора 3. Один выход коммутатора-селектора 3 соединен непосредственно с однимвходом коммутатора-мультиплексора 4, а другой выход через единичное плечо триггера 5 - с соответствующим входомкоммутатора-мультиплексора 4. Генерацтор тактовых импульсов через вход 7подсоединяется к управляющим входамкоммутатора-селектора 3, коммутатора,мультиплексора 4 и к нулевому входутриггера 5. Источник сигнала опросаподсоединяется через вход 8 к соот-,ветствующему входу выходного формирователя б, На вход 9 подают сигналнастройки. Выход выходного формирователя б является выходом всего устройства,2 п-входовый сумматор 1 по модулюдва состоит йз 2 ппоследовательносоединенных сумматоров 1 , 1,117 18а а ф 1+р 1 по модулюдва на два входа (где и = 8). Коммутатор-селектор 3 выполнен на двухпоследовательно соединенных элементах 3 и 3 И-НЕ. Вход коммутатораселектора 3 подсоединен к одному извходов элемента 3 И-НЕ и является2одним из его выходов, подсоединяемыхк коммутатору-мультиплексору 4. Управляющий вход коммутатора-селектора 3 является входомэлемента 3 И-НЕ.Второй вход элемента 34 И-НЕ является входом 14 контроля. Коммутатормультиплексор 4 состоит из последовательно соединенных элемента 4 И-НЕи двухвходовогосумматора 4 по модулю два. Один вход элемента 4 И-НЕи один вход двухвходового сумматора4 по модулю два являются входамикоммутатора-мультиплексора 4, а другой вход элемента 4 А И-НЕ являетсяуправляющим входом коммутатора-мультиплексора 4. Соединение выхода двухвходового .сумматора 1 по модулюдва через ключ 12 с выходами соответствующихблоков образует цель обратной .связи. Вход 9 настройки подсоединен к инверсному выходу триггера 5.Усилитель-формирователь 2 служитдля увеличения нагрузочной способности (коэффициента разветвления по выходу) сумматора 1. В качестве негоиспользуется инвертор или группа инверторов, обеспечивающих надежное формирование логических уровней напряжения с выхода сумматора 1, подаваеьих на необходимое (достаточно больщое) количество входов самого сумматора 1 и на вход коммутатора-селектора 3.Коммутатор-селектор 3 осуществляет переключение сигнала с одного входа на один из двух выходов, а комаутатсрмультиплекстор 4 обеспечивает обратную коммутацию, т.е. переключение сигнала с одного иэ двух входов на выход.962933 45С = 0,1 Управление работой обоих коммутаторов 3 и 4 осуществляется посредством тактовых импульсов со входа 7.В качестве триггера 5 используется асинхронный триггер с установочными входами (асинхронный КБ-триггер). 5Выходной формирователь б осуществляет формирование выходной случайной синхронной последовательности. В данном качестве можно применить, например, коньюнктор или синхронный 0-тренггер. Однако лучшие результаты получаются при использовании в качестве вй 1- ходного формирователя б Т-триггера (счетного триггера). В этом случае статистические характеристики выход ного процесса дополнительно улучшаются операцией суммирования по модулю два, осуществляемой Т-триггером.Генератор работоспособен при любом способе построения 2 п-входового 20 сумматора 1 по модулю два, но последовательное соединение 2 пдвухвходовых сумматоров по модулю два для этой цели более предпочтительно (где и =,2, 3, 4, ). Данный вариант реализации сумматора 1 представлен на чертеже для случая и = 8. Такая организация схемы обеспечивает лучшие характеристики й более надежную работу всего устройства. 2 п(нечет.ное число) входов сумматора 1 используются для образования обратной связи, а вход 9 служит для настройки всего контура обратной связи на режим устойчивого генерирования первичной асинхронной случайной последова- З 5 тельности.В качестве ключа 12 используют, например коньюктор, управляемый от сигнала контроля по входу 13, или обычную монтажную перемычку. Состояние ключа 12 определяет режим работы устройства. Когда ключ 12 открыт, следовательно контур обратной связи замкнут (например, подана лбгическая "1 ф на вход 13 коньюктура или реализована перемычка), то это соответствует рабочему состоянию, т.е. состоянию генерирования случайных последовательностей. Запретное состояние ключа 12, т,е. разорванный контур 50 обратной связи (например, подачей логического "Оф на вход 13 коньюнктора или изъятием перемычки) соответствует режиму контроля, когда устройство проверяется как детерминированный 55 автомат (без генерации случайного процесса) .В рабочем режиме при действии по входу 7 тактового сигнала Т = О образуется контур обратной связи, состоящий из блоков 1, 12, 2, 2, 3,е 6 5 и 4. При .Т = 1 образуется также контур обратной связи из блоков 1, 12, 2, 3 и 4. В обоих случаях сущест вует контур обратной связи, состоящий из сумматора 1 по модулю два : ф с нечетным количеством входов (2 п, где и = 2, 3, 4.не учитывая входа 9), блоков 12, 2, 3, 4 и при Т0 блока 5, осуществляющих вместе со всеми отдельными 2 пвходами сумматора 1 по модулю два операцию непрерывной (асинхронной) задержки логическихсигналов. Аналогично, как и в известном устройстве под действием даже малых естественных флуктуаций временных задержек блоков 12, 2, 3, 4, 5 и блока 1 по каждому из 2 пего входу, устанавливается режим генерирования широкополосного асинхронно ного случайного процесса, представляющего собой временную совокупность отрезков псевдослучайных последовательностей различной структуры, случаной длительности, случайного масштаба по времени и со случайной фазой. При достаточно большой величине п и ощутимой разнице средних временных задержек, п риведенных по каждому входу счмматооа 1 по модулю два (поэтому последовательная схема данного сумматора 1 и является более предпоч" тительной), требование к иррациональности соотношений этих задержек значительно снижается, а на этапе инженерной практики не учитывается вообще. Однако в целях создания устойчивого режима генерирования контура, должно быть обязательно выполнено следующее условие (аналогично присутствию инвертора в известной схеме )В, 1 Я(Ду ЯяЖ(АТОВ)Т(АО+19 С)ТЯВ=1, (1) где У = 0,1 - сигнал с выхода сумматора 1;А = 0,1 - оператор инверсии уси-лителя-формирователя 2;В = 0,1 - оператор инверсии последовательно соединенных коммутаторов3 и 4 (при Т = 1);оператор инверсии госледовательно соединенных коммутатора 3, триг.гера 5 и коммутатора 4(при Т = О);Х = 0,1 - сигнал настройки, подаваемь й на вход 9;К и- соответственно объемпервой и второй группвходов сумматора 1,причем К + 1 = 2 п.Оператор инверсии какого-либо блока обозначает следующее если он ра)вен О, то данный блок не инвертирует сигнал, подаваемый на его вход а если равен 1, то - инвертирует. формула (1) справедлива, когда ключ 12 имеет оператор инверсии, равный О.Упрощая выражение (1) и разрешая его относительно Х, получаем болееудобную Формулу для.вычисления сигналанастройки, подаваемого на вход 91+4Х=А Е 10+ВтОСт 0+1 ь, (2)1=1Например, пусть усилитель-формирователь 2 инвертирует сигнал (А = 1),блоки 3-5 не инвертируют (ц = С = 0),1а 1 - четное число, тогда получаемХ = 0 (для любого Т = 0,1).При таком Х в контуре всегда выпол.няется логически противоречивое усло" 10вие У = 7(т.е. 1 = 0), благодаря чему. поддерживается устойчивый процесс генерации асинхронной случайной после,довательности,Благодаря работе коммутаторов 3 15и 4 триггер 5 осуществляет посредничество между генерирующим асинхроннуюслучайную последовательность контуроми формирующим выходную синхронную случайную последовательность выходным , щформирователем Ь, т.е, в паузе .междутактовыми импульсами (при Т = 0)триггер 5 включается в контур, а вмомент действия тактовых импульсов(при Т = 1) выключается из него, устанавливаясь при этом в случайное .состояние и формирует с помощью выходного формирователя б элементы выходной последовательности. Такаяорганизация работы устройства исключает сбои триггера 5 по причине конечности его быстродейстивя, так какскорость протекания процессов в контуре всегда согласована с,минимальным быстродействием входящих в негоблоков. Например, если быстродействиетриггера 5 оказывается меньше быстродействия блоков 1, 12, 2, 3 и 4,то при Т = 0 минимально возможныедлительности элементов асинхроннойпоследовательности в контуре возрас" 46тают до величины, допустимой длянормального срабатывания данного триггера. Л если триггер 5 просто подключается к контуру, то он не успеваетпереработать некоторые фрагменты 45асинхронной последовательности, чтоприводит к погрешностям формирования синхронной случайной последовательности.Устройство работает следующим об Оразом,Пусть в рабочем режиме по входу 7от генератора тактовых импульсов прихоцит сигнал Т = О. Он переводит работу коммутаторов 3 и 4 в такой режид, что сигнал с выхода усилителяформирователя 2 проходит последовательно через коммутатор 3, триггер 5и коммутатор 4 на отдельный вход сумматора 1. На вход 9 подается сигналх, рассчитанный по Формуле (2)дляТ = О, благоцаря чему выполняетсяусловие (1) и в конутре развиваетсяасинхронный случайный процесс (аналогично), как и в известном устройстве. Триггер 5 при этом также бес- И прерывно случайным образом переключается. Формирование выходного элемента синхронной случайной последовательности при этом не происходит. В момент действия Т = 1 триггер 5, со случайно установленным состоянием выключается из контура, но контур продолжает свою работу, так как сигнал с выхода усилителя-формирователя 2 проходит на отдельный вход сумматора 1 через последовательно соединенные коммутаторы 3 и 4, выполняется условие (1), благодаря подаче на вход 9 сигнала настройки Х, рассчитанного по формуле (2) для Т = 1. В этот же момент триггер 5 передает своим состоянием 0 случайный символ в выход" ной Формирователь б. При подаче сигнала опроса на вход 8, Формирователь б выдает элемент выходной синхронной случайной последовательности. Генерй рующий без триггера 5 контур подго-таливает случайную фазу для следующего цикла работы.Аналогичным образом Описывается работа устройства и по более подробной схеме, изображенной на чертеже (с учетом конкретной реализации его блоков), В качестве триггера 5 применяется асинхронный КЯ-триггер с инверсными .установочными входами.Формирователь б выполнен на Т-триггере, счетный вход которого подключен к инверсному выходу триггера 5. В качестве ключа 12 используется перемычка. В рабочем режиме на вход 14 контроля необходимо подать 1. При Т = 0 со входа 7 элемент 4 И-НЕ закрывается и сигнал с выхода инвертора 3 (в качестве усилителя-Формирователя) проходит через элемент 3, единичное плечо триггера 5 и двухвходовой сумматор 4 на вход двухвходового сумматора 11. Случайный про цесс, действующий в контуре, заставляет случайным образом переключаться и единичное плечо триггера 5, при этом нулевое плечо под действием Т = О находится в единичном (детерминированном) состоянии, Сигнал Т = 1 запирает элемент 3 И-НЕ и открывает элемент 4 И-НЕ, пропуская тем самым сигнал с выхода инвертора 2 мимо триггера 5 на вход сумматора 1 и сохраняя рабочий режим контура.В этот момент триггер 5 Устанавливается в устойчивое (случайное) состо" яние Я = 01. Сигнал Я действует на счетный вход Т-триггера б, Формируя таким образом выходной сигнал при условии действия по входу 8 разрешающего сигнала опроса, равного 1. Заметим, что на инверсном выходе триггера 5 Формируется тактированная последовательность случайных символов вида ТЯ = 7 Ц, обеспечивая тем самым возможность применения в качестве формирователя б простого асинйхронного Т-триггера, тогда на вход 8необходимо подать постоянный разрешающий сигнал опроса, равный 1. Крометого, сигнал с инверсного выхода триггера 5 используют в качестве сигнала,настройки, подаваемого на вход 9. 5Анализируя инвертирующие свойства,блоков 2, 3 4 и 5 можно записатьА = 1, В = Я и С = 1. В данной схеме1 = бПодотавляя эти значения вФормулу (2), получаем Х = яТ, что и 0требовалось доказать,В режиме контроля (при.наладкеили .Ремонте устройства) цель обратнойсвязи контура необходимо разорватьключом 12 (в данном случае перемыч- . 15кой). Тогда рассматриваемое устройствопревращается в детерминированный автомат, контроль работоспособности когорого осуществляют обычными тестовМми средствами, пользуясь входами 7, 8 щ.10 и 14, выходом 11, выходом яриггера б, а также выходами с остальныхпромежуточных точек схемы. Подаваяопределенные двоичные комбинации навходы 7, 8, .10 и 14 обеспечивают дляданной конкретной схемы устройствавсе возможные переходы автомата. Неисправность, выявленная на данномэтапе контроля, соответствует неисправности и генератора случайной последовательности с замкнутой цепью бобратной связи) уже как вероятностного автомата.Описанное конкретное устройствохорошо реализуется на б-и корпусахциФровых микросхем серии 155, т.е.в качестве блоков 4 яХ111используют элементы четырех корпусовмикросхем 155 ЛП 5, блоки 2, 3,1, 3и 4 легко реализуются на одном корпусе микросхемы ХЛБ 553, в,качестве 40триггера 5 используют асинхронную,часть (выходной ЙЯ-триггер) В-триггера микросхемы 1 ТК 552, выходнойФормирователь 6 в этом случае стро.ят на основе второго П-триггера корпуса микросхемы ХТК 552, т.е. соединяя его инверсный выход с Р-входом,получаем по.синхровходу Т-триггер,на нулевой установочный вход (%) врабочем режиме (по входу 8 устройства 0необходимо подать постоянный разрешающий сигнал опроса, равный 1.Благодаря коммутируемой с помощьюключа 12 обратной связи и наличиювходов контроля, устройство в режимеконтроля допускает достаточно подроб". ную проверку его работоспособности,а в рабочем режиме Формирует какасинхронную, так и синхронную (посред"ством работы блоков 5 и б) случайныепоследовательности, что выгодно отлиЧает предлагаемый генератор от известных.Кроме того, использование в качестве выходного формирователя счетноготриггера улучшает статистические ха ъ рактеристики выходного процесса (засчет дополнительного суммирования помодулю два) .Как видно из вышеприведенного примера, предлагаемое изобретение можетбыть реализовано исключительно на цифровых элементах, что позволяет. егоизготовление полностью по интегральнойтехнологии цифровых микросхем. Данныйтехнологический эффект определяетдополнительные преимущества предлага,емого устройства по отношению к извест ным генераторам случайных процессов.формула изобретенияГенератор случайной последователь-ности, содержащий элемент НЕ, группуиз 2 п(и = 2, 3, 4 ..) сумматоровпо модулю два, выход каждого 1-го(1 = 1, 2, , 2 п) сумматора помодулю два группы соединен с первымвходом (1+ 1) -го сумматора по модулюдва группы, о т л и ч а ю щ и й с ятем, что, с целью повышения надежности генератора, он содержит три элемента И-НЕ, сумматор по модулю два,ЙЯ-триггер, Т-триггер и элемент И,первый вход которого является первымуправляющим входом генератора, выход (2 п)-го сумматора по модулюдва группы соединен с вторым входомэлемента И, выход которого соединенс входом элемента НЕ, выход которогосоединен с вторыми входами первыхщ (щ = 1, 2, ) сумматоров по модулю два группы, вторые входы последующих 2 п-в сумматоров по модулюдва группы подключены к выходу элемента И, второй вход (2 п)-го сумматора по модулю два группы соединенс инверсным выходом НЯ-триггера исо счетным входом Т-триггера, выходкоторого является выходом генератора, а синхронизирующий вход Т-триггера является входом "Опрос" генератора, тактовый вход которого соединенс первыми входами первого и второгоэлементов И-НЕ и с инверсным входомВЯ-триггера, выход которого соединенс первым входом сумматора по модулюдва, выход которого соединен с первым входом первого сумматора по модулю два группы, второй управляющийвход генератора соединен с вторымвходом второго элемента И-НЕ, выходкоторого с оединен с первым входомтретьего элемента И-НЕ, выход которого соединен с прямым входом НЯ-триггера, выход элемента НЕ соединенс вторыми входами первого и третьегоэлементов И-НЕ.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 306558, кл. Н 03 К 5/08, 1971.2. Авторское свидетельство СССРпо заявке 9 2822848/18-24,кл. С Об Р 7/58, 1979 прототип 1.962933 Заказ 7514/69 Тираж 731 П ВНИИПИ Государственного комитета СС по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., исное 5 Фил ПП ."Патент",г. Ужгород, ул. Проект Составитель Л. Карасоведактор Ю. Середа Техред Т.Фанта Корректор Л. Бо