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

 

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

На первом этапе по структуре команды определяется ее цвет как сумма единиц по модулю 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.

S 2 S 1 Рис. 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.

 

S 1

S 2

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

 

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

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

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

 

,

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

 

 

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

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

 

.

 

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

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