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

 

Изобретение относится к вычислительной технике и может использоваться в системах тестового диагностирования дискретных объектов. Цель изобретения - расширение класса решаемых задач за счет увеличения периода формируемой последовательности. Генератор содержит установочный 1 и тактовый 2 входы, счетчик 3, генератор 4 входных воздействий и блок 5 ускоренного деления многочленов. Поставленная цель достигается за счет введения счетчика 3 и генератора 4 входных воздействий. 7 ил.

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

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

РЕСПУБЛИН (51) 4 С 06 F 1/02

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

1М4

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

"" " 4

Фиг.! (21) 4122342/24-24 (22) 22. 09. 86 (46) 30. 06. 88. Вюл. У 24 (72) А.М. Дисман, А.А. Иванов и М.А.Иванов (53) 681.325 (088.8) (56) Электроника, 1977, У 5, с.23-33.

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

И- 1185338, кл. G 06 F 11/00, 1985. (54) ГЕНЕРАТОР L-ИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕИ (57) Изобретение относится к вычисли„„SU„„1406586 А 1 тельной технике и может использоваться в системах тестового диагностирования дискретных объектов. Цель изобретения — расширение класса решаемых задач за счет увеличения периода формируемой последовательности. Генератор содержит установочный 1 и тактовый 2 входы, счетчик 3, генератор 4 входных воздействий и блок 5 ускоренного деления многочленов. Поставленная цель достигается за счет введения счетчика 3 и генератора 4 входных воздействий. 7 ил.

1406586

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

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

На фиг. 1 представлена схема генератора; на фиг.2а,б — примеры реализации генератора входных воздействий !

Э на фиг.3 — пример реализации блока ускоренного деления многочленов; на фиг.4,5 — реакция блока ускоренного деления многочленов на входные набо-! ры; на фиг.6,7 — последовательные соединения триггеров блока фиг.3.

Генератор (фиг.1) содержит установочный 1 и тактовый 2 входы, счетчик 20

3 по модулю Б=L — 1, генератор 4 входН ных воздействий и блок 5 ускоренного деления многочленов, который содержит узлы 6 умножения, узлы сложения

7 и деления 8, N регистров 9, где 25 . N — степень образующего многочлена у ф(х) =а,! х ... а; х + ° .. а, х+а „, а; а, E

EGF(L) .

1 0 ... 0 а .а, а, а ар 1 а ацафаф а ф

1 0 ° . ° 0 0

0 1 а

0 а, 0 или T = ан0 ао

0 .. ° 1

° ° Э ° ° ° ° ° ° ° ° °

0 0 ... 0 ан а

0 0 ... 1 0

11 — счетчик по модулю S =L — 1; 12

k генератор входных воздействий, 13 блок ускоренного деления многочленов, степень образующего многочлена которого равна К. Выходы регистров блока

13 ускоренного деления многочленов

14; (i=1,K} поступают на узлы ?; сложения. Генератор 12 входных воздействий в свою очередь также может иметь структуру, аналогичную показанной на фиг.2б, и т.д.

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

Регистры 9 блока ускоренного деления многочленов устанавливаются в одно из уазрешенных состояний (запрещенными

Блок ускоренного деления многочленов осуществляет деление на многочлен

Ф (х), которым является определитель матрицы Т вЂ” XE, где Š— единичная матрица.

На фиг.2а и б показаны два варианта построения генератора входных воздействий. Разрядные выходы счетчиков

10 по модулю L являются выходами генератора входных воздействий, такто50 вый вход которого соединен со счетным входом счетчика 10„, а каждый L-й импульс, поступающий на счетный вход

i-ro счетчика 10, i=1 (К-1), появляясь на его выходе, поступает на счетный вход (+1)-го счетчика 10;,„. Струк

55 тура генератора входных воздействий, показанная на фиг.2б, анапогична структуре генератора в целом (фиг.1);

Узлы сложения, умножения и деления представляют собой комбинационные схемы, которые строятся на основе соответствующих им таблиц истинности, последние в свою очередь однозначно определяются правилами сложения, умножения и деления в поле Галуа иэ элементов. Величина, на которую происходит умножение в i-м узле умножения каждой группы узлов 6 умножения, определяется соответствующим коэффициентом а образующего многочлена. Узел !

8 осуществляет деление на — а в поле о

GF(L) . При лог. "0" на своих входах блок ускоренного деления многочленов функционирует в соответствии с уравнением ((г+1)C3(t)Т9

rpe Q(t+1) = (q,(t+1)...q (t+1) . .... qH(t+1)3;

q(t) = h1(t) ° ° ° q1(t) ° ° ° qN(t)

Ч -(t) и q;(t+1) — содержимое х-го регистра 9 . соответ1 ственно в моменты времени t и (t+1);

Т вЂ” квадратная матрица порядка И, вида

1406586

45

55 являются состояния 1., (1.+1),... део,к ..., (2 -1) какого-либо из регистров 9„-9 ) .

На фиг.3 показана схема блока 5 ускоренного деления многочленов для случая K=N=3, 1 =2, Ф (х)=х +х +1. Все узлы умножения осуществляют умножение

1на "О" или на "1", поэтому на фиг.3

10 не показаны. Узел 8 осуществляет деление на "1", поэтому также не показан. Регистры 9;, i=1,N, разрядность которых в общем случае равна 31og L5 вырождаются в триггеры, так как

)1о8 23=1. В рассматриваемом устройстве за один такт выполняются преоб. разования, которые в обычном устройстве для деления многочленов, соответствующем уравнениям:

q (t+1) =d(t) е Ч,(t) eqft);

q,(t+1)=q (t);

qэ("1) =q, (с), выполняются за К=З такта. Уравнения, блока ускоренного деления многочле- 25 нов, показанного на рис.3 имеют следующий вид:

q, (t+1) =dэ Ж Эа (t)® Ы+Ч,() ®ц, И);

q (t+1)=d,,() ЕЧ ()+ q ()

q,(t+1)-d () O+q,(t) Oq () °

Рассмотрим работу генератора на примере случаев, рассмотренных на фиг.2а и 3. Каждый счетчик 10 в рассматриваемой ситуации вырождается в триггер, и поэтому фактически гене-, ратор входных воздействий можно рас- З5 сматривать как трехразрядный двоичный счетчик. Счетчик 3 считает по модулю

1 2з 1 7 и

Пусть начальное состояние триггеров 9, -9 равно 7 (111) . Прежде чем

40 перейти непосредственно к описанию работы устройства, рассмотрим реакцию блока ускоренного деления многочленов, показанного на фиг. 3, на различные входные наборы d, d ф > (фиг. 4, 5), Столбец 1 на фиг.4 соответствует ситуации, когда d „д д =О О 0=. const.

Колонки А и В соответствуют обычному устройству для деления многочленов (см. первую из приведенных выше систем уравнений): А — последовательность на входе D=d(1) d(2) Й(t) ° ° .=

1,d 1 2 3. ° » () 1 3 состояние регистра сдвига устройства (q q q ) . Последовательные состояния триггеров устройства, показанного на фиг.3, обведены. В колонке С показана диаграмма переходов блока ускоренного деления многочленов для рассматриваемой ситуации (коды О О О ... 1 1 1 обозначены соответственно О ... 7).

Столбцы 2 — 4 на фиг.4 и столбцы 1 — 4 на фиг.5 соответствуют случаям, когда наборы d,d d>=const и равны соответственно О 1 О, 1 1 О, О О 1, 1 О 1, О 1 1, 1 1 1, О О О.

На фиг.6 показаны последовательные состояния q„q 1 триггеров устройства, показанного на фиг.3 когда на

его входы с выходов счетчика на триггерах 10„, 10, 10З приходят коды

О, 1, 2, ..., 7. Строка А — состояние счетчиков 10„, 10, 10 з,  — состояния и о о триггеров 9,, 9, 9, из которйх при данном фикс.IpoBBHHQM значении набора d,d с1з триггеры выйти не могут; С вЂ” последовательные состояния триггеров (q,q q ) 9,,9,9> при заданном значении входного набора с1,д,й з.

Таким образом, первые S =7 тактов на входе блока ускоренного деления многочленов — код О О О, а триггеры устройства, показанного на фиг.3 последовательно проходят все состояния от 7 до 2 (1-й столбец на фиг,6).

Появляющийся на выходе счетчика 3 седьмой тактовый импульс переключает счетчики 10,,10,10 генератора входных воздействий в состояние 1 (на входах блока ускоренного деления многочленов — код 1 О О) и следующие

7 тактов триггеры 9,9,,9 будут находиться в состоянии О 1 0(2) (2-И столбец на фиг.6). Следующие 7 тактов счетчики 101, 10, 10 > будут находиться в состоянии 2 и триггеры 91, 9, 9 последовательно проходят все сосЭ таяния от 2 до О (3-й столбец на фиг.6). Все указанные переключения триггеров 91,9,9 отражены на фиг.7 следующим образам: 7 — 2 2 — 2 2 — О.

Последовательность дальнейших пере-. ключений отражена также на фиг.7, из которой видно, что период формируемой последовательности, снимаемой с выходов одного из триггеров (в общем случае с одного из регистров 9), имеет (1 " 1) I,N=(2 1) (2

-1) . 2з =7 . 7. 8=392

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

Генератор L-è÷íûõ последовательностей, содержащий блок ускоренного

1деления многочленов, причем выходы блока ускоренного деления многачл»5 14(16586 6 нов подключены к выходу генератора, воздействий, причем тактовый вход установочный и тактовый входы кото- генератора подключен к счетному входу рого подключены к установочному и счетчика, выход которого подключен тактовому входам блока ускоренного к тактовому входу генератора входных ения многочленов о т л и ч а ю — воздействий, выходы которого; подклюя тем что с целью расшире- чены к входам блока ускоренного де ния класса решаемых задач за счет ления многочленов, установочные входы возможности увеличения периода форми- счетчика и генератора входных воздей, руемой последовательности, в него 0 ствий подключены к установочному вхо-! введены счетчик и генератор входных ду генератора.

7к (7

1406586

111

707

00 1 оо а

)1о 1)

1 01 sr о)

011

007 а а)

f10

117

Д 111)

10 7

110 1f

111

071 ап

000

I I I

III! ooа

0 f00

1 010 oî oÄ

0 Ооо

0 0.0 to о

1 f11

П :1! )

0 111

011 ro Ä

0 010

1 101

1 (ДДД

0 аа1

1 100

1 ) 11о)

01

1 001 оо о

1 00 or o)

01

0 10

Яа1)

01 7 ОО 1)

110 rr

017

107 rr o

111

111 or rÄ

001

I I I

000 оп à) о ооо

100 »о

1f1 ССЛ!

071.

101 а or а)

-1а1

010

710 O! t1) аo1

000 пап

О 10

007

Д аоя

Д а а) f0O

1 0!! 1!) 1

1 f 1 a !

1 01

О1О

) а1) 010

001 ro о

010

01 1 Оо 1) Оаа

100 (о Д) 001

000

Да п) Риг. 4 oo o) 00

170 а! 1)

701 а 10

)а а!) ааа

100 < а)

011

)а! а

001

000 !оп

1 10

01 1 10 /)

001

) па о) о

О

0

0

0

0

О

О

Р

0

О д

О oo o)

О 00

000 ro а)

01 0

101 or o

101

11 О

Е11)

00f

f00

)11! 1а

111

011 or !

f0

111

) 111)

011

007

0 1!)

017

001 ro о а10

101 (1:! о)

f17

011 оо 1)

10 0

01 0 <î

1 11 o< ()

О01

100 or и

107

110 11 !3

1406586

6 7 Д

5 7 д

0 2

70 Э "1 1 8 26

4 Л 30 г-з (7 (з з) з-т -з

5 7 7б б 1

10 ОФ Ф2

2 и

0 7

3 2 б 3

7 $

11 -е7

ZP ((«до ua7"

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

Техред N.Ходанич Корректор В.Гнрняк

Редактор А. Маковская

Заказ 3194/44 Тираж 304 Подписное

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

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

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

1 2 3 0

0 2 lf 6 1 р

4 0 О 0

4 2 7 0 1 б

3 7 д 5

s p

2 1 3 3 7

Риа Р

О О д

2 б

2 з и

lу 5