Устройство для диагностирования цифровых объектов

 

Изобретение относится к вычислительной технике и может быть использовано в системах тестового диагностирования дискретных обьектов. Цель изобретения - повышение надежности. Устройство содержит сигнатурный анализатор, блок формирования обобщенной сигнатуры, центральный процессор, блок внешней памяти программ контроля, блок оперативной памяти, блок постоянной памяти программ формирования сигнатур, блок задания режимов и блок индикации. Цель изобретения достигается за счет существенного уменьшения объема блока памяти эталонных сигнатур. 3 ил..

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

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

РЕСПУБЛИК (я)з G 06 F 11/00

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4748451/24 (22) 11.10.89 (46) 15.01.92. Бюл. l4 2 (71) Институт проблем управления (72) В.Л.Геурков и В.Н.Дынькин (53) 681.326.7(088.8) (54) УСТРОЙСТВО ДЛЯ ДИАГНОСТИРОВАНИЯ ЦИФРОВЫХ ОБЪЕКТОВ (57) Изобретение относится к вычислительной технике и может быть использовано в системах тестового диагностирования дискИзобретение относится к вычислительной технике и может быть использовано в системах тестового диагностирования цифровых устройств.

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

На фиг.1 показана схема устройства для диагностирования; на фиг.2 — схема блока формирования обобщенной сигнатуры; на фиг.3- алгоритм работы устройства в случае восьмираэрядных сигнатур и одиночных неисправностях ТЭЗов.

Устройство содержит сигнатурный анализатор 1, блок 2 формирования обобщенной сигнатуры. блок 3 индикации, центральный процессор 4, блок 5 оперативной памяти, блок 6 постоянной памяти программ формирования сигнатур, блок 7 внешней памяти программ контроля и блок 8 клавиатуры.

Блок 2 состоит иэ дешифратора 9, элемента И 10, первого 11 и второго 12 шинных формирователей, а также регистров 13 и 14 и сумматоров 15-30 по модулю два, образующих формирователь 31 сигнатур, „„5U „„1705829 А1 ретных объектов. Цель изобретения — повышение надежности. Устройство содержит сигнатурный анализатор, блок формирования обобщенной сигнатуры, центральный процессор, блок внешней памяти программ контроля, блок оперативной памяти, блок постоянной памяти программ формирования сигнатур, блок задания режимов и блок индикации. Цель изобретения достигается за счет существенного уменьшения объема блока памяти эталонных сигнатур. 3 ил.

Перед тестированием в ОД размыкаются обратные связи, идущие от ТЭЗов, а ТЭЗы ранжируются. К первому рангу относятся ТЭЗы, на которые воздействия поступают непосредственно с генератора тестов. К -му рангу относят ТЭЗы, на которые воздействия поступают с ТЕЗов ранга

i-1 и меньше. ТЭ3ы, принадлежащие 1-му рангу, образуют i-ю область аппаратуры объекта. Диагностирование областей выполняется последовательно в порядке возрастания их рангов. Сначала проверяются

ТЭЗы первой области. Если все они неисправны, то переходят к следующей области.

Если найдены неисправные ТЭЗы, то процесс диагностирования возобновляется только после их восстановления. Очевидно, при таком подходе кратность неисправностей ТЭЗов в пределах любой области не превышает t, где t — число одновременно отказавших ТЭЗов. Для поиска неисправных ТЭЗов областей в устройстве используется процедура декодирования кодов, локализующих t-кратные ошибки (ЛО-кодов). Данные коды позволяют указать t искаженных подслов кодовых слов, В качестве

1705В29

i-го кодового слова рассматриваются выходные последовательности ТЭЗов 1-й области.

Проверочная часть кодового слова — обобщенная сигнатура. ЛО-коды строятся íà основе двух кодов: Ki, обнаруживающего 5 ошибки, и Kz, корректирующего ошибки.

Сигнатурный анализатор 1 — декодер кода К1, обнаруживающий некоторый класс ошибок. Длина m сигнатуры определяет число проверочных символов этого кода. 10

