ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Российский патент 1997 года по МПК H03K3/84 H03B29/00 

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

Известен генератор случайной последовательности [1] содержащий блок задержки, сумматор по модулю два, элемент НЕ. Вход элемента НЕ подключен к выходу сумматора по модулю два, а выход элемента НЕ соединен с входом асинхронного блока задержки, выходы которого соединены с входами сумматора по модулю два соответственно.

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

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

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

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

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

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

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

Предложенное техническое решение удовлетворяет критерию "изобретательский уровень", так как введенные отличительные признаки являются существенными и позволяют повысить степень стохастичности устройства, используя в контурах управляемого генератора асинхронных сигналов динамическую обратную связь и суммируя несколько случайных процессов, следовательно, повысить надежность, качество и быстродействие формирования случайной последовательности. Известно, что в основу функционирования управляемого генератора асинхронных сигналов положены три принципа (Кузнецов В.М. Цифровые устройства формирования случайных сигналов с неавтономным источником шума. Дис. на соиск. канд. техн. наук. Казань, 1986. 225 с. [4]):
использование естественных флуктуаций временных параметров цифровых элементов, осуществляющих операцию непрерывной задержки двоичных сигналов;
установление оптимальных соотношений временных параметров исходных компонент формируемого процесса путем аппаратной реализации псевдослучайных алгоритмов в непрерывном времени;
использование эффекта "накопления" дисперсии фазы высокочастотного импульсного сигнала при независимом и достаточно редком обращении к нему.

Первый принцип позволяет осуществить построение устройства исключительно на цифровой элементной базе, что определяет положительный эффект технологического порядка. Реализации второго принципа позволяет преобразовать известный рекуррентный алгоритм формирования псевдослучайных двоичных сигналов (Песошин В.А. Устройства вычислительной техники для генерирования случайных и псевдослучайных последовательностей и чисел. Дис. на соиск. докт. техн. наук. Казань, 1985. 408 с. [5]):

где t дискретное (в тактах) время реализации процесса a ∈0,1} j - дискретное время задержки; c_j e0,1} постоянные коэффициенты; m - порядок последовательности; суммирование проводится по модулю два. Сущность преобразования заключается в замене дискретного времени на непрерывное, т.е.

,
где в отличие от известного алгоритма t и t_i непрерывные величины, а n количество производимых операций непрерывной задержки. Непрерывность времени аппаратной реализации алгоритма и иррациональность в соотношениях задержек, которая неизбежно появляется при переходе в непрерывную область временного аргумента, позволяют трансформировать малые флуктуации задержек цифровых элементов в высокодисперсный результирующий асинхронный процесс. Реализация третьего принципа предполагает работу устройства фиксации случайных двоичных символов из асинхронного процесса a(t). Процесс фиксации должен быть синхронизирован достаточно низкочастотной (по сравнению с 1/t_i) тактовой последовательностью. Наиболее важной характеристикой качества генератора асинхронного случайного сигнала является относительная погрешность (p) равновероятности символа процесса a(t).

δ_p = 2(p-0,5),
где p вероятность появления символа 1. При идеальной работе цифровых элементов p стремиться к 0,5. Однако в реальных условиях на равномерность существенное влияние оказывает свойство нелинейности задержки цифровых элементов, что выражается неравенством t₀ не равно t₁, где t₀ и t₁ соответственно задержка цифровым элементом символа 0 и 1 по выходу. Погрешность в этом случае определяется выражением
δ_p = (t₀-t₁)/(t₀+t₁),
Например, для выполнения операций непрерывной задержки и суммирования по модулю два в составе управляемого генератора асинхронных сигналов могут быть применены микросхемы 555ЛП5, которые имеют t₀=22 нс и t₁=30 нс как предельные паспортные значения. Следовательно δ_p-0,15. В практических случаях при реальных значениях задержек погрешности выражаются несколько меньшими по модулю значениями. В дальнейшем рассматривается модуль этого значения как верхняя оценка погрешности по равновероятности. Очевидно, что оцененная погрешность во многих практических случаях применения является неприемлемой.

