Устройство генерации равномерно распределенных псевдослучайных чисел Российский патент 2025 года по МПК G06F7/58 G06F1/02 

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

Из уровня техники, известен генератор равномерно распределенных случайных чисел (патент RU 2092892, МПК: G06F 7/58 (1995.01), опубликовано 10.10.1997). Указанный генератор содержит генератор импульсов, выход которого подключен к входу генератора линейно изменяющегося напряжения и входу "Запись " блока памяти, выход которого соединен с первым входом первой схемы сравнения, выход источника шума подключен к информационному входу блока памяти, выход генератора линейно изменяющегося напряжения подключен к второму входу первой схемы сравнения, элемент И-НЕ, выход которого соединен со своим первым входом и входом "Сдвиг" регистра сдвига, выход i-го и k-го разрядов регистров сдвига подключены соответственно к первому и второму входам сумматора по модулю два, выход которого соединен с входом "Сдвиг" регистра сдвига, а выход k-го разряда которого является выходом генератора. При этом в структуру генератора введены первый и второй элементы И, RS-триггер, элемент НЕ, регулируемый источник напряжения и вторая схема сравнения, к первому и второму входам которой подключены соответственно выходы генератора линейно изменяющегося напряжения и регулируемого источника напряжения, выход второй схемы сравнения подключен к второму входу первого элемента И, выход которого соединен с входами второго элемента И, выход первой схемы сравнения подключен к первому входу первого элемента И и через элемент НЕ - к R-входу RS-триггера, S-вход которого соединен с выходом второго элемента И, а выход RS-триггера подключен к второму входу элемента И-НЕ.

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

Известен генератор нелинейных псевдослучайных последовательностей {патент RU 2549524, МПК: G06F 7/58 (2006.01), опубликовано 27.04.2015), содержащий генератор тактовых импульсов, регистр сдвига на h разрядов с синхровходом и с последовательным входом, h умножителей, каждый из которых на два входа и один выход, и сумматор по модулю два на h входов. При этом в него введены h/3 однотипных нелинейных преобразователей с тремя входами данных и двумя выходами каждый, причем hmod3=0, и блок из h мультиплексоров с двумя входами данных каждый и с общим управляющим входом, каждый из нелинейных преобразователей содержит инвертор, четыре функциональных преобразователя и четыре конъюнктора на два входа каждый, из которых первый и второй входят в первую группу конъюнкторов, а третий и четвертый - во вторую группу конъюнкторов, и два дизъюнктора на два входа каждый.

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

Известен генератор случайной последовательности {патент RU 2797406, МПК: G06F 7/58 (2006.01), опубликовано 05.06.2023), который содержит первый селектор-мультиплексор 1, второй селектор-мультиплексор 2, первый регистр 3, источник случайных чисел 4, оперативное запоминающее устройство 5, К≥2 блоков хранения границ интервалов 6₁-6_K, К блоков сравнения 7₁-7_K, шифратор приоритетов 8, N≥1 инверторов 9₁-9_N, второй регистр 10 и блок нейро-нечеткой сети 11. К недостатку указанного изобретения можно отнести наличие вычислительно затратных нелинейных операций вычисления функций ехр{•} в блоке нейро-нечеткой сети.

Известен способ формирования псевдослучайных сигналов и устройство для его осуществления {патент RU 2769539, МПК: G06F 7/58 (2006.01), опубликовано 01.04.2022). Устройство содержит пять элементов исключающее «ИЛИ», восемь умножителей в поле Галуа GF(2^P), четыре регистра и один трехвходовый элемент исключающее «ИЛИ», при этом в устройство дополнительно введены три элемента исключающее «ИЛИ», три линии задержки, вычислитель, счетчик отсчетов псевдослучайного сигнала, четыре регистра, три переключателя и блок памяти примитивных полиномов.

К недостатку устройства можно отнести аппаратные затраты на реализацию умножения в полях Галуа {Червяков Н.И., Бабенко М.Г., Ляхов П.А., Лавриненко И.Н., Лягин A.M. Умножение и деление в системе остаточных классов с использованием полей Галуа GF(p) // Информатика, телекоммуникации и управление. 2014. Т. 3, №198. С. 65-76).

Аналогичный недостаток можно отнести к устройству для генерации псевдослучайных чисел {патент. RU 2774812, МПК: G06F 7/58 (2006.01), опубликовано 23.06.2022), которое состоит из двух регистров 2.1 и 2.2 разрядности n, двух блоков сложения 4.1 и 4.2 в GF(2ⁿ), блока сложения 3 по модулю 2ⁿ, двух блоков 5 и 6 циклического сдвига и дополнительно содержит третий блок 7 циклического сдвига, и к генератору псевдослучайных чисел {патент RU 2815485, МПК: G06F 7/58 (2006.01), опубликовано 18.03.2024), который состоит из двух регистров разрядности n, блока сложения в поле Галуа GF(2ⁿ), двух блоков умножения в GF(2ⁿ), двух блоков сложения в GF(2ⁿ).

В качестве прототипа выбрано наиболее близкое по совокупности признаков устройство генерации псевдослучайных чисел (патент RU 2815828, МПК: G06F 7/58 (2006.01), G06F 1/02 (2006.01), опубликовано 22.03.2024). Указанное устройство включает в себя четыре сумматора/вычитателя, три интегратора, три умножителя, три узла формирования констант, блок временной задержки и аналоговый блок, при этом элементы соединены между собой с обеспечением генерации псевдослучайных чисел. При этом, с целью повышения функциональных возможностей, сокращения аппаратурных затрат и хаотичности выходных сигналов, первый вход первого сумматора/вычитателя устройства-прототипа соединен с первым входом первого умножителя, с входом блока временной задержки, с выходом первого интегратора, первым входом второго умножителя и является первым выходом генератора, второй вход первого сумматора/вычитателя соединен с первым входом второго сумматора/вычитателя, первым входом четвертого умножителя, выходом второго интегратора и является вторым выходом генератора, третий вход первого сумматора/вычитателя соединен с выходом аналогового блока, второй вход четвертого умножителя подключен к выходу блока временной задержки, выход первого сумматора/вычитателя соединен с первым входом первого умножителя, второй вход которого подключен к выходу первого узла формирования константы, а выход первого умножителя к соответствующему входу первого интегратора, второй вход второго умножителя подключен к выходу второго узла формирования константы, а выход второго умножителя - ко второму входу второго сумматора/вычитателя, выход которого соединен с первым входом третьего сумматора/вычитателя, второй вход которого подключен к выходу третьего умножителя, второй вход которого подключен к выходу третьего интегратора и является третьим выходом генератора и первым входом пятого умножителя, второй вход которого соединен с выходом третьего узла формирования константы, а выход пятого умножителя подключен к первому входу четвертого сумматора/вычитателя, второй вход которого соединен с выходом четвертого умножителя, выход четвертого сумматора/вычитателя подключен к входу третьего интегратора, а вход второго интегратора соединен с соответствующим выходом третьего сумматора/вычитателя.

Устройство прототипа обладает хорошими показателями качества. Так, его показатель минимальной информационной энтропии равен 0,996, что является высоким значением, поскольку энтропия идеального генератора равна единице. Приводимый в описании изобретения прототипа иллюстративный материал, в частности, фиг. 2 и фиг. 3 описания прототипа, подтверждает его качественные показатели.

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

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

Технический результат изобретения заключается в уменьшении количества умножителей в схеме генератора псевдослучайных чисел с сохранением высокой энтропии и близких к идеальному шуму корреляционных свойств, так как автокорреляционная функция шума имеет вид дельта-функции Дирака {Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения: учеб. пособие для втузов. 2-е изд. М.: Высшая школа, 2000. 480 с).

Для достижения технического результата устройство генерации равномерно распределенных псевдослучайных чисел выполнено по принципу конгруэнтного генератора (Lehmer D.H. Mathematical methods in large-scale computing units // Proc. of the 2nd Symposium on large-scale digital calculating machinery. Harvard University Press, 195LP. 141-146; Knuth D.E. The art of computer programming. Vol.2: Seminumerical algorithms. 3rd ed. Boston: Addison-Wesley, 1997. 762 p), однако для повышения его энтропии и устранения недостатков, свойственных линейному конгруэнтному генератору, дополнительно реализован сдвиг сформированного бинарного кода на r разрядов вправо и разрядов влево, причем данные величины формируются непосредственно из генерируемого псевдослучайного отсчета.

Структурная схема предлагаемого генератора равномерно распределенных n-разрядных случайных двоичных чисел представлена на фиг. 1 и содержит:

- первый, второй, третий, четвертый, пятый, шестой и седьмой узлы формирования констант с_1, с₂, с₃, с₄, с₅, с₆ и с₇ - соответственно блоки 1, 7, 9, 11, 13, 15 и 19;

- первый и второй сумматоры - соответственно блоки 2 и 10;

- двухвходовый мультиплексор 3,

- первый и второй параллельные регистры - соответственно блоки 4 и 23;

- синхронизатор 5;

- умножитель 6;

- первый, второй, третий, четвертый и пятый модули логического сдвига вправо - соответственно блоки 8, 12, 14, 18 и 20;

- логическую схему поразрядного Исключающего ИЛИ (XOR) 16;

- модуль вычисления сдвигов r и 17;

- модуль логического сдвига влево 21;

- логическую схему поразрядного ИЛИ 22.

На первый вход первого сумматора 2 с выхода первого узла формирования констант 1 поступает 2n-разрядная константа Сn, необходимая для инициализации устройства генерации равномерно распределенных псевдослучайных чисел. На второй вход первого сумматора 2 поступает внешний 2n-разрядный параметр z - так называемое «зерно» (от англ. seed).

Первый параллельный регистр 4 в режиме генерации хранит текущее -е состояние s_i; генератора в виде двоичного 2n-разрядного числа в формате представления без знака. Состояние s_i+1 в следующий момент времени (i+1) формируется на выходе второго сумматора 10:

при этом с₃=2n, а вычисленное новое состояние s_i+1 подается на вход данных первого параллельного регистра 4 путем коммутации значения с первого входа данных двухвходового мультиплексора 3 на его выход.

Вычисления согласно (1) реализует каскадное соединение блоков умножителя 6, на первый вход которого с выхода первого параллельного регистра 4 поступает текущее 2n-разрядное состояние генератора s_i, а на второй вход - 2n-разрядная константа c₂ с выхода второго узла формирования констант 7, первого модуля логического сдвига вправо 8, первый вход которого соединен с выходом умножителя 6, а на второй поступает значение сдвига с₃ с выхода третьего узла формирования констант 9 и второго сумматора 10, первый вход которого соединен с выходом третьего узла формирования констант 9, а на второй поступает значение с₄ с выхода четвертого узла формирования констант 11.

Оператор вида «а>>b» в (1) по аналогии с синтаксисом языка программирования С для чисел в формате представления без знака означает логический сдвиг числа а вправо на b разрядов.

В момент включения схемы, т.е. в момент времени i=0, синхронизатор 5 вырабатывает и подает на адресный вход двухвходового мультиплексора 3 короткий строб-импульс для того, чтобы в первый параллельный регистр 4 было записано инициализирующее значение s₀, действующее на втором входе данных двухвходового мультиплексора 3, к которому подключен выход первого сумматора 2. Таким образом, в момент включения устройства на выходе двухвходового мультиплексора 3 действует инициализирующее значение

коммутируемое на выход мультиплексора с его второго входа.

Значение s_l+1 с выхода второго сумматора 10 параллельно поступает на первый вход второго модуля логического сдвига вправо 12, на второй вход которого поступает значение сдвига с₅ с выхода пятого узла формирования констант 13, и на первый вход логической схемы поразрядного Исключающего ИЛИ 16. На второй вход логической схемы 16 поступает значение с выхода второго модуля логического сдвига вправо 12. В результате на выходе логической схемы поразрядного Исключающего ИЛИ 16 формируется значение:

где «⊕» - обозначение операции поразрядного XOR.

Значение х с выхода логической схемы поразрядного Исключающего ИЛИ 16 далее поступает на первый вход четвертого модуля логического сдвига вправо 18, на второй вход которого поступает значение с₇ с выхода седьмого узла формирования констант 19. В результате на выходе четвертого модуля логического сдвига вправо 18 действует значение:

Значение w далее параллельно поступает на первые входы пятого модуля логического сдвига вправо 20 и модуля логического сдвига влево 21. На вторые входы данных блоков с первого и второго выходов модуля вычисления сдвигов 17 соответственно поступают сигналы r и , несущие информацию о количестве разрядов для сдвига вправо (r) и влево () соответственно. На вход модуля вычисления сдвигов 17 поступает значение у с выхода третьего модуля логического сдвига вправо 14, на первый вход которого поступает текущее состояние генератора s_i, с выхода первого параллельного регистра 4, а на второй вход - величина сдвига с₆ с выхода шестого узла формирования констант 15. Таким образом,

Значения сдвигов вправо и влево в модуле 17 вычисляются из у следующим образом:

Логическая схема поразрядного ИЛИ 22, к входам которой подключены выходы пятого модуля логического сдвига вправо 20 и модуля логического сдвига влево 21, вычисляет двоичный n-разрядный код:

где «v» - оператор дизъюнкции, а оператор в (6) по аналогии с синтаксисом языка программирования С для чисел в формате представления без знака означает логический сдвиг числа w влево на разрядов.

Значение q с выхода логической схемы поразрядного ИЛИ 22 подается на вход данных второго параллельного регистра 23, выход которого и является выходом устройства.

Тактовые импульсы на тактовые входы первого 4 и второго 23 параллельных регистров поступают с синхронизатора 5.

Предполагается, что разрядность генерируемых заявляемым устройством случайных чисел n=32.

Сравним работу устройства с прототипом. Пусть входное значение параметра z=0, значения констант на выходах первого, второго, третьего, четвертого, пятого, шестого и седьмого узлов формирования констант соответственно равны:

с₁=14057B7EF767814F₍₁₆₎,

c₂=5851F42D4C957F2D₍₁₆₎,

с₃=64,

с₄=14057B7EF767814F₍₁₆₎,

c₅=18,

с₆=59,

с₇=27.

Для компактности записи значения 2n-разрядных констант с_1, с₂ и с₄ приведены в 16-ричном коде.

Поскольку в описании прототипа рассмотрен генератор 16-разрядных чисел в формате со знаком, для сравнения с ним заявляемого генератора с n=32 будем использовать, например, только старшие 16 бит генерируемых кодов, также в формате со знаком.

По аналогии с описанием прототипа сгенерируем выборку длиной N=1000000 элементов. Вычислим для нее энтропию Шеннона и автокорреляционную функцию для сдвигов m=1,2, …, 100000.

Вычисленная по реализации длиной N отсчетов энтропия Шеннона составляет H=15,951738, т.е. близка к максимально теоретически возможной энтропии для идеальной выборки 16-разрядных чисел с равномерным законом распределения, равной Н_mах=16.

Показатель минимальной информационной энтропии

сопоставим по своей величине с аналогичным показателем прототипа (0,996).

Модули значений автокорреляционной функции R(m) приведены на фиг. 2. Максимальный но модулю отсчет автокорреляционной функции имеет значение R_max=0,004095, т.е. близок к нулевому значению коэффициента корреляции (для идеального генератора).

На фиг. 3 для двух различных ансамблей случайных чисел с z₁=0 и z₂=1 и на фиг. 4 - для трех различных ансамблей с z₁=0, z₂=1 и z₃=2 - графически показано, что при различных параметрах z отсутствует корреляция отсчетов между генерируемыми ансамблями.

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

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