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

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

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

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

А₀ – 0 0 – {A₀,A₅}

A₁ – 4 1 – {A₈}

A₂ – 2 2 – {A₂}

A₃ – 4 3 – {A₄}

A₄ – 3 4 – {A₁, A₃, A₆, A₈, A_k}

А₅ – 0

А₆ – 4

А₇ – 4

А₈ – 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, а вторая команда ГСА А₁ – цвет 4. Счетчик цветов при переходе А_о ® D ® A₁ примет значение 2. Следовательно, в свободных разрядах данной вершины D должно стоять число 2, чтобы цвет А₁ совпадал со значением счетчика цветов. Обозначим эту сдвигающую вершину D+2. Аналогично проставлены значения сдвига для других диагностических вершин.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

W₀_₁ – 01011110 = 101

W₁_₂ – 01100011 = 100

W₂_₃ – 11111100 = 110

W₃_₁ – 10001101 = 100

W₂_₅ – 00011001 = 011

W₅_₈ – 10110110 = 101

W₆_₂ – 01101111 = 110

W₂_₄ – 01010010 = 011

W₅_₆ – 01110110 = 101

W₈_₂ – 10101111 = 110

W₄_₅ – 01001011 = 100

W₆_₇ – 10100110 = 100

W₂__k – 10000111 = 100

W₇_₂ – 11001001 = 100

W₃_₇ – 00110101 = 100

W₀ = 101

По рис. 4.39 видно, что для вершины схождения А₅ в обеих парах со­седней будет команда А₄. Для вершины схождения А₇ вес перехода А₃ ® А₇ равен весу перехода А₆ ® А₇, так что в эти пары вставлять диагностиче­скую вершину не требуется. Для вершины схождения А₂ вес перехода А₆ ® А₂ равен весу перехода А₈ ® А₂, но отличается от веса перехода А₇ ® А₂, поэтому в пару А₇–А₂ вставляется диагностическая вершина D, которая подбирается так, чтобы вес перехода D ® А₂ был также равен 110.

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

S1

S2

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

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

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

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

,

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

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

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

.

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

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