Для того, чтобы стохастические перестройки в работе управляемого генератора асинхронных сигналов были более интенсивны, производится настройка структуры на базовую последовательность с характеристическим полиномом F(D), где D оператор задержки t', являющийся мерой измерения всех t_i для сумматоров по модулю два. Для элементов микросхем 555ЛП5 численное значение усредненной реальной задержки составляет t'= 13 нс. Наилучшие результаты в смысле устойчивости стохастического режима дает настройка структуры контура управляемого генератора асинхронных сигналов на (M-1)-последовательность [5] для которой
F(D)=(1+D)F_m(D),
где F_m(D) характеристический полином M-последовательности. Если считать, что F(D)-полином n-го порядка, то F_m(D) имеет порядок n-1. Главным недостатком рассмотренных схем является жесткая фиксированная обратная связь в контуре управляемого генератора асинхронных сигналов, например настройка управляемого генератора асинхронных сигналов на базовый полином (M-1)-последовательности. Это приводит к тому, что в синхронной модели управляемого генератора асинхронных сигналов количество возможных циклов (ансамбль последовательностей) минимально и, самое главное, отсутствуют переходы из одного цикла в другой и обратно. В реальной модели управляемого генератора асинхронных сигналов за счет флуктуаций возможны переходы из одного цикла в другие. Однако уровень флуктуаций порядка 0,0001 [4] относительно средней задержки одного элемента и его фильтрующие свойства дают слабый эффект, поэтому вероятность переходов из одного цикла в другие становится чрезвычайно низкой. Следовательно, вероятность попадания в один из возможных циклов синхронной модели управляемого генератора асинхронных сигналов (в том числе и в примитивный цикл), например, для (M-1)-последовательности остается близкой к 1. Повысить стохастичность генератора асинхронных случайных сигналов (уменьшить вероятность попадания в примитивный цикл) можно двумя способами:
выбором в качестве базового полинома (M-1)-последовательности с большой степенью, чтобы увеличить уровень суммарных флуктуаций контура управляемого генератора асинхронных сигналов, как это предложено, например, в [2]
использованием двух контуров управляемого генератора асинхронных сигналов, каждый из которых жестко настроен на определенный базовый полином, при этом один из контуров является генератором сигналов возбуждения для другого контура, как это предложено в прототипе [3]
Тем не менее в этих случаях по-прежнему сохраняется высокая степень детерминизма, поскольку в синхронной модели генератора ансамбль возможных последовательностей состоит всего из двух циклов.

В данном генераторе случайной последовательности предлагается использовать как минимум три каскада генераторов:
первый каскад ГТИ, как простейший генератор возбуждения второго каскада;
второй каскад управляемого генератора асинхронных сигналов, реализованный на основе базового полинома (M-1)-последовательности, в качестве генератора сигналов возбуждения третьего каскада;
третий каскад управляемого генератора асинхронных сигналов, реализованный на основе базового полинома M-последовательности, как наиболее вероятного среди множества других полиномов, в качестве управляемого генератора с динамической обратной связью.

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

На фиг. 1 представлена схема генератора случайной последовательности, на фиг. 2 представлена схема генератора сигналов возбуждения, на фиг. 3 приведена схема управляемого генератора асинхронных сигналов, на фиг. 4 приведен пример конкретной реализации генератора сигнала возбуждения, на фиг. 5 приведена диаграмма состояний и переходов синхронной модели генератора сигналов возбуждения, на фиг. 6 приведен пример конкретной реализации управляемого генератора асинхронных сигналов, на фиг. 7 приведена таблица структуры последовательностей управляемого генератора асинхронных сигналов, на фиг. 8 приведена диаграмма состояний и переходов синхронной модели управляемого генератора асинхронных сигналов, на фиг. 9 приведен пример конкретной реализации управляемого генератора асинхронных сигналов.

