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

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

Иллюстрации

Показать все

Реферат

 

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

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

Республик (t>)935951

Ф ъ

/ (6! ) Дополнительное к авт. свид-ву (22) Заявлено l 8.04.80 (2() 291 1282/1 8-24 с пригоелинением заявки Рй (23) Приоритет—

Опубликовано15.06 82. Бюллетень .% 22

Дата опубликования описаиия15 06 82 (51)М. Кл.

606 F 7/58

Гооудеротееииый комитет оо делам изобретений и открытий (6 ) ДК681.325, (088.8) A. М. Романкевич и B. В. Гроль (72) Авторы изобретения (7l) Заявитель

Киевский ордена Ленина политехнический ттнститут им. 50летия

Великой Октябрьской социалистической революции (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислителт ной технике и автоматике и может найти

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

Известен генератор равномерно распределенных псевдослучайных чисел, содержащий у1 -разрядный регистр сдвига с сумматорами по модулю два в цепи обратной связи, причем первые уп разрядов регистра сдвига выполнены на трщ герах со счетным входом, а остальные (тт - VVI) разрядов — на триггерах с установочным входом (1).

Недостатком этого генератора явля ется невозможность обнаружения отказов элементов памяти регистра сдвига; приводящих к существенному уменьшению периода генерируемой последовательности.

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

Недостатком известного устройства является наличие длительного периода неправильной работы генератора от момента возникновения отказа в регистре сдвига до обнаружения неисправности схемой контроля.

Цель изобретения - повышения быстродействия за счет сокращения времени обнаружения неисправности.

Для достижения поставленной цели в известный генератор равномерно распределенных псевдослучайных чисел, содержащий рекуррентный регистр сдвига, выходы которого являются выходами генератора, счетчик, элемент НЕ и два элемента И, причем вход тактовых импуль сов соединен с входом рекуррентного регистра сдвига и с счетным входом счет чика. выход элемента НЕ подключен к первому входу первого элемента И, введены блок памяти, элемент неравнозначности и триггер, единичнъ|й выход которого подключен ко второму входу первого и первому входу второго элементов И и к управляющему входу блока памяги, информационный вход которого соединен с выходом л -го разряда рекуррентного сдвига, подключенным также к первому входу элемента неравнозначности, второй вход которого соединен с выхсдом блока памяти, а выход элемента неравнозначности соединен со входом элемента HE и вторым входом второго элемента И., выход которого подключен к ну15 левому входу триггера и к входу "Сброс счетчика, выход которого соединен с треть|м входом первого элемента И и с единичным входом триггера, тактовый вход которого подключен к входу тактовых импульсов устройства, соединенному также с четвертым входом первого эле

«лента И, разрядные выходы счетчика подключены к адресным входам блока памяти.

На фиг. l представлена структурная схема генератора равномерно распределенных псевдослучайных чисел, на фиг. 2 - структура регистра для случая

11 =6, (где p — - число разрядов регистра), >О на фиг. 3 — схема неисправного регистра.

В состав генератора входит yt -разрядный регистр сдвига 1 с сумматорами по модулю два в цепи обратной связи, на вход которого подключена шина синхроимпульсов 2, соединенная также со счетным входом счетчика 3. Выход 4 с выхода счетчика 3 подключен к единичному входу триггера 5, единичный выход которого заведен на входы элвментов И 6 и 7. Выход 4 подключен также ко входу элемента И 6, со входом которого соединена шина синхроим пульсов 2, заведенная, кроме того, на тактовый вход триггера 5. Выходы счет» чика 3 подк|почены к адресным входам блока памяти 8, на управляющий вход ко*=торой подключен единичный выход триг=гера 5. Информационный вход блоки памяти 8 соединен с выходом j -го 5Î (1 О, 1, 2, ..., И-1) разряда регистра сдвига 1. Выход этого же л-го разРяда подключен к первому входу элемента неравнозначности 9, на второй вход которого заведен выход памяти 8. Вы- 55 ход элемента неравнозначности 9 подклю= чен ко входу элемента И 7 непосредст венно„ а через элемент HE 1 О - ко вхо= ду элемента И 6. Выход элемента И 7 заведен HQ вход .à-cBJlh>tort установки счетчика 3 и на нулевой вход триггера 5. Цепи исходной (пультовой) установки не и оказаны. устройство работает следующим образом.

Исходное состояние — нулевое для счетчика 3 и нулевое для триггера 5.

Нулевой сигнал, подаваемь|й с выхода триггсра 5 на управляющий вход блока памяти 8, соответствует режиму 3 лись" ддя блока 8. Каждый приходящий по гггггне 2 синхроим|тульс меняет состояние регистра 1 и добавляет единицу в счет» чик 3, на выходах которого формируется адрес очередной ячейки блока 8, Таким образом, каждый синхрошлпульс шины 2 осуществляет запись состояния q -го выхода регистра 1 в очередную ячейку . блока памяти 8. Процесс записи повторяется до заполнения счетчика 3. В этом случае на шине 4 формируется единичный сигнал, поступающий на единичный информационный вход триггера 5, что приводит к переключе ппо последнего в единицу с приходом очередного синхрош.лпульса на тактовый вход триггера с шины 2. Отметим, что в режпле Запись" элементы

И 6 и 7 закрыты нулевьпл сигналом с выхода триггера 5. Переключение триггера 5 в единицу после заполнения счет чика 3 сопровождается формированием единичного сигнала Чгение, подаваемого ца управляющий вход блока памяти 8 с единичного выхода триггера 5. Одновременно синхросигнал, переключающий, в единицу триггер 5, обнуляет счетчик 3 (после единичного состояния всех разрядов счетчика 3 следующее состояние— нулевое). Каждый следующий синхро— импульс с шины 2, по-прежнему, изменяет состояние регистра 1 и осуществпяет теперь уже последовательное считывание ячеек памяти блока 8 путем добавления единицы в счетчик 3. Каждый такт чтения сопровождается сравнением с помощью элемента перавнозначности 9 состояния б .oza 8 rr состояиля 4 -ro хода per ":cTpQ 1. Элемент неравнозначности 9 на каждом такте цикла "Чтение осуществляет сравнение двух состояний выхода -1 -ro разряда регистра 1, между которыми прошло тактов работы генератора псевдои учайных чисел, K=2, 3 коэффициент пересчета счетчика 3, )"— целое полохщтельное число Несовпадение на некотором такте считываемог о слова, т. е. единичный признак отказа в генераторе формируется на выходе элемента И 6 и случае, если последний

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

Рассмотрим контроль генератора псев дослучайных чисел на основе предлагаемого принципа для случач и « 6 (И -чиоJTo разрядов peI HcTpB 1 ) ° Для такого ге нератора W:=5.

Допустим, контроль регистра в соот ветствии с принципом предлагаемого устройства осуществляется 10 состоянию триггера Т . Для генераторов псевдослучайных чисел при отсутств пт неисправI ностей последовательность состояний любого (в том числе и Т ) разряда имеет рериод 2 -1 тактов, т, е. является по следовательностью макстматтьного периода.

Если же в регистре возникает неисправность (типа застревание любого триггера в 1 . U -и О или эквивалентной этой неисправности отказ типа обрыв для связи между;-аэрядами), то наибольший возможный период для лтобого разряда (в том числе и Т ) составляет величину, равную бтпвкайшей степени числа "2", не, меньшой, чем число N триггеров со счет ным входом в регистре генератора. Это свойство может быть записано в виде неравенства с

2 )gyy,- 2

