Исследование генератора случайных чисел, основанного на трехзначной логике — это анализ возможностей генератора случайных чисел, который выполнен на базе случайной логики.
Введение
Проблема увеличения производительности цифрового оборудования считается одной из самых главных задач передовой схемотехники. Используемая сегодня во многих устройствах тактовая частота является очень близкой к предельной, а процесс распараллеливания пригоден далеко не для каждой задачи. В связи с этим внимание специалистов вновь сосредоточено на схемах, которые используют трехзначную логику.
В последние годы были спроектированы элементарные физические устройства, которые реализуют трехзначную логику. Кроме того, известно о разработке технологии, которая позволяет выполнить произвольную комбинационную схему, функционирующую в троичной логике. Физические генераторы случайных последовательностей являются примерами устройств, использование в которых многозначных логик может позволить увеличить их производительность, так как в каждый момент времени формируемый сигнал обладает большей длиной в сравнении с подобной схемой, которая работает в двоичной логике. Такие генераторы могут использоваться для формирования криптографических ключей.
Исследование генератора случайных чисел, основанного на трехзначной логике
В некоторых работах рассматривается цифровой стохастический генератор двоичных последовательностей, который составлен из сумматоров по модулю два с обратными связями. По сути можно исследовать подобные модули, но вместо сумматора использовать блоки, имеющие два входа и один выход, которые реализуют комбинационную схему, функционирующую в трехзначной логике. Пример аналогичного генератора изображен на рисунке ниже.
Рисунок 1. Генератор случайных чисел, основанный на трехзначной логике. Автор24 — интернет-биржа студенческих работ
Тут символом F обозначается блок, использующий трехзначную логику, а сигнал может сниматься с выхода любого блока. При формировании подобных генераторов могут возникнуть следующие проблемы:
- Наличие возможности перехода генератора в стационарное состояние.
- Необходимо доказать независимость сгенерированных символов.
После того как генератор перешел в стационарное состояние, получаемый с его выхода сигнал не изменяется во времени. Можно показать, что при оптимальном выборе блока F генератор может не иметь стационарных состояний.
Касательно независимости символов генерируемой последовательности, то о ней следует сказать только после того, как будет осуществлен выбор математической модели работы отдельных блоков и метод их соединения. Кроме того, потребуется равномерность распределения выходного сигнала на выходе блока. Это требование считается вполне естественным, так как предоставляет возможность преобразования выходного сигнала в сигнал, имеющий произвольное распределение.
Обобщенный подход к исследованию генератора, который составлен из нелинейных блоков, отображен во многих работах известных специалистов, тем не менее использование трехзначной логики может вносить определенные упрощения в представление ситуации. Все блоки должны реализовать определенную функцию:
c = F(a, b), a, b, c G {0,1,2}.
Когда изменяются входные сигналы, то блок должен срабатывать, выполняя функцию F. В отношении срабатывания блоков, необходимо сделать следующие замечания:
- Время срабатывания блока считается случайной величиной с экспоненциальным распределением. Это означает, что вероятность того, что после того, как поступил измененный сигнал на вход блока, время изменения сигнала на выходе меньше T, равняется 1 - exp(-T).
- Срабатывание отдельных блоков могут считаться как независимые события, при этом никакая пара блоков не может срабатывать одновременно.
Введем нумерацию блоков генератора. Состоянием генератора в момент времени t может считаться вектор s(t), элементом которого $s(t)[k]$, k = 1, . . . , N является сигнал на выходе блока, имеющего номер k, в момент времени t. Далее можно использовать векторное обозначение состояния в форме:
S = hs1, s2, ..., sNi.
Когда генератор имеет N блоков, то количество его состояний равняется:
M = 3N.
Подсоединения среди блоков должны задаваться списком Con. Компонент списка:
$ Con[k] = [ik, jk]$,
где ik, jk являются номерами блоков, с выходов которых сигналы должны поступать на вход блока, имеющего номер k. К примеру, структура генератора, который представлен на рисунке выше, может задаваться списком:
$ Con= ([1, 2]; [2, 3]; [3, 1])$.
Установленные ограничения являются аналогичными предположениям, которые накладываются на системы массового обслуживания, и это позволяет описать функционирование генератора при помощи уравнений Эрланга. Воспользуемся системой дифференциальных уравнений Эрланга, которые описывают динамику генератора.
Введем нумерацию всех состояний генератора числами от единицы до M. Пусть sn является состоянием с номером n, а Pn(t) является вероятностью того, что в момент времени t генератор будет находиться в состоянии sn . Введем обозначения через i1, i2, . . ., im всех номеров состояний, своих для каждого n, из которых можно перейти в состояние sn в результате срабатывания лишь одного блока.
Вероятность того, что через момент At генератор может оказаться в состоянии sn, определяется вероятностью того, что генератор мог находиться в данном состоянии прежде и ни один из N блоков не срабатывал, и вероятностью перехода в состояние sn из одного из состояний с номерами i1, i2, . . ., im в результате срабатывания лишь одного блока. В итоге получаем следующее уравнение:
m
-П(-)= -NPn(t) + P Pik(t) dP (t)/ dt. (1)
k=1
Когда выводилось уравнения (1), то не выдвигалось никаких предположений о форме функции F и методе соединения блоков между собой. Как было отмечено выше, следует обеспечить отсутствие стационарных состояний генератора. Сделаем предположение, что функция F может обладать следующим свойством:
c = F (a, b), ∀a, b (c ≠ a, c ≠ b). (2)
Из условия (2) можно сделать вывод, что при срабатывании какого-либо из блоков состояние генератора должно измениться при любом соединении блоков между собой.
