Тестопригодное логическое устройство

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

А1 (19) (Ш 5Н 4 С 06 F 11/О

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ж

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (2 1) 4148860/24-24 (22) 18.11.86 (46) 15.01.89. Бюл. Р 2 (72) М.М.Татур, А.И.Белоус, А.И.Сухопаров, В.С.Шкроб, В.А.Мищенко, В.С.Панчиков, С.Н.Изотов и Л.Б.Авгуль (53) 681.3(088.8) (56) Многофункционные автоматы и элементная база цифровых ЭВМ / Под редакцией В. А. Мищенко. M.: Радио и связь, 1981, с. 73, рис. 4.8.

Авторское свидетельство СССР

N - 1196845, кл. G 06 F 11/00, 1984. (54) ТЕСТОПРИГОДНОЕ ЛОГИЧЕСКОЕ УСТРОЙСТВО (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении БИС с самодиагностикой. Цель изобретения — повьппение быстродействия. В изобретении рассматривается построение устройства, выполненного по древовидной схеме и реализованного на элементах РАВНОЗНАЧНОСТЬ (НЕРАВНОЗНАЧНОСТЬ), что позволяет производить контроль фиксированным тестом, т.е. данное устройство является моделью, от которой можно перейти к конкретному устройству, реализующему произвольную булеву функцию и-переменных. 3 ил., 3 табл.

1451695

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

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

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

Однако объективно существуют ограничения на количество входов любого логического элемента, которые приводят к необходимости построения многоуровневых древовидных схем для 25 реализации функций от большого числа йеременных (функции И, ИЛИ, И-HJIH и т.п.). Недостатком таких схем является то, что длина теста зависит от количества входов. Так, например, для 3Q многоуровневых И и ИЛИ L = n + 1.

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

35 записываемый на основании анализа логической структуры.

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

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

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

Я-<

U Ч Л х; U

4-I

Я-<

Е(х;, U) = Л х приU= 1, й(х;) = Л х;, а все устройство — функцию конъюнкции от п-переменных.

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

UI = О, U = О. Тогда каждый элемент схемы выполняет функцию. дизъюнкции при U= О, й(х;

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

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

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

Устройство по фиг. 1 содержит элементы НЕРАВНОЗНАЧНОСТЬ 1.1, 1.8, группы информационных входов 2 устройства, настроечные входы 3, 4 устройства, выход 5 устройства, элементы РАВНОЗНАЧНОСТЬ 6.1, ..., 6.4, элементы НЕРАВНОЗНАЧНОСТЬ 7.1, 7.2, элемент РАВНОЗНАЧНОСТЬ 8. Устройство по фиг. 2 содержит элементы 9.1,..., 9.п сравнения (n — разрядность информационного слова устройства),элементы 10.1, ..., 10.ш сравнения (m— число терм, реализуемых устройством), элементы 11.1, ° ...11.с сравнения, элемент 12 сравнения, выход 13 устройства. На фиг.. 3 обозначены элементы РАВНОЗНАЧНОСТЬ 14.1,... 14.8, элементы НЕРАВНОЗНАЧНОСТЬ 15.1,..., 15.3.

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

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

РАВНОЗНАЧНОСТЬ, а сигналы управления

U< = 1; U = 1. Тогда каждый элемент схемы выполняет функцию конъюнкции

1451695 мается усеченная таблица истинности логического элемента, покрытие которой гарантирует проверку всех одиночных константных неисправностей

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

00...0 и 11...1

Таблица, 1

Ф тесЛогические сигналы тового набора

U,(3) И,(4) Информационные входы (2) х,х х Е

0 0 ... 0 0

Х Х Х 1 х

0 0 ... 0 1

00 ... 0

1 0

Х X ... Х 0

1 1 ... 1 1

Х Х ... Х 1

1 ... 1 0

00 ;.. О

11 ... 1

11 ... 1

1 0

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

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

1 °

2 °

4.

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

Состав такого теста приведен в табл. 1.

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

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

5 14

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

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

Число уровней К, количество элементов в каждом уровне N,« в зависимости от количества входов и, (переменных) и от ограничения на количество входов логического элемента

РАВНОЗНАЧНОСТЬ, q (НЕРАВНОЗНАЧНОСТЬ) может быть рассчитано по формулам:

К =)log,п,t

N; = n; + 1 = " 1,з = (1»K)» где п; количество входов в каждом

i-м уровне схемы.

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

К1 К »

К, =)log,n(К = ) log,mt, 51695

10 15

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

К -уровней имеют инверсный вход наста ройки. При этом сигналы управления в основном режиме сохраняют свои значения.

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

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

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

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

Uк равны 0.

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

145 I 695

° 1 к

Выявляемые неисправности

Входы

2-ro уровня

11 .. ° 1

00 ... 0

10 ... 1

1 0

11 ... 0

0 0 0

Таблица 3

° +., Ук

Выявляемые неисправности ов00 ° .. 0

10 ... 0

01 ... 0

00-... 1

0 1

00 ... 0

1 1

Информационные входы

200...0

3 00 ... 0

К+1 00 ... 0

К+2 11 ... 1

9 Информационные входы

1 11 ... 1

2 11 ... 1

3 11 ... 1

К+1 11 ° .. 1

К+2 00 ° .. 0

Входы

1-ro уровня

Входы

1-ro ровя

Входы

2-ro уровня

Таблица 2

Входы

К-ro уровня

Входы f

К-ro

° ° °

1 1

451695 1О

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

Очевидно, что при подаче в основ10

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

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

Необходимо определить число уровней К,, реализующих конъюнкцию от максимального числа переменных (х х х х ).

К, =)logo,4(= 2.

РАВНОЗНАЧНОСТЬ, выходы пятого и шес55 того элементов НЕРАВНОЗНАЧНОСТЬ сое9 1

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

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

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

И и по ИЛИ под фиксированный тест.

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

ИДНФ: х х Y х х4х х ч х х х °

Схемную реализацию данного терма обозначим II. Дерево схемной реализации терма (х х ) вырождается, как показано на фиг. 3, а терма (х х8

° xq) — Т . Реализация дизъюнкции от трех термов обозначена IV

К =)log >, 3(= 2.

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

50 ном режиме на U +, -й (U -й) вход

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

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

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

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

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

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

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

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

2

7

1451695

Редактор И.Рыбченко

Заказ 7081/47 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 и, Dz

gz и

Составитель А.Сиротская

Техред A.Êðàâ÷óê Корректор Л.Пилипенко