ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ N-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ Российский патент 1997 года по МПК G06F7/58 

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

Известен генератор случайных чисел последовательного типа [1] содержащий генератор опорной последовательности, выходы которого подключен к входу n-разрядного регистра сдвига, выходы каждой ячейки параллельно подключены ко вторым входам элементов И, к первому входу которых подается последовательность тактовых импульсов, разрешающих съем случайного числа с выходов элементов И.

Однако в данном генераторе после каждого такта необходимо в регистре менять последовательность случайных чисел, что снижает скорость выходной последовательности случайных чисел в 1/n-раз.

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

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

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

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

Умножитель частоты содержит два элемента И, элемент НЕ, две линии задержки и элемент ИЛИ. Выход элемента ИЛИ является выходом умножителя, вход которого соединен с первым входом первого элемента И и со входами первой линии задержки и элемента НЕ. Выход элемента НЕ подключен к первому входу второго элемента И и через вторую линию задержки ко второму входу первого элемента И. Выходы элементов И подключены ко входам элемента ИЛИ.

Формирователь коротких импульсов содержит линию задержки, элемент НЕ и элемент И. Выход элемента И является выходом формирователя, вход которого через линию задержки и элемент НЕ соединен со входами элемента И.

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

На фиг.1 приведена схема генератора псевдослучайных N-разрядных двоичных чисел; на фиг.2 и 3 функциональные схемы соответственно умножителя частоты и формирователя коротких импульсов; на фиг.4 временные диаграммы, поясняющие принцип работы генератора псевдослучайных N-разрядных двоичных чисел; на фиг.5 временные диаграммы, поясняющие принцип работы умножителя частоты.

Предлагаемое устройство содержит генератор периодических импульсов (ГПИ) 1, элемент ИЛИ 2, генератор опорной последовательности (ГОП) 3, умножители частоты (УЧ) 4.1-4.n, формирователи коротких импульсов (ФКИ) 5.1-5n, линии задержки (ЛЗ) 6.1-6.n, элементы И 7.1-7.n, блок памяти (БП) 8 и выходы генератора 9.1-9.n.

Умножители частоты 4.1-4. n содержат элементы задержки 13.1 и 13.2, элементы И 14.1 и 14.2, элемент НЕ 15 и элемент ИЛИ 16.

Формирователи коротких импульсов 5.1-5.n содержат элемент НЕ 10, элемент И 11 и линию задержки 12.

Генератор псевдослучайных N-разрядных двоичных чисел использует следующий принцип работы.

Пусть дана последовательность псевдослучайных двоичных чисел g(t) с частотой следования F, из которой формируются n-опорных последовательностей псевдослучайных двоичных чисел с частотами следования
g₁(t)2⁰F, g₃(t)2¹F, g₃(t)2²F, g_n(t)2^n-1F. (1)
Самый старший n-й разряд формируется с частотой 2^n-1F, n-1-й разряд с частотой 2^n-2F и т.д. а первый разряд (самый младший) с частотой 2⁰F.

В результате будет получено псевдослучайное N-разрядное число с равновероятным законом распределения.

Действительно, автокорреляционная функция псевдослучайного N-разрядного двоичного числа R_g(τ) будет удовлетворять требованию равновероятности, т.к. будет равняться взвешенной сумме автокорреляционных функций последовательностей случайных последовательностей g_i(t)2^i-1 с коэффициентами, равными квадрату веса соответствующему разряда числа

где i номер псевдослучайной последовательности, формирующей соответствующий разряд [1]
Откуда следует, что к самым старшим разрядам N-разрядного псевдослучайного двоичного числа необходимо предъявлять самые высокие требования "случайности", а к самым младшим существенно заниженные, без ущерба качества равномерного закона их распределения.

Предлагаемое устройство работает следующим образом.

В начальный момент времени импульс с выхода ГПИ 1 (фиг.4a) скважности T/τ=2 (где T-период следования последовательности импульсов, τ длительность импульсов) поступает на вход УЧ 4.1 и ФКИ 5.1, где соответственно происходит умножение частоты следования импульсов вдвое (фиг.4b) и формируется короткий импульс по заднему фронту входного импульса (фиг.4d). С выхода УЧ 4.1 (фиг. 5b) последовательность импульсов поступает на вход УЧ 4.2 и ФКИ 5.2, где также происходит соответственно умножение частоты следования импульсов вдвое (фиг.5c) и формирование короткого импульса (фиг.5e). Сформированный короткий импульс через элемент ИЛИ 2 запускает ГОП 3, на выходе которого формируется одно из значений псевдослучайного числа g(t) ноль или единица, которое поступает на вторые входы элементов И 7.1-7.n. Разрешающий импульс с выхода ФКИ 5.1, пройдя через линию задержки 6.1, время задержки которой есть сумма времен задержек в элементе ИЛИ 2 и времени формирования одного разряда псевдослучайного числа в ГОП t_з t^или + t^гоп в ГОП, записывает значение g(t) в первый разряд БП 8. Аналогично будут формироваться другие разряды с той лишь реакцией, что частота смены последующего значения разряда будет удваиваться.

