ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ Российский патент 1998 года по МПК G06F7/58 H03B29/00 

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

Известно много применений случайных чисел, таких, например, как моделирование природных явлений, взятие случайных выборок, принятие независимых решений, испытание алгоритмов программирования для ЭВМ, получение шумоподобных сигналов и т.д. [1].

До середины века случайные числа получали исключительно с помощью физических моделей, таких как радиоактивное излучение, дробовой шум радиоламп, туннельный пробой полупроводникового стабилитрона. В настоящее время физические модели случайных чисел практически не используются. Это объясняется тем, что для ряда практических применений требуется не только случайный характер битовой последовательности, но и дополнительные свойства.

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

В 60-х годах развитие компьютерной техники привело к интенсивной разработке математических алгоритмов для генерации псевдослучайных последовательностей, повторяющихся через определенное число элементов. Эта работа оказалась плодотворной и успешно продолжается в настоящее время. Однако совместить требования неограниченной длины последовательности и возможности генерации ее копии математическими методами невозможно - алгоритмические последовательности потенциально ограничены и, следовательно, периодичны. Алгоритмичность набора последовательности обеспечивает возможность ее воспроизведения на ЭВМ.

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

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

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

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

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

Известно, что такие сигналы можно генерировать с помощью двухконтурных (двухчастотных) параметрических генераторов, работающих в невырожденном режиме [3]. Эти устройства исследовались в 60-е годы. В недовозбужденном состоянии они применяются в качестве параметрических усилителей и преобразователей частоты, в стационарном состоянии они используются для диапазонной стабилизации частоты.

В невырожденном режиме отношение частот ω₁/ω₂ параметрических колебаний, генерируемых двухконтурным генератором, иррационально, сумма этих частот равна частоте генератора накачки ω₁+ω₂= ω_н, а сумма фаз колебаний равна фазе накачки ϕ₁+ϕ₂= ϕ_н; сами же фазы являются антикоррелированными функциями времени и при ϕ_н= 0,ϕ₁(t) = -ϕ₂(t), а разность фаз Δϕ(t) = ϕ₁(t)-ϕ₂(t) является почти-периодической функцией.

Действительно, согласно теории почти-периодических функций [4]) в результате взаимодействия между чисто периодическими функциями с несоизмеримыми частотами образуется почти-периодическая функция f(x). Одним из основных свойств такой функции является то, что любые рациональные преобразования ее тоже приводят к почти-периодической функции. Поэтому ее автокорреляционная функция также является почти-периодической.

В отличие от чисто периодических функций, у которых границы периодов отмечаются на числовой оси точками, границы "почти-периодов" почти-периодических функций отмечаются на числовой оси интервалами. Длина этих интервалов, а также плотность их распределения и, следовательно, длина почти-периодов τ(ε), зависят от выбираемой точности (ε>0) совпадения повторяющихся значений почти-периодической функции:
Если к почти-периодической функции применить нелинейную операцию ограничения, то по мере углубления ограничения диапазон возможных значений функции уменьшаться, а длина почти-периодов τ(ε) возрастает. В пределе при идеальном ограничении плотность распределения почти-периодов неограниченно убывает, что уже не соответствует определению почти-периодичности функции. Иначе говоря, идеальное ограничение переводит почти-периодическую функцию f(x) в класс непериодических функций вида sign[f(x)].

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

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

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

Согласно современным представлениям невырожденный параметрический генератор является консервативной хаотической системой, в которой состояние хаоса не менее устойчиво, чем автосинхронизация колебаний в вырожденном режиме. В такой системе нет условий для синхронизации энергообмена между слабо связанными резонаторами, настроенными на несоизмеримые частоты. Устойчивым является только энергообмен между генератором накачки и системой резонаторов в целом. При этом энергетический баланс резонаторов непрерывно и антикоррелированно меняется во времени и никогда не повторяется, как периодическое явление.

