генератор последовательности случайных чисел

Формула изобретения

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

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

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

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

5. Генератор последовательности случайных чисел по п.4, отличающийся тем, что введены третий и четвертый Т-триггеры, счетные входы которых подключены соответственно к первому и второму выходам генератора тактовых импульсов, а выходы являются соответственно выходами контроля счета и контроля записи генератора.

Описание изобретения к патенту

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

Известны устройства для формирования последовательности случайных чисел [1-5], позволяющие получить случайные равновероятные двоичные числа.

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

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

Датчик случайных чисел с равномерным распределением [1] содержит лишь один источник случайных равновероятных чисел (блок памяти), что обусловливает наличие корреляции между числами формируемой последовательности.

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

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

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

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

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

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

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

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

На фиг.1 показана электрическая структурная схема предлагаемого генератора последовательности случайных чисел по п.1 формулы изобретения, а на фиг. 2 - временные диаграммы, поясняющие его работу. На фиг.3 показана электрическая структурная схема предлагаемого генератора последовательности случайных чисел по п.4 и 5 формулы изобретения. На фиг.4 показана электрическая структурная схема предлагаемого генератора последовательности случайных чисел в частном случае выполнения устройства на ПЛИС фирмы ALTERA. На фиг.5 показана электрическая структурная схема прототипа [5].

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

Генератор последовательности случайных чисел по п.4 формулы изобретения (см. фиг. 3) содержит, кроме указанных выше элементов, третий 16, четвертый 17, пятый 18 D-триггеры и четвертый элемент 19 И, причем выход формирователя 14 импульса сброса подключен к входам установки в нулевое состояние первого 7 и второго 8 Т-триггеров через четвертый элемент 19 И, другой вход которого соединен с выходом пятого D-триггера 18, информационный и тактовый входы которого являются соответственно входами разрешения сброса и управления сбросом устройства, первым и вторым входами разрешения счета которого являются информационные входы соответственно третьего 16 и четвертого 17 D-триггеров, выходы которых подключены к третьим входам соответственно первого и второго элементов И, а тактовые входы соединены с входом управления счетом устройства, вход начального сброса которого подключен к входам установки в нулевое состояние третьего 16, четвертого 17 и пятого 18 D-триггеров.

Генератор последовательности случайных чисел по п.5 формулы изобретения (см. фиг.3) содержит, кроме указанных выше элементов, третий 20 и четвертый 21 Т-триггеры, счетные входы которых подключены соответственно к первому и второму выходам генератора 12 тактовых импульсов, а выходы являются соответственно выходами контроля счета и контроля записи устройства.

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

Шумовые сигналы с выходов первого 1 и второго 2 источников шума подают на входы соответственно первого 3 и второго 4 формирователей импульсов, на выходах которых получают разные последовательности случайных импульсов, которые подают через первый 5 и второй 6 элементы И на счетные входы первого 7 и второго 8 Т-триггеров, работающих в счетном режиме.

Первый 7 и второй 8 Т-триггеры всегда начинают счет из состояния логического "0" и переключаются случайным образом в течение заданного интервала времени - периода счета ТС, после чего полученные на их выходах случайные сигналы записывают в соответственно первый 9 и второй 10 D-триггеры. Затем записанные случайные сигналы с выходов первого 9 и второго 10 D-триггеров подают на входы элемента 11 ИСКЛЮЧАЮЩЕЕ ИЛИ, на выходе которого получают последовательность случайных чисел, которую подают на информационный выход устройства.

Процессами записи сигналов в первый 7 и второй 8 Т-триггеры, а также в первый 9 и второй 10 D-триггеры управляют с помощью генератора 12 тактовых импульсов, который вырабатывает две последовательности импульсов, взаимное расположение которых во времени показано на фиг.2:

- последовательность запрещающих импульсов длительностью Т₃ с периодом следования Т_T на первом выходе (фиг.2а);

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

Запрещающие импульсы (см. фиг.2а) поступают с первого выхода генератора 12 тактовых импульсов на вторые входы первого 5 и второго 6 элементов И и запрещают поступление случайных импульсов с выходов первого 3 и второго 4 формирователей импульсов на счетные входы первого 7 и второго 8 Т-триггеров в течение времени Т₃, что позволяет избежать возникновения метастабильного состояния во время перезаписи информации в первый 9 и второй 10 D-триггеры, осуществляемой по переднему фронту тактовых импульсов (см. фиг.2б), которые подают со второго выхода генератора 12 тактовых импульсов через третий элемент 13 И на тактовые входы первого 9 и второго 10 D-триггеров.

После записи информации в первый 9 и второй 10 D-триггеры с помощью формирователя 14 импульса сброса и формирователя 15 сигнала готовности формируют сигнал (фиг.2в) готовности данных на сигнальном выходе устройства и импульс (фиг. 2г) сброса для установки в нулевое состояние первого 7 и второго 8 Т-триггеров.

