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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 119) (11) А(51) С 06 Г 11/12 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ члена, причем разрядность каждого ре 1,если Ь=2,гистра равна М, где И=,р , р),(и+1), если ЬФ 2,выходы блока сложения ло модулю Ьсоединены с соответствующими входамиблока деления на Ь-а, выходы которого соединены с соответстгующими ин- .формационными входами первого регистра, аыхады каждого г-го регистра,где =1,(М), соединены с информационными входами (1+1)-го регистраги со входами операнда -го блока умножения по модулю Ь, выходы М-го регистра соединены с соответствующимивходами М-го блока умножения по модулю Ь, выходы 1-х блоков умножения по модулю Ь, где 1=1,М, соединены с соответствукнцими входами 1-йгруппы блока сложения по модулю Ь,контролируемые входы устройства соеди. фффффнены с соответствующими входами (М ++1) - й группы блока сложения по модулюЬ, вход старшего разряда (М+1)-йгруппы которого соединен с шиной ну- Завамлевого потенциала, тактовый вход уст ввйройства соединен с тактовыми входами рвырегистров. ФФ(71) Московский ордена ТрудовогоКрасного Знамени инженерно-физический институт(56) 1. "Зарубежная.радиоэлектроника", 1979, Мр 1, с. 53,2. Авторское свидетельство СССРВ 792256, кл. С 06 Р 11/08, 1979(прототип),(54) (57) УСТРОЙСТВО ДЛЯ КОНТРОЛЯДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, содержащее два регистра, о т л и ч а ю -щ е е с я тем, что, с целью повышения быстродействия, оно содержитблок сложения по модулю Ь, где Ьпростое число, лежащее в интервале(2", 2"), а п - число контролируемых входов устройства, М - 2 регистров,где М - степень неприводимого многочлена, М блоков умножения по модулюЬ, блок деления на Ь-а, где а 0 -свободный член неприводимого многоОПИСАНИЕ ИЗОБРЕТЕНИЯ й 13К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ1164Изобретение относится к вычислительной технике и может быть использовано в системах диагностирования цифровых объектов.Известно устройство, которое содержит регистр сдвига, число разрядов которого определяется степенью не- приводимого многочлена, и сумматор по модулю два, выход которого соединен с информационным входом регистра сдви.0 га, а первый вход - с входом устройства, остальные входы сумматора по модулю два соединены с выходами соответствующих разрядов регистра сдвига, причем номер разряда, к которому5 подключается соответствующий вход сумматора по модулю два, определяется показателем степени соответствующего члена неприводимого многочлена, синхронизационный вход устройства соединен с шиной сдвига регистра, выходы которого являются выходами устройства1 .Недостатком этого устройства является невозможность получения диаг ностической сигнатуры последовательностей, поступающих одновременно по нескольким каналам.Наиболее близким к изобретению является устройство, содержащее счет 30 чик, преобразователь параллельного кода в последовательный и регистр сдвига с сумматором по модулю два в цепи обратной связи2 .1ЬНедостатком данного устройства яв, ляется низкое быстродействие.Целью изобретения является повышение быстродействия устройства.Поставленная цель достигается тем,что в устройство для контроля двоичных последовательностей, содержащеедва регистра, введены блок сложенияпо модулю Ь, где Ь - простое число,лежащее в интервале 2", 2), а и -чиспок онтролируемых входов устройств а 451М - 2 регистров, где М степень неприводимого многочлена, М блоковумножения по модулю Ь, блок деленияна Ь-ао, где а - свободный член неприводимого многочлена, причем разрядность каждого регистра равна М,Г 1, если Ь=2,где М=. выходы блока(п+1),если ЬФ 2,сложения по модулю Ь соединены с соответствующими входами блока деления 55на Ь-ао, выходы которого соединеныс соответствующими информационнымивходами первого регистра, выходы каж 31, . 1дого -го регистра, где =1, 5-1 Т,соединены с информационными входами(+1)-го регистра и со входами операнда -го блока умножения по модулю Ь,выходы И-го регистра соединены с соответствующими входами М-го блока умножения по модулю Ь, выходы 3-х блоков умножения по модулю Ь, где1,И, соединены с соответствующими входами -й группы блока сложения по модулю Ь, контролируемые входы устройства соединены с соответствующими вхчдами (И+1) -й группы блока сложения помодулю Ь, вход старшего разряда (И ++1)-й группы которого соединены с шиной нулевого потенциала, тактовый входустройства соединен с тактовыми входами регистров,На фиг, 1 приведена схема предлагаемого устройства на фиг. 2 - пример построения устройства для случая Ф(х)=Зх+х+4, Ь=5, которое имеютконтролируемые 1 ,1и тактовый2 входы, содержит блок 3 сложения помодулю Ь, М-разрядные регистры 414 я, число которых равно степени неприводимого многочлена, блоки 55 н умножения по модулю Ь, блок 6 деления на (Ь-ао), где а о - свободныйчлен неприводимого многочлена максимального периода. Ь - простое число, лежащее на интервале 2", 2 "),где и - число контролируемых входов11,если Ь=2,устройства, М=, , ф вели(п+1),если М 2,чина а, на которую происходит умножение в 1-м блоке умножения, =1,И,определяется коэФфициентом при соответствующем члене неприводимого многочлена,Устройство работает следующим образом.Для Ь-ричного числа 4 на выходеблока 6 при отсутствии сигналов навходах 11 можно записать(Ь-а )И=а ЭЯа 0 Иа %,одгде сложение и умножение осуществляет ся по модулю Ь, а ) - оператор задержки на с тактов. После несложных преобразований получимЩа 1)а 0 а П+а )=О,о ф т.е, характеристический многочленустройства, изображенного на фиг. 1,имеет вид Ч(х)=ах а х М 33 111 б 4Подобрав соответствующим образом коэффициенты а, а, можно получить9 о Фнеприводимый многочлен максимального периода Б = 1, - 1.йПоступающим на входы 1 1 анаь лизируемым последовательностям можно поставить в соответствие многочлен, максимальная степень которого равна (ш), где ш - длина входных последовательностей, а коэффициенты при О соответствующих членах могут прини - мать значения от О до 2 - 1. Получение сигнатуры анализируемых последовательностей будет заключаться в делении по модулю 1, многочлена вход ных последовательностей на многочлен, инверсный по отношению к неприводи мому многочлену устройства. Поскольку рассматриваемое устройство является линейным, возможно применение 20 принципа суперпозиции. Из этого принципа следует, что реакция устройства на сумму двух входных векторов равна сумме его реакций на каждый векторв отдельности. Если анализируе 5 мый вектор г рассматривать как сумму по модулю Ь вектора последовательностей без ошибок Х и вектора ошибок У, то полученная сигнатура В будет равна сумме сигнатур векторов Хи У30кг ("х+ Еу) тпос 1" Таким образом, для обнаружения искажений в правильных двоичных пос- . ледовательностях необходимо, чтобы сигнатура вектора ошибок была отлична от нуля, т,е. чтобы многочлен вектора ошибок не делился нацело на многочлен Ф(Х), инверсный по отношению к неприводимому многочлену максимального периода Ф(Х),На фиг. 2 приведен пример построения устройства для случая Ф(Х) =ЗХ 2+Х+4,Ь=5. В таблице приведен пример получения сигнатуры входных пос 45 ледовательностей в данном устройстве. Исходное состояние регистров - 000.Рассмотрим достоверность контроля предлагаемого устройства.чевидно что при ш ( И сигнатур любого вектора ошибок отлична от нуля. При ш ) Н вероятность обнаружения ошибки в последовательностях-ь (1+й2" - 1 Р1 Если Ь ) М + 1Положительный эффект от использования предлагаемого устройства связан с увеличением его быстродействия. Если в устройстве, являющемся прототипом, на формирование сигнатуры требуется пш тактов, то в предлагаемом устройстве - только ш тактов, где а - длина анализируемых последовательностей. 31 4длиной ш при использовании М И-разрядных регистров 4 составито(п-й2 - 1Р 1о 2 от 1 фгде и - число контролируемых входовустройства.Рассмотрим достоверность устройства по отношению к обнаружению одиночных, двойных и пакетов ошибок. Подкратностью ошибок будем в дальнейшем понимать количество искаженных входных наборов.Очевидно, что ни один многочленошибок вида а,Х (одиночная ошибка)не делится нацело многочленом Ф (Х),т.е, обеспечивается 1007-ная достоверность по отношению к обнаружениюодиночных ошибок независимо от длины входных последовательностей,Двойная ошибка может быть представлена многочленом а.Х+а Х.3 3 При использовании свойств И-последовательностей с Ь уровнями вероятность пропуска двойной ошибки составитЮК ь)Р1но г 2"-)где Б =Я(Ь) , причем необнаружираемым векторам двойных ошибок соответствуют многочлены, для которыхЫ и2 ф ЗфПо отношению к пакету ошибок длиной Ъ не более И обеспечивается 1003-ная достоверность независимо от длины регистрируемых двоичных последовательностей, Если Ъ=Б+1, то вероятность пропуска пакета ошибок составитРгктор Г,Огар Редакто Тимохи исное к 5 Ужгор роектна 6931/39 Тираж 6 ВНИИПИ Государственногпо делам изобретений 113035, Москва, Ж,иал ППП "Патент",Подкомитета СССРоткрытийушская наб., д