Генератор псевдослучайных кодов Советский патент 1982 года по МПК G06F7/58 

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

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

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

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

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

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

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

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

30 Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных кодов, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи, управляемый регистр сдвига, каждый разряд которого содержит триг гер, первый, второй и третий элементы и элемент ИЛИ, блок задания веса кода Ез 3. Известное устройство позволяет получить на каждомвыходе различные псевдослучайные последовательности, причем вероятность появления единич ного символа в каждой последовательности может быть изменена с заданной дискретностью.Однако при использовании его в качестве источника испытательных последовательностей в пр цессе генерирования могут появиться комбинации выходных сигналов, при которых происходит одновременное слу чайное изменение двух или более сигналов на входах испытуемой схемы, в результате чего испытуемая схема может принять неопределенное состояние Кроме того, для него скорость генерирования зависит от числа выходов генератора, существенно уменьшаясь С увеличением, числа выходов. Цель изобретения - расширение фун кциональных возможностей генератора путем получения последовательностей псевдослучайных сигналов с заданными фанзовыми соотношениями, а также повышение быстродействия генератора; Для достижения поставленной цели в известный генератор псевдослучайных кодов, содержащий генератор М-последовательности, первая группа выходов которого соединена с группой входов управляемого регистра сдвига, управляющий вход которого подключен к выходу блока задания веса кода, первый вход которого является -управляющим входом генератора, тактовый вход которого подключен к тактовым входам генератора М-последовательности и управляемого регистра сдвига, выход которого соединен с вторым входом блока задания веса кода, введены п групп/триггеров и п дешифраторов, управляющие входы которых соединены с группой выходов управляемого регистра сдвига соответственно, выходы второй,третьей, ..., 1-ой ) групп генератора М-последовательности соединены с соответствующими входами первого, второго,..., п-го дешифраторов, выходы каждого i-ro (,2,...п) дешифратора соединены со счетными входами соответствую1151х .триггеров i-ой группы, выходы которых образуют i-ую группу выходов генератора. На фиг.1 приведена блок-схема генератора; на фиг.2 - схема управляемогр регистра сдвига; на фиг.З схема блока:задания веса кода. Генератор содержит генератор М послёдовательности 1, выходы которого разбиты на 1 групп по m разрядов в каждой. Выходы каждой группы блока 1 связаны с входами одного из 1 дешифраторов 2. Управляющий вход 3 каждого из дешифраторов 2 подключен к одному из 1 выходов управляемого регистра сдвига 4. Каждый из 1-2.выходов всех дешифраторов 2 связан со счетным входом одного из 1-2 выходных триггеров 5, выходы б которых являются выходами генератора. Входы управляемого регистра сдвига 4 связаны с 1 произвольными выходами блока 1. Выход 7 последнего разрядауправляемого регистра сдвига 4 связан с одним входом блока задания веса 8, второй вход которого подключен к шине настройки 9,а выход которого подсоединен к входу 10 первого разряда управляемого регистра сдвига 4.Шина тактовых сигналов 11 подключена к тактовым входам 12.и 13 блоков 4 и 1. Управляемый регистр сдвига 4 (фиг.2) содержит , триггеры 14, элементы И 15-17, элемент ИДИ 18. Этот блок выполняет функции вероятностного коммутатора, который в случайном порядке подключает заданное число дешифраторов.2 к выходам генератора псевдослучайных чисел блоку 1. Существенно, что для обеспечения изменения вероятности появления единичного сигнала на любом из . выходов б предлагаемого генератора очень удоб.йо использовать для построения блока 4 управляющий регистр сдвига. При изменении числа единиц (веса кода), циркулируемых в управляемом -регистре сдвига, происходит пропо.рдиональное изменение частоты выбора каждого из дешифраторов 2 (необходимо обратить внимание, что в каждый момент времени одновременно выбрано столько дешифраторов 2, сколько единиц циркулирует в блоке 4) и соответственно пропорционально этому изменяется частота появления единицы на каждом выходе любого из дешифраторов 2. Назначение блока 8задания веса кода (фиг.З) заключается в осуществлении изменения в процессе работы (т.е. без остановки генератора) числа единиц, .циркулируемых в блоке 4. Для этого блок 8 в соответствии с поступгшщим по шийе 9сигналом, говорящим об увеличении или уменьшении на определенное число количества единиц в блоке 4, производит блокировку цепи обратной связи блока 4 в момент появления на выходе 7единиц - в случае уменьшения числа единиц, либо производят запись единиц по входу 10 в моменты появления на выходе 7 нулей - в слу: чае увеличения числа единиц. Кроме того, начальный код последовательно может быть записан с помощью блока 8 в блок 4. Блок задания веса кода содержит элементы И 19-21 и элемент ИЛИ 22.Устройство функционирует следующим образом. В управляемый регистр сдвига 4 по шине 9 через блок задания веса кодов 8 поступает код настройки с заданным весом к. При этом блок 4 настраивает ся на выдачу разрешающих сигналов по К из 1 произвольным выходшлм шинам. Число КМожет быть изменено от О до 1 в зависимости от веса кода настрой ки. Так как сигналы, поступающие с выходов блока 1, являющегося датчиком псевдослучайных равномерно распределенных чисел, на входы блока 4 носят псевдослучайный характер, то изменение кодовых комбинаций с задан ным весом К в блоке 4 также происходит случайным образом и соответствен но выбор К из 1 дешифраторов 2 случайный. Работа блока 4 заключается в следующем. Если в данном такте на. 1 выходах блока 1, связанных с входами блока 4, нулевые сигналы, то блок 4 в этом такте срабатывает как обычный сдвиговый регистр. Если же вход ной случайный вектор, формируемый на 1 выходах блока 1, имеет в каких-либ разрядах единичные компоненты, то соответствующие разряды блока 4 отк-; лючены как своими входами, так и выходами, а информационные сигналы, движущиеся между разрядами блока 4, обходят отключенные разряды блока 4. Таким образом в каждом такте сдвига разряды кода, записанного в управ ляемом регистре 4, перепрыгивают через разряды регистра, отмеченные единицами во входном векторе, сформированном блоком 1. Вероятность появления разрешающего сигнала на входе 3 каждого из дешифраторов 2 определяется вероятностью появления единицы в соответствующем разряде блока 4 и равна . Кажда1й из разрешенных дешифраторов 2 в данный момент времени формирует единичный сигнал на одном из своих выходов, номер которого определяется случайной т-раз рядной комбинацией на соответствующей группе выходов блока 1. Поэтому в каждом такте на входы случайно выбранных К триггеров 5 поступают единичные сигналы. Именно эти К выбранных триггеров 5 изменяют свое состояние на противоположное, а остальные триггеры 5 сохраняют прежнее состояние., Такое функционирование триггеров 5 обусловлено тем, что они рабоTeUOT в счетном режиме. Таким образом, достигается изменение состояния (переключение сигнала на заданном числе выходов. При этом генератор является управляемым. Возможно задание вероятности изменения сигнала по каждому выходу в соответствии с формулойгде К }0,1,...,lj В частном случае, когда К 1, получаем в каждом такте изменение состояния только одного выхода генератора. Последовательность таких псевдослучайных кодов, получившая в литературе название последовательности псевдоциклических кодов, находит в практике испытаний цифровых схем наибольшее применение. По сравнению с прототипом предлагаемый генератор обладает дополнительными возможностями, обеспечивающими улучшение его свойств как источника псевдослучайных испытательных сигналов, предназначенных для контроля цифровых схем. В частности, возможность генерации псевдоцикли еских кодов, характеризующихся перепадом уровня .сигнала только на одном выходе в любой момент времени, особенно полезна в том случае, если при подаче независимых случайных сигналов на входы испытуемой схемы возникают условия для временной неопределенности или гонки фронтов. В этом смысле предложенный генератор практически не имеет ограничений в применении. Псевдоциклические кодымогут быть использованы при проверке любых комбинационных или логических схем с памятью - обычно в системах с общим информационным каналом для выборки адресов устройств, дешифраторов управления или строби-. рующих схем систем передачи данных. Кроме того, предложенный генератор позволяет обеспечить большую скорость генерации псевдослучайных кодов по сравнению с прототипом. Сравним.скорости генерации предлагаемого генератора и прототипа. Скорость генераг ции обусловлена частотой тактовых сигналов, синхронизирующих работу блоков генератора. Однако этот параметр нельзя .выбирать произвольно. Для того, чтобы были выполнены необходимые для правильной работы генератора временные соотношения, максимёшьная задержка на распространение сигнала по самому большому пути в каждом из блоков должна быть равна wax тс где - период следования тактовых сигналов; tn - время задержки переключе. ния триггера. Судя по структуре блоков как предла гаемого генератора, так и прототипа самая большая задержка имеет место ;для блока 4. Если г - ,длина (число элементов) цепочки из последователь но соединенных логических элементов И и ИЛИ, по которым должен пройти без искажения сигнал, а Cjcp- средне время задержки сигнала для логических элементов, определяемое по паспортным данным для используемой серии логических элементов, то должно выполняться Если пpeдпoлo з ть что предлагаемый и известный гецераторы имеют одинаковое число выходкйх каналов N, то величины 2 для прототипа и предложенного генератора определяются соответственно следующим образом 2N N 7 , где 2 - число выходов используемых дешифраторов. Если пренебречь величиной t, то иэ .приведенных рассуждений следует, что скорость предлагаемого генератора выше в cp-t .ср-Ль раз, т.е. скорость генерации для предлагаемого генератора может быть увеличена по сравнению с прототипом во столько раз, сколько выходов име ет каждый из вводимых в схему предлагаемого генератора депшфраторов. Формула Изобретения Генератор псевдослучайных кодов, содержа1дий генератор М-последовательности, первая группавыходов Которого соединена с группой входов управляемого регистра сдвига, управляющий в-ход которого подключен к выходу бло-ка задания веса кода, первый вход которого является управляющим входом генератора, тактовый вход которого подключен к тактовым входам генератора М-г оследовательности и управляемого регистра сдвига, выход которого соединен с вторым входом блока задания веса кода, отличающийся тем, что, с целью повышения быстродействия генератора, он содержит п групп триггеров и п ,дешифраторов, управляющие входы которых соединены с группой выходов управляемого регистра сдвига соответственно, выходы второй, третьей,..., 1-й () групп генератора М-последовательности соединены с соответствующими входами первого, второго,..., п-го -дешифраторов, выходы каждого i-ro (,2,...,п) дешифратора соединены со счетными входами соответствующих триггеров i-и группы, выходы которых образуют i-ую группу выходов генератора. Источники информации, принятые во внимание при экспертизе 1.Авторское свдительство СССР 436340,. кл.а Об F 1/02, 1973. 2.Авторское свидетельство СССР 440777, кл.С Об F 1/02, 1973. 3.Авторское свидетельство СССР № 696510, кл.С 06 F 1/02, 1977 (прототип). .