Метод синтеза неизбыточных схем в стандартном базисе, допускающих единичные диагностические тесты длины два Текст научной статьи по специальности «Математика»
Актуальность и цели. Цель данной работы состоит в демонстрации возможности синтеза (для произвольной функции алгебры логики) схемы из функциональных элементов в стандартном базисе, реализующей эту функцию и допускающей единичный диагностический тест длины не более двух при инверсных неисправностях на выходах элементов , что может быть полезно при проектировании легкотестируемых СБИС. Материалы и методы. При получении основных результатов использовались методы алгебры логики и теории синтеза схем из функциональных элементов . Результаты. Доказывается, что для произвольной функции алгебры логики f, зависящей от n переменных, существует неизбыточная реализующая функцию f схема из функциональных элементов в базисе < x & y, x Ú y, Ø x >, допускающая единичный диагностический тест длины не более двух при инверсных неисправностях на выходах элементов , при этом для каждой булевой функции установлена длина минимального единичного диагностического теста .
Похожие темы научных работ по математике , автор научной работы — Романов Дмитрий Сергеевич
A METHOD OF SYNTHESIS OF IRREDUNDANT CIRCUITS (IN A STANDARD BASIS) ADMITTING SINGLE FAULT DIAGNOSTIC TEST SETS WITH CARDINALITY 2
Background. The aim of this work is to demonstrate that for an arbitrary Boolean function it is possible to construct a circuit (in the basis < x & y, x Ú y, Ø x >) realizing this function and allowing a small single fault diagnosing test set (under inverse faults on outputs of gates). It can be useful for the design of easily testable VLSI. Materials and methods. The theory of Boolean functions and combinational circuits design methods were used. Results. It has been established that for arbitrary Boolean function f depending on n variables there exists an irredundant combinational circuit (in the basis < x & y, x Ú y, Ø x >) realizing f and admitting a single fault diagnosing test set (under inverse faults on outputs of gates) with cardinality 2 or less. For every Boolean function the minimal cardinality of a single diagnostic test set has been established.
Текст научной работы на тему «Метод синтеза неизбыточных схем в стандартном базисе, допускающих единичные диагностические тесты длины два»
МЕТОД СИНТЕЗА НЕИЗБЫТОЧНЫХ СХЕМ В СТАНДАРТНОМ БАЗИСЕ, ДОПУСКАЮЩИХ ЕДИНИЧНЫЕ ДИАГНОСТИЧЕСКИЕ ТЕСТЫ ДЛИНЫ ДВА1
Актуальность и цели. Цель данной работы состоит в демонстрации возможности синтеза (для произвольной функции алгебры логики) схемы из функциональных элементов в стандартном базисе, реализующей эту функцию и допускающей единичный диагностический тест длины не более двух при инверсных неисправностях на выходах элементов, что может быть полезно при проектировании легкотестируемых СБИС.
Материалы и методы. При получении основных результатов использовались методы алгебры логики и теории синтеза схем из функциональных элементов.
Результаты. Доказывается, что для произвольной функции алгебры логики f, зависящей от n переменных, существует неизбыточная реализующая функцию f схема из функциональных элементов в базисе , допускающая единичный диагностический тест длины не более двух при инверсных неисправностях на выходах элементов, при этом для каждой булевой функции установлена длина минимального единичного диагностического теста.
Ключевые слова: схема из функциональных элементов, диагностический тест, инверсная неисправность на выходе элемента, функция Шеннона, легко-тестируемая схема.
A METHOD OF SYNTHESIS OF IRREDUNDANT CIRCUITS (IN A STANDARD BASIS) ADMITTING SINGLE FAULT DIAGNOSTIC TEST SETS WITH CARDINALITY 2
Background. The aim of this work is to demonstrate that for an arbitrary Boolean function it is possible to construct a circuit (in the basis ) realizing this function and allowing a small single fault diagnosing test set (under inverse faults on outputs of gates). It can be useful for the design of easily testable VLSI.
Materials and methods. The theory of Boolean functions and combinational circuits design methods were used.
Results. It has been established that for arbitrary Boolean function f depending on n variables there exists an irredundant combinational circuit (in the basis ) realizing f and admitting a single fault diagnosing test set (under inverse faults on outputs of gates) with cardinality 2 or less. For every Boolean function the minimal cardinality of a single diagnostic test set has been established.
Key words: combinational circuit, fault diagnostic test set, inverse fault on output of gate, Shannon function, easily testable circuit.
1 Статья написана при финансовой поддержке проектов РФФИ № 15-01-07474-а и № 16-01-00593-а.
Задача построения близких к минимальным тестов [1-3] для схем из функциональных элементов (СФЭ) [3], и, более точно, задача построения таких схем, которые допускают достаточно короткие тесты, является актуальной в теории контроля управляющих систем. Все несформулированные в статье определения (СФЭ, источник неисправностей, константная неисправность, инверсная неисправность, проверяющий тест, диагностический тест, единичный тест, полный тест, длина теста, минимальный тест) могут быть найдены в книгах [3, 4]. Введем обозначения для базисов: Во = - стандартный базис, В1 = - базис Же-галкина,
Неисправность в схеме назовем нетривиальной, если хотя бы на одном входном наборе на выходе хотя бы одного элемента схемы оказалось неверное значение. Тестопригодной (относительно источника неисправностей и) назовем схему, функционирование которой при любой нетривиальной неисправности (вызванной источником неисправностей и) отличается от функционирования исправной схемы. Схему, тестопригодную относительно источника одиночных неисправностей, назовем неизбыточной. Под длиной минимального проверяющего (соответственно диагностического) теста относительно источника неисправностей и для булевой функции /, реализованной с помощью СФЭ в базисе В, будем понимать минимум по всем реализующим / тестопригодным схемам длины минимального проверяющего (соответственно диагностического) теста для схемы, а обозначать эту длину будем через
£Месг(и,у) (¡ап(и,у)). Через р2(п) обозначим множество всех булевых функций, существенно зависящих от всех своих п переменных х1 , х2. , хп . Функцию Шеннона длины проверяющего (соответственно диагностического) теста относительно источника неисправностей и для реализованной с помощью СФЭ в базисе В булевой функции / определим так:
^ (и п) = __„ ¡¿е** (и у) (¡Вф (и,п) = тах 4а8п (и, /)^
l(un) = тах щксl(u j)
Обозначение для источника неисправностей будет иметь вид XZy , где X - это последовательность букв (или буква), характеризующая место возможной неисправности (P - на входах схем, I - на входах элементов, O -на выходах элементов), y указывает на вид неисправности (const, 0, 1 -константные, типа 0, типа 1 соответственно, inv - инверсные неисправности), z указывает на максимально возможное число поломок (k, если число поломок не превосходит k ; нижний индекс опускается при отсутствии ограничений на число поломок).
Дадим обзор результатов о поведении функций Шеннона длин тестов для СФЭ (все оценки справедливы при произвольном натуральном n).
ЬсЦ1ес'(Юскот',п) < 4 + 2 I ■ (см. [6] с применением техники из [3, 1 ]=1 ^ ■!) с. 113-116]). В произвольном полном базисе В [7, 8]:
detect /r^const \ ,■ ^/^Ги/21 и/2 I ч D
B (О , и) < 2(2 ' + 2L J + и); в B0:
lB:tect(10,и) = Ldletect(I\и) < О(2и/2) [9],
(О0, п) = (О1, п) < 2п + 1 [11].
Ца^(в-0,п) = Ь^(О1,п) < 2 Г1ов2(п + 1)1 + 1, ьВа^поп,п) < п + 1 [12, 13],
В произвольном полном базисе имеет место оценка
Ь^е^а (вест*,< п + 3 [14-16]. В работе [17] дан метод построения для каждой булевой функции /(Хп) схемы с тремя добавочными входами и одним добавочным выходом, допускающей проверяющий не более чем к произвольных неисправностей элементов или блоков схемы тест длины О(п + 2к). В базисе В™ = и ^