Синтез самопроверяемого комбинационного детектора равновесных кодов | Вестн. Том. гос. ун-та. 2000. № 271.

Синтез самопроверяемого комбинационного детектора равновесных кодов

Предлагается Memacbyntpf комбинационного детектора (т, л)-кодов. Метод основан на разложении кодов по заданному разбиению компонент кодов на два подмножества. Многократное применение разложения приводит к представлению всевозможных (от, п)-кодов формулой над множеством функций {л,Dp(X)}. Здесь Dp(X) - ДНФ, представ-ляющая всевозможные (q, р)-коды в подмножестве переменных X', X' с X , где X - {jt,.....х„}~ множество пере-менных, сопоставляемых входам детектора, q й т, р < п . Обсуждается возможность синтеза детектора в базисе FPGA (field of programmable gate array), а также проблема обеспечения его самопроверяемости в классе неисправностей, обусловленных этим базисом.

Self-testing combinational (m-n)-code checker design.pdf Самопроверяемые детекторы комбинационного типа, описанные в работах [1, 2] ориентированы на относительно небольшое число равновесных кодов (или кодов Бергера), достигаемых проверяемым дискретным управляющим устройством на его выходах в исправном состоянии. При этом в работе [1] допускаются как равновесные коды, так и коды Бергера, предполагается реализация детектора на ПЛМ. В работе [2] вообще не требуется кодировать выходы проверяемого устройства, однако предполагается специальная двухуровневая факТориЗационна* реализация совместно управляющего устройства и детектора В нашей работе предлагается компактная, по сравнению с [I, 2], реализация самопроверяемого комбинационного детектора, сложность которого линейно зависит от длины п равновесного кода Детектор реализует все (т, riyкоды, либо их подмножества, содержащие (т, и)-коды, достигаемые на выходах проверяемого устройства; его реализация ориентирована на FPGA (field of programmable gate arrays) технологию [3]. Никаких ограничений на реализацию проверяемого дискретного управляющего устройства не накладывается. Важно лишь, чтобы его неисправности проявляли себя на выходах устройства монотонным образом. К выходам проверяемого управляющего устройства подключены входы детектора (рис. 1). Выходы ym+i,-,yJ обеспечивают равновесность кодов. Я Ут ▲ к L ДУУ к. Л W Ут+1 ^ W w Рис. 1 Пусть детектор реализует функцию /, принимающую значение 1 на (т, и)-коде и 0 в остальных случаях. Дискретное управляющее устройство (ДУУ) проявляет любую неисправность из рассматриваемого класса его неисправностей монотонным образом. Имеется в виду следующее. Пусть а - произвольный тестовый набор для некоторой неисправности w,weW, Р,Р* - выходы исправного и неисправного устройств соответственно, сопоставляемые а. В случае монотонного проявления неисправностей из W Р,Р" - сравниваемые векторы (наборы), т.е. либо Р^Р", либо р" ^р. Это значит, что для любого а и любой неисправности w мы имеем на выходах устройства вектор Р", не являющийся (т, riyкодом. Такой вектор обращает в 0 функцию /, реализуемую детектором. Следовательно, любое проявление неисправности из W немедленно обнаруживается детектором. Представим функцию, реализуемую детектором, в виде ДНФ. Она является совершенной, одновременно сокращенной, кратчайшей и минимальной, так как склеивания между конъ-юнкциймй йовершенйой ДНФ, реализующей (rt, й^коди, не* возможны. Обозначим ее через £>" = ktv k2 v...vi ,. Любые две конъюнкции кь kj из D™ ортогональны не менее чем по двум переменным. Более того, они инверсно ортогональны не менее чем по двум переменным. Конъюнкции kt, kj инверсно ортогональны по переменным xs, хг, если в kt xs содержится без инверсии, а в kj - с инверсией; в то же время хг содержится в к, с инверсией, а в kj - без инверсна Например, конъюнкции х1х2х}х4, xlx2xix4 ДНФ D", представляющей (2, 4)-коды, инверсно ортогональны по х, их,. Число конъюнкций D", реализующей всевозможные (т, л)-коды, равно С", что уже при «=10, т = 5 достигает 252, а число букв - 1260. Использовать такую ДНФ в качестве задания на синтез для последующего применения известных двухуровневых [4] и многоуровневых [5] методов синтеза не представляется целесообразным ввиду громоздкости получаемых в результате схем. Предлагается специальный метод разложения D™ по подмножествам переменных. 1. Декомпозиционный метод синтеза детектора равновесных кодов 1.1. Построение скобочной формы А Представим D" (Х),Х = {х......*„} формулой А над множеством функций a,v, Dp(Xr), причем p распределение весов по разбиению для этого поддерева: /', = 2, /2 = 0, /3 = 1. Предложение 2. Различным, существенным лодч деревьям GA сопоставляется одно и то же разбиение множества X на подмножества Хх,...,Х'*х. Предложение 3. Различным существенным поддеревьям Ga сопоставляются различные распределения весов по разбиению. Предложение 4. Различные распределения весов по разбиению отличаются друг от друга не менее чем по двум компонентам. Предложение 5. Существенное поддерево представляет функцию D'jiX1) ■ D't2(X2) D'„-(X') • D';«(X'+>) (произведение ДНФ), задающую все (от, и)-коды с распределением (/,,/2,-.,/,,/,+,) весов. Назовем это произведение ДНФ характеристикой существенного поддерева. Характеристика существенного поддерева представляет подмножество (т, riy- кодов, которые могут быть представлены ДНФ, полученной перемножением соответствующих D4p(Xr) этой характеристики. Предложение 6. Каждому (от, и)-коду сопоставляется единственное существенное поддерево в Ga . Подстановка сопоставляемого (от, и)-коду булева вектора в формулу А обращает в единицу ДНФ, порожденную характеристикой поддерева GA, и только эту ДНФ. Предложение 7. Объединение (от, и)-кодов, представляемых характеристиками всех существенных поддеревьев Ga , есть множество всех (т, л)-кодов. В [6] предложен метод перебора всех существенных поддеревьев. Зная множество М(т, п) - кодов, достижимых на выходах проверяемого ДУУ, можно упростить дерево Ga (формулу А), исключая в Ga существенные поддеревья, реализующие (от, и)-коды, не принадлежат щие М. Операция исключения существенного поддерева сводится к замене на константу 0 пары D4p(Xr) нижнего яруса дерева из характеристики этого поддерева. Речь идет о D* (Xf), принадлежащих только рассмат-» риваемому поддереву. Приписывание констант 0 концевым вершинам существенных поддеревьев приводит к упрощению Ga по правилам, описанным в [6]. 1.3. Построение схемы самопроверяемого детектора по формуле А Структура формулы А представлена деревом Ga (возможно, упрощенным). Каждый элемент (CLB), реализующий Dp(Xr), удовлетворяет условию р й к. Здесь к < 4 или к i(,V') о!(х') dl(x') d'(x') Djf-V') D,"(.V') Рис. 2. Дерево GA для ДНФ при к = 2 Рис.3 Остановимся на реализации схемы С по формуле А (представляющему ее дереву GA, в том числе упрощенному). Пусть каждая функция вида Dqp(Xr) реализуется на одном из выходов CLB. Один и тот же CLB ^ можно использовать для реализации двух функций одного и того же множества переменных'. 5то необходимо ' учитывать при покрытии различных функций D4p(Xr) с помощью CLB для сокращения числа CLB-элемешов. Выражение вида и,и,+2 v...vw,+1«J(t+1) (2) можно реализовать тремя CLB. В (2) переменные и,...и4+1 сопоставляются функциям D', а переменные м*+2-и2(*+о либо функциям того же вида, либо скобкам одной и той же глубины. ДНФ (2) задана поддеревом, обведенным в GA (рис. 2). Число конъюнкций в (2) может быть менее (к + 1) и определяется соотношением (1). Пусть к = 8. С помощью CLB1 реализуем первые 4 конъюнкции из (2), затем с помощью CLB2 - следующие 4 конъюнкции и, наконец, CLB3 реализует функцию ю, vffl2v«(tlK2(M)) (3) где щ,аг - переменные, сопоставляемые выходам CLB1 и CLB2 соответственно. Обозначим дубль схемы С через Сд, входы схем С ,Сд общие. Схема и ее дубль образуют детектор D. Если на обоих выходах детектора достигается значение 1 - система исправна. Покажем, что система, представленная на рис. 2, полностью самопроверяемая. 2. Самопроверяемость системы ДУУ - детектор Рассмотрим неисправности детектора из множества V и неисправности проверяемого ДУУ из множества W. Всякая w eW проявляет себя на выходах этого устройства монотонным образом. Обеспечим полную самопроверяемость системы управляющее устройство-детектор простым дублированием схемы С, реализующей А. В этом случае система приобретает вид, представленный на рис. 3. Будем считать, что в системе устройство - детектор сначала возможно появление одной неисправности либо v е V, либо weW. Если детектор исправен, weW обнаружима в рабочей области функционирования устройства на выходах детектора. Если первой появляется неисправность в детекторе, она может оказаться необнаружимой в системе устройство - детектор в рабочей области функционирования устройства. Тогда детектор накапливает эту неисправность. Будем предполагать, что в нем возможно накопление не более одной неисправности. Обозначим через А/* объединение множества М со всеми А/". Здесь М" - множество векторов, достижимых на выходах ДУУ в присутствии неисправности w. Рассмотрим одиночную константную неисправность v детектора на его входном полюсе. Обозначим их множество через V", V" с V. Теорема 2. Одиночная константная неисправность на входном полюсе детектора обнаружима в М. Доказательство. Предполагаем, что в М содержатся равновесные коды как с единичным значением переменной х,, так и с нулевым значением переменной х,, сопоставляемой неисправному полюсу (иначе эту переменную можно было бы исключить, сохранив равновесность кодов в М ). Это значит,'что' при неисправности константа ноль вектор из М с единичным значением компоненты х, заменяется на некодовый, что приводит к появлению на выходах детектора z,z2 значений 00. Все элементы схемы детектора исправны. Аналогично при неисправности константа один, вектор из М с нулевым значением компоненты х, заменяется на некодовый. Это приводит к появлению на выходах детектора z,z2 значений 00. Теорема доказана. Рассмотрим неисправность v, ve{F\F"}. Теорема 3. Неисправность v е {V \ V") обнаружима в М'. Доказательство. Рассматриваемая неисправность может проявить себя на некотором (от, и)-коде из М. Так как неисправность возможна только в одной из дублирующих подсхем детектора, то в этом случае на его выходах достигаются наборы 01 или 10. Если неисправность не проявляет себя в М, то она остается необнаружимой в детекторе, накапливаясь в нем. При появлении монотонно проявляющейся неисправности в проверяемом ДУУ возможно маскирование некодового набора неисправной подсхемой детектора (другая дублирующая его подсхема исправна). Это приводит к появлению на выходах детектора наборов 01 или 10. Если маскирование не имеет места, тогда первый некодовый набор, реализуемый не выходах проверяемого ДУУ, обеспечивает значение 00 на выходах z,z2 детектора. Теорема доказана. Мы считаем, что каждая последующая неисправность v е К, или w е W появляется после того, как рабочая область ДУУ в присутствии предыдущей неисправности исчерпана. При таком предположении w е W всегда обнаружится, a v е V может остаться необнаружимой. В связи с предположением о возможности накопления в системе устройство-детектор не более одной неисправности следующая неисправность должна быть обязательно в ДУУ. На основании теоремы 3 заключаем, что она обязательно проявится на выходах детектора в рабочей области функционирования ДУУ.

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Матросова Анжела ЮрьевнаТомский государственный университетпрофессор, доктор технических наук, заведующая кафедрой программирования факультета прикладной математики и кибернетикиmau@fpmk.tsu.ru
Никитин Константин ВладимировичТомский государственный университетаспирант кафедры программирования факультета прикладной математики и кибернетикиmau@fpmk.tsu.ru
Всего: 2

Ссылки

I. Levin and М. Karpovsky. On-line self-checking of microprogram control unit // 4-th IEEE int. on-line testing workshop. Italy, Capri. July 1998. P. 152-156.
I. Levin and V. Sinelnikov, Self-checking of FPGA-based control units // Proceeding of 9" great lakes symposium on VLSI, Ann Arbor, Michigan, March 4-6,1999, IEEE press. P. 292-295.
Xilinx, the programmable logic. Data book, 1996.
S. Baranov. Logic synthesis for control automata // Kluwer academic publishers, Dordrecht / Boston / London, 1994.
R.K. Brayton, R. RudeH A. Sagiovanni-Vmcenlelli and A. R. Wang, MIS: A multiple-level logic optimization program. IEEE Trans. On computer-aided design. Nov. 1987. Vol. 7, P. 1062-1081.
Матросова А.Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во ТГУ, 1990. 206 с.
 Синтез самопроверяемого комбинационного детектора равновесных кодов | Вестн. Том. гос. ун-та. 2000. № 271.

Синтез самопроверяемого комбинационного детектора равновесных кодов | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия