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

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

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

Известен генератор случайных чисел заданных значений набора данных (см. Авт. св. РФ №2138074, кл. G06F 1/02, 1999), состоящий из источника случайных чисел, первого и второго оперативных запоминающих устройств (выполненных в виде набора из 16-ти оперативных запоминающих устройств каждое), N-разрядного селектора-мультиплексора (выполненного в виде набора из 3-х селектров-мультиплексоров), блока сравнения и блока элементов И. Второй аналог обеспечивает формирование случайной конечной последовательности элементов заданного набора данных с заданным законом распределения.

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

Известен генератор случайной последовательности по Патенту РФ №2250489, «Генератор случайной последовательности», МПК G06F 7/58, НОЗК 3/84, опубликованный 20.04.2005, бюл. №11, включающий источник случайных чисел, N-разрядный селектор-мультиплексор, оперативное запоминающее устройство, блок контроля интервалов, блок контроля количества генераций, J-входовый элемент ИЛИ, блок элементов И. Третий аналог обеспечивает формирование конечной последовательности заданных значений набора данных по заданному в интервальном виде закону распределения со случайной частостью появления значений в пределах интервалов.

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

Из известных наиболее близким аналогом (прототипом) по своей технической сущности заявленному устройству является генератор случайной последовательности по Патенту РФ №2313125, «Генератор случайной последовательности», МПК G06F 7/58, H03K 3/84, G07C 15/00, опубликованный 20.12.2007, бюл. №35. Устройство-прототип содержит источник случайных чисел, оперативное запоминающее устройство, N-разрядный селектор-мультиплексор, K P-разрядных регистров, K блоков сравнения, шифратор приоритетов, N инверторов. Устройство-прототип обеспечивает формирование неограниченной последовательности заданных значений набора данных, частность появления которых определяется только заданным законом распределения.

Однако устройство-прототип имеет недостаток - узкую область применения, ограниченную возможностью моделирования дискретных случайных процессов, характеризующихся отсутствием вероятностной связи между состояниями случайного процесса (между генерируемыми значениями заданного набора данных). В то же время, при исследовании многих случайных процессов, протекающих в реальных системах, широкое применение находят марковские модели [1], предполагающие наличие зависимости каждого очередного состояния случайного процесса от предыдущего.

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

Указанная цель достигается тем, что в известный генератор случайной последовательности, содержащий K блоков сравнения, где K≥2 - максимально возможная мощность заданного множества генерируемых значений, первый селектор-мультиплексор, оперативное запоминающее устройство, шифратор приоритетов, N инверторов, где N=[log₂K] - число двоичных разрядов, достаточное для адресации элементов заданного множества генерируемых значений, K блоков хранения границ интервалов, выполненных в виде оперативных запоминающих устройств и источник случайных чисел, дополнительно включены второй селектор-мультиплексор, первый регистр и второй регистр. При этом P-разрядный, где Р>N, выход «Случайное число» источника случайных чисел соединен с P-разрядными входами «Случайное число» K блоков сравнения, P-разрядный выход k-го блока хранения границ интервалов, где k=1, 2, …, K, соединен с P-разрядным входом «Верхняя граница» k-го блока сравнения. Выход «Результат сравнения» А-го блока сравнения соединен с k-м инверсным входом шифратора приоритетов, n-й инверсный выход которого, где n=1, 2, …, N, соединен с входом n-го инвертора. Вход выбора первого селектора-мультиплексора соединен с управляющим входом источника случайных чисел и является управляющим входом генератора, первый N-разрядный информационный вход первого селектора-мультиплексора является первым N-разрядным адресным входом генератора, N-разрядный выход первого селектора-мультиплексора соединен с N-разрядным адресным входом оперативного запоминающего устройства, инверсные входы «Чтение/запись» и «Выбор кристалла» которого являются соответственно первым входом «Чтение/запись» и первым входом «Выбор кристалла» генератора. Причем M-разрядный выход оперативного запоминающего устройства, где М≥2 - количество разрядов, достаточное для представления максимального значения из числа значений, входящих в состав заданного множества генерируемых значений, является M-разрядным выходом «Результат» генератора, M-разрядный информационный вход оперативного запоминающего устройства является M-разрядным информационным входом генератора. При этом P-разрядный информационный вход k-го блока хранения границ интервалов является k-м P-разрядным информационным входом генератора, n-й разряд N-разрядного информационного входа второго регистра соединен с инверсным выходом n-го инвертора, а N-разрядный выход второго регистра соединен с вторым N-разрядным информационным входом первого селектора-мультиплексора и вторым N-разрядным информационным входом второго селектора-мультиплексора, первый N-разрядный вход которого является вторым N-разрядным адресным входом генератора, а его N-разрядный выход соединен с N-разрядным информационным входом первого регистра, TV-разрядный выход которого соединен с N-разрядными адресными входами каждого из К блоков хранения границ интервалов, соответствующие инверсные входы «Выбор кристалла» и «Чтение/запись» которых объединены между собой и являются соответственно вторым входом «Выбор кристалла» и вторым входом «Чтение/запись» генератора. Вход выбора второго селектора-мультиплексора соединен с управляющим входом источника случайных чисел, входы инициализации первого и второго регистров являются соответственно первым и вторым входом «Установка» генератора, а входы сброса первого и второго регистров объединены и являются входом «Обнуление» генератора.