Умножитель частоты 4.1-4.n работает следующим образом.

С выходе ГПИ 1 последовательность импульсов скважности T/t 2 (фиг.5a) поступает на элемент задержки 13.1, время задержки которой t_лз1 t/2 (фиг. 5v), и элемент НЕ 15 (фиг.5z), где они соответственно задерживаются и инвертируются. В момент одновременного присутствия импульсов на входах элемента И 14.1 будет сформирован импульс. Кроме того, импульс будет сформирован и на выходе элемента И 14.2 в момент присутствия на первом входе инвертированного и задержанного импульса, поступающего с выхода элемента НЕ, на величину t_лз2 t/2-t_не (где t_не время задержки на элементе НЕ 15), и входного импульса. Элемент ИЛИ 16 формирует удвоенную частоту следования импульсов (фиг.4b) из последовательностей импульсов, поступающих на его вход с выходов соответственно, элементов И 14.1 и 14.2 (фиг.5h,g). Если частота следования входной последовательности импульсов равна F=1/T при скважности равного 2, то выходная удвоенная частота следования импульсов есть сумма последовательностей удвоенной скважности с той же частотой следования импульсов, T/(0,5τ)+T/(0,5τ)=2(T/0,5τ) или F 1/2T, 2F=1/T.

Формирователь коротких импульсов 5.1-5.n работает следующим образом.

На входы элемента НЕ 10 и линии задержки 12 поступает опорная последовательность импульсов (фиг.4a), которая в этих элементах соответственно инвертируется и задерживается. Тогда в момент присутствия на входах элемента И 11 этих импульсов сформируется короткий импульс, длительность которого будет определяться временем задержки элемента НЕ 12 t_лз и достаточного для его формирования в элементе И 11 и запуска ГОП 3.

По сравнению с прототипом генератор псевдослучайных N-разрядных двоичных чисел значительно проще и генерирует требуемые последовательности весьма экономичным способом, используя единственный задающий генератор псевдослучайных чисел. При этом с выхода устройства снимается псевдослучайное N-разрядное двоичное число при каждом такте его работы, при сохранении жестких требований к выходной последовательности. Тогда как в известном устройстве требуется n-опорных генераторов, что весьма не экономично и проблематично, т.к. при увеличении значности псевдослучайных N-разрядных двоичных чисел необходимо иметь абсолютно одинаковых характеристики у каждого генератора опорной последовательности [1]
При формировании псевдослучайных N-разрядных двоичных чисел последовательным способом достичь большой скорости весьма затруднительно, так как в (n-1)-раз должна увеличиться частота генерации опорной последовательности на выходе устройства, что в свою очередь влияет на качество опорной последовательности при таких частотах генерации [2]
Источники информации:
1. Яковлев В.В. Стохастические вычислительные машины. Л. Машиностроение, 1974. с. 191.

2. Бобнев М. П. Генерирование случайных сигналов.-М. Энергия, 1971, с. 170.

Использование: в вычислительной технике и может быть использовано в синтезаторах частоты, формиpующих сигнал с программной перестройкой рабочей частоты. Сущность изобретения: создание генератора, обеспечивающего формирование псевдослучайных N-разрядных двоичных чисел с помощью одного опорного генератора псевдослучайной последовательности. Поставленная цель достигается тем, что при формировании псевдослучайных N-разрядных двоичных чисел от одного опорного генератора 3 значения самых старших разрядов формирующих чисел в блоке памяти 8 меняются чаще, чем самые младшие, без ущерба качества к выходной последовательности в целом на выходе 9.1-9.n генератора. Генератор содержит генератор периодических импульсов 1, генератор опорной последовательности равновероятных чисел 3, элемент ИЛИ 2, умножители частоты 4, формирователи коротких импульсов 5, линии задержки 6, элементы И 7 и блок 8 памяти. 2 з.п. ф-лы, 5 ил.

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