Или щи рассматриваемого примера, если 5, то 5 3 и наибольший возможный период для любого разряда при неисправности равен 8 тактам. Работа предлагаемого устройства и основана на измерении периода последовательностн произвольного разряда (в данном случае

T ). Для этого в блок 8 записывается

8 последовательных состояний .триггера Tg. Затем производится чтение этих записанных разрядов и сравнение каждого иэ них с текущим состоянием триггера Т<.

Чтение продолжается до несовпадения выхода блока 8 и состояния Т . Признаком неисправности является совпадение двух соседних наборов, формируемых трщгером Т, каждый иэ которых содержит по 8 состояний. Отсюда следует, что ра"-ьрядность счетчика адреса З.составляет величину, равную 6, т. е. коэффтшиент

5 93595 1 из блока 8 одноразрядного слова и со . стояния 1 -ro выхода регистра 1 приводит к формированию единичного сигна ла на выходе элемента неравноэначности

9 и на выходе элемента И 7 (так KBK триггер 5 находится в единичном состоянии - режим Чтение" ). Единичный сигнал с выхода элемента И 7 сбрасывает в нуль счетчик 3 и после прихода ближайшего синхроимпульса по шине 2 на такто-<О вый вход триггера 5 осуществляет переключение данного триггера в нулевое состояние, т. е, переводит блок памяти 8 в режим Запись". Если несравнение считываемого из блока 8 одноразрядного слова и состояния -го выхода регистра 1 произошло лишь на последнем К«ом тактс чтения (все предшест вуюшие такты такого пик#а чтения сопровождаются. нулевыми сигналами ра- 20 венства с выхода схемы неравнозначнос-". ти 9), то обнуление счетчика 3 очередным сигналом по шине 2 лишь подтвердится сигналом по входу начальной установки с выхода элемента И 7. Элемент же И 6 закрыт на этом такте нулевым сигналом свыхо,да инвертора 10, на вход которого поступает единичный приз нак несравнения.

1 ЗО

Обычно генераторы псевдослучайных чисел строятся иэ расчета получения максимально возможного периода 2" -1.

В случае же отказа типа застревание одного или нескольких элементов памя35 ти регистра сдвига период такого неисп- равного генератора определяется, исходя иэ соотношения 2 )/ Wl 7 2, где ) целое положительное число, vn- число триггеров со счетным входом s регистре сдвига. Если коэффициент пересчета счетчика 3 К=2 . 2, тогда величина К кратна величине периода неисправного генератора. Следовательно, при возникно вении отказа в регистре 1 период последовательности на 1»м выходе регистр ра определяется не величиной 2 -1, и как это было бы в исправном генераторе, а гораздо меньшей величиной 2 . Так как коэффициент пересчета счетчика

