WWW.DISSERS.RU

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

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

Pages:     | 1 | 2 || 4 |

Для построения a-тестового набора, обнаруживающего исчезновение некоторой конъюнкции Ki из D, получим D* путем вычеркивания конъюнкции Ki из D. Строим D, D = D*(Ki). Пусть ri конъюнкция, представляющая корень логического уравнения D = 0, тогда всякий набор значений переменных БДНФ, обращающий в единицу логическое произведение Kia = ri Ki, есть а-тестовый набор. Здесь Kia – конъюнкция, представляющая тестовые наборы.

Обозначим символом A множество a-тестовых наборов (по одному на каждую неисправность), обнаруживающих все a-неисправности БДНФ.

Для построения b-тестового набора, обнаруживающего исчезновение переменной xi из конъюнкции K, полагаем D = D(K*(xi)) и решаем уравнение D = 0. Пусть конъюнкция, представляющая корень этого уравнения. Всяr i кий набор значений переменных БДНФ, обращающий в единицу логическое произведение Kib = ri K*(xi), есть b-тестовый набор. Здесь Kib – конъюнкция, представляющая тестовые наборы.

Обозначим символом B множество b-тестовых наборов (по одному на каждую неисправность), обнаруживающих все b-неисправности БДНФ.

В дальнейшем множество A(B) будем называть A(B) тестом БДНФ.

Длина A теста не превосходит количества конъюнкций в БДНФ, а длина B теста не превосходит суммы рангов конъюнкций БДНФ. Обозначим символом T проверяющий тест, обнаруживающий все одиночные неисправности БДНФ. Тест T может быть получен путем объединения всех a,b-тестовых наборов, построенных по БДНФ. Длина проверяющего теста T не превосходит суммы длин A, B тестов.

Сокращение длины A теста для БДНФ невозможно, а B тест можно сократить за счет того, что один и тот же тестовый набор в общем случае может обнаруживать некоторое подмножество b-неисправностей. Таким образом, сокращение проверяющего теста БДНФ осуществляется за счет сокращения длины B теста.

Предлагается алгоритм сокращения длины B теста, который состоит из трех этапов:

1. Построение Kib – конъюнкций, представляющих b-тестовые наборы. При реализации этого этапа отыскивается корень ri уравнения.

Предложена модификация известного алгоритма А.Д. Закревского поиска одного корня логического уравнения D = 0, позволяющая найти корень уравнения по возможности меньшего ранга. Эффективность предложенной модификации подтверждается компьютерными экспериментами, приведенными в диссертации.

2. Выделение среди множества {Kib} конъюнкций максимально совместимых подмножеств.

3. Поиск безызбыточного покрытия максимально совместимыми подмножествами заданного множества b-неисправностей.

Множество конъюнкций называется совместимым, если их пересечение не пусто.

Совместимое множество конъюнкций называется максимальным относительно некоторого заданного множества конъюнкций P, если в него нельзя добавить ни одной конъюнкции из P.

Рассмотрим множество конъюнкций Е. Напомним, что множество конъюнкций можно интерпретировать как ДНФ. Множество (ДНФ) монотонно по переменной xi, если эта переменная встречается в нем с одним и тем же знаком инверсии. Иначе множество не монотонно по рассматриваемой переменной.

Предложено выделять максимально совместимые подмножества из Е в процессе построения дерева разложений (ДР). Порядок разложения по переменным заранее не определен.

Каждой вершине v приписывается подмножество Pv из Е следующим образом. Пусть Kv конъюнкция, сопоставляемая простой цепи, соединяющей корень ДР с вершиной v. Конъюнкция K из Е входит в Pv, если она имеет с Kv непустое пересечение. Это значит, что каждая буква из Kv либо содержится в K с тем же знаком инверсии, либо отсутствует в ней.

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

Пусть Pi - произвольное максимальное совместимое подмножество из Е.

Теорема 6. В ДР, построенном для множества Е, найдется концевая i i вершина vi, такая что сопоставляемое ей подмножество Pv, есть Pi, Pv = Pi.

Построим все максимально совместимые подмножества для E = {-100-, 01---0, 10--0-, -0-0-1, -0-000, 001-1-, 0010--, --0000}, используя ДР. Здесь конъюнкции представлены троичными векторами. Подмножества для внутренних вершин обозначим Mi(xj), для концевых - Pi (рис.2).