Генератор случайной последовательности содержит генератор сигналов возбуждения 1, сумматор по модулю два 2, триггер 3 и генератор тактовых импульсов 4, выход которого соединен с установочным входом триггера 3, управляемый генератор асинхронных сигналов 5, элемент И 6, выход которого подключен к информационному входу триггера 3, при этом первый вход элемента И 6 соединен с выходом сумматора по модулю два 2, вход генератора сигналов возбуждения 1 соединен с выходом генератора тактовых импульсов 4, первый и второй входы сумматора по модулю два 2 соединены соответственно с выходом управляемого генератора асинхронных сигналов 5 и выходом генератора сигналов возбуждения 1, выходы группы выходов генератора сигналов возбуждения 1 соединены с соответствующими входами группы входов управляемого генератора асинхронных сигналов 5, второй вход 7 элемента И 6 и выход 8 триггера 3 являются соответственно внешним входом управления и выходом генератора случайной последовательности. Генератор сигналов возбуждения 1 (фиг. 2) содержит n последовательно соединенных сумматоров по модулю два 9.1-9.n, где n степень полинома синхронной модели генератора (M-1)-последовательности, выход последнего сумматора два 9. n является выходом 10 генератора сигналов возбуждения 1 и подключен к первому входу первого сумматора по модулю два 9.1 и первым входам некоторых сумматоров по модулю два 9 в соответствии с выбранным полиномом синхронной модели генератора (M-1)-последовательности; и элемент НЕ 11, второй вход первого сумматора по модулю два 9.1 соединен с входом элемента НЕ 11 и является входом 12 генератора сигналов возбуждения 1, выход элемента НЕ 11 подключен к другому входу одного из n сумматоров по модулю два 9, выход n-го сумматора по модулю два 9.n является выходом генератора сигналов возбуждения 1, а выходы K сумматоров по модулю два 9 являются выходами группы выходов генератора сигналов возбуждения 1. Управляемый генератор асинхронных сигналов 5 (фиг. 3) содержит элемент И 13, сумматор по модулю два 14, первый вход которого является первым входом 15.1 группы входов 15.1-15.К, а также содержит К-1 последовательно соединенных управляемых формирователей импульсов 16, где К определено степенью выбранного полинома синхронной модели управляемого генератора асинхронных сигналов, при этом первый вход сумматора по модулю два 14 и вход управления каждого из К-1 управляемых формирователей импульсов 16 являются входами группы входов управляемого генератора асинхронных сигналов 5, выход элемента И 13 соединен с вторым входом сумматора по модулю два 14, выход которого соединен с сигнальным входом первого управляемого формирователя импульсов 16.1, выход (К-1)-го управляемого формирователя импульсов 16.К-1 соединен с первым и вторым входами элемента И 13 и является выходом управляемого генератора асинхронных сигналов. Каждый из К управляемых формирователей импульсов содержит первый элемент И 17, первый вход которого является входом управления 15 управляемого формирователя импульсов 16, сумматор по модулю два 18, второй элемент И 19, первый вход сумматора по модулю два 18 подключен к выходу первого элемента И 17, второй вход которого соединен с выходом сумматора по модулю два 18, выход второго элемента И соединен с вторым входом сумматора по модулю два 18, выход которого является выходом управляемого формирователя импульсов 16, а первый и второй входы второго элемента И 19 объединены и являются сигнальным входом управляемого формирователя импульсов 16.

Генератор сигналов возбуждения 1 (фиг. 4) содержит элемент НЕ 11, группу последовательно соединенных сумматоров по модулю два 9.1-9.4.

Управляемый генератор асинхронных сигналов 5 (фиг. 6) содержит элемент И 13, сумматор по модулю два 14, два управляемых формирователя импульсов 16.1 и 16.2, содержащих элементы И 17, И 19 и сумматор по модулю два 18.