ЗК у 2 и кратен величине 2, то поо50 ле К тактов записи последовательных

К состояний 1-го выхода неисправно го регистра 1 следуют К тактов чтения содержимого блока памяти 8, причем на каждом из этих тактов чтения осуществляется сравнение состояния го выхода регистра 1 и считываемого на этом такте из блока 8 одноразрядного

93.") 45 1

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

Допустим, схема (фиг. 2 ) при отсутствии отказа формирует следующую псевдослучайную последовательность.

Т Т Т Т Т № такта Т Т Т Т Т Т

6 Д 4- 3

0 О 1 1 О 4+8 О 1 1 0 1 1

% такта Т

1+1 0 +2 О 0 О 1 О 1 +9 1 О О 1 1 0 +3 1 0 0 1 1 1 +10 1 1 0 1 О

О 1 О 1 О О j+11 О 1 1 1 1 1

1+5 О 0 1 1 1 О 1+12 1 О О О О 0

0 0 1 О 0 1 +13 1 1 О О О О

1 О 1 1 О 1 <+14 1 1 1 О О 0

j+6 с

1+7, Допустим также, что начиная с (1+1)- Тогда на (1+1)-ом, (i+2)-ом, (+3)го такта выполняется цикл "Запись (т. е, ом, ..., (<+8)-ом тактах состояния Т на 4 м такте - несовпадение считывае- записывается в ЗУ мого ю ЗУ разряда и состояния Тд). 20

Такты цикла

Запись 4+8

1 +1 1+2 4+3 <+4 1+5 j+ 5 1+ 7

Со стоя ние счетчика 3 000 001 010 011 110 111

: Состояние Т О 1

1 О О 1 1 1

После этого (т. е. после пере- пись ) ЗУ переключается в режим полнения счетчика 3 в режиме "За- "Чтение". зо

Такты цикла

«Чтение +9 <+10 +11 1+12 "+13 +14

Состояние счетчика 3 000 001 010 011

100 101

Считываемый из ЗУ бит 0

О

Состояние Т О

