Устройство для контроля двоичных последовательностей

 

УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащее два регистра, отличающееся тем, что, с целью повьшения быстродействия, оно содержит блок сложения по модулю L, где L простое число, лежащее в интервале

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

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

РЕСПУБЛИК (19) (11) g 1) С 06 F 11/12

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ члена, причем разрядность каждого ре(1,если L=2, гистра равна М, где М=1, 1,,2

1,(n+1), если 1.) 2, выходы блока сложения ло модулю Ь соединены с соответствующими входами блока деления на L-а, выходы которого соединены с соответстгующими ин-формационными входами первого регистра, аыхады каждого i-го регистра, где i=1, (N-1), соединены с информационными входами (i+1)-ro регистра г и со входами операнда i-ro блока умножения по модулю L, выходы N-ro регистра соединены с соответствующими входами N-ro блока умножения по модулю L выходы j-х блоков умножения по модулю L, где j=1,N, соединены с соответствукнцими входами j é группы блока сложения по модулю L, контролируемые входы устройства соеди- "" нены с соответствующими входами (М +

+1) — и группы блока сложения по модулю

L, вход старшего разряда (N+1)-й группы которого соединен с шиной ну- ) левого потенциала, тактовый вход уст- )eall ройства соединен с тактовыми входами )аале регистров. Cb (21) 3594018/18-24 (22) 20.05.83 (46) 30.09.84. Бюл. №- 36 (72) М.А.Иванов (71) Московский ордена Трудового

Красного Знамени инженерно-физический институт (53) 681.3(088.8) (56) 1. "Зарубежная.радиоэлектроника", 1979, ¹ 1, с. 53.

2. Авторское свидетельство СССР № 792256, кл. G 06 F 11/08, 1979 (прототип) . (54) (57) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ

ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащее два регистра, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия, оно содержит блок сложения по модулю Ь, где L простое число, лежащее в интервале (2", 2 "), а п — число контролируемых входов устройства, N — 2 регистров, где Ы вЂ” степень неприводимого многочлена, N блоков умножения по модулю

L, блок деления íà L-a, где а 0— свободный член неприводимого многоОПИСАНИЕ ИЗОБРЕТЕНИЯ Й 13

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

OA.!.,;..., .,ж, Ф 11164

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

1цифровых объектов.

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

ra а первый вход — с входом устройства, остальные входы сумматора по модулю два соединены с выходами соответствующих разрядов регистра сдвига, причем номер разряда, к которому 5 подключается соответствующий вход сумматора по модулю два, определяется показателем степени соответствующего члена неприводимого многочлена, синхронизационный вход устройства соединен с шиной сдвига регистра, выходы которого являются выходами устройства j1 ).

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