1 0 0 0 0 0 0 M (x ) 0 0 1 1 x 0 0 1 0 0 0 1 1 0 0 1 0 P 01 1 x5 M (x ) 0 0 0 0 0 0 0 0 0 2 0 0 1 1 0 0 0 0 0 1 0 1 0 P 0 0 1 0 0 0 M (x ) 0 0 x6 M (x ) 0 0 1 3 6 0 0 1 3 0 0 1 0 0 0 1 0 0 0 x x M (x ) 0 0 1 4 0 0 0 1 0 1 1 0 0 0 0 1 0 P3 P 0 0 1 0 0 1 0 x P5 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 P6 P0 0 1 0 0 0 0 Рисунок 2 – Дерево разложений Построим матрицу M, в которой строкам сопоставлены конъюнкции множества Е, а столбцам – максимально совместимые подмножества из этих конъюнкций. Кратчайшее покрытие строк такой матрицы ее столбцами представляет множество Pmin = {P1, P2, …, Ps} максимально совместимых подмножеств. Сопоставим максимально совместимому подмножеству Pi логическое произведение Pi конъюнкций этого подмножества, получим множество {P1, P2, …, Ps}.

Если в качестве множества Е выбрано множество конъюнкций, представляющее тестовые наборы для всех b – неисправностей, тогда логические произведения {P1, P2, …, Ps} представляют В тест. Вместо кратчайшего покрытия строк матрицы M можно строить безызбыточное покрытие, по возможности близкое к минимальному.

Сформулируем алгоритм построения проверяющего теста для системы БДНФ. Алгоритм включает в себя следующие шаги.

Ш.1. Строим множество конъюнкций {Kia}, представляющих a-тестовые наборы для всех БДНФ системы.

Ш.2. Строим множество конъюнкций {Kib}, представляющих b-тестовые наборы для всех БДНФ системы.

Ш.3. Объединяем {Kia}и{Kib}, находим множество Е, выделяем в нем максимально совместимые подмножества конъюнкций.

Ш.4. Находим безызбыточное покрытие неисправностей системы БДФ максимально совместимыми подмножествами. Покрытие представляет проверяющий тест для системы БДНФ.

Эффективность предложенного алгоритма подтверждается компьютерным экспериментом (таблица 6). Испытания проводились на контрольных примерах, представляющих STG описание поведения синхронных автоматов.

Проводилось кодирование состояний автомата, а затем выполнялся переход к системе безызбыточных ДНФ.

В таблице 6 введены следующие обозначения: K – количество конъюнкций в системе БДНФ; L – количество букв в системе БДНФ; DT – длина теста T, построенного предложенным алгоритмом; DT* – длина теста Т*, построенного путем объединения всех a, b тестовых наборов системы БДНФ;

% – отношение длины проверяющего теста T к длине теста T*, выраженное в процентах.

Таблица Наз-е Экспериментальные реK L DT DT* % примера зультаты показали, что предлоbbsse 44 218 77 220 женный алгоритм позволяет bbtas 18 48 24 45 строить проверяющий тест, длиbeecount 24 79 27 71 на которого значительно меньше, dk16 120 583 113 395 чем длина теста, построенного donfile 166 987 128 327 путем объединения всех a, bex1 108 540 98 440 keyb 87 727 211 599 35 тестовых наборов системы planet 218 1153 187 1024 БДНФ.

s1 105 548 165 619 Сокращение длины теста sand 184 1179 240 1088 позволяет в рамках BISTscf 354 2493 253 1146 технологий сократить время тесsync 117 521 116 483 тирования синхронных автомаtbk 243 2130 529 1255 тов и объем памяти, необходимой для хранения тестовых наборов.

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

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

Пусть задано описание функционирования синхронного автомата, например, STG -описание. Требуется построить схему, обеспечивающую заданное функционирование, и устойчивую к неисправностям.

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

Самопроверяемое синхронное устройство ССУ1 y1,…,ym y1',...,ym' x1,…,xn y11,…,ym u y',…,ys' m+Ky1,…,y1 ИЛИ MX m+1 s ' ' ДК z,…,z 1 p uz11,…,zp1 z1,…,zp d11,…,dpСамопроверяемое синхронное устройство ССУy12,…,ym'' '' y,…,y 1 m K2 y2,…,y m+1 s И z1",…,zp" z12,…,zpd12,…,dpРисунок 3 – Архитектура отказоустойчивого дискретного устройства Схема, устойчивая к неисправностям, представлена на рис. 3. Ее компонентами являются две идентичные самопроверяемые схемы, схема из элементов И, схема из элементов ИЛИ, мультиплексор и детектор кодов.