Т4 1 Т Тф 3 4(1 0 1 1 0 1 № такта

О 1 1 0 1 1

0 1 1 О

1 О

4+10

1+1 1

О 1 0 1 О

1 О 1 1 1 1

Отсюда следует, что на такте чтения 4о +14 происходит несовпадение считываемого из блока 8 разряда с состоянием триггера Т . Это вызывает переключение блока 8 на цикл Запись", состоящий нз 8 тактов, затем в цикле Чте- 45 нне" вновь сопостаьляется каждый считываемый из блока 8 бит и сост ояние Т до обнаружения нес овпа пения н т д. - °

Пусть на входе Т(возникает неисправность константа 1 за счет обрыва соьдинения выхода Т со входом Т q (фиг. 3).

Это наихудший случай, так как при этом все триггеры (в том числе и Т ) работоспособны. Б то же время данная неисправность по отношению к Т, эквивалентна

"застреванию Т в единице.

Пусть отказ происходит после выполнения такта 1+7

0 0

935951

1 1

4+12

q +13

rt +14. +15

1+16

0 0

0 1

0 0

1 0

0 1

1 1

1 0

1 рассматриваемом случае, так как период в 4 такта кратен наибольшему периоду

Ф в 8;тактов в наихудшем случае).

Состояния регистра и триггера Т имеют период 8 тактов. Следует отме- 1о тить, что отказ, например, триггера Т приводит к тому, что период состояний триггеров Т -Т составляет 4 такта, так как на участке Т - С имеется три триггера со счетным входом. Настройка же схемы контроля на признак неисправности в 8 тактов позволяет обнаружить и отказ любого другого триггера (Т в

Пусть на такте 3 +1 (так же, как в рассматриваемом случае отсутствия от» каза) начат, цикл юЗаписью Начиная с такта +9 ЗУ переключается на Чтение" (длительность цикла Запись всегда составляет 2 *=8 тактов).

Такты цикла

Чтение

j+9 j+1 0 й-1 1 +1 2 4+1 3 1+1 4

Считываемый из ЗУ бит 0

0

Состояние Т

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

Несовпадение происхоцит на тактеМ+14 );акты цикла

Запись 1+1 5 <+16 1+17 +1 8 < +19 +20 4+21 +22

0 0 0

Состояние Т 1

1 0

Затем выполняется цикл Чтение .

Такты цикла

Чтение 1+23 +24 i+25 1+26 +27 i+28 1+29 4+30

Состояние выхода ЗУ 1 1 0 1 1

Состояние Т 1 1 0 1 1 0 0 !

Все 8 тактов чтения сопровождаются коэффициент пересчета счетчика ).

3). Тасовпадением состояния Т и выхода ЗУ, ким образом, если и - разр sutHbta исправя ° что и является признаком ошибки. Обнару ный генератор имеет ри д

° пе о 2 м 1 так жение отказа происходит спустя 23 так тов, то отказ в регистре приводит к

45 кото ый о деляется после его возникновения т. е. мень снижению периода, р пре щ сте3- К 24 такта. Если отказ бпижайшей, не меньшей, чем ич, ше, чем - К;-4 т числа м2ю Однако если величина происходит на цикле Чтение, то наи пенью числа 2 . днако е х дшим вариантом является отказ в на- р мала, то веро но то ве оятность 1/2 того, что худ чале этого цикла, а также условие, что в исправном генера ре два то соседних на»

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

2 +2 «длительность циклов Запись

4 ю ю К тность величин К с **2 и и Чтение, т. е. время неправильной М . 2 определяется тем, чт что оба эти числа ставпяют степень числа 2 . Наботы генератора (до обнаружения отка- представп

ebs ст генеуетора не содер» эа) можно охарактеризовать величиной, пример если реги р Ж

"т гге в со счетным входом (т. е. не превышаюшей 3- К q 4тактов (Кщ- ядрит"триггеро

935951

Q ), то 2 52 1. Действительно, отказ в

«регист ре чис To сдвиг О В Ого типа приво дит к тому, что состояние крайнего разряда регистра, в направлении которого осуществляется сдвиг, перестает изме= няться, т. е. период равен одному такту. Однако если схему контроля строить нв основании Кон=2 1, то сигнал ошибки формируется и при исправном I eIIepa-!

IÎ торе с вероятностью — = - на каждом

2Ксн 2 такте. Если же увеличить число записываемых в блок 8 разрядов до величины

2 7 2, то можно свести вероятность ложнОГО формирования сигнала Ошибки к 15 пренебрежимым значениям при достаточно большом 1" у;„

Следовательно, разрядность g счетчика 3 определяется числом Vn триггеров со счетным входом в регистре генератора, если учиты ть соотношение 2 >rI7 2," величина ложного формирования сигнала ошибки g/g< достаточно мала. В противном случае коэффициент пересчета выбирается равным 2, v ), таким, что д5

