Генератор псевдослучайных кодов

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к ввт. свид-ву— (22) Заявлено 01. 10. 80 (21) 2987192/18-24 (31) М. КЛ.з

G F 7/58 с присоединением заявки ¹â€” (23) Приоритет—

Государственный комитет

СССР но делам изобретений и открытий

Опубликовано150882. Бюллетень ¹ 30

Дата опубликования описания 150882 (33) УДК 681. 325 (088. 8) (72) Авторы изобретения

Л.Ф.Карачун, В.Н.Кущ, Р.И.Лупанова и А.М. (71) Заявитель

Специальное конструкторско-технологическо бюро вычислительной техники (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ КОДОВ

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

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

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

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

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

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

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

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

30 испытательных последовательностей.

951301

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

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

Кроме того, для него скорость генерирования зависит от числа выходов генератора, существенно уменьшаясь с увеличением числа выходов.

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

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

М-последовательности, первая группа выходов которого соединена с группой входов управляемого регистра сдвига, управляющий вход которого подключен к выходу блока задания веса кода, первый вход которого является .управляющим входом генератора, тактовый вход которого подключен к тактовым входам генератора М-последовательности и управляемого регистра сдвига, выход которого соединен с вторым входом блока задания веса кода, введены и групп /триггеров и и дешифраторов, управляющие входы которых соединены с группой выходов управляемого регистра сдвига соответственно, выходы второй,третьей,...,1-ой (1=n+1) групп генератора М-последовательности соединены с соответствующими входами первого, второго,..., n-ro дешифраторов, выходы каждого i-го,i-=1Ä2,...,n) дешифратора соединены со счетными входами соответствующих, триггеров

i-ой групп, выходы которых образуют i.-ую группу выходов генератора.

На фиг.1 приведена блок-схема генератора; на фиг.2 — схема управляемого регистра сдвига; на фиг.3схема блока задания веса кода.

Генератор содержит генератор М-последовательности 1, выходы которого разбиты на 1 групп по m разрядов в

5 каждой. Выходы каждой группы блока 1 связаны с входами одного из 1 дешифраторов 2. Управляющий вход 3 каждого иэ дешифраторов 2 подключен к одному иэ 1 выходов управляемого ре-!

О гистра сдвига 4. Каждый из 1 2. " выходов всех дешифраторов 2 связан со счетным входом одного из 1 2 выходных триггеров 5, выходы 6 которых являются выходами генератора. Входы управляемого регистра сдвига 4 связаны с 1 произвольными выходами блока 1. Выход 7 последнего разряда управляемого регистра сдвига 4 связан с одним входом блока задания веса 8, второй вход которого подключен к шине настройки 9,а выход которого подсоединен к входу 10 первого разряда управляемого регистра сдвига 4.Шина тактовых сигналов 11 подключена к тактовым входам 12,и 13 блоков 4 и 1. Управляемый регистр сдвига 4 (фиг.2) содержит, триггеры 14, элементы II 15-17, элемент

ИЛИ 18. Этот блок выполняет функции вероятностного коммутатора, который в случайном порядке подключает заданное число дешифраторов.2 к выходам генератора псевдослучайных чисел блоку 1. Существенно, что для обеспечения изменения вероятности появ- ления единичного сигнала на любом иэ выходов 6 предлагаемого генератора очень удобйо использовать для построения блока 4 управляющий регистр сдвига. При изменении числа единиц (веса кода), циркулируемых в управО ляемом регистре сдвига, происходит пропорциональное изменение частоты выбора каждого из дешифраторов 2 (необходимо обратить внимание, что в каждый момент времени одновременно выбрано столько дешифраторов 2, сколько единиц циркулирует в блоке

4) и соответственно пропорционально этому изменяется частота появления единицы на каждом выходе любого из дешифраторов 2. Назначение блока

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

9 сигналом, говорящим об увеличении или уменьшении на определенное число количества единиц в блоке 4, производит блокировку цепи обратной связи блока 4 в момент появления на выходе 7 единиц - в случае уменьшения числа единиц, либо производят запись единиц по входу 10 в моменты появления на выходе 7 нулей — в слу;

