ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Российский патент 2005 года по МПК G06F7/58 H03K3/84 

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

Известно устройство для получения случайных чисел с заданным законом распределения (см. Авт. св. СССР №478298, кл. G 06 F 1/02, 1973), содержащее генератор равномерно распределенных случайных чисел, многоступенчатый дешифратор, наборное поле, блок элементов ИЛИ и выходное устройство, в состав которого входит блок элементов И-НЕ, счетчик и дешифратор.

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

Известен генератор последовательностей случайных чисел (см. Авт. св. СССР №447706, кл. G 06 F 1/02, 1974), содержащий датчик равномерно распределенных чисел, коммутатор, первый и второй генераторы тактовых импульсов, счетчик, регистры, клапаны, элемент задержки, преобразователь, формирователь импульса сбора и ключ.

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

Известен генератор случайных чисел (см. Авт. св. СССР №771654, кл. G 06 F 1/02 G 07 15/00, 1978), содержащий источник равномерно распределенных случайных сигналов, два блока памяти, сумматор, переключатель и умножитель.

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

Из известных наиболее близким аналогом (прототипом) по своей технической сущности заявленному устройству является генератор случайных чисел заданных значений набора данных (см. Авт. св. РФ №2138074, кл. G 06 F 1/02, 1999), состоящий из источника случайных чисел, первого и второго оперативных запоминающих устройств (выполненных в виде набора из 16-и оперативных запоминающих устройств каждое), N-разрядного селектора-мультиплексора (выполненного в виде набора из 3-х селектров-мультиплексоров), многовходового элемента ИЛИ (выполненного в виде набора из 5-и элементов ИЛИ) и блока элементов И. М-разрядный выход блока элементов И, где М≥ 2 - разрядность генерируемых чисел, является М-разрядным выходом генератора. Разряды N-разрядного выхода источника случайных чисел, где N≥ 2 - количество разрядов, достаточное для адресации элементов заданного набора данных, подключены к соответствующим входам второй группы информационных входов N-разрядного селектора-мультиплексора, N выходов которого подключены к соответствующим адресным входам первого и второго оперативного запоминающего устройства. N входов первой группы информационных входов N-разрядного селектора-мультиплексора являются соответствующими разрядами N-разрядного адресного входа генератора. Каждый из М информационных входов первого оперативного запоминающего устройства соединен с соответствующим информационным входом второго оперативного запоминающего устройства и является соответствующим разрядом М-разрядного информационного входа устройства. М выходов первого оперативного запоминающего устройства подключены к соответствующим входам многовходового элемента ИЛИ, а М выходов второго оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа блока элементов И. Каждое оперативное запоминающее устройство снабжено инверсными входами выбора кристалла и чтения/записи, которые являются соответствующими входами "Выбор кристалла 1", "Выбор кристалла 2", "Чтение/запись 1", "Чтение/запись 2" генератора. Выход многовходового элемента ИЛИ подключен к второму управляющему входу блока элементов И. Управляющий вход источника случайных чисел соединен с входом выбора N-разрядного селектора-мультиплексора, с управляющим входом блока элементов И и одновременно является управляющим входом устройства. Инверсный разрешающий вход N-разрядного селектора-мультиплексора является первым разрешающим входом генератора.

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

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

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

2. Невозможностью генерирования случайной последовательности с законом распределения, представленным в широко используемом на практике интервальном виде (полигоном частот) без преднамеренного внесения детерминированности, обусловленной субъективным характером задания частости значений.

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

Поставленная цель в заявленном генераторе случайной последовательности достигается тем, что в известном генераторе случайной последовательности заданных значений набора данных, содержащем источник случайных чисел, N-разрядный селектор-мультиплексор, оперативное запоминающее устройство, многовходовый элемент ИЛИ, блок элементов И, M-разрядный выход которого, где М≥ 2 - разрядность генерируемых чисел, является М-разрядным выходом "Результат" генератора, разряды N-разрядного выхода "Случайные значения адреса" источника случайных чисел, где N≥ 2 - количество разрядов, достаточное для адресации элементов заданного набора данных, подключены к соответствующим входам второй группы информационных входов N-разрядного селектора-мультиплексора, N выходов которого подключены к соответствующим адресным входам оперативного запоминающего устройства, М информационных входов которого являются соответствующими разрядами М-разрядного информационного входа устройства, а М выходов оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа "Случайное число" блока элементов И, второй разрешающий вход которого подключен к выходу многовходового элемента ИЛИ, управляющий вход источника случайных чисел, вход выбора N-разрядного селектора-мультиплексора, управляющий вход блока элементов И объединены и являются управляющим входом генератора, N входов первой группы информационных входов N-разрядного селектора-мультиплексора являются N-разрядным адресным входом генератора, инверсный разрешающий вход N-разрядного селектора-мультиплексора является первым разрешающим входом генератора, а инверсные входы выбора кристалла и чтения/записи оперативного запоминающего устройства, являются соответственно входами "Выбор кристалла" и "Чтение/запись" генератора, дополнительно введены блок контроля интервалов, блок контроля количества генераций. Многовходовый элемент ИЛИ выполнен с J входами, где J≥ 2 - разрядность значений количества генераций. К M-разрядных входов значений интервалов блока контроля интервалов, где К≥ 2 - количество интервалов на которые разбит заданный набор данных, являются К N-разрядными входами значений интервалов устройства. К J-разрядных входов "Количество генераций" блока контроля количества генераций являются К J-разрядными входами "Количество генераций" генератора. Вход "Установка" блока контроля количества генераций является входом "Установка" генератора, причем М выходов оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа "Случайное число" блока контроля интервалов. L-разрядный выход "Номер интервала", где L= - количество разрядов, достаточное для кодирования номеров интервалов, блока контроля интервалов подключен к L-разрядному входу "Номер интервала" блока контроля количества генераций, разряды J-разрядного выхода "Текущее значение количества генераций" которого подключены к соответствующим входам J-входового элемента ИЛИ. Выход J-входового элемента ИЛИ подключен к второму разрешающему входу блока контроля количества генераций.

