Тестопригодное логическое устройство Советский патент 1989 года по МПК G06F11/25 

ел

о: со ел

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

Известно, что длина проверяюп1его теста логических элементов И и ШШ равна L q + 1, где q - число входов элемента, в то время как длина проверяющего теста элементов РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ постоянна и равна трем. При этом элемент РАВНОЗНАЧНОСТЬ может вьтолнять

Устройство по фиг. 1 содержит элементы НЕРАВНОЗНАЧНОСТЬ 1.1, ... , 1.8, группы информационных входов 2 устройства, настроечные входы 3, 4 устройства, выход 5 устройства, элементы РАВНОЗНАЧНОСТЬ 6.1, ..., 6.4, элементы НЕРАВНОЗНАЧНОСТЬ 7.1, 7.2,

функцию конъюнкции при использовании t5 элемент РАВНОЗНАЧНОСТЬ 8. ,Устройство

по фиг. 2 содержит элементы 9.1,..., 9.П сравнения (п - разрядность информационного слова устройства),элементы 10.1, .,., Ю.т сравнения (т 20 число терм, реализуемых устройством), элементы 11.1,...,11.q сравнения, элемент 12 сравнения, выход 13 устройства. На фиг., 3 обозначены элементы РАВНОЗНАЧНОСТЬ 14.1,..., t4.8,

25 элементы НЕРАВНОЗНАЧНОСТЬ 15.1

15.3.

Тестопригодное логическое устройство работает следующим образом.

Для реализации функции конъюнкции

одного из его входов в качестве входа настройки и подаче на него сигнала 1. Элемент НЕРАВНОЗНАЧНОСТЬ может выполнять функцию дизъюнкции при подаче на вход настройки О. Однако объективно существуют ограничения на количество входов любого логического элемента, которые приводят к необходимости построения многоуровневых древовидных схем для реализации функций от большого числа Переменных (функции И, ИЛИ, И-ИЛИ, и т.п.). Недостатком таких схем является то, что длина теста зависит от

количества входов. Так, например, дляjg от большого числа переменных выбираются элементы древовидной структуры. РАВНОЗНАЧНОСТЬ, а сигналы управления и, 1; Uj 1. Тогда каждый элемент схемы выполняет функцию конъюнкции

многоуровневых И и РШИ L п + 1.

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

Решение задачи синтеза тестов для комбинационных схем произвольной функциональности может быть заменено синтезом тестопригодных схем под фиксированньш тест. Тогда для автономной проверки различных комбинационных схем в составе сложного устройства (например БИС) может быть использован один и тот же генератор фиксированного теста. В этом случае тест сложного устройства представлен алгоритмом последовательного тестирования (посредством фиксированного теста) отдельных комбинационных узлов и связей между ними. В результате трудоемкость составления теста для сложного устройства практически не зависит от аппаратурной сложности.

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

35

40

f(x,-, и) Д

Ч-« V Л х;

(1.-1

при и - 1, f(x;) А

i 1

а все устройство - функцию конънЬнк- ции от п-переменных.

Для реализации функции дизъюнкции выбираются элементы структуры НЕРАВ- 45 НОЗНАЧНОСТЬ, а сигналы управления У Oi и2. О Тогда каждый элемент схемы выполняет функцию, дизъюнкции

50

Ч-1 V- f(x;, и) ( Vx; V и)Л( V X, V и)

-. и о, f(x-) .V

при

I

55

а все устройство - функцию дизъюнкции от п-переменных.

Проверяющий тест таких многоуровневых логических схем, построенных на базе элементов РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ, независимо от pea

На фиг. 1 представлена схема реа- лиза ции тестопригодного логического устройстваJ на фиг. 2 - общий принцип построения устройства, основанный на древовидной структуре; на фиг. 3 - конкретный пример.

Устройство по фиг. 1 содержит элементы НЕРАВНОЗНАЧНОСТЬ 1.1, ... , 1.8, группы информационных входов 2 устройства, настроечные входы 3, 4 устройства, выход 5 устройства, элементы РАВНОЗНАЧНОСТЬ 6.1, ..., 6.4, элементы НЕРАВНОЗНАЧНОСТЬ 7.1, 7.2,

элемент РАВНОЗНАЧНОСТЬ 8. ,Устройство

35

f(x,-, и) Д

Ч-« V Л х;

40

(1.-1

при и - 1, f(x;) А

i 1

а все устройство - функцию конънЬнк- ции от п-переменных.

Для реализации функции дизъюнкции выбираются элементы структуры НЕРАВ- НОЗНАЧНОСТЬ, а сигналы управления У Oi и2. О Тогда каждый элемент схемы выполняет функцию, дизъюнкции

Ч-1 V- f(x;, и) ( Vx; V и)Л( V X, V и)

-. и о, f(x-) .V

при

I

а все устройство - функцию дизъюнкции от п-переменных.

Проверяющий тест таких многоуровневых логических схем, построенных на базе элементов РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ, независимо от peaлизуемой функции, количества логических элементов, числа входов и уровней всегда является постоянным. Состав такого теста приведен в табл. 1.

Таблица

м.

1451695

мается усеченная таблица истинности логического элемента, покрытие которой гарантирует проверку всех одиночных константных неисправностей этого элемента. Тогда покрытие проверяющим тестом всех элементарных тестов схемы гарантирует обнаружение всех одиночных константных неисправ- - 10 ностей этой схемы. Ниже приведены

элементарные тесты q-входоБых элемен- тов РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ, состоящие из трех элементарных проверок. Набор fxX...XJ мо- 15 жет быть произвольным, кроме {ос...о и 11...l.

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении БИС с самодиагностикой. Цель изобретения - повьшение быстродействия. В изобретении рассматривается построение устройства, выполненного по древовидной схеме и реализованного на элементах РАВНОЗНАЧНОСТЬ (НЕРАВНОЗНАЧНОСТЬ), что позволяет производить контроль фиксированным тестом, т.е. данное устройство является моделью, от которой можно перейти к конкретному устройству, реализующему произвольную булеву функцию п-пёременных. 3 ил., 3 табл.

Необходимо доказать, что приведенный в табл. 1 проверяющий тест обнаруживает все неисправности из класса .одиночных константных неисправностей для логических схем, построенных предложенным способом.

Для доказательства воспользуемся понятием элементарного теста и методом построения проверяющих тестов, основанным на покрытии элементарных тестов (модифицированный алгоритм Рота) . Под элементарным тестом пони1.

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

РАВНОЗНАЧНОСТЬ пяти уровней и покрытие их четырьмя тестовыми наборами из табл. 1. В столбцах, обозначенных () помечаются те элементарные проверки, которые покрываются

соответствуннцим тест-набором:

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

Бьио показано, что для реализции . функций конъюнкции и дизъюнкции на управляющие входы U (3) и 2.. должны быть поданы взаимоинверсные сигналы. Для обеспечения этих условий при прежнем числе входов управления элементы НЕРАВНОЗНАЧНОСТЬ К -уровней имеют инверсный вход наст ройки. При этом сигналы управления в основном режиме сохраняют свои значения.

Проверяющий тест.логических схем, построенных на элементах РАВНОЗНАЧ20

исправностей и является фиксированным 15 НОСТЬ и НЕРАВНОЗНАЧНОСТЬ, вьшолняю- независимо от выполняемой функции, числа элементов, входов и уровней. Можно доказать справедливость утверждения для схемы, построенной на элементах НЕРАВНОЗНАЧНОСТЬ и реали- зукицих функцию ИЛИ.

Число уровней К, количество элементов в каждом уровне N; в зависимости от количества входов п, (переменных) и от ограничения на количество входов логического элемента РАВНОЗНАЧНОСТЬ, q (НЕРАВНОЗНАЧНОСТЬ) может быть рассчитано по формулам:

25

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

Доказательство утверждения аналогичное описанному выше.

Поскольку описание логики работы любого устройства в совершенной дизъюнктивной или конъюнктивной нормальной форме является универсальК log п,з

.N. п;

1 ;1 (1.к).

где nj количество входов в каждом i-M уровне схемы.

Для построения многоуровневой схемы на элементах РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ, реализующей в основном режиме функцию И-ИЛИ п-переменных т-конституент воспользуемся полученными ранее тестопригод- ными структурами многоуровневых И и ИЛИ, построенных на элементах РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ. Тогда количество уровней К будет равно

к - к, + к i

К. log., К loga-,m .

Бьио показано, что для реализции . функций конъюнкции и дизъюнкции на управляющие входы U (3) и 2.. должны быть поданы взаимоинверсные сигналы. Для обеспечения этих условий при прежнем числе входов управления элементы НЕРАВНОЗНАЧНОСТЬ К -уровней имеют инверсный вход настройки. При этом сигналы управления в основном режиме сохраняют свои значения.

Проверяющий тест.логических схем, построенных на элементах РАВНОЗНАЧ

НОСТЬ и НЕРАВНОЗНАЧНОСТЬ, вьшолняю-

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

Доказательство утверждения аналогичное описанному выше.

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

Дли общего случая устройства, показанного на фиг. 2, при реализации функции конъюнкции от п-переменных выбираются элементы многоуровневой древовидной структуры РАВНОЗНАЧНОСТЬ,

U равны 0.

Uo U,, .,

Проверяющий тест для такого класса тестопригодных схем имеет типовой состав, приведенный в табл. 2 (для структуры из элементов РАВНОЗНАЧНОСТЬ) и в табл. 3 (для структуры из элементов НЕРАВНОЗНАЧНОСТЬ).

К+1 11

Кн-2 00

00 1

00 ... о

Таблица 2

Таблица 3

О 1

1

о 1

Из табл. 2 и 3 видно, что тесто- пригодное устройство проверяется всего на двух информационных наборах - все О и все 1 при подаче на входы управления U, , Uj, ., U всех единиц (нулей) и бегущий ноль (единица).

На практике ограничено применение схем, реализующих в отдельности функцию конъюнкции либо только функцию дизъюнкции от большого числа переменных. Наиболее часто используются схемы, описываемые минимизированными дизъюнктивными либр конъюнктивными нормальными формами. Это схемы И-ИЛИ (ИЛИ-И) с произвольным числом объединения по И и по ИЛИ, а также с инверсиями на входе.

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

Пример (фиг. 3). Пусть дана булева функция, представленная в МДНФ:

f X,Xj V V XjXgX.

Необходимо синтезировать комбинационную схему, реализующую данную функцию в основном режиме и проверяемую фиксированным тестом (табл.2

Синтез осуществляется по следующей методике.

Необходимо определить число уровней К, максимального

V, , реализующих конъюнкцию от

числа переменных

(х,х,,х,х,;) .

К, log,., 4 2.

Схемную реализацию данного терма обозначим II. Дерево схемной реали- . зации терма (xtXz.) вырожда.ется, как показано на фиг. 3, а терма (xjXg .X,) - III. Реализация дизъюнкции от трех термов обозначена IV,

К lo-g5.. 3 2.

Для обеспечения проверки устройства фиксированным тестом из табл.1, необходимо элементы с 1-го по К,-и уровень (2) выбрать РАВНОЗНАЧНОСТЬ, элементы (К, + 1)-го уровня (3) выбрать НЕРАВНОЗНАЧНОСТЬ, элементы с (К + 2)-го уровня по К-й (К К, +

1451695

10

+ K,j,) - НЕРАВНОЗНАЧНОСТЬ с инверсным входом настройки.

Очевидно, что при подаче в основ-й (Uj-й) вход

ном режиме на Уц ,

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

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

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

Тестопригодное логическое устрой0 ство, содержащее первый элемент

РАВНОЗНАЧНОСТЬ, выход которого является выходом устройства, первый вход элемента РАВНОЗНАЧНОСТЬ является первым настроечньм входом устройст5 ва, отличающееся тем, что, с целью повышения достоверности контроля, устройство дополнительно содержит десять элементов НЕРАВНОЗНАЧНОСТЬ и четыре элемента РАВНО0 ЗНАЧНОСТЬ, причем группы входов

элементов НЕРАВНОЗНАЧНОСТЬ с первого по восьмой включительно образуют группы информационных входов устройства, входы элементов НЕРАВНОЗНАЧНОСТЬ- с первого по восьмой включительно объединены и подключены к второму настроечному входу устройства, а также соединены с первыми входами девятого и десятого элементов

40 НЕРАВНОЗНАЧНОСТЬ, выходы которых

соединены с вторым и третьим входами первого элемента НЕРАВНОЗНАЧНОСТЬ, первые входы второго, третьего, четвертого и пятого элементов РАВНОЗНАЧНОСТЬ объединены и соединены с первым управляющим входом устройства, выходы первого и второго элемеи-; тов НЕРАВНОЗНАЧНОСТЬ соединены с вторым и третьим входами второго эле-

gQ мента РАВНОЗНАЧНОСТЬ, выходы третьего и четвертого элементов НЕРАВНОЗНАЧНОСТЬ соединены с вторым и третьим входами третьего элемента РАВНОЗНАЧНОСТЬ, выходы пятого и шес- 55 того элементов НЕРАВНОЗНАЧНОСТЬ соединены с вторым и третьим входами четвертого элемента РАВНОЗНАЧНОСТЬ, второй и третий входы пятого эле- РАВНОЗНАЧНОСТЬ соединены с вы

ходами седьмого и восьмого элементов НЕРАВНОЗНАЧНОСТЬ, выходы второго и третьего элементов РАВНОЗНАЧНОСТЬ соединены с вторым и третьим входами девятого и десятого элеменcfjus.i

1451695

1 2

тов НЕРАВНОЗНАЧНОСТЬ, второй и третий входы десятого элемента НЕРАВНОЗНАЧНОСТЬ соединены с выходами четвертого и пятого элементов РАВНОЗНАЧНОСТЬ.

IP./

Ю.1

Зк

Фиг.