ГЕНЕРАТОР ПОРЯДКОВЫХ СТАТИСТИК Российский патент 1994 года по МПК G06F7/58 

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

Известен генератор последовательностей случайных чисел (авт.св. СССР N 1179325, кл. G 06 F 1/02, 1986), содержащий блок памяти, датчик случайных чисел, схему сравнения, генератор тактовых импульсов, два триггера, три счетчика, три ключа, шесть элементов И, блок элементов ИЛИ и позволяющий генерировать последовательности случайных чисел с требуемым одномерным законом распределения вероятностей и экспоненциально-косинусными автокорреляционными функциями.

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

Известно также устройство (авт.св. СССР N 1327102, G 06 F 7/58, 1987), содержащее блок памяти, датчик случайных чисел, схему сравнения, генератор тактовых импульсов, триггер, три счетчика, два ключа, блок элементов ИЛИ, два элемента задержки. Данное устройство выполняет те же функции, что и первый аналог, но отличается от него простотой.

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

В качестве прототипа выбран генератор порядковых статистик (авт.св. СССР N 1312569, кл. G 06 F 7/58, 1987, содержащий блок памяти, датчик случайных чисел, схему сравнения, генератор тактовых импульсов, два триггера, пять счетчиков, восемь ключей, три блока элементов ИЛИ, два элемента задержки, три блока вычитания, семь элементов И, элемент НЕ. Данное устройство позволяет генерировать порядковые статистики с требуемым рангом.

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

Целью изобретения является упрощение генератора.

Цель достигается тем, что в генератор введены блок памяти, два элемента задержки и две схемы сравнения, но исключаются триггер, счетчик, семь ключей, блок элементов ИЛИ, три блока вычитания, четыре элемента И, элемент НЕ. Удаление этих элементов и связей между ними значительно упрощает схему генератора.

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

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

Генератор порядковых статистик содержит генератор 1 тактовых импульсов, выход которого соединен с вторыми входами элементов И 2 и 3, первые входы которых соединены с прямым и инверсным выходами триггера 4. Выход элемента И2 соединен с входом элемента 5 задержки и первым входом элемента ИЛИ 6, выход которого соединен со счетным входом счетчика 7. Выход переполнения счетчика 7 соединен с первым входом элемента И 8 и с входом элемента 9 задержки. Выход счетчика 7 соединен с адресным входом блока 10 памяти. Выход блока 10 памяти соединен с первым входом блока 11 сравнения. Выход элемента 5 задержки соединен с входами управления считыванием блоков 10 и 12 памяти. Выход "меньше" блока 11 сравнения соединен со счетным входом счетчика 13 и первым входом элемента ИЛИ 14. Выход "равно" блока 11 сравнения соединен с вторым входом элемента ИЛИ 14. Выход этого блока соединен со счетным входом счетчика 15. Выходы счетчиков 13 и 15 соединены с первыми входами блоков 16 и 17 сравнения, к вторым входам которых подключен вход всей схемы. Выход элемента 9 задержки соединен с установочными входами счетчиков 13 и 15 и первым входом элемента ИЛИ 18, выход которого соединен со счетным входом счетчика 19. Выход переполнения счетчика 19 соединен с установочным входом триггера 4, а информационный выход - с адресным входом блока 12 памяти, выход которого соединен с вторым входом блока 11 сравнения и информационным входом ключа 20. Выход "меньше" блока 16 сравнения и "больше" блока 17 сравнения соединены с вторым и третьим входами элемента И 8. Выход элемента И3 соединен с вторыми входами элементов ИЛИ 6 и 18, входом элемента 21 задержки и входом "опрос" датчика 22 случайных чисел, выход которого соединен с информационными входами блоков 10 и 12 памяти. Выход элемента 21 задержки соединен с входами управления записью блоков 10 и 12 памяти. Выход элемента И 8 соединен с разрешающим входом ключа 20, с входом элемента 23 задержки, выход которого соединен со счетным входом триггера 4 и установочным входом счетчика 19. Выход ключа 20 соединен с выходом всей схемы.

Генератор порядковых статистик работает следующим образом.

В исходном положении блоки 10 и 12 памяти содержат по n независимых реализаций случайной величины, распределенной по требуемому закону, генерируемому датчиком 22 случайных чисел. Счетчики 7 и 13 установлены в нулевые состояния, счетчики 15 и 19 - в единичные. Триггер 4 установлен в единичное состояние, он открывает прямым выходом элемент И 2, а инверсным выходом закрывает элемент И 3. На входе генератора статистик установлено целое число k (k=1, ..., n), задающее ранг порядковой статистики. Импульс от генератора 1 тактовых импульсов поступает через элемент И 2 на вход элемента 3 задержки и на вход элемента ИЛИ 6. С выхода элемента ИЛИ 6 импульс поступает на вход счетчика 7, увеличивая его содержимое на единицу. С выхода элемента 5 задержки импульс поступает на входы управления считыванием блоков 10 и 12 памяти. Числа из блоков 10 и 12 памяти, адреса которых установлены в счетчиках 7 и 19, поступают на первый и второй входы блока 11 сравнения. Если число на первом входе блока 11 сравнения меньше числа на его втором входе, то на выходе "меньше" схемы появляется сигнал, который, поступая на счетные входы счетчиков 13 и 15 (на последний через элемент ИЛИ 14), увеличивает их содержимое на единицы. Если числа на входах блока 11 сравнения равны, то на его выходе "равно" появляется сигнал, который через элемент ИЛИ 14 поступает на счетный вход счетчика 15, увеличивая его содержимое на единицу. При приходе следующих тактовых импульсов генератор порядковых статистик работает аналогично до тех пор, пока в счетчике 7 не произойдет переполнение. В этом случае счетчик 7 устанавливается в начальное состояние, сигнал с его выхода переполнения поступает на вход элемента 9 задержки и на первый вход элемента И 8. Если сравнения в блоках 16 и 17 сравнения не произойдет (для успешного сравнения сигнал на первом входе блока 16 сравнения должен быть меньше сигнала на его втором входе, а для блока 17 сравнения - наоборот), то сигналы на их выходах "меньше" и "больше" соответственно не появляются и элемент И 8 закрыт.

Сигнал с выхода элемента 9 задержки поступает на установочные входы счетчиков 13 и 15, устанавливая их в начальные состояния и через элемент ИЛИ 18 поступает на счетный вход счетчика 19, увеличивая его содержимое на единицу. На второй вход блока 11 сравнения поступает число из блока 12 памяти, адрес которого установлен в счетчике 19, и работа генератора продолжается описанным выше образом до тех пор, пока не произойдет сравнение в блоках 16 и 17 сравнения.

Если сравнение произойдет, элемент И 8 открывается, сигнал с его выхода поступает на вход элемента 23 задержки и открывает ключ 20, в результате чего число из блока 12 памяти поступает на выход генератора порядковых статистик. Сигнал с выхода элемента 23 задержки устанавливает счетчик 19 в нулевое состояние и изменяет состояние триггера 4 на противоположное. Элемент И2 закрывается, элемент И3 открывается.

Импульсы с выхода генератора 1 тактовых импульсов поступают на вход "опрос" датчика 22 случайных чисел, вызывая генерирование случайных чисел, и на входы элементов ИЛИ 6 и 18. Сигналы с выходов этих элементов ИЛИ, поступая на счетные входы счетчиков 7 и 19, увеличивают их содержимое на единицу, обеспечивая тем самым запись чисел с выхода датчика 22 в блоки 10 и 12 памяти по адресам, установленным в счетчиках 7 и 19. Работа генератора порядковых статистик продолжается описанным образом до тех пор, пока в счетчиках 7 и 19 не произойдет переполнение. В этом случае счетчики 7 и 19 устанавливаются в начальные состояния (нулевое и единичное соответственно), сигнал с выхода переполнения счетчика 19, поступая на установочный вход триггера 4, устанавливает его в начальное состояние, элемент И2 открывается, элемент И3 закрывается. Генератор порядковых статистик переводится в начальное состояние. Цикл работа генератора заканчивается.

Изобретение позволяет генерировать порядковые статистики с заданным рангом. Устройство относится к вычислительной технике и может быть использовано в качестве приставки или внутреннего блока ЭВМ. В отличие от аналогов и прототипа с целью упрощения в генераторе используются два блока 10 и 12 памяти. Определение значения порядковой статистики осуществляется последовательным сравнением каждого числа, записанного в блок 12 памяти, со всеми числами, записанными в блок 10 памяти. Если число из блока 10 памяти меньше или равно K числам из блока 12 памяти, то это число соответствует порядковой статистике с рангом K. Счетчики, ключи, элементы ИЛИ, элементы задержки, блоки сравнения, элементы И, датчик случайных чисел, триггер используются для организации сравнения и записи новых случайных чисел в блоки 10 и 12 памяти. 1 ил.

ГЕНЕРАТОР ПОРЯДКОВЫХ СТАТИСТИК, содержащий четыре счетчика, первый блок памяти, датчик случайных чисел, триггер, три элемента ИЛИ, первый блок сравнения, три элемента И, блок ключей, два элемента задержки и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам триггера, выход датчика случайных чисел соединен с информационным входом блока памяти, выход которого подключен к информационному входу блока ключей, информационный выход первого счетчика соединен с адресным входом первого блока памяти, выход первого элемента задержки подключен к установочным входам второго и третьего счетчиков, выход "Равно" первого блока сравнения соединен с первым входом первого элемента ИЛИ, выход которого подключен к счетному входу третьего счетчика, отличающийся тем, что, с целью упрощения, в него введены два блока сравнения, два элемента задержки и второй блок памяти, информационный вход которого соединен с выходом датчика случайных чисел, а выход подключен к первому входу первого блока сравнения, второй вход которого соединен с выходом первого блока памяти, выход "Меньше" первого блока сравнения подключен к второму входу первого элемента ИЛИ и к счетному входу второго счетчика, выход которого соединен с первым входом второго блока сравнения, выход "Меньше" которого подключен к первому входу третьего элемента И, выход которого соединен с управляющим входом блока ключей и через второй элемент задержки со счетным входом триггера и с установочным входом первого счетчика, выход переполнения которого подключен к установочному входу триггера, выход третьего счетчика соединен с первым входом третьего блока сравнения, выход "Больше" которого подключен к второму входу третьего элемента И, выход блока ключей является выходом генератора, вход которого соединен с вторыми вхадами второго и третьего блоков сравнения, выход первого элемента И подключен к входу запроса датчика случайных чисел и первым входам второго и третьего элементов ИЛИ и через третий элемент задержки к входам управления записью первого и второго блоков памяти, выход второго элемента И соединен с вторым входом второго элемента ИЛИ и через четвертый элемент задержки с входами управления считыванием первого и второго блоков памяти, выход второго элемента ИЛИ подключен к счетному входу четвертого счетчика, информационный выход которого соединен с адресным входом второго блока памяти, а выход переполнения подключен к третьему входу третьего элемента И и через первый элемент задержки к второму входу третьего элемента ИЛИ, выход которого соединен со счетным входом первого счетчика.