Рассмотрим работу генератора случайной последовательности. При включении напряжения питания генератор тактовых импульсов 4 (фиг. 1) формирует последовательность тактовых импульсов, которые поступают как первичные сигналы возбуждения на генератор сигналов возбуждения 1 по входу 12 (фиг. 2). В генераторе сигналов возбуждения 1 формируется асинхронный случайный процесс, который по выходу 10 поступает на первый вход сумматора по модулю два 2. С выходов 15.1-15. К сигналы генератора сигналов возбуждения 1 поступают на соответствующие входы управляемого генератора асинхронных сигналов 5. В управляемом генераторе асинхронных сигналов 5 в свою очередь формируется высокодисперсный асинхронный случайный процесс за счет динамически изменяющейся обратной связи по сигналам управления с входов 15.2-15.К асинхронного случайного процесса генератора возбуждения 1. По входу 15.1 происходит непосредственное "подмешивание" случайного сигнала с генератора сигналов возбуждения 1 через сумматор по модулю два 14. Это необходимо для того, чтобы получать незатухающий случайный процесс, поскольку для управляемого генератора асинхронных сигналов 5 в качестве базового взят полином M-последовательности, структура которого содержит устойчивое нулевое состояние. Элемент И 13 используется как дополнительная задержка к первому разряду (согласно выбранной единой меры измерения t" синхронной модели управляемого генератора асинхронных сигналов 5). Остальные разряды управляемого генератора асинхронных сигналов 5 представляют собой однородные управляемые формирователи импульсов 16 с одинаковой средней задержкой как единой меры измерения. Управляемые формирователи импульсов 16 могут находиться либо в статическом режиме функционирования, когда на вход подается логическая константа "0" или "1", либо в динамическом режиме, когда на вход поступают сигналы с генератора сигналов возбуждения 1. Количество разрядов управляемого генератора асинхронных сигналов 5 определяет степень выбранного полинома, а распределение статических и динамических сигналов управления определяет в среднем базовый трином M-последовательности, представленный в виде (Лоу, Тан. Генерирование циклической последовательности с помощью динамических и статических триггеров. ТИИЭР, 175, т. 63, N 8. С. 185,186)
f(x)=xⁿ+x^m+1=x^m(x^n-m+1)+1.

С учетом этого трином, описывающий функционирование управляемого генератора асинхронных сигналов (фиг. 3), можно представить в следующем виде:
f(D)=Dⁿ+D^m+1=D(D+1)ⁱ (D+O)^j (D+p)^K+1= D^j+1(D+1)ⁱ(D+p)^K+1,
где D оператор задержки единой меры t", i+j+1 количество стационарных каскадов, к количество динамических каскадов, p сигналы управления. При условии равномерного распределения сигналов управления необходимо выполнение следующих требований:
n i+j+к+1, n-m=i+2к.

Асинхронные случайные процессы с выхода генератора сигналов возбуждения 1 и управляемого генератора асинхронных сигналов 5 суммируются по модулю два в сумматоре с целью улучшения равномерности распределения выходного асинхронного случайного процесса. При подаче внешнего логического сигнала "1" сигнала по входу 7 устройства выходной случайный процесс фиксируется на триггере 3 по тактовому сигналу с ГТИ 4. Выход триггера 3 является выходом 8 генератора случайной последовательности.

В качестве примера реализации генератора сигналов возбуждения 1 из таблицы неприводимых и примитивных полиномов (Питерсон У. Уэлдон Э. Коды, исправляющие ошибки. М. Мир, 1976. 596 с.) выберем восьмиричный набор <13>, для которого справедлива следующая запись:
F_m(D)=1+D+D³.

Тогда
F(D)=1+D²+D³+D⁴,
где D оператор задержки t', t' среднее время задержки сумматоров по модулю два 9. Как видно из записи F(D), количество операторов задержки три - нечетное число, оно же определяет и число контуров обратных связей (фиг. 4). На неиспользуемые входы сумматоров контура подаются тактовые сигналы по входу 12 и с выхода элемента НЕ 11. Последовательно соединенные сумматоры по модулю два 9.1-9.4 с обратной связью реализуют базовый полином F(D), описывающий (M-1)-последовательность. Диаграммы состояний и переходов синхронной модели данной схемы при постоянных значениях сигнала ГТИ ("1" и "0") приведены на фиг. 5. При ГТИ1 формируется либо (M-1)-последовательность 4-го порядка вида
Ц1: 0 1 1 1 1 0 1 1 0 0 0 0 1 0, 0 0
либо примитивная последовательность длиной 2 при начальных состояниях 1110 или 0011 вида
Ц2: 0 1, 0 1, 0 1
Циклическую структуру последовательностей генератора сигналов возбуждения можно описать в виде1(2), 1(14)} т.е. в структуре имеется 1 цикл длиной два и один цикл длиной 14. При ГТИ=0 формируется такая же (M-1)-последовательность, но со сдвигом относительно Ц1 на 5 тактов, т.е. структура типа 1(2), 1(14)}
Ц3: 0 0 0 1 0 0 1 1 1 1 0 1 1 0, 0 0
либо примитивная последовательность длиной 2 при начальных состояниях 0110 или 1011 вида
Ц4: 0 1, 0 1, 0 1
В отличие от аналога [2] и прототипа [1] переходы от примитивного цикла Ц2 к циклу Ц1 (M-1)-последовательности и обратно возможны только за счет флуктуаций временных задержек dt, в данном случае за счет входного сигнала C от ГТИ возможны следующие дополнительные переходы:
из примитивного цикла в цикл (M-1)-последовательности и обратно;
из цикла первой (M-1)-последовательности в цикл второй (M-1)-последовательности;
из одного примитивного цикла в другой и обратно. Характер и последовательность возможных переходов определяется интенсивностью флуктуаций задержек элементов, как следствие, дисперсией фазы асинхронных сигналов и ее относительным сдвигом относительно фазы входного сигнала. В любом случае по сравнению с аналогом [2] время нахождения схемы в примитивных циклах существенно уменьшается, что в целом увеличивает ее стохастичность. Для асинхронной модели генератора рассмотренная диаграмма состояний является лишь одной из многих, наиболее вероятной (базовой) диаграммой.

