Генератор случайных чисел на основе трехзначной логики



Генератор случайных чисел на основе трехзначной логики
Генератор случайных чисел на основе трехзначной логики

 


Владельцы патента RU 2495479:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Казанский (Приволжский) Федеральный Университет" (ФГАОУ ВПО "КФУ") (RU)

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

 

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

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

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

Известно устройство [1] для генерации случайных чисел, однако, в нем используется источник элементарных частиц и их приемник, что делает такое устройство очень дорогим.

Известно устройство [2], состоящее из разнородных устройств, содержащее элементы памяти в виде счетчика, что усложняет его изготовление. Известно устройство [3], использующее для генерации случайных чисел аналоговый хаотический генератор. Его недостатком является использование АЦП для перевода аналоговых сигналов в цифровые сигналы.

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

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

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

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

Заявленное техническое решение реализуется посредством устройства, вид которого для случая трех комбинационных схем представлен на Фиг.1.

Подобная схема может быть составлена из любого числа комбинационных схем. Каждая комбинационная схема имеет два входа, один выход и работает в трехзначной логике, реализуя одну и ту же функцию c=F(a,b), a,b,c∈{0,1,2}.

Функция определяется следующим образом: если a≠b, то с≠а&с≠b, тем самым функция определена однозначно, если аргументы не совпадают; если аргументы совпадают, то значения функции определены следующей таблицей.

F(0,0) F(1,1) F(2,2)
F 1 2 0