Блок контроля интервалов состоит из К компараторов, К двухвходовых элементов ИЛИ-НЕ, шифратора приоритетов, L инверторов. Выход l-го, где l=1,2,... ,L, инвертора является l-м разрядом L-разрядного выхода "Номер интервала" блока контроля интервалов, а вход l-го инвертора подключен к l-у инверсному выходу шифратора приоритетов, k-й, где k=1,2,... K, инверсный вход которого соединен с инверсным выходом k-го двухвходового элемента ИЛИ-НЕ. Первый и второй входы k-го двухвходового элемента ИЛИ-НЕ подключены соответственно к выходам "Равенство" и "Неравенство" k-го компаратора, m-е, где m=1,2,... ,М, входы первых групп информационных входов компараторов соединены между собой и являются m-ым разрядом М-разрядного входа "Случайное число" блока контроля интервалов, а m-й вход второй группы информационных входов k-го компаратора является m-м разрядом k-го M-разрядного входа значения интервалов блока.

Блок контроля количества генераций состоит из дешифратора низкого уровня, инвертора, К двухвходовых элементов ИЛИ-НЕ, К реверсивных счетчиков, J селекторов-мультиплексоров, каждый из которых снабжен L входами выбора данных и К информационными входами. Каждый из L входов дешифратора низкого уровня соединен с соответствующими входами выбора данных J селекторов-мультиплексоров и является соответствующим разрядом входа "Номер интервала" блока контроля количества генераций. Первый вход k-го двухвходового элемента ИЛИ-НЕ подключен к k-у инверсному выходу дешифратора низкого уровня. Вторые входы К двухвходовых элементов ИЛИ-НЕ соединены между собой и подключены к выходу инвертора. Вход инвертора является вторым разрешающим входом блока контроля количества генераций. Инверсный выход k-го двухвходового элемента ИЛИ-НЕ подключен к счетному входу k-го реверсивного счетчика. J информационных входов k-го реверсивного счетчика являются соответствующими разрядами k-го J-разрядного входа "Количество генераций" блока контроля количества генераций. Инверсные входы стробирования предварительной записи каждого реверсивного счетчика соединены между собой и являются входом "Установка" блока контроля количества генераций. При этом, j-й выход где j=1,2,... ,J, k-го реверсивного счетчика подключен к k-у информационному входу j-го селектора-мультиплексора. Выходы J селекторов-мультиплексоров являются соответствующими разрядами J-разрядного выхода "Текущее значение количества генераций" блока.

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

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

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

Заявленное устройство поясняется чертежами, на которых

на фиг.1 - генератор случайной последовательности;

на фиг.2 - блок контроля интервалов;

на фиг.3 - блок контроля количества генераций;

на фиг.4 - блок элементов И;

на фиг.5 - таблица режимов работы генератора;

на фиг.6 - графическое представление работы генератора;

на фиг.7 - иллюстрация отличий циклов генерирования устройства-прототипа и предлагаемого устройства.

Генератор случайной последовательности (см. фиг.1) состоит из источника случайных чисел 1, N-разрядного селектора-мультиплексора 2, оперативного запоминающего устройства 3, блока контроля интервалов 4, блока контроля количества генераций 5, J-входового элемента ИЛИ 6, блока элементов И 7.

