Генератор равномерно распределенных псевдослучайных чисел Советский патент 1979 года по МПК G06F1/02 G07C15/00 

Изобретение относится к области вь1 числительной техники и может, быть использовано в стохастических счетнореша юйшх устройствах. Известное изофетение по авт. св. № 468231 содержит п -разрядный регистр сдвига с сумматором по модулю в цепи обратной связи, часть разрядов регистра сдвига вьптолнень на триггерах со счетнь1М входом, а осТальньте (n-m) разрядов - на триггерах с установочным входами, счетные входы первых m триггеров соединены с единичными вьЦоД/ами соответствующих (й- m ) триггеров, установочные входы которых подключены к вьпсодам первых m триггеров соответственно l . Недостатком известного изобретения является невозможность обнаружения неисправности генератора псевдослучайных чисел (ГПСЧ проявляющейся в уменьшении периода последовательности псевпослучайных чисел. ЦелЬю изобретения 1юляется повышение надежности работы г енератора. Для достижения поставленной цели ГПСЧ по авт. св. hfc 486231, содержит дешифратор, делитель, элемент задержки, элемент НЕ, первый и второй элементы И и реверсивньгй счетчик, суммирующий и вычитающий, входы которого соединены с выходами первого и второго элементов И соответственно, первые входы которых через элемент задержки и делитель подключены ко входу генератора, а вторые входы - к прямому и инверснбму выходам i -го разряда регистра сдвига, вьгходы регистра сдвига соединены со :входами дещи4)атора, выход которого через элемент НЕ соединен с третьим входом первого элемента И. На фиг.,JL представлена блок-схема генератора; на фиг. 2 изображено соединение триггеров регистра сдвига для ,п -5, m 3. На вход П -разрядного регистра сдвига 1, состоящего из m триггеров Г2,1) - (2.ГП ) со счетнь(м входом и (п -т ) триггеров 2 С m+l) - (2. п ) (5 уйтан6вочнб1м входом, заведёнй шина тактовьсс импуттьсов 3, которая подключе на также к входу делителя 4, Выход делителя 4 через элемент задержки 5 соединен со входом элемента И 6 и входом элемента И 7. Единичный выход произвольного (2. J )-го триггера регистра сдв1Па 1 подключен к входу п -входового элемеш-а И 8, а также к входу элемента И 6. На остальные (п -1) входы элемента И 8 заведены любые выхоя г (п -1) триггеров регистра сдвига 1. Вы- ход элемента И 8 через .элемент НЕ 9 . соединен с третьим входом элемента -И 6. Выкоды элементов И 6 и И 7 подключены соответственно к входам 10 и 11 реверсивного счетчика 12, вьжод которого соединен с шиной ошибки 13. Нулевой выход (2, )-го триггера регистра сдвига 1 заведен на вход элемента И 7, Работа устройства осуществляется сле дующим образом. i Если числа п и гп выбраны в соответствии с индексами единственных едини ных коэффициентоб неразложимого и примитинного многочлена степени п и, кроме того, чисута гп и (2 -1) являоются взаюлно простыми, тогда генерируемая последовательность псевдослучайных чисел имеет период (2 -1) тактов при отсутствии от- казоа в схеме. Так как нулевое состояние регистра сдвига 1 является запрёщенньал, то для любого разряда регистра сдвига 1 число единичных состояний этого рйз1эяда за (2 -1) тактов равно 2 ; а число нулевых состояний - (). Текущая разность числа единиц и нулей в t -м разряде регистр сдвига 1 подсчитывается с йЬмощью реверсивного счетчика 12. На вхо .10 (например, вход суммирования) им.пульс с выхода делителя 4 через элемент задержки 5 и элемент И 6 проходит при совпадении единичного уровня с выхода (2. i )-гр триггера регистра 1 и едишг ного уровня с выхода; элемента НЕ 9. Нулевой уровень на выходе элемента НЕ 9 вырабатьгоается только в течение одного из (2 -1) тактов работы генератора, так КК& элемент И 8 деши4рирует только одно из (2 -1), чисел, причем для этого числа 4 .-разряд должен находиться в единичном состоянии. Нулевой уровень с выхода элемента НЕ 9 закрьгоает на один такт элемент И 6 и блокирует добавление одной единицы в счетчик 12, исключая тем самым накопление единиц в счетчик.е 12 и переполнение этого счетчика, которое может произойти за счет наличия разницы числа нулевых и единичных состояний (2. )-го триггера регистра 1 в т&чение (2 -1) тактов. I При нулевом состоянии (2л)-го триггера т тупьс с выхода элемента задержки 5 через элемент И 7 проходит на вычитающий вход 11 реверсивного счетчика 12, Разрядность этого счетчика должна выбираться такой, чтобы при правильной: работе сдвигового регистра 1 не происходило переполнение счетчика 12 за й „1 тактов его работы (так как после этого числа тактов содержимое реверсивjioro счетчика. 12 должно быть равно нулю, учитывая коррекцию с нок {рщью элементов И 8 и НЕ 9, а также при условии отсутствия отказов в сдвиговом регистре). Поябление неисправности в регистре 1 пргобдйт тому, что один или несколь1со триггеров этого ретистра будут постоянно (независимо от сигналов на их входах) находиться в одних и тех же (единичных или нулевых) состояниях При этом произойдет уменьшение периода генерируемы ; ... .. .„ чисел по ср(авнению с величиной (). Новый перио д будет равен 2 тактов (t 0,1,2,3 ,.,)( вёлитана отфадапя© - - ся из соотношения, 2 где k - количество тригг ов со счетным входом в регистре сдвига 1. При появлении многократных оишбок ъ этом регист ре (или же в за&исимоСти от числа, хра : нйщегбся в регистре в момент возникновения отказа) период левой последователь:ности может быт меньше чем 2 тактов, однако величина 2 будет кратна этому новому периоду. Таким образом, если коэффициент деления частоты 4, выбран (установлен) равным 2 (т.е. на выход делителя 4 проходит каждый 2 -и тактовый импульс --л с шины 3), то в реверсивный счетчик 12 будет постоянно добавляться (или вычитаться) единйпа, так как при неисправном регистре сдвига 1 (2. 4 )-ь1й триггер н каждом 2 -также будет находиться в одном и том же (единичном или нулев) состоянии. Это приведет к переполнению счетчика 12 и по шине 13 будет вьщан сигнал ошибки. Элемент задержки 5 введен для yci ранения влияния на работу устройства зЬ1ержек дешифратора И 8 и элемента НЕ 9, а также п еходныэс процессов гри изменении состояния регистра сдвига 1. В качестве примера рассмотрим ГПСЧ для которого в соответствии с требованиями, предъявляемыми к соотношению величин п и m , выбраны о -5 игл«3. Для такого ГПСЧ (фиг. 2) триггер (2.1) (2.3) должны быть вьтолнены со счетным входом, а (2.4) и (2.5) - с установленным. Так как ТЯ 3, то Ц 2 вследствие того, что 2 3 2 . Пусть в резуль тате отказа на единичном выходе триг гера (2.5) постоянно присутствует вьюокий (единичный) уровень, а неисправность возникла на j/ -м такте, когда триггеры регистра сдвига 1 находились в спеяующих состояниях: триггер 2.1 2.2 2.3 2.4 состояние 1 О О 1 1 При дальнейшем поступлении тактовых импульсов генератор будет вьфабатьгоать такую последовательность: триггер: ( j +1) такт (j-bS) (}+5) (i -6). и т.д. . , , .::; . Из примера видно, что, начиная с (j+lj-ro такта, ГПСЧ вырабатывает по« следовательность чисел с Периодом в 4 такта. Следова1:«льно, каждый четвертый тактовый импульс,проходя с выхода делителя частоты через элемент задержки, будет совпадать с одним и тем ж (нулевым или единичным) состоянием любого триггера регистра сдвига, что привед .к переполнению реверсивного счетчика. Аналогично можно показать, что Bogi никновение неисправности другого типа (например, постоянное единичное состояни нескольких ргригтеров регистра 1) приведет к выдаче последовательности с периодом, меньшим чем 4 такта, но равным целите лю числа 4. Если время использования генератора меньше, ч&л 2 « (2 -1) тактов, то деши(}ратор 8 и элемент НЕ 9 могут быть удалены, так как при правильной работе регистра сдвига 1 реверсивный счетчик 12 не переполнится за время работы, вследствие того, что перед началом исч, пользования генератора счетчик 12 устана ливается в исходное нулевое состояние (на структурной схеме цепи исходной установ ки не показаны). В случае, если (т.е. если в гей рлтррах испйльэуются только триггеры с установочными входами), существует возможность дальнейшего упрощения заявляемого устройства путем удаления делителя частоты тактовьк импульсов, так как при .возникнов ении неисправности в сдвиговом регистре, триггеры которого выпрлнены только с установочными входами, период повторения формируемой генератором последовательности будет составлять один такт, т.е. триггеры регистра не будут изменять свое состояние. Эффективность применения ГПСЧ повышенной надежности можно обосновать исходя из следующих соображений: в автоматизированных системах контроля фулкциональных модулей (печатных ) электронно-вычислительных машин, использование статических методов контроля приводит к пост роению генератора с большим количеством разрядов (числа входных коктактов на таких платах может достигать сотни и более). С ростом сложности генератора увеличиваете вероятность появления в нем отказов, приводящих к снижению периода генерируемой последовательности и, как следствие этого, к умен эшению надежности и достоверности работы сист« 1Ы статистического контроля, уменьшения разнообразия чисел, подаваемых на входные контакты проверяемых печатных плат. В связи с этим уменьшается вероятность обнаружения неисправное гай на плате и функциональный модуль, содержащий неисправные элементы, по результатам статистического контроля может быть признан исправным. Следовательно, введение в ГПСЧ ВОЕМОЖНОСТИ обнаружения в нем неисправностей приводит к повьшению надежности и достоверности функционирования системы статистического контроля в целом. Формула и 3 о б р е т е н и -я Генератор псевдослучайных чисел по авт. св. № 468231, отличающ и и с я тем, что, с целью повьппения надежности генератора, он дополнительно содфжит дешифратор, делитель, элемент задержки, элемент НЕ, первый и второй элементы И и реверсивный счетчик, суммирующий и вычитающий входы которого соединены с выходами первого и второго элементов И соответственно, первые входы которых через элемент задержки и делитель подключены ко входу генератора, а вторые входы - к прямому и инверс- . ному вьгходам i -го разряда регистра сдвига, выходы регистра здвига соединены со входами дещй(|ратора, вьисод которого через элемент НЕ соединен с третьим входом первого элемента И. Источники информадии, принятые во внимание при экспертизе 1, Авторское свидетельство СССР № 468231, клГв 06 F 1/02, 197Ь.