Методы контроля, реализующие раскраску команд

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

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

Метод контроля, использующий раскраску без учета ????структуры команд

Данный метод изложен в работе [3]. Модели дефекта выбраны следующие:

– переход команды в команду Ki/Kj, т.е. соответствующий дефект механизма хранения в нашей модели;

– пропадание команды, определяемое нулями по всем разрядам команды, т.е. дефект механизма дешифрации Ki/0 в нашей модели;

– искажение команды, определяемое как одиночная неисправность в двоичном представлении команды, т.е. дефект механизма хранения.

Каждая программа представляется, как указывалось выше, граф-схемой алгоритма.

На первом этапе производится раскраска ГСА. Выбирается m – количество цветов – в зависимости от требуемой вероятности обнаружения дефектов перехода. Каждой команде присваивается цвет так, чтобы по любому пути ГСА соблюдалась правильная последовательность цветов от 0 до m–1.

Если последовательность нарушается, то в ГСА вводятся диагностические вершины. В данном методе в качестве диагностической вершины может выступать любая команда, не нарушающая выполнения программы (типа NOP – пустой команды, СМР – команды сравнения и т.д.).

Пример 4.4. На рис. 4.31 представлена раскрашенная ГСА рис.

4.30 при m = 5, цвета записаны сверху у обозначения команды. Буквой D обозначены введенные диагностические вершины.

Рис. 4.31. Пример раскрашенной ГСА

Преобразованная программа приведена ниже:

CLR AX M1: MOV CX,2

MOV BX,1 M5: CMP C,4

CMP C,2 ADD C,4

JNE M1 M3: CMP C,10

CMP C,5 JNE M6

JNE M3 CMP C,2

CLR DX ; D4 CMP C,4

NOP ; D0 JMP M5

MOV BX,1 M4: CMP AX,1 ; D1

CMP C,2 M6: CMP C,2

CLR CX ; D3 RET

CMP C,4

JNE M2

INC BX

JMP M4

DEC BX

JMP M4

Команды, соответствующие введенным диагностическим вершинам, помечены комментарием. В качестве диагностических вершин введены команды NOP, CMP AX,1 INC DX, CLR CX, не влияющие на ход выполнения программы. На втором этапе в каждую команду дополнительно вводится еще один избыточный разряд, дополняющий ее двоичное представление до четности.

Пример 4.5. Ниже представлена двоичная запись команд раскрашенной ГСА, представленной на рис 4.30, с избыточными разрядами, включающими цвет от 0 до 4 и дополнение до четности:

Рандомно подобранные статьи с сайта:

3 ГЛАВНЫЕ ПРИЧИНЫ ЗАНИМАТЬСЯ ТВОРЧЕСТВОМ | Раскраска по номерам “Цветовой квест”


Похожие статьи:

admin