Устройство для диагностирования цифровых объектов Советский патент 1992 года по МПК G06F11/00 

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

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

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

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

Блок 2 состоит из дешифратора 9, элемента И 10, первого 11 и второго 12 шинных формирователей, а также регистров 13 и 14 и сумматоров 15-30 по модулю два, образующих формирователь 31 сигнатур.

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

(Л

С

4 О СЛ 00

кэ о

max

1-го кодового слова рассматриваются выходные последовательности ТЭЗов 1-й области. Проверочная часть кодового слова - обобщенная сигнатура. ЛО-коды строятся на основе двух кодов: Ki, обнаруживающего ошибки, и «2, корректирующего ошибки.

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

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

Л| - где I - число облап

условию .. - .-.

i ,

стей, на которые разбит ОД, а гн - число ТЭЗов в 1-й области.

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

В качестве кода К2 можно использовать код, корректирующий одиночные ошибки 2 - ичных символов, например, обобщенный код Хеммингэ, порождаемый многочленом над полем GF(2S) степени г 2:G(x) 1 +/ х + х2, где ft - примитивный элемент поля GF(2 ) (корень двоичного неприведенного многочлена восьмой степени д(х) 1+ х+ х + х + х8). Длина п такового кода равна 257.

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

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

Пусть необходимо закодировать слова В {Ь2. .... 0256} длиной К п-г 257-2 255 (где bi - 2 -ичный символ или элемент поля GF(28), i 2,256), с которым сопоставляется многочлен В(х) Ь2+Ьзх+...+Ь25бх , т.е. найти такое (кодовое) слово Вк {Ь0, bi,...,D256} длиной п К + г 257, чтобы сопоставляемый с ним многочлен Вк(х) Ь0 + bix ... + D256X256 делился на С(х)без остатка. Найдем символы bo, bi. Поскольку/3-примитивный элемент GF(2 ), то выразим все нулевые символы bi степенями Д i 0,256(4). Например, 28-ичному символу Ь4 01101010

соответствует/Г /Г,, поскольку х modg(x) х + х2 + х4 + х:°.

Аналогично, символу Ьз 11010100

соответствует/ 3 /г , так как х modg(x) 1 х . Тогда (для ненулевых в Ь)

+ х +

Х3 +

получим Вк(х) -/З10 + х + х256 , где Ij

0

5

0

5

0

5

0

5

0

5

. j 0,256 - некоторые целые числа, а искомыми являются/ 0, . Очевидно/ 0 + (x2B(x))modG(x)(0 + Oxi+ +... + / 256x25G)modG(x). Например, для В(х) {fP{PjPjP.Q.....Q} имеют

Вк(х) №fPfPfPfljP.Q.,.o} поскольку

$ s№ &&+$№ 4+flx+x1

fi8 &

fl8 р9х j&c

$ + $ 9 -р°+р Ь

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

В начальный момент времени импульс, поступающий на вход Сброс, устанавливает регистры 13 и 14 в нулевое состояние. Далее на вход Чтение подается О (что соответствует передаче информации с входов-выходов ДВ на выходы ДО двунаправленного шинного формирователя 11), на шину данных - 2 -ичный символ D256. а на шину адреса - адрес двунаправленного шинного формирователя 11 (что вызывает появление 1 на первом выходе дешифратора 9). Приходящий вслед за этим на вход Запись, импульс проходит через элемент И 10 на входы STB регистров 13 и 14 и вызывает запись в них информации, присутствующей на их входах Д1. Каждый такой такт работы блока 2 называется сдвигом. Далее на шину данных подается символ Ь255, и осуществляется еще один сдвиг и т.д. до символа 02 включительно, после чего на .шину данных подается нулевой байт и осуществляется еще два сдвига. Содержимое bo и bi регистров 13 и 14 соответственно является искомым остатком. Очевидно, если содержимое регистров 13. и 14 было нулевым, то оно останется таковым при любом количестве сдвигов с нулевым байтом на шине данных. Поэтому нулевые символы D256,..., be можно не подавать на шину данных и не осуществлять лишние сдвиги. Процесс можно начать непосредственно с

символа bs Ф{Р.

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

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

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

Если содержимое регистра 13 не равно нулю, то поступают следующим образом. На шину данных подается нулевой байт и осуществляется один (дополнительный) сдвиг блока 2. Затем нулевой байт снимается, а на шину данных поступает содержимое регистра 13 (путем адресации и двунаправленного шинного формирователя 11 и установления соответствующего направления передачи информации через него).

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

Пусть, например, в Вк искажен второй

символе/ 2 / на 0. Тогда, после257сдвигов в регистрах 13 и 14 соответственно имеется /5е иуЗ9 .поскольку fi +о-х2 +J& +jW+ r+W+.

F+P

После 255-го дополнительного сдвига содержимое регистра 13 обнуляется, т.е. искажен был 257 - 255 2-й символ Вк.

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

Пусть сигнатурный анализатор 1 описывается порождающим многочленом д(х) 1+х+х3+х5+х8. ЛО-код составлен из кодов KI и Ка с порождающими многочленами д(х) и G(x) соответственно.

Предположим, что проверяемая область содержит 257 ТЭЗов, сигнатуры которых обозначим соответственно через S0, .... S256.

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

Сначала вычисляются сигнатуры So,,... S256r представим ненулевые сигнатуры в виде степеней примитивного элемента, т.е.

Si ($ I 0,256. Затем определяется остаток

09 +/8|1х +... + / 256x256)modG(x) i/f° +/9Klx

Очевидно, кодовым является слово, соответствующее многочлену L(x) (j$° ) + & ®/3К1)х +

+ / 256Х256 р° +... + / 25бх256

Совокупность символов (в данном случае ненулевых). №° jso, S является обобщенной сигнатурой областью, Пусть, например. {S0,.... 8255} -j/.. О,..., О}, где сигнатура, например Si 0, соответствует следующей двоичной последовательности с выхода первого ТЭЗа 10010111000000001. Деист- вительно,

