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

(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислительной технике и автоматике и может найти применение при разработке устройств, использующих статистические приншшы . функционирования и обладающих вооможгностью самоконтроля, Известен генератор равномерно распределенных псевдослучайных чисел, содержащий У1 -разрядный регистр сдвига с сумматорами по модулю два в цепи обратной связи, причем первые Yn разрядов регистра сдвига выполнены на триг герах со счетным входом, а остальные (V - w) разрядов - на триггерах с установочным входом ll Недостатком этого генератора явля« ется невозможность обнаружения отказов элементов памяти регистра сдвига, приГво дящих к существенному уменьшению пери да генерируемой последовательности. Наиболее близким техническш решением к изобретению является генератор равномерно расположенных псевцослучай ных чисел, содержащий Vl -разрядный сдвиговый регистр с сумматорами по модулю два в цепи обратной связи, деши(| ратор, делитель, элемент задержки, элемент НЕ, первый и второй элементы И и реверсивный счетчик L2. Недостатком известного устройства является наличие длительного периода неправильной работы генератора от момента возникновения отказа в регистрю сдвига до обнаружения неисправности схемой контроля. Цель изобретения - повышения быстродействия за счет сокращения времени обнаружения неисправности. Для достижения поставленной цели в давестный генератор равномерно распределенных псевдослучайных чисел, содержащий рекуррентный регистр сдвига, ны ходы которого являются выходами гетюратора, счетчик, элемент НЕ и два элемента И, причем вход тактовых импульсов соединен с входом рекуррентного регистра сдвига и с счетным входом счетчика, выход элелгенгга НЕ подключен к первому входу первого элемента И, введены блок памяти, элемент неравноз(юч ности и триггер, единичный выход которо го подключен ко второму входу первого и первому входу-второго элементов И и к управляющему входу блока памяти, информационш.1й вход которого соединен с выходом ( -го разряда рекурректн{. го сдвига, подключенным также к первому входу элемента неравнозначности, второй вход которого соединен с выходом блока памяти, а выход элемента tieравнозначности соединен со входом элемента НЕ и вторым входом второго элемента И, выход которого подключен к ну левому Входу триггера и к входу Сброс счетчика, выход которого соединен с третьим, входом первого элемента И и с единичным входом триггера, тактовый вход которого подключен к входу тактовых импульсов устройства, соединенному также с четвертым входом первого эле мента И, разрядные выходы счетчика подключены к адресным входам блока памяти. На фиг. 1 представлена структурна схема генератора равномерно распределенных псевдослучайных чисел, на фиг. 2 - структура регистра шм , (где И - число разрядов регистра) на фиг. 3 - схема неисправного регистр В состав генератора входит ц -раз рядный регистр сдвига 1 с сумматорами по модулю два в цепи обратной связи, на вход которого подключена шина сиихроиьшульсов 2, соединенная таюке со счетньш входом счетчшса 3. Выход с 4й)1хода счетчика 3 подгшючен к едИ ничному входу триггера 5, единичный выход которого заведен на входы элементов И 6 и 7. Выход 4 подключен также ко входу элемента И б, со вхо дом которого соединена сннхроимпульсов 2, заведенная, кроме того, на тактовый вход триггера 5. Выходы счеа чшш 3 пошопочены к адрес а.1м входам, блока памяти 8, на управляющий вх.од к торой подключен единичный выход триг гера 5. Инфо,р;1ационный вход блока памяти 8 соединен с выходом i -го (lO, 1, 2, ....И-) разряда регистра сдвига 1. Выход этого же 1-го раз. ряда подключен к первому входу элемен та неравнозначности 9, на второй вход которого заведен выход 8. Выход элемента неравнозначности 9 подклк чей ко входу элемента И 7 непосредственно, а через элемент НЕ 10 - ко вхо ду элемента 1-1 О. Г. элемента 1 7 заведен на вход начальной установки счеРчика 3 и на яллссойвкод rptirrepa 5. Пени исходной ( пультовой) установки не показаны. Устройство работает следующим образом. Исходное состояние - нулевое для счетчика 3 и нулевое для триггера 5. Пулевой , подаваеМ1,й с выхода триггера 5 на управляющий вход блока памяти 8, соответствует режиму Запись для блока 3. Каждый приходящий по шине 2 синхроигуцтульс меняет состояние pervicTpa 1 и добавляет единшгу в счет4VIK 3, на выходах которого формируется адрес очередной ячейки блока 8, Таким образол. каждый cHHXpoicvtnyabc шины 2 ocyu ecтБляeт запись состоя}шя -го выхода регистра 1 в очередную ячейку . блока памяти 8. Пропесс записи повторяется до заполнеяия счетчика 3. В этом случае на шкне 4 формируется единичный с прнал, поступающий на едиш1чный информапионный вход триггера 5, что приводит к переключетсо последнего в едикгшу с приход (Ж очередного синхрода-гпульса на тактовый вход тр сггера с 2. Отметим, что в релслме Запись элементы И 6 и 7 закрыты нулевым сигналом с выхода триггера 5. Переключение триггера 5 в едш1Ицу после заполнения счет чггка 3 сопровождается формированием еди шчного сигнала Чтение, пода.ваемого ш ртраышюнп й вход блока паьштк 8 с единичного выхода триггера 5. Одновременно синхросигнал, переключающий, в единицу триггер 5, обнуляет счетчик 3 (после единичного состоятдая всех разрядов счетчшш 3 следующее состояние - }гулевое). Каждый следующий сиихро - импульс с шины 2, пск-прех нему, изменяет состоящю регистра 1 и осуществляет теперь уже последовательное с итывание ячеек памяти блока 8 путем добавления едннизхы в счетчик 3. Каждый такт чтения сопровождается сравнением с помощью элемента аеравнозначности 9 состояния выхода б ч ока 8 и состояния -i -го выхода регистра 1. Элемент неравнозначпосш 9 на каждом такте цикла осуществляет сравнение двух состояний выхода -} -го разряда регистра 1, между которььми прошло К тактов работы генератора псевдослучайных тесел, , коэффициент пересчета счетчика 3, V цепое пополотгельное число Несовпадение на некотором такте считываемого из блока 8 одноразрядного слова и со . стояния i -го выхода регистра 1 приводит к формированию единичного сигнала на выходе элементе неравнозначности 9 и на выходе элемента И 7 (так как триггер 5 находится в единичном состоя нии - режим Чтение). Единичный сигнал с выхода элемента И 7 сбрасывает в нуль счетчик 3 и после прихода бянжа шего синхроимпульса по шине 2 на такт вый вход триггера 5 осужестиляет переключение данного триггера в нулевое состояние, т. е. переводит блок п Jvшти в режим Запись. Если несравнетше считываемого из блока 8 одноразряднего слова и состояния -го выхода регистра 1 произошло лишь на последнем К-ом такто чтения (все предшест- вующие такты такого цикЛа чтения сопровождаются нулевьи ли cигнaлa ш равенства с выхода схемы неравнозначноети 9), то обнуление счетчика 3 очеред ным сигналом по шине 2 лишь подтвердится сигналом по входу начальной уста новки с выхода элемента И 7. Элемент же И 6 закрыт ка этом такте нулевым сигналом -с выхода инвертора 10, на вход которого поступает единичный приз« нак несравнения. Обычно генераторы псевдослучайных чисел строятся.из расчета получения мак симально возможного периода . В случае же отказа типа застревание одного или нескольких элементов памяти регистра сдвига период такого кексправного генератора определяется, исходя из соотношения w 7 2, где 5 целое положительное число, т- число триггеров со счетньш входом в регистре сдвига. Если коэффициент пересчета счетчика 3 К.2 7 2, тогда величина К кратна величине периода неисправного генератора. Следовательно, при возникно вении отказа в регистре 1 период по- следовательности на Н-м выходе регис1 ра определяется не величиной , как это было бы в исправном генераторе а гораздо меньшей величиной 2 . Так как коэффициент пересчета счетчика ЗК / 2 и кратен величине 2 , то поо ле К тактов записи последовательных К состояний i-ro выхода неисправно го регистра 1 следуют К тактов чтения содержимого б л ежа памяти 8, причем ва каждом из этих тактов чтения осу- ществляется сравнение состоя Ш1Я -i -го выхода регистра 1 и считываемого на этом такте из блока 8 одноразрядного слова, т. е. единичный признак отказа в генераторе фор щруется на выходе элемента И 6 в случае, если последний К-ый такт чтения содержимого блока 8 г (так же , и предшествующие К-1 тактов) .сопровождается сра.внением состояния -го выхода регистра 1 и считываемого из блока 8 разряда. Рассмотргол контроль генератора псев«дослучайных чисел на основе предлагаемого пришлгаа для спушя П б (И -чиоло разрядов регистра 1). Для такого га нератора W . Допустим, контроль регистра в соот- ветствик с принципом предлагаемого устройства ocjTuecTMiHeTCH по состоянию триггера Т2. Для генераторов псевдослучайных чг1сел при отсутствш неисправностей последовательность состояний любого (в том «шсле и Т) разряда имеет рериод 2 -1 тактов, т. е, яытяется по следовательностьго маястгмапьтсого периода. Если же в регистре воз шкает неисправность (т11Па застревание любого триггера в 1 лши О или эквивалентной этой нексправностт отказ Т1ша обрыв для связи-между разрядами), то наибольшими возможный период для любого разряда (в том числе и составляет БeлтI шнy, равную ближайшей степетг числа 2, не. мек1-дшой, чем гасло Vn тр -3 геров со C4eiv, ным входом в регистре генераторво Это свойство может быть записано в виде неравенства 2%т72 . Или для рассматриваемого приг- ера, если , то S 3 и шкболыттй воз можный период для любого разряда при неисправности равен 8 тактам. Работа предлагаемого устройства к ос1гована на измерении пертгода последовательности произвольного разряда (в данном случае TjJ. Для этого в блок 8 записывается 8 последовательных, состояний .триггера Tg,. Затем производится чтение этих записанных разрядов к сравнение ка кд6го из них с текущим состоянием триггера Т. Чтение продолжается до несовпадения выхода блока 8 к состояния Т. Признаком неисправности является совпадение двук соседних наборов, формируа олх триггером. Tg, из которых содержит по 8 состояний. Отсюда следует, что раэрядность счетчика адреса 3.составляет величину, равную S , т. е. коэффициент

793,

пересчета счетчика 3 равен 2 (ияи 8 для рассматр-иваемого пртыера).

Допустим, схема (фиг. 2) при отсутДопустим также, что начиная с (-1+1)-Тогда на (.i+l)-oM, ( 14-2)-ом, ( -f+S)-

го такта выполняется цикл Заггась (т. е,ом, ..., ( 1+8)-ом тактах состояния Т

на -i-M такте - несовпадение считывае-записывается в ЗУ

мого вз ЗУ разряда и состояния Tg.).20

Такты цикла

Запись xi+l1+21+31+4 |+5

Состояние

счетчика 3 ООО 001010

; Состояние Т, О11

После этого ( т. е. после переполнения счетчика 3 в режиме За- Отсюда следует, что на такте чтения 40 1+14 происходит несовпадение считываемого из блока 8 разряда с состоянием триггера Т,. Это вызывает переключение блока 8 на цикл Запись, .состоящий из 8 тактов, затем в цикле Чге- 5 ние вновь сопостаъляется кажоьШ считываемый из блока 8 бит и сое- гояние Т ао обнаружения нвсовпаце- ния и т.д.

ствии отказа формирует следуюи1ую псевдослучайную последовательность.

пись ) ЗУ переключается в Чтение. Г Пусть на входе Т/ возникает неисправность константа 1 за счет обрыва соединения выхода Ту со входом Т/ (фиг. 3). Это наихудший случай, так как при этом все триггеры (в том числе и работоспособны. В то же время данная неисправность по отношению к Т эквивалентна застреванию единице, Пусть отказ происходит после выполнеНИИ такта I+T имеют период 8 тактов. Следует отм&тить, что отказ, например, триггера Тгприводит к тому, что период состояний триггеров составляет 4 такта, так как на участке Ti-Xj имеется три триггера со счетным входом. Настройка же схемы контроля на признак неиспра& ности в 8 тактов позволяет обнаружить и отказ любого другого триггера (Т f в Такты цикла Чтение -J+9 1+10 Считываемый из ЗУ битО1 Состояние Т- О1

Несовпадение происхоаит на тактеУп+14

Такты цикла Запись1+15 t+ie1+17

Состояние Т 11О

Затем выполняется цикл Чтение. Такты цикла Чтениеi+23 1+25 -1+26 Состояние выхода ЗУ1 Состояние Тл 1 Все 8 тактов чтения сопровождаются совпадением состояния Т„ и выхода ЗУ, что и является признаком ошибки. Обнар жение отказа происходит спустя 23 та& та после его возникновения, т. е. мен1 ше, чем 3-Кс4 24 такта. Если отказ происходит на цикле Чтение, то наихудшим вариантом является отказ в начале этого цикла, а тежже условие, что переключение на запись имеет место на (2 -1)-м такте чтения. Тогда обнару женве такого отказа происходит после () К.д-1 тактов, причем - длительность циклов Запись И Чтение, т. е. время неправильной работы генератора (до обнаружения отка за) можно охарактеризовать величиной, не превышающей 3 К с г}-

Следующий цикл Запись.

ч+21

1+19 1

1+20 О

-f+22 О О в 4 такта кратен наибольшему периоду в 8 .тактов в наихудщем случае), Пусть на такте i +1 (так же, как в рассматриваемом случае отсутствия о каза) начат .цикл Запись. Начиная с такта I+O ЗУ переключается на Чтение (длительность цикла Запись всегда составляет 2 тактов). +27 коэффициент пересчета счетчика 3). Таким образом, если и - разрядный исправь ный генератор имеет период 2 так ч тоБ, то отказ в регистре приводит к снижению периода, который определяется ближайшей , ие меньшей, чал VM , ст&пенью числа 2. Однако если величина № мала, то вероятность 1/2 того, что в испрбшном генераторе два соседних набора, каждый вз которых содержит 2 состояний какогонтибо разряда, равны, велика. Тогда можно увеличить коэффи ииент пересчета счетчика 3 до величины 2. Кратность величии К с4 2 и 2 определяется тем, что оба эти числа представпяхзгт степень чнсла 2. На- щиплер, если регистр генератора не содержяттрвггеров саз счетным входом (т. е. 119 «О), то , Действительно, отказ Тзегистре чисто сдвигового типа npifflo- дит к тому, что состояние крайнего разряда регистра, в направпенин которого осуществляется сдвиг, перестает изме няться , т. е, период равен одному такту. Однако если схему контроля строить на основании , то сигнал ошибки формируется и при исправном генера1. 1 торе с вероятностью -± на каждом 2Ксн 2 такте, Ьсли же увеличить число записы ваемых в блок 8 разрядов до величины 2 7 то можно свести вероятность ложного формирования сигнала ошибки к пренебрежимым значениям при достаточн большом г - -. Следовательно, разрядность 5 счетчика определяется числом Уг триггеров со счетным входом в регистре генератора, если учитывать соотношение 7 2 величина ложного формирования сигнала ошибки 1/2 достаточно мала. В против- ном случае коэффициент пересчета выбирается равным 2, S , таким, что l|2 уменьшается до допустимого значени При этом кратность чисел 2 и 2 обе печивается тем, что оба эти значения являются степенью числа 2. Последовательность, формируемая ге- вератором псевдослучайных чисел, близка к случайной для достаточно больших ве личин V , когда период 2 -1 такой последовательности гораздо больше времени рабочего использования генератора. С другой стороны, необходимость в пост роении многофазных генераторов псевдослучайных чисел часто вызвана требо ваниями к параметрам статических устройств, в составе которых ш геется такой генератор. Например, в системах технологического контроля печатч1ых плат, иоиольаующих статические принципы провер ки, разрядность генератора испытательны псевдослучайных последовательностей о ределяется числом контактов разъема печатной платы и может достигать сотни и более. Необходимость повь1шения быстродействия при формировании псевдослучайных последовательностей приводит к разработке генераторов, регистр сдвига которых целиком выполнен на триггерах со счетным входом, т. е. у которых У1 - ж . В связи с изложенным коэфф{щие{гр пересчета счетичка 3 предлагаемого устрой ства может быть оценен на основе соотношения / И 7 2 Я , где 9 делое положительное число. Если считать что при отсутствии отказов последова 51тельность состояний произвольного 1 -го разряда генератора представляет собой чисто случайную величину, то вероятность того, что два соседних набора последовательных состояний (каждый набор содержит К-2г состояний) -1-го разряда регистра сдвига окажутся одинаковыми, можно найти как величину 1/2 . Если , то вероятность формирования ло кного сигнала ошибки в исправном ге нераторе сотавляет величину 1/2 т. е. величину пренебрежтФДо малую. Если отказ в регистре сдвига предлагаемого устройства происходит в конце некоторого цикла записи, и следующий за ним цикл сопровождается несравнением сигналов схемой 9 тольжо ш последнем К-ом такте, то для обнар жения данной неисправности потребует ся еще один цикл Запись и один цикл Чтение, в конце которого формируется признак отказа, т. е. время работы неисправного 1 енератора до обнаружения отказа в предлагаемом устройстве можно охарактеризовать величиной порядка ЗК тактов. Для известного устройства время неправильной работы генератора можно оценить величиной К коэффициент деления делителя, Кр максимальная абсолютная величина, которая может храниться в реверсивном счет чике. Если сдвиговый регистр генератора имеет VI im, то при одном и том же И Кд-К, т. е. делитель известного уст ройства имеет такой же коэффициент пересчета (деления), .как и счетчик 3, предлаг аемого устройства . При оценке величины Кро известного устройства для упрощения допускаем, что заполнение реверсивного счетчика происходит, если в последовательности состояний ,-i -го выхода генератора подряд Кр, нулей либо единиц. Тогда вероятность ложного формирования сигнала неисправности генератора составляет величину 2/2 К считая выходную последовательность генератора случайной величиной. ЕСЛИ принять, что величины вероятности формирования ложного сигнала отказа ( для известного и предлагаемого устройств 2/2 PC, олжны быть равны, те. 1/2 о отсюда К Kp/;, и время неправильной работы генератора для известного характеризуется величиной порядка К тактов. Таким образом, время обнаружения отказа в регистре сдвига предлагаемым устройством существенно меньше, чем для известного, Hanpvivrep у vn 123, и обнаружешю неисправности visBecTHbtM происходит за 128 -1,710 тактов,, предлагаемому же устройству для этого потребуется -10 тактов. Аппаратурные затраты, необходимые для реализации предлагаемого устройства cpaBjnnvtbi с затратами аппаратуры для известного. В частности, сложность счетчика соответствует сложности делителя известного, сложность функциональных эл®у1ентов (элементы :И, инвертор, за держка) примерно равна сложности функциональных элементов предлагаемого уст ройства (элементы И, инвертор, триггер, схема неравнозначности). Что же касает ся схемы одноразрядной памяти, то сов ременная элементная база располагает такими узлами, вьшолненными на одном кристалле и тмеющими высокую информационную емкость, например элемент ОЗУ 5О5 РУ 4 емкостью 256 одноразрядных слов со схемами утфавления в одном корпусе. Формула изобретен ияя Генератор псевдослучайных чисел, содержащий рекуррентный регистр сдвига, выходы которого являются выходами гене ратора,, счетчик, эл«лент НЕ и два элемента И, причем вход тактовых импульсо генератора соединен с входсж рекуррент ного регистра сдвига и счетным входом 9 5114 счетч ска, выход элилента НЕ подключен к первому входу первого элемента И, отличающийся тем, что, с целью повышения быстродействия, он содержит блок памяти,, элемент наравш значности и триггер, единичный .выход которого подключен ко второму входу первого и первому входу второго элементов И и к управляющему входу блока памяти, информационный вход которого соединен с выходом i-ro разряда рекуррентного регистра сдвига, подключенным , к первому входу элабсента неравноена ьности, второй вход которого соединен с выходом блока памяти, а выход элемента неравнозначности соединен со входом элемента НЕ и вторьпус входом второго элемента И, выход которого подключен к нулевому входу триггера и к входу Сброс счетчика, выход, которого соединен с третьим входом первого элемента И и с единичным входом тригг©- ра, тактовый вход которого подключен к входу тактовых импульсов устройства, соединенному также с четвертым входом первого элемента И, разрядные выходы счетчика подключены к адресным входам блока памяти. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 468231, кл. &06 F 1/02, 1973. 2.Авторское свидетельство СССР № 674007, кл. GO6 F 1/02, 1977. (прототип).