Синтез легкотестируемых схем при константных неисправностях на выходах элементов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Бородина, Юлия Владиславовна

• Бородина, Юлия Владиславовна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Бородина, Юлия Владиславовна

Введение.

Глава I. Схемы, допускающие минимальные полные проверяющие тесты.

§ 1. Схемы, допускающие полные проверяющие тесты единичной длины в случае неисправностей типа "1".

§ 2. Схемы, допускающие минимальные полные проверяющие тесты в случае неисправностей типа "1".

§ 3. Неисправности типа "0".

Глава II. Синтез легкотестируемых схем для систем булевых функций.

§ 1. Реализация систем булевых функций в базисе {&, V,.

§ 2. Реализация систем монотонных функций в базисе {&, V}.

§ 3. Некоторые другие классы булевых функций.

Глава III. Синтез легкотестируемых схем в базисе

Жегалкина в случае единичных неисправностей.

Введение диссертации (часть автореферата) на тему «Синтез легкотестируемых схем при константных неисправностях на выходах элементов»

Диссертация посвящена синтезу легкотестируемых схем из функциональных элементов в различных базисах для булевых функций в случае однотипных константных неисправностей на выходах элементов. В ней найдена минимальная длина проверяющего теста при реализации произвольной булевой функции в базисе {&, V,"}, для этого же базиса предложены конструктивные методы синтеза легкотестируемых схем для систем булевых функций, а также найдены способы реализации произвольных булевых функций схемами в базисе Жегал-кина, допускающими короткие единичные проверяющие тесты. I

Пусть S — некоторая схема из функциональных элементов [4], [29] с одним выходом, реализующая булеву функцию /(ж), х = (rci, ., хп)

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

Для обеспечения надежного функционирования схемы S необходимо решать задачу контроля исправности ее элементов. Для решения этой задачи С.В. Яблонским [25] предложены (в случае контроля исправности элементов общих управляющих систем) логические методы контроля, суть которых состоит в том, что на входы схемы S подаются некоторые специальным образом подобранные "проверяющие" наборы значений переменных xi, х^,., хп и на основе выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии).

Функция, реализуемая на выходе схемы при наличии в схеме неисправных элементов, называется функцией неисправности. Всякое множество Т входных наборов схемы S называется полным проверяющим тестом для этой схемы, если для любой функции неисправности д(х), не равной тождественно /(ж), в Т найдется хотя бы один набор а такой, что /(а) ф д(а) [28],[19]. Число наборов, составляющих тест, называется длиной теста. В качестве тривиального теста всегда можно взять тест, содержащий все 2П наборов значений переменных булевой функции от п переменных.

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

Введем обозначения [28], [19]: D(T) — длина теста Т; D(S) — minD(T), где минимум берется по всем полным проверяющим тестам Т для схемы 5; D(f:B) = min D(S), где минимум берется по всем схемам S в данном базисе В, реализующим функцию /;

D(n,B) = maxD(f, В), где максимум берется по всем булевым функциям / от п переменных. Функция D(n, В) называется функцией Шеннона длины полного проверяющего теста для базиса В.

Кроме проверяющих тестов, рассматриваются еще так называемые диагностические тесты. Множество Т входных наборов схемы S называется полным диагностическим тестом для этой схемы, если Т является полным проверяющим тестом для S и для любых двух различных функций неисправности gi(x) и в Т найдется набор а такой, что g\(cr) ф #2(0") [28],[19]. Для длин полных диагностических тестов также определяется функция Шеннона D(n, В) в заданном базисе В.

В настоящее время задачи логического контроля исправности схем из функциональных элементов часто формулируются так: оценить сверху и снизу (в идеале — найти точные значения) величин D(f, В) и D(n, В) для различных базисов В. Представляют интерес также оценки "промежуточных" величин D(K,B) = max{D(/, В) : f Е К}, где К — некоторый выделенный класс булевых функций от п переменных. Для упрощения решения этих задач существуют следующие пути:

- ограничение типов возможных неисправностей и их количества [1],

И, [П], [12];

- выбор схем определенного типа [9], [10];

- выбор класса К булевых функций;

- синтез легкотестируемых схем [14], [18].

В настоящее время выделяются три основных типа неисправностей: константные, однотипные константные и инверсные. Неисправности каждого из указанных типов могут предполагаться либо на входах, либо на выходах элементов схемы. Константная неисправность типа а (где а равно 0 или 1) на входе (выходе) элемента означает, что на этот вход подается константа а (соответственно, значение на выходе этого элемента всегда равно ск). В общем случае значение а может быть своим у каждого неисправного элемента. В случае однотипных константных неисправностей значение а предполагается одним и тем же у всех неисправных элементов. Инверсная неисправность на входе элемента означает, что подаваемое на этот неисправный вход значение противоположно значению, подаваемому па исправный вход; инверсная неисправность на выходе означает, что значение на выходе неисправного элемента противоположно значению на выходе исправного элемента.

Число неисправных элементов в схеме может предполагаться или любым, или не превосходящим N. В последнем случае обычно полагают N = 1, говоря о единичных неисправностях данного типа и, соответственно, о длине единичного проверяющего теста или длине единичного диагностического теста.

Везде ниже употребляется одно и то же обозначение D(n, В) для функций Шеннона длин тестов при различных неисправностях, но всякий раз поясняется, какие неисправности (константные, константные данного типа, инверсные, на входах или на выходах) и какие тесты (полные или единичные, проверяющие или диагностические) имеются в виду.

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

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

Основоположник математической теории тестов С.В. Яблонский и ряд его учеников и последователей в основном разрабатывали логические методы контроля контактных схем (см. [25], [27], обзорную работу [28]). В дальнейшем существенное внимание стало уделяться схемам из функциональных элементов, однако соответствующая теория для схем из функциональных элементов все еще далека от завершенности.

1т.е. схемами, "каждая из которых реализует отличную от константы функцию и при переходе любого одного элемента в неисправное состояние реализует функцию неисправности, отличную от исходной функции (реализуемой схемой при исправных состояниях всех ее элементов) "[19, с. 111]

Ряд важных результатов в оценивании длин тестов для схем из функциональных элементов при различных типах неисправностей получен в работах S. Reddy, В.Н. Носкова, Н.П. Редькина, С.В. Коваценко, В.Г. Хахулина.

Для единичных константных неисправностей на выходах элементов интересный результат был получен S. Reddy для базиса Жегалкина В1 = {&,©,1}.

Теорема А [30] (1972). При любом натуральном п функция Шеннона D(n,Bi) длины единичного проверяющего теста в случае константных неисправностей на выходах элементов удовлетворяет неравенству n,£i) ^п + 3.