1 ф уменьшается до допустимого значения, При этом кратность чисел 2 и 2 обесY печивается тем, что оба эти значения являются степенью числа 2".

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

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

45 ределяется числом контактов разъема печатной платы и может достигать сотни и более. Необходимость повышения быстродействия при формировании псевдослучайных последовательностей приводит к раз50 работке генераторов, регистр сдвига коTopbIx целиком выполнен на триггерах со счетным входом, т. е. у которых = и

В связи с жложенным коэффицие п- пересчета счетичка 3 предлагаемого устройства может быть оценен на основе соот ношения К 2 )/ И 7 2 ), где целое положительное число. Если считать, что IlpH отсутствии отказов последова— тельность состояний произвольного q -го разряда генератора представляет собой чисто случайную величину, то вероятность того, что два соседних набора последова» тельных состояний (каждьIA набор содержит К=Я состояний) 1 -го разряда ре-! гистра сдвига окажутся одинаковыми, можно найти как величину 1/2 . Если

И=123, то вероятность формирования ложного сигнала ошибки в исправном ге нераторе сотавляет величину 1/2 т. е. величину пренебрежимо малую.

Если отказ в регистре сдвига предлагаемого устройства происходит в конце некоторого цикла записи, и следующий за ним цикл "Чтение сопровождается несравнением сигналов схемой 9 только па последнем K-ом такте, то для обнаружения данной неисправности потребует ся еще один цикл Запись" и один цикл

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

ЗК тактов.

Для известного устройства время неправильной работы генератора можно оценить величиной К>, К >с, где Кдкоэффициент деления делителя, К максимальная абсолютная величи на, котс рая может храниться в реверсивном счетппе. Если сдвиговый регистр генератора имеет у = Yn, то при одном и том же и Кд=К, т. е. делитель известного устройства имеет такой же коэффициент пересчета (деления),,как H счетчик 3> предлагаемого устройства . При оценке величины К Ос. известного устройства для упрощения допускаем, что заполнение реверсивного счетчика происходит, если в последовательности состояний .j -го выхода генератора подряд К нулей либо единиц. Тогда вероятность ложного формирования сигнала неисправности генератора составляет величину

2/2 К с, считая выходную последователь ность генератора случайной величиной.

Если принять, что величины вероятности формирования ложного сигнала отказа для известного и предлагаемого у-стройств должны быть равны, т е. 1/2 2/2 РС, k

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

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

935051

14 известного, например и =N= 123, K=128 и обнаружение неисправности известным происходит за 128 — 1,7 10 тактов,. предлагаемому же устройству для этого потребуется 3 128 4 ° 10 тактов.

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

ОЗУ 505 РУ 4 емкостью 256 одноразрядных слов со схемами управления в одном корпусе.

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

Генератор псевдослучайных чисел, содержащий рекуррентиый регистр сдвига, 30 выходы которого являются выходами генеpampa, счетчик, элемент HE и два элемента И:, причем вход тактовых импульсов генератора соединен с входом рекуррентного регистра сдвига и счетным входом з счетчика, выход элемента HE подключен к первому входу первого элемента И, о т л и ч а ю m и и с s тTеeмM, что, с целью повышения быстродействия, он содержит блок памяти,, элемент неравнозначности и триггер, единичный .выход которого подключен ко второму входу первого и первому входу второго элементов И и к управляющему входу блока памяти, информационный вход которого соединен с выходом (-го разряц1 рекуррентного регистра сдвига, подключенным к первому входу элемента неравнозначности, второй вход которого соединен с выходом блока памяти, а выход элемента неравнозначности соединен со входом элемента HE и вторым входом второго элемента И, выход которого подключен к нулевому входу триггера и K входу Сброс счетчика, выхсд которого саединен с третьим входом первого элемента И и с единичным входом тригге ра, тактовый вход которого подключен к входу тактовых импульсов устройства, соединенному также с четвертым входом первого элемента И, разрядные выходы счетчика подключены к адресным входаМ блока памяти.

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

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

l4 468231, кл. Сч06 F 1/02, 1973.

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

% 674007, кп. 606 F 1/02, 19 (7. (прототип) .

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

Редактор Л. Повхан Техред К.Мьщьо Корректор М. Шароши

Заказ 421 3/52 Тираж 73l Подпис ное

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

T.Х3035, .Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г. Ужгород, ул. Проектная, 1