Блок 2 является декодером циклического кода Kz над полем GF(2 ), исправляющего ошибки и порождаемого 2m-ичным многочленом 6(х)степени r. Поскольку для целей диагностирования достаточно лишь указать 15 неисправные ТЭЗы, то коррекция искаженныхх 2m-ичных символов (сигнатур) не производится, а только определяется их местоположение. Длина п(когда Kz) выбирается таким образом, чтобы удовлетворять 20

max условию и > и(- где i — число обла1= (, стей, на которые разбит ОД, à ni — число

ТЭЗов в I-й области.

Рассмотрим работу устройства для слу- 25 чая, когда в каждой из 1 областей ОД возможна неисправность одного ТЭЗа, а сигнатуры ТЭЗов — восьмиразрядные.

В качестве кода Kz можно испольэовать код, корректирующий одиночные ошибки 2 - 30 ичных символов, например, обобщенный код

Хемминга, порождаемый многочленом нар полем GF(2 ) степени r = 2 G(x) = 1 + P х + х, где P — примитивный элемент поля GF(2 ) в (кореньдвоичногонеприведенногомногочле- 35 на восьмой степени g(x) = 1+ х+ х + x + хВ), э

Длина и такового кода равна 257, Рассмотрим процедуры кодирования и декодирования выбранного кода Хемминга.

Процедура кодирования. 40

Пусть необходимо закодировать слова

В = (Ь2.... Ь2ы) длиной К = и-r = 257-2=255 (где bi — 2 -ичный символ или элемент поля

"Ъ

GF(2 ). i = 2.256). с которым сопоставляется многачлЕн В(х) = Ьг+Ьэх+...+bZ56x т,Е. най- 45

256 ти такое (кодовое) слово By, = (b, b>,...,Ьг56) длиной n = К + r = 257, чтобы сопоставляемый с ним многочлен Вк(х) = Ьо + Ь1х ... +

bz56x делился íà G(x) без остатка. Найдем символы Ьо, b>. Поскольку Р-примитивный 50 элемент GF(2 ). то выразим все нулевые символы bi степенями /t, l = 0,256(4), Например, 2 -ичному символу Ь4 = 01101010 в соотееттхтует к = ((С,, поскоп кку x modg(x) =

Х+Х +Х +Х.

Аналогично, символу Ьз = 11010100 соответствует Р(з =/3в, так как х modg(x) = 1 в

+ х + х + х . Тогда (для ненулевых в b)

В () PО +P 1 +/7256. ) - 0,256 — некоторые целые числа. а искомыми являются P P . Очевидно/ (+ф =

=(xzB(x))modG(x) = (О + Ох + Р(2 xZ + +PZ56 x25)mpdG(x) Напримвр для В(х) = 1/Р,/Р,/Ф,/У,0,...,0) имеют ок(х) = (((е яутк уте ут" .(те 0, 0) поскопьку оехк.ф.фх .фл 1 ах+к" .фх"фхк ркк * (тк 8 к.

Процедура кодирования, т.е. вычисления остатка х В(х) по modG(x), реализуется в г блоке 2 для восьмиразрядных сигнатур в случае одиночных неисправностей ТЭЗов следующим образом, В начальный момент времени импульс, поступающий на вход "Сброс", устанавливает регистры 13 и 14 в нулевое состояние.

Далее на вход "Чтение" подается "0" (что соответствует передаче информации с входов-выходов ДВ на выходы ДО двунаправленного шинного формирователя 11), на шину данных — 2 -ичный символ bz56. а на в шину адреса — адрес двунаправленного шинного формирователя 11 (что вызывает появление "1п на первом выходе дешифратора 9). Приходящий вслед за этим на вход

"Запись", импульс проходит через элемент

И 10 на входы STB регистров 13 и 14 и вызывает запись в них информации, присутствующей на их входах Д1. Каждый такой такт работы блока 2 называется сдвигом.

Далее на шину данных подается символ

bz55, и осуществляЕтСя ЕщЕ Один Сдвиг и т.д. до символа bz включительно, после чего на шину данных подается нулевой байт и осуществляется еще два сдвига. Содержимое

Ьо и bt регистров 13 и 14 соответственно является искомым остатком. Очевидно, если содержимое регистров 13 и 14 было нулевым, то оно останется TBK08b(M при любом количестве сдвигов с нулевым байтом на шине данных. Поэтому нулевые символы

bz56,".. b6 можно не подавать на шину данных и не осуществлять лишние сдвиги, Процесс можно начать непосредственно с символа Ь5 ф .

Процедура декодирования рассматриваемого кода заключается в следующем.

На шину данных поступают символы слова Вк, отличающегося от слова Вк одним (искаженным) символом, местоположение которого неизвестно. Причем первым поступает 256-й символ, а последним — нулевой.

1705829 м ..кхв + Х" Jt

1 а Х +Х ах

g ИвХ + Х +Xе

1е х -Х . -Х х х + х х" х"Ф

Х+ 4хх+ х ох + ХХе

g)t + Х +)t а Х

1+ х х+х х

Найдем обобщенную сигнатуру р О Х еу Х рЖ,ф +,8 1 1+УХ

Р.х-х, У Ух ах, е

40 ется/Р и/У, Р +ф х +0 х

+ + г

Р8„з

Х-вУХХ вф.1Г

О ° 8 х

После 255-го дополнительного сдвига Таким образом, S*-(О,ф). Тогда кодо45 содержимое регистра 13 обнуляется, т.е. ис- вым является слово

° кажен оыл 257 — 25о» 2-и символ Вк, = (pÂ@ Og+pаpвреуоамлВ.О

Рассмотрим процедуры кодирования и

/ 8ф фвфвф,68,0,....О декодирования ЛО-кода.

Пусть сигнатурный анализатор 1 описыб К(х) mod Q(õ)= вается порождающим многочленом g(x) = . = +Рх +Р х +Р х Р х +Р " )modG(x

1+х+х +х +х . ЛО-код составлен из кодов К1 Очевидно, если ненулевой является

3 5 8 и Кг с порождающими многочленами g(x) и толькосигнатура ЯонулевогоТЭЗа(т.е. чисG(x) соответственно. ло ненулевых сигнатур меньше r), то ЬбобПредположим, что проверяемая об- щеннаЯ сигнатУРа этой области содеРжит ласть содержит 257 ТЭЗов, сигнатуры кото- всего один 2 -ичный символ, совпадающий

8 рых обозначим соответственно через S, .... с сигнатурой, Таким образом, для слов (/3;

S256. О, ..., 0) сигнатура S = (5о ) = (Р"о) = (/3 о).

Поступление каждого символа сопровождается сдвигом блока анализа. После 267-ro сдвига на вход "Чтение" подается н1н (что соответствует передаче информации с входов Д1 на входы-выходы ДВ двунаправленного шинного формирователя 11), а на шину адреса-адрес двунаправленного шинного формирователя 11. Тогда содержимое регистра 13 с его выходов ЯО поступает на шину данных. Если это содержимое равно нулю, то на шину адреса подается адрес однонаправленного шинного формирователя 12 (что вызывает появление нОн на первом выходе дешифратора 9 адресов и "1н на его втором выходе). через который на шину данных поступает содержимое регистра 14 с его выходов ДО. Если и это содержимое равно нулю, то считается, что ошибок нет; если содержимое регистра 14 не равно нулю, то ошибочным является нулевой символ слова Вк, Если содержимое регистра 13 не равно нулю, то поступают следующим образом. На шину данных подается нулевой байт и осуществляется один (дополнительный) сдвиг блока 2. Затем нулевой байт снимается, а на шину данных поступает содержимое регистра 13 (путем адресации и двунаправленного шинного формирователя 11 и установления соответствующего направления передачи информации через него).

Дополнительные сдвиги с последующим считыванием содержимого регистра 13 продолжается до тех пор, пока в последнем не окажется ноль. Тогда искаженным является (257-h)-й символ слова Вк, где h — число дополнительных сдвигов.

Пусть, например, в Вк искажен второй символ сР =ф на О. Тогда, после 257 сдвигов в регистрах 13 и 14 соответственно имеПроцедура кодирования ЛО-кода заключается в следующем.

Сначала вычисляются сигнатуры S<„., S256, представим ненулевые сигнатуры в ви5 де степеней примитивного элемента, т,е.

Si = ф - 0.256. Затем определяется остаток (/у+Я х + .. + pl256х256)п1об6(х) око + рк1х

Очевидно, кодовым является слово, соответствующее многочлену L(x)Plo +go) y ф1 gPк1)х + PI2Õ2 +

+pl256x256 pvo +calx +фгх2 + +pl256х256

Совокупность символов (в данном слунае ненулевых), (p" ô"11= воо,во1)= s валяетсяя обобщенной сигна ой областью, Пусть, например. (So...,, S256)

= j3,0ô(ÐЯР8, О,..., О).. где сигнатура. нап имер S1 = О, соответствует следующей двоичной последовательности с выхода первого ТЭЗа 10010111000000001, Дейст25 вительно, 1705829

Процедура декодирования ЛО-кода совпадает с процедурой декодирования кода

Кр, рассмотренной выше, Пои этом на блок

2 подаются символы слова L, отличающегося от слова L одним символом.

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

Обозначим через Nl - )-й ТЭЗ I-й облаi сти, J О, (ni-1), I = 1,I.

Перед включением устройства входы

"Старт", "Стоп" и "Такт" сигнатурного анализатора 1 соединены с соответствующими выходами ОД, При включении устройства процессор 4 формирует на шине управления сигнал "Сброс", поступающий на R-входы регистров 13 и 14 и устанавливающий их в нулевое состояние, Затем программа диагностирования объекта вместе с обобщенными сигнатурами его областей загружается в блок 5 оперативной памяти из блока 7, после чего процессор 4 адресует блок 3 индикации и выдает на него сообщение "Снять сигнатуру с ТЭЗа Тп-! ". Затем адресуется сигнатурный анализатор 1 и процессор 4 переходит в режим ожидания.

При этом работа сигнатурного анализатора

1 запрещена. т.е. двоичная информация, присутствующая на входе "Данные" сигнатурного анализатора 1. не воспринимается последним. После соединения например, (через щуп) входа "Данные" сигнатурного анализатора 1 с выходом ТЭЗа T>-! опера1 тор нажимает кнопку ввода данных на щупе или соответствующую клавишу на блоке 8, информируя процессор 4 о том, что соединение с контрольной точкой выполнено, По сигналу "Прерывание 1", выдаваемому блоком клавиатуры 8 или сигнатурным анализатором 1 на шину управления при этом нажатии, процессор 4 разрешает работу сигнатурного анализатора 1, т.е. по приходу сигнала "Старт" от ОД на соответствующий вход сигнатурного анализатора 1 в нем начинается формирование сигнатуры, По приходу сигнала "Стоп" формирование сигнатуры завершается, и она поступает на шину данных. Одновременно сигнатурный анализатор 1 выдает на шину управления сигнал "Прерывание 2", по которому процессор 4 считывает сигнатуру. присутствующую на шине данных и снимает с шины адреса адрес сигнатурного анализатора 1, отключая последний от шины данных. Далее процессор 4 сравнивает номер j проверенного ТЭЗа с числом 1. Если j <1, т.е. была снята сигнатура S! с ТЭЗа, номер которого соответствует проверочной части кода К2, то Sl суммируется с соответствующим символом Si* обобщенной сигнатуры.

0 < j < (r - 1) = 1 и выдается на шину данных

В противном случае сигнатура S! поступает на шину данных непосредственно. Далее процессор 4 осуществляет сдвиг блока 2, Такой процесс повторяется для всех и> сигнатур первой области. После и>-го сдвига анализируется содержимое регистров 13 и

14, как было описано для кода Kg. в результате чего либо выдается номер неисправного ТЭЗа текущей области и процесс останавливается, либо переходит к следующей области. Если неисправность не обнаружена ни в одной области. то выдается сообщение об отсутствии неисправных ТЭЗов и процесс останавливается. Чтобы вновь запустить его. необходимо нажать в блоке 8 клавишу "Сброс".

В данном случае для хранения обобщенных сигнатур областей, каждая из которых содержит по 257 ТЭЗов, требуется

2х8х! = 16I бит памяти, а при использовании прототипа требовалось 257х8х! = 2056! бит, т,е. затраты памяти уменьшены в 128,5 раз.

Когда ОД содержит областей, сигнатура каждого ТЭЗа — m ðàýðÿäíàÿ и возможны неисправности не более чем в одном

ТЭЗе каждой области, Пусть GF(2 ) — наименьшее расширение поля GF(2 ), содержащее все корни G(x). Тогда число 2 -ичных проверочных символов кода Kz Хемминга над G F(2 ) равно r = р и экономия памяти для

ОД в целом составит ! 1

p = Q (nim))/Irm = ч/!р, где v =,", ni— !

=1 i=1 число ТЭЗов в ОД. Максимальная экономия памяти получится, если каждая область содержит ni = n = (2 Р - 1)/(2 -1) ТЭЗов, i = 1,!, где n — длина кода Хемминга. Тогда /с =

=!(2 Р-1)/(2 -1)lp = 2"!" )/р

С возрастанием m увеличивается разрядность регистров блока 2, а с возрастанием t — количество этих регистров (и соответственно — сумматоров по модулю два) при некотором усложнении алгоритма работы устройства.

Интервальное значение числа-провем/ рочных символов. обозначаемое через r, может быть оценено из выражений для нижней границы Варшамова-Гильберта и верхней границы Хемминга, Используя эти выражения, можно записать

d — 2, од (С „(2 — 1) )<=rm

i i=0 где d — минимальное расстояние кода Кг, выбор которого определяется характером возможных искажений кодовых слов

1705829

t = ((d-1)/2) — кратность неисправностей; (а) — целая часть а;

m — длина сигнатуры; и — максимальное по областям число

ТЭЗов (или длина кода Kz). 5

Отсюда

logZ(С„(2" — 1) )/m Г "=(Щ(С (г — () )/m (-г, I= I=

10 и интервальное значение суммарной эконом мии, определяемое как p = v/lr, лежит в л пределах р 5д <ð, где 2 и = vml(logz(Y Co(2 -1Д1;

15 р = vm/(1ogz(Сп (2 -1) ))1.

1=

Использование устройства является

V/ экономически выгодным, если gc < 1, и тем 20 л самым более выгодным, чем больше (Если р < 1, а Й > 1, то целесообразность использования устройства зависит от конкретно выбранного кода К . Если для этого кода точечное значение,и*> 1, то ис- 25 пользование устройства является экономически выгодным, если же,й*< 1, то испольэовать устройство невыгодно, Локализация искаженных банков данных производится аналогично. На вход 30

"Данные" блока 1 поступает непосредственно содержимое банков.

При локализации дефектных частей печатных плат состояние очередной точки платы кодируется троичным кодом, например, 35 с помощью лазерной установки.

Наличию проводника соответствует"0", наличию отверстия — "1", отсутствию проводника и отверстия — "2". Лучи лазера последовательно пробегают все точки платы. 40

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

Локализация дефектных частей производится аналогично, Таким образом, положительный эффект от использования изобретения заключает- 50 ся в увеличении надежности, за счет уменьшения объема памяти и снижения вероятности записи в нее ошибочных сиг- натур при определенных соотношениях количества ТЭЗов в областях ОД и кратно- 55 сти их неисправностей. При этом экономия памяти достигается как в блоке 5, так и в блоке 7.

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

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

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

1705S29

1705829

1705829

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

Редактор Л.Пчолинская Техред М.Моргентал Корректор О.Кундрик

Заказ 194 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", f. Ужгород, ул.Гагарина, 101