Блок сравнения состоит из компаратора, P-входового элемента ИЛИ-НЕ и элемента ИЛИ, первый вход которого подключен к выходу «Неравенство» компаратора. Второй вход элемента ИЛИ подключен к инверсному выходу P-входового элемента ИЛИ-НЕ. Выход элемента ИЛИ является выходом «Результат сравнения» блока сравнения. Р входов первой группы информационных входов компаратора являются P-разрядным входом «Случайное число» блока сравнения, Р входов второй группы информационных входов компаратора соединены с соответствующими входами P-входового элемента ИЛИ-НЕ и являются вторым P-разрядным входом «Верхняя граница» блока сравнения.

Благодаря новой совокупности существенных признаков, за счет введения второго селектора-мультиплексора, обеспечивающего запись новых значений (для данного шага) верхних границ интервалов, на которые разбивается множество адресов заданного набора данных, определяемых на каждом последующем шаге вероятностями переходов случайного процесса из состояния в состояние [1], а также первого регистра и второго регистра, обеспечивающих, соответственно, регистрацию и хранение значений новых верхних границ интервалов и значений верхних границ интервалов предыдущего шага, в заявленном генераторе случайной последовательности достигается возможность расширения области его применения за счет обеспечения возможности генерации последовательности значений из заданного множества значений с учетом наличия вероятностной связи каждого очередного значения с предыдущим.

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

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

на фиг. 2 - структурная схема блока сравнения.

Генератор случайной последовательности (см. фиг. 1) состоит из первого селектора-мультиплексора 1, второго селектора-мультиплексора 2, первого регистра 3, источника случайных чисел 4, оперативного запоминающего устройства 5, К блоков хранения границ интервалов 6₁-6_K, K блоков сравнения 7₁-7_K, шифратора приоритетов 8, N инверторов 9₁-9_N и второго регистра 10.

Элементы соединены между собой следующим образом (см. фиг. 1). P-разрядный выход «Случайное число» 42 источника случайных чисел 4 соединен с P-разрядными входами «Случайное число» 71₁-71_K K блоков сравнения 7₁-7_K, P-разрядный выход 65_k k-го блока хранения границ интервалов 6_k, где k=1, 2, …, K, соединен с P-разрядным входом «Верхняя граница» 72_k k-го блока сравнения 7_k. Выход «Результат сравнения» 73_k k-го блока сравнения 7_k соединен с k-м инверсным входом 81_k шифратора приоритетов 8, n-й инверсный выход 82_n которого, где n=1, 2, …, N, соединен с входом 91_n n-го инвертора 9_n. Вход выбора 13 (вход SE) первого селектора-мультиплексора 1 соединен с управляющим входом 41 источника случайных чисел 4 и является управляющим входом 07 генератора, первый N-разрядный информационный вход 11 (вход для разрядов A₁-A_N) первого селектора-мультиплексора 1 является первым N-разрядным адресным входом 01 генератора, N-разрядный выход 14 (выход для разрядов Q₁-Q_N) первого селектора-мультиплексора 1 соединен с N-разрядным адресным входом 52 (входом для разрядов A₁-A_N) оперативного запоминающего устройства 5, инверсные входы «Чтение/запись» 54 (вход $$\overline{WE}$$ ) и «Выбор кристалла» 51 (вход $$\overline{CS}$$ ) которого являются соответственно первым входом «Чтение/запись» 02 и первым входом «Выбор кристалла» 04 генератора. Причем M-разрядный выход 55 (выход для разрядов C₁-C_M) оперативного запоминающего устройства 5 является M-разрядным выходом «Результат» 013 генератора, M-разрядный информационный вход 53 (вход для разрядов D₁-D_M) оперативного запоминающего устройства 5 является M-разрядным информационным входом 03 генератора. При этом P-разрядный информационный вход 63_k (вход для разрядов D₁-D_P) k-го блока хранения границ интервалов 6_k является k-м P-разрядным информационным входом 09_k генератора, n-й разряд N-разрядного информационного входа 101 второго регистра 10 соединен с инверсным выходом 92_n n-го инвертора 9_n, а N-разрядный выход 104 второго регистра 10 соединен с вторым N-разрядным информационным входом 12 (входом для разрядов B₁-B_N) первого селектора-мультиплексора 1 и вторым N-разрядным информационным входом 22 (входом для разрядов B₁-B_N) второго селектора-мультиплексора 2, первый N-разрядный вход 21 которого является вторым N-разрядным адресным входом 05 генератора, а его N-разрядный выход 24 соединен с N-разрядным информационным входом 31 первого регистра 3, N-разрядный выход 34 которого соединен с N-разрядными адресными входами 62₁-62_K K блоков хранения границ интервалов 6₁-6_K, соответствующие инверсные входы «Выбор кристалла» 61₁-61_K (входы $$\overline{CS}$$ ) и «Чтение/запись» 64₁-64_K (входы $$\overline{WE}$$ ) которых объединены между собой и являются соответственно вторым входом «Выбор кристалла» 08 и вторым входом «Чтение/запись» 010 генератора. Вход выбора 23 (вход SE) второго селектора-мультиплексора 2 соединен с управляющим входом 41 источника случайных чисел 4, входы инициализации 33 и 103 (входы С) первого 3 и второго 10 регистров являются соответственно первым 06 и вторым 012 входом «Установка» генератора, а входы сброса 32 и 102 (входы R) первого 3 и второго 10 регистров объединены и являются входом «Обнуление» 011 генератора.

