WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 | 4 |

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

Андреева Валентина Валерьевна ОБЕСПЕЧЕНИЕ СОКРАЩЕНИЯ АППАРАТУРНЫХ ЗАТРАТ В СХЕМАХ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ СО СВОЙСТВАМИ САМОПРОВЕРЯЕМОСТИ, САМОТЕСТИРУЕМОСТИ И ОТКАЗОУСТОЙЧИВОСТИ 05.13.01 – системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Томск - 2009 2

Работа выполнена на кафедре программирования ГОУ ВПО «Томский государственный университет»

Научный консультант: доктор технических наук, профессор Матросова Анжела Юрьевна

Официальные оппоненты: доктор технических наук, профессор Евтушенко Нина Владимировна кандидат технических наук, доцент Тюнина Людмила Васильевна

Ведущая организация: Институт вычислительного моделирования СО РАН, г. Красноярск

Защита состоится:

8 октября 2009 г. в 10.30 час. на заседании диссертационного совета Д 212.267.12 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 4 сентября 2009 г.

Ученый секретарь диссертационного совета В.И. Смагин доктор технических наук, профессор 3

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

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

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

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

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

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

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

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

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

Эффективность разработанных методов подтверждается компьютерными экспериментами.

Научная новизна:

– Вводится понятие интервала системы булевых функций с максимальной характеристикой. Показано, что кратчайшая частично монотонная (монотонная) безызбыточная реализация из таких интервалов получается объединением кратчайших частично монотонных (монотонных) реализаций для элементов системы частичных булевых функций с одной и той же характеристикой.

– Предлагается алгоритм построения проверяющего теста, ориентированный на сокращение длины теста. Тест обнаруживает одиночные неисправности системы безызбыточных дизъюнктивных нормальных форм. Метод основан на выделении максимально совместимых подмножеств конъюнкций, представляющих тестовые наборы, в процессе построения специального дерева разложения. Конъюнкции строятся путем решения соответствующих логически уравнений. Разработана модификация алгоритма А.Д.

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

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

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

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

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

– Алгоритм минимизации систем частичных булевых функций в рамках частично монотонных (монотонных) реализаций, основанный на использовании максимальных интервалов с максимальными характеристиками, программно реализован и может быть использован на этапе логического синтеза самопроверяемых схем в существующих САПР с целью сокращения аппаратурных затрат.

– Предлагаемый в работе алгоритм построения проверяющего теста для системы безызбыточных ДНФ программно реализован и может быть использован для тестирования логических схем. Проверяющий тест позволяет обнаруживать все кратные константные неисправности на полюсах логических элементов схемы, построенной по системе безызбыточных ДНФ факторизационным методом синтеза, сохраняющим систему. Обеспечиваемое алгоритмом сокращение длины теста дает возможность сократить время тестирования и память для хранения тестовых наборов при использовании BIST (Build in Self Testing) технологий.

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

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

– Алгоритм минимизации частично монотонных (монотонных) реализаций частичных систем булевых функций.

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

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

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

- «Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования», 1999-2000 гг.

- НИР «Разработка математических и программных средств обеспечения надежного и безопасного доступа к электронным ресурсам коллективного пользования», 2006-2007 гг.

Основные результаты диссертации внедрены в учебный процесс ТГУ.

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

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

1. The 8th IEEE International On-Line Testing Workshop (Bendor, France, 2002).

2. The 8-th Biennial Baltic Electronic Conference ( Tallinn, Estonia, 2002).

3. 2-ая Сибирская научная школа-семинар с международным участием «Проблемы компьютерной безопасности и криптографии» (Томск, Россия, 2003).

4. The 6th International Workshop on Boolean Problems (Freiberg, Germany, 2004).

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

6. 4-ая / 6-ая Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (Шушенское, Россия, 2006 / Горно-Алтайск, 2007).

7. 5-ая Международная конференция студентов и молодых ученых «Перспективы развития фундаментальных наук» (Томск, Россия, 2008) 8. The 7-th East-West Design & Test international Symposium (Львов, Украина, 2008).

Результаты диссертации опубликованы в 14 научных работах, одна из которых из перечня изданий, рекомендованных ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, 4-х глав, заключения, приложения и списка используемой литературы, включающий 109 наименований. Общий объем диссертации составляет 128 страниц текста, включая 14 рисунков и 15 таблиц.

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

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

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

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

Дается обоснование алгоритмов.

Рассмотрим систему частичных булевых функций F(X)={f1(X), …, fm(X)}, Х = {x1,…,xn}, заданную множествами M1(fi), M0(fi). Здесь M1(fi) – множество наборов (булевых векторов) значений переменных, на которых функция fi системы принимает единичное значение, а M0(fi) – множество наборов значений переменных, на которых функция fi принимает нулевое значение, m – число функций системы.

Определение 1. Интервал u булева пространства En является допустимым для функции fi, если u M1( fi), u M0(fi) =.

Определение 2. Допустимый интервал u является максимальным для функции fi, если не существует допустимого интервала u, такого что u u.

Обозначим через (u, h) допустимый интервал системы F (X). В паре (u, h) символом u обозначен интервал булева пространства En, символом h – характеристика интервала. Интервал представляется троичным вектором, в характеристике перечисляются функции fi1,…, fil, для каждой из которых выполняется условие: u M1( fi ), u M0( fi ) =. Характеристика h j j обычно представляется булевым вектором.

Определение 3. Допустимый интервал (u, h) системы называется максимальным, если при сохранении характеристики h не существует интервала (u’, h), такого что u’ u.

Обозначим через (, g) элемент системы F. Здесь – элемент булева пространства En, представляемый булевым вектором размерности n, g – характеристика элемента, задающая множество булевых функций { f,…, f } j1 js системы, принимающих единичное значение на этом элементе.

Определение 4. Будем говорить, что интервал (u, h) покрывает элемент (, g) и обозначать это (, g) (u, h), если u, { fi1,…, fil }{ f,…, f }.

j1 js Определение 5. Пусть характеристики подмножества элементов системы F(X), покрываемых некоторым интервалом (u, h), одинаковы и представляются вектором h, тогда характеристика h интервала (u, h) системы F(X) является максимальной по мощности. Будем называть интервал (u, h) интервалом с максимальной характеристикой.

Рассмотрим некоторое множество W допустимых интервалов системы, W={w1,w2,…,ws}. Для каждой функции fi системы F(X) выделим подмножество Wi, WiW, в характеристике каждого интервала этого подмножества содержится функция fi. Представим элемент множества M1(fi) как элемент (, g) системы F(X), в характеристике которого содержится единственная функция fi.

Определение 6. Назовем множество W реализацией системы F(X), если для каждого элемента (, g) из M1(fi) выполняется условие: (, g) покрывается интервалом из Wi, i = 1, …, m.

Определение 7. Множество W максимальных интервалов системы F(X) является безызбыточной реализацией, если из характеристик максимальных интервалов wi нельзя выбросить ни одной функции: выбрасывание функции fi из характеристики приводит к тому, что некоторые элементы множества M1(fj) оказываются не покрытыми оставшимися интервалами.

Определение 8. Безызбыточную реализацию будем называть кратчайшей, если она состоит из наименьшего числа максимальных интервалов системы F(X).

Определение 9. Дискретный автомат-это пятерка объектов (X,Q,Y,, ), где X – входной алфавит, Y – выходной алфавит, Q – внутренний алфавит или множество состояний автомата, – функция переходов, – функция выходов.

Pages:     || 2 | 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»