Генератор L-ичных последовательностей Советский патент 1988 года по МПК G06F1/02 

Ф

(Л

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

а ел

00 Од

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

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

На фиг.1 представлена схема генератора; на фиг.2а,б - примеры реализации генератора входных воздействий на фиг.З - пример реализации блока ускоренного деления многочленов; на фиг.4,5 - реакция блока ускоренного деления многочленов на входные наборы; на фиг.6,7 - последовательные соединения триггеров блока фиг.З.

Генератор (фиг.1) содержит установочный 1 и тактовый 2 входы, счетчик 3 по модулю , генератор 4 входных воздействий и блок 5 ускоренного деления многочленов, который содержит узлы 6 умножения, узлы сложения 7 и деления 8, N регистров 9, где N - степень образующего многочлена ф(х).. ..а.х + . . .а,х+ао, а-а е eGF(L).

45

40

. Блок ускоренного деления многочленов осуществляет деление на многочлен Ф(х), которым является определитель .матрицы Т - ХЕ, где Е - единичная матрица.

На фиг.2а и б показаны два варианта построения генератора входных воздействий. Разрядные выходы счетчиков 10 по модулю L являются выходами генератора входных воздействий, тактовый вход которого соединен со счетным входом счетчика 10, а каждый Ь-й импульс, поступающий на счетный вход i-ro счетчика 10-, ,(K-1), появляясь на его выходе, поступает на счетный вход (i + 1)-ro счетчика 10;. Струк55 тура генератора входных воздействий, показанная на фиг.26, аналогична структуре генератора в целом (фиг.1);

50

Узлы сложения, умножения и деления представляют собой комбинационные схемы, которые строятся на основе соответствующих им таблиц истинности, последние в свою очередь однозначно определяются правилами сложения, умножения и деления в поле Галуа из L элементов. Величина, на которую про- Q исходит умножение в i-м узле умножения каждой группы узлов 6 умножения, определяется соответствующим коэффициентом а. образующего многочлена. Узел 8 осуществляет деление на - а в поле 5 GF(L) . При лог. О на своих входах блок ускоренного деления многочленов функционирует в соответствии с уравнением

Q(t-H) q(t).TS 0 где Q(t + 1) Cqi(t-H)...q,(t + 1) .;.

- qN(t+i);

Q(t)qi(t)...q,(t)...q(t); qj(t) и q-(t+1) - содержимое i-го регистра 9 . соответ5ственно в моменты

времени t и (t+1); Т - квадратная матрица порядка N, вида

11 - счетчик по модулю 8 ь -1 ; 12 - генератор входных воздействий, 13 - блок ускоренного деления многочленов, степень образующего многочлена которого равна К. Выходы регистров блока 13 ускоренного деления многочленов 14; () поступают на узлы 7 сложения. Генератор 12 входных воздействий в свою очередь также может иметь структуру, аналогичную показанной на фиг.26, и т.д.

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

о или на 1, поэтому на фиг.З показаны. Узел 8 осуществляет де10

15

20

25

являются состояния L, (L+1),...,

..., v ) какого-либо из регистров 9v, -9 fj) .

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

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

rq,(t+1)d(t)® qjCt) ®q|t);

U(t+1)qi(t);

U5((t),

выполняются за такта. Уравнения, блока ускоренного деления многочленов, показанного на рис.3, имеют следующий вид:

rqi(t+1)d5(t)@di(t)€tj5(t)+q(t)®qi(t); lq(t+1)dj(t) ) + ); , . q5(t+1)) ®q j(t) ©q.j(t) .

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

Пусть начальное состояние триггеров 9,-9з равно 7 (111). Прежде чем перейти непосредственно к описанию работы устройства, рассмотрим реакцию блока ускоренного деления многочленов, показанного на фиг.З, на различные входные наборы d,d,d j (фиг.4,5),

