автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы синтеза самопроверяемых дискретных систем

На правах рукописи

Никитин Константин Владимирович

МЕТОДЫ СИНТЕЗА САМОПРОВЕРЯЕМЫХ ДИСКРЕТНЫХ

СИСТЕМ

05.13.01 - системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Томск-2003

Работа выполнена в Томском государственном университете на кафедре программирования

Научный руководитель - доктор технических наук, профессор

Матросова А.Ю.

Официальные оппоненты: доктор технических наук, профессор

Евтушенко Нина Владимировна, кандидат технических наук, профессор Щербанов Виктор Анатольевич

Ведущая организация Томский политехнический университет

Защита состоится ЗР октября 2003 г. В Ю30 часов в ауд. 2126 II уч. корпус ТГУ на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан « » сентября 2003 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Смагин В.И.

2доЗ-А_

\SSSb

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы.

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

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

Разработка методов проектирования самопроверяемых дискретных систем, ориентированных на использование новой элементной базы является, безусловно, актуальной.

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

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирование неупорядоченными кодами (в частности, равновесными) символов выходного алфавита и состояний автомата и наблюдения выходов синхронного самопроверяемого устройства и его линий обратных связей.

2. Разработан метод синтеза самотестируемых комбинационных детекторов равновесных кодов.

Поставленные задачи решаются в предположении, что каждый ПЛБ реализует либо одну (любую) булеву функцию от £+1 переменной, либо две (любые) булевы функции от к переменных.

Методы исследования.

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

Научную новизну полученных в работе результатов определяют:

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

Декомпозиционный метод проектирования самотестируемых комбинационных детекторов равновесных кодов в базисе ПЛБ. Детектор кодов является самотестируемым относительно кратных константных неисправностей на полюсах ПЛБ. Проблема синтеза самотестируемых детекторов в базисе ПЛБ исследуется впервые. Алгоритмы сокращения числа допустимых кодовых слов на входах самотестируемых детекторов.

Формула оценки сложности детектора кодов, то есть числа ПЛБ, необходимых для реализации детектора.

Достоверность полученных результатов.

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

Практическая значимость работы.

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

Разработанные методы синтеза самопроверяемых устройств ориентированы на реализацию в базисе программируемых элементов, в частности ПЛБ ХШпх 3000. Проектирование может также быть выполнено в базисе ПЛБ любых производителей, удовлетворяющих описанным ранее требованиям, предъявляемым к ПЛБ.

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

Реализация полученных результатов.

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

1. Госбюджетная тема Сибирского физико-технического института при ТГУ, программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95-1-21 и №591-7 "Информационные компьютерные технологии дискретного

математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

3. Научный проект Минобразования России «Решение логических уравнений на BDD-графах в задачах диагностики».

Результаты работы также используются в курсе лекций "Диагностика дискретных устройств" на факультете прикладной математики и кибернетики Томского государственного университета (ТГУ).

Апробация работы и публикации.

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

Результаты работы представлялись на следующих научных конференциях:

1. Третья всероссийская конференция с международным участием «Новые информационные технологии в исследовании дискретных структур» (Россия, Томск 2000);

