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

 

Изобретение относится к вычислител)Ной технике и может использоваться в системах тестового диагностирования цифровых устройств. Целью изобретения является упрощение конструкции генератора. Устройство имеет тактовый вход 1,- содержит регистры 2, ...2), блоки 3 умножения в поле GF(L), где L 2, п 0 - целое, блоки 44...4f, сложения в поле GF(L), дешифратор 5. N - степень обраэующе , - ГО многочлена Ф{Х) а„Х ...+ i : + а;Х + + - примитивного. GF(L). Величина а , на которую происходит умножение в т-м блоке умножения i-й группы (i-ю группу блоков умножения образуют блоки 3, подключенные к i-му блоку сложения 4 , i 1,N) определяется соответствующим элементом сопровождающей матрицы V Т , где К - индекс децимации, - целое, а Т - квадратная матрица . Если какой-либо элемент сопровождающей матрицы равен О, то СВЯЗБ между соответствуннцим регистром и блоком сложения отсутствует. Если какой-либо элемент сопровождающей матрицы V равен 1, то соответствующий блок умножения осуществляет простую передачу сигналов со своих входов на выходы без изменения. Таким образом , число блоков умножения в i-й .группе может принимать значения от 1 до N включительно. Разрядность регистров 2;,...2(( равна п. 5 ил. S С/)

СОЮЗ СОВЕТСНИХ, СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (11) А1 (Я)1 С 06 Р 7/58

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

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

ПРИ ГННТ СССР (21) 4140891/24-24 (22) 30.10.86 (46) 15.03.89. Бюл. № 10 (71) Московский инженерно-физический институт (72) М.А.Иванов (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹ 1116431, кл. Н 03 М 13/02.

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

¹ 1251303, кл. Н 03 К 3/84, 1986. (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (57) Изобретение относится к вычислительной технике и может использо-ваться в системах тестового диагностирования цифровых устройств. Целью изобретения является упрощение кон" струкции генератора. Устройство имеет тактовый вход 1, содержит регистры

2„...2N, блоки 3 умножения в поле

GF(L), где L = 2", и > 0 — целое, блоки 41...4)(сложения в поле GF(L) дешифратор 5. N — степень обраэующе )

ro многочлена Ф(К) = а„Х + ... +

:+ а. Х + а Х + а — прймитивного.

1 о

GF(L). Величина а;, на которую про исходит умножение в m-м блоке умноь .жения i-й группы {i-ю группу блоков умножения образуют блоки 3, подключенные к i-му блоку сложения 4(, 1,N) определяется соответствующим элементом сопровождающей матрицы ,К

U = Т, где К вЂ” индекс децимации, К ) Π— целое, а Т вЂ” квадратная матрица. Если какой-либо элемент сопровождающей матрицы равен О, то связь между соответствующим регистром и блоком сложения отсутствует. Если какой-либо элемент сопровождающей матрицы U равен 1, то соответствующий блок умножения осуществляет простую передачу сигналов со своих входов на выходы без изменения. Таким образом, число блоков умножения в i-й .группе может принимать значения от до N включительно. Разрядность регистров 2„...2q равна и. 5 ил.

1465885 а4 а

1 0 ... 0

О О а 2. а„

О 1 ... О

0 0

0 О ... О

О О ао

Т, О 0

cl Q а а, а ао ак а и-

° а а аG ая» ха;„аф, i=1,N, Изобретение относится к вычислительной технике и может использоваться в системах тестового диагностирования цифровых устроиств.

Цель изобретения — упрощение конструкции генератора °

На фиг.1 представлена структурная ,схема генератора псевдослучайных пос- 10 ледовательностей; на фиг.2 — пример конкретной реализации генератора для случая ь - 4, GF(L = (о,1,ы,и 3

Ф(Х) =ЯХ + Х+ 1, К = 1; на фиг 3— ,пример конкретной реализации генера тора для случая L = 4, Ф(Х),= дХ + + Х + 1, К = 2,на фиг.4 — последо вательность переключений регистров генератора, показанного на фиг.2; на фиг.5 - последовательность переЕсли какой-либо элемент сопровождающей матрицы V равен О.„ то связь между соответствующими регистром и

35 блоком сложения отсутствует. Если какой-либо элемент сопровождающей матрицы V равен 1, то соответствующий блок умножения осушествляет простую передачу сигналов со своих входов íà 40 выходы без изменения. Таким образом, число блоков умножения в х-й группе может принимать значения от 1 до N включительно.

Разрядность регистров 2, — 2 „ g5 равна и.

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

И Н

Q;(t+1) = a; Q (t) + Z °, . х

th =-4 йя л l ключений регистров генератора, показанного на фиг.3.

Устройство имеет тактовый I вход, содержит регистры 24 — 2H блоки 3 умножения в поле GF(L), где L = 2

n Π— целое, блоки 4„ — 4 сложения в поле GF(L), дешифратор 5. N —степень образующего многочлена Ф(Х) и

=а4Х+...+аХ +...+аХ+а

1 4 о примитивного над GF(L). Величина а;„, на которую происходит умножение в

m-м блоке умножения i-й группы (i""þ группу блоков умножения образуют блоки 3, подключенные к i-му блоку сложения 4;, i = 1,N) определяется соответствующим элементом сопровождающей к матрицы V = Т, где К вЂ” индекс децимации; К 0 — целое; Т вЂ” квадратная матрица порядка N вида Т или Т

1 2F где Q (t) и 0; (t + 1) — содержимое

i-го регистра 2; соответственно в моменты времени и (t + 1) (до и после прихода заднего фронта тактового им- пульса), "а сигнал Z на выходе дешифратора равен 1, когда регистры 2,, 2 2 2;, ..., 2 g находятся в одном из состояний 10 О О ... О...

1 Ф + %01 или -:Га,а а, ... а з ° ° ° ° ° а„), для а „ < GF(L) и хотя бы одно иэ значений а, отлично от нуля.

Пусть L = 4, Ф(Х) = ИХ + Х +

К = 1 Т = Т, . В этом случае сопровождающая матрица имеет вид

1 1

Q О

Пусть а, = О, а = у,. тогда гене+ ратор будет иметь вид, показанный на фиг.2. Первый блок сложения реализован на двух сумматорах по модулю два (И2), второй блок сложения на фиг.2 не показан, так как на его входы поступает лишь одно слагаемое и он осуществляет простую передачу сигналов со своих входов на выходы без изменения. Блок умножения на И реалиэо3 1465885 4 ван на элементе ИСКЛЮЧАЮЩЕЕ ИЛИ, де- ное число тактов относительно исходной шифратор — на элементе ИЛИ-HE. Раз- последовательности, и т.д. рядность каждого из двух регистров равна 2.

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

Пусть при тех же 1, Т и Ф(Х), К = 2. Тогда

1 1

Фиг. 2

G3 О И 0

Пусть а» = О, а = Q тогда гене4. ратор имеет вид, показанный на фиг.З.

Каждый из блоков сложения реализован.на двух сумматорах по модулю два (M2). Дешифратор реализован на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ и ИЛИ-НЕ.

Таким образом, положительный эффект от использования изобретения заключается в упрощении конструкции генератора: из схемы устройства исключены элементы И, ИЛИ-НЕ, 0+1 дешифраторов. Аппаратные затраты íà у5 реализацию генератора не зависят от величины К, что позволяет использо-. вать устройство для формирования

L-ричных последовательностей длиной

S L, многоразрядных L-ричных псев- З

Ф дослучайных чисел,для формирования последовательностей сдвинутых на эаданГенератор псевдослучайных прследовательностей, содержащий N регистров, где N — степень образующего многочлена, N блоков сложения, N групп блоков умножения»и дешифратор, причем вькоды блоков умножения i-й группы (i = 1,N) соединены с соответствующими группами входов i-го блока сложения, выходы которого соединены с информационными входами i-го регистра, выходы j-х регистров (j = 1, (N-1) ) соединены с соответствующими группами входов дешифратора, тактовые входы регистров объединены и образу ют тактовый вход генератора, группы выходов регистров образуют группу информационных выходов генератора, отличающийся тем, что, с целью упрощения конструкции,генератора, группа выходов N-го регистра соединена с соответствующей группой входов дешифратора, выход которого соединен с разрешающими входами блоков сложения, выходы i-x регистров соединены с входами i-х блоков умножения соответствующих -групп.

1465885

9У

fó2

Составитель С. Старчихин

Техред А. Кравчук Корректор С.Шекмар

Редактор И.Сегляник

Заказ 948/50

Тираж 667

Подписное

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

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

Производственно-издательский ком5инат "Патент", г. Ужгород, ул. Гагарина,1Ñ1