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

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

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

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

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

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

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

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

Однако устройство-прототип имеет недостатки, в частности, известный генератор не обеспечивает формирование случайной конечной последовательности заданных значений набора данных с заданным законом распределения. Кроме того, известный генератор не может быть применен при проектировании и отладке баз данных в автоматизированных системах, так как генерирует только числа и нет возможности задать количество генераций по каждому числу. Объясняется это тем, что блоки памяти используются для хранения максимальных значений интегральной функции распределения в точках x_j и ее значений слева и справа от этих точек, а схемное решение данного устройства не позволяет вводить в память произвольные (не числовые) значения набора данных и генерировать их с заданным законом распределения.

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

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

Благодаря новой совокупности существенных признаков за счет введения мультиплексора, блока сравнения и блока элементов "И" на выходе генератора формируется конечная последовательность заданных значений набора данных с заданным законом распределения. Этим достигается возможность расширения области применения заявленного устройства, в частности, при проектировании и отладке баз данных.

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

Заявленное устройство поясняется чертежами, на которых показаны:
фиг. 1 - структурная схема генератора случайной последовательности заданных значений набора данных с заданным законом распределения;
фиг. 2 - графическое представление функции распределения;
фиг. 3 - схема мультиплексора;
фиг. 4 - схема блока памяти;
фиг. 5 - схема блока сравнения;
фиг. 6 - схема блока элементов "И".

Генератор случайной последовательности (ГСП) заданных значений набора данных, показанный на фиг. 1, состоит из источника случайных чисел с заданным законом распределения 1, мультиплексора 2, первого 3 и второго 4 блоков памяти, блока сравнения 5 и блока элементов "И" 6.