Число «N, (N=[log₂K]; N≥1)» (блоков, разрядов, входов, выходов и т.п.) определяется в соответствии с количеством двоичных разрядов, достаточных для адресации элементов заданного множества генерируемых значений случайной последовательности (т.е. для адресации элементов набора данных) и, как правило, составляет от 2 (двух) до 10 (десяти).

Число «K, (K≥2)» характеризует максимально возможную мощность заданного множества генерируемых значений случайной последовательности (т.е. количество элементов в заданном наборе данных) и, как правило, составляет от 2 (двух) до 500 (пятисот).

Число «M, (M≥2)» характеризует количество двоичных разрядов, достаточное для представления максимального значения из числа значений, входящих в состав заданного множества генерируемых значений случайной последовательности (т.е. для представления значений элементов заданного набора данных) и, как правило, составляет от 2 (двух) до 10 (десяти).

Число «P, (P>N)» характеризует разрядность информационных входов генератора и определяется в соответствии с количеством, большим, чем количество двоичных разрядов, достаточных для адресации элементов заданного множества генерируемых значений случайной последовательности и, как правило, составляет от 3 (трех) до 11 (одиннадцати).

Блоки сравнения 7₁-7_K, входящие в общую структурную схему генератора случайной последовательности, предназначены для сравнения случайного значения, генерируемого источником случайных чисел, и значения на выходе соответствующего регистра, а также для формирования результата сравнения. Блок сравнения 7_k может быть технически реализован, как показано на фиг. 2, содержит компаратор 7.1_k, P-входовый элемент ИЛИ-НЕ 7.2_k и элемент ИЛИ 7.3_k, первый вход 7.3_k-1 которого подключен к выходу «Неравенство» 7.1_k-3 (выходу А>В) компаратора 7.1_k. Второй вход 7.3_k-2 элемента ИЛИ 7.3_k подключен к инверсному выходу 7.2_k-2 P-входового элемента ИЛИ-НЕ 7.2_k, выход 7.3_k-3 элемента ИЛИ 7.3_k является выходом «Результат сравнения» 73_k блока сравнения 7_k. P входов (входов A₁-A_P) первой группы 7.1_k-1 информационных входов компаратора 7.1_k являются P-разрядным входом «Случайное число» 71_k блока сравнения 7_k, Р входов (входов B₁-B_P) второй группы 7.1_k-2 информационных входов компаратора 7.1_k соединены с соответствующими входами 7.2_k-1₁-7.2_k-1_P P-входового элемента ИЛИ-НЕ 7.2_k и являются вторым P-разрядным информационным входом «Верхняя граница» 72_k блока сравнения 7_k.

Компаратор 7.1_k блока сравнения 7_k предназначен для сравнения двух P-разрядных чисел и формирования результата сравнения. Описание работы и схема компаратора известны, приведены, например, в книге [В.Л. Шило «Популярные цифровые микросхемы». - М.: «Радио и связь», 1987, с.183-184].

Элемент ИЛИ-НЕ 7.2_k блока сравнения 7_k предназначен для формирования на своем выходе значения логического нуля, если на всех разрядах второго P-разрядного входа «Верхняя граница» 72_k блока сравнения 7_k установлены значения логической единицы. Элемент ИЛИ-НЕ 7.2_k может быть реализован технически на базе серийно выпускаемого элемента ИЛИ-НЕ, как показано в [И.И. Петровский и др. Логические ИС КР1533, КР1554. Справочник в двух частях. Часть 1. - М.: Бином, 1993, с.246-247].

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

Первый селектор-мультиплексор 1, входящий в общую структурную схему генератора случайной последовательности, предназначен для коммутации на свой N-разрядный выход сигналов одной из двух групп: с первого N-разрядного информационного входа 11 (входа для разрядов A₁-A_N) либо со второго N-разрядного информационного входа 12 (входа для разрядов B₁-B_N). Схема построения первого селектора-мультиплексора 1 известна, он может быть технически реализован на базе серийно выпускаемого N-разрядного селектора-мультиплексора, как показано в [И.И. Петровский и др. Логические ИС КР1533, КР1554. Справочник в двух частях. Часть 1. - М.: Бином, 1993, с.211].

