Генератор равновероятной двоичной цифры Советский патент 1983 года по МПК G06F7/58 

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

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

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

Известен блок формирования опорных последовательностей генератора GENAP-2, основанный на пересчете нетактированных последовательностей случайных импульсов на триггере со счетным входом 2.

10

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

Наиболее близким к изобретению является генератор случайной последовательности импульсов, состоящий из

20 двух двухвходовых элементов ИЛИ-НЕ,. интегратора блока согласования, элемента НЕ и генератора тактовых импульсов Сз.

Недостатками рассмотренного гене25 ратора случайной последовательности импульсов являются сложность его аппаратурного построения, которая в основном определяется наличием аналоговых элементов интегратора и 30 блока согласования), а также необходимость наличия устройств контрол равновероятности. Цель ичобретения - сокращение об ема используемого оборудования, т.е упрощение генератора. Поставленная цель достигается тем, что генератор равновероятной двоичной цифры, содержащий генерато тактовых импульсов, первый и второй элементы ИЛИ-НЕ,,причем выход пер-вого элемента НЛИ-НЕ подключен к первому входу второго элемента ИЛИвыход которого подключен к первому входу первого элемента ИЛИ-НЕ, вве дены третий и четвертый элементы ИЛИ-НЕ, выходы которых подключены к вторым входам первого и второго элементов ИЛИ-НЕ соответственно, к первым входам третьего-и четвертого элементов ИЛИ-НЕ подключен- выход генератора тактовых импульсов,выход второго элемента ИЛИ-НЕ соединен - с вторым входом третьего элемента ИЛИ-НЕ, выход которого - подключен к второму гходу четвертого элемента ИЛИ-НЕ. На фиг. 1 приведена функциональная схема генератора; на фиг. 2 реализация генератора на триггере; на фиг. 3 - временна.я диаграмма его работы. Генератор состоит из генератора 1 тактовых импульсов, первого 2, вт рого 3, третьего 4, четвертого 5 двухвходовых элементов ИЛИ-НЕ причем выход первого элемента ИЛИ-НЕ 2 подключен к первому входу второго элемента ИЛИ-НЕ 3, выход которого подключен к первому входу первого элемента ИЛИ-НЕ 2. Выход генератора 1 тактовых импульсов подключен к первым входам третьего 4 и четвертого 5 элементов.ИЛИ-НЕ, выход трет его элемента ИЛИ-НЕ 4 подключен к вторым входам первого 2 и четвертого 5 элемента ИЛИ-НЕ, а выход четве того элемента ИЛИ-НЕ 5 подключен к второму входу второго элемента ИЛИ3, выход которого подключен к второ му входу третьего элементг ИЛИ-НЕ 4 Генератор тактовых импульсов сос тоит из последовательно включенных инверторов сопротивления и емкости. Источником случайности в предла гаемом устройстве является действие внутренних шумов логических элементов, которые проявляются в форме флуктуации времен задержек этнх эле ментов. Для многих параметров дискретных элементов и логических элементов может быть принята гипотеза о нормальном законе распределения. Так, в частности, время задержки на логическом элементе есть случайная величина, распределенная по нор мальному - закону распреде/гения. Прич на флуктуации времен задержки на ло гическом э; ементе заключается в дис кретном характере зарядов, создающих электрический ток (дробовый эффект/, в тепловом движении этих носителей зарядов (тепловой шум), в изменениях проводимости под воздействием некоторых случайных-факторов (модуляционный шум ) и т.д. Фукционирование генератора равновероятной двоичной цифры происходит следующим образом. На выходе генератора 1 тактовых импульсов формируется последовательность прямоугольных импульсов (фиг. За, которые поступают на вторые входы третьего 4 и четвертого 5 элементов ИЛИ-НЕ. В первоначальный момент на, выходе генератора 1 генерируется высокий уровень эквивалентный логической единице (фиг. За). На выходах элементов 4 и 5 фиксируется значение логического нуля, которое сохраняет предыдущее состояние RS-триггера, состоящего из элементов 2 и 3. Предположим, что на выходе RS-триггера зафиксировано значение нуля, соответственно на нулевом выходе (выходе элемента 3 ) фиксируется значение логической единицы (фиг. Зб. В момент времени t , когда на выходе генератора 1 тактовых импульсов появляется уровень логического нуля, на выходе элемента 2 и cooтвeтcтвeн c но элемента 3 генерируется некоторый колебательный процесс. Средний период следования импульсов в выходном колебательном процессе и максимальная и минимальная амплитуды импульсов в сильной степени зависят от задержки сигнала на каждом логическом .элементе. Период следования импульсов в такой последовательности есть величина случайная, минимальное значение которой для данного случая (для случая, когда последовательно включено три транзисторно-транзисторных логических элемента )составляет 0,1-0,3 МКС. Кроме того, в силу влияния внутренних случайных факторов стабильность периода импульсов в выходном колебательном процессе не превышает 20%. Таким образом, начиная с момента времени t. на выходе элемента 3 (фиг. Зб) генерируется колебательный процесс со случайной длительностью периода. При появлении на выходе генератора 1 тактовых импульсов высокого уровня, соответствующего логической единице (момент времени t) колебательный процесс прекращается, и выходной RS-триггер устанавливается в одно из двух устойчивых состояний. Состояние, в которое устанавливается RS-триггер, определяется сигналами на выходах элементов 4 и 5 в момент времени tj, которые однозначно определяются автоколебаниями со случайным периодом, поэтому в общем случае RS-триггер равновероятно устанавливается или в нулевое, или в единичное состояние. На фиг. Зб показана конкретная реализация на выходе элемента ИЛИ-НЕ 3, а на фиг. Зв - осциллограмма на выходе устрой ства. Приведенное описание работы устройства было проверенодля случая, когда период следования тактовых импульсов является величиной постоянной.Однако на практике это требование всегда не выполняется. Даже кварцевые генераторы характеризуются нестабильностью периода выходной импульсной последовательности. Нестабильность входной импульсной последовательности вносит еще большую нестабильность в получение на выходе генератора равномерной двоич ной цифры: нуля или единицы. Соотношение между периодом автоколебаний Т( и периодом тактовых импульсов Т должно иметь вид Т,, что объясняется мгшой величиной случайных флюктуации задержек на логическом элементе. Преимущества генератора равновер ятной двоичной цифры заключаются в следующем. Рассмотренный генератор реализуется при минимальном количес ве элементов, причем в данном случае отсутствуют аналоговые элементы которые характерны для всех известных генераторов равновероятной двои ной цифры, в том числе и для прототипа. Для реализации предлагаемого генератора, необходимо лишь четыре элемента ИЛИ-НЕ, в то время как для реализации прототипа необходимо два элемента ИЛИ-НЕ, инвертор,интегратор и согласующее устройство. В ряд случаев предлагаемый генератор равновероятной двоичной цифры может быть реализован на однотактном 1 - риггере 6 фиг. 2} , для чего могут быть использованы интегральные схемы К155ТМ5 или К155ТМ7. В этом случае на реализацию генератора рав новероятной двоичной цифры требует ся только 1/4 корпуса ИС. К155ТМ5 или К155ТМ7.

db nz

В сравнении с базовым объектом блоком формирования опорных последовательностей генератора GENAP-2 предложенное устройство отличается существенной простотой аппаратурной регшизации и кроме того, более высокой надежностью функционирования. Подобный генератор равновероятной двоичной цифры целесообразно использовать для построения генераторов рондомизированных псевдослучайныз4 чисел, где необходим источник равновероятной двоичной цифры, не отличаю1дийся высоким требованием к равновероятности выходных последовательностей. Формула изобретения Генератор равновероятной двоичной цифр, содержащий генератор тактовых импульсов, первый и второй элементы ИЛИ-НЕ, причем выход первого элемента ИЛИ-НЕ подключен к первому входу второго элемента ИЛИ-НЕ, выход которого подключен кпервому входу первого элемента ИЛИ-НЕ, о тличающийся тем, что, с целью упрощения генератора, он содержит третий и четвертый элементы ИЛИ-НЕ, выходы которых подключены к вторым входам первого и второго элементов ИЛИ-НЕ соответственно, к первым входам третьего и четвертого элементов ИЛИ-НЕ подключен выход генератора тактовых импульсов, выход второго элемента ИЛИ-НЕ соединен с вторым входом третьего элемента ИЛИ-НЕ, выход которого подключен к второму входу четвертого элемента ИЛИ-НЕ. Источники информации, принятые вс внимание при экспертизе 1.Авторское свидетельство СССР 834855, кл. Н 03 К 3/84, 1981. 2.Яковлев В.Б., Федоров Р.ф. Вероятностные вычислительные машины Л., Машиностроение, 1974, с. 228. 3.Авторское свидетельство СССР № 688905, кл. G 06 Т 1/02, G 07 С 15/00, 1979 (прототип).

л

„ уцм МММ

ятям тщн--- -тЛтттЛЪш м .