Здесь K1 и K2 - комбинационные составляющие идентичных самопроверяемых синхронных устройств ССУ1, ССУ2, обеспечивающие монотонное проявление допустимых для этих устройств неисправностей на выходах. В качестве допустимых неисправностей рассматриваются одиночные константные неисправности на полюсах логических элементов комбинационной составляющей, а также одиночные константные неисправности на полюсах dтриггеров синхронного устройства.

Подсхема ИЛИ состоит из s+p двухвходовых элементов ИЛИ, так что входами одного и того же элемента ИЛИ являются одноименные выходы комбинационных схем K1 и K2. Эта подсхема имеет s+p выходов, то есть выходы элементов ИЛИ являются выходами подсхемы.

Подсхема И состоит из s+p двухвходовых элементов И, так что входами одного и того же элемента И являются одноименные выходы комбинационных схем K1 и K2. Эта подсхема имеет s+p выходов, то есть выходы элементов И являются выходами схемы.

Выходы подсхемы ИЛИ являются входами подсхемы детектора (ДКподсхемы) равновесных кодов. ДК-подсхема имеет два выхода: u1,u2.

Выходы подсхемы И являются входами подсхемы мультиплексора.

Мультиплексор MX связывает линии y1, …, ym; z1, …, zp с линиями y1, …, ym; z1, …, zp, если на входах u1, u2 мультиплексора достигаются значения 01 (10). Иначе мультиплексор связывает линии y1, …, ym; z1, …, zpc линиями y1, …, ym; z1, …, zp.

Допустимыми неисправностями подсхем ИЛИ (И) являются одиночные константные неисправности на полюсах составляющих эти подсхемы элементов.

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

Неисправности мультиплексора могут привести к замене связей некоторых линий из ряда y1, …, ym; z1, …, zp на одноименные линии ряда y1, …, ym; z1, …, zp. Допускаются также одиночные константные неисправности на линиях связей между подсхемами, кроме линий x1, …, xn; y1, …, ym; z1, …, zp. Если линия разветвляется, то неисправность имеет место на одной из ветвей линии.

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

Обозначим через VД множество допустимых неисправностей несамотестируемого детектора кодов. Пусть VИЛИ, VИ – множества допустимых неисправностей подсхем ИЛИ, И, соответственно. V1,V2 – множества неисправностей подсхем ССУ1,ССУ2; VL – множество неисправностей линий. Обозначим через V объединение этих множеств: V=V1 V2 VД VИЛИ VИ VL.

Теорема 7. Неисправность v из V сохраняет корректное поведение синхронного последовательностного устройства.

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

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

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

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

В таблице 7 введены следующие обозначения: КП– контрольные примеры: 1 – sync, 2– s1a, 3 – dk16, 4 – s1, 5 – dk14, 6 – opus, 7 – ex4; n – число входов синхронного последовательностного устройства; m – число выходов;

p – число конъюнкций в STG-описании; s – число состояний; q – число линий обратных связей после кодирования состояний; NТ – сложность последовательностной схемы при троировании без учета сложности схемы голосования и сложности d-триггеров; N – сложность предложенной архитектуры без учета сложности мультиплексора и d-триггеров. Под сложностью понимается число двухвходовых элементов НЕ И и инверторов.

Таблица КП n m p s q NТ N Из таблицы видно, что 1 19 7 80 52 6 4584 сложность предлагаемой схемы не больше сложности трех не2 8 6 107 20 5 5349 самотестируемых схем, исполь3 2 3 108 27 5 5427 зуемых при троировании.

4 8 6 107 20 5 6387 5 3 5 56 7 3 2382 6 5 6 22 10 4 927 7 6 9 21 14 4 873 Заключение В диссертационной работе предложены решения некоторых задач контролепригодного проектирования дискретных устройств, их решение позволяет сократить аппаратурные затраты при проектировании самопроверяемых, самотестируемых и отказоустойчивых устройств.

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

Pages:     | 1 | 2 || 4 |






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