Управляющий вход 10 источника случайных чисел 1 является управляющим входом генератора и соединен с входом выбора SE N-разрядного селектора-мультиплексора 2 и управляющим входом блока элементов И 7. Первая группа из N информационных входов A₁-А_N N-разрядного селектора-мультиплексора 2 является N-разрядным адресным входом генератора. Входы второй группы из N информационных входов B₁-B_N N-разрядного селектора-мультиплексора 2 подключены к соответствующим разрядам N-разрядного выхода "Случайные значения адреса" 12 источника случайных чисел 1. Инверсный разрешающий вход N-разрядного селектора-мультиплексора 2 является первым разрешающим входом 8 генератора. N выходов Q₁-Q_N N-разрядного селектора-мультиплексора 2 подключены к соответствующим адресным входам A₁-А_N оперативного запоминающего устройства 3, М информационных входов D₁-D_M которого являются соответствующими разрядами М-разрядного информационного входа 11 устройства. Оперативное запоминающее устройство 3 снабжено инверсным входом выбора кристалла и инверсным входом чтения/записи , которые являются соответственно входом "Выбор кристалла" 14 и входом "Чтение/запись" 15 генератора. М выходов С₁-С_M оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа "Случайное число" 16 блока контроля интервалов 4 и блока элементов И 7. К М-разрядных входов значений интервалов 17₁-17_K блока контроля интервалов 4, являются К М-разрядными входами значений интервалов генератора, L-разрядный выход "Номер интервала" 18 блока контроля интервалов 4 подключен к L-разрядному входу "Номер интервала" блока контроля количества генераций 5. К J-разрядных входов "Количество генераций" 19₁-19_K блока контроля количества генераций 5 являются К J-разрядными входами "Количество генераций" генератора. Вход "Установка" 20 блока контроля количества генераций 5 является входом "Установка" генератора. Разряды J-разрядного выхода "Текущее значение количества генераций" 21 блока контроля количества генераций 5 подключены к соответствующим входам J-входового элемента ИЛИ 6. Выход 22 J-входового элемента ИЛИ 6 подключен к второму разрешающему входу блока контроля количества генераций 5 и второму разрешающему входу блока элементов И 7, M-разрядный выход "Результат" которого является M-разрядным выходом "Результат" 23 генератора.

Источник случайных чисел 1, предназначенный для генерирования N-разрядных случайных адресов, известен и показан, например, в книге М.П.Бобнева "Генерирование случайных сигналов" (М.: Энергия, 1971, с.170, рис.6-13).

J-входовый элемент ИЛИ 6 предназначен для сравнения с нулем текущего значения количества генераций. Схема реализации такого элемента ИЛИ известна. См., например, в книге: Б.В.Тарабрин, С.В.Якубовский, Н.А.Барканов и др. "Справочник по интегральным микросхемам". - 2-е изд., перераб. и доп. - М.: Энергия, 1981, с.109.

N-разрядный селектор-мультиплексор 2 предназначен для коммутации на свой N-разрядный выход сигналов одной из двух групп из N информационных входов. Схема реализации N-разрядного селектора-мультиплексора известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 1. - М.: Бином, 1993, с.211).

Оперативное запоминающее устройство 3 предназначено для хранения значений заданного набора данных. Схема реализации оперативного запоминающего устройства известна. См., например, в книге: В.Л.Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, с.164-166.

Блок элементов И предназначен для подачи выбранного случайным образом значения набора данных на выход при наличии двух управляющих сигналов, поступающих на его соответствующие входы. Блок элементов И может быть реализован в различных вариантах. В частности вариант построения блока элементов И представлен на фиг.4. Блок элементов И состоит из М трехвходовых элементов И. Вторые входы всех трехвходовых элементов И включены в параллель и являются управляющим входом 10 блока элементов И. Третьи управляющие входы всех трехвходовых элементов И включены в параллель и являются вторым разрешающим входом 22 блока элементов И. Каждый разряд М-разрядного входа "Случайное число" 16 блока элементов И подключен к первому входу соответствующего элемента И. Выходы всех элементов И 7.1₁-7.1_M являются соответствующим разрядом М-разрядного выхода "Результат" блока элементов И.

Трехвходовый элемент И предназначен для коммутации на свой выход сигналов на одном из своих входов при наличии разрешающих сигналов высокого логического уровня на двух остальных входах. Схема реализации трехвходовых элементов И известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 2. - М.: Бином, 1993, с.258-259).

Блок контроля интервалов предназначен для задания нижних границ интервалов, определения номера интервала, которому принадлежит генерируемое значение, и передачи его в двоичном коде на свой выход. Блок контроля интервалов может быть реализован в различных вариантах. В частности его схема, показанная на фиг.2, содержит К компараторов 4.1₁ - 4.1_K, К двухвходовых элементов ИЛИ-НЕ 4.2₁-4.2_K, шифратора приоритетов 4.3, L инверторов 4.4₁-4.4_L. Элементы соединены между собой следующим образом. Выход l-го, где l=1,2,... L, инвертора является l-ым разрядом L-разрядного выхода "Номер интервала" 18 блока контроля интервалов. Вход l-го инвертора подключен к l-у инверсному выходу шифратора приоритетов 4.3, k-й, где k=1,2,... К, инверсный вход которого соединен с инверсным выходом k-го двухвходового элемента ИЛИ-НЕ. Первый и второй входы k-го двухвходового элемента ИЛИ-НЕ подключены соответственно к выходам "Равенство" и "Неравенство" (которые на фиг.2 обозначены символами "А=В" и "А>В" соответственно) k-го компаратора, m-е, где m=1,2,... ,М, входы первых групп информационных входов A₁-А_M компараторов соединены между собой и являются m-м разрядом Поразрядного входа "Случайное число" 16 блока контроля интервалов. При этом m-й вход второй группы информационных входов B₁-В_м k-го компаратора является m-м разрядом k-го М-разрядного входа значений интервалов блока контроля интервалов.