Эта оценка остается верной и в случае, когда единичные константные неисправности допускаются не только на выходах, но и на входах элементов (именно, конструкция схемы Reddy и его тест пригодны и для этого более общего типа неисправностей [19, с. 116]).

В третьей главе настоящей работы оценка Reddy уточнена в случае единичных однотипных константных неисправностей на выходах элементов.

Для произвольного полного конечного базиса В в случае константных неисправностей на выходах элементов Н.П. Редькин [13] (1986), [16] (1989) получил оценку

D{n: В) ^ 2(2^/2] + Я*™ + п) функции Шеннона длины полного проверяющего теста.

В случае же константных неисправностей на входах элементов схем в стандартном базисе В0 = {&, V, "} функция Шеннона длины полного проверяющего теста была асимптотически оценена также Н.П. Редькиным [21] (1997):

П(п,В0) < —= .

V log2 п

Правая часть последней оценки неслучайно намного больше правой части предыдущей оценки. Как показал Н.П. Редькин [17] (1987), для конкретных последовательностей булевых функций при переходе от константных неисправностей на выходах элементов к константным неисправностям на входах элементов может оказаться необходимым существенное увеличение длины проверяющих тестов. Именно, для любого полного конечного базиса существует такая последовательность булевых функций fi(xi), /2(гсь ж2),., /п(жь . ., жп),., что

Янх(/п, В) > nD вых где Z)bx(/> В) и .Овыx(f,B) обозначают минимально возможную длину полного проверяющего теста при реализации функции / схемами в базисе В в случае константных неисправностей соответственно на входах и на выходах элементов.