2. The Fourth International Conference on Computer-added Design of Discrete Devices (CAD DD'2001) (Minsk, Republic of Belarus, November 14-16,2001);

3. Международная конференция «Компьютерные науки и информационные технологии» (Россия, Саратов 14-18 мая 2002г.).

4. 7th ШЕЕ International On-Line Testing Workshop (Taormina, Italy, July 9-11,2001);

5. 9th IEEE International On-Line Testing Workshop, Greece, Kos, July 7-9,2003.

По результатам выполненных исследований опубликовано 7 печатных

работ.

Структура и объем диссертации.

Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 33 рисунка и 14 таблиц. Объем диссертации составляет 115 стр., в том числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 104 стр., библиография из 90 наименования - 8 стр.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обоснование актуальности работы, изложены ее цель, научная новизна и практическая ценность.

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

Определение I. Функция f(xl,x2,.~,xn), xi е Е2 -{0,1}, г = 1,«,

причем, f(ai,a2,...,a„)eE2, где а( е Е2, г = 1,и называется булевой функцией.

Определение 2. Автомат - это пятерка (X,Q,Y,v/,q>), где X.Q.Y -конечные алфавиты, называемые входным алфавитом, множеством состояний и выходным алфавитом, ц/ - функция переходов, отображающая множество XxQ в Q, ф - функция выходов, отображающая множество XxQ в Y.

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

В последние годы большое развитие получила FPGA (Field of Programmable Gâte Array) технология. Основу FPGA технологии составляют программируемые логические блоки - CLB (Configurable Logic Block). CLB -это конфигурация логических элементов, которые могут быть программируемы пользователем. Существуют реализации CLB (в частности Xilinx 3000), где каждый CLB может выполнять одну или две (любые) булевы функции от заданного числа переменных. Если CLB реализует две функции, то эти функции могут зависеть от одних и тех же переменных.

Поскольку исследования диссертационной работы не ориентированы на конкретную реализацию FPGA технологии, в работе введено понятие программируемого логического блока (ПЛБ). Каждый ПЛБ имеет k +1 вход и один выход или к входов и два выхода. Если ПЛБ имеет один выход, то на этом выходе может быть реализована одна (любая) булева функция, зависящая от ¿+1 переменных. В случае если ПЛБ имеет два выхода, то он может выполнять любые две булевы функции, каждая из которых зависит от одних и тех же к входных переменных.

Существуют два основных подхода к проверке исправности работы схемы:

- метод тестового диагностирования;

- метод функционального диагностирования.

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

Метод функционального диагностирования не предусматривает перевода схемы в специальный режим, исправность схемы относительно некоторого рассматриваемого множества неисправностей определяется в процессе нормального функционирования схемы. При реализации данного метода выходные наборы схемы представляют собой кодовые слова некоторого кода (например, равновесного кода, кода Бергера и т.д.). Специальное кодирование выходных наборов приводит к увеличению количества выходов схемы. К выходам схемы должно постоянно быть подключено проверяющее устройство - детектор кодов. Если некоторый выходной набор схемы не является кодовым словом, то детектор кодов сигнализирует об этом. В этом случае оборудование, обеспечивающее тестовое диагностирование, размещается непосредственно на том же чипе, где размещена основная схема (тестируемая схема). В рассматриваемом подходе дополнительным оборудованием являются дополнительные выходы схемы, вместе с реализуемыми ими функциями, и детектор кодов.

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

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

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

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

У\ Д'т

Рис. 1. Самопроверяемая синхронная последовательностная схема

Рассмотрим схему, представленную на рис. 1. В ней комбинационная часть синхронного автомата реализует следующие функции: функции выходов автомата {У\,--,Ут), функции дополнительных выходов (ут+\.---,ух), обеспечивающие специальное кодирование выходов схемы, и

функции переходов для представления следующего состояния (г,.....гр).

Выходы у\,—,у$ формируют кодовые слова равновесного или любого неупорядоченного кода.

На рис 1. К является комбинационной частью, с1х,...,с1р - задержки,

реализуемые ¿-триггерами.

Комбинационная схема К реализует систему из (я + р) булевых функций, зависящих от (п + р) булевых переменных. В случае возникновения неисправности комбинационная схема К реализует систему булевых функций Р™.

Пусть ava2 - входные наборы, представленные булевыми векторами

длины (п + р). Если для любых компонент ai;, a2¡, i = (l,(n + р)), аи < а2(-, то оц < а2. Например, если а, =010010, а2=110110,то а,<а2.

F( а) есть булев вектор длины (s + p), F(a)-$. Он представляет значение системы F функций на входном наборе а: /=Гсц; = Р1, F(а2; = р2.

Пусть а,,а2 - различные последовательности булевых векторов. Последовательности й,,а2 сравнимы, если для любой пары a¡, а'2, i е {1,2,...} их элементов имеем: а{<а2 или а2<а',. Обозначим их как а, ^ а2. Например, последовательности й, = 010010,011010,111011 и а2 = 010010,001010,111111 сравнимы.

Пусть неисправность w проявляет себя как однонаправленная неисправность. Однонаправленная неисправность вызывает замену в выходном векторе (3 либо только нулей на единицы либо только единиц на нули, но не те и другие одновременно. Если набор а является тестом для некоторой однонаправленной неисправности w схемы К, то имеем: либо F(a)<Fw(a), либо Fw(a)<F(a). Если входной набор а не является тестом, то F(a) = Fw(а).

Пусть p,pw равны F(a),Fw(а), соответственно, и р = F(a), Р w = Fw(a).

Теорема 1. Если w является однонаправленной неисправностью, то для любой последовательности a F(а) > Fw(а) то есть р > pw.

Пусть F есть система из т булевых функций, зависящих от п булевых переменных хи...,хп, {xl,...,xn} = X .

Определение 3. Система F функций является монотонной, если для любой пары булевых векторов ах,а2, таких что а, <а2, имеет место условие: F(ax) < F(a2), то есть (3, < Р2, где р, =F(al), р2 = F(а2) .

Рассмотрим подмножество X* булевых переменных, X* = {xñ,...,x¡r}, X* с X. Пусть а,, а2 булевы векторы п переменных.

Определение 4. Если для любого /, соответствующего переменной Х1

из множества X*, аи < а2г, и для любого ), соответствующего переменной

х*

х], X/ е {X \ X*}, а1у = а2у , то а, < сс2.

Определение 5. Система Г функций является частично монотонной по переменным множества X*, если для любой пары булевых векторов ар а2, х*

таких что а, < а2, имеет место условие: Р(а.1) < Р(а2), (Р, <Р2,

Определение 6. Неисправность называется однонаправленной, если ее проявление на наблюдаемых выходах приводит к замене значений некоторых переменных только с «О» на «1» или с «1» на «О», но не в обоих направлениях одновременно.

Определение 7. ЕЮО-графом булевой функции называется ориентированный граф с корнем, имеющий множество вершин V. V содержит два типа вершин: нетерминальные и терминальные. Нетерминальная вершина V, ve V, имеет в качестве атрибутов индекс аргумента тйех(у) е {\,...,п] и две дочерние вершины high(v)Jow(v) е V. Терминальная вершина V имеет один атрибут - \а1ие{у) 6 {0,1}.

Функция /„, соответствующая вершине V ВОБ - графа, определяется рекурсивно следующим образом:

1. Если V является терминальной вершиной, и

a. \а1ж( V,) = 1, то /„ = 1,

b. уа1ие(у) = 0, то /у = 0.

2. Если V - нетерминальная вершина с индексом тйех(V) -1, то /„ является функцией следующего вида:

/у > • • • >хп ) = Х1 ' //оЦу) (■х\'• • *М > >••'>*„) V

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

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

Табл. 1, аналогичным микропрограммному. Здесь символы входного и выходного алфавита уже закодированы. После кодирования состояний получаем интервальное описание (Табл. 2). Для обеспечения самопроверяемости состояния будем кодировать кодовыми словами какого либо неупорядоченного кода, например равновесного.

Имея интервальное описание системы булевых функций переходов-выходов автомата, можно получить представление комбинационной схемы автомата в виде системы ЕШО-графов, а затем покрыть полученную систему программируемыми логическими блоками, с тем, чтобы получить комбинационную схему К в базисе ПЛБ.

Таблица 1. Таблица 2.

х1х2 2 а У\У2УгУ№

0 - - 1 1 0 0 0 1 0

- 0 - 1 1 0 0 0 1 0

1 1 - 1 2 1 0 0 1 0

- - 0 2 2 0 0 1 1 0

- - 1 2 3 1 0 1 1 0

1 0 - 3 3 0 1 ООО

0 - - 3 4 1 1 ООО

- 1 - 3 4 1 1 ООО

- - 0 4 4 0 1 0 0 1

- - 1 4 1 1 1 0 0 1

212223г4 У\УгУзУ*У5

0 - -- 0 -1 1 - 10 0 0 10 0 0 10 0 0 10 0 0 10 0 0 0 10 0 0 0 0 1 0 0 0 0 1 0 10 0 10

- - 0 - - 1 0 10 0 0 10 0 0 10 0 0 0 10 0 0 110 10 110

1 0 -0 - -- 1 - 0 0 10 0 0 10 0 0 10 0 0 10 0 0 0 1 0 0 0 1 0 10 0 0 110 0 0 110 0 0

- - 0 - - 1 0 0 0 1 0 0 0 1 0 0 0 1 10 0 0 0 10 0 1 110 0 1

Предложен алгоритм покрытия системы ЕШО-графов программируемыми логическими элементами (ПЛБ).

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

2. Выбираем любую вершину и, мощность множества Ви которой равна к. Если такой вершины нет, то ищем вершину, для которой мощность множества Ви равна (к-\) и т.д., пока не определим вершину и.

3. Сопоставляем вершине и ПЛБ, который реализует функцию, представленную графом с корнем в вершине и. Сама вершина и сопоставляется новой переменной - м>,.

4. Выполняем п.1 данного алгоритма для новой системы БОБ-графов и т.д., пока не покроем систему ВБО-графов целиком.

Введем следующий класс неисправностей \¥\ одиночные константные неисправности на входных полюсах синхронной последовательностной схемы, одиночные константные неисправности на ее выходных полюсах и полюсах (¿-тригг еров и одиночные функциональные неисправности функций, реализуемых ПЛБ. На выходе ПЛБ в случае возникновения такой неисправности может быть реализована любая другая функция того же множества переменных. В синхронной последовательностной схеме возможна единственная неисправность из IV.

Рассмотрим функциональную неисправность м>. Соответствующий ПЛБ реализует вместо ф функцию ф*, зависящую от входных переменных

ПЛБ. Пусть а - произвольная входная последовательность схемы К и -неисправная система, которую реализует схема в присутствии рассматриваемой неисправности.

Теорема 2. Р(а)$ Ры(а).

Следствие. Любая одиночная функциональная неисправность проявляется как однонаправленная неисправность.

Рассмотрим одиночную неисправность м>(!, на полюсе й-

триггера. Любая такая неисправность проявляется как одиночная

неисправность на входе К, соответствующей линии обратных связей синхронного последовательностного устройства.

Теорема 3. Р*'1 (а)$ Р(а) .

Следствие. Любая неисправность и^ проявляется как однонаправленная неисправность.

Рассмотрим одиночную константную неисправность , н>- б IV , одной из входных переменных синхронной последовательностной схемы.

Теорема 4. FW| (а) $ Р(а) .

Следствие 1. Любая неисправность проявляется как

однонаправленная неисправность.

Следствие 2. Любое покрытие программируемыми логическими блоками (ПЛБ) ВОО-графов сохраняет свойства однонаправленного проявления неисправностей множества ¡V.

Так как любая одиночная константная неисправность на выходе К очевидно является однонаправленной, то в соответствии со следствиями теорем 2,3, 4, любая неисправность \velV является однонаправленной.

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

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

В третьей главе предлагается метод проектирования самотестируемого детектора (/и,и)-кодов, ориентированный на использование программируемых логических блоков (ПЛБ).

Рассматривается множество неисправностей детектора V, которое включает в себя все кратные константные неисправности на входах и выходах ПЛБ. Только один ПЛБ в детекторе может быть неисправен.

К детектору предъявляются следующие требования.

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

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

Самотестируемый детектор имеет два выхода (рис. 2). Комбинации значений сигналов:

a) (01) или (10) означают, что выходной набор самопроверяемой схемы является кодовым словом и детектор кодов исправен;

b) (00) или (11) означают, что либо выходной набор самопроверяемой схемы не является кодовым словом, либо детектор неисправен.

-► ДК

-►

Рис.2. Детектор кодов

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

неисправность монотонно проявляет себя на выходах детектора, т.е. либо Р(а)< Ру(а), либо Р^а)<Р(а).

Заметим, что число всевозможных кодовых слов (т,п)- кода равно С™, то есть числу сочетаний из и по т. Кодовые слова могут быть представлены дизъюнкцией конъюнкций ранга п. Обозначим эту дизъюнкцию О^(Х), где X ={х1,...,х„} - множество переменных. Уже при

п = 10, т = 5 /)]5(/X) состоит из 252 конъюнкций ранга 10 и содержит 2520 букв. Это выражение не может быть сокращено в результате минимизации ДНФ, ДНФ X) является совершенной и сокращенной одновременно, поскольку любые две конъюнкции из О^(Х) ортогональны по крайней мере по двум переменным.

Для представления всевозможных (/я,и)-кодов предложена специальная формула разложения А. Формула включает скобки, символы л, V и ДНФ Очр(Хг). Функция разложения йяр(Хг) - это дизъюнкция

конъюнкций, соответствующих всем (д, р) -кодам, р<к , д < р, Хг с X, X = {х],...,хп}. В частности, к может быть равно числу входов двухвыходного ПЛБ. Каждый ПЛБ либо реализует одну произвольную булеву функцию от ¿ + 1 переменных, либо две произвольные булевы функции от к переменных, и - функция, сопоставляемая одному из выходов ПЛБ.

Разделим множество X на два подмножества Х], X*, где

ХХ=(х\.....~{хк+\>->хп}-

Теорема 5.

о:(Х)=и0к(х1 )в:_к(х')ч о\(х' дау**; V

V В\(ХХ )о::к2(х*) ч^и^х1 )в::кк(х*)

Здесь И"(Х) - дизъюнкция конъюнкций, представляющих всевозможные кодовые слова (т,п)- кода. Назовем й1к(Хх), о1_к(Х*) функциями разложения. Если п-к>к, то выполним следующий шаг данного разложения для каждой й1_к(Х*), и так далее. В результате получим формулу А, в которой для любой йчр(Хг) выполняется условие р < к, где к равно числу входов ПЛБ. Данное разложение обозначается формулой А.

Теорема 6. Число / различных конъюнкций любого выражения (1) не более к +1.

Представим выражение (1) деревом разложения (рис. 3). Корень дерева пометим символом V, а / смежных с ним вершин - символом д. Его листьям соответствуют функциям разложения. Корню дерева и его / неконцевым вершинам сопоставляются булевы функции, являющиеся композицией функций разложения. Каждая из этих функций зависит от одного и того же подмножества переменных формулы А.

Рис. 3. Дерево разложения

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

Теорема 7. Любое кодовое слово некоторого (т,л)-кода 1) обращает в единицу V функций разложения, каждая из которых зависит не более чем от