Столбец 1 на фиг.4 соответствует ситуации, когда , О 0 const. Колонки А и В соответствуют обычному устройству для деления многочленов (см. первую из приведенных выше систем уравнений): А - последовательность на входе (1) d(2)... d(t)... didjdjd,d,;d. ..,d(t) еЛО.П; Н- состояние регистра сдвига устройства (). Последовательные состояния триггеров устройства, показанного на фиг.З, обведены. В колонке С показана диаграмма переходов блока ускоренного

30

40

45

50

55

10

15

6586

деления многочленов для рассматриваемой ситуации (коды О О О ... 1 1 1 обозначены соответственно О ... 7). Столбцы 2 - 4 на фиг.4 и столбцы 1 - 4 на фиг.З соответствуют случаям, когда наборы d d dj const и равны соответственно 010, 11 О,001, 101, 011,111,000.

На фиг.6 показаны последовательные состояния триггеров устройства, показанного на фиг.З, когда на его входы с выходов счетчика на триггерах 10, 10-1, Юз приходят коды О, 1, 2,...,7. Строка А - состояние

0

5

; .

0

40

45

50

счетчиков ния

10, 10,

10

q.q q триггеров

3

1

в 9,

состоя3

из

55

которых при данном фикс.грованном значении набора dfd-j dj Триггеры выйти не могут; С - последовательные состояния триггеров (q,q,2q3) 9,,9,,9з при заданном значении входного набора d-fd-id,.

Таким образом, первые тактов на входе блока ускоренного деления многочленов - код О О О, а триггеры устройства, показанного на фиг.З, последовательно проходят все состояния от 7 до 2 (1-й столбец на фиг.6). Появляющийся на выходе счетчика 3 седьмой тактовьм импульс переключает счетчики 10, ,10,10л| генератора вход- .ных воздействий в состояние 1 (на входах блока ускоренного деления многочленов - код 1 О 0) и следующие 7 тактов триггеры 9 ,9,j ,9 будут находиться в состоянии О 1 0(2) (2-й столбец на фиг.6). Следующие 7 тактов счетчики 10,, 10,, Юз будут находиться в состоянии 2 и триггеры 9,, 9, 9 последовательно проходят все состояния от 2 до О (3-й столбец на фиг.6). Все указанные переключения триггеров 91,9г,9з отражены на фиг.7 следующим образом: 7-22-22-0. Последовательность дальнейших переключений отражена также на фиг.7, из которой видно, что период формируемой последовательности, снимаемой с выходов одного из триггеров (в общем случае с одного из регистров 9), имеет период M(L -1) () Ь(2з-1) ()-23 7-7-8 392.

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

Генератор L-ичных последовательностей, содержащий блок ускоренного деления многочленов, причем выходы блока ускоренного деления многочлсJ

i

I Ф

/45r

/УАГ

7f 7

о о о 1 о о

010

ПГ

000 000

о о о

о

1

о

1

1

о

1

/

о

1

1

о

1

1

о

1

1

о

1

0Q 0

1О О 1 1 о

г/тп

/ / / / / /

ITTTI / о 1 о 1 о

ГТУП о 1 о

001

ТТ

010 011

о о 1

000 1 00

о 1 о

001 000

00 0 Фи.Ц

о о 1 о о 1

о о 1 о о i о

о 1 о о 1 о о 1

о о о

000 000

Г7ТП

01 о

101

/ о 1

1 1 о

TTJ

001 100

FTTgl

/ / / oil

1 о 1 1 1 о

11 /

111

о 1 1

001

о о о

и/л

о 1 1

001

01 о

101

УГГо

11 1

01 1

100 01 о

/ / о 111

0о 1

1о о

о 1 1}

1 о 1 1 1 о

Сриг.5

11 л

г) 2-5

7- J 3-11- 5 5-3

33-5

55-г (7-7) 5- 5-3 СЗ-ЗЭ / -3 7-5 5-7 5-/ Т / - (-V -2 «-5 5-5 5-г 2-7 (7

Фи9.6

3

(7-7) 5- 5-3 СЗ-ЗЭ / -3 7-5 5-7 5-/ Т / - (-V -2 5 5-5 5-г 2-7 (7