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

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

Известен генератор случайной последовательности [1], содержащий источник случайных чисел, N-разрядный селектор-мультиплексор, оперативное запоминающее устройство, блок контроля интервалов, блок контроля количества генераций, J-входовый элемент ИЛИ, блок элементов И.

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

Известен генератор случайной последовательности [2], содержащий селектор-мультиплексор, оперативное запоминающее устройство, источник случайных чисел, К Р-разрядных регистров, К блоков сравнения, шифратор приоритетов, N инверторов.

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

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

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

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

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

Структурная схема предлагаемого устройства представлена на Фиг. 1 и включает в себя генератор псевдослучайных двоичных чисел 1, демультиплексор 2, первый дешифратор 3, первый блок памяти 4, регистр памяти со сдвигом влево 5, второй дешифратор 6, второй блок памяти 7, блок вычисления переходных вероятностей 8, третий блок памяти 9, мультиплексор 10, устройство сравнения 11, первый управляющий вход 12, второй управляющий вход 13, информационный вход 14, информационный выход 15.

Блок вычисления переходных вероятностей 8 предназначен для вычисления переходных вероятностей по формулам (9-15), приведенных ниже, и может быть реализован с использованием программируемых логических интегральных схем.

Устройство сравнения 11 предназначено для сравнения двух десятичных дробей, в результате которого на выход поступает 0, если пороговое значение, подаваемое на первый вход устройства, больше значения подаваемого на его второй вход, в противном случае - 1.

Первый дешифратор 3 и второй дешифратор 6 интерпретируют двоичную последовательность как двоичное число, меньшее 1, и преобразуют в десятичную дробь.

В статическом виде элементы предлагаемого устройства взаимосвязаны следующим образом (см. Фиг. 1): первый управляющий вход 12, являющийся управляющим входом устройства, подключен ко второму управляющему входу демультиплексора 2, первый информационный вход которого подключен к выходу генератора псевдослучайных двоичных чисел 1, а третий выход подключен к входу первого дешифратора 3, выход которого подключен к первому информационному входу первого блока памяти 4, второй вход которого является вторым управляющим входом устройства 13, второй выход демультиплексора 2 подключен ко второму информационному входу регистра памяти со сдвигом влево 5, третий управляющий вход которого является вторым управляющим входом устройства 13, первый выход демультиплексора 2 подключен к входу второго дешифратора 6, выход которого подключен к первому входу устройства сравнения 11, вход второго блока памяти является информационным входом устройства 14, а выход подключен ко второму входу блока вычисления переходных вероятностей 8, первый вход которого подключен к выходу первого блока памяти 4, а 2^n-1 выходов подключены соответственно к 2^n-1 входам третьего блока памяти 9, 2^n-1 выходов которого подключены соответственно ко вторым 2^n-1 информационным входам мультиплексора 10, первый управляющий вход которого подключен к выходу регистра памяти со сдвигом влево 5, а выход подключен ко второму входу устройства сравнения 11, выход которого подключен к первому информационному входу регистра памяти со сдвигом влево 5 и является информационным выходом 15 устройства.

Рассмотрим порядок вычисления вероятностных характеристик перехода в 0 или 1 из двоичных последовательностей длины n-1.

Двоичная последовательность длины n-1 представляет собой кортеж длины n - 1:

где х_i ∈{0,1}, i=1,2,…,n-1.

Множество кортежей (1) обозначим как А_n-1 ⋅ А_n-1 конечно и ограничено количеством всевозможных сочетаний значений элементов кортежа X_i ∈ {0,1}. Следовательно мощность А_n-1 принимает следующее значение:

А_n-1 является упорядоченным множеством, где каждый кортеж может быть интерпретирован как двоичное n-1 - разрядное число:

Для проведения дальнейших преобразований для А_n-1 вводится индексное множество:

где

Индексация элементов множества А_n-1 элементами множества J является биективным отображением и выполняется путем сопоставления интерпретированному двоичным числом кортежу X_j элемента из множества J:

где j ∈ {0,1,…,2^n-1-1}.