65 чае увеличения числа единиц. Кроме

951301.

65 того, начальный код последовательно может быть записан с помощью блока

8 в блок 4. Блок задания веса кода . содержит элементы И 19-21 и элемент

ИЛИ 22.

Устройство функционирует следующим образом.

B управляемый регистр сдвига 4 по шине 9 через блок задания веса кодов

8 поступает код настройки с заданным весом К. При этом блок 4 настраивает-10 ся на выдачу разрешающих сигналов по

К из 1 произвольным выходным шинам.

Число К может быть изменено от 0 до

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

Работа блока 4 заключается в следующем. Если в данном. такте на 1 выходах блока 1, связанных с входами блока 4, нулевые сигналы, то блок

4 в этом такте срабатывает как обычный сдвиговый регистр. Если же входной случайный вектор, формируемый на

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

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

4 и равна . КаждЫй из разрешенных

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

В частном случае, когда К = 1, получаем в каждом такте изменение состояния только одного выхода генератора.

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

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

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

Для того, чтобы были выполнены необходимые для правильной работы генератора временные соотношения, максимальная задержка на распространение сигнала по самому большому пути в каждом из блоков должна быть равна где Т вЂ” период следования тактовых

re сигналов; — время задержки переключения триггера..951301

Судя по структуре блоков как предлагаемого генератора, так и прототипа, самая большая задержка имеет место для блока 4. Если r — длина (число элементов) цепочки из последовательно соединенных логических элементов

И и ИЛИ, о которым должен пройти без искажения сигнал, à С <р- среднее время задержки сигнала для логических элементов, определяемое по паспортным данным для используемой се- 10 рии логических элементов, то должно выполняться

» д Р» ." "у.с р

Если предполохять, что предлагаемый и известный генераторы имеют, одинаковое число выходных каналов Х,, то величины 2 для прототипа и предложенного генератора опредеЛяются соответственно следующим образом

r = 2N

Ф

» = 2 „, 1 где 2 — число выходов используемых дешифраторов. Если пренебречь величиной ty, то из.приведенных рассуждений следует, что скорость предлагаемого генератора выше в

Т тм " 1" ъср - t.> р \

Т,„-g 2.ъ ">.ср. раз, т.е. скорость генерации для предлагаемого генератора может быть увеличена по сравнению с прототипом во столько раз, сколько выходов имеет каждый из вводимых в схему предлагаемого генератора дешифраторов. ч

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

Генератор псевдослучайных кодов, содержащий генератор М-последовательности, первая группа. выходов которого соединена с группой входов управляемого регистра сдвига, управляющий вход которого подключен к выходу блока задания веса кода, первый вход которого является управляющим входом генератора, тактовый вход которого подключен к тактовым входам генератсра М-последовательности и управляемого регистра сдвига, выход . которого соединен с вторым входом блока задания веса кода, о т л и ч а ю шийся тем, что, с целью повышения быстродействия генератора, он содержит и групп триггеров и н",дешифраторов, управляющие входы которых соединены с группой выходов управляЬмого регистра сдвига соответственно, выходы второй, третьей,. ° ., 1-й (1=п+1) групп генератора М-последовательности соединены с соответствующими входами первого, второго,..., и-го дешифраторов, выходы каждого

i-го (i=1,2,...,п) дешифратора соединены со счетными входами соответствующих триггеров i-й группы, выходы которых образуют i-ую группу выходов генератора.

Источники информации, принятые Во внимание при экспертизе

1. Авторское свдительство СССР

9 436340 кл.G Об F 1/02,. 1973.

2. Авторское свидетельство СССР

Р 440777, кл.G Об F 1/02, 1973.

3. Авторское свидетельство СССР

Р 696510„ кл.G Об F. 1/02, 1977 (прототип).

951301

@АЗ

Составитель A.Êàðàñoâ

Редактор К.Волощук Техред T.Ìàòo÷êà Корректор И. Myñêà

Заказ 5948/55 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035) Москва, Ж-.35, Раушокая наб., д.4/5

Филиал ППП "Патент", г.ужгород, ул.Проектная,4