Из оценок длин тестов для конкретных функций отметим результат В.Г. Хахулина [24] (1995). Пусть В — произвольный базис, в котором можно реализовать все функции счетчика четности = хг ф Ф • • • е хп при п > 1. Тогда для минимально возможных длин полных проверяющих тестов в случае константных неисправностей на входах элементов имеют место неравенства п + 1^£>вх(/®,Б) sen+ 2, п = 2,3,. .

В случае однотипных константных неисправностей верхние оценки функций Шеннона найдены Н.П. Редькиным. Они существенно меньше соответствующих оценок для случая константных неисправностей.

Теорема В [14] (1988). При любом натуральном п функция Шеннона D(n, Bq) длины полного проверяющего теста в случае однотипных константных неисправностей на выходах элементов удовлетворяет неравенству

D(n: В0) ^ п.

В первой главе настоящей работы эта оценка Н.П. Редькина уточнена, и найдено точное значение D{n, В0) = 2, п = 2, 3,.

В случае же однотипных константных неисправностей на входах элементов схем в базисе Bq функция Шеннона длины полного проверяющего теста удовлетворяет следующей асимптотической оценке [15] (1988):

Для длин единичных диагностических тестов также имеются принадлежащие Н.П.Редькину [18] (1989), [20] (1992) оценки функций Шеннона

Bx(n,50)<2M+2 + 2W2[+l; £>вых(п, Во) < 2п + 1, где DBX(n,Bo) и DBblx(n,Bo) обозначают функции Шеннона длины единичного диагностического теста для схем в стандартном базисе Bq в случае однотипных константных неисправностей соответственно на входах и на выходах элементов.

Для инверсных неисправностей на выходах элементов оценки функций Шеннона длин различных тестов получены Н.П. Редькиным и

С.В. Коваценко. Для краткости приведем эти оценки в бесформульном виде.

С.В. Коваценко [3] (2000) доказал, что в случае базиса Жегалкина Bi и инверсных неисправностей на выходах элементов любую булеву функцию, существенно зависящую от п переменных, п ^ 1, можно реализовать а) схемой, допускающей единичный проверяющий тест длины 1; б) схемой, допускающей единичный диагностический тест длины, не превосходящей п + 1; в) схемой, допускающей полный диагностический тест длины, не превосходящей 2п~2.

В случае стандартного базиса Bq и инверсных неисправностей на выходах элементов Н.П. Редькин [22] (1999) доказал, что любую булеву функцию можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест длины 2.

Этот результат, а также результат а) С.В. Коваценко, оказались уточнениями следующего результата Н.П. Редькина [23] (2003): Для любого базиса В при любом натуральном п функция Шеннона D(n, В) длины единичного проверяющего теста в случае инверсных неисправностей на выходах элементов удовлетворяет неравенству

D(n,B) ^ 3.

В серии работ В.Н.Носкова [5 - 10] предложены несколько иные методы логического контроля схем из функциональных элементов (и более общих логических устройств). В частности, в работе [10] для булевых функций f(xi, #2, • • •, хп) от п переменных предложен метод синтеза легкотестируемых схем определенного класса в произвольном полном базисе. Каждая из этих схем имеет блочную структуру (число и вид блоков определяются параметрами данного класса схем), а также п + 3 входа х\. £2,.,жп+з и два выхода. На одном из этих выходов при условии xn+i = хп+2 = xn+z = 0 реализуется функция /, а другой выход предназначен для наблюдения за поведением схемы при ее тестировании. В качестве допустимых неисправностей предполагается весьма широкий класс неисправностей, который, в частности, включает в себя константные неисправности на входах и выходах элементов. Число этих неисправностей ограничено в том смысле, что эти неисправности не нарушают блочную структуру схемы и при этом не более т блоков становятся неисправными. Для таких схем и неисправностей В.Н. Носков получает оценку функции Шеннона длины полного проверяющего теста, которая зависит от п, т и других параметров схемы. Здесь эта оценка не приводится ввиду громоздкости необходимых предварительных определений. Трудно также вывести какие-то следствия из этой оценки, например, для константных неисправностей (сам В.Н. Носков такого рода следствия не приводит).

Структура диссертации. Диссертация состоит из введения, трех глав и списка литературы из 35 наименований. Общий объем диссертации — 74 страницы, в работе содержится 8 рисунков. В каждой главе принята сквозная нумерация теорем, лемм и рисунков.

Список литературы диссертационного исследования кандидат физико-математических наук Бородина, Юлия Владиславовна, 2008 год

1. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств. — М.: Наука, 1987.

2. Карибский В.В., Пархоменко П.П., Согомонян Е.С., Халчев В.Ф. Основы технической диагностики. — М.: Энергия, 1976.

3. Коваценко С.В. Синтез легкотестируемых схем в базисе Жегал-кина для инверсных неисправностей // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2000.- №2. - С.45-47.

4. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. — М.: Издательство Московского университета, 1984.

5. Носков В.Н. Диагностические тесты для входов логических устройств // Дискретный анализ. — Новосибирск: ИМ СО АН СССР, — 1974. Т.26. - С.72-83.

6. Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ.— Новосибирск: ИМ СО АН СССР, 1975. - Т.26. - С.23-51.

7. Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Математические заметки. — 1975. — Т. 18, №1. С.137-150.

8. Носков В.Н. О длинах единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — Сборник трудов Института математики СО АН СССР. — 1978. — Вып. 32. С. 40-51.

9. Носков В.Н. Метод синтеза контролепригодных схем из функциональных элементов // Методы дискретного анализа в изучении булевых функций и графов. — Сборник трудов Института математики СО АН СССР. 1989. - Вып. 48. - С. 52-69.

10. Носков В.Н. Метод синтеза удобных для контроля комбинационных схем // Дискретная математика. — 1993. — Т.5, вып. 4. — С. 3-23.

11. Пархоменко П.П. Диагноз технического состояния дискретных устройств методом выделения подозреваемых неисправностей. Комбинационные устройства. Устойчивые неисправности // Автоматика и телемеханика. — 1971. — №6. — С.26-137.

12. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. — М.: Энергоиздат, 1981.

13. Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1986. — N 1. — С. 72-74.

14. Редькин Н.П. О схемах, допускающих короткие тесты // Вестник Московского университета. Серия 1. Математика. Механика. — 1988. N 2. - С. 17-21.

15. Редькин Н.П. О проверяющих тестах для схем при однотипных константных неисправностях на входах элементов // Известия вузов. Математика. — 1988. — №7. — С. 57-64.

16. Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. Вып.2. — 1989. - С. 198-222.

17. Редькин Н.П. О зависимости длины проверяющих тестов от вида неисправностей // Методы дискретного анализа в теории кодов и схем. — Сборник трудов Института математики СО АН СССР.- 1987. Вып. 46. - С. 65-71

18. Редькин Н.П.О схемах, допускающих короткие единичные диагностические тесты // Дискретная математика. — 1989. — Т.1, вып. 3. С. 71-76.

19. Редькин Н.П. Надежность и диагностика схем. — М.: Издательство Московского университета, 1992.

20. Редькин Н.П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1992. — N 5. — С. 43-46.

21. Редькин Н.П. О проверяющих тестах для схем при константных неисправностях на входах элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1997. — №1.- С. 12-18.

22. Редькин Н.П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов // Математические вопросы кибернетики. 2003.— Вып. 12. — С. 217-230.

23. Хахулин В.Г. О проверяющих тестах для счетчика четности // Дискретная математика. — 1995. — Т.7, вып. 4. — С. 51-59.

24. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Труды МИАН. — 1958. — Т.51,— С.270-360.

25. Яблонский С.В., Чегис И.А. О тестах для электрических схем // УМН 1955. - Т. 10, вып. 4(66). - С.182-184.

26. Яблонский С.В. Надежность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и ее приложениям. М.: МГУ. — 1986. — С.7-12.

27. Яблонский С.В. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. — 1988. № 1. - С.5-25.

28. Яблонский С.В. Введение в дискретную математику. — М.: Высшая школа. — 2002.

29. Reddy S.M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. - v.21. - N1. - P. 124-141.

30. Бородина Ю.В. Синтез легкотестируемых схем в базисе {&, V, "} при однотипных константных неисправностях на выходах элементов // Дискретная математика. — 2005. — Т.17, вып. 1. — С. 129-140.

31. Бородина Ю.В. Синтез легкотестируемых схем в базисе {&, V, "} для систем функций из некоторых классов // Вестник Московского университета. Серия 1. Математика. Механика. — 2007. — Ш. — С. 68-72.

32. Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008.— №1. — С.40-44.