Второй селектор-мультиплексор 2, входящий в общую структурную схему генератора случайной последовательности, предназначен для коммутации на свой N-разрядный выход сигналов одной из двух групп: с первого N-разрядного входа 21 (входа для разрядов A₁-A_N) либо со второго N-разрядного информационного входа 22 (входа для разрядов B₁-B_N). Он отвечает за запись новых значений (для данного шага) верхних границ интервалов, на которые разбивается множество адресов заданного набора данных, определяемых на каждом последующем шаге вероятностями переходов случайного процесса из состояния в состояние [1]. Схема построения второго селектора-мультиплексора 2 известна и аналогична схеме первого селектора-мультиплексора 1. Он может быть технически реализован на базе серийно выпускаемого N-разрядного селектора-мультиплексора, как показано в [И.И. Петровский и др. Логические ИС КР1533, КР1554. Справочник в двух частях. Часть 1. - М.: Бином, 1993, с.211].

Первый регистр 3, входящий в общую структурную схему генератора случайной последовательности, предназначен для регистрации и хранения двоичных кодов, определяющих генерацию последовательности значений из заданного множества значений с учетом наличия вероятностной связи каждого очередного значения с предыдущим. Он отвечает за регистрацию и хранение значений новых (для каждого последующего шага) верхних границ интервалов, величина которых динамично изменяется по методам марковских цепей, зависит от вероятности перехода случайного процесса из состояния в состояние и соответствует значениям требуемых на данном шаге вероятностей наблюдения соответствующих элементов заданного набора данных. Описание работы и схема таких регистров известны и приведены, например, в книге [П.П. Мальцев, Н.С. Долидзе и др. Цифровые интегральные микросхемы: справочник. - М.: Радио и связь, 1994, с.57-62].

Источник случайных чисел 4, входящий в общую структурную схему генератора случайной последовательности, предназначен для генерирования P-разрядных случайных чисел, известен и может быть технически реализован, как показано, например, в [М.П. Бобнев. Генерирование случайных сигналов. - М.: Энергия, 1971, с.168-174].

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

Блоки хранения границ интервалов 6₁-6_K, входящие в общую структурную схему генератора случайной последовательности, предназначены для хранения двоичных кодов, определяющих граничные значения вероятности появления соответствующих элементов заданного набора данных (набора данных в заданном интервале). Они выполнены в виде оперативных запоминающих устройств, структура их построения известна, они могут быть технически реализованы на базе серийно выпускаемых оперативных запоминающих устройств, как показано в [В.Л. Шило. Популярные цифровые микросхемы. - М.: Радио и связь, 1987, с.164-166].

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

Инверторы 9₁-9_N, входящие в общую схему генератора случайной последовательности, предназначены для инвертирования сигналов с инверсных выходов шифратора приоритетов. Схема реализации инвертора известна и подробно описана, например, в [И.И. Петровский и др. Логические ИС КР1533, КР1554. Справочник в двух частях. Часть 1. - М.: Бином, 1993, с.471-472].

Второй регистр 10, входящий в общую схему генератора случайной последовательности, предназначен для хранения двоичных кодов, определяющих вероятности появления соответствующих элементов заданного набора данных. Он отвечает за регистрацию и хранение значений предыдущих (для прошлого шага) верхних границ интервалов, величина которых динамично изменяется по методам марковских цепей, зависит от вероятности перехода случайного процесса из состояния в состояние и соответствует значениям требуемых на прошедшем шаге вероятностей наблюдения соответствующих элементов заданного набора данных. Он аналогичен первому регистру 3, описание работы и схема таких регистров известны и приведены, например, в книге [П.П. Мальцев, Н.С. Долидзе и др. Цифровые интегральные микросхемы: справочник. - М.: Радио и связь, 1994, с.57-62].

В предлагаемом генераторе случайной последовательности выбор значения элемента из заданного набора данных с учетом наличия вероятностной связи каждого очередного значения с предыдущим осуществляется на основе закона распределения, который задается путем указания требуемой вероятности появления соответствующего элемента заданного набора данных. При этом применяется подход [2], основанный на использовании источника случайных чисел, распределенных равномерно в диапазоне [0; 1). Данный диапазон разбивается на совокупность интервалов, количество которых соответствует количеству элементов в заданном наборе данных. Величины интервалов соответствуют значениям требуемых вероятностей наблюдения соответствующих элементов заданного набора данных. Вероятность попадания случайного числа, сформированного источником случайных чисел, внутрь каждого интервала равна его длине. Номер интервала используется в качестве адреса для извлечения элемента заданного набора данных из оперативного запоминающего устройства, а для задания интервалов указываются их верхние границы.

Исходное задание начальных вероятностей появления элементов заданного набора данных, на первом шаге - без учета наличия вероятностной связи каждого очередного значения с предыдущим, осуществляется следующим образом. Пусть Н={h₁, h₂, …, h_k, …, h_K} - множество требуемых вероятностей появления элементов заданного набора данных, где $$k=\overline{1,K}$$ , K - количество элементов заданного набора данных, а В={b₁, b₂, …, b_k, …, b_K} - множество соответствующих значений начальных верхних границ интервалов. Тогда начальное значение верхней границы k-го интервала будет равно сумме значений вероятностей появления элементов из заданного набора данных от 1-го до k-го:

Таким образом, диапазон [0; 1) на первом шаге генерации будет разбит на следующие интервалы:

Используется Р-разрядный источник случайных чисел с равномерным законом распределения. При этом Р-разрядный двоичный код, формируемый на выходе источника случайных чисел, и Р-разрядный двоичный код, используемый для задания начальной (для первого шага) верхней границы интервала, рассматриваются как числа из диапазона [0; 1) без указания целой части.

Например, задано множество требуемых вероятностей появления элементов заданного набора данных H={0,125; 0,125; 0,25; 0,5}. Тогда значения верхних границ интервалов будут равны соответственно 0,125, 0,25, 0,5 и 1. В соответствии с правилами перевода [3] правильных десятичных дробей в двоичное представление данные значения в четырехразрядном коде представляются соответственно в виде чисел 0,0010, 0,0100, 0,1000, 0,1111. А в устройство заносятся только дробные части этих чисел: соответственно значения 0010, 0100, 1000 и 1111.

Аналогичным образом, если источник случайных чисел сформировал значение 1101 (в десятичном представлении 0,8125), то, представляя это значение как дробную часть числа из диапазона [0; 1), т.е. как 0,1101, и учитывая множество начальных верхних границ интервалов из предыдущего абзаца, видно, что случайное значение попало в интервал, ограниченный числами 0,1000 и 0,1111.

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

Генератор случайной последовательности работает следующим образом.

В исходном положении на управляющем входе 07, перовом 06 и втором 012 входах «Установка» установлены значения логического нуля, а на первом 02 и втором 010 входах «Чтение/запись» и на первом 04 и втором 08 входах «Выбор кристалла» - значения логической единицы.

Генератор работает в следующих режимах:

режим подготовки к генерации;

режим генерации.

Режим работы генератора с учетом вероятностной связи между состояниями случайного процесса определяется комбинацией сигналов на управляющем входе 07, первом 06 и втором 012 входах «Установка», первом 02 и втором 010 входах «Чтение/запись», а также на первом 04 и втором 08 входах «Выбор кристалла».

Для перевода устройства в режим подготовки необходимо на управляющий вход 07 генератора, первый 04 и второй 08 входы «Выбор кристалла», первый 02 и второй 010 входы «Чтение/запись» подать значения логического нуля, а на первый 06 и второй 012 входы «Установка» - значение логической единицы.

В режиме генерации на управляющем входе генератора 07, первом 02 и втором 010 входах «Чтение/запись» устанавливаются значения логической единицы, а на первом 04 и втором 08 входах «Выбор кристалла» и первом 06 и втором 012 входах «Установка» - значения логического нуля.

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

Первый шаг - занесение множества А={a₁, a₂, …, a_K} значений элементов заданного набора данных в оперативное запоминающее устройство, при этом:

0≤a _k≤2^M-1 - элемент заданного набора данных, где $$k=\overline{1,K}$$ ;

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

K≥1 - количество элементов в заданном наборе данных;

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

Второй шаг - установка множества В={b₁, b₂, …, b_K} значений начальных верхних границ интервалов, на которые разбивается множество адресов заданного набора данных А.

Третий шаг - установка множества С={с₁, с₂, …, c_K} значений новых (для данного шага) верхних границ интервалов, на которые разбивается множество адресов заданного набора данных А, определяемых на каждом последующем шаге вероятностями переходов случайного процесса из состояния в состояние [1].

Первый шаг подготовки генератора к работе включает следующие действия. По первому N-разрядному адресному входу 01 генератора на первую группу информационных входов 11 (группу входов A₁-A_N) первого селектора мультиплексора 1 подается N-разрядный адрес, по которому должно быть записано значение первого элемента а₁. На управляющем входе 07 генератора устанавливают значение логического нуля, который поступает на вход 13 (вход SE) первого селектора-мультиплексора 1, что приводит к коммутации адреса, установленного на входе 11 (входах A₁-A_N) первого селектора-мультиплексора 1, на N-разрядный адресный вход 52 (вход для разрядов A₁-A_N) оперативного запоминающего устройства 5. По M-разрядному информационному входу 03 генератора на информационные входы 53 (входы D₁-D_M) оперативного запоминающего устройства 5 подается значение первого элемента а ₁ заданного набора данных, которое записывается в оперативное запоминающее устройство 5 при поступлении на его входы 51 ( $$\overline{CS}$$ ) и 54 ( $$\overline{WE}$$ ) значений логического нуля по первым входам «Выбор кристалла» 04 и «Чтение/запись» 02 соответственно. Затем по первому N-разрядному адресному входу 01 генератора на первую группу информационных входов 11 (группу входов A₁-A_N) первого селектора мультиплексора 1 подается N-разрядный адрес, по которому должно быть записано значение второго элемента a ₂, а по M-разрядному информационному входу 03 генератора на информационные входы 53 (входы D₁-D_M) оперативного запоминающего устройства 5 подают значение элемента a ₂ и путем установки значений логического нуля на первых входах «Выбор кристалла» 04 и «Чтение/запись» 02 записывают значение а ₁ в оперативное запоминающее устройство 5. Аналогичным образом в оперативное запоминающее устройство 5 заносятся все К значений элементов заданного набора данных. После чего на первом входе «Чтение/запись» 02 генератора устанавливают значение логической единицы.