Происходит это следующим образом. В исходном состоянии на прямом выходе формирователя 15 сигнала готовности сигнал (см. фиг.2в) готовности данных имеет значение логического "0", что означает неготовность данных на информационном выходе устройства. При этом сигнал (см. фиг.2г) на выходе формирователя 14 импульса сброса имеет значение логической "1".

По заднему фронту тактовых импульсов (см. фиг.2б), которые подают со второго выхода генератора 12 тактовых импульсов на тактовый вход формирователя 14 импульса сброса с периодом ТТ на выходе последнего формируют передний фронт импульса (см. фиг.2г) сброса, который поступает на входы установки в нулевое состояние первого 7 и второго 8 Т-триггеров и на второй вход формирователя 15 сигнала готовности. При этом на прямом выходе последнего сигнал (см. фиг.2в) готовности данных принимает значение логической "1", что означает готовность данных на информационном выходе устройства.

В то же время сигнал, подаваемый с инверсного выхода формирователя 15 сигнала готовности на второй вход третьего элемента 13 И и на управляющий вход формирователя 14 импульса сброса, принимает значение логического "0", в результате чего на выходе формирователя 14 импульса сброса формируют задний фронт импульса (см. фиг.2г) сброса. После этого формирователь 14 импульса сброса не реагирует на поступление на его тактовый вход тактовых импульсов (см. фиг.2б) до тех пор, пока на вход чтения устройства не поступит импульс чтения. В то же время запрещается прохождение тактовых импульсов (см. фиг. 2б) со второго выхода генератора 12 тактовых импульсов через третий элемент 13 И на тактовые входы первого 9 и второго 10 D-триггеров, поэтому до тех пор, пока случайное число не будет считано с информационного выхода устройства с помощью импульса чтения, отсутствует возможность записать следующие значения случайных сигналов в первый 9 и второй 10 D-триггеры.

При поступлении импульса (фиг.2д) чтения с входа чтения устройства на первый вход формирователя 15 сигнала готовности на прямом выходе последнего сигнал (см. фиг.2в) готовности данных принимает значение логического "0". В то же время сигнал, подаваемый с инверсного выхода формирователя 15 сигнала готовности на управляющий вход формирователя 14 импульса сброса, принимает значение логической "1", после чего формирователь 14 импульса сброса и формирователь 15 сигнала готовности находятся в исходном состоянии. Далее цикл работы устройства повторяется.

При введении в состав устройства в соответствии с п.4 формулы изобретения (см. фиг.3) третьего 16, четвертого 17, пятого 18 D-триггеров и четвертого элемента 19 И генератор последовательности случайных чисел работает следующим образом.

В штатном режиме работы на вход разрешения сброса, первый и второй входы разрешения счета (информационные входы пятого 18, третьего 16 и четвертого 17 D-триггеров) и вход начального сброса (входы установки в нулевое состояние третьего 16, четвертого 17 и пятого 18 D-триггеров) устройства подают сигнал, имеющий значение логической "1". Затем на вход управления счетом и вход управления сбросом (тактовые входы третьего 16, четвертого 17 и пятого 18 D-триггеров) устройства подают импульс записи, в результате чего сигналы на выходах третьего 16, четвертого 17 и пятого 18 D-триггеров принимают значение логической "1". Указанные сигналы подают соответственно на третьи входы первого 5 и второго 6 элементов И и на вход четвертого элемента 19 И. В результате этого сигналы на счетные входы и входы установки в нулевое состояние первого 7 и второго 8 Т-триггеров поступают в том же порядке, как это описано выше при рассмотрении работы генератора последовательности случайных чисел по п.1 формулы изобретения. Поэтому в штатном режиме работы генератор последовательности случайных чисел по п.4 формулы изобретения (см. фиг.3) работает так же, как и генератор последовательности случайных чисел по п.1 формулы изобретения (см. фиг.1).

В режиме контроля генератор последовательности случайных чисел по п.4 формулы изобретения (см. фиг.3) обеспечивает такие дополнительные возможности, как раздельный контроль первого 1 и второго 2 источников шума совместно с первым 3 и вторым 4 формирователями импульсов, а также контроль установки первого 7 и второго 8 Т-триггеров в нулевое состояние.

Для раздельного контроля первого 1 и второго 2 источников шума совместно с первым 3 и вторым 4 формирователями импульсов на первый и/или второй входы разрешения счета (информационные входы третьего 16 и четвертого 17 D-триггеров) устройства подают сигнал, имеющий значение логического "0". Затем на вход управления счетом (тактовые входы третьего 16 и четвертого 17 D-триггеров) устройства подают импульс записи, в результате чего сигналы на выходах третьего 16 и/или четвертого 17 D-триггеров принимают значение логического "0". Указанные сигналы подают соответственно на третьи входы первого 5 и второго 6 элементов И, в результате чего запрещают поступление случайных импульсов с выходов первого 3 и второго 4 формирователей импульсов на счетные входы соответственно первого 7 и/или второго 8 Т-триггеров.