Компараторы 4.1₁-4.1_K предназначены для сравнения двух М-разрядных чисел и формирования результата сравнения. Описание работы и схема компаратора приведены, например, в книге: В.Л.Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, с.183-184.

Элементы ИЛИ-НЕ 4.2₁-4.2_K - предназначены для формирования на своем выходе сигнала низкого уровня в случае появления сигналов на любом из выходов "А=В" или "А>В" соответствующих компараторов. Схема реализации элементов ИЛИ-НЕ известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 1. - М.: Бином, 1993, с.246-247).

Шифратор приоритетов 4.3 предназначен для преобразования сигнала низкого уровня на одном из его входов в двоичный код на его выходе, причем преобразование осуществляется с учетом приоритетов сигналов, соответствующих номерам входов. Схема реализации шифратора приоритетов известна. См., например, в книге: П.П.Мальцев, Н.С.Долидзе и др., справочник "Цифровые интегральные микросхемы", - М.: "Радио и связь", 1994, с.40-41.

Инверторы 4.4₁-4.4_к предназначены для инвертирования сигналов с инверсных выходов шифратора приоритетов. Схема реализации инвертора известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 2. - М.: Бином, 1993, с.471-472).

Блок контроля количества генераций предназначен для задания количества генераций для каждого из интервалов, формирования на своем выходе текущего значения количества генераций при подаче на его вход номера выбранного интервала в двоичном коде и уменьшения на единицу текущего значения количества генераций для соответствующего интервала. Блок контроля количества генераций может быть реализован в различных вариантах. В частности его схема, показанная на фиг.3, содержит дешифратор низкого уровня 5.1, инвертор 5.2, К двухвходовых элементов ИЛИ-НЕ 5.3₁-5.3_K, К реверсивных счетчиков 5.4₁-5.4_K, J селекторов мультиплексоров 5.5₁-5.5_J, каждый из которых снабжен L входами выбора данных S₁-S_L и К информационными входами I₁-I_K. Каждый из L входов дешифратора низкого уровня 5.1 соединен с соответствующими входами выбора данных каждого из J селекторов мультиплексоров 5.5₁-5.5_J и является соответствующим разрядом входа "Номер интервала" 18 блока контроля количества генераций. Первый вход k-го (k=1,2,... K) двухвходового элемента ИЛИ-НЕ подключен к k-у инверсному выходу дешифратора низкого уровня, а вторые входы К двухвходовых элементов ИЛИ соединены между собой и подключены к выходу инвертора 5.2, вход которого является вторым разрешающим входом 22 блока. Инверсный выход k-го двухвходового элемента ИЛИ-НЕ подключен к счетному входу "-1" k-го реверсивного счетчика. J информационных входов D₁-D_J k-го реверсивного счетчика являются соответствующими разрядами k-го J-разрядного входа "Число генераций" 19₁-19_K блока. Инверсные входы стробирования предварительной записи каждого реверсивного счетчика 5.4₁-5.4_K соединены между собой и являются входом "Установка" 20 блока контроля количества генераций. При этому j-й выход (j=1,2,... ,J) k-го реверсивного счетчика подключен к k-у информационному входу j-го селектора мультиплексора. Выходы J селекторов мультиплексоров 5.5₁ -5.5_J являются соответствующими разрядами J-разрядного выхода "Текущее значение числа генераций" 21 блока.

Дешифратор низкого уровня 5.1 предназначен для преобразования двоичного кода на его входе в сигнала низкого уровня на одном из его выходов, причем номер выхода соответствует числу в двоичном коде, поданному на вход дешифратора. Схема реализации дешифратора низкого уровня известна. См., например, в книге: П.П.Мальцев, Н.С.Долидзе и др., справочник "Цифровые интегральные микросхемы", - М.: "Радио и связь", 1994,с.42-43.

Элементы ИЛИ-НЕ 5.3₁-5.3_K предназначены для формирования на своем выходе сигнала высокого уровня в случае одновременного появления сигналов низкого уровня на входах. Схема реализации элементов ИЛИ-НЕ известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 1. - М.: Бином, 1993, с.246-247).

