Раскраска без внесения в команду избыточных разрядов

 

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

На первом этапе по структуре команды определяется ее цвет как сумма единиц по модулю m в двоичном представлении команды.

Пример 4.7. Ниже приведены цвета команд программы, описанной в примерах 4.2 и 4.3:

 

А0 – 0 0 – {A0,A5}

A1 – 4 1 – {A8}

A2 – 2 2 – {A2}

A3 – 4 3 – {A4}

A4 – 3 4 – {A1, A3, A6, A8, Ak}

А5 – 0

А6 – 4

А7 – 4

А8 – 1

Аk – 4

На втором этапе производится раскраска ГСА с помощью диагно­стических вершин так, чтобы цвета правильно чередовались.

Пример 4.8. На рис. 4.36 приведена ГСА (см. рис. 4.30), раскрашен­ная с учетом цветов, присвоенных командам в примере 4.7. Контроль осу­ществляется так же, как и в предыдущем случае, но теперь для определения цвета не требуются избыточные разряды. Поэтому в СВК не будет второго сумматора по модулю m и входа Кизб (блоков, об­веденных пунктиром на рис. 4.34).

Изменятся следующие характеристики:

– Kизб сведено к 0, так как избыточные разряды отсутствуют;

– верхняя граница tизб не изменится, но очевидно, что для конкрет­ных ГСА в большинстве случаев tизб увеличится по сравнению с предыдущим методом.

Пример 4.9. tизб для раскрашенной ГСА на рис. 4.31 равно 3/17, то­гда как tизб для раскрашенной ГСА рис. 4.36 (см. ниже) равно 37/17. Как видно из примера, tизб увеличилось на порядок, при этом быстродействие программы снизилось в 3 раза.

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

Пример 4.10. На рис. 4.37 представлена ГСА (см. рис. 4.30), раскра­шенная с помощью сдвигающих диагностических вершин. Первая команда ГСА Ао в соответствии с примером 4.7 имеет цвет 0, а вторая команда ГСА А1 – цвет 4. Счетчик цветов при переходе Ао ® D ® A1 примет значение 2. Следовательно, в свободных разрядах данной вершины D должно стоять число 2, чтобы цвет А1 совпадал со значением счетчика цветов. Обозначим эту сдвигающую вершину D+2. Аналогично проставлены значения сдвига для других диагностических вершин.

ССВК представлена на рис. 4.38. Сумматор по модулю m определяет цвет команды. Дешифратор определяет, является ли команда диагностиче­ской вершиной: если да, то он блокирует сравнение цветов команды и эта­лона и увеличивает счетчик цветов на величину, записанную в диагности­ческую вершину; если нет, то дешифратор ждет следующую команду. Если команда не является диагностической вершиной, то сравнивается цвет, подсчитанный по структуре команды, и цвет, получившийся к дан­ному моменту в счетчике цветов. По результатам сравнения определяется правильность выбранной команды.

 


Рис 4.36. ГСА, раскрашенная с учетом предварительного присвоения цветов


Рис. 4.37. ГСА, раскрашенная с помощью сдвигающих диагностических вершин

Пример 4.11. Для ГСА, представленной на рис. 4.37, tизб равно 16/17.

S2
S1

Рис. 4.38.ССВК для метода контроля с помощью сдвигающих диагностических вершин

 

 

Методы контроля механизмов дешифрации и хранения ко­манд     с помощью веса перехода

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

Весом перехода W будем называть количество единиц в сумме по модулю двух соседних по ГСА команд. Под соседними будем понимать команды, соединенные на ГСА ребром.

Метод контроля заключается в следующем. В каждой команде в из­быточных разрядах записывается вес перехода по отношению к предыду­щей команде. Для начальной команды определяется вес перехода по отно­шению к нулевой комбинации. При работе программы предыдущая ко­манда Ki складывается по модулю два с последующей командой Kj и вес перехода сравнивается с эталонным весом, записанным в избыточных раз­рядах команды Kj. Если команда Kj была выбрана неправильно или обна­ружен дефект механизма хранения, вес перехода будет отличаться от эта­лонного. Данный метод контроля также предполагает использование диаг­ностических вершин, так как в ГСА имеются разветвления и схождения.

Вершину, в которую входят два или более направленных ребра, на­зовем вершиной схождения, а соответствующую ей команду по ГСА – ко­мандой схождения.

 

Пример 4.12. Для ГСА (см. рис. 4.30) вершинами схождения будут вершины А5, А7 и А2, которые обведены на преобразованной ГСА (рис. 4.39).

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


Рис. 4.39. ГСА, преобразованная для контроля по весу перехода

 

Пример 4.13. На рис. 4.39 представлена преобразованная схема ГСА (см. рис. 4.30) с введенными диагностическими вершинами. Распределения весов переходов для каждой пары команд приведены ниже:

 

W0_1 – 01011110 = 101

W1_2 – 01100011 = 100

W2_3 – 11111100 = 110

W3_1 – 10001101 = 100

W2_5 – 00011001 = 011

W5_8 – 10110110 = 101

W6_2 – 01101111 = 110

W2_4 – 01010010 = 011

W5_6 – 01110110 = 101

W8_2 – 10101111 = 110

W4_5 – 01001011 = 100

W6_7 – 10100110 = 100

W2_k – 10000111 = 100

W7_2 – 11001001 = 100

W3_7 – 00110101 = 100

W0 = 101

 

По рис. 4.39 видно, что для вершины схождения А5 в обеих парах со­седней будет команда А4. Для вершины схождения А7 вес перехода А3 ® А7 равен весу перехода А6 ® А7, так что в эти пары вставлять диагностиче­скую вершину не требуется. Для вершины схождения А2 вес перехода А6 ® А2 равен весу перехода А8 ® А2, но отличается от веса перехода А7 ® А2, поэтому в пару А7–А2 вставляется диагностическая вершина D, которая подбирается так, чтобы вес перехода D ® А2 был также равен 110.

ССВК для метода контроля по весу перехода представлена на рис. 4.40.

 

S1
S2
Рис. 4.40. ССВК для метода контроля по весу перехода

 

Она работает следующим образом. В регистр команды подаются ос­новные разряды команды. Эти разряды складываются на первом сумма­торе по модулю два с основными разрядами предыдущей команды. Для обработки начальной команды в регистре предыдущей команды преду­смотрен сигнал «сброс», который переводит его в нулевое состояние. Де­шифратор веса определяет вес перехода, который и записывается в регистр веса. Далее на втором сумматоре по модулю два полученный вес сравнива­ется с эталонным, поступающим из регистра эталонного веса, куда запи­сываются избыточные разряды команды. В момент строба результат срав­нения поступает на выход S2, а содержимое регистра команды переписыва­ется в регистр предыдущей команды.

СВК является самопроверяемой, так как любая одиночная констант­ная неисправность приводит к появлению на выходах S1S2 некодового слова {11} {00}, при этом любой выход на рабочих наборах побывает в 0 и 1.

Количество избыточных разрядов

 

,

tизб имеет верхней границей

 

 

где N – первоначальное количество команд в ГСА; kS – число вершин схо­ждения; iS – количество схождений для каждой вершины схождения.

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

 

.

 

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

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