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

ш

тУ

DC

Изобретение относится к вычис- лител)Ной технике и может использоваться в системах тестового диагностирования цифровых устройств. Целью изобретения является упрощение конструкции генератора. Устройство имеет тактовый вход 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 С/)

%Vl Фаг./

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

Цель изобретения - упрощение кон- струк1щи генератора.

На фиг,1 представлена структурная схема . генератора псевдослучайньсх пос- ледовательностей; на фиг.2 - пример конкретной реализации генератора для случая L 4, GF(L) {о,1,со,оз2, Ф(Х) ЩХ2 + X + 1, К 1j на; фиг„3 - пример конкретной реализации генера- тора для случая L 4, Ф(Х), ооХ2 + + X + 1, К 2; ,на фиг.4 - последо- вательность переключений регистров генератора, показанного на фиг.2; на фиг.5 - последовательность пере

Если какой-либо элемент сопровожающей матрицы V равен 0., то связь между соответствующими регистром и

блоком сложения отсутствует. Если какой-либо элемент сопровождающей матрицы V равен 1, то соответствующий

блок умножения осуществляет простую передачу сигналов со своих, входов на 40 выходы без изменения. Таким образом, число блоков умножения в i-й группе может принимать значения от 1 до N включительно.

Разрядность регистров 2, - 2 равна п.

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

45

50

l)

N На

im

.Qm(t)

+ Z

н

г X

та|

X ai«,a.

i 1,N,

ключений регистров генератора, показанного на фиг.З.

Устройство имеет тактовый 1 вход, содержит регистры 2 - 2, блоки 3- умножения в поле GF(L), где L 2, п i О - целое, блоки 4, -4, сложения в поле GF(L), дешифратор 5. N - степень образующего многочлена Ф(Х) + ... + а-Х + ... + а,Х + а- а,Х

примитивного над GF(L). Величина а- ,

т на которую происходит умножение в

га-м блоке умножения i-й группы (i-ю группу блоков умножения образуют блоки 3, подключенные к i-му блоку сложения 4;, i 1,N) определяется соответствующим элементом сопровождающей матрицы 7 1, где К - индекс децимации; - целое; Т - квадратная

д j

20 матрица порядка N вида Т. или Т,

2

0

5

где Q;(t) и Q;(t + 1) - содержимое i-ro регистра 2j соответственно в моменты времени t и (t + 1) (до и посл е прихода заднего фронта тактового им- пульса), а сигнал Z на выходе дешифратора равен 1, когда регистры 2,, г 2,, ..., 2,, ... 2ц, находятся в одном из состояний LO О О О Ч 0 и.-ГаГа а,..., af,..; , для а е ) и хотя бы одно из значений а; отлично от нуля.

Пусть L 4, Ф(Х) 03X2 + X + 1, К 1, Т Т,. В этом случае сопровождающая матрица имеет вид 1 11

0

(J

Пусть а О,

Oj

а --СО, тогда гене5

ратор будет иметь вид, показанный на фиг.2. Первый блок сложения реализован на двух сумматорах по модулю два (М2), второй -блок сложения на фиг. 2 не показан, так как на его вхады поступает лишь одно слагаемое и он осуществляет простую передачу сигналов со своих входов на выходы без изменения. Блок умножения на HJb реализо 1465885 4

ван на элементе ИСКЛЮЧАМЦЕЕ НШ1, де- ное число тактов относительно исходной шифратор - на элементе ИЛИ-НЕ. Раз- последовательности, и т.д. рядность каждого из двух регистров равна 2,Формулаизобретения

Пусть при тех же К 2. Тогда

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

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

5

0

5

0

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

аи- /б «е

tа;

.

f

/й;

,

.