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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к импульсной технике и может использоваться в информационно-измерительной технике . Целью изобретения является улучшение корреляционных характеристик формируемых последовательностей, что достигается за счет введения в генератор псевдослучайных последователь-. ностей блока 5 умножения и дешифратора 3 и за счет образования новых функциональных связей. Генератор содержит также генератор 1 тактовых импульсов, блок 2 регистров сдвига, логический преобразователь 4, блок 6 сложения, элемент ИЛИ-НЕ 7, элемент НЕ 8, элементы И 9, 12 и 15, элементы 2(2К)-ИЛИ-НЕ 10 и 11, триггеры 13 и 18, опорный генератор 14 импульсов, счетчик 16 импульсов, блок 17 сравнения , датчик 19 кодов, регистры 20- 22. 1 з.п.ф-лы, 1 ил. с $ (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1636995

А1 (51)5 Н 03 К 3 84

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A 9TOPCH0MY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

IlPH ГКНТ СССР (21) 4643372/21 (22) 20.12.88 (46) 23.03.91. Бюл.N - 11 (71) Киевское геофизическое отделение Украинского научно-исследовательского геологоразведочного института (72) П.Т.Сиротенко и В.И.Роман (53) 621.384.2(088,8) (56) Авторское свидетельство СССР

11 - 1173529, кл.Н 03 К 3/84, 1984.

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

Ь 1228236, кл. Н 03 К 3/84, 1984, (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ (57) Изобретение относится к импульсной технике и может использоваться в информационно-измерительной технике. Целью изобретения является улучшение корреляционных характеристик формируемых последовательностей, что достигается за счет введения в генератор псевдослучайных последовательностей блока 5 умнржения и дешифратора 3 и за счет образования новых функциональных связей, Генератор содержит также генератор 1 тактовых импульсов, блок 2 регистров сдвига, логический преобразователь 4, блок 6 сложения, элемент ИЛИ- НЕ. 7, элемент .НЕ 8, элементы И 9, !2 и 15, элементы 2(2И)-ИЛИ-НЕ 10 и 11, триггеры 13 и 18, опорный генератор 14 импульсов, счетчик 16 импульсов, блок 17 сравЮ нения, датчик 19 кодов, регистры 2022. 1 з.п.ф-лы, 1 ил.

3 1636995. 4

Изобретение относится к- импульсной технике и может использоваться в информационно-измерительной технике.

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

На чертеже представлена электрическая функциональная схема генератора псевдослучайных последовательное- 1О тей.

Генератор псевдослучайных последовательностей содержит последовательно соединенные генератор J тактовых импульсов, блок 2 регистров сдвига, де-. 15 шифратор 3 и логический нреабразова:-: тель 4, последовательно соединенные блок 5 умножения и блок 6 сложения, выходы которого соединены с соответствующими входами блока 2 регистров 20 сдвига, первая и вторая группа выходов которого соединены соответственно с .входами блока 5 умножения и с .второй группой входов блока 6 сложения. Вход синхронизации логического преобразователя 4 соединен с выходом генератора 1 тактовых импульсов.

Логйческий преобразователь 4 содержит последовательно соединеинь|е элемент ИЛИ-НЕ 7, элемент НЕ 8, пер- ЗО вый элемент И 9 и первый элемент

2(2И)-ИЛИ-НЕ 10, первый вход которого соединен с первым входом второго элемента 2И(2И)-ИЛИ-НЕ, 3 1, второй и третий входы которого соединены соот- g5 ветственно с выходом второго элемента И 12 и с первым выходом триггера

13, вход которого соединен с первым входом второго элемента И 12 и с вторым входом первого элемента И 9, @ третий вход которого соединен с вторым входом второго элемента И 12, третий вход которого соединен с выходом элемента ИПИ-НЕ 7, входы которого и третий вход первого элемента 45

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

-соединен с четвертым входом второго 50 элемента 2(2И)-ИЛИ-НЕ 11 и с вторым входом первого элемента 2(2И)-ИЛИ-НЕ .10 третий и четвертый входы которого соединены соответственно с выходом второго элемента И 12 и с пер- 55 вым выходом триггера. 13.

Генератор 1 тактовых импульсов содержит последовательно соединенные опорный генератор 14 импульсов, элемент И 15, счетчик 16 импульсов, блок 17 сравнения и триггер 18, датчик 19 кодов, выходы которого соединены с второй группой входов блока.

17 сравнения. Второй вход элемента

И 15 соединен с выходом триггера 18, второй вход которого соединен с вторым входом счетчика 16 импульсов, с входом опорного генератора 14 импульсов и является входом "Пуск". ге-.нератора 1 тактовых импульсов.

Блок 2 регистров сдвига содержит последовательно соединенные первый

20, второй 21 и третий 22 регистры, входы синхронизации которых являются входом синхронизации блока 2 регистров, первая и вторая группы выходов которого являются выходами третьг его 22 и второго 21 регистров блока

2 регистров сдвига, входы первого регистра 20 которого являются входами блока 2 регистров сдвига..

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

Перед началом работы в первый регистр 20 блока 2 регистров сдвига записывается код единицы, а во второй 21 и третий 22 регистры — код нуля. Генератор формирует периодичес" кие псевдослучайные последовательности, период которых состоит из

3 о 1

Я ю з

q-1 элементов, где q - простое число.

Длительность генерируемой последовательности задается датчиком 19 ко. дов. Запуск генератора псевдослучайных последовательностей осуществля. ет пусковой импульс, поступающий на вход "Пуск" геяератора 1 тактовых имнульсов и осуществляющий запуск опорного генератора 14 импульсов, установку счетчика 16. импульсов в нулевое состояние и установку триггера 18 в единичное состояние. Сигнал с выхода триггера 18 поступает на второй вход элемента И 15, разрешая поступление импульсов опорного генератора 14 импульсов на входы счетчика 16 импульсов и регистров 20-22 блока 2 регистров сдвига.

Формируемые устройством псевдослучайные последовательности могут содержать как целое число периодов, так и не целое. При равенстве кодов

5 163 чисел с выходов счетчика 16 импульсов и датчика 19 кодов блоком 17 сравнения выдается сигнал, который устанавливает триггер 18 в нулевое состояние. Вследствие этого снимается сигнал разрешения с входа элемента И 15 и прекращается поступление тактовых импульсов на входы счетчика

16 импульсов и регистры 20-22. Формирование генератором псевдослучайных последовательностей новой последовательности осуществляется при повторении поступления пускового импульса на вход генератора 1- тактовых импульсов.

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

Б1 = Sj г + аБ1-э где 1 (а а а — натуральное число

)з9 3 2>

S — элементы ц-ичной последовательности.

Реализация рекуррентного уравнения осуществляется в поле Галуа

GF(q). Блок 5 умножения по модулю а и блок 6 сложения по модулю q представляют собой комбинационные схемы и синтезируются на основе соответствующих таблиц истинности. Блок 5 умножения осуществляет умножение по модулю q на величину а, где а — коэффициент рекуррентного уравнения при слагаемом S 1 з, а блок 6 сложения осуществляет сложение по модулю а слагаемых S j и а Э, S, которые

mo ô получаются соответственно на выходах второго регистра 21 и блока 5 умножения.

Дешифратор 3 и логический преобразователь 4 выполняют преобразование q-ичной псевдослучайной последовательности в троичную псевдослучайную последовательность, элементы которой принимают значения †.1, О, +1.

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

1 О, если g = .О б F(q)

З3 ((17 (К, ), если 0(406 GF(q), 1 У или — 1 О, если М1= О 6GF(q), 1 1 (-1) g (0(), если ф,„ =

= 0 C GF(q), 6995 6 где 1О .1- формируемая генератором

13 троичная последовательность, g — j-é элемент q-ичной псевдо) случайной последовательности;

У ) (1 ) — индекс чисел, устанавливаемый на основании теоремы о квадратичных вычетах

j = 0,И-1.

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

20 правило выбрано верно, в противном случае для. формирования троичной последовательности применяется второе решающее правило. Проведенный анализ для q < 31 показал, что для формиро25 вания троичных последовательностей, период которых состоит из 31, 307, 993 элементов, необходимо применение второго решающего правила, а для остальных последовательностей — перво30 го решающего правила, для реализации которого триггер 13 логического преобразователя 4 блокируется в нулевом состоянии на все время формирования последовательности.

При формировании троичной последовательности для q = -- 3,,q - =13, например, в дешифраторе 3 используется всего два выхода, соответствующие числам О и 1.

40 Сигнал низкого уровня с выхода дешифратора 3, соответствующего числу О, подается на третий и второй входы элементов И 9 и 12, являясь сигналом запрета на пропускание так45 тового импульса с генератора 1 такто-. вых импульсов. Поэтому на выходах элементов 2(2И)-KIN-HE 10 и 11 образуются сигналы высокого уровня, соответствующие формированию элемента

1I f l

О последовательности.

В случае появления на выходе дешифратора 3 сигнала, соответствующего числу 1, с выхода дешифратора 3, соответствующего числу О, на третий

55 и второй входы элементов И 9 и 12 поступает сигнал высокого уровня, а поэтому во время подачи тактового импульса с генератора 1 тактовых импульсов сигнал с выхода элемента

163á995

ИЛИ-НЕ 7 проходит через элемент И 12 на выход элемента 2(2И)-ИЛИ-НЕ 11.

Таким образом, во время формирования элемента "+1" последовательности на выходе элемента 2(2И)-ИЛИ-НЕ 11 бу5 дет сигнал низкого уровня, а на выходе

l элемента 2(2И)-ИЛИ-НЕ 10 — сигнал высокого уровня, поскОльку с ВыхОдя элемента НЕ 8 на первый вход элемента И 9 будет подавагься сигнал низкого уровня, зanрещающий прохождение через него тактового импульса с генератора 1 тактовых импульсов.

При формировании элемента троичной последовательности дешифратор 3 на выходах, соответствующих числам 0 и 1, выдает сигналы высокого уровйя кoTopbIe ПОступяют HB третий и первый (через элемент НЕ 8) входы элемента И 9 и разрешают пройти тактовому импульсу с генератора 1 тактовых импульсов на выход элемента

2(2И)-ИЛИ-НЕ 10, в результате чего 25 формируется на его выходе сигнал йизкого уровня. В то же время с элемента ИЛИ-НЕ 7 поступает на вход элемента И 12 сигнал низкого уровня, который зanрещает прохождение через него тактового импульса, а поэтому на выходе элемента 2(2И)-ИЛИ-НЕ 11 будет сигнал высокого уровня.

При формировании логическим преобразователем 4 последовательности по второму решающему правилу триггер !3 разблокируют и он начинает работать как счетный триггер, определяя четность и нечетность формируемых элементов последовательности. Когда производится формирование четных элементов последовательности, на втором (нулевом) выходе триггера 13 образуется сигнал высокого уровня, что 45 обеспечивает прохождение сигнала с выхода элемента И 12 на выход элемента 2(2И)-ИЛИ-НЕ 11, а сигнала с выхода элемента И 9 — на выход элемента 2(2И)-ИЛИ-НЕ 10. Когда же произ50 водится формирование нечетных элементов последовательности, сигнал высокого уровня с первого (единичного) выхода триггера 13 обеспечивает про- хождение сигнала с выхода элемента

H 12 на выход элемента, 2(2И)-ИЛИ-НЕ

10, а сигнала с выхода элемента И 9— на выход элемента 2(2И)-ИЛИ-НЕ 11.

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

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

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

2. Генератор по и. 1, о т л и— ч а ю шийся тем, что логический преобразователь содержит последовательно соединенные элемент ИЛИ-НЕ, элемент HE первый элемент И и первый элемент 2(2И)-ИЛИ-НЕ, первый вход которого соединен с первым входом второго элемента 2(2И)-ИЛИ-НЕ, второй и третий входы которого соединены соответственно с выходом второго элемента И и с первым выходом триггера, вход, которого соединен с первым входом второго элемента И и с вторым входом первого элемента И, третий вход которого соединен с вторым входом второго элемента И, третий вход которого соединен с выходом элемента ИЛИ-HE входы которого и третий вход первого элемента И являются группой входов логического преобразователя, .вход синхронизации которого соединен с входом триггера, второй выход которого соединен с че тв е рт ым в ход о м в то ро го элемен та

I0 соответственно с выходом второго элемента И и с первым выходом триггера.

2(2И)-ИЛИ-НЕ и с вторым входом первого элемента 2(2И)-ИЛИ-НЕ, третий и четвертый входы которого соединены

Составитель Ю.Бурмистров

Редактор В.Данко Техред Л.Сердюсова Корректор Т.Иалец

Заказ 824 Тиран 473 Подписное

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

133035, Иосква, Ж-35, Раувская наб. ° д. 4/5

Производственно-издательский комбинат "Еатент", г.уигород, ул. Гагарина; 101