Второй шаг подготовки генератора к работе выполняется следующим образом. На K P-разрядных информационных входах «Верхняя граница» 09₁-09_K генератора устанавливают начальные значения верхних границ интервалов. При этом на вход 09₁ устанавливают значение b₁, которое поступает на группу информационных входов 63₁ (группу D₁-D_P) блока хранения границ интервалов 6₁, на вход 09₂ - значение b₂, которое поступает на группу информационных входов 63₂ блока хранения границ интервалов 6₂, на вход 09_K - значение b_K, которое поступает на группу информационных входов 63_K блока хранения границ интервалов 6_K. Для записи начальных значений верхних границ интервалов в блоки хранения границ интервалов 6₁-6_K на вторых входах «Выбор кристалла» 08 и «Чтение/запись» 010 устройства устанавливают значение логической единицы, которая поступает на входы 61_k ( $$\overline{CS}$$ ) и 64_l ( $$\overline{WE}$$ ) каждого k-го блока хранения границ интервалов 6k. По окончании записи начальных значений верхних границ интервалов в соответствующие блоки хранения границ интервалов на вторых входах «Выбор кристалла» 08 и «Чтение/запись» 010 устройства устанавливают значение логического нуля.

Третий шаг подготовки генератора к работе выполняется следующим образом. По второму N-разрядному адресному входу 05 генератора на первый N-разрядный вход 21 (входов разрядов A₁-A_N) второго селектора мультиплексора 2 подается N-разрядный адрес, по которому должно быть записано значение первого элемента c₁, определяющее новое значение верхней границы данного (первого) интервала исходя из вероятностей переходов генерируемого случайного процесса из состояния в состояние. Аналогичным образом во второй селектор-мультиплексор 2 заносятся все K новых N-разрядных значений верхних границ интервалов. На управляющем входе 07 генератора устанавливают значение логического нуля, который поступает на вход 23 (вход SE) второго селектора-мультиплексора 2, что приводит к коммутации адреса, установленного на входе 21 второго селектора-мультиплексора 2 на N-разрядный информационный вход 31 (вход регистров D₁-D_N) первого регистра 3. В режиме подготовки генератора к работе на входы сброса 32 и 102 (входы R) первого 3 и второго 10 регистров соответственно поданы значения логической единицы. На второй N-разрядный информационный вход 22 (вход для разрядов B₁-B_N) второго селектора-мультиплексора 2 с выхода 104 второго регистра 10 подается предыдущее (с прошлого шага) значение первого элемента c₁ из множества значений вероятностей переходов случайного процесса из состояния в состояние, которое определяет новое значение верхней границы данного интервала. Это значение первого элемента c₁ записывается в первый регистр 3, причем для записи новых (для данного шага) значений верхних границ интервалов в первый регистр 3 на первом входе «Установка» 06 устройства устанавливают значение логической единицы, которая поступает на вход инициализации 33 (вход С) первого регистра 3. По окончании записи в первый регистр 3 новых (для данного шага) значений верхних границ интервалов в первый регистр 3 на первом входе «Установка» 06 устройства устанавливают значение логического нуля.

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

В режиме генерации работа устройства происходит следующим образом (см. фиг. 1). На управляющий вход 07 генератора подают значение логической единицы, которое поступает на вход выбора 13 (вход SE) первого селектора-мультиплексора 1, что обеспечивает коммутацию адреса, поступающего с выхода 104 второго регистра 10, на N-разрядный адресный вход 52 (вход для разрядов A₁-A_N) оперативного запоминающего устройства 5.

Источник случайных чисел 4 при наличии на управляющем входе 07 генератора значения логической единицы формирует P-разрядное случайное значение адреса, которое поступает одновременно на P-разрядные входы «Случайное число» 71₁-7_K K блоков сравнения 7₁-7_K, где происходит сравнение случайного значения адреса с начальными значениями верхних границ заданных интервалов В={b₁, b₂, …, b_K} (см. фиг. 2). В случае если поступившее значение адреса принадлежит k-му интервалу, т.е. оно меньше либо равно значения верхней границы k-го интервала, то на выходе «Неравенство» (выходе А>В) компараторов 7.1₁-7.1_k-1 формируются значения логической единицы, а на выходах «Неравенство» остальных компараторов - значения логического нуля.

Сигналы с выходов «Неравенство» каждого компаратора 7.1₁-7.1_K через элементы ИЛИ 7.3₁-7.3_K и выходы «Результат сравнения» 73₁-73_K K блоков сравнения 7₁-7_K поступают на соответствующие инверсные входы 81₁-81_K (входы регистров $${\overline{X}}_0-{\overline{X}}_{K-1}$$ ) шифратора приоритетов 8.