Рассмотрим пример конкретной реализации управляемого генератора асинхронных сигналов 5 с двумя управляемыми формирователями импульсов (фиг. 6). Мерой измерения для данной схемы выберем интервал времени (t") одного каскада схемы t"= t₁+t_s, где t_i средняя задержка элементов И 13, 17, 19, t_s средняя задержка сумматоров по модулю два 14, 18. Работу управляемого формирователя импульсов 16 можно описать характеристическим уравнением
f(D')=[D' not(v) OR (D'+1)v]D'+v,
где D' оператор задержки t", v=0,1} сигнал управления. Тогда синхронную модель 3-каскадного управляемого генератора асинхронных сигналов 5 можно описать следующим характеристическим уравнением:
F(D') 1+D'(D'+v2)(D'+v3)+v1.

Зафиксируем сигнал v1= 0 и определим структуру последовательностей при различных комбинаций v2 и v3 и соответствующих им характеристических полиномах (таблица 1, фиг. 7).

Как видно из таблицы, структура последовательностей состоит из циклов максимальной (Ц5, Ц6, Ц7), немаксимальной (Ц3, Ц4) длин и примитивных циклов (Ц1, Ц2). С учетом воздействия всех управляющих сигналов v1, v2, v3 построим диаграмму состояний (фиг. 7) для синхронной модели схемы управляемого генератора асинхронных сигналов (фиг. 8).

На данной диаграмме вершина показывает, в каком из элементарных циклов, определяемых входными сигналами v2, v3, в данный момент времени находится синхронная модель схемы управляемого генератора асинхронных сигналов 5. При v1=0 схема может оставаться в устойчивом состоянии. Если сигнал v1=1, то диаграмма показывает возможные переходы из текущего цикла в другие. Знак "х" указывает, что состояние схемы в данном цикле не зависит от соответствующего сигнала. Анализ диаграммы показывает, что связность вершин почти максимальна, следовательно, многосвязность диаграммы переходов обусловливает повышение непредсказуемости выходной последовательности. При переходе к асинхронной модели это приводит к существенному повышению стохастичности даже при сравнительно невысоком уровне флуктуаций временных задержек, например при работе схемы в условиях низких температур. Поскольку меры измерений синхронной модели генератора сигналов возбуждения 1 (t', фиг. 4) и управляемого генератора асинхронных сигналов 5 (t", фиг. 6) находятся в общем случае в иррациональном соотношении, это приводит к еще более высокой непредсказуемости выходной последовательности. Наконец, суммируя по модулю две случайные последовательности с выхода генератора сигналов возбуждения 1 и управляемого генератора асинхронных сигналов 5, получаем выходную последовательность со статистическими параметрами лучшими, чем параметры исходных последовательностей.

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

Изобретение относится к вычислительной, информационно-измерительной, радиотехнике и может быть использовано в стохастических вычислительных машинах при построении генераторов случайных чисел для ЭВМ в системах криптографической защиты информации. Решаемая техническая задача заключается в повышении надежности, качества и быстродействия формирования случайной последовательности. Генератор случайной последовательности содержит генератор сигналов возбуждения 1, сумматор по модулю два 2, триггер 3, генератор тактовых импульсов 4, управляемый генератор асинхронных сигналов 5, элемент И 6, второй вход 7 элемента И 6, выход 8 триггера 3. Генератор сигналов возбуждения 1 содержит n последовательно соединенных сумматоров по модулю два 9.1-9.n, выход последнего из которых является выходом 10 генератора сигналов возбуждения 1, который имеет вход 12, элемент НЕ 11. Управляемый генератор асинхронных сигналов 5 содержит элемент И 13, сумматор по модулю два 14, первый вход которого является первым входом 15.1 группы входов 15.1-15.К, а также содержит К-1 последовательно соединенных управляемых формирователей импульсов 16, каждый из которых содержит первый элемент И 17, сумматор по модулю два 18 и второй элемент И 19. 3 з.п. ф-лы, 9 ил.

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