В классификации хаотических явлений этот режим называется стохастическим синхронизмом. Физически непериодичность хаотического движения обусловлена нестабильностью параметров резонаторов, какой бы малой она ни была. Корпускулярныые свойства электрона не предоставляют физической возможности настроить резонаторы на частоты, отношения которых соответствовало бы одному единственному иррациональному числу. Математическим эквивалентом этой нестабильности является неопределенность "задания" иррациональных чисел на их бесконечном множестве (см., например, [7]. Такой механизм возникновения хаоса объясняет возможность его моделирования в детерминированных системах.

Для генерации сигналов радиодиапазона удобны невырожденные двухконтурные емкостные параметрические генераторы в балансном исполнении [2]. Дальнейшие преобразования сигналов удобно проводить с помощью цифровых схем [8]: ограничение - в компараторах, сложение по модулю два - на логическом элементе типа ИСКЛЮЧАЮЩЕЕ ИЛИ, дискретные выборки нулей и единиц - также на логическом элементе ИСКЛЮЧАЮЩЕЕ ИЛИ. Для ограничения длины серий нулей и единиц тактовая частота выборок не должна превышать разностную частоту сравниваемых сигналов, или частоту биений между соответствующими им неограниченными параметрическими колебаниями.

С помощью одного параметрического генератора можно получить только одну битовую последовательность. Для синхронной генерации ее копии необходим второй аналогичный генератор, работающий с той же частотой накачки, что и первый, а также вторая пара элементов ИСКЛЮЧАЮЩЕЕ ИЛИ; при этом тактовые частоты логических элементов, формирующих выборки нулей и единиц, должны быть одинаковыми и синхронизированными.

Два параметрических генератора дают две пары стабильных радиосигналов с несоизмеримыми частотами, у каждой из которых суммы фаз равны фазе общей накачки. Для генерации двух одинаковых последовательностей используются парные комбинации сигналов разных генераторов, имеющие коррелированные разности фаз. После глубокого ограничения в компараторах каждая пара сигналов складывается по модулю два последовательно в соответствующих элементах ИСКЛЮЧАЮЩЕЕ ИЛИ с синхронной тактовой частотой, создаваемой делением частоты накачки.

В такой схеме на выходах логических элементов формируются два когерентных случайных битовых потока. При этом генераторы и логические элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, а следовательно, и генерируемые ими потоки нулей и единиц могут быть пространственно разнесены и связаны в общую систему с помощью односторонней связи на частоте накачки и двухсторонней связи на неперекрывающихся частотах основных параметрических колебаний. В этом случае в элементах ИСКЛЮЧАЮЩЕЕ ИЛИ принимаемые сигналы складываются с сигналами местных генераторов. Корреляцией битовых потоков можно управлять с помощью задержки сигналов местных генераторов относительно принимаемых сигналов на время их распространения по каналу связи. Общую тактовую частоту можно создавать делением частоты накачки, связывающей систему.

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

Рассмотренный принцип генерации двух когерентных случайных битовых потоков можно реализовать в широком частотном диапазоне радиоволн от НЧ до СВЧ. Тактовую частоту следования элементов можно изменять в широких пределах от разностной частоты основных параметрических колебаний до однократных случайных выборок нулей и единиц.

Работа заявляемого комбинационного генератора случайных чисел с двумя невырожденными двухконтурными параметрическими генераторами была проверена экспериментально на частотах радиодиапазона. Частота накачки была равна 3 МГц, основные частоты генерации - около 0,97... и 2,3... МГц. При измерениях делались выборки длиной 8192 бита для различных тактовых частот 1, 10 и 25 кГц. Для обработки данных на ПЭВМ использовался стандартный пакет программ STATISTICA for Windows, release 4.3 фирмы Stat Soft Inc.

При экспериментальной проверке работы комбинационного генератора случайных чисел зарегистрирован следующий положительный эффект. Генерируемые битовые потоки дельта-коррелированы, не содержат длинных серий (трендов). Максимальное значение коэффициента взаимной корреляции битовых потоков составляло 0,95±0,02.

На чертеже показана блок-схема заявляемого генератора случайных чисел, содержащая один общий генератор накачки (1), два двухконтурных параметрических генератора (2, 3), четыре компаратора (4, 5, 6, 7), две управляемые цифровые линии задержки (8, 9), два логических элемента (10, 11) и один общий делитель частоты накачки (12). Каждый логический элемент 10 и 11 представляет собой стробируемый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и имеет в этом случае два сигнальных входа для сложения по модулю два выходных сигналов компараторов, один управляющий вход для управления тактовой частотой выборок результата сложения выходных сигналов компараторов и один выход, являющийся одним из двух симметричных выходов генератора случайных чисел.

Схема работает следующим образом. Генератор напряжения накачки 1 непрерывно возбуждает двухконтурные параметрические генераторы 2 и 3 в невырожденном режиме, т.е. с настройкой контуров на некратные частоты, сумма которых равна частоте накачки. Параметрические колебания генераторов преобразуются на выходе компараторов 4, 5, 6, и 7 в меандры, имеющие логические уровни напряжения 0 и 1. Выходные сигналы компараторов, принадлежащие разным параметрическим генераторам (2 и 3), складываются попарно по модулю два в логических элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 10 и 11 с тактовой частотой, создаваемой в делителе частоты накачки 12. На выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (10 и 11), которые являются симметричными выходами генератора случайных чисел, формируются когерентные дельта-коррелированные последовательности импульсов - нулей и единиц. Когерентность последовательностей (коэффициент их взаимной корреляции) управляется с помощью цифровых линий задержки 8 и 9.

Работа выполнена в лаборатории оптимальных методов радиоприема кафедры радиофизики физического факультета МГУ им. М.В.Ломоносова.

Список литературы
1. Кнут Д. Искусство программирования для ЭВМ. - М.: Мир, 1977 г., т. 2, с. 13.

2. Комолов В.П., Трофименко И.Т. Квантование фазы при обнаружении радиосигналов. - М.: Сов. Радио, 1976 г., с. 149.

3. Каплан А. Е., Кравцов Ю.А., Рылов В.А. Параметрические генераторы и делители частоты. - М.: Сов. Радио, 1966 г., с. 163-164.

4. Левитан Б.М. Почти-периодические функции. - М.: Гос.тех.- теор.издат, 1953 г.

5. Левин Б. Р. Теоретические основы статистической радиотехники. - М.: Сов.радио, 1966 г.

6. ТИИЭР, т. 75, N 8, август 1987 г.

7. Шустер Г. Детерминированный хаос. М.: Мир, 1988 г.

8. Шило В.Л. Популярные цифровые микросхемы. - М.: Радио и связь , 1989 г.

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

Генератор случайных чисел, содержащий последовательно соединенные генератор напряжения накачки и делитель частоты накачки, отличающийся тем, что в него введены: два невырожденных двухконтурных параметрических генератора, входы которых подключены параллельно к выходу генератора накачки, четыре компаратора, входы которых подключены раздельно к выходам параметрических генераторов, две управляемые линии задержки, входы которых подключены раздельно к выходам двух компараторов, два стробируемых логических элемента типа ИСКЛЮЧАЮЩЕЕ ИЛИ, сигнальные входы которых подключены раздельно к выходам двух компараторов и выходам двух линий задержки, а управляющие входы подключены параллельно к выходу делителя частоты накачки, выходы логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются выходами генератора случайных чисел.