Таким образом (см. фиг. 1), при выполнении условия b_k-1<a_k<b_k на входах 81₁-81_K (входах регистров $${\overline{X}}_0-{\overline{X}}_{K-1}$$ ) шифратора приоритетов 8 будут установлены значения логической единицы, а на входах 81_k-1-81_K (входах регистров $${\overline{X}}_k-{\overline{X}}_{K-1}$$ ) - значения логического нуля. В этом случае на N инверсных выходах 82₁-82_N (выходах $${\overline{Y}}_1-{\overline{Y}}_N$$ ) шифратора приоритетов 8 будет сформирован двоичный код в инверсном представлении, соответствующий значению первого номера входа $${\overline{X}}_k$$ с установленным значением логического нуля, т.е. код, соответствующий числу k - номеру интервала, которому принадлежит значение a_k. Полученный код после инвертирования в элементах 9₁-9_N поступает на N-разрядный информационный вход 101 второго регистра 10, здесь регистрируется как код предыдущего шага, затем поступает на второй N-разрядный информационный вход 12 (вход для разрядов B₁-B_N) первого селектора-мультиплексора 1 и второй N-разрядный информационный вход 22 (вход для разрядов B₁-B_N) второго селектора-мультиплексора 2. Затем со второго N-разрядного информационного входа 12 (входа для разрядов B₁-B_N) первого селектора-мультиплексора 1 полученный и инвертированный код поступает на N-разрядный адресный вход 52 (вход для разрядов A₁-A_N) оперативного запоминающего устройства 5. При этом по первому входу «Выбор кристалла» 04 генератора на вход 51 (вход $$\overline{CS}$$ ) оперативного запоминающего устройства 5 подают значение логического нуля, а по первому входу «Чтение/запись» 02 генератора на вход 54 (вход $$\overline{WE}$$ ) оперативного запоминающего устройства 5 подают значение логической единицы, что соответствует операции чтения данных. Таким образом, в соответствии со случайными адресами, формируемыми источником случайных чисел, происходит чтение начальных (для первого шага работы генератора) значений элементов А={а₁, a₂, …, a_k} заданного набора данных из оперативного запоминающего устройства 5, которые через выход 55 поступают на M-разрядный выход «Результат» 013 генератора.

На втором и последующих шагах генерирования значений дискретного случайного процесса работа устройства осуществляется с учетом вероятностной связи между состояниями случайного процесса (между генерируемыми значениями заданного набора данных) следующим образом. После регистрации значения предыдущих (для прошлого шага) верхних границ интервалов (величина которых динамично изменяется по методам марковских цепей, зависит от вероятности перехода случайного процесса из состояния в состояние и соответствует значениям требуемых на прошедшем шаге вероятностей наблюдения соответствующих элементов заданного набора данных) с выхода 104 второго регистра 10 поступают на второй N-разрядный информационный вход 12 (вход для разрядов B₁-B_N) первого селектора-мультиплексора 1 и второй N-разрядный информационный вход 22 (вход для разрядов B₁-B_N) второго селектора-мультиплексора 2. С выхода 24 второго селектора-мультиплексора 2 предыдущие (с прошлого шага) значения элементов, определяющих новые значения верхних границ интервалов с учетом множества значений вероятностей переходов случайного процесса из состояния в состояние, записываются в первый регистр 3, который отвечает за регистрацию и хранение значений новых верхних границ интервалов. Таким образом, имеем новые, определяемые в соответствии с марковской моделью значения верхних границ интервалов для конкретного шага.

Текущие (изменившиеся по сравнению с начальными) значения верхних границ интервалов для конкретного шага с N-разрядного выхода 34 первого регистра 3 поступают на N-разрядные адресные входы 62₁-62_K К блоков хранения границ интервалов 6₁-6_K и далее на P-разрядные входы «Верхняя граница» 72₁-72_K блоков сравнения 7₁-7_K (см. фиг. 2). На P-разрядные входы «Случайное число» 71₁-71_K блоков сравнения 7₁-7_K по-прежнему поступает P-разрядное случайное значение адреса от источника случайных чисел 4, вновь, но уже для данного конкретного шага происходит сравнение случайного значения адреса с текущими значениями верхних границ заданных интервалов. Цикл повторяется, причем значения предыдущего адреса, поступающего с выхода 104 второго регистра 10 на второй N-разрядный информационный вход 12 (вход для разрядов B₁-B_N) первого селектора-мультиплексора 1, затем на N-разрядный адресный вход 52 (вход для разрядов A₁-A_N) оперативного запоминающего устройства 5, служат исходными данными для получения последующих значений элемента из заданного набора данных с учетом наличия вероятностной связи каждого очередного значения с предыдущим.

В итоге в соответствии со случайными адресами, формируемыми источником случайных чисел и в соответствии с корректируемыми на каждом шаге (с учетом наличия вероятностной связи каждого очередного значения с предыдущим) текущими значениями верхних границ интервалов, происходит чтение текущих вероятностно-временных значений элементов А={а ₁, а ₂, …, a _K} заданного набора данных из оперативного запоминающего устройства 5, которые через выход 55 поступают на M-разрядный выход «Результат» 013 генератора.

Генератор прекращает работу, когда на его управляющий вход 07 подается значение логического нуля, что соответствует прекращению формирования источником случайных чисел случайных адресов, либо когда по первому входу «Выбор кристалла» 04 генератора на вход 51 (вход $$\overline{CS}$$ ) оперативного запоминающего устройства 5 подают значение логической единицы.

Таким образом, предлагаемый генератор случайной последовательности обеспечивает расширение области его применения за счет реализации возможности генерации последовательности значений из заданного множества значений с учетом наличия вероятностной связи каждого очередного значения с предыдущим. Реализация возможности генерации случайной последовательности с учетом наличия вероятностной связи каждого очередного значения с предыдущим происходит за счет реализуемой во втором селекторе-мультиплексоре 2 записи новых значений (для текущего конкретного шага) верхних границ интервалов, на которые разбивается множество адресов заданного набора данных, определяемых на каждом последующем шаге вероятностями переходов случайного процесса из состояния в состояние, а также за счет реализуемых в первом регистре 3 и втором регистре 10 регистрации и хранения значений новых верхних границ интервалов и значений верхних границ интервалов предыдущего шага соответственно. Данный результат обусловлен получением на M-разрядном выходе «Результат» 013 генератора текущих вероятностно-временных значений элементов заданного набора данных с учетом наличия вероятностной связи каждого очередного значения с предыдущим.

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

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

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

1. Тихонов В.И., Миронов М.А. Марковские процессы. - М.: Советское радио, 1977. - 488 с.

2. Моделирование информационных систем. / Под ред. О.И. Шелухина. Учебное пособие. - М.: Радиотехника, 2005. - 368 с.

3. Никитин Б.Я., Скребков В.Н. Теоретические основы вычислительной техники. Часть 2. - Л.: ЛВВИУС, 1988, стр. 9-11.

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

Генератор случайной последовательности, содержащий К блоков сравнения (7₁-7_K), где К≥2 - максимально возможная мощность заданного множества генерируемых значений, первый селектор-мультиплексор (1), оперативное запоминающее устройство (5), шифратор приоритетов (8), N инверторов (9₁-9_N), где N=[log₂K] - число двоичных разрядов, достаточное для адресации элементов заданного множества генерируемых значений, К блоков хранения границ интервалов (6₁-6_K), источник случайных чисел (4), Р-разрядный, где Р>N, выход «Случайное число» (42) которого соединен с Р-разрядными входами «Случайное число» К блоков сравнения (7₁-7_K), Р-разрядный выход k-го блока хранения границ интервалов (6_k), где k=1, 2, …, К, соединен с Р-разрядным входом «Верхняя граница» (72_k) k-го блока сравнения (7_k), выход «Результат сравнения» (73_k) k-го блока сравнения (7_k) соединен с k-м инверсным входом шифратора приоритетов (8), n-й инверсный выход которого, где n=1, 2, …, N, соединен с входом n-го инвертора (9_n), вход выбора первого селектора-мультиплексора (1) соединен с управляющим входом источника случайных чисел (4) и является управляющим входом генератора (07), первый N-разрядный информационный вход первого селектора-мультиплексора (1) является первым N-разрядным адресным входом (01) генератора, N-разрядный выход первого селектора-мультиплексора (1) соединен с N-разрядным адресным входом оперативного запоминающего устройства (5), инверсные входы «Чтение/запись» и «Выбор кристалла» которого являются соответственно первым входом «Чтение/запись» (02) и первым входом «Выбор кристалла» (04) генератора, М-разрядный выход оперативного запоминающего устройства (5), где М≥2 - количество разрядов, достаточное для представления максимального значения из числа значений, входящих в состав заданного множества генерируемых значений, является M-разрядным выходом «Результат» (013) генератора, М-разрядный информационный вход оперативного запоминающего устройства (5) является М-разрядным информационным входом генератора (03), Р-разрядный информационный вход k-го блока хранения границ интервалов является k-м Р-разрядным информационным входом (09_k) генератора, отличающийся тем, что дополнительно введены второй селектор-мультиплексор (2), первый регистр (3), второй регистр (10), а блоки хранения границ интервалов (6₁-6_K) выполнены в виде оперативных запоминающих устройств, при этом n-й разряд N-разрядного информационного входа второго регистра (10) соединен с инверсным выходом n-го инвертора (9_n), а N-разрядный выход второго регистра (10) соединен с вторым N-разрядным информационным входом первого селектора-мультиплексора (1) и вторым N-разрядным информационным входом второго селектора-мультиплексора (2), первый N-разрядный вход которого является вторым N-разрядным адресным входом (05) генератора, а его N-разрядный выход соединен с N-разрядным информационным входом первого регистра (3), N-разрядный выход которого соединен с N-разрядными адресными входами каждого из К блоков хранения границ интервалов (6₁-6_K), соответствующие инверсные входы «Выбор кристалла» и «Чтение/запись» которых объединены между собой и являются соответственно вторым входом «Выбор кристалла» (08) и вторым входом «Чтение/запись» (010) генератора, вход выбора второго селектора-мультиплексора (2) соединен с управляющим входом источника случайных чисел (4), входы инициализации первого (3) и второго (10) регистров являются соответственно первым (06) и вторым (012) входом «Установка» генератора, а входы сброса первого (3) и второго (10) регистров объединены и являются входом «Обнуление» (011) генератора.