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

 

Изобретение относится к вычислительной технике и может использоваться в системах тестового диагностирования в качестве источника входных воздействий. Цель - увеличение периода формируемых последовательностей, что достигается благодаря введению в генератор, содержащий N регистров 6, где N - степень образующего многочлена с коэффициентами из поля GF (L),блок 4 сложения, блок S деления, Р-блоков 3 умножения (Р N) , преобразователь 2 кодов, счетчика 1 с соответствующими связями. Устройство формирует L-ричную последователь-, ность длиной т(Ь - I), где m - длина повторяющегося фрагмента управляющего воздействия. 4 ил. i (Л С

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

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

РЕСПУБЛИН (19) (11) А1

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

Н А BTOPCHOMY СВИДЕТЕЛБСТВУ

1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 41 22768/24-24 (22) 22.09.86 (46) 15.04.88. Вюл. !! !4 (72) М.А.Иванов, А.М.Дисман, А.А.Иванов и В.Г.Тьппкевич (53) 681.3 (088.8) (56) Гордон, Hagur. Локализация неисправностей в микропроцессорных системах при помощи шестнадцатирич- ных ключевых кодов. — Электроника, 1977, У 5, с.23-33.

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

9 1116431, кл. Н 03 М !3/02, 1984. (11 4 Н 03 M 13/02,G 06 F 1/02 (54) ГЕНЕРАТОР TECTOBbIX ПОСЛЕДОВАТЕЛЬНОСТЕЙ (57) Изобретение относится к вычислительной технике и может использоваться в системах тестового диагностирования в качестве источника входных воздействий. Цель — увеличение периода формируемых последовательностей, что достигается благодаря введению в генератор, содержащий И регистров

6, где N — - степень образующего многочлена с коэффициентами из поля GF (L),áëîê 4 сложения, блок 5 деления, P-блоков 3 умножения (P < cN), преобразователь 2 кодов, счетчика 1 с соответствующими связями. Устройство формирует L-ричную последователь-. ность длиной m(L 1), где ш — длина повторяющегося фрагмента управляющего воздействия. 4 ил.

1388999

s2 (t+ 1 ) = Й (г. ) Т, а

1 0 а р

a ° ° О

0 1 ... 0 а„ ан

0 О ... 1, а „а, g GF(L) ар

0 0 ... 0 ар

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

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

На фиг.! приведена схема генера- 1О

1 тора; на фиг.2 - 4 — примеры реализации преобразователя кодов.

Устройство содержит. счетчик 1, преобразователь 2 кодов, блоки 3 умножения, блок 4 сложения, блок 5 деления и регистры 6.

На фиг.1 показан также тактовый вход 7 устройства.

Устройство работает следующим образом. 20

Перед началом работы все регистры 6 и счетчик 1 устанавливаются в нулевое состояние„ Регистры 6 устаСчетчик 1 н преобразователь 2 кодов вводятся в состав устройства для формирования на последней группе 40 входов блока 4 сложения периодических управляющих воздействий.

На фиг.2 показана структурная схема преобразователя, формирующего управляющие воздействия произвольного вида, содержащего группы 8; управляющих входов преобразователя, на которых задается код j --ro символа управляющего воздействия, дешифратор 9, элементы И 10.

Если в качестве счетчика 1 исполь- 50 эуется, например, трехразрядный счетчик по модулю m = 7, à L = 5, 9(X) образующий многочлен, примитивный над полем GF (5), период формируемой последовательности становится равным S = m (L — 1) = 7(5 -1) = 168.

Для сравнения можно указать, что период пятиричной последовательноснавливаются в одном из разрешенных состояний. Запрещенными являются, например, состояния Ь,(L+1),..., 1Ер, ( (2 1) какого-либо иэ регистров 6. Установочный вход устройства на фиг.1 не показан.

При "0" на всех выходах преобразователя 2 устройство работает обычным, . образом в соответствии с уравнением где Q (t+I) =(Q,(с+1) ...Q„(t+1) ... ...Qz(t+!); 52(с) = (Я,(t)

"."Q;(t) " Q.(t)), Q (с) и Q; (с+1) — содержимое

i.-ro регистра, i 1,N, соответственно в моменты времени г и (t+1) (до и после прихода соответствующего тактового импульса), а Т— сопровождающая матрица вида (ти, формируемой обычным генератором с таким же количеством последовательностных элементов (равным 9), равен лишь S = 5 - 1 = 124. С увеличением

2

N разница между S и S2 возрастает. Если необходимо сформировать управляющее воздействие определенного вида, то преобразователь 2 имеет вид, показанный на фиг.3, и содержит дешифратор 11 и элементы ИЛИ 12 число которых и « ) log2LE.

Другой возможный путь — реализация преобразователя 2 на основе ПЗУ, адресные входы которого становятся входами преобразователя, а выходы— выходами преобразователя. В простейших случаях, при малых m и L, преобразователь 2 кодов можно построить, используя известные методы синтеза комбинационных схем, например, метод диаграмм Вейча.

1388999

На фиг.4 показан пример построения преобразователя 2, содержащего дешифратор, который реализован на элементе И 13 и элементе ИЛИНЕ 14, элементе ИЛИ 15, формируемое воздействие имеет вид 3222223 (для 3-х разрядного счетчика по модулю 7 и ) log Lt = 3)

Рассмотрим периодические свойст- 1О ва формируемых последовательностей.

Определение 1.

Последовательность L-ричных чисел, поступающих на входы генератора

1 блоки 3,4,5 и регистры 6), называет- 15 ся управляющей последовательыостьюА Определение 2.

Повторяющийся фрагмент 6 управляющей последовательности, где

G -б,G,...G> ...6,G> 6 GF(L)j го

=1,ш, имеющий минимальйую длину m, называется элементарным входным воэ действием.

Известно, что устройство, содержа. щее блоки 3,4,5 и регистры 6, осу- 25 .ществляет деление многочлена после"

I довательностей, поступающих на последнюю группу входов блока сложения, на многочлен, инверсный по отношению к образующему многбчлену 9 (Х) .Ис- 30 пользуя это свойство, можно доказать следующие теоремы.

Теорема 1.

Максимальный период формируемой н последовательности равен m(L -I), где Н вЂ” степень образующего иногочлена, примитивного над полем GF(L).

Теорема 2.

Пусть задан многочлен А(Х) степени и + P вида 40

А(Х) o(X"(Õ + Х +...+Х +1), oLE GF(L), о(Ф О, P = 0 — целое.

Если (n+m) = 0(mod(L -1)), то многоtl 45 член А(Х) делится без остатка на лю- бой многочлен степени N, примитивный над полем GF(L).

Теорема 3.

Если образующий многочлен Р(Х) генератора является примитивным над полем GF(L), а н.о.д.((L 1),m) l, то формируемая последовательность является последовательностью максимальной длины. 55

Теорема 4.

Если удовлетворяются условия теоремы 2 и G (X) (где б (Х) — многочлен, соответствующий элементарному входному воздействию) делится без остатка на У (Х), то нулевое состояние всех регистров генератора одновременно не входит в полное кодовое кольцо децимаций по индексу m состояний генератора.

Теорема 5 °

Символы любой формируемой последовательности можно представить в виде (11 (i) (11

o(. d; + к Dd; +...+и В d; +

m-i (11

+...+ (П Д, E GF (L) — оператор задержки на j тактов; — i-й элемент последовательности, формируемой под воэр действием А, состоящей из (i). фрагментов вида G

1 0 О ... О.

>/le

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

Следует отметить, что последовательности, формируемые генератором, на входы которого поступают периодические управляющие воздействия, обладают качественно новыми свойствами по сравнению с обычными M-последовательностями, которые являются простейшими частными случаями рассмотренных при ш = 1.

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

Генератор тестовых последовательностей, содержащий И регистров (N — степень образующего многочлена с коэффициентами из поля 0Р(Ь)), блок сложения в поле GF(L),áëîê деления в поле GF(L), P блоков умножения в поле GP (L) (P N), ïðè÷ åì тактовый и установочный входы генератора подключены к тактовым и установочным входам регистров, выходы регистров, соответствующих ненулевым коэффициентам образующего многочлена, подключены через соответствующие блоки

1388999 умножения к P входам блока сложения, выход которого через блок деления подключен к информационному входу первого регистра, выходы i-х регистров (i 1 (N-1)) подключены к информационным входам (ь.+1)-х регистров ! отличающийся тем, что, с целью увеличения периода формируемых последовательностей, в него введены счетчик и преобразователь кодов, причем тактовый и установочный входы генератора подключены к тактовому и установочному входам счетчика, выход которого через преобразователь кодов подключен к (Р+1) -му входу блока сложения.

1388999

Составитель С.Курош

Редактор M.Öèòêèíà Техред Л.Олийнык Корректор И.Муска

Заказ 1585/56 Тираж 928 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4