Устройство для контроля двоичных последовательностей Советский патент 1984 года по МПК H03M13/51 

Изобретение относится к вычислительной технике и может быть использовано в системах диагностирования 1цифровых объектов. Известно устройство, которое содержит регистр сдвига, число разрядо которого определяется степенью непрлводимого многочлена, и сумматор п модулю два, выход которого соединен с информационным входом регистра сдв га, а первый вход - с входом устройства, остальные входы сумматора по модулю два соединены с выходами соответствующих разрядов регистра сдви га, причем номер разряда, к которому подключается соответствующий вход сумматора по модулю два, определяется показателем степени соответствующего члена неприводимого многочлена, синхронизационный вход устройства co динен с шиной сдвига регистра, выходы которого являются выходами устройства 1 . Недостатком этого устройства является невозможность получения диагностической сигнатуры последовательностей, поступающих одновременно по нескольким каналам. Наиболее близким к изобретению является устройство, содержащее счет чик, преобразователь параллельного кода в последовательный и регистр сд га с сумматором по модулю два в цепи обратной связи 2 . Недостатком данного устройства яв ляется низкое быстродействие. Целью изобретения является повыше ние быстродействия устройства. Поставленная цель достигается тем что в устройство для контроля двоичных последовательностей, содержащее два регистра, введены блок сложения по модулю L, где L - простое число, лежащее в интервале 2, 2), а п числоконтролируемых входов устройства N - 2 регистров, где N степень неприводимого многочлена, N блоков умножения по модулю L, блок деления на L-a,, где а,- свободный член неприводимого многочлена, причем разрядность каждого регистра равна М, Г1, если .-, где ,ч т-io выходы блока (п+1),если Lf2, сложения по модулю L соединены с соо ветствующими входами блока деления на L-a.j, выходы которого соединены с соответствующими информационными входами первого регистра, выходы каж дого i-ro регистра, где ,(N-1), соеди:нены с информационными входами (i+1)-ro регистра и со входами операнда i-ro блока умножения по модулю L, выходы N-ro регистра соединены с соответствукяцими входами N-ro блока умножения по модулю L, выходы J-X блоков умножения по модулю L, где j 1,N, соединены с соответствующими входами j-й группы блока сложения по модулю L, контролируемые входы устройства соединены с соответствующими входами (Н-ьр-й группы блока сложения модулю L, вход старшего разряда (N + +1)-й группы которого соединены с шиной нулевого потенциала, тактовый вход устройства соединен с тактовыми входами регистров. На фиг. 1 приведена схема предлагаемого устройства; на фиг. 2 - пример построения устройства для случая Ф(х)Зх2+х+4, , которое имеет контролируемые 1,...1„.1И тактовьш 2 входы, содержит блок 3 сложения по модулю L, М-разрядные регистры 4 ... 4|, число которых равно степени неприводимого многочлена, блоки 5 ... 5j умножения по модулю L, блок 6 деления на () , где а - свободный член непривода1мого многочлена максимального периода. L - простое число, лежащее на интервале 2, Z), где п - число контролируемых входов .. П,если , устройства, М. V , вели- (п+1) ,если Lf 2, чина а., на которую происходит умножение в J-M блокеумножения, j 1,N, определяется коэффициентом при соответствующем члене неприводимого многочлена. Устройство работает следующим образом. Для L-ричного числа W на выходе блока 6 при отсутствии сигналов на входах 1...1 можно записать (L-ao). . .+a.. . ., где сложение и умножение осуществляется по модулю L, а D - оператор заержки на oL тактов. После несложных преобразований получим . . .+a.jD- + .. .)0, .е. характеристический многочлен стройства, изображенного на фиг. 1, меет вид Ч(х)а.,.. .+а х-+...+ .Подобрав соответствующим образом коэффициенты а, а, можно получить неприводимый многочлен максимального периода S L - 1. Поступающим на входы анализируемым последовательностям можно поставить в соответствие многочлен, максимальная степень которого равна (т-1), где m - длина входных последовательностей, а коэффициенты при соответствующих членах могут принимать значения от О до 2 -1. Получение сигнатуры анализируемых последовательностей будет заключаться в делении по модулю L многочлена входных последовательностей на многочлен инверсный по отношению к неприводимому многочлену устройства. Поскольку рассматриваемое устройство является линейным, возможно применение принципа суперпозиции. Из этого прин ципа следует, что реакция устройс -ва на сумму двух входных векторов равна сумме его реакций на каждый вектор в отдельности. Если анализируемый вектор Z рассматривать как сумму по модулю L вектора последователь ностей без ошибок X и вектора ошибок У, то полученная сигнатура R будет равна сумме сигнатур векторов X и У R (R;(+ R) mod L. Таким образом, для обнаружения искажений в правильных двоичных последовательностях необходимо, чтобы сигнатура вектора ошибок была отлична от нуля, т.е. чтобы многочлен век тора ошибок не делился нацело на многочлен Ф(Х), инверсный по отноше нию к неприводимому многочлену макси мального периода Ф(Х). На фиг. 2 приведен пример построе ния устройства для случая Ф(Х) 3X2+X-4-4,. В таблице приведен при мер получения сигнатуры входных последовательностей в данном устройстве Исходное состояние регистров - 000. Рассмотрим достоверность контроля /предлагаемого устройства. Очевидно, что при m 4 N сигнатура любого вектора ошибок отлична от нуля. При m N вероятность обнаружения ошибки в последовательностях длиной m при использовании N М-разрядных регистров 4 составит ,п{п-Ы) РО 1 2пт 1 где п - число контролируемых входов устройства. Рассмотрим достоверность устройства по отношению к обнаружению одиночных, двойных и пакетов ошибок. Под кратностью ошибок будем в дальнейшем понимать количество искаженных входных наборов. Очевидно, что ни один многочлен ошибок вида а.X (одиночная ошибка) не делится нацело многочленом Ф(Х), т.е. обеспечивается 100%-ная достоверность по отношению к обнаружению одиночных ошибок независимо от длины входных последовательностей. Двойная ошибка может быть представлена многочленом а.Х+а:Х. При использовании свойств М-последовательностей с L уровнями вероятность пропуска двойной ошибки составит т .) Ч ) где S S(L-1) , причем необнаружиаемым векторам двойных ошибок соответствуют многочлены, для которых , , 2, 3 По отношению к пакету ошибок длиной b не более N обеспечивается 100%-ная достоверность независимо of длины регистрируемых двоичных последовательностей. Если , то вероятность пропуска пакета ошибок составит ,-л() 1 Если Ь N + 1 . Положительный эффект от использования предлагаемого устройства связан с увеличением его быстродействия. Если в устройстве, являющемся прототипом, на формирование сигнатуры требуется nm тактов, то в предлагаемом устройстве - только m тактов, где m лина анализируемых последовательностей.

It

Ui

иг.2

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