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

(22) Заявлено 18,04,80 (2 29112821 8-24с пригоелинением заявки Рй(51)М. Кл,606 Р 7/58 ооударотеениый комитет оо делам изобретений и открытий(7 ) Заявитель Киевский ордена Ленина политехнический ттнститут им. 50 летия Великой Октябрьской социалистической революции(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и автоматике и может найтиприменение при разработке устройств,использующих статистические принципыфункционирования и обладающих возможностью самоконтроля,Известен генератор равномерно распределенных псевдослучайных чисел, содержащий И -разрядный регистр сдвигас сумматорами по модулю два в цепиобратной связи, причем первые е разрядов регистра сдвига выполнены на триггерах со счетным входом, а остальные(т 1 - ттт) разрядов - на триггерах с установочным входом 11,Недостатком этого генератора является невозможность обнаружения отказовэлементов памяти регистра сдвига; приводящих к существенному уменьшению периода генерируемой последовательности,Наиболее близким техническим решьнием к изобретению является генераторравномерно расположенных псевдослучайных чисел, содержащий И -разрядный сдвиговый регистр с сумьяторами по модулю два в цепи обратной связи, дешиф. ратор, делитель, элемент задержки, элемент НЕ, первый и второй элементы И и реверсивный счетчик 2.Недостатком известного устройства является наличие длительного периода неправильной работы генератора от момента возникновения отказа в регистре сдвига до обнаружения неисправности схемой контроля.Цель изобретения - повышения быстродействия за счет сокращения времени обнаружения неисправности,Для достижения поставленной цели в известный генератор равномерно распределенных псевдослучайных чисел, содержащий рекуррентный регистр сдвига, выходы которого являются выходами генератора, счетчик, элемент НЕ и два элемента И, причем вход тактовых импульс сов соединен с входом рекуррентного регистра сдвига и с счетным входом счет чика. выход элемента НЕ подключен кпервому входу первого элемента И, ввдецы блок памяти, элемент церавцозцачности и триггер, единичнъй выход которого подключен ко второму входу первогои первому входу второго элементов И ик управляющему входу блока памяти,информационный вход которого соединенс выходом 1 -го разряда рекуррентцого сдвига, подключенным также к первому входу элемента неравцозначности,второй вход которого соединен с выхсдом блока памяти, а выход элемента церавнозначности соединен со входом элеме%та НЕ и вторым входом второго элемента И., выход которого подключен к цу 15левому входу триггера и к входу Сброссчетчика, выход которого соединен стретьж входом первого элемента И ис единичным входом триггера, тактовыйвход которого подключен к входу тактовых импульсов устройства, соединенномутакже с четвертым входом первого эле;ента И, разрядные выходы счетчикаподключены к адресным входам блокапамяти,2.На фиг. 1 представлена структурнаясхема генератора равномерно распределенных псевдослучайных чисел, нафиг. 2 - структура регистра для сл ия11 =6, (где 1 а - число разрядов регистра), она фиг. 3 - схема неисправного регистра.В состав генератора входит и -разрядный регистр сдвига 1 с сумматорами по модулю два в цепи обратной связи, на вход которого подключена шица синхроимпульсов 2, соединенная также со счетным входом счетчика 3, Выход 4 с выхода счетчика 3 подключен к единичному входу триггера 5, единичный выход которого заведен на входы элементов И 6 и 7, Выход 4 подключен также ко входу элемента И 6, со входом которого соединена шина синхроимпульсов 2, заведенная, кроме того, на тактовый вход триггера 5, Выходы счетчика 3 подключены к адресным входам блока памяти 8, на управляющий вход ко-. торой подключен единичный выход триг=- гера 5. Информационный вход блока памяти 8 соединен с выходом 1 -го 5 О (1 О, 1, 2, , 1 а) разряда регистра сдвига 1. Выход этого же 1-го разряда подключен к первому входу элемента неравнозначиости 9, на второй вход которого заведен выход памяти 8, Вы ход элемента неравнозначности 9 подклю= чен ко входу элемента И 7 непосредст венно а через элемент 115 1 О - ко вхо= ду элемецта И 6, Выход элемента И 7 заведец на вход начальной установки счетчика 3 и ца нулевой вход триггера 5, Цепи исходной ( пультовой) установки непоказаны. устройство работает следующим образом.Исходное состояние - нулевое для счет цка 3 и нулевое для триггера 5.11 улевой сигнал, подаваемй с выхода триггсра 5 на управляющий вход блока памяти 8, соответствует режиму Запись" ддя блока 8. Каждый приходящий по ип- це 2 сицхроимтульс меняет состояние регистра 1 и добавляет единицу в счет чик 3, ца выходах которого формируется адрес очередной ячейки блока 8, Таким образом, каждый сицхроимпульс шины 2 осуществляет запись состояния-го выхода регистра 1 в очередную ячейку . блока памяти 8. Процесс записи повторяется до заполнения счетчика 3, В этом случае на шине 4 формируется единичный сигнал, поступающий на единичный информационный вход триггера 5, что приводит к переключеппо последнего в единицу с приходом очередного синхроимпульса на тактовый вход триггера с шины 2. Отметим, что в рехапле Запись" элементы И 6 и 7 закрыты нулевым сигналом с выхода триггера 5. Переключение триггера 5 в единилу после заполнения счетьчика 3 сопровождается формированием едцщчцого сигнала Чтение, подаваемого на управляющий вход блока памяти 8 с единичного выхода триггера 5. Одновременно синхросигнал, переключающий, в единицу триггер 5, обцуляет счетчик 3 после единичного состояния всех разрядов счетчика 3 следующее состояние - нулевое). Каждый следующий сицхро - импульс с шины 2, по-прежнему, изменяет состояние регистра 1 и осуществляет теперь уже последовательное считывание ячеек памяти блока 8 путем добавления единицы в счетчик 3. Каждый такт чтениясопровождается сравнением с помощью элемента церавцозначцости 9 состояния выхода б-ока 8 и состояния 1 -го выхода ре 1",:стра 1, Элемент неравнозначности 9 ца каждом такте цикла "Чтение осуществляет сравнение двух состояний выхода -1 -го разряда регистра 1, между которыми прошлотактов работы генератора псевдоиучайных чисел, К=2, коэф)ициент пересчета счетчика 3, 1" - целое полохщтельное число Несовпадение ца некотором такте считываемогослова, т. е. единичный признак отказав генераторе формируется на выходеэлемента И 6 в случае, если последнийК-ый такт чтения содержимого блока 8(так же, и предшествующие К 1 тактов)сопровождается сравнением состояния-го выхода регистра 1 и считываемого из блока 8 Разряда. Рассмотрим контроль генератора псев дослучайных чисел на основе предлагаемого принципа для случая 11 ф"6 (И -число разрядов регистра 1). Для такого генератора Ю:=5. Допустим, контроль регистра в соот ветствии с принципом предлагаемого устройства осуществляется по состоянию триггера Т 2, Для генераторов псевдослуь чайных чисел при отсутств 1 п неисправностей последовательность состояний лкбого (в том числе и Т ) разряда имеет рериод 2 -1 тактов, т, е, является пофследовательностью максмального периода. Если ке в регистре возникает неисправность (типа застревание любого триггера в 1 .цлн О или эквивалентной этой неисправности отказ типа обрыв для связи между; - .аэрядами), то наибольший возможный период для любого разряда (в том числе и Т ) составляет величину, Равную блокайшей степени числа "2", не, меньшой, чем пасло л триггеров со счесть. ным входом в регистре генератора. Это свойство может быть записано в виде неравенства с2 Ъи,-, 2 Или щи рассматриваемого примера, если и 5, то3 и наибольший возможный период для любого разряда при неисправности равен 8 тактам. Работа предлагаемого устройства и основана на измерении периода последовательностн произвольного разряда (в данном случае Т). Для этого в блок 8 записывается 8 последовательных состояний,триггера Т. Затем производится чтение этих записанных разрядов и сравнение каждого из них с текущим состоянием триггера Т. Чтение продолжается до несовпадения выхода блока 8 и состояния Т, Признаком неисправности является совпадение двух соседних наборов, формируемых трщгером Т, каждый из которых содержит по 8 состояний, Отсюда следует, что раэрядность счетчика адреса З,составляет величину, равную 6, т, е. коэффициент 5 935951из блока 8 одноразрядного слова и со,стояния 1 -го выхода регистра 1 приводит к формированию единичного сигнала на выходе элемента неравнозначности9и на выходе элемента И 7 (так как 5триггер 5 находится в единичном состоянии - режим Чтением). Единичный сигнал с выхода элемента И 7 сбрасываетв нуль счетчик 3 и после прихода ближайшего синхроимпульса по шине 2 на такто-овый вход триггера 5 осуществляет переключение данного триггера в нулевоесостояние, т. е, переводит блок памяти 8в режим фЗаписьф, Если несравнениесчитываемого из блока 8 одноразрядного слова и состояния , -го выходарегистра 1 произошло лишь на последнем Ком такте чтения (все предшествующие такты такого пика чтениясопровождаются .нулевыми сигналами равенства с выхода схемы неравнозначнос-".ти 9), то обнуление счетчика 3 очередным сигналом по шине 2 лицп подтвердится сигналом по входу начальной установки с выхода элемента И 7. Элемент 25же И 6 закрыт на этом такте нулевымсигналом с выхода инвертора 10, навход которого поступает единичный признак несравнения.1 ЗООбычно генераторы псевдослучайныхчисел строятся из расчета получения максимально возможного периода 2" -1,В случае же отказа типа "застреваниеодного или нескольких элементов памя 35ти регистра сдвига период такого неисп-равного генератора определяется, исходяиз соотношения 2 )у Ю 7 2, где 9целое положительное число, ю- числотриггеров со счетным входом в регистресдвига. Если коэффициент пересчета счеъчика 3 К=2 .7 2, тогда величина Ккратна величине периода неисправногогенератора. Следовательно, при возникновении отказа в регистре 1 период последовательности на 1 м выходе регисъра определяется не величиной 2 -1,Икак это было бы в исправном генераторе,а гораздо меньшей величиной 2 . Таккак коэффициент пересчета счетчикаЗК у 2 и кратен величине 2, то поо 50ле К тактов записи последовательныхК состояний 1-го выхода неисправного регистра 1 следуют К тактов чтениясодержимого блока памяти 8, причемна каждом из этих тактов чтения осуществляется сравнение состояния-говыхода регистра 1 и считываемого наэтом такте из блока 8 одноразрядного93)951 7пересчета счетчика 3 равен 2 (или 8для рассматриваемого примера),Допустим, схема (фиг, 2) при отсутствии отказа формирует следующую псевдослучайную последовательность,Т ТТ Т Ттакта Т Т Т Т Т Т6 5 4 ф Ф Ь0 0 1 1 0 4+8 О 1 1 0 1 1+3 1 0 0 1 1 1 +10 0 1 0 1 0 0 +11 О 1 1 1 1 1 1+5 0 0 1 1 1 0 1+12 1 0 0 0 0 0 0 0 1 0 0 1 1+13 1 1 0 0 0 0 1 0 1 1 0 1 +14 1 1 1 0 0 0 1+6 1+7,Допустим также, что начиная с (1+1)- Тогда на ( +1)-ом, ( 1+2)-ом, ( +3)- го такта выполняется цикл "Запись (т. е, ом( 1+8)-ом тактах состояния Т на 4 м такте - несовпадение считывае- записывается в ЗУ мого ю ЗУ разряда и состояния Тд). гоТакты циклаЗапись" 1+8+1 1+2 +3 +4 1+5 + 6 1+ 7 Состоя ниесчетчика 3 000 001 010 011 100 101 110 111 Состояние Т 0 11 0 0 1 1 1 После этого ( т. е, после пере- пись ) ЗУ переключается в режимполнения счетчика 3 в режиме "За- "Чтение".зо Такты цикла+9 1+1 О 1+11 1+1 2 4+1 3 1+1 4 Состояние 1счетчика 3 000 001 010 011 100 101 Считываемыйиз ЗУ бит 0 0 0 0 Состояние Т 0 ТТ Т Т1 0 1 1 0 1такта 0 1 1 0 1 1 0 1 1 0 1 0 л+10 1+11 0 1 О 1 01 О 1 1 1 1 Отсюда следует, что на такте чтения 4 о +14 происходит несовпадение считываемого из блока 8 разряда с состоянием триггера Т. Это вызывает переключение блока 8 на цикл "Запись", состоящий нз 8 тактов, затем в цикле Чтение" вновь сопостаьляется кажный считываемый из блока 8 бит и сост ояние Т цо обнаружения нес овпа пения н т ц.Пусть на входе Т( возникает неисправность "константа 1 ф за счет обрыва соьдинения выхода Т со входом Т (фиг, 3). Это наихудший случай, так как при этом все триггеры (в том числе и Т) работоспособны. Б то же время данная неисправность по отношению к Т, эквивалентна "застреванию Т в единице.Пусть отказ происходит после выполнения такта 1+79359511 1 0 4+12 +13 и+14+15 1+16 0 0 1 О 0 1 о о 1 0 0 1 О 1 0 1 11рассматриваемом случае так как периодв 4 такта кратен наибольшему периодув 8 ;тактов в наихудшем случае),Состояния регистра и триггера Т имеют период 8 тактов, Следует отме о тить, что отказ, например, триггера Т приводит к тому, что период состояний триггеров Т-Т составляет 4 такта, так как на участке Т-С имеется три триггера со счетным входом. Настройка же схемы контроля на признак неисправности в 8 тактов позволяет обнаружить и отказ любого другого триггера (Тв Пусть на такте 3+1 (так же, как в рассматриваемом случае отсутствия отъказа) начат .цикл фЗапись". Начиная с такта +9 ЗУ переключается на фЧтение" (длительность цикла Запись всегда составляет 2 =8 тактов).5 Такты циклафЧ теннеси+9 +1 О й.1 1 3+1 2 4+1 3 1+1 4 Считываемыйиз ЗУ бит 0 0 0 0 0 0 Состояние Т Следующий цикл фЗаписьф. Несовпадение пронсхопкт на тактеМ+14 Такты циклаЗапись 1+1 5 1+16 1+17+1 8 1 +19 1+20 4+21 1+22 О 0 0 Состояние Т11 0 Затем выполняется цикл "Чтение". Такты циклаЧтение +23 +24 1+25 +26 1+27 +28 1+29 +30 0 Состояниевыхода ЗУ 1 1 0 1 1Состояние Т 1 1 0 1 1 0 0Все 8 тактов чтения сопровождаются коэффициент пересчета счетчика ).3). Тасовпадением состояния Т и выхода ЗУ, кнм образом, если и - разр ядный исправ-что и является признаком ошибки. Обнару- ный генератор имеет ри дпе о 2 п м 1 такжение отказа происходит спустя 23 таь- тов, то отказ в регистре приводит к4кото ый о деляетсяпосле его возникновения т. е. мень. снижению периода, р прещ стеф3- К;. =24 такта. Если отказ бпижайшей, не меньшей, чем и,ше, чем - К;.4= тчисла м 2 ф Однако если величинапроисходит на цикле фЧтениеф, то наи- пенью числа 2 . днако ех дшим вариантом является отказ в на- р мала, то веро ното ве оятность 1/2 того, чтохудчеле этого цикла, а также усповие, что в исправном генера ре двато соседних най из которых содержит 2 переключение на запись имеет место на ф бора, каждый вз которыравны,.(2 -1)-м такте чтения, Тогда обнару- состояний какогэ и разряде,Тог можно увеличить коэффи -жение та кого отказа происходит после велика. Тогда мож увыетчика 3 до величины(2-1)+2 +2=3 К -1 тактов, причем циент пересчета счетчика д2 +2 длительность циклов фЗаписьф ютность величин Кс 2 ии Чтение т е время неправильной 5 . 2 определяется тем, чтчто оба эти числаставпяют степень числа ф 2. Наботы генератора (до обнаружения отка- представпесли ст генеуетора не содеэа) можно охарактеризовать величиной, пример если реги Р Ж"т гге в со счетным входом (т. е.не превышаюшей 3 К о 4 тактов (Кщ- бакит"тратероФО), то 25 2 1. Действительно, отказ в 33 егистре чисто сдвигового тита приводит к тому, что состояние крайнего разряда регистра, в направлении которого осуществляется сдвиг, перестает изменяться, т. е. период равен одному такту. Однако если схему контроля строить нв ОснОВании Ксн=2 1, то сигнал Ошибки формируется и при исправном генера1 О торе с вероятностью - = - на каждом2 Кси 2такте. Если же увеличить число записываемых в блок 8 разрядов до величины 2 7 2 , то можно свести вероятность ложного формироВания сигнала Ошибки к 15 пренебрежимым значениям при достаточно большом 1" р, - =Следовательно, разрядность 5 счетчика 3 определяется числом И триггеров со счетным входом в регистре генератора, ,120 если учитывать соотношение 25 ъи 1 7 2," величина ложного формирования сигнала ошибкидостаточно мала. В протиь- ном случае коэффициент пересчета выбирается равным 2, Р )5, таким, что д 5 1 уменьшается до допустимого значения, При этом кратность чисел 2 и 2 обеспечивается тем, что оба эти значения являются степенью числа 2".Последовательность, формируемая генератором псевдослучайных чисел, близка к случайной для достаточно больших величин И , когда период 2 -1 такой последовательности гораздо больше времени рабочего использования генератора.35 С другой стороны, необходимость в пост роении многофазных генераторов псевдослучайных чисел часто вызвана требованиями к параметрам статических устройств в составе которых имеется такой генератор. Например, в системах техно- логического контроля печатнъ 1 х плат, использующих статические принципы проверки, разрядность генератора испытательных псевдослучайных последовательностей оп 45 ределяется числом контактов разъема печатной платы и может достигать сотни и более. Необходимость повышения быстродействия при формировании псевдослучайных последовательностей приводит к раз 50 работке генераторов, регистр сдвига которых целиком выполнен на триггерах со счетным входом, т. е. у которых м 1: и В связи с жложенным коэффициенч. пересчета счетичка 3 предлагаемого устройства может быть оценен на основе соот ношения К 2)/ 112), гдецелое положительное число. Если считать, что при отсутствии отказов последова -тельность состояний произвольного 1 -го разряда генератора представляет собой чисто случайную величину, то вероятность того, что два соседних набора последова тельных состояний (каждый набор содержит К=2состояний) 1 -го разряда регистра сдВига окажутся одинакоВыми можно найти как величину 1/2 . Если И=123, то вероятность формирования ложного сигнала ошибки в исправном ге нераторе сотавляет величину 1/2" т. е. величину пренебрежимо малую.Если отказ в регистре сдвига предлагаемого устройства происходит в конце некоторого цикла записи, и следующий за ним цикл фЧтение сопровождается несравнением сигналов схемой О только 1 а последнем К-ом такте, то для обнаружения данной неисправности потребует- ся еще один цикл "Запись" и один цикл Чтение", В конце которого формируется признак отказа, т. е. Время работы неисправного генератора до обнаружения отказа в предлагаемом устройстве можно охарактеризовать величиной порядка ЗК тактов.Для известного устройства время неправильной работы генератора можно оценить величиной К К,с, где Кдкоэффициент деления делителя, К максимальная абсолютная величина которая может храниться в реверсивном счет- ппе, Если сдвиговый регистр генератора имеет у = 1 и то при одном и том же и Кд=К, т. е. делитель известного устройства имеет такой же коэффициент пересчета (деления),как и счетчик 3 предлагаемого устройства , При оценке величины К ос. известного устройства для упрощения допускаем, что заполнение реверсивного счетчика происходит, если в последовательности состояний:1 -го выхода генератора подряд К нулей либо единиц. Тогда вероятность ложного формирования сигнала неисправности генератора составляет величину 2/2 Кс, считая выходную последователь ность генератора случайной величиной. Если принять, что величины вероятности формирования ложного сигнала отказа чтя известного и предлагаемого у.стройств должны быть равны, т е. 1/2 2/2 РС, то отсюда К =Кр и время неправильной работы генератора для известного харак 2. теризуется величиной порядка К тактов,Таким образом, время обнаружения отказа в регистре сдвига предлагаемым устройством существенно меньше, чем дляизвестного, например и =ю= 123, К=128и обнаружение неисправности известнымпроисходит эа 128 - 1,7 10 тактовпредлагаемому же устройству для этогопотребуется Зф 128 4 10 тактов,5Аппаратурные затраты, необходимыедпя реализации предлагаемого устройства,сравнимы с затратами аппаратуры дляизвестного. В частности, сложность счетчика соответствует сложности делителяизвестного, сложность функциональныхэлементов (элементы И, инвертор, задержка) примерно равна сложности функциональных элементов предлагаемого устройства (элементы И, инвертор, триггер,схема неравнозначности), Что же касаетсся схемы одноразрядной памяти, то современная элементная база располагаеттакими узлами, выполненными на одномкристалле и имеющими высокую информа ационную емкость, например элементОЗУ 505 РУ 4 емкостью 256 одноразрядных слов со схемами управления водном корпусе.Формула изобретенияяГенератор псевдослучайных чисел, содержащий рекуррентиый регистр сдвига, 30 выходы которого являются выходами генератора, счетчик, элемент НЕ и два элемента И:, причем вход тактовых импульсов генератора соединен с входом рекуррентного регистра сдвига и счетным входом зз счетчика, выход элемента НЕ подключенк первому входу первого элемента И,о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия, он содержит блок памяти элемент неравнозначности и триггер, единичный .выходкоторого подключен ко второму входупервого и первому входу второго элементов И и к управляющему входу блока памяти, информационный вход которого соединен с выходом -го раэряд 1 рекуррентного регистра сдвига, подключеннымк первому входу элемента неравноэначности, второй вход которого соединенс выходом блока памяти, а выход элемента неравнозначности соединен со входом элемента НЕ и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера и квходу Сброс счетчика, выхсд которогосаединен с третьим входом первого элемента И и с единичным входом триггера, тактовый вход которого подключенк входу тактовых импульсов устройства,соединенному также с четвертым входомпервого элемента И, разрядные выходысчетчика подключены к адресным входамблока памяти.Источники информа ции,принятые во внимание при экспертизе1. Авторское свидетепьс лво СССР% 468231, кл. С 06 Г 1/02, 1973.2. Авторское свидетельство СССРЪ 674007, кп, 606 Г 1/02, 1977.421 3/52ВНИИ ГП Подписноглтета СССРкрытийушская наб., д. 4 1130 ФиСоставитель Л. Карасов едактор Л. Повхан Техред К.Мьщьо Корректор М. Шар