Математическая модель генератора случайных чисел на основе трёхзначной логики | ПДМ. 2012. № 2(16).

Математическая модель генератора случайных чисел на основе трёхзначной логики

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

Mathematical model of random generator based on ternary logic.pdf ВведениеУвеличение производительности цифровых устройств является одной из основныхзадач современной схемотехники. Достигнутая тактовая частота уже близка к пре-дельной, распараллеливание пригодно не для любой задачи. В этой связи вниманиеисследователей снова обращается к схемам, использующим трёхзначную логику. В по-следнее время созданы элементарные физические устройства, реализующие указаннуюлогику (см., например, работу [1]), где говорится о разработке технологии, позволяю-щей реализовать произвольную комбинационную схему, работающую в троичной логи-ке. Физические генераторы случайных последовательностей дают примеры устройств,применение в которых k-значных логик позволяет увеличить их производительность,поскольку в любой момент времени снимаемый сигнал имеет большую длину по срав-нению с аналогичной схемой, работающей в двоичной логике. Упомянутые генераторыиспользуются для создания криптографических ключей. В работах [2, 3] рассмотренцифровой стохастический генератор бинарных последовательностей, составленный изсумматоров по модулю 2 с обратными связями. В предлагаемой работе рассматрива-ются аналогичные устройства, только вместо сумматора используются блоки с двумявходами и одним выходом, реализующие комбинационную схему, работающую в трёх-значной логике. Пример подобного генератора представлен на рис. 1. Здесь символом Fобозначен упомянутый блок, а сигнал снимается с выхода любого из блоков.Рис. 1. Пример генератора тернарных последовательностейПри создании указанных генераторов возникают следующие проблемы:1) возможность перехода генератора в стационарное состояние;2) доказательство независимости сгенерированных символов.После перехода генератора в стационарное состояние снимаемый с его выхода сиг-нал не меняется во времени. Ниже показано, что при надлежащем выборе блока Fгенератор не имеет стационарных состояний. Что касается независимости символовгенерируемой последовательности, то о ней можно говорить лишь после того, как бу-дут выбраны математическая модель функционирования отдельных блоков и способих соединения. Кроме того, потребуем равномерности распределения выходного сиг-нала на выходе блока. Это требование является естественным, поскольку появляетсявозможность преобразования выходного сигнала в сигнал с произвольным распреде-лением.1. Математическая модель генератораОбщий подход к исследованию генератора, составленного из нелинейных блоков,представлен в работе [4], однако применение трёхзначной логики вносит некоторыеупрощения в описание ситуации. Каждый из блоков реализует некоторую функциюc = F(a, b), а, b, c Е {0,1, 2}. При изменении входных сигналов блок срабатывает, реа-лизуя функцию F. Относительно срабатывания блоков сделаны следующие предполо-жения:1) время срабатывания блока является случайной величиной с экспоненциальнымраспределением, то есть вероятность того, что после поступления изменённогосигнала на вход блока время изменения сигнала на выходе меньше Т, равна1 - exp(-Т);2) срабатывания отдельных блоков являются независимыми событиями, причёмникакие два блока не могут сработать одновременно.Определение 1. Перенумеруем блоки генератора. Состоянием генератора в мо-мент времени t называется вектор s(t), компонента которого s(t)[k], k = 1 , . . . , N естьсигнал на выходе блока с номером k в момент времени t.В дальнейшем будем пользоваться векторным обозначением состояния в формеs = (Si, S2, . . . , SN).Если генератор содержит N блоков, то число его состояний M = 3N. Соединенияблоков друг с другом задаются списком Con. Элемент списка Con[k] = [ik, jk], гдеifc, jfc - номера блоков, с выходов которых сигналы поступают на вход блока с номе-ром k. Например, структура генератора, представленного на рис. 1, задается спискомCon = ( [ 1 , 2]; [2, 3];[3,1]).Наложенные ограничения аналогичны предположениям, накладываемым на систе-мы массового обслуживания, благодаря чему функционированиегенератора описы-вается уравнениями Эрланга [5]. Выпишем систему дифференциальных уравненийЭрланга, описывающих динамику генератора. Перенумеруем все состояния генера-тора числами от 1 до M. Пусть sn - состояние с номером n, а Pn ( t ) -вероятностьтого, что в момент времени t генератор находится в состоянии sn. Обозначим черезi 1 , i 2 , . . . , im все номера состояний, свои для каждого n, из которых можно попастьв состояние sn в результате срабатывания только одного блока. Вероятность того, чточерез момент At генератор окажется в состоянии sn , складывается из вероятноститого, что генератор находился в этом состоянии прежде и ни один из N блоков несработал, и из вероятностей перейти в состояние sn из одного из состояний с номерамиi1, i 2 , . . . , im в результате срабатывания только одного блока. ИмеемdP (t) m^ = - NPn(t) + Е Pik(t). (1)d t fc=12. Выбор функции F и способа соединения блоковПри выводе уравнения (1) не делалось никаких предположений о виде функции Fи способе соединения блоков между собой. Как отмечалось выше, нужно гарантиро-вать отсутствие стационарных состояний генератора. Предположим, что функция Fобладает следующим свойством:c = F(a,b), Va, b (c = a, c = b). (2)Из условия (2) следует, что при срабатывании любого блока состояние генератораизменится при любом соединении блоков между собой. Таким образом, данное условиеисключает наличие стационарных состояний. Перечислим все функции, обладающиесвойством (2). Значение F(a, b) определено однозначно, если a = b, поэтому F(a,b) == F(b, a). Это означает, что достаточно определить функцию лишь для совпадающихаргументов. Если a - произвольная перестановка чисел 0,1, 2, то функции F(a,b) иa ( F ( a ( a ) , a(b)) будем считать неразличимыми. Отсюда следует, что существуют лишьдве существенно разные функции, обладающие свойством (2):F(0, 0) F(1,1) F(2, 2)Fi 1 2 0F2 1 2 1Изучаемый генератор предназначен для генерации последовательностей, в которыхкаждый из элементов появляется с одной и той же вероятностью. В этой связи далеев качестве функции F будем использовать только Fi.Остановимся на выборе соединения блоков друг с другом. Рассмотрим соединение,определенное списком Con = ([1, 2], [2, 3 ] , . . . , [N - 1, N], [N, 1]). На рис. 1 представленуказанный вид соединения для N = 3. Достоинством указанной схемы является равно-правность всех выходов блоков и одинаковая электрическая нагрузка на выходе каж-дого блока. Далее показано, что схема обладает свойством «забывания» начальногосостояния, поэтому в силу отмеченной симметрии на выходе любого блока при сня-тии сигнала через достаточно большой интервал времени T0 генерируется тернарнаяпоследовательность, в которой каждый символ появляется с одной и той же вероят-ностью.3. Матрица переходов генератораОбозначим через A матрицу размера M х M переходов генератора. Эта матрицасостоит из нулей и единиц, причём A[i, k] = 1 тогда и только тогда, когда при сраба-тывании какого-либо блока генератор переходит из состояния с номером i в состояниес номером k. Изучим особенности матрицы переходов исследуемого генератора. Рас-смотрим произвольное состояниеs = ( s i , . . . , s f c , . . . , S N ) . (3)В силу свойства (2) в результате срабатываниялюбого из N блоков состояние гене-ратора изменится, причем все получившиеся состояния будут разными. Это означает,что каждая строка матрицы A имеет ровно N единиц.У т в е р ж д е н и е 1. Состояния (3), в которых все сигналы равны между собой, приуказанных выборе функции F и способе соединения блоков недостижимы из другихсостояний генератора.Доказательство. Рассмотрим состояние s0 = ( 0 , . . . , 0). Если из некоторого со-стояния si возможен переход в состояние s0 в результате срабатывания одного блока,то все компоненты вектора s1 , кроме одной, равны 0. Легко видеть, что после сра-батывания любого блока, в силу (2), переход в состояние s0 невозможен. Посколькув рассматриваемой схеме все троичные значения равноправны, аналогичные утвер-ждения справедливы для векторов ( 1 , . . . , 1) и ( 2 , . . . , 2). Из доказанного утверждения следует, что столбцы с номерами, отвечающими тремнедостижимым состояниям, являются нулевыми. Удалим из A эти три столбца и тристолбца с теми же номерами и обозначим через A' получившуюся матрицу.Напомним некоторые известные факты из теории матриц.Определение 2 [6]. Матрица B с неотрицательными элементами называетсяразложимой, если существует матрица перестановки P, такая, чтоЭТ D D _ I B1 1 0 PТ B P - , 1 D D B 2 1 B22В противном случае матрица называется неразложимой.Согласно [6, c. 166-168], неотрицательная матрица B неразложима тогда и толькотогда, когда для любой пары индексов i , j существует натуральное число k, такое,что Bк [ i , j ] > 0. Кроме того, наибольшее характеристическое число r неразложимойматрицы является простым корнем характеристического многочлена этой матрицы.Свойства генерируемой последовательности базируются на следующей теореме.Т е о р е м а 1. Матрица A' является неразложимой.Доказательство. Под множеством состояний будем понимать множество всехсостояний генератора, кроме трёх отмеченных недостижимых состояний. Достаточ-но доказать, что из любого состояния можно перейти в любое другое. Пусть s1 == ( 1 , 0 , . . . , 0). Покажем, что из s1 можно перейти в любое другое состояние.После двукратного срабатывания второго блока генератор перейдет в состояние(1,1, 0 , . . . , 0), а затем - в состояние (1, 2, 0 , . . . , 0). Итак, из s1 можно перейти в со-стояние (1, а, 0 , . . . , 0), где а - любой элемент множества L = {0,1, 2}. При срабатыва-нии первого блока переходим из состояния s1 в состояние (2, 0 , 0 , . . . , 0). После этого,как и выше, доказывается, что достигается любое состояние (2, а, 0 , . . . , 0), где а Е L.Предположим, что уже доказана достижимость из состояния si любого состояния ви-да (1, а2, а 3 , . . . , ак, 0 , . . . , 0) или (2, а2, а 3 , . . . , ак, 0 , . . . , 0), где а2, а 2 , . . . , ак - любые эле-менты множества L. Если k < N - 1, то присрабатывании блока с номером k +1 из со-стояния (1, а2, а 3 , . . . , ак, 0, 0 , . . . , 0) переходим в состояние (1, а2, а 3 , . . . , ак, 1, 0 , . . . , 0), азатем - в (1, а2, а 3 , . . . , ак, 2, 0 , . . . , 0). Если k = N - 1, то при срабатывании блока с но-мером N из состояния (1, а2, а 3 , . . . , ак, 0) переходим в состояние (1, а2, а 3 , . . . , ак, 2),а из состояния (2, а 3 , . . . , ак, 0) -в (2, а2, а 3 , . . . , ак, 1). После срабатывания первогоблока переходим в состояние (2, 0 , а 3 , . . . , ак, 0) и после срабатывания блока с номе-ром N - в состояние (2, 0 , а 3 , . . . , а к , 1). Наконец, покажем достижимость состояниявида ( 1 , . . . , 1, b p , . . . , bN - 1 , 1 ) , где bp = 1. Согласно предположению, достижимо состоя-ние (2, 0 , . . . , 0, b p , . . . , b_N- i , 1). После последовательного срабатывания блоков с номе-рами 1, 2 , . . . ,p - 1 получим состояние ( 1 , . . . , 1, b p , . . . , b ^ - 1 , 1 ) , поскольку bp = 0 илиbp = 2. -Теперь покажем, что из любого состояния s можно перейти в состояние s1 . Присрабатывании первого блока происходит переход из состояния ( 0 , а 2 , . . . , а ^ ) в со-стояние (b,a2 , . . . , a N ) , где b =1 или b = 2. Это означает, что можем ограни-читься состояниями, начинающимися с 1 или 2. Из состояния (1, 0, . . . , 0, 1) последвукратного срабатывания блока с номером N получаем состояния (1, 0 , . . . , 0, 2),(1, 0 , . . . , 0,0). Из состояния (2, 0 , . . . , 0, 0) после срабатывания блока с номером N по-лучается состояние (2, 0 , . . . , 0,1), а после срабатывания первого блока- (1, 0 , . . . , 0,1).Из состояния (2, 0, . . . , 0, 2) после срабатывания блока с номером N получается со-стояние (2, 0 , . . . , 0, 0). Это означает, что состояние sx достижимо из состояний вида(1, 0 , . . . , 0, a), (2, 0 , . . . , 0, a) для любых a Е L. Пусть уже доказана достижимость sxиз состояний вида (1, 0 , . . . , 0, b p , . . . , b^) для любых bi Е L. Рассмотрим произволь-ное состояние вида (1, 0 , . . . , 0, bp _ 1, b p , . . . , bN) , bp _ 1 = 0. Возможны следующие наборызначений b p - i , b p : (1,2), (2,1), (2,2), когда после срабатывания блока с номером p - 1получаем 0 в позиции p - 1; (1,1), когда после двукратного срабатывания блока с но-мером p - 1 получаем 0 в позиции p - 1; (2,0), (1,0) -последняя ситуация требует до-полнительного рассмотрения. Рассмотрим состояние (1, 0 , . . . , 0,1,0, b p + i , . . . , b^). Присрабатывании блока с номером p в этой позиции появится 1 или 2, что сводит эту ситу-ацию к предыдущему случаю. Для завершения доказательства достаточно поменятьместами значения 1 и 2. 4. Статистические свойства генерируемой последовательностиВведем обозначение B = AT . Согласно определению матрицы A, каждая строкаматрицы B с номером i содержит 1 в позиции j тогда и только тогда, когда возможенпереход из состояния с номером j в состояние с номером i в результате срабатыванияодного блока. Рассмотрим более подробно систему уравнений (1). Положим p(t) == ( P i ( t ) , . . . , PM (t)). Указанная система может быть переписана в виде^ = (B - N I ) p ( t ) = Dp(t). (4)Решение данной системы имеет видp(t) = exp(Dt)e,где e - произвольный стохастический вектор, определяющий начальное состояние.Матрица B имеет три нулевых строки; пусть это строки с номерами 1, 2, 3. Из (4)следует, чтоPfc(t) = efc exp(-Nt), k Е {1, 2, 3}, (5)где 0 ^ ek ^ 1. Отсюда вытекает, что Pk(t) ^ 0 при t ^ то, k Е {1, 2, 3}. Исключимиз векторов компоненты с индексами 1, 2, 3, а из матриц - строки и столбцы с эти-ми номерами. В результате получим векторы e', p'(t), D' = A'T - N I', а решениесистемы (4) сведется к решению системыp' ( t ) = exp(D' t ) e '.Т е о р е м а 2. Пусть C(t) = exp(Dt). Тогда C(t) ^ C0 при t ^ то, где C0 -мат-рица с одинаковыми столбцами, равными стохастическому вектору d, такому, чтоd = (0, 0, 0, d')T, A'Td' = Nd'.Доказательство. Из (5) вытекает, что первые три строки матрицы C0 нуле-вые. Сумма элементов в каждой строке матрицы A равна N, и при выбранной ну-мерации состояний её первые три столбца нулевые. Таким образом, матрица A ' /Nстохастическая, её максимальное характеристическое число равно 1, все остальныехарактеристические числа имеют модули, не превосходящие 1 (см. [6, с. 200]), а изнеразложимости этой матрицы вытекает, что 1 является простым корнем. Други-ми словами, если .1 , . . . , . м - з - все характеристические числа матрицы A! и .i -максимальный по модулю корень, то .1 = N, ^ N, i > 1. По определениюD' = A/ T - N I' , поэтому для характеристических чисел этой матрицы выполненыусловия = 0, real(^) < 0, i = 2 , . . . , M - 3. Характеристические числа матрицыC/ ( t ) = exp(D/ t ) равны e x p ( ^ t ) , поэтому существует предел C0 = lim C/ ( t ) и матри-t-^^оца C имеет ранг 1. Если A/ Td/ = Nd/ , то D/d/ - нулевой вектор, а из представленияматрицы C/ ( t ) в виде ряда вытекает, что C/ ( t ) d / = d/ для любого t. Это означает,что CQd/ = d/ . Далее, ( 1 , 1 , . . . , 1)A/ T = N ( 1 , 1 , . . . , 1), поэтому ( 1 , 1 , . . . , 1)D/ - нулевойвектор и ( 1 , 1 , . . . , 1)CQ = ( 1 , 1 , . . . , 1), т. е. сумма элементов в каждом столбце этойматрицы равна 1. Вектор d/ задает финальное распределение вероятностей состояний генератора.Из теоремы 2 следует независимость этого распределения от начального состояния, афинальные вероятности появления 0, 1 и 2 на выходе любого блока равны 1/3. Следует,однако, заметить, что отсюда нельзя заключить, что финальные вероятности каждогоиз состояний генератора совпадают между собой.5. Результаты численных экспериментовПри практическом использовании разработанного генератора возникает вопрос оскорости сходимости решения уравнения (4) к финальному вектору в зависимости отчисла N блоков в схеме. В качестве меры близости выбрано среднеквадратическоеотклонение 8 финального вектора - собственного вектора матрицы D, отвечающегособственному значению 0, - от первого столбца матрицы exp(Dt). Результаты экспе-риментов представлены в следующей таблице.Зависимость 8 от N и tN \t 2 4 6 8 102 0,0095249 0,0001857 0,0000034 6,288e-08 1,141e-093 0,0026750 0,0000398 0,0000005 7,596e-09 1,102e-104 0,0014727 0,0000404 0,0000011 3,592e-08 1,113e-095 0,0004785 0,0000077 8,981e-08 9,856e-10 3,056e-116 0,0001991 0,0000055 0,0000002 6,546e-09 2,868e-10Из приведённых результатов следует, что при любом N схема практически забы-вает своё начальное состояние при t ^ 5. Расчёт проведён для параметра экспоненци-ального распределения Л = 1 .ЗаключениеРассмотренный в работе физический генератор, составленный из одинаковых бло-ков, реализующих специальную функцию трёхзначной логики, может использоватьсядля генерации случайных ключей. Генерация возникает за счёт наличия обратныхсвязей и случайности времени срабатывания. Если время срабатывания блока опреде-ляется экспоненциальным распределением, то при одном и том же значении параметрараспределения трёхзначный генератор обеспечивает большую производительность посравнению с бинарной схемой, работающей в том же режиме. Выбранный способ со-единения блоков обеспечивает одинаковую электрическую нагрузку на выходах всехустройств. Использование более чем трёх блоков не уменьшает время «забывания»начального состояния генератора.

Ключевые слова

асинхронный генератор, трёхзначная логика, марковский процесс, asynchronous generator, ternary logic, Markov process

Авторы

ФИООрганизацияДополнительноE-mail
Столов Евгений ЛьвовичКазанский федеральный университетпрофессор, доктор технических наук, профессор кафедры системного анализаyevgeni.stolov@ksu.ru
Всего: 1

Ссылки

Sheng L., Yong-Bin K., and Lombardi F. CNTFET-Based Design of Ternary Logic Gates and Arithmetic Circuits //IEEE Trans. Nanotechnology. 2011. V. 10. No. 2. P. 217-225.
Кузнецов В. М., Песошин В. А., Столов Е. Л. Марковская модель цифрового стохастического генератора //АиТ. 2008. №9. С. 62-68.
Кузнецов В. М., Песошин В. А., Столов Е. Л. Стабильные состояния асинхронного генератора //Учёные записки Казанского государственного университета. 2010. Т. 152. Кн. 1. Сер. Физико-математические науки. С. 174-180.
Столов Е. Л. Генератор случайных чисел, составленный из нелинейных асинхронных элементов // Исследования по прикладной математике. Вып. 26. Казань: Институт информатики КГУ, 2006. С. 101-106.
Хинчин А. Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963. 236 с.
Маркус М., Минк Х. Обзор по теории матриц и матричных неравенств. М.: Наука, 1972. 232 c.
 Математическая модель генератора случайных чисел на основе трёхзначной логики | ПДМ. 2012. № 2(16).

Математическая модель генератора случайных чисел на основе трёхзначной логики | ПДМ. 2012. № 2(16).

Полнотекстовая версия