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

Союз Советскнх Соцналнстнцескнх Реслублнк(23) Приоритет- Опубликовано 1 Дата опублико Государотвенный коиитет СССР ео делам изобретений и открытийДК 681.325088.8) 07.79.Бюллетень 26 иия описания 18.07.79 12) Авторы изобретения В. В. Гроль и А. М. Романкевич невский ордена Ленина политехнический институтим. 50-летия Великой Октябрьской Социалистической революции) Заявител ГЕНЕРАТОР ПСЕВПОСЛУЧ Изобретение относится к области вь . числительной техники и может. быть использовано в стохастических счетнорешаюших устройствах.Известное изобретение по авт. св.468231 содержит й -разрядный регистр сдвига с сумматором по модулю 2 в цепи обратной связи, часть разрядов регистра сдвига выполнены на триггерах со счетным входоМ, а остальные Ь-Гп) разрядов - на триггерах с установочными входами, счетные входы первых е триггеров соединены с единичными выходамисоответствующих (о. - пт ) трщтеров, уотанойочные входы которых подключены к выходам первых тп триггеров соответственно Ц ,Йедостатком известного изобретения лвляется невозможность обнаружения неисправности генератора псевдослучайных чисел (ГПСф проявляющейся в уменьшении периода последовательности псевпьслучайных чисел. 2БелЬю изобретения является повышениенадежности работы генератора.Для достижения поставленной целиГПСЧ по авт. св,486231, содержитдешифратор, делитель, элемент задержки,.элемент НЕ, первый и второй элементыИ и реверсивный счетчик, суммирующийи вычитающий, входы которого соединены с выходами первого и второго элементов И соответственно, первые входыЧ которых через элемент задержки и делитель подключены ко входугенератора, авторые входы - к прямому и инверсномувыходам т, -го разряда регистра сдвига,выходы регистра сдвига соединены совходами дещифратора, выход которого через элемент НЕ соединен с третьим входом первого элемента И.На фиг. 1 представлена блок-схемагенератора; на фп . 2 изображено соедита некие триггеров регистра сдвига для,и =5, п 1 -:3,На вход и -разрядного регистрасдвига 1, состоящего из ттт триггеровС,1) - (2,ГО ) со счетным входом и (и -гт ) триггеров 2 ( гп+1) - (2. и ) с установочным входом, заведена шина тактовых импульсов 3, котораа подключена также к входу делителя 4. Выход делителя 4 через элемент задержки 5 сое динен со входом элемента И 6 и входом элемента И 7, Единичный выход произвольного (2. 1 ) -го триггера регистра, сдвига 1 подключен к входу и -входово.го элемента И 8, а также к входу элемента И 6. На остальные ( -1) входы элемента И 8 заведены любые выходы Ь -1) триггеров регистра сдвига 1 Выход элемента И 8 через элемент НЕ 9 соединен с третьим входом элемента И 6.Выходы элементов И 6 и И 7 подключены соответственно к входам 10 и 11 ревер- сивного счетчика 12, выход которого соединен с шиной ошибки 13. Нулевой выход (2, 1 )-го триггера регистра сдвига 1 заведен на вход элемента И 7.. Работа устройства осуществляется следующим образом.Если числа и и и вьбракы в соот ветствии с индексамиедкнственных единичных коэффициентов неразложимого и прими тивного многочлена степени и и, кроме того, числа и и (2 -1) являются взаимно простыми, тогда генерируемая последо вательность псевдослучайных чисел имеет период (2 -1) тактов прк отсутствии отказов в схеме. Так как нулевое состояние регистра сдвига 1 является запрещенным, то для любого разряда регистра сдвига 1 число единичных состояний этого разряда за (2 -1) тактов равно 2 а числоП "1:нулевых состояний (21). Текущая3разность числа единиц и нулей в 4 м40 "разряде регистр сдвига 1 подсчитывается с помощью реверсивного счетчика 12, На вход 3.О (например, вход суммирования) им-.пульс с выхода делителя 4 через элемент задержки 5 и элемент И 6 проходит при совпадении единичного уровня с выхода ( 2.)-го триггера регистра 1 и единичного уровня с выхода элемента НЕ 9. Нулевой уровень на выходе элемента НЕ 9 вырабатывается только в течение одною о из (2 -1) тактов работы генератора, фитак как элемент И 8 дешифрирует только одно кз (2 -1), чисел, причем дла этг числа 3 .-разряд должен находиться в единичном состоянии. Нулевой уровень с выхода элемента НЕ 9 закрывает на один такт элемент И 6 и блокирует добавление одной единицы в счетчик 12, исключая тем самым накопление единиц в счетчике Д12 и переполнение этого счетчика, которое может произойти за счет наличия разницы числа нулевых и единичных состояний (2.)-го триггера регистра 1 в те чение (2 -1) тактов.О"тПри нулевом состоянии (2.) -го триггера импульс с выхода элемента задержки 5 через элемент И 7 проходит на вычитающий вход 11 реверсивюго счетчика 12, Разрядность этого счетчика должна выбиратьса такой, чтобы при правильной . работе едвигового регистра 1 не прокоходило переполнение счетчика 12 за 3 -1 тактов его работы (так как после этого числа тактов содержимое реверсивного счетчика 12 должно быть равно ну:ю, учитывая коррекцию с помощью элемейтов И 8 и НЕ 9, а также прк условии отсутствия отказов в сдвиговом регистре.Поавленке неисправности в регистре 1 приводит к тому, что один или несколько триггеров этого регистра будут постоянно (независимо от сигналов на их входах) находиться в одних к тех же (единичных или нулевых) состояниях, При этом произойдет уменьшение периода генерируемых чисел но сравнению с величиной (2 -1). . Новый период будет равен 2" тактов ( =0 1,2 3 .), величина ощидолаеъ" са из соотношейия, 2 М:, 2 . где 1 - количество триггеров со счетным входом в регистре сдвига 1. Прн появлении многократных ошибок в этом регистре (или же в мвисимоти от числа, хранящегося в регистре в момент возникновения отказа) нервод левой последователь ности может быть меньше чем 2 такК тов,однако величина 2 будет кратна этому новому периоду.Таким образом, если коэффициент де-;ления частоты 4 выбран (установлен)Кравным 2 (т.е. на выход делителя 4 проходит каждый 2 -й тактовый импульс с шины 3), то в реверсивный счетчик 12 будет постоянно добавпаться (или вьгчитаться) единица, так как при неисправномрегистре сдвига 1 (2. 4 )-ый триггер на каждом 2 -также будет находиться вкодном и том же (единичном или нулевом) состоянии. Это приведет к переполнению счетчика 12 и по шике 13 будет выдан сигнал ошибки. Элемент задержки 5 введен для устранения влияния на работу устройства задержек дешвфратора И 8 и элемента НЕ 9, а также переходных процессов при измененин состоания регистра сдвига 1.В качестве примера рассмотрим ГПСЧ, для которого в соответствии с требованиями, предъявляемыми к соотношению величин и и Ф выбраны и "-5 и е з 3. Для такого ГПСЧ (фиг. 2) триггер (2.1)- 5 (2.3) должны быть выполнены со счетным входом, а (2.4) и (2.5) - с установленным. Так какгй =3, то К =2 вследствие того, что 232 . Пусть в резульатате отказа на единичном выходе триггера (2 5) постоянно присутствует высокий (единичный) уровень, а неисправность возникла на р -м такте, когда триггеры регистра сдвига 1 находились в следующих состояния."стриггер .2.1 2,2 2.3 2.4 2.5 состояние 1 О О 1 1При дальнейшем поступлении тактовых импульсов генератор будет вырабатывать такую последовательность:триггер: 2.1 2,2 2.3 2.4 2.Б (+1) такт 1 1 1 1 1 (+2) " О О О 1 (у+3) " 0 1 1 0 1 (+4) " 1 1 О О 1 (+5) 1 1 1 - 1 1 (+6) " 0 . О О 1 1и т.д.Из примера видйо, что, начиная с (+1)-го такта, ГПСЧ вырабатывает поФ1ЗО следовательность чисел с периодом в 4 такта. Следовательно, каждый четвертый тактовый импульс, проходя с выхода де" лителя частоты через элемент задержки, будет совпадать с одним и тем же (ну 15 левым или единичным) состоянием любого триггера регистра сдвига, что приведет .к переполнению реверсивного счетчикаЛналогично можно показать, что воЗ- никновение неисправности другого типа (например, постоянное единичное состояние нескольких триггеров регистра 1) приведет к выдаче последовательности с периодом, меньшюй чем 4 такта, но равным делитеФ 4 лю числа "4.Если время использования генератора меньше, чем 2 (2 -1) тактов, то депшифратор 8 и элемент НЕ 9 могут быть удалены, так как при правильной работе регистра сдвига 1 реверсивный счетчик 12 не переполнится за враля работы, вследствие того, что перед началом ис-, пользования генератора счетчик 12 устанавливается в исходное нулевое состояние (на55 структурной схеме цепи исходной установки не показаны).В случае, если гав =0 (т.е. если в гейе;Рюарах используются только триггеры с установочными входами), существует возможность дальнейшего упрощения заявляемого устройства путем удаления делителя частоты тактовых импульсов, так как при возникновении неисправности в сдвиговом регйстре, триггеры которого выполнены только с установочными входами, период повторения формируемой генераторомефпоследовательности будет составлять один такт, т.е. триггеры регистра не будут изменять свое состояние.Эффективность применения ГПСЧ повышенной надежности можно обосновать исходя из следующих соображений; в автоматизированных системах контроля функциональных модулей (печатных плат) электронно-вычислительных машин, использование статических методов контроля приводит к построению генератора с большим количеством разрядов (числа входных контактов на таких платах может достигать сотни и более). С ростом сложности генератора увеличивается вероятность появления в нем отказов, приводящих к снижению периода генерируемой последовательности и, как следствие этого, к уменьшению надежности и достоверности работы системы статистического контроля, из-аа уменьшения разнообразия чисел, подаваемых на входные контакты проверяемых печатных плат. В связи с этим уменьшается вероятность обнаружения неисправностнй на плате и функциональный модуль, содержащий неисправные элементы, по результатам статистического контроля может быть признан исправным, Следовательно, введение в ГПСЧ возможности обнаружения в нем неисправностей приводит к повышению надежности и достоверности функционирования системы статистического контроля в целом. Формула изобретенияГенератор псевдослучайных чисел по авт. св. М 468231, о т л и ч а ю - щ и й с я тем, что, с целью повышения надежности генератора, он дополнительно содержит дешифратор, делитель, элемент задержки, элемент НЕ, первый и второй элементы И и реверсивный счетчик, суммирующий и вычитаюший входы которого соединены с выходами первого и второго элементов И соответственно, первые входы которых через элемент задержки и делитель подключены ко входу генератора, а вторые входы - к прямому и инверс-. ному выходам-го разряда регистра674007 Источники информации, принятые вовнимание при экспертизе 1. Авторское свидетельство СССРЯо 468231, кл. Ь 06 Р 1/02, 1973. Фиг. 1 ив,8 Составитель С. Кй. Зубов Гехред Л. Алферова79 едакто 78/48ЦН Заказ Подписноекомитета СССРи открытийушскаи"наб.д. 4/ Филиал ППП фПатейт, г. Ужгород, ул. Проектная 7сдвига, выходы регистра сдвига соединенысо входами дешйфратора, выход которогочерез элемент НЕ соединен с третьимвходом первого элемента И. Тираж 7 ИИПИ Государс по делам изо 13038; Москва, Ж