Вход источника случайных чисел 1 с заданным законом распределения является управляющим входом ГСП и соединен с входом выбора мультиплексора 2 и вторым управляющим входом блока элементов "И" 6. Первый адресный вход мультиплексора 2 является адресным входом ГСП (AI₁). Второй адресный вход мультиплексора 2 подключен к выходу источника случайных чисел 1. Вход разрешения мультиплексора 2 является входом разрешения ГСП Выход мультиплексора 2 подключен к адресным входам первого 3 и второго 4 блоков памяти. Информационный вход первого 3 блока памяти является информационным входом ГСП и подключен к информационному входу второго 4 блока памяти. Первый 3 и второй 4 блоки памяти снабжены входами выбора кристаллов ( на фиг. 1 обозначены CS₁ и CS₂) и сигналов чтения/записи (на фиг. 1 обозначены Выход первого 3 блока памяти подключен к блоку сравнения 5, выход которого подключен к первому управляющему входу блока элементов "И" 6. Выход второго 4 блока памяти подключен к информационному входу блока элементов "И" 6, выход которого является выходом ГСП.

Все информационные входы и выходы блоков ГСП являются шестнадцатиразрядными шинами, что обусловлено схемой построения первого 3 и второго 4 блоков памяти (показанной на фиг.4 ) и количеством элементов памяти 3.1₁- 3.1₁₆, входящих в состав этих блоков. Такая схема построения позволяет хранить во втором 4 блоке памяти значения данных размерностью 2 байта и в первом 3 блоке памяти количество их генераций, равное 2¹⁶ для каждого из генерируемых значений.

Все адресные входы и выходы блоков ГСП являются десятиразрядными шинами, что обусловлено разрядностью элементов памяти 3.1₁-3.1₁₆, входящих в состав первого 3 и второго 4 блоков памяти. Такая разрядность адреса позволяет записывать в память набор данных, состоящий из 1024 элементов.

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

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

Мультиплексор 2 предназначен для переключения между первым AI₁ и вторым AI₂ адресными десятиразрядными входами, причем с первого по четвертый разряд адресного входа AI₁ подключены, соответственно, ко входам 1.0, 2.0, 3.0 и 4.0 элемента 2.1₁, а соответствующие разряды адресного входа Al₂ подключены, соответственно, ко входам 1.1, 2.1, 3.1 и 4.1 того же элемента. С пятого по восьмой разряды AI₁ подключены, соответственно, ко входам 1.0, 2.0, 3.0 и 4.0 элемента 2.1₂, a соответствующие разряды входа AI₂ подключены, соответственно, ко входам 1.1, 2.1, 3.1 и 4.1 того же элемента. Девятый и десятый разряды AI₁ подключены, соответственно, ко входам 1.0 и 2.0 элемента 2.1₃, а соответствующие разряды адресного входа AI₂ подключены, соответственно, ко входам 1.1 и 2.1. Входы 3.0, 3.1, 4.0 и 4.1 элемента 2.1₃ не задействованы.

Первый 3 и второй 4 блоки памяти идентичны и вариант их построения приведен на фиг. 4. Элементы памяти 3.1₁ - 3.1₁₆ идентичны, известны и описаны, например, в книге "Интегральные микросхемы ТТЛ, ТТЛШ" (Справочник. Г.Р. Аванесян, В.П. Левшин. - М.: Машиностроение, 1993, с. 209). В частности, они могут быть реализованы на микросхемах памяти 155 РУ7. Первый блок памяти 3 предназначен для хранения количества генераций для каждого значения набора данных, а второй блок памяти 4 предназначен для хранения генерируемых значений набора данных.

Каждый разряд шестнадцатиразрядного информационного входа первого 3 блока памяти (второй 4 блок памяти идентичен) подключен к информационному входу DI одного из элементов памяти. Адресные входы 0 всех элементов памяти включены в параллель и являются первым разрядом десятиразрядного адресного входа блока памяти. Адресные входы 1 всех элементов памяти включены в параллель и являются вторым разрядом десятиразрядного адресного входа блока памяти. Адресные входы 2, 3, 4, 5, 6, 7, 8, 9 всех элементов памяти включены аналогично входам 0 и 1. Входы выбора кристалла CS всех элементов памяти включены в параллель и являются входом выбора кристалла блока памяти. Входы чтения/записи всех элементов памяти включены в параллель и являются входом чтения/записи блока памяти. Информационный выход элемента памяти 3.1₁ является первым разрядом шестнадцатиразрядного выхода блока памяти. Информационный выход элемента памяти 3.1₂ является вторым разрядом шестнадцатиразрядного выхода блока памяти. Аналогично выходам элементов памяти 3.1₁ и 3.1₂ выходы элементов памяти 3.1₃ - 3.1₁₆ являются соответствующими разрядами шестнадцатиразрядного выхода блока памяти.

Блок сравнения 5 предназначен для сравнения количества генераций каждого значения набора данных с нулем, вариант его схемы приведен на фиг. 5. Элементы 5.1₁-5.1₄ и 5.2 идентичны и представляют собой четырехвходовые элементы "ИЛИ".

С первого по четвертый разряды шестнадцатиразрядного входа блока сравнения 5 подключены ко входам элемента 5.1₁, с пятого по восьмой разряды подключены ко входам элемента 5.1₂, с девятого по двенадцатый разряды подключены ко входам элемента 5.1₃, с тринадцатого по шестнадцатый разряды подключены ко входам элемента 5.1₄. Выходы элементов 5.1₁, 5.1₂, 5.1₃, 5.1₄ подключены ко входам элемента 5.2, а его выход является выходом блока сравнения 5.

Блок элементов "И" 6 предназначен для подачи генерируемого значения набора данных на выход при наличии двух управляющих сигналов, поступающих на его соответствующие входы. Схема блока элементов "И" 6 приведена на фиг. 6. Элементы 6.1₁ -6.1₁₆ идентичны и представляют собой трехвходовые элементы "И".

Первые управляющие входы всех элементов "И" включены в параллель и являются первым управляющим входом блока элементов "И". Вторые управляющие входы всех элементов "И" включены в параллель и являются вторым управляющим входом блока элементов ''И". Каждый разряд шестнадцатиразрядного информационного входа блока элементов "И" подключен к информационному входу одного из элементов "И". Выходы всех элементов "И" являются выходом блока элементов "И".

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

Устройство работает в двух режимах: первый - режим подготовки устройства к генерации; второй - режим генерации. Режим подготовки к генерации осуществляется следующим образом. На первый адресный вход AI₁ мультиплексора 2 выставляется адрес, по которому должно быть записано первое генерируемое значение a₁, а на вход разрешения и управляющий вход устройства подают низкий уровень напряжения (логический "0"), что приведет к формированию на выходе мультиплексора адреса, поступающего на вход AI₁. Этот же адрес в свою очередь поступает на адресные входы первого 3 и второго 4 блоков памяти. На шестнадцатиразрядный информационный вход DI устройства подают генерируемое значение a₁ размерностью не более 2-х байт, которое записывается во второй блок памяти 4, при поступлении на его вход выбора кристалла CS₂ и вход чтения/записи сигналов низкого уровня напряжения. После этого на вход выбора кристалла CS₂ второго блока памяти 4 подают сигнал высокого уровня напряжения (логическая "1"), а на информационном входе устройства DI выставляют количество m₁ генерируемых значений вида a₁, которое записывается по этому же адресу, но в первый блок памяти 3, при подаче на его вход выбора кристалла CS₁ и вход чтения/записи сигналов низкого уровня напряжения. Затем на адресном входе устройства AI₁ устанавливают следующий адрес для генерируемого значения a₂ и количества его генераций m₂, и действия по их записи повторяются по аналогии с вышеописанными. Этот процесс продолжается до тех пор, пока не будет записано все множество генерируемых значений набора данных {a₁, a₂,...,a_n} во второй блок памяти 4 и все множество {m₁, m₂,...,m_n} в первый блок памяти 3. При этом n ограничено разрядностью адреса и не может превышать 1024. В результате общее число генерируемых значений набора данных {a₁, a₂,...,a_n} становится равным
Функцию распределения, представленную на фиг. 2, устанавливают в источнике случайных чисел 1, где f_i - ордината функции распределения, соответствующая генерируемому значению a_i.

После вышеописанных действий, выполняемых в режиме подготовки к генерации, устройство переключается в режим генерирования путем выставления на управляющий вход устройства сигнала высокого уровня напряжения, который поступает на вход выбора мультиплексора 2 и переключает его на режим передачи на свой выход адреса, поступающего с выхода источника случайных чисел 1, на второй адресный вход AI₂ мультиплексора. Источник случайных чисел 1 при наличии на управляющем входе устройства сигнала высокого уровня напряжения генерирует десятиразрядные адреса согласно установленной функции распределения, которые через мультиплексор 2 поступают на адресные входы первого 3 и второго 4 блоков памяти. На входы выбора кристаллов этих блоков подают низкий уровень напряжения, а на входы чтения/записи - высокий уровень напряжения, что соответствует режиму чтения данных. По каждому сгенерированному адресу с первого блока памяти 3 считывается число m_i, означающее количество генерируемых значений вида a_i, и подается на вход блока сравнения 5, где происходит проверка условия m_i>0, а со второго блока памяти 4 считывается само генерируемое значение a_i и подается на информационный вход блока 6 элементов "И". Если условие m_i>0 выполняется, то на выходе блока сравнения 5 появляется сигнал высокого уровня напряжения, который подается на первый управляющий вход блока 6 элементов "И". При высоком уровне напряжения на втором управляющем входе блока 6 на выход устройства поступает генерируемое значение a_i, после чего на информационный вход устройства подают значение (m_i-1) и записывают по адресу, считываемому с выхода мультиплексора 2, в первый блок памяти 3. Тем самым осуществляется уменьшение на единицу количества генерируемых значений вида a_i. Затем источник случайных чисел 1 генерирует новый адрес и вышеописанные действия устройства в режиме генерирования повторяются.

Устройство прекращает работу, когда все элементы множества {m₁, m₂,..., m_n} становятся равными нулю, что определяется невыполнением условия m_i>0 для всех i.

Источники информации
1. Авторское свидетельство СССР N 771654, кл. G 06 F 1/02, G 07 C 15/00, 1978 (прототип).

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

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

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

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

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

Изобретение относится к области вычислительной техники и может быть использовано в системах для обработки информации. Техническим результатом является формирование случайной конечной последовательности заданных значений набора данных с заданным законом распределения. Генератор состоит из источника случайных чисел с заданным законом распределения, мультиплексора, блоков памяти, блока сравнения и блока элементов И. 6 ил.

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