Данную таблицу можно заменить любой таблицей, полученной из исходной, с помощью преобразования σ(F)=σ(F(σ(a),σ(b)), где σ - любая перестановка из 3 символов. N комбинационных схем соединены в кольцо. Сигнал с выхода каждой схемы поступает на один из входов той же схемы и на вход следующей за ней схемы. Генерируемый сигнал снимается с любого выхода функционального элемента Si. Статистические свойства снимаемого сигнала обосновываются следующим образом. Время срабатывания каждой комбинационной схемы задается экспоненциальным распределением с некоторым параметром λ, одинаковым для всех схем, при этом разные схемы срабатывают независимо друг от друга. Согласно [4], в этом случае поведение генератора описывается марковским процессом с непрерывным временем, состояние которого задается выходами всех комбинационных схем. Предлагаемое соединение функциональных элементов обеспечивает существование единственного финального распределения состояний генератора. В этом финальном распределении каждое достижимое состояние имеет свою вероятность, вообще говоря, отличную от других состояний, однако, появление каждого из сигналов {0,1,2} на выходах функциональных элементов равняется 1/3. Для обеспечения независимости снимаемых сигналов нужно, чтобы время съема превосходило время установления генератора в финальное распределение состояний. Ниже (табл.2) приведены результаты вычисления времени t установления генератора для нескольких значений N числа комбинационных схем при значении параметра экспоненциального распределения λ=1. В качестве критерия близости текущего распределения вероятностей состояний к финальному распределению выбрана величина δ - среднеквадратическое отклонение распределения вероятностей состояний в момент времени t от финального распределения.

N/t 2 3 4 5 6
2 0.0095249 0.0001857 0.0000034 6.288D-08 1.141D-09
3 0.0026750 0.0000398 0.0000005 7.596D-09 1.102D-10
4 0.0014727 0.0000404 0.0000011 3.592D-08 1.113D-09
5 0.0004785 0.0000077 8.981D-08 9.856D-10 3.056D-11
6 0.0001991 0.0000055 0.0000002 6.546D-09 2.868D-10

Из представленной таблицы следует, что при выбранном значении параметра λ установление финального распределения происходит уже при t=5. Отсюда следует, что для произвольного значения λ установление финального состояние происходит через время t0, удовлетворяющее неравенству λt0>5.

Заявленное техническое решение реализовано в виде устройства, составленного из комбинационных схем, соединенных согласно схеме, приведенной на Фиг.1, на Фиг.2 представлена эмуляций комбинационной схемы, работающей в трехзначной логике, булевской комбинационной схемой, в которой парам булевских сигналов сопоставлены сигналы троичной логики согласно правилу (0,0)→0,(0,1)→1, (1,0)→2.

Устройство состоит из N комбинационных схем F. Каждая комбинационная схема F имеет шину питания два информационных входа, один информационный выход и работает в троичной логике согласно приведенному выше описанию. Комбинационные схемы соединены кольцевым образом, при этом выход с каждой схемы поступает на вход этой же схемы и на свободный вход следующей схемы в кольцевом соединении. Состоянием устройства является набор S1,S2,…,SN выходных сигналов всех комбинационных схема. Устройство работает следующим образом: при подаче питания в начальный момент состояние устройства будет произвольным. Поскольку стационарные состояния в устройстве отсутствуют, выход каждой комбинационной схемы изменится, однако, это произойдет в разные моменты времени, поскольку время срабатывания каждой схемы является случайным, и схемы работают независимо. Через моменты времени t0, вычисленные заранее на основе параметра λ, экспоненциального распределения и числа N, снимается сигнал с выхода любой комбинационной схемы. В результате получаем независимые трехзначные случайные величины с равномерным распределением, что повышает производительность устройства в полтора раза по сравнением с аналогом, работающим в двоичной логике.

Устройство подвергнуто тестированию в качестве математической модели, в результате которого получен случайный сигнал, имеющий равномерное распределение в троичной логике, что является доказательством соответствия критерию «промышленная применимость» в лаборатории при Казанском Федеральном университете. Заявленное устройство может быть реализовано на любой стандартной элементной базе, что является доказательством соответствия заявленного технического решения критерию «промышленная применимость» предъявляемого к изобретениям.

Источники информации

1. Патент РФ 2331916.

2. Патент РФ 2281603.

3. Заявка на изобретение РФ 2009104431.

4. Кузнецов В.М., Песошин В.А., Столов Е.Л. Марковская модель цифрового стохастического генератора // Автоматика и телемеханика - 2008 - №9 - С.62-68.

5. Peiman Keshavarzian, Keivan Navi. Universal ternary logic circuit design through carbon nanotube technology // International Journal of Nanotechnology - 2009 - №10-11 - P.942-953.

Генератор случайных чисел на основе трехзначной логики, реализованный в виде кольцевого соединения N одинаковых комбинационных схем, работающих с трехзначной логикой и реализованных с помощью любой технологии, имеющих два входа и один выход, реализующих функцию c=F(a,b) a,b,с∈{0,1,2}, определенную формулой: если а≠b, то c≠a&c≠b; если аргументы совпадают, то значение функции определено таблицей

F(0,0) F(1,1) F(2,2)
F 1 2 0

причем эта функция F может быть заменена новой функцией G, полученной согласно формуле G(a,b)=σ(F(σ(a), σ(b)) с помощью любой перестановки σ из трех чисел, при этом выход каждой комбинационной схемы соединен с одним из входов этой схемы и с одним из входов следующей комбинационной схемы в кольцевом соединении, а случайный сигнал снимается с выхода любой комбинационной схемы.



 

Похожие патенты:

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и электросвязи, предназначено для решения задач защиты компьютерной информации, может использоваться при построении генераторов псевдослучайных чисел, а также криптографических примитивов хеширования, блочного и поточного шифрования. Достигаемый технический результат - повышение криптостойкости и быстродействия нелинейного преобразования. Способ включает представление входных 1 и выходных 2 блоков данных, всех промежуточных результатов S преобразований и раундовых ключей (RoundKeys) 30, 31, 32, 33 в виде кубического массива байтов 4×4×4, определение понятия слоя 4 (Layer) - квадратного массива байтов 4×4, представление i-го раундового ключа в виде четырех подключей (RoundSubKeys) 3i0, 3i1, 3i2, 3i3, i=1, 2, 3, каждый из которых суть квадратный массив байтов 4×4, сложение 10 (XOR) блока 1 данных с раундовым ключом 30, трехмерное преобразование блока данных по слоям 4x0, 4x1, 4х2, 4x3, 4у0, 4у1, 4у2, 4у3, 4z0, 4z1, 4z2, 4z3 соответственно вдоль осей x, у, z, включение в состав операции двухмерного преобразования слоя (T-Layer) 5 четырех шагов: замену 6 байтов (SubBytes), перемешивание 7 строк (MixRows), перемешивание 8 столбцов (MixColumns), сложение (XOR) 9 с раундовым подключом (AddRoundSubKey). 4 ил., 1 табл.

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

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

Изобретение относится к способам создания широкополосных случайных процессов с заданными собственными и взаимными спектральными плотностями мощности и может быть использовано в приборостроении, машиностроении, вычислительной технике для создания, в частности, многоканальных автоматических систем, в испытаниях на вибростойкость к воздействиям случайной вибрации. Техническим результатом является генерирование двух случайных сигналов с заданной функцией когерентности. Способ включает формирование во временной области по заданным спектральным плотностям Sx(f) и Sy(f) стационарных случайных сигналов x(f), y(t) в форме разложения Райса-Пирсона со случайными на каждой гармонике fi фазами Θi и Ωi, определяемыми методом случайной выборки случайной величины, одна из которых - Θi для сигнала x(t) равномерно распределена в диапазоне [-π, π], а другая - Ωi для второго сигнала y(t) определяется как сумма Ωi=Θi+Δφi случайной величины Θi и случайной величины Δφi, равномерно распределенной в диапазоне [-φi, φi], границы которого определяются через взаимную спектральную плотность Sxy(f) случайных сигналов x(t) и y(t). 1 ил.

Изобретение относится к области вычислительной техники и может быть использовано для генерирования широкополосных случайных стационарных сигналов с заданными собственными и взаимными спектральными плотностями мощности. Техническим результатом является генерирование двух случайных сигналов с заданной функцией когерентности. Устройство содержит однопроцессорный компьютер, программное обеспечения для формирования по заданным спектральным плотностям Sx(f) и Sy(f) случайных сигналов в форме разложения Райса-Пирсона со случайными на каждой гармонике fi фазами Θi и Ωi, определяемыми методом случайной выборки случайной величины, одна из которых - Θi для сигнала x(f) равномерно распределена в диапазоне [-π, π], а другая - Ωi для второго сигнала y(t), определяется как сумма Ωi=Θi+Δφi случайной величины Θi и случайной величины Δφi, равномерно распределенной в диапазоне [-φi, φi], границы которого определяются через взаимную спектральную плотность Sxy(f) случайных сигналов x(t) и y(t) с последующим выполнением процедуры ОБПФ, модуля цифро-аналогового преобразователя для перевода сформированных цифровых сигналов в аналоговые сигналы генератора. 1 ил.

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

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

Изобретение относится к вычислительной технике и может быть использовано для генерации потоков псевдослучайных чисел (ПСЧ). Техническим результатом является возможность генерации N начальных значений и отсутствие корреляций при их использовании между не менее N потоками ПСЧ. Устройство содержит генератор получения начального значения и генератор ПСЧ, который содержит устройство вычисления потока ПСЧ, средство вычисления битов ПСЧ из координат единичного квадрата, средство формирования прообраза n-битного ПСЧ из n битов ПСЧ, средство записи в промежуточные регистры, средство сдвига битов регистра, элемент памяти, средство записи ПСЧ в элемент памяти, средство формирования потока ПСЧ из записанных в память ПСЧ, средство передачи потока ПСЧ в вычислительное устройство. 3 н.п. ф-лы, 3 ил.

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

Изобретение относится к вычислительной технике, в частности к генераторам псевдослучайных функций (ПСФ), и может быть использовано в цифровых вычислительных устройствах, а также в системах защиты информации. Техническим результатом является повышение скорости вычисления псевдослучайной функции. Устройство содержит два входа для секретного ключа и входных данных, три регистра, сумматор по модулю p, блок вычисления обратного элемента по модулю p, умножитель по модулю p, блок возведения в степень по модулю p. 1 ил., 1 табл.
Наверх