V

о°к о:_к в\ о: в°п_к

к переменных, 2) активизирует у-\ деревьев разложения и ровно одну вершину, отмеченную символом "л", в каждом активизированном дереве разложения, причем, 3) корни активизированных вершин соединены между собой и корнем дерева А единственной простой цепью.

Следствие. Любое кодовое слово (яг,л)-кода активизирует в любом дереве разложения формулы А не более одной вершины, отмеченной символом " л ".

Теорема 8. Для любого дерева разложения и любой его вершины, отмеченной символом д, существует набор, являющийся кодовым словом (/и, и)-кода, активизирующий эту вершину.

Все кодовые слова (ш,и)-кода разделяются на два подмножества, и V формула А представляется следующим образом: А = А1 V А2. Так как каждая

конъюнкция ДНФ представляющей все кодовые слова (т,п)-кода,

ортогональна любой другой конъюнкции этой ДНФ, то можно представлять формулу А следующим образом: А = А1ФА2 .Здесь А1 реализует кодовые слова первого подмножества, А2 - оставшиеся кодовые слова (/л,и)-кода. А1 и А2 соответствуют двум выходам детектора. , Построим двухвыходную схему С (детектор (т, п) - кода), которая

реализует на своих выходах формулы А1 и Аг . Значения 10, 01 достигаются на выходах С, если на ее входы поступают кодовые слова (/я,и)-кода, значения 00, 11 - если на входы поступают некодовые слова.

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

Пусть переменные У\>Уг>—>Уг1-\-Уг1 сопоставлены различным | функциям разложения в выражении (1). Тогда его правая часть

к I представляется в виде:

(2) УхУг V У3У4 V • •• V УгыУц •

Согласно следствию теоремы 7 любое кодовое слово обращает в единицу не более одной конъюнкции выражения (2). Это позволяет заменить выражение (2) дизъюнкцией конъюнкций, представляющих (2,2/) -коды.

Например, выражение у[у1 V у3у4 vy5y6 можно представить в виде: У\УгУъУ*УьУь V Л^Д'зЛЛЗ'б V УМУзУлУьУб ■

Реализуем выражение (2) одновыходными ПЛБ с £ + 1 входами. Пусть к нечетно. Выполним следующие шаги.

¿ + 1

1. Выделим первые —конъюнкций выражения (2) с последующим

изменением их на дизъюнкцию конъюнкций, представляющих соответствующие (2,к + 1) -коды. Блок ПЛБ[ реализует эту дизъюнкцию

¿ + 1

конъюнкций. Если число конъюнкций выражения (2) меньше или равно ——,

тогда это выражение реализуется единственным одновыходным ПЛБ1. В противном случае выполняем шаг 2.

2. Возможны следующие ситуации.

А + 1

Рис. 4. Подсхема £> для / = к +1, с>1.

a) Число оставшихся конъюнкций выражения (2) равно

£

(согласно теореме 6 это число конъюнкций является максимальным). Используем одновыходной ПЛБ2 для реализации этих конъюнкций в виде суммы конъюнкций, представляющих соответствующие (2, к +1) -коды.

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

b) Число оставшихся конъюнкций выражения (2) меньше или равно

к-1

-. Соответствующая подсхема С представлена на рис. 5.

ПЛБ2

1 1'

ПЛБ,

1 - I

У\ Уш У 21

Рис. 5. Подсхема О для I <, к, у> 1

Теорема 9. Схема является самотестируемой для множества V неисправностей.

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

Таблица 3

Я? д? А2 Д63 * Ао Л6 и\2

ПЛБ в предложенном методе 2 6 6 8 6 9 18 25

Другие методы при условии покрытия ПЛБ 7 10 5 14 24 36

В четвертой главе предлагаются оценки сложности детекторов, описанных в главе 3. Выведены формулы для подсчета числа ПЛБ, необходимых для реализации самотестируемого детектора при следующих предположениях относительно параметров детектора: а) рассматривается детектор (2и,и)-кодов;

b) число входов ПЛБ равно к, vin делится на к, .

Полученные формулы (3) позволяют подсчитать число ПЛБ при различных значениях к, и п для четного или нечетного числа входов ПЛБ.

п

(3)

N =3'

' * иеч

п-к + 2 п п + 2к + 2 2 ~к + 2

п-к + 2 п п + 2к + 2 2 ~к + 2

--1

(к + 2)

\к

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

Обычно свойства самотестируемости детектора доказываются в предположении, что все кодовые слова некоторого равновесного кода достигаются на его входах. Множество этих кодовых слов будем называть допустимым на входах детектора. На практике это не всегда возможно: число кодовых слов на выходах самопроверяемой схемы меньше числа всевозможных кодовых слов равновесного кода. В этом случае желательно обеспечение свойства самотестируемости на подмножестве кодовых слов, близком к подмножеству кодовых слов, достижимых на выходах самопроверяемой схемы.

Один из способов решения этой проблемы - построение детекторов неупорядоченных кодов на основе детекторов различных (т,п) -кодов.

Доказано, что при использовании неупорядоченного кода специального вида (4) детектор кода остается самотестируемым при сокращении числа допустимых кодовых слов по сравнению с подходящим детектором (т,п) -кодов. При этом число ПЛБ, необходимых для реализации детектора неупорядоченных кодов, не увеличивается. (4) .^-хчО^-х, щ-щ>\

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

1. Удаляем только поддеревья, корни которых отмеченные символом л.

2. Поддерево удаляем только в том случае, если у следующей вершины, отмеченной V (при движении по дереву к корню),

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

Самотестируемость детектора в классе рассматриваемых неисправностей сохраняется.

Основные положения, выдвигаемые на защиту.

