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

Синтез самопроверяемых дискретных устройств по BDD-реализациям их функционирования

Устанавливается, что покрытие И, ИЛИ, НЕ элементами BDD-представления системы булевых функций с целью получения комбинационной схемы С обеспечивает монотонное проявление одиночных константных неисправностей полюсов элементов схемы С на ее выходах. Рассмотрены подходы к обеспечению самопроверяемости схемы С, основанные на использовании детекторов двурельсового кода, (ш, п)-кода и кода Бергера.

We deal with the combinational circuits derived from BDD descriptions.pdf Введение Распространенный подход к синтезу комбинационных схем или комбинационных составляющих синхронных последова-тельносгных схем заключается в получении в качестве задания на синтез минимизированной системы булевых функций в интервальной форме. Примененные к системам методы синтеза [1-3] обычно «сохраняют систему», и по схеме с помощью суперпозиции, не сопровождающейся склеиванием и поглощением конъюнкций, можно получить систему булевых функций практически в той же интервальной форме. Отличие может заключаться лишь в наличии повторяющихся интервалов или в повторяющихся буквах конъюнкций, представляющих интервалы системы Самопроверяемость схемы достигается обеспечением специальных свойств интервальной формы. Например, характеристики интервалов являются равновесными кодами или кодами Бергера [4,5]; множества интервалов системы могут быть монотонными [6] или частично монотонными и т.д. Фак-торизационные методы синтеза, двухуровневые [1, 2] и многоуровневые [3J, выполненные по специальным интервальным формам, обеспечивают монотонное проявление константных неисправностей полюсов вентилей полученных схем. Под монотонным проявлением неисправности понимается следующее. Если а - тестовый набор для неисправности v в схеме С, а Р и Р" - векторы, сопоставляемые выходам схемы в исправном и неисправном состояниях соответственно, то Р и Р" сравнимы, т.е. либо Р^З"либо Р^З". Напомним, что векторы р, Р" находятся в отношении Р^Р" (здесь р - предшествующий набор, а Р" - последующий), если для каждой ю компонент выполняется условие Р, Например, 010010 а, £ а2. Например, X={хь хь ху, х«}, a,=100001, дг» с*2=101101, а, йа2. Система F частично монотонна относительно подмножества Л* переменных, если для любой пары булевых векх• торов ai, а2 таких, что а, < а2, выполняется условие ЯаО^аг) (Pi^ Pt-^otiX fc=F(a.d)). Например, система двух уравнений /, = х, v х3 v х4 v х5 v х6 к/2=х^2 является частично монотонной относительно подмножества переменных Х*={х1^с2&&}- Покажем, что неисправности из U проявляют себя монотонным образом. Теорема 1. Неисправность из U либо не проявляется на выходах схемы С, либо проявляется на них монотонно. Доказательство. Рассмотрим функции, сопоставляемые элементам полученной схемы и зависящие от входов элемента. Каждая из функций зависит в общем случае от входных и внутренних переменных схемы. В вышеизложенном методе построения схемы инверторы используются только на внешних полюсах схемы. Это значит, что все функции элементов схемы частично монотонны по внутренним переменным. Неисправность на полюсе элемента схемы проявляется (при соответствующем входном наборе a, поступающем на схему Q на выходе элемента сменой значений 1 -> 0 или 0 1. Выход элемента сопоставляется внутренней переменной схемы. В силу частичной монотонности всех функций схемы по внутренним переменным смена 1 -> 0 (0 1) распространяется на подмножество элементов, связанных с неисправным, и либо дойдет до выходов схемы, либо «заглохнет», оставив выходы схемы неизменными. Выделим в схеме С, реализующей/ /, два элемента. Их выходы соответствуют выходам схемы, а входы сопоставляются внутренним и, возможно, некоторым входным переменным схемы. Рассматриваемые элементы реализуют систему функций /',/' от соответствующих переменных, частично монотонную по внутренним переменным. Обозначим ее F'. Система F' в исправном состоянии реализует на своих выходах значения 10 или 01. Пусть в присутствии неисправности входным переменным системы сопоставляется 1-монотонно измененный вектор р", Р^Р", где р - вектор, соответствующий входному набору а в исправном состоянии схемы С. Тогда F'(P) й F'(pv). В случае 0-монотонно измененного вектора Р", (Р" f'n, где/и-число выходов схемы С. Отличие этого метода от предыдущего состоит в отсутствии необходимости реализации инверсий функции. Это достигается иеной введения дополнительных выходных переменных. В зависимости от конкретной системы булевых функций выбирается тот метод обеспечения самопроверяемости, который требует меньших дополнительных аппаратурных затрат. При этом необходимо учитывать как затраты на реализацию самопроверяемой схемы, так и соответствующих детекторов.

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

Авторы

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

Ссылки

Закревский А.Д., Балаклей Л.И., Елисеева Н.А. и др. Синтез асинхронных автоматов на ЭВМ. Минск: Наука и техника, 1975. 181 с.
S. Baranov. Logic synthesis for control automata // Dordrecht; Boston; London: Kluwer academic publishers, 1994.
K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli and A.R. Wong. MIS: A multi-level logic optimization program // IEEE Trans. On com puter-aided design. Nov. 1987. Vol. 7. P 1062-1081.
Levin, M. Karpovski On-line self-checking of microprogram control unit // 4 IEEE Intl. On-line testing workshop. Capry, Italy, July 1998. P152-156.
A. Yu. Matrosova. S.A. Oslanin Self-checking synchronous FSM network design // 4"1 IEEE Intl. On-line testing workshop. Capry, Italy, July 1998. P. 162-166.
Астафьев M.B., Левин И., Матросова А.Ю., Синельников В. Синтез самопроверяемых автоматных сетей в базисе ПЛМ // Автоматика и телемеханика (в печати).
Агибалов Г.П., Оранов A.M. Лекции по теории конечных автоматов. Томск: Изд-во ТГУ, 1984. 185 с.
Е Randal Bryant graph-based algorithms for boolean function manipulation // IEEE transactions on computers. August 1986. Vol. C-35, № 8.
A. Yu. Matrosova, S. A. Oslanin Self-checking FSM design with observing only FSM outputs // 4lh IEEE Intl. On-line testing workshop. Capry, Italy, July 1998.Italy, July 1998.
 Синтез самопроверяемых дискретных устройств по BDD-реализациям их функционирования | Вестн. Том. гос. ун-та. 2000. № 271.

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

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