Инвертор 5.2 предназначен для инвертирования сигнала, поступающего на вход "Разрешение" 22 блока контроля количества генераций. Схема реализации инвертора известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 2. - М.: Бином, 1993, с.471-472).

Реверсивные счетчики 5.4₁-5.4_K, предназначены для хранения текущего значения числа генераций для каждого их К интервалов и уменьшения указанного значения на единицу при поступлении на их счетный вход сигнала высокого уровня. Схема реализации реверсивного счетчика известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 1. - М.: Бином, 1993. с.71).

Селекторы-мультиплексоры 5.5₁-5.5_J предназначены для коммутации сигнала на одном из информационных входов на выход, при этом номер входа определяется двоичным кодом, поданным на входы выбора данных селекторов-мультиплексоров. Схема реализации селектора-мультиплексора известна. См., например, в книге: "Логические ИС КР1533, КР1554" (Справочник И.И.Петровского и др. В двух частях. Часть 1. - М.: Бином, 1993, с.194).

Заявленное устройство работает следующим образом.

В исходном положении на первом разрешающем входе 8, входе "Выбор кристалла" 14, входе "Установка" 20 устройства установлены высокие логические уровни, а на управляющем входе 10 - низкий логический уровень.

Устройство работает в двух режимах первый - режим подготовки устройства к генерации; второй - режим генерации. При этом режим работы устройства определяется комбинацией сигналов на первом разрешающем входе 8 и управляющем входе 10 устройства (см. фиг.5).

В режиме подготовки генератора к работе выполняются следующие шаги.

Первый шаг - занесение множества А={а₀, a₁, a₂,... а_R} значений элементов заданного набора данных (см. фиг.6) в оперативное запоминающее устройство, при этом

0≤ а_r≤_{2^м-1 - элемент заданного набора данных, где r=0,1,... ,R;}

М≥ 2 - количество двоичных разрядов, достаточное для представления значений заданного набора данных;

1≤ R≤ 2^N-1 - количество элементов заданного набора данных;

N≥ 2 - количество двоичных разрядов, достаточное для адресации элементов заданного набора данных.

Второй шаг - установка множества В={b₁, b₂, b₃,... , b_K} значений нижних границ интервалов, на которые разбит заданный набор данных (см. фиг.6), при этом

0≤ b_k≤_{2^M-1 - значение нижней границы k-то интервала, где k=1,2,... ,K и 0≤ b1≤b2≤... ≤bК;}

1≤ К... 2^L-1 - количество интервалов;

L= - количество двоичных разрядов, достаточное для кодирования порядкового номера интервала.

Таким образом, заданный набор данных разбивается на следующие интервалы:

1-й интервал - [b₁; b₂];

2-й интервал - [b₂; b₂];

K-й интервал - [b_K; (2^м-1)].

Третий шаг -установка множества D={d₁, d₂, d₃,... , d_K} значений количества генераций для каждого интервала (см. фиг.6), при этом

1≤ d_K≤_{2^J-1 -значение количества генераций для k-го интервала, k=1,2,... ,K}

J≥ 2 - количество двоичных разрядов, достаточное для представления значений числа генераций.

Первый шаг подготовки устройства к работе включает следующие действия. По N-разрядному адресному входу 9 устройства на первую группу информационных входов A₁-А_N селектора мультиплексора 2 подается N-разрядный адрес, по которому должно быть записано значение первого элемента а₀. На первом разрешающем входе 8 устройства устанавливают низкий логический уровень, который поступает на вход разрешения Е селектора-мультиплексора 2, что при наличии низкого логического уровня на управляющем входе 10 устройства приводит к коммутации адреса, установленного на входах A₁-А_N селектора-мультиплексора, на N-разрядный выход "Адрес" 13, по которому он поступает на адресные входы A₁-A_N оперативного запоминающего устройства 3. По М-разрядному информационному входу 11 устройства на информационные входы D₁-D_M оперативного запоминающего устройства подают значение первого элемента а₀ заданного набора данных, которое записывается в оперативное запоминающее устройство при поступлении на его входы и сигналов низкого уровня по входам "Выбор кристалла" 14 и "Чтение/запись" 15 соответственно. Затем по N-разрядному адресному входу 9 устройства на первую группу информационных входов A₁–А_N селектора мультиплексора 2 подается N-разрядный адрес, по которому должно быть записано значение второго элемента a₁, а по М-разрядному информационному входу 11 устройства на информационные входы D₁-D_M оперативного запоминающего устройства подают значение элемента a₁ и, путем установки сигналов низкого уровня на входах "Выбор кристалла" 14 и "Чтение/запись" 15, записывают значение a₁ в оперативное запоминающее устройство. Аналогичным образом в оперативное запоминающее устройство заносятся все R значений элементов заданного набора данных. После чего на первом разрешающем входе 8 устройства устанавливают высокий логический уровень.

Второй шаг подготовки устройства к работе выполняется следующим образом. На М-разрядные входы значений интервалов 17₁-17_K устройства устанавливают значения нижних границ интервалов. При этом на вход 17₁ устанавливают значение b₁, которое поступает на вторую группу входов B₁-В_M компаратора 4.1₁, на вход 17₂ - значение b₂, которое поступает на вторую группу входов B₁-В_м компаратора 4.1₂, на вход 17_K - значение b_к, которое поступает на вторую группу входов B₁-В_м компаратора 4.1_K.

Третий шаг подготовки устройства к работе включает следующие действия. На J-разрядные входы "Число генераций" 19₁-19_K устройства устанавливают значения количества генераций. При этом на вход 19₁ устанавливают значение d₁, которое поступает на информационные входы D₁-D_J реверсивного счетчика 5.4₁, на вход 19₂ - значение d₂, которое поступает на информационные входы D₁-D_J реверсивного счетчика 5.4₂, на вход 19_K - значение d_K, которое поступает на информационные входы D₁-D_J реверсивного счетчика 5.4_K. Затем на входе "Установка" 20 устройства устанавливают низкий логический уровень, который поступает на вход стробирования предварительной записи всех реверсивных счетчиков, что обеспечивает начальную установку реверсивных счетчиков в соответствии с установленными на входах 19₁-19 к значениями.

После вышеописанных действий устройство готово к работе.

В режиме генерации работа устройства происходит следующим образом. На первый разрешающий вход 8 устройства подают низкий логический уровень, который поступает на вход разрешения селектора-мультиплексора 2, на управляющий вход 10 подают высокий логический уровень, который поступает на вход выбора SE селектора-мультиплексора 2, что обеспечивает коммутацию адреса, поступающего с выхода источника случайных чисел 1, на N-разрядный выход "Адрес" 12, по которому он поступает на адресные входы A₁-A_N оперативного запоминающего устройства 3.

Источник случайных чисел 1 при наличии на управляющем входе устройства сигнала высокого уровня напряжения генерирует N-разрядные адреса, которые через селектор-мультиплексор 2 поступают на адресные входы A₁-А_N оперативного запоминающего устройства 3. По входу "Выбор кристалла" 14 на вход оперативного запоминающего устройства подают низкий уровень сигнала, а по входу "Чтение/запись" 15 на вход оперативного запоминающего устройства подают высокий уровень сигнала, что соответствует операции чтения данных. Таким образом, в соответствии со случайными адресами, формируемыми источником случайных чисел, происходит чтение значений элементов А={а₀, а₁, а₂,... , a_R} заданного набора данных из оперативного запоминающего устройства, которые по M-разрядному выходу "Случайное число" поступают на входы блока контроля интервалов 4 и блока элементов И 7.