Наиболее близким к изобретению является устройство, содержащее счет30 чик, преобразователь параллельного кода в последовательный и регистр сдвига с сумматором по модулю два в цепи обратной связи (2 j.

I

Недостатком данного устройства яв-35, ляется низкое быстродействие.

Целью изобретения является повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для контроля двоич- 40 ных последовательностей, содержащее два регистра, введены блок сложения по модулю L, где L — простое число, лежащее в интервале (2", 2""), а n— чиспок онтролируемых входов устройств а 45

Ф . N — 2 регистров, где N степень неприводимого многочлена, N блоков умножения по модулю Ь, блок деления на L-ао, где а - свободный член неприводимого многочлена, причем раз- 50 рядность каждого регистра равна И, Г1, если L-2, где М= .,, выхоцы блока (n+1) åñëè ЬФ2, сложения по модулю Ь соединены с соответствующими входами блока деления 55 на L-ao выходы которого соединены с соответствующими информационными входами первого регистра, выходы каж31, . 2 дого i-го регистра, где i=1, (N-1}, соединены с информационными входами (i+1)-го регистра и со входами операнда i ãî блока умножения по модулю L, выходы N-го регистра соединены с соответствующими входами N-го блока умножения по модулю L выходы j-х блоков умножения по модулю L, где

1,N соединены с соответствующими входами j-й группы блока сложения по модулю L контролируемые входы устрой1ства соединены с соответствующими вхчдами (N+1) é группы блока сложения по модулю L, вход старшего разряда (N + !

+1)-й группы которого соединены с шиной нулевого потенциала, тактовый вход устройства соединен с тактовыми входами р егис тров .

На фиг. 1 приведена схема предлагаемого устройства; на фиг. 2 — пример построения устройства для случая Ф (х) =Зх +х+4, L=5, котор ое имеют контролируемые 1,,... 1,„,и тактовый

2 входы, содержит блок 3 сложения по модулю L, M-разрядные регистры 4 ...

4, число которых равно степени неприводимого многочлена, блоки 5„...

5я умножения по модулю Ь, блок 6 деления на (L-ао), где а о — свободный член неприводимого многочлена мак— симального периода. L — простое число, лежащее на интервале $2" 2" "), где n — число контролируемых входов

11, если L=2 устройства, M= . . вели((и+1) åñëè L 2, чина а., на которую происходит умножение в j ì блоке умножения, j=1,N, определяется коэффициентом при соот— ветствующем члене неприводимого многочлена.

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

Для L-ричного числа W на выходе блока 6 при отсутствии сигналов на входах 1„...1 можно записать

1 h (L-а }W=a D W+...+а D W+...+а DW, о ° где сложение и умножение осуществляет. ся по модулю L à D — оператор задержки на с тактов. После несложных преобразований получим

W(a„D +...+à 0 +...+а „П+а )=О, о т.е. характеристический многочлен устройства, изображенного на фиг. 1, имеет вид ч(х)=а„х +...+а х +...+

М 3

+а x+aо

3 11164

Подббрав соответствующим образом коэффициенты а, а, можно получить

У о Ф неприводимый многочлен максимального периода S = Ь вЂ” 1.

Поступающим на входы 1 ...1 ана1 лизируемым последовательностям можно поставить в соответствие многочлен, максимальная степень которого равна (m 1), где m — длина входных последовательностей, а коэффициенты при 1р соответствующих членах могут прини— мать значения от 0 до 2 — 1. Получение сигнатуры анализируемых последовательностей будет заключаться в делении по модулю L многочлена входных последовательностей на многочлен, инверсный по отношению к неприводи«! мому многочлену устройства. Поскольку рассматриваемое устройство является линейным, возможно применение 2р принципа суперпозиции. Из этого принципа следует, что реакция устройства на сумму двух входных векторов равна сумме его реакций на каждый вектор в отдельности. Если анализируе5 мый вектор z рассматривать как сумму по модулю Ь вектора последовательностей без ошибок Х и вектора ошибок У, то полученная сигнатура Rz будет равна сумме сигнатур векторов

Хи У зр

Rz= (R>+ К ) mod L.

Таким образом, для обнаружения искажений в правильных двоичных пос- . ледовательностях необходимо, чтобы сигнатура вектора ошибок была отлична от нуля, т.е. чтобы многочлен вектора ошибок не делился нацело на многочлен Ф (Х), инверсный по отношению к неприводимому многочлену максимального периода Ф(Х).

На фиг. 2 приведен пример построения устройства для случая Ф(Х)

=3X2+Х+4,Ь=5. В таблице приведен пример получения сигнатуры входных пос45 ледовательностей в данном устройстве.

Исходное состояние регистров — 000.

Рассмотрим достоверность контроля ! пр едл ага е мог о ус тр ойс т ва .

Очевидно, что при m < N сигнатура р любого вектора ошибок отлична от нуля. При m ) N вероятность обнаружения ошибки в последовательностях

-h(1+el f

2" — 1

Ноъ

Если Ь ) М + 1

Положительный эффект от использования предлагаемого устройства связан с увеличением его быстродействия.

Если в устройстве, являющемся прототипом, на формирование сигнатуры требуется nm тактов, то в предлагаемом устройстве — только m тактов, где m —длина анализируемых последовательностей.

31 4 длиной m при использовании N И-разрядных регистров 4 составит

n(v-NJ

2 — 1

P 1 о 2от где n — число контролируемых входов устройства.

Рассмотрим достоверность устройства по отношению к обнаружению одиночных, двойных и пакетов ошибок. Под кратностью ошибок будем в дальнейшем понимать количество искаженных входных наборов.

Очевидно, что ни один многочлен ошибок вида а,Х (одиночная ошибка) не делится нацело многочленом Ф (Х), т.е. обеспечивается 1ООХ-ная достоверность по отношению к обнаружению одиночных ошибок независимо от дли— ны входных последовательностей.

Двойная ошибка может быть представлена многочленом а.Х +а Х!.

1 3

При использовании свойств И-последовательностей с L уровнями вероятность пропуска двойной ошибки составит

Ю 5 )

1

1 но г (gü <) де S„=S(L-1), причем необнаружи аемым векторам двойных ошибок соответствуют многочлены, для которых

S*=i-j=nS„, n=1, 2, 3, По отношению к пакету ошибок длиной

Ъ не более N обеспечивается 100Х-ная достоверность независимо о длины регистрируемых двоичных последовательностей. Если Ь=Б+1, то вероят ность пропуска пакета ошибок составит

Р

ko4, 2

0

Фие. 1

Номер такта

1116431

0 0

1 3

1 3

1 1

1 1

1116431

12 фиг. 2

Составитель И.Сигналов

Редактор С.Тимохина Техред Л.Коцюбняк Корректор Г.Огар

Заказ 6931/39 Тираж 698 Подписное

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

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

Филиал ППП"Патент", г. Ужгород, ул . Проектная, 4