.xs.x«.x7

J.t.&lP fP

H «X 5«Xe

.

1-х)иг«жв«х +

- .

гч.л «х +.

t

35

. х8. . A tJC Х X

1 + Х Х3 + Х

Найдем обобщенную сигнатуру

л tj3

J3X «A

fiW

fH j&x Ј

X .ЈЈ

лЫ

0 « ft f.

Таким образом. S {О, /З9 }..Тогда кодовым является слово

U {/3e®0,0@/39 /38-/58-/59 /ge-0,...,o}

fpff№f.o.....ol

Можно проверить, что LK(x)modG(x)

-08е +$ +/38х2 )modG(xH). Очевидно, если ненулевой является только сигнатура So нулевого ТЭЗа (т.е. чис- ло ненулевых сигнатур меньше г), то обобщенная сигнатура этой области содержит всего один 2 -ичный символ, совпадающий с сигнатурой. Таким образом, для слов {/

О, ..., 0} сигнатура S - ).

Процедура декодирования Л 0-кода совпадает с процедурой декодирования кода К2, рассмотренной выше. Пди этом на блок 2 подаются символы слова L, отличающегося от слова L одним символом.

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

Обозначим через NJ - -й ТЭЗ 1-й области, J 0,(щ-1). 1 1.1.

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

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

О j (г- 1) 1 и выдается на шину данных В противном случае сигнатура Sj поступает на шину данных непосредственно. Далее процессор 4 осуществляет сдвиг блока 2.

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

В данном случае для хранения обобщенных сигнатур I областей, каждая из которых содержит по 257 ТЭЗов, требуется 2x8x1 161 бит памяти, а при использовании прототипа требовалось 257x8x1 20561 бит, т.е. затраты памяти уменьшены в 128,5 раз.

Когда ОД содержит I областей, сигнатура каждого ТЭЗа - m-разрядная и возможны неисправности не более чем в одном ТЭЗе каждой области. Пусть GF(2mp) - наименьшее расширение поля GF(2m), содержащее все корни G(x). Тогда число 2т-ичных проверочных символов кода К2 Хемминга над GF(2m) равно r p и экономия памяти для ОД в целом составит

II

/ (Z,(n m))/irrri V/ P- где v Eni

число ТЭЗов в ОД. Максимальная экономия памяти получится, если каждая область содержит m п (2тр - 1)/(2т-1) ТЭЗов. i ТТ, где п -длина кода Хемминга. Тогда fi l(2mp-1)/(2m-1)(p-1)/p.

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

Интервальное значение числа-лроверочных символов, обозначаемое через может быть оценено из выражений для нижней

границы ВаршамоваТильберта и верхней

границы Хемминга.

Используя эти выражения, можно записать

/Ч О

l 2 |{:ln(2m-1))cil(2m-i)1

где d - минимальное расстояние кода «2, выбор которого определяется характером возможных искажений кодовых слов

t (d-1)/2 - кратность неисправностей; a - целая часть а; m - длина сигнатуры; п - максимальное по областям число ТЭЗов (или длина кода to). Отсюда JLи СЬ2

(2n-1)

logjlTc nCZ - O i/m

и интервальное значение суммарной экономии, определяемое как , лежит в пределах /г и и. где

v0-2 .

/ vm/(log2 gCn P1 -)1):

/z vm/(log2 XCn (2m-1) DI.

Использование устройства является экономически выгодным, если ft 1, и тем самым более выгодным, чем больше/ .

Если /$ 1 , а /) 1 , то целесообразность использования устройства зависит от конкретно выбранного кода «2. Если для этого кода точечное значение /г 1 , то использование устройства является экономически выгодным, если же 1 , то использовать устройство невыгодно.

Локализация искаженных банков данных производится аналогично. На вход Данные блока 1 поступает непосредственно содержимое банков.

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

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

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

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

5 формирования сигнатур и блока клавиатуры и входам блока индикации и образует шину данных устройства, группы адресных и управляющих выходов центрального процессора соединены с одноименными группами

0 входов блока внешней памяти программ контроля, блока оперативной памяти, блока постоянной памяти программ формирования сигнатур, блока клавиатуры, сигнатурного анализатора и блока индикации и

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

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

5 дешифратора соединен с вторым входом элемента И и входом разрешения первого шинного формирователя, выход элемента И соединен с тактовым входом формирователя сигнатур, первая группа выходов которо0 го соединена с группой информационных входов первого шинного формирователя, группа выходов которого соединена с группой информационных входов формирователя сигнатур, вторая группа выходов

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

см

S

Включение.

,itb--251

I I

0б/3дгб /ft Ct.tf .:„Снягь сигнаг. сT33aTJ

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

I / I

Переписать сигнат Sj и$ cfa. 1 б pti.A Ллока / {

.1

BttfanсоЭерж../)Ј,с.на. ш.дан. и оеущ.e4Јui.b.t

Htr

far

ВыЪатьпноль на. w.Aw Uocyiq.tJfut fa. и

нет

ВыЪаП на Јл.6емЈщ.: Неиеярайн ТМ П

ВыЪать на $л,6сооЈщ.:„№иепра#ные ТЭЗы oTtyTerS.

l

Выйеаь nafabnoftn.: fftaeape/енТЗЗГ%

±

( Останов )