Считанное из оперативного запоминающего устройства значение а_r, по M-разрядному входу "Случайное число" 16 поступает одновременно на первые группы информационных входов A₁-А_м всех компараторов 4.1₁-4.1_M блока контроля интервалов 4, где происходит сравнение значения а с значениями нижних границ заданных интервалов В={b₁, b₂, b₃,... ,b_к}. В случае если поступившее значение а_r принадлежит k-у интервалу, т.е. выполняется условие b_k≥_{аr<bk+1, на соответствующих выходах "А>В" или "А=В" компараторов 4.11-4.1k формируются сигналы высокого логического уровня, при этом на выходах "А>В" и "А=В" компараторов 4.1k+1-4.1K будут присутствовать сигналы низкого логического уровня. Сигналы с выходов "А>В" и "А=В" каждого компаратора объединяются и инвертируются двухвходовыми элементами ИЛИ-НЕ 4.21-4.2K, а затем поступают на соответствующие инверсные входы шифратора приоритетов 4.3 (вход шифратора приоритетов не используется, так как нумерация интервалов начинается с единицы). Таким образом, при выполнении условия bk (аr bk+1, на входах шифратора приоритетов 4.3 будут установлены сигналы низкого логического уровня, а на входах - сигналы высокого логического уровня. В этом случае на L-разрядном выходе шифратора приоритетов 4.3 будет сформирован двоичный код в инверсном представлении, соответствующий значению максимального номера входа из числа входов с установленными низкими логическими уровнями, т.е. код, соответствующий числу k, - номеру интервала, которому принадлежит значение аr. Полученный код после инвертирования в элементах 4.41 - 4.4L поступает на L-разрядный выход "Номер интервала" 18 и далее на вход блока контроля количества генераций 5.}

В блоке контроля количества генераций 5 код, соответствующий номеру интервала, которому принадлежит значение а_r, поступает одновременно на входы Y₁-Y_L дешифратора низкого уровня 5.1 и входы выбора данных S₁-S_L, всех селекторов-мультиплексоров 5.5₁-5.5_J. При этом на k-м выходе дешифратора низкого уровня 5.1 формируется сигнал низкого логического уровня, а на выходы Y селекторов-мультиплексоров 5.5₁-5.5_J коммутируются сигналы с выходов Q₁-Q_J k-го реверсивного счетчика. Таким образом, значение количества генераций d_k, соответствующее номеру интервала, которому принадлежит значение а_r поступает на J-разрядный выход "Текущее значение количества генераций" 21 и далее на J-входовый элемент ИЛИ, на выходе которого в случае неравенства значения количества генераций нулю (d_k≠_{0) формируется сигнал высокого уровня, который по второму разрешающему входу 22 поступает одновременно в блок элементов И 7 и блок контроля количества генераций 5.}

Сигнал высокого логического уровня, поступивший по второму разрешающему входу 22 в блок контроля количества генераций 5, инвертируется и, совместно с сигналом низкого логического уровня, сформированным на k-м выходе дешифратора низкого уровня 5.1, обеспечивает формирование сигнала высокого логического уровня на выходе k-го элемента ИЛИ-НЕ. Это приводит к уменьшению значения, установленного в k-м реверсивном счетчике на единицу, что соответствует уменьшению на единицу значения d_k – количества генераций для k-го интервала, т.е. интервала, которому принадлежит значение а_r.

Поступление сигнала высокого уровня по второму разрешающему входу 22 в блок элементов И 7 при наличии сигнала высокого уровня на управляющем входе 10 обеспечивает поступление значения а_r с выхода оперативного запоминающего устройства на выход "Результат" 23 генератора.

Устройство прекращает работу, когда все элементы множества D={d₁, d₂, d₃,... , d_K}, установленные в реверсивных счетчиках 5.4₁-5.4_K, становятся равными нулю.

В устройстве-прототипе (см. фиг.7а, 7б) для каждого элемента а_r заданного набора данных А={а₀, a₁, а₂,... , а_R} жестко задается количество (частость) его появлений на выходе устройства, что при выполнении повторных циклов генерирования, выполняемых с теми же исходными данными, приводит к детерминированности частоты появления заданных значений набора данных в пределах каждого цикла.

В отличие от устройства-прототипа в предлагаемом устройстве (см. фиг.7в, 7 г) заданный набор данных А={a₀, a₁, a₂,... ,а_R} делится на К интервалов и для каждого интервала задается количество dk появлений значений, находящихся в его пределах. При этом. как для первого цикла генерирования, так и для всех последующих, каждое из значений а_r где r=0,1,... ,R, заданного набора данных появится на выходе устройства случайное число раз . При этом сумма случайных значений числа появлений элементов заданного набора данных, принадлежащих k-у интервалу, в первом и последующих циклах генерирования будет равна d_k (см. фиг 7в, 7г).

ИСТОЧНИКИ ИНФОРМАЦИИ.

1. Авторское свидетельство РФ №2138074, кл. G 06 F 1/02 (прототип).

2. Авторское свидетельство СССР №771654, кл. G 06 F 1/02, G 07 15/00, 1978.

3. Авторское свидетельство СССР №478298, кл. G 06 F 1/02, 1973.

4. Авторское свидетельство СССР №447706, кл. G 06 F 1/02, 1974.

5. М.П.Бобнев. Генерирование случайных сигналов. - М: Энергия, 1971, - 240 с.

6. Б.В.Тарабрин, С.В.Якубовский, Н.А.Барканов и др. "Справочник по интегральным микросхемам". - 2-е изд., перераб. и доп. - М.: Энергия, 1981, 816 с.

7. В.Л.Шило "Популярные цифровые микросхемы", М.: "Радио и связь", 1987, - 352 с.

8. П.П.Мальцев, Н.С.Долидзе и др., справочник "Цифровые интегральные микросхемы", - М.: "Радио и связь", 1994.

9. Справочник И.И.Петровского и др. "Логические ИС КР1533, КР1554". В двух частях. Часть 1. - М.: Бином, 1993, - 256 с.

10. Справочник И.И.Петровского и др. "Логические ИС КР1533, КР1554". В двух частях. Часть 2. - М.: Бином, 1993, - 244 с.

Изобретение относится к вычислительной технике. Технический результат заключается в расширении возможностей генератора. Устройство состоит из источника случайных чисел, N-разрядного селектора-мультиплексора, оперативного запоминающего устройства, блока контроля интервалов, блока контроля количества генераций, J-входового элемента ИЛИ, блока элементов И. Благодаря разбиению последовательности заданных значений набора данных на интервалы и задания частости появления значений в их пределах обеспечивается генерирование случайной последовательности с законом распределения, представленным в интервальном виде. 2 з.п. ф-лы, 7 ил.

1. Генератор случайной последовательности, содержащий источник случайных чисел, N-разрядный селектор-мультиплексор, оперативное запоминающее устройство, многовходовый элемент ИЛИ, блок элементов И, М-разрядный выход которого, где М≥2 - разрядность генерируемых чисел, является М-разрядным выходом “Результат” генератора, разряды N-разрядного выхода “Случайные значения адреса” источника случайных чисел, где N≥2 - количество разрядов, достаточное для адресации элементов заданного набора данных, подключены к соответствующим входам второй группы информационных входов N-разрядного селектора-мультиплексора, N выходов которого подключены к соответствующим адресным входам оперативного запоминающего устройства, М информационных входов которого являются соответствующими разрядами М-разрядного информационного входа генератора, а М выходов оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа “Случайное число” блока элементов И, второй разрешающий вход которого подключен к выходу многовходового элемента ИЛИ, управляющий вход источника случайных чисел, вход выбора N-разрядного селектора-мультиплексора, управляющий вход блока элементов И объединены и являются управляющим входом генератора, N входов первой группы информационных входов N-разрядного селектора-мультиплексора являются N-разрядным адресным входом генератора, инверсный разрешающий вход N-разрядного селектора-мультиплексора является первым разрешающим входом генератора, а инверсные входы выбора кристалла и чтения/записи оперативного запоминающего устройства являются соответственно входами “Выбор кристалла” и “Чтение/запись” генератора, отличающийся тем, что дополнительно введены блок контроля интервалов и блок контроля количества генераций, а элемент ИЛИ выполнен с J-входами, где J≥2 - разрядность значений количества генераций, К М-разрядных входов значений интервалов блока контроля интервалов, где К≥2 - количество интервалов, на которые разбит заданный набор данных, являются К М-разрядными входами значений интервалов генератора, К J-разрядных входов “Количество генераций” блока контроля количества генераций являются К J-разрядными входами “Количество генераций” генератора, вход “Установка” блока контроля количества генераций является входом “Установка” генератора, причем М выходов оперативного запоминающего устройства подключены к соответствующим разрядам М-разрядного входа “Случайное число” блока контроля интервалов, L-разрядный выход “Номер интервала”, где L=[log₂K]+1 – количество разрядов, достаточное для кодирования номеров интервалов, блока контроля интервалов подключен к L-разрядному входу “Номер интервала” блока контроля количества генераций, разряды J-разрядного выхода “Текущее значение количества генераций” которого подключены к соответствующим входам J-входового элемента ИЛИ, выход которого подключен к второму разрешающему входу блока контроля количества генераций.2. Устройство по п.1, отличающееся тем, что блок контроля интервалов состоит из К компараторов, К двухвходовых элементов ИЛИ-НЕ, шифратора приоритетов, L инверторов, выход l-го, где l=1, 2,..., L, инвертора является l-м разрядом L-разрядного выхода “Номер интервала” блока контроля интервалов, а вход l-го инвертора подключен к l-му инверсному выходу шифратора приоритетов, k-й, где k=1, 2,..., К, инверсный вход которого соединен с инверсным выходом k-го двухвходового элемента ИЛИ-НЕ, первый и второй входы k-го двухвходового элемента ИЛИ-НЕ подключены соответственно к выходам “Равенство” и “Неравенство” k-го компаратора, m-е, где m=1, 2,..., М, входы первых групп информационных входов компараторов соединены между собой и являются m-ым разрядом М-разрядного входа “Случайное число” блока контроля интервалов, а m-й вход второй группы информационных входов k-го компаратора является m-м разрядом k-го М-разрядного входа значения интервалов блока.3. Устройство по п.1, отличающееся тем, что блок контроля количества генераций состоит из дешифратора низкого уровня, инвертора, К двухвходовых элементов ИЛИ-НЕ, К реверсивных счетчиков, J селекторов-мультиплексоров, каждый из которых снабжен L входами выбора данных и К информационными входами, каждый из L входов дешифратора низкого уровня соединен с соответствующими входами выбора данных J селекторов-мультиплексоров и является соответствующим разрядом входа “Номер интервала” блока контроля количества генераций, первый вход k-го двухвходового элемента ИЛИ-НЕ подключен к k-му инверсному выходу дешифратора низкого уровня, а вторые входы К двухвходовых элементов ИЛИ-НЕ соединены между собой и подключены к выходу инвертора, вход которого является вторым разрешающим входом блока контроля количества генераций, инверсный выход k-го двухвходового элемента ИЛИ-НЕ подключен к счетному входу k-го реверсивного счетчика, J информационных входов k-го реверсивного счетчика являются соответствующими разрядами k-го L-разрядного входа “Количество генераций” блока контроля количества генераций, инверсные входы стробирования предварительной записи каждого реверсивного счетчика соединены между собой и являются входом “Установка” блока контроля количества генераций, j-й выход, где j=1, 2,..., J, k-го реверсивного счетчика подключен к k-му информационному входу j-го селектора-мультиплексора, выходы J селекторов-мультиплексоров являются соответствующими разрядами J-разрядного выхода “Текущее значение количества генераций” блока контроля количества генераций.