Для контроля установки первого 7 и второго 8 Т-триггеров в нулевое состояние на вход разрешения сброса (информационный вход пятого D-триггера 18) устройства подают сигнал, имеющий значение логического "0". Затем на вход управления сбросом (тактовый вход пятого D-триггера 18) устройства подают импульс записи, в результате чего сигнал на выходе пятого D-триггера 18 принимает значение логического "0". Указанный сигнал подают на вход четвертого элемента 19 И, на выходе которого получают сигнал, имеющий значение логического "0". Этот сигнал подают на входы установки в нулевое состояние первого 7 и второго 8 Т-триггеров и тем самым устанавливают их в нулевое состояние. Затем после считывания случайного числа с информационного выхода устройства при поступлении тактовых импульсов на тактовые входы первого 9 и второго 10 D-триггеров они также устанавливаются в нулевое состояние, в результате чего сигнал на выходе элемента 11 ИСКЛЮЧАЮЩЕЕ ИЛИ (и на информационном выходе устройства) принимает значение логического "0".

Кроме того, дополнительно предусмотрена одновременная установка в нулевое состояние третьего 16, четвертого 17 и пятого 18 D-триггеров. Для этого на вход начального сброса (входы установки в нулевое состояние третьего 16, четвертого 17 и пятого 18 D-триггеров) устройства подают сигнал, имеющий значение логического "0".

При введении в состав устройства в соответствии с п.5 формулы изобретения (см. фиг.3) третьего 20 и четвертого 21 Т-триггеров генератор последовательности случайных чисел работает в штатном режиме и в режиме контроля так же, как и генератор последовательности случайных чисел по п.4 формулы изобретения. При этом дополнительно обеспечивается возможность контроля запрещающих (фиг.2а) и тактовых (фиг.2б) импульсов соответственно на первом и втором выходах генератора 12 тактовых импульсов. Указанные импульсы подают счетные входы третьего 20 и четвертого 21 Т-триггеров, которые работают в счетном режиме, т. е. переходят в противоположное состояние после поступления каждого входного импульса. Сигналы с выходов третьего 20 и четвертого 21 Т-триггеров поступают соответственно на выходы контроля счета и контроля записи устройства и могут быть проконтролированы той системой, для которой формируется случайная последовательность чисел.

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

Первый 1 и второй 2 источники шума, а также первый 3 и второй 4 формирователи импульсов известны из прототипа [5], электрическая структурная схема которого показана на фиг.5. Все другие элементы могут быть выполнены либо на дискретных элементах, либо на ПЛИС фирмы ALTERA [6].

Возможный пример выполнения генератора последовательности случайных чисел на ПЛИС фирмы ALTERA показан на фиг.4, где обозначения всех элементов соответствуют обозначениям элементов на фиг.3.

В частном случае выполнения генератора последовательности случайных чисел на ПЛИС фирмы ALTERA формирователь 14 импульса сброса (в соответствии с п. 2 формулы изобретения) содержит элемент 22 НЕ, выход которого подключен к тактовому входу асинхронного D-триггера 23, вход установки в нулевое состояние которого является управляющим входом формирователя 14 импульса сброса, тактовым входом которого является вход элемента 22 НЕ, а выходом - инверсный выход асинхронного D-тригтера 23, информационный вход которого соединен с шиной единичного потенциала.

При этом формирователь 15 сигнала готовности (в соответствии с п.3 формулы изобретения)содержит формирователь 24 короткого импульса, первый вход которого является первым входом формирователя 15 сигнала готовности, а выход подключен к тактовому входу асинхронного D-триггера 25, прямой выход которого соединен со вторым входом формирователя 24 короткого импульса, причем вход установки в единичное состояние асинхронного D-триггера 25 является вторым входом формирователя 15 сигнала готовности, прямым и инверсным выходами которого являются соответственно прямой и инверсный выходы асинхронного D-триггера 25, информационный вход которого соединен с шиной нулевого потенциала.

Кроме того, формирователь 24 короткого импульса содержит элемент И 26, первый и второй входы которого являются соответственно первым и вторым входами формирователя 24 короткого импульса, а выход подключен к тактовому входу асинхронного D-триггера 27, инверсный выход которого соединен через первый 28 и второй 29 элементы НЕ с входом установки в единичное состояние асинхронного D-триггера 27, прямой выход которого является выходом формирователя 24 короткого импульса.

Для предотвращения конфликтной ситуации между записью нового значения случайной последовательности и чтение предыдущего бита с помощью формирователя 24 короткого импульса формируется короткий импульс, сбрасывающий в логический "0" D-триггер 25 после чтения каждого бита.

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

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

1. RU, авторское свидетельство 2103725, кл. G 06 F 7/58, 1998.

2. RU, авторское свидетельство 2096912, кл. Н 03 К 3/84, 1997.

3. SU, авторское свидетельство 1124295, кл. G 06 F 7/58, 1984.

4. SU, авторское свидетельство 1159015, кл. G 06 F 7/58, 1985.

5. SU, авторское свидетельство 1226451, кл. G 06 F 7/58, 1986.

6. Стешенко В.Б. ПЛИС фирмы ALTERA: проектирование устройств обработки сигналов. - М.: ДОДЕКА, 2000.