Регулярный метод синтеза тестовых последовательностей. Установочная последовательность - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Генераторы реальных случайных последовательностей 1 108.06kb.
О синтезе дискретно-кодированных последовательностей периода 3 317.51kb.
Банк данных Общая химия 577. 1(076. 1) С232 Сборник тестовых вопросов 1 306.63kb.
Вопросы к экзамену по дисциплине «Прикладной функциональный анализ» 1 36.69kb.
Метод сборки контигов геномных последовательностей из парных чтений... 1 58.76kb.
Задача Вычисление количества последовательностей значений из заданного... 1 53kb.
Реферат по дисциплине исследование операций на тему метод деформируемого... 1 140.84kb.
Программа государственного экзаменА по специальности 230201. 1 52.42kb.
Рекомендации по выполнению некоторых заданий егэ из части С 1 29.89kb.
Реферат статьи Рассмотрим ту же последовательность, что и в статье... 1 29.96kb.
Задачи: ( Огран-ть, альтер-ная ст-ть, кпв, факторы пр-ва, специализация... 1 220.28kb.
Материал к витатонус и фибромакс сера минерал красоты, большого спорта... 1 194.37kb.
Направления изучения представлений о справедливости 1 202.17kb.

Регулярный метод синтеза тестовых последовательностей. Установочная последовательность - страница №1/1

УДК 681.326.06

РЕГУЛЯРНЫЙ МЕТОД СИНТЕЗА ТЕСТОВЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ. УСТАНОВОЧНАЯ

ПОСЛЕДОВАТЕЛЬНОСТЬ

ГОЛЫНИЧЕВ В. Н., ЗВЯГИН В. Ф., НЕМОЛОЧНОВ О. Ф.

(Ленинград)

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



1. Введение

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

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

Метод синтеза установочной последовательности базируется на необ­ходимых и достаточных условиях отсутствия критических состязаний, сформулированных в [1] для схем, функционирование которых не осно­вано на специальном подборе задержек. Установочная последовательность строится на основании модели исправной схемы. Поведение схемы с за­данной неисправностью является задачей, представляющей самостоятель­ный интерес.

В качестве иллюстрации метода синтезирована установочная последо­вательность для схемы двухразрядного счетчика.
2. Модель схемы. Макроэлементы

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



Рис. 1. Модель последовательностпой подсхемы: а - асинхрон­ный триггерный макроэлемент, б — режим установки, в — ре­жим хранения. КС — комбинационная схема, б — произвольная задержка, Схобласть установки кубического покрытия мак­роэлемента, Сробласть хранения кубического покрытия макро­элемента

π-алгоритму [3]. Вопросы, связанные с построением кубических покрытий, подробно рассмотрены в [4], там же показана адекватность принятой модели исходной схеме. В модели функция, реализуемая подсхемой, при­нимается троичной. Это обстоятельство используется для обеспечения кор­ректности установочной последовательности [1]. Каждой подсхеме сопо­ставляется макроэлемент, и вся дальнейшая обработка схемы производит­ся на уровне соединения макроэлементов. Построение модели производит­ся программным образом. Класс обрабатываемых схем ограничивается схемами, представимыми в виде соединения макроэлементов. Имеющаяся программная реализация рассчитана на обработку схем объемом до 1200 вентилей.

Будем различать комбинационные и последовательностные макроэле­менты. Последовательностпый макроэлемент соответствует простейшей последовательностной подсхеме, которая выделяется таким образом, что для разрыва одной или нескольких петель обратной связи достаточно ввести одну точку разреза (рис. 1, а). Обозначим через X вектор логических зна­чений на входах схемы, через 2 — вектор логических значений на выходах комбинационных макроэлементов.

Примем в качестве выходного значения последовательностного макро­элемента логическое значение до точки разреза и обозначим его Оу. Тогда Оу=у(Х, Iy), где Iy — логическое значение псевдохода, отражающее пре­дыдущее состояние. Последовательностный макроэлемент характеризует­ся двумя режимами работы: режимом установки, когда предыдущее состоя­ние безразлично, 1у=х (рис. 1, б), и режимом хранения, когда предыду­щее состояние существенно, (рис. 1, в). Кубическое покрытие С(0у), , подразделяется на две области С(Оу)=Сх(Оу) Сp(Оу), где Сх — область установки, Сробласть хранения. В [4] показано, что для последовательностного макроэлемента, корректное функционирование ко­торого пе основано па специальном подборе задержек, кубы удов­летворяют условию Оу=1у.

В принятой модели различают два вида петель обратной связи: локаль­ные и глобальные. Петля обратной связи, охватывающая один макроэле-


Таблица 1. Схемы и кубические покрытия макроэлементов

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

Состояние схемы отображается вектором ОУ. Выходы схемы включены в векторы ОУ и Z.

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

Функционирование многовыходной последовательностной схемы рис. 3 для некоторого состояния описывается кубическим покрытием С(ОУ) = С(ОУI), объединение проводится по всем таким, что Куб сС(ОУI) записывается в формате с=Х1УОУZ, где Х1У — входное воздействие, ОУZсостояние и реакция схемы, ОУ=У(Х, 1У), Z=Z (X, ОУ). Кубы покрытия С(ОУ{) подразделяются на две области С(ОУ()=Сх(ОУI)Ср(ОУI). Соотношения векторов и ОУ для кубов, при-

Рис. 2. Схема двухразрядпого счетчика. Выходы эле­ментов памяти Оу1, Оу2, Оу3, Оу4. Псевдовходы эле­ментов памяти Iy1, Iy2, Iy3, Iy4, –х1, х2, х3 - входы схе­мы, Z1, Z2 — выходы комбинационных подсхем


надлежащих областям Сх и СР, показаны на рис. 3, б и в соответственно. Назовем кубическое покрытие обобщенным кубическим покрытием для состояния ОУ.

3. Корректность входной последовательности

Назовем входную последовательность корректной, если она без крити­ческих состязаний сигналов переводит схему в требуемое состояние. В кор­ректной входной последовательности все входные воздействия корректны и отсутствуют переходы, на которых может возникать риск сбоя. Будем различать два вида входных воздействий: переключающие и нейтральные. Переключающим входным воздействием назовем такое воздействие, кото­рое вызывает переход схемы из состояния ОУ1i–1 в состояние ОУ1i, .Нейтральное входное воздействие сохраняет достигнутое на преды­дущем наборе состояние ОУ1i–1, ОУ1i–1= ОУ1i.

Модель корректной последовательности (рис. 4), предложенная в [1], детализирует процесс переключения. В последовательности чередуются пе­реключающие и нейтральные наборы, Q1 , L1, Q2,, …,Li-1, Qi…. Нейтраль­ные наборы вводятся с целью устранения статического риска сбоя. Набор Qi имеет три составляющие: ci, c*i, c1i; Набор Li имеет две составляющие:

Куб обеспечивает отсутствие статического риска сбоя на переходе от переключающего набора Qi-1 к нейтральному наборуLi-1,



Куб обеспечивает отсутствие статического риска на пере­ходе к переключающему набору

Куб обеспечивает изменение состояния, достигнутого в пре­дыдущем наборе, без критических состязаний, Кубом c*i вырабатываются к* такие, что Оук* равно 1 (0), Iy*k равно х. Состояние ОУ{ используется совместно с X*i для получе­ния Оук*.

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



Рис. 3. Модель схемы: а - асинхронная последовательностная схема, б — переключение в состояние ОУ, в — хранение состоя­ния ОУ. Отношения выполняются над кубами

Qi-1 и Qi не нужен. В переключающем наборе наряду с кубами из области Ср используется куб из области Сх, что позволяет изменить состояние. Со­стояние, достигнутое схемой при подаче очередного переключающего на­бора Qi , равно

Отметим, что существуют схемы, логика работы которых требует по­дачи более одного нейтрального набора. Метод построения корректных входных последовательностей для таких схем предложен в работе [5].



4. Синтез установочной последовательности

Установочная задача формулируется следующим образом: найти после­довательность, свободную от состязаний, переводящую схему из произволь­ного состояния в заданное — ОУ (поглощаемое ОУ). Если установочная последовательность Q(ОУ) существует, то она представима в виде Q(ОУ) = Q1, Q2, …, Qn, где п — заранее неизвестное число переключающих набо­ров, Установочная последовательность синтезиру­ется в направлении, противоположном подаче наборов на схему: с!n, сn*, сn ..., c!1, c*1. Исходными данными для синтеза куба cn' является состоя­ние ОУ (или в общем случае три вектора X, ОУ, Z). Процесс синтеза пред­ставляет собой поочередное вычисление кубов единого формата с', с*, с в указанном порядке и объединения их в переключающие и нейтральные наборы. Синтез продолжается до тех пор, пока не будет выполнено усло­вие 1У*=хх….х. Рассмотрим правила, применяемые при вычислении ку­бов ci1, ci*, ci.

Вычисление сi1i1I1i1 Zi1. В качестве исходного значения вектора сi1 выбирается вектор IYi+1. Если набор непосредственно предшествует проверяющей последовательности i=п, то исходный вектор может быть до­определен в соответствии с требованиями проверяющей последовательно­сти. Значение на выходе любого последовательностного макроэлемента вы­числяется кубом из области Ср(0у). Входной вектор Хi1 должен удовлет­ворять условию .
Вычисление сi*=Хi* IУi* 0Уi*Zi*. В качестве исходного значения вектора сi* выбирается вектор IYi!. Значение на выходе последовательностного мак­роэлемента вычисляется только кубом из области Сх(0у). Входной вектор Хi* должен удовлетворять условию. В случае отсутствия реше­ния из области Сх значение О (1) переносится в вектор IУi*, так как син­тез вектора Хi* IУi* 0Уi*Zi* проводится только с использованием кубов из области Сх(0у). Вектор IYi* должен удовлетворять условию т. е. по крайней мере для одной из координат Оуi* должен быть вы­бран куб с такой, что .Выполнение этого условия означает, что найденный набор действительно является переключающим. Для того что-

Рис. 4. Модель перехода из безразличного состояния 1У=хх... х в состояние ОУi'. Отношения и операции выполняются над кубами

бы в качестве i' использовался вектор, отличный от 0Yi+1, куб с, такой, что, должен быть выбран по крайней мере для одной из коор­динат. Полученный вектор IУi* сравнивается с ранее синтезиро­ванными векторами 0YK, k>i. Выполнение условия означает, что синтезированный вектор должен быть забракован.

Вычисление сiii 0УiZi. В качестве исходного значения вектора сi выбирается вектор i*. Значение на выходе любого последовательностного макроэлемента вычисляется кубом из области Ср(0у). Входной вектор Хi должен удовлетворять условию . Входной вектор IУi дол­жен удовлетворять следующему условию. Все i такие, что i*=х, Оуi' =0 (1), должны остаться безразличными на переходе. Вычисленный век­тор i является исходным вектором для синтеза очередного набора уста­новочной последовательности.

По окончании вычисления векторов искомая установочная последова­тельность формируется следующим образом. Набор Q1 формируется как Нейтральный набор Li, необходимый только, если справедли­во формируется как Набор Qi формируется как Набор Qn формируется как. Для случая, когда n=1, набор Q1 есть X1*0Y1*.

5. Синтез куба обобщенного покрытия

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

Куб обобщенного покрытия получается из исходного вектора Ni= Х1УОУZ заменой выходных значений макроэлементов значениями их входов и псевдовходов. Процесс повторяется до тех пор, пока в векторах ОУ и Z, имеются макроэлементы, выход которых не заменен значениями входов и псевдовходов. Вычисление куба производится по шагам. На каж­дом шаге выполняется операция подстановки. Под операцией подстановки понимается сопоставление выходному значению макроэлемента 1 (0) куба из его единичного (нулевого) покрытия и пересечения этого куба с имею­щимся кубом единого формата, где iномер шага, с — куб из

Таблица 2. Покоординатное пересечение

покрытия макроэлемента. Куб с должен давать непустое пересечение с кубом единого формата. Операция покоординатного пересечения двух ку­бов приведена в табл. 2.

Символ х обозначает неопределенное логическое значение. В результа­те подстановок х может быть заменен на логическое значение О (1). Сим­вол у обозначает, что данной координате не может быть присвоено ни ло­гическое значение 0, ни логическое значение 1.

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

Наличие разветвлений в схеме из макроэлементов может приводить к противоречиям при поиске решения. В процессе вычисления куба обоб­щенного покрытия может возникнуть ситуация, когда требуется выпол­нить подстановку для очередного макроэлемента, но все кубы его покры­тия дают пустое пересечение с кубом единого формата. Это приводит к перебору. Если противоречие возникает при поиске куба, принадлежащего области С*, для последовательностного макроэлемента, то результатом подстановки считается перенос логического значения выхода последова­тельностного макроэлемента из вектора ОУ в вектор IУ.

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

Окончательно сформированный куб удовлетворяет условиям: ОУОУ, . Для куба, принадлежащего области Ср, справедливо 1У=ОУ; для куба, принадлежащего области Сж, справедливо 1У=ОУ.

Пример. Вычислим куб единого формата, принадлежащий области Ср, для схемы, представленной на рис. 2. Вычисления сведены в табл. 3.

Начнем вычисления с координаты 0Y3=0. На шаге 1 выбираем для под­становки куб с22 и пересекаем его с исходным вектором. Продолжая синтез, на шаге 3 получим искомый куб единого формата, противоречий в процес­се синтеза не было.

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

Введем в рассмотрение вектор Т, который в отличие от вектора N со­держит допустимые логические значения выходов макроэлементов. Координаты вектора Т принимают значения из {О, 1, х, у}. Значение О (1) в Т означает, что в N допускается О (1) или х по соответствующей коорди­нате. Значение x в T означает, что в N данная координата может быть любой. Значение у в Т означает, что в N данная координата может принять только значение х.


Таблица 3. Построение куба обобщенного покрытия Ср1 0 х)

На каждом шаге вычисления куба единого формата помимо выбора и подстановки куба из покрытия макроэлемента выполняются действия по доопределению векторов N к Т, перечисленные ниже.

1. Доопределение входов макроэлемента по известному значению вы­хода. Выполняется для координат векторов ОУ и Z, для которых операция подстановки еще не выполнена. Рассматриваются кубические покрытия макроэлементов, для которых , где Na— значение на выходе макро­элемента а. Из кубического покрытия С (а=р) выбираются кубы, имеющие непустое пересечение с N и Т. Если во всех выбранных кубах А-я коорди­ната имеет логическое значение О (1), то выбор любого куба влечет под­становку для k-й координаты куба.

2. Доопределение выхода макроэлемента по известным значениям вхо­дов. Выполняется для координат векторов ОУ и Z, таких, что Nа=x. Коор­дината Nа принимает значение О (1), если

Пункты 1 и 2 выполняются итеративно до получения устойчивого (не изменяющегося) вектора N.





3. Определение допустимого значения выхода макроэлемента во вспо­
могательном векторе Т по известным значениям его входов. Выполняется
для координат векторов ОУ и 2, таких, что Nа=x. Координате Та присваи­–
вается значение по следующим правилам:


где М=NT.

Очередной подставляемый куб должен давать непустое пересечение как с вектором N, так и с вектором Т. Вектор Т вычисляется вычисляется итеративно.






Примеры. Рассмотрим схему рис. 2. Кубические покрытия макроэлемен­тов схемы приведены в табл. 1. Пусть N={0у1=1, 0y2=0}. Выполним пункт 1 для С (0y1=1). Доопределятся координаты х3=0, x1 =0.

Пусть N содержит координату х3=1. Вычислим вектор Т. Координаты Оу1 и 0y3 принимают значение 0.

4. Очередной подставляемый куб должен удовлетворять условиям ло­кальной и глобальной оптимальности [5] по отношению к вектору N. Вы­полнение этих условий позволяет получить простой куб. Под простым кубом понимается куб, который не поглощается другими кубами обобщенного покрытия.

Таблица 4. Синтез установочной последовательности для Оу4 = О



6. Пример синтеза установочной последовательности

Рассмотрим двухразрядный счетчик, схема которого представлена на рис. 2. Кубические покрытия макроэлементов приведены в табл. 1. Син­тезируем установочную последовательность для 0y4=0. Результаты вы­числения кубов с', с*, с сведены в табл. 4.



Шаг 1. Вычисление с*. Проведем доопределение вектора N={0у4 =0}. Получаем N={0у4=0, Z2=0}. Начинаем подстановки с 0y4=0. Для под­становки выберем куб с26. Подстановка куба с26 определяет очередной за­каз 0y3=1. В области Сх(0у3=1) нет кубов, пригодных для подстановки, поэтому в вектор заносим 1 по координате 3. На этом синтез вектора с* заканчивается, так как заказов на подстановку больше нет. Вектор IV, полученный при синтезе с*, является исходным для синтеза с.

Вычисление с. Проведем доопределение вектора N={0у3=1}. Полу­чаем N={x3=0, 0y3=1}. Начинаем подстановки. Куб с16 противоречит условию глобальной оптимальности. Для подстановки выбираем куб с17. Заказов на подстановку нет, синтез вектора окончен.



Шаг 2. Вычисление с'. Проведем доопределение вектора N={0у3=1}. Получаем N={x3=0, Оу3=1}. Начинаем подстановки с Оу3=1. Для под­становки выбираем куб с16. Теперь N={x3=0, 0y3=1, Оу3=1, Z1=0}. Появ­ляется новый заказ на подстановку Z1=0. Выбираем для следующей под­становки куб Сзо. После доопределения вектор N={x2=0, x3=0, 3=1, 0y3=1, 0y4=1, Z1=0}. Заказ 0y4 выполняется подстановкой куба с25. Все заказы на подстановку выполнены, синтез вектора с' окончен. Далее син­тезируются векторы с* и с. Шаг 2 заканчивается.

Шаги повторяются до тех пор, пока при синтезе вектора с* на шаге 5 получаем, что вектор 1У=хххх. Синтез установочной последовательности заканчивается. Переключающие наборы последовательности получаются



Таблица 5. Установочная последовательность для Оу4 = О

как результат пересечения векторов сiI, сi*, сi. Установочная последова­тельность приведена в табл. 5. Время синтеза одного вектора на ЭВМ ЕС-1022 составляет 0,1-2,0 с.



7. Заключение

Рассмотренный метод положен в основу алгоритма синтеза тестов. Алгоритм реализован в виде программы на языке ФОРТРАН-4. Програм­ма "включена в состав системы автоматизированного проектирования кон­тролирующих тестов на базе ЭВМ ЕС-1022. При помощи системы было проведено проектирование тестов для 200 плат процессора ЭВМ ЕС-1060. В зависимости от сложности платы число наборов теста изменяется в пре­делах от 2 до 1700. Время, затраченное на проектирование теста, изменя­лось от нескольких секунд до 8 часов.

В качестве примера приведем данные по модели и тесту для платы, логическая схема которой состоит из 542 вентилей и имеет 45 входов и 46 выходов. В схеме выделено 53 последовательностных и 82 комбинацион­ных макроэлемента. Затраты машинного времени на построение модели составили 15 мин. Полный список одиночных константных неисправностей включает в себя 3190 неисправностей. Синтезированный контролирующий тест состоит из 361 сегмента, 1610 наборов. Максимальное число наборов в сегменте — девять. Затраты машинного времени на синтез теста соста­вили шесть часов.

ЛИТЕРАТУРА


1. Звягин В. Ф., Голыничев В. Н., Немолочнов О. Ф. Метод синтеза корректных по­следовательностей для логических схем.— Автоматика и вычислительная тех­ника, 1979, № 5, с. 33-40.

2. Звягин В. Ф., Немолочнов О. Ф. Сокращение перебора при решении установочной



задачи для логических схем с глобальными обратными связями.— Автоматика и вычислительная техника, 1978, № 4, с. 28-32.

  1. Миллер Р. Теория переключательных схем. Т. 1. М.: Наука, 1970.

  2. Немолочнов О. Ф., Усвятский А. Е. Метод анализа состязаний по кубическим покрытиям логических схем.— Автоматика и телемеханика, 1977, № 2, с. 126-135.

5. Немолочнов О. Ф. Анализ и устранение критических состязаний сигналов при синтезе тестовых последовательностей.- Автоматика и телемеханика, 1976 № 11, с. 173-181.

Поступила в редакцию 30.1Х.1980




Жениться стоит только на женщинах, которым нельзя доверять в браке. Чезаре Павезе
ещё >>