1. Обоснование возможности применения метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства к синтезу комбинационной составляющей самопроверяемого синхронного последовательностного устройства. Речь идет о методе покрытия программируемыми логическими блоками (ПЛБ) системы BDD-графов, представляющей функции переходов-выходов автомата. Состояния и символы выходного алфавита синхронного автомата кодируются при синтезе самопроверяемого устройства неупорядоченными кодами. Наблюдаются выходы и линии обратных связей устройства. Допускаются функциональные неисправности ПЛБ и одиночные константные неисправности на полюсах триггеров и входных полюсах.

2. Метод проектирования самотестируемых комбинационных детекторов равновесных кодов, ориентированный на использование ПЛБ. Допускаются кратные неисправности на полюсах одного ПЛБ. Проблема синтеза детекторов такого типа рассмотрена впервые.

3. Формула подсчета числа ПЛБ, необходимых для реализации детектора равновесных кодов.

4. Алгоритмы сокращения числа допустимых кодовых слов, поступающих на вход детектора, при сохранении свойств самотестируемости детектора.

Основные результаты диссертации опубликованы в работах:

1. Матросова А.Ю., Никитин К.В. Проектирование самотестируемого детектора неупорядоченных кодов // Докл. Международной конференции Компьютерные науки и информационные технологии. Саратов, 2002. - С. 44-45.

2. A. Matrosova, О. Goloubeva, К. Nikitin, S. Ostanin. Self-Checking FSM Design Based on BDD Synthesis methods and FPGA Implementation // The Fourth International Conference on Computer-added Design of Discrete Devices, Minsk, Republic of Belarus, November 14-16, 2001 - P. 23-31.

3. К.В. Никитин. Об оценке сложности комбинационного детектора равновесных кодов И Третья всероссийская конференция с международным

участием Новые информационные технологии в исследовании дискретных структур, Томск, 2000 - С. 252-256.

4. Матросова А.Ю., Никитин К.В. Синтез самопроверяемого детектора равновесных кодов // Вестник Томского государственного университета № 271 -2000.-С. 101-105.

5. A. Matrosova, К. Nikitin, О. Goloubeva. Totally self-checking FSM design based on multilevel synthesis methods and FPGA implementation // 7th IEEE International On-Line Testing Workshop, Taormina, Italy - July 9-11, 2001 -P. 144.

6. А.Ю. Матросова, К.В.Никитин. Синтез самотесшруемого детектора (m,n) - кодов на программируемых логических блоках // Вестник Томского государственного университета. Приложение. №6.2003. - С. 124-136.

7. A. Matrosova, V. Ostrovsky, I. Levin, К. Nikitin. Designing FPGA based Self-Testing Checkers for m-out-of-n Codes // 9th IEEE International On-Line Testing Workshop, Greece, Kos. - July 7-9,2003 - P. 49-53.

отпечатано на ризографе. Тираж 100 экз. Заказ №1541 Центр оперативной полиграфии ООО "Графика" Лицензия ПД №12-0061 от 27.02.01 г. Томск, ул. Беленца, 17 тел.: 51-09-59

» 15 5 56

ВВЕДЕНИЕ.

1. ОСНОВНЫЕ ПОНЯТИЯ.

1.1. Булевы функции, конечные автоматы, логические схемы.

1.2. Программируемые логические элементы.

1.3. Методы тестового и функционального диагностирования.

1.4. Обзор методов проектирования дискретных систем.

1.4.1. Методы проектирования самопроверяемых схем.

1.4.2. Обзор методов проектирования детекторов кодов.

1.5. Выводы по главе.

2. ПРОЕКТИРОВАНИЕ САМОПРОРВЕРЯЕМЫХ СХЕМ.

2.1. Однонаправленные неисправности самопроверяемой синхронной последовательностной схемы.

2.2. Получение интервального описания.

2.3. Монотонные и частично-монотонные системы.

2.4. ПЛБ реализация синхронной последовательностной схемы, представленной системой BDD - графов.

2.5. Однонаправленное проявление неисправностей класса W в комбинационной схеме.

2.6 Результаты экспериментов.

2.7. Выводы по главе.

3. ПРОЕКТИРОВАНИЕ САМОТЕСТИРУЕМОГО ДЕТЕКТОРА (M,N)-КОДОВ.

3.1. Метод разложения множества кодовых слов (т,п) - кода.

3.2. Реализация самотестируемого детектора кодовых слов (т,п) - кода для т> 1.

3.3. Обоснование самотестируемости схемы С.

3.4. Реализация (1,п)-детекторов.

3.5. Результаты сравнения с другими известными реализациями детекторов т,п) -кодов.

3.6. Выводы по главе.

4. ОЦЕНКА СЛОЖНОСТИ ДЕТЕКТОРА.

4.1. Подсчет числа ПЛБ.

4.2. Неупорядоченные коды.

4.2.1. Построение детекторов неупорядоченных кодов.

4.2.2. Обсуждение свойства самотестируемости детектора.

4.3. Сокращение дерева формулы А.

4.4. Выводы по главе.

Актуальность проблемы.

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

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

Разработка методов проектирования самопроверяемых дискретных систем, ориентированных на использование новой элементной базы является, безусловно, актуальной.

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

1. Выполнено исследование известного метода логического синтеза комбинационной составляющей несамопроверяемого синхронного последовательностного устройства на возможность его применения к синтезу комбинационной составляющей самопроверяемого синхронного последовательностного устройства. Метод основан на покрытии системы BDD-графов, представляющей функции переходов-выходов синтезируемого синхронного автомата, программируемыми логическими блоками (ПЛБ). Его применение при синтезе самопроверяемых устройств требует кодирование неупорядоченными кодами (в частности, равновесными) символов выходного алфавита и состояний автомата и наблюдения выходов синхронного самопроверяемого устройства и его линий обратных связей.

2. Разработан метод синтеза самотестируемых комбинационных детекторов равновесных кодов.

Поставленные задачи решаются в предположении, что каждый ПЛБ реализует либо одну (любую) булеву функцию от к+\ переменной, либо две (любые) булевы функции от к переменных.

Методы исследования. В работе используется методы дискретной математики, в частности, алгебры логики, теории автоматов и теории графов.

Научную новизну полученных в работе результатов определяют:

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

- Декомпозиционный метод проектирования самотестируемых комбинационных детекторов равновесных кодов в базисе ПЛБ. Детектор кодов является самотестируемым относительно кратных константных неисправностей на полюсах ПЛБ. Проблема синтеза самотестируемых детекторов в базисе ПЛБ исследуется впервые.

- Алгоритмы сокращения числа допустимых кодовых слов на входах самотестируемых детекторов.

- Формула оценки сложности детектора кодов, то есть числа ПЛБ, необходимых для реализации детектора.

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

Практическая значимость работы.

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

Разработанные методы синтеза самопроверяемых устройств ориентированы на реализацию в базисе программируемых элементов, в частности ПЛБ Xilinx 3000. Проектирование может также быть выполнено в базисе ПЛБ любых производителей, удовлетворяющих описанным ниже требованиям, предъявляемым к ПЛБ.

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

Реализация полученных результатов.

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

1. Госбюджетная тема Сибирского физико-технического института при ТГУ, программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95 1 21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

3. Научный проект Минобразования России «Решение логических уравнений на BDD-графах в задачах диагностики».

Результаты работы также используются в курсе лекций "Диагностика дискретных устройств" на факультете прикладной математики и кибернетики Томского государственного университета (ТГУ).

Апробация работы и публикации.

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

Результаты работы представлялись на следующих научных конференциях:

1. Третья всероссийская конференция с международным участием «Новые информационные технологии в исследовании дискретных структур» (Россия, Томск 2000);

2. The Fourth International Conference on Computer-added Design of Discrete Devices (CAD DD'2001) (Minsk, Republic of Belarus, November 14-16,2001);

3. Международная конференция «Компьютерные науки и информационные технологии» (Россия, Саратов 14-18 мая 2002г.). iL

4. 7 IEEE International On-Line Testing Workshop (Taormina, Italy,

July 9-11,2001); th

5. 9 IEEE International On-Line Testing Workshop, Greece, Kos, July 79, 2003.

По результатам выполненных исследований опубликовано 7 печатных работ.

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 33 рисунка и 14 таблиц. Объем диссертации составляет 115 стр., в том числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 104 стр., библиография из 90 наименования - 8 стр.

4.4. Выводы по главе

1. Получены формулы для подсчета числа ПЛБ для некоторых частных случаев детекторов. Формулы позволяют оценить сложность самотестируемых детекторов для произвольных (т,п)-кодов.

2. Установлено, что сложность детекторов, реализуемых предложенным в работе декомпозиционным методом, растет пропорционально квадрату длины п (т,и)-кода.

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

ЗАКЛЮЧЕНИЕ

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

Известные методы проектирования таких систем ориентированы прежде всего на вентильную реализацию, хотя и могут быть перенесены на ПЛБ. Эти методы не учитывают специфику программируемых элементов, а именно возможность одним блоком реализовать одну или две любые булевы функции от фиксированного числа переменных. Использование таких свойств позволило бы сократить как сложность схем (число элементов, необходимых для реализации), так и алгоритмы проектирования.

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

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

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

Несмотря на то, что полученный детектор является универсальным, то есть не ориентированным на какой-либо конкретный равновесный код, его реализация в рамках FPGA-технологии довольно компактна.

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

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

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

1. В.В. Соловьев. Проектирование функциональных узлов цифровых схем на программируемых логических устройствах // ПК ООО «Бестпринт». Минск-1996.

2. Д. Бадашин, А. Савчук. Сверхбольшие специализированные ИС в оборудовании цифровых систем передачи // Технология и конструирование в электронной аппаратуре.

3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. — 272 с.

4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Элементы теории автоматов // Учебное пособие. — М.: Изд-во Минск. Ун-та, 1978. 216 с.

5. Г.П. Агибапов, A.M. Оранов. Лекции по теории конечных автоматов // Изд-во Томского Ун-та. Томск, 1984. -185 с.

6. ACT™ Family FPGA Data Book // Actel Corporation. Sunny vale, California.-1992.

7. FPGA Data Book and Design Guide // Ibid. 1993.

8. XILIX. The Programmable Logic Data Book // San Jose, California. 1996.

9. Component Selector Guide. Altera Corporation. San Jose, California. -1995.

10. Согомонян E. С., Слабаков E. В. Самопроверяемые схемы и системы защищенные от неисправностей // М.: Радио и связь, 1989. -158 с.

11. McCluskey Е. J. Verification Testing-A Pseudo-Exhausted Test Technique // IEEE Tran. on Computers. Vol.C-33, - №6.-1984.-P. 541-546.

12. Tang D. Т., Chen C. L. Iterative Exhaustive Pattern Generation for Logic Testing // IBM J. Res. Develop. Vol. 28, - №2. -1984. - P. 212-219.

13. Min Y., Li Z. Pseudo-Exhausted Testing Strategy for Large Combinational Circuits // Computer Systems Science and Engineering. Vol. 1, - №4. -1986.-P. 213-220.

14. Furuya K. A Probabilistic Approach to Locally Exhaustive Testing // Tran. of the IEICE. Vol. E-72. - 1989. - P. 656-660.

15. Hellebrand S. Sythese vollstanding testbarer Schaltungen // VDI Verlag. Reihe 10,-№177.-1991.

16. Rajski J., Tyszer J. Recursive Pseudo-Exhaustive Test Pattern Generator // IEEE Tran. on Computers. Vol. 42, -№12. - 1993. - P. 1517-1521

17. Wunderlich H. J. Self Test Using Uniquiprobable Random Patterns // Proc. IEEE Int. Symposium on Fault Tolerant Computing. 1987. - P. 258-263.

18. Wunderlich H. J. Multiple Distributions for Biased Random Test Patterns // Proc. IEEE Int. Test Conference. -1988. P. 236-244.

19. Hartmann J. The Random Testability of the n-Input AND Gate // Proc. 8th Annual Symposium on Theoretical Aspects of Computer Science. 1991. - P. 488-498.

20. Hartmann J. On Numerical Weight Optimization for Random Testing // Proc. EDAC-EUROASIC. 1993. - P. 223-230.

21. Pateras S., Rajski J. Generation of Correlated Random Patterns for the Complete Testing of Synthesized Multi-Level Circuits // Proc. 28th Design Automation Conference. 1991. - P. 347-352.

22. Pateras S., Rajski J. Cube-Contained Random Patterns and their Application to the Complete Testing of Synthesized Multi-Level Circuits // Proc. IEEE Int. Test Conference. 1991. - P. 473-482.

23. McCluskey E. J. Built-in Self-Test Structures // IEEE Design & Test of Computers.-April 1985.-P. 29-36.

24. McCluskey E. J. Built-in Self-Test Techniques // IEEE Design & Test of Computers. April 1985. - P. 21-28.

25. Bardell P. H., McAnney W. H., Savir J. Built-in Test for VLSI. Pseudorandom Techniques. New York: John Wiley&Sons Inc. -1987.

26. Abramovici M. A., Breuer M. A., and Friedman A. D. Digital Systems Testing and Testable Design. New York: W. H. Freeman and Company. -1990.

27. Wunderlich H. J. Hochintegrierte Schaltungen: Prufgerechter Entwurf und Test // Berlin: Springer Verlag. - 1991.

28. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part1: Principles // IEEE Design & Test of Computers. Vol.10, -№1. - 1993. -P. 73-82.

29. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 2: Applications // IEEE Design & Test of Computers. Vol.10, - №2. - 1993. -P. 69-77.

30. Savir J., Bardell P. H. Built-in-Self-Test: Milestones and Challenges // VLSI design. Vol. 1, - №1. - 1993. - P. 23-44.

31. Parag K. Lala. Self-Checking and Fault-Tollerant Digital Design // University of Arkansas.

32. W. K. Fuchs, J. A. Abraham. A Unified Ap-proach to Concurrent Error Detection in Highly Structured Logic Arrays // Proc. Of 1984 Int. Test Conference P. 4-9.

33. H. Fujiwara. A New PLA Design for Universal Testability // IEEE Transaction on Computers. Vol. C-33, No. 8 - August 1984 - P. 745-750.

34. К. C. Wei, J. J. Sheu and B. D. Liu. Low Over-head Design for Programmable Logic Array with Testability // Int. J. Electronics 1994 - vol. 77, No. 2 - P. 241-250.

35. Levin and M. Karpovsky. On-Line Self-Checking of Microprogram Control Unit // 4th IEEE Intl. On-Line Testing Workshop Capri, Italy - July 1998 -P. 152-156.

36. Yu. Matrosova, S. A. Ostanin. Self-Checking Synchronous FSM Network Design // 4th IEEE Intl. On-Line Testing Workshop Capri, Italy - July 1998 -P. 162-166.

37. Levin and V. Sinelnikov. Self-Checking of FPGA-based Control Units // Proceedings of 9th Great Lakes Symposium on VLSI Ann Arbor, Michigan - March 4-6 -1999 IEEE - P. 292-295.

38. Levin, A. Yu. Matrosova, V. Sinelnikov, S. A. Ostanin. Totally Self-Checking FPGA based FSM // 5th IEEE Intl. On-Line Testing Workshop Rhodes, Greece- July 1999- P. 5.

39. Fadi Y. Busaba and Parag K. Lala. Self-Checking Combinational Circuit

40. Design for Single and Unidirectional Multibit Error // JETTA, 5 1994 - P. 19-28.

41. Bryant R.E. Graph-Based Algorithms for Boo-lean Function Manipulation // IEEE Trans, on Corp. Vol. C-35, № 8 - 1986 - P. 677-691.

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

43. Согомонян Е. С. Построение дискретных устройств с диагностикой в процессе функционирования // Автоматика и телемеханика. -№11 1970 -С. 153-160.

44. Аксенова Г. П., Согомонян Е. С. Синтез схем встроенного контроля для автоматов с памятью // Автоматика и телемеханика. №9 - 1971 — С. 170-179.

45. Carter W. С., Schneider P. R. Design of Dynamically Checked Computers // JFIP Congress. 1968 - P. 878-883.

46. Horwarth J. Checking Sequential Logic Circuits // US PS 4556976, G06F 11/00.-1985.

47. Reinert D. Entwurf und Diagnose komplexer digitaler Systeme. Berlin. VEB Verlag Technik. -1983.

48. Siewiorek D. P., Schwarz R. S. The Theory and Practice of Reliable System Design. Bedford: Digital Press. -1982.

49. Sellers F. F., Hsiao M. J., Bearnson L. W. Error Detecting Logic for Digital

50. Computers. New York: McGraw-Hill. - 1968.

51. Minero R. H., Anello A. J., Furey R. G., Palounek L. R. Checking by pseudoduplication//US PS 3660646, G06F 11/00.-1972.

52. Murayama N. Matrix Collating System // US PS 3548376, НОЗК 13/34. -1970.

53. Betrand J. C., Gambiasi N., Mercier J. J. Totally Self-Checking Sequential Circuits // Proc. Int. Sympos. «Discrete Systems». Riga: Zinatne. - Bd. 2. -1974-P. 36-44.

54. V.V. Dimakopoulos et al., On TSC Checkers for m-out-of-n Codes // IEEE Trans. Comput.-Vol. 44-Aug. 1995 -P. 1055-1059.

55. C. Efstathiou and C. Halatsis. Efficient Modular Design of m-out-of-2m TSC Checkers, for m=2K-l, K>2 // Electron. Lett., Vol. 21 Nov. 1985 - P. 10821084.

56. Paschalis Efficient Structured Design of Totally Self-Checking M-out-of-N Code Checkers with N>2M and M=2K-1 // Int. J. Electronics Vol. 77 - Aug. 1994-P. 251-257.

57. A.M. Paschalis, D. Nicolos, and C. Halatsis. Efficient Modular Design of TSC Checkers for m-out-of-n Codes // IEEE Trans. Comput., Vol. C-37 — March 1988- P. 301-309.

58. D.A. Anderson and G. Metze. Design of Totally Self-Checking Check Circuits for m-out-of-n Codes // IEEE Trans. Comput., Vol. C-22 — March 1973- P. 263-269.

59. S.J. Piestrak. The Minimal Test Set for Sorting Networks and the Use of Sorting Networks in Self-Testing Checkers for Unordered Codes // Dig.Pap.FTCS-20, Newcastle upon Tyne, Uk. June 1990 - P. 457-464.

60. S.J. Piestrak. Design Method of Totally Self-Checking Checkers for m-out-of-n Codes//Dig. Pap. FTCS-13, Milan, Italy- Junel983 P. 162-168.

61. S.J. Piestrak. Design of Fast Self-Testing Checkers for m-out-of-2m and m-out-of-(2m±l) Codes // Int. J. Electronics, Vol. 74 Feb. 1993 - P. 177199.

62. S.J. Piestrak. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Scientific Papers of Inst, of Techn. Cybern. of Techn. Univ. of Wroclaw, No. 92, Ser.: Monographs No. 24, Oficyna Wyd. Polit. Wroct., Wroclaw 1995 - P. 112.

63. V.V. Sapozhnikov and VI.V. Sapozhnikov. Universal Algorithm for Synthesizing Self-Checking Testers for Constant-Weight Codes // Probl. Inf. Transm., Vol. 20, No. 2 1984 -P. 128-137.

64. V.V. Sapozhnikov and Vl.V. Sapozhnikov. Self-Checking Checkers for Balanced Codes // Autom. Remove Control, Vol. 53 March 1992 - P. 321348.

65. J.E. Smith. The Design of Totally Self-Checking Check Circuits for a Class of Unordered Codes // J. Des. Autom. Fault-Tolerant Comput., Vol. 2 — Oct. 1977-P. 321-342

66. C.Y. Lee. Representation of switching circuits by binary-decision programs // Beil. Syst. Tech. J., vol. 38 July 1959 - P. 985-999.

67. S. B. Akers. Binary decision diagrams // IEEE Trans. Comput., vol. C-27 -June 1978-P. 509-516

68. M.R. Garey and D.S. Johnson. Computers and Intractability. A Guid to the Theory of NP-Completeness. New York: Freeman, 1979.

69. F.J. Hill and G.R. Peterson. Introduction to Switching Theory and Logical Design. New York: Wiley, 1974.

70. J.P. Roth, Computer Logic, testing, and Verification. Rockville, MD: Computer Science Press, 1980.

71. R. Brayton. Fast recursive Boolean function manipulation // in Proc. Int. Symp. Circuits and Syst., IEEE. Rome, Italy May 1982 - P. 58-62.

72. B.M.E. Moret. Decision trees and diagrams // Ass. Comput. Mach., Comput. Surv., vol. 14-Dec. 1982-P. 593-623.

73. S. Fortune, J. Hopcroft and E.M. Sehmidt. The complexity of aquivalence and containment for tree single variable program schemes // in Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 62,

74. Goos. Hartmannis, Ausiello and Boehni. Eds. Berlin: Springer-Verlag. 1978 -P. 227-240.

75. R.W. Payne. Reticulation and other methods of reducing the size of printed diagnostic keys // J. Gen. Microbiol., vol. 98 -1977 P. 595-597.

76. R. Brayton et al., Logic manipulation Algorithms for VLSI Synthesis, Hingham, MA: Kluver, 1984.

77. C.E. Shannon. A symbolic analysis of relay and switching circuits // Trans. AIEE, vol. 57-P. 713-723.

78. C.S. Wallace. A suggestion for s fast multiplier // IEEE Trans. Electron. Comput., vol. EC-13 Jan. 1964-P. 14-17.

79. A.V. Aho, J.E. Hoperolt and J.D. Ullman. The Design and analysis of Computer Algorithms. Reading. M.A.: Addition-Wesley, 1974.

80. J.S. Jephson, R.P. McQuarrie and R.E. Vogelsberg. A three-level design verification system // IBM Syst. J., vol. 8, no. 3 1969 - P. 178-188.

81. TTL Data Book, Texas Instruments, Dallas, TX, 1976.

82. M. Rowan-Robinson, Cosmology. London: Oxford University Press, 1977.

83. S.B. Akers. Functional testing with binary decision diagrams // in Proc. Sth. Ann. IEEE Conf. Fault-Tolerant Comput. 1978 - P. 75-82.

84. R.P. Brent and H.T. Kung. The aria-time complexity of binary multiplication // J. Ass. Comput., Mach., vol. 28 July 1981 - P. 521-534

85. H. Abelson and P. Andreae. Information transfer and aria-time tradeoffs for VLSI multiplication // Commun. Ass. Comput. Mach., vol. 23 Jan. 1980 — P. 20-23.

86. Матросова А.Ю., Никитин K.B. Проектирование самотестируемого детектора неупорядоченных кодов // Докл. Международной конференции Компьютерные науки и информационные технологии. Саратов, 2002. с. 44-45.

87. К.В. Никитин. Об оценке сложности комбинационного детектора равновесных кодов // Третья всероссийская конференция с международным участием Новые информационные технологии висследовании дискретных структур, Томск, 2000 — С. 252-256.

88. Матросова А.Ю., Никитин К.В. Синтез самопроверяемого детектора равновесных кодов // Вестник Томского государственного университета №271-2000.-С. 101-105.

89. A. Matrosova, К. Nikitin, О. Goloubeva. Totally self-checking FSM design based on multilevel synthesis methods and FPGA implementation // 7th IEEE International On-Line Testing Workshop, Taormina, Italy July 9-11, 2001 -P. 144.

90. А.Ю. Матросова, К.В.Никитин. Синтез самотестируемого детектора (m,n) кодов на программируемых логических блоках // Вестник Томского государственного университета. Приложение. №6. 2003. — С. 124-136.

91. A. Matrosova, V. Ostrovsky, I. Levin, К. Nikitin. Designing FPGA based Self-Testing Checkers for m-out-of-n Codes // 9th IEEE International On-Line Testing Workshop, Greece, Kos. July 7-9,2003 - P. 49-53.