ВВЕДЕНИЕ 5
1 Постановка задачи 7
2 Построение частичных функций для подсхем 8
3 Программная реализация алгоритма 18
3.1 Входные данные 18
3.2 Обработка данных 20
3.3 Троичное моделирование 27
4 Результаты исследований 31
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 34
Производство логических схем высокого уровня интеграции и высокого быстродействия связано с большими трудозатратами. К сожалению, даже на последних этапах проектирования возможно обнаружение неисправности в схеме. Возвращение к ранним этапам проектирования является дорогостоящим, а выбрасывание неисправной схемы приводит к снижению выхода годных схем, что отражается на себестоимости производимых схем. Конечно, маскировать неисправность можно, используя дублирование в предположении, что неисправность возможна только в одной из двух схем. Тогда достаточно использовать вместо неисправной схемы исправную схему. Возможно также применение устойчивых к неисправностям схем с использованием дублирования и детекторов кодов [1-3]. Однако этот подход связан с существенными аппаратурными затратами, которые часто оказываются неприемлемыми на практике. В работе [4] предложен подход к синтезу частично программируемых схем, в которых имеет место аппаратурная избыточность в пределах 10 % и обеспечивается маскирование более 80 % неисправностей. Подход основан на возможности представления поведения функций, сопоставляемых подсхемам, реализациями соответствующих частичных функций, конкретный вид которых определяется способом включения подсхемы в схему. Причем, для подсхемы подмножества единичных и нулевых наборов значений переменных частичной функции компактно представляются Reduced Ordered Binary Decision Diagram (ROBDD)-графами и, следовательно, обеспечивается возможность поиска лучших ее реализаций. Речь идет о частичных функциях, зависящих от входных переменных схемы, которой рассматриваемая подсхема принадлежит.
В данной работе предлагается алгоритм извлечения из этой частичной функции частичной функции от заданного множества внутренних переменных схемы, основанный на использовании троичного моделирования. Применяется специальное троичное моделирование, позволяющее определять допустимость интервала для функции или ее инверсии процедурой, сложность которой является линейной функцией от числа вершин ROBDD графа, представляющего эту функцию. Воспользовавшись таким троичным моделированием, получаем интервальное описание областей, содержащих искомые множества единичных и нулевых наборов частичной функции в пространстве выделенного подмножества внутренних переменных схемы. Далее из этих областей двоичным моделированием выделяются множества единичных и нулевых наборов частичной функции. Эти множества могут затем использоваться для синтеза схемы, маскирующей неисправность выходного полюса подсхемы. Входы маскирующей подсхемы подключаются к внутренним переменным заданного подмножества и к выходу подсхемы. Такое подключение используется в рамках Engineering Change Order (ECO) технологий. Будем иметь в виду, что маскирующая подсхема корректирует не только неисправность выходного полюса рассматриваемой подсхемы, но и любую неисправность фрагмента этой подсхемы от ее выхода до ближайших точек ветвления подсхемы. Это выбросить, поскольку решили ограничиваться двухуровневыми схемами- заплатками.
Рассмотрен алгоритм построения частичных функций для подсхем, который позволяет получить множества единичных и нулевых наборов частичной функции от внутренних переменных. По этим наборам может быть построена компактная схема, позволяющая маскировать неисправность в исходной схеме с низкой аппаратурной избыточностью. Осуществлена программная реализация алгоритма. Проведены исследования результатов работы программы на схемах пакета MCNC.