Пример для множества кортежей длины 3:

|000|₂ → 0, |001|₂ → 1, |010|₂ → 2, |011|₂ → 3,

|100|₂ → 4, |101|₂ → 5, |110|₂ → 6, |111|₂ → 7.

Переход в состояние 0 или 1 из п - 1 предыдущих значений представляет собой кортеж длины n, полученный путем конкатенации кортежа (х_х,х₂,…,х_n-1) из множества А_n-1 с элементом х_n ∈ {0,1}.

С учетом (2) множество полученных кортежей А_п имеет мощность:

и с учетом (4, 5) А_n индексируется множеством f'с мощностью card(J')=2ⁿ.

Множество А_n включает два непересекающихся подмножества, где первое подмножество А⁰_n-1 образуется путем конкатенации элементов из А_n-1 и х_n=0:

второе подмножество А¹_n-1 образуется путем конкатенации элементов из А_n-1 и x_n=1^:

При этом мощности множеств А⁰_n-1 и А¹_n-1 равны и принимают значение:

Отображение каждого кортежа из А_n-1 в кортежи (6) или (7) множества А_n определяют абсолютные вероятности, которая рассчитывается по следующим правилам:

1. Абсолютные вероятности перехода из кортежей длины n-1 в n имеют следующие зависимости:

где i=1,2,… n-1, j=0,1,2,…,2ⁱ-1.

Пример j=0,1, 2, 3:

для j=0:

для j=1:

для j=2:

для j=3:

2. Из зависимости (8) для каждого кортежа длины / существует распределение абсолютных вероятностей получаемых кортежей длины /+1:

где k=0,1,…,2^i-1 -1.

3. Из системы (9) для Р_мi+1,2k определяется минимальное и максимальное значение:

Если P_i,k - P_i,2k <0 или P_i,2k - P_i,k+2^i-1 < 0, то min(P_i+1,2k) = 0

4. Диапазон допустимых значений определяется по следующей формуле:

5. Значения Р_i+1,2k определяется из выражения:

где g_i+,k - случайная величина на интервале [0,1]. Для n=1 g - не существует.

6. Абсолютные вероятности Р_i+1,2k+1, P_i+1,2k+2ⁱ вычисляются из (9) с учетом значения Р_i+1,2k, полученного из (13):

7. Вычисление переходных вероятностей кортежа длины n-1:

где k=0,1,…,2^n-1-1 и интерпретируется как кортеж (6, 7).

Пример для n=3:

Для n=1:

вероятности задаются: Р(0)=0,6, Р(1)=0,4:

Для n=2, k=0, i=1, i+1=2:

из (9) получим:

Р(0)=Р(00)+Р(01),

Р(0)=Р(00)+Р(10);

Р(1)=Р(01)+Р(11),

Р(1)=Р(10)+Р(11).

Из (10) вычислим максимум для Р(00):

mах(P)00))=min(P0),Р(1))=min(0,4;0,6)=0,4.

Из (11) вычислим минимум для Р(00):

min(P(00))=mах(Р(0) - Р(1), Р(0) - Р(1))=mах(0,6 - 0,4;0,6 - 0,4)=0,2.

Из (12) вычислим диапазон допустимых значений:

I(Р(00))=max(P(00)) - min(P(00))=0,4 - 0,2=0,2

Из (13) вычислим значение Р(00), где случайная величина g_2,0=0,5:

Р(00)=I(P(00))g_2,0+min(Р(00))=0,2 ⋅ 0,5+0,2=0,3.

Из (14) вычислим Р(01), Р(10), Р(11):

Р(01)=Р(0) - Р(00)=0,6 - 0,3=0,3,

P(10)=Р(0) - Р(00)=0,6 - 0,3=0,3,

Р(11)=Р(1) - Р(01)=0,4 - 0,3=0,1.

Для n=3, k=0,1; i=2, i+1=3:

для k=0:

из (9) получим:

Р(00)=Р(000)+Р(001),

Р(00)=Р(000)+Р(100);

Р(01)=Р(001)+Р(101),

Р(10)=Р(100)+Р(101).

Из (10) вычислим максимум для Р(000):

max(P(000))=min(P(00), P(00))=min(0,3;0,3)=0,3.

Из (11) вычислим минимум для Р(000):

min(P(000))=mах(Р(00) - Р(01), Р(00) - Р(10))=mах(0,3 - 0,3;0,3 - 0,3)=0.

Из (12) вычислим диапазон допустимых значений:

I(Р(000))=max(P(000)) - min(P(000))=0,3 - 0=0,3

Из (13) вычислим значение Р(000), где случайная величина g_3,0=0,4:

Р(000)=I(P(000))g_3,0+min(P(000))=0,3 ⋅ 0,4+0=0,12.

Из (14) вычислим Р(001), Р(100), Р(101):

Р(001)=Р(00) - Р(000)=0,3 - 0,12=0,18,

Р(100)=Р(00) - Р(000)=0,3 - 0,12=0,18,

Р(101)=Р(01) - Р(001)=0,3 - 0,18=0,12.

для k=1:

из (9) получим:

Р(01)=Р(010)+Р(101),

Р(00)=Р(010)+Р(110);

Р(11)=Р(011)+Р(111),

Р(11)=Р(110)+Р(111).

Из (10) вычислим максимум для Р(010):

mах(Р(010))=min(P(01), P(10))=min(0,3;0,3)=0,3.

Из (11) вычислим минимум для Р(000):

min(P(010))=max(P(01) - P(l 1), P(10) - P(11))=max(0,3 - 0,1;0,3 - 0,1)=0,2.

Из (12) вычислим диапазон допустимых значений:

I(Р(010))=max(P(010)) - min(P(010))=0,3 - 0,2=0,1

Из (13) вычислим значение Р(010), где случайная величина g_3,1=0,6:

Р(010)=I(P(010))g_3,1+min(P(010))=0,1 ⋅ 0,6+0,2=0,26.

Из (14) вычислим Р(001), Р(100), Р(101):

Р(011)=Р(01) - Р(010)=0,3 - 0,26=0,04,

Р(110)=Р(10) - Р(010)=0,3 - 0,26=0,04,

Р(111)=Р(11) - Р(011)=0,1 - 0,04=0,06.

Для наглядности значения абсолютных вероятностей, полученных для n - 1, 2, 3 систематизируем в таблице 1.

7. Вычисление переходных вероятностей (15) для кортежей длины 2 в 0:

Функционирование предлагаемого устройства осуществляется в два этапа. Этап 1 - предварительные вычисления набора данных для генерации последовательности. Этап 2 - генерация последовательности.

На этапе 1 с управляющего входа 12 устройства на второй управляющий вход демультиплексора 2 подается сигнал «0», включающий коммутацию его первого информационного входа с третьим выходом, при этом с генератора псевдослучайных двоичных чисел 1 подается 2^n-1-1 последовательностей длины n бит, на первый информационный вход демультиплексора 2, далее поступают через его третий выход на вход первого дешифратора 3. В дешифраторе 3 2^n-1-1 последовательностей длины n бит преобразуются в десятичные дроби, которые соответствуют значениям случайных величин (13). Со второго управляющего входа 13 устройства на второй управляющий вход первого блока памяти 4 подается сигнал «0», включающий режим «записи/выдачи данных», также подается сигнал «0» на третий управляющий вход регистра памяти со сдвигом влево 5, включающий режим «начального заполнения данных» только со второго его информационного входа. Далее с выхода первого дешифратора 3 2^n-1-1 значений случайных величин поступают на первый блок памяти 4. Из блока памяти 4 2^n-1-1 значений случайных величин поступают на первый информационный вход блока вычисления переходных вероятностей 8. Далее с информационного входа 14 устройства поступают на вход второго блока памяти 7 значения абсолютных вероятностей Р(0) и Р(1), которые подаются с выхода блока памяти 7 на первый информационный вход блока вычисления переходных вероятностей 8. Далее в блоке вычисления переходных вероятностей 8 вычисляются 2^n-1 переходных вероятностей в 0, которые передаются с 2^n-1 выходов блока вычисления переходных вероятностей 8 на 2^n-1 входов третьего блока памяти 9, в котором осуществляется запись 2^n-1 переходных вероятностей. Далее с управляющего входа 12 устройства на второй управляющий вход демультиплексора 2 подается сигнал «1», включающий коммутацию его первого информационного входа со вторым выходом, при этом с генератора псевдослучайных двоичных чисел 1 подается последовательность длины n-1 бит, которая далее со второго выхода демультиплексора 2 поступает на второй информационный вход регистра памяти со сдвигом влево 5, в котором осуществляется запись последовательности длины n-1. Далее с управляющего входа 13 устройства на второй управляющий вход первого блока памяти 4 подается сигнал «1», включающий режим «блокировки записи/ выдачи данных», также подается сигнал «1» на третий управляющий вход регистра памяти со сдвигом влево 5, включающий режим «побитовой записи данных со сдвигом влево» только с его первого информационного входа.

На этапе 2 в момент начала работы с управляющего входа 12 устройства на второй управляющий вход демультиплексора 2 подается сигнал «2», включающий коммутацию его первого информационного входа с первым выходом, при этом значение регистра памяти со сдвигом влево 5 определяет номер коммутируемого входа мультиплексора 10, т.е. определяет значение переходной вероятности в 0 для текущего значения двоичной последовательности, записанной в регистр памяти со сдвигом влево 5. Далее на первом шаге генерации последовательности с генератора псевдослучайных двоичных чисел передается последовательность длины п, которая поступает с первого выхода демультиплексора 2 на второй дешифратор 6, где преобразуется в десятичную дробь, далее значение поступает на первый информационный вход устройства сравнения 11, при этом на первый информационный вход устройства сравнения 11 поступает пороговое значение (значение переходной вероятности в 0), далее на выходе устройства сравнения формируется значение 0, если значение на первом информационном входе меньше значения на втором информационном входе, и «1» в противном случае. Далее результат сравнения поступает на информационный выход 15 устройства и поступает на первый информационный вход регистра памяти со сдвигом влево. Генерация второго и последующих бит последовательности выполняется аналогично.

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

Предложенное устройство может быть реализовано с использованием современной элементной базы программируемых логических интегральных схем фирм Altera и Xilinx.

Литература

1. RU 2250489, 2005.

2. RU 2313125, 2007.

3. RU 2542903, 2015.

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

N-связный Марковский генератор псевдослучайной двоичной последовательности, включающий генератор псевдослучайных двоичных чисел, регистр памяти со сдвигом влево, мультиплексор, устройство сравнения, отличающийся тем, что введены демультиплексор, первый дешифратор, первый блок памяти, второй дешифратор, второй блок памяти, блок вычисления переходных вероятностей, третий блок памяти, причем выход генератора псевдослучайных двоичных чисел подключен к первому информационному входу демультиплексора, второй управляющий вход которого является первым управляющим входом устройства, а третий выход подключен к входу демультиплексора, выход которого подключен к первому информационному входу первого блока памяти, второй вход которого является вторым управляющим входом устройства, второй выход демультиплексора подключен к второму информационному входу регистра памяти со сдвигом влево, третий управляющий вход которого является вторым управляющим входом устройства, первый выход демультиплексора подключен к входу второго дешифратора, выход которого подключен к первому входу устройства сравнения, вход второго блока памяти является информационным входом устройства, а выход подключен к второму входу блока вычисления переходных вероятностей, первый вход которого подключен к выходу первого блока памяти, а 2^n-1 выходов подключены соответственно к 2^n-1 входам третьего блока памяти, 2^n-1 выходов которого подключены соответственно к вторым 2^n-1 информационным входам мультиплексора, первый управляющий вход которого подключен к выходу регистра памяти со сдвигом влево, а выход подключен к второму входу устройства сравнения, выход которого подключен к первому информационному входу регистра памяти со сдвигом влево и является выходом устройства.