СИНТЕЗ СХЕМ ВСТРОЕННОГО КОНТРОЛЯ ПО МЕТОДУ ЛОГИЧЕСКОГО ДОПОЛНЕНИЯ С ПРИМЕНЕНИЕМ ВЗВЕШЕННЫХ КОДОВ С СУММИРОВАНИЕМ
Д.В. Ефанов, д-р техн. наук,
А.В. Пашуков
Аннотация
встроенный контроль код цифровой
Исследуются особенности применения взвешенных кодов с суммированием при организации схем встроенного контроля для цифровых вычислительных устройств по методу логического дополнения. Описан сам метод логического дополнения. Дается краткий обзор применения равномерных блочных кодов для синтеза схем встроенного контроля по методу логического дополнения. Отмечено, что ранее в этих целях не применялись взвешенные коды с суммированием. При их использовании можно для цифрового устройства с известной структурой подбирать значения весовых коэффициентов в процессе определения способа кодирования. В статье описаны особенности выбора весовых коэффициентов, а также шаги синтеза схемы встроенного контроля по методу логического дополнения. Применение взвешенных кодов с суммированием позволяет синтезировать полностью самопроверяемые цифровые устройства даже в тех случаях, когда этого невозможно добиться путем применения других кодов, - например, Бергера или Боуза-Лина, а также стандартного метода дублирования.
Ключевые слова: схема встроенного контроля, метод логического дополнения, взвешенные коды с суммированием, синтез самопроверяемых цифровых устройств, контроль вычислений.
Введение
Современные цифровые устройства и вычислительные системы снабжаются развитым диагностическим обеспечением, что позволяет выявлять неисправности, возникающие в их компонентах в процессе эксплуатации, а также фиксировать и парировать ошибки в вычислениях [1 - 3]. В процессе проектирования цифровых устройств обращают внимание на контролепригодность их структур, возможности самоконтроля и самопроверки в процессе выполнения своих функций, а также наделения их свойствами парирования ошибок и отказоустойчивости [4 - 7]. В этой связи важнейшим подходом является снабжение устройств, их блоков и узлов самопроверяемыми схемами встроенного контроля (СВК) [8]. Они реализуются с применением методов теории информации и кодирования [9, 10].
Известно два основных метода реализации СВК с применением избыточного кодирования [9].
Первый метод реализует идею вычисления (или дополнения) контрольных разрядов и подразумевает следующее. Выходы объекта диагностирования F(x) отождествляются с информационным вектором <fmfm-1... f2f1> длиной m. В СВК эти выходы дополняются контрольными разрядами, формируемыми блоком контрольной логики G(x). Его выходы отождествляются с контрольным вектором <gk gk-1... g2 g1> длиной k. Между выходами блоков F(x) и G(x) на этапе проектирования СВК устанавливается однозначное соответствие путем определения принадлежности формируемых информационных и контрольных векторов какому-либо блочному равномерному коду. Контроль этого соответствия в процессе эксплуатации самопроверяемого устройства осуществляется с использованием полностью самопроверяемого тестера TSC (totally self-checking checker) [11, 12]. В качестве блочного равномерного кода может выступать любой из известных кодов [13]. При этом могут использоваться и неразделимые коды. В этом случае функции <gk gk-1... g2 g1> дополняют функции <fm fm-1... f2 f> до кодового слова неразделимого кода, - например, равновесного кода [14].
Типовыми структурами организации СВК являются структура дублирования и контроля вычислений по паритету. В первом случае применяется один из кодов с повторением [13], во втором - код паритета [10]. Часто СВК реализуется с применением кодов с суммированием [15, 16]. Как показано в большом количестве работ (например, в обозначенных монографиях), в случае использования кодов с суммированием удается учитывать структуру объекта диагностирования и выбирать наименее сложный с позиции структурной избыточности конечного устройства вариант организации СВК.
Второй метод организации СВК связан не с формированием контрольного вектора с помощью контрольных функций, а с коррекцией сигналов от объекта диагностирования. Этот метод является развитием метода контроля по паритету [17] и получил название «метод логического дополнения» [18].
Метод логического дополнения исследовался учеными в основном с позиции применения неразделимых кодов, а также особых способов представления функций. Например, в [18 - 23] описываются особенности синтеза СВК по методу логического дополнения с применением равновесных кодов, а в [24 - 27] - с преобразованием функций в самодвойственные. Использованию разделимых кодов при синтезе СВК по методу логического дополнения посвящено не так много работ [28, 29].
Данная же работа освещает особенности применения класса взвешенных кодов с суммированием [30, 31] при организации СВК по методу логического дополнения.
Постановка задачи
Рассматривается структура СВК, реализуемая по методу логического дополнения. Задача состоит в исследовании особенностей применения взвешенных кодов с суммированием при синтезе СВК по методу логического дополнения с обеспечением обнаружения полного множества ошибок на выходах объекта диагностирования. Требуется установить закономерности взвешивания разрядов информационного вектора и фиксируемого значения модуля для построения полностью самопроверяемой СВК.
Метод логического дополнения
Метод логического дополнения подразумевает применение коррекции сигналов от объекта диагностирования F(x) в СВК для формирования кодовых слов заранее выбранного равномерного блочного кода. В структуре самопроверяемого устройства, реализуемого по методу логического дополнения, выделяются четыре функциональных блока (рис. 1). Блок F(x) является исходным устройством и объектом диагностирования, для которого контролируются вычисления. Остальные три блока образуют СВК. Блок G(x) является блоком контрольной логики и вычисляет значения контрольных функций дополнения, которые подаются на входы блока коррекции сигналов. С другой стороны, на его входы подаются сигналы от объекта диагностирования. Блок коррекции сигналов образован двухвходовыми элементами сложения по модулю M = 2 (элементами XOR). На входы каждого элемента XOR подключаются одноименные выходы , m от блоков основной и контрольной логики.
Преобразования осуществляются по правилу:
Рис. 1 Обобщенная структура организации СВК по методу логического дополнения
На выходах блока коррекции сигналов формируется кодовое слово заранее выбранного кода. Принадлежность заданному коду формируемого вектора контролируется с помощью схемы самопроверяемого тестера TSC. Он синтезируется в парафазной логике и снабжается двумя выходами, на которых формируется парафазный сигнал об отсутствии ошибок в вычислениях. Непарафазность сигнала свидетельствует о наличии ошибок в вычислениях.
При организации СВК по методу логического дополнения могут применяться любые блочные равномерные коды. Наиболее изучены при построении СВК по методу логического дополнения неразделимые коды. Глубоко исследованными являются вопросы использования равновесных кодов «1 из 3» [18, 20, 22], «1 из 4» [19, 20], «2 из 4» [32], «1 из 5» [33], «2 из 5» [34] при синтезе СВК по методу логического дополнения. Гораздо меньшее количество работ посвящено применению разделимых кодов для синтеза СВК по методу логического дополнения. Это связано с большей сложностью организации самопроверяемых структур по разделимым кодам, поскольку они не обнаруживают гораздо большее количество ошибок в кодовых словах, чем те же равновесные коды [15, 16]. Среди известных работ по применению разделимых кодов при синтезе СВК по методу логического дополнения отметим следующие. В [28] предлагается синтезировать СВК на основе использования базовой структуры, позволяющей контролировать группу из пяти выходов с помощью кода Бергера с тремя информационными разрядами и двумя контрольными разрядами. Выходы устройства F(x) покрываются группами по пять выходов в каждой. Каждая такая группа контролируется на основе кода Бергера, а выходы отдельных подсхем контроля объединяются на входах самопроверяемого компаратора. В [29] предложено использовать коды Бергера и Боуза-Лина для синтеза СВК по методу логического дополнения для единой группы выходов устройства. Установлены условия, при которых можно уменьшить число потенциальных ошибок в кодовых словах за счет выделения групп зависимых и независимых выходов. Ряд работ [35, 36] посвящен изучению характеристик обнаружения ошибок кодами Бергера и Боуза-Лина в кодовых словах при использовании данных кодов в задачах синтеза СВК по методу логического дополнения.
Более широким классом разделимых кодов является класс взвешенных кодов с суммированием. Такие коды строятся путем приписывания весовых коэффициентов в виде заранее выбранных натуральных чисел, а затем суммирования весовых коэффициентов значащих разрядов для получения суммарного веса W информационного вектора [30]. Взвешенные коды с суммированием применяются при контроле вычислений и при синтезе СВК для цифровых устройств [37, 38]. Рассмотрим особенности их применения при синтезе СВК по методу логического дополнения.
Использование взвешенных кодов с суммированием при синтезе схем встроенного контроля по методу логического дополнения
Введем обозначение для взвешенных кодов с суммированием: WMm- коды, где m - длина информационного вектора; M - значение модуля для подсчета суммарного веса информационного вектора; W - принадлежность кода к классу взвешенных (weight-based code). При построении кода в контрольный вектор записывается значение наименьшего неотрицательного вычета суммарного веса информационного вектора по модулю M:
Как известно из результатов исследований характеристик обнаружения ошибок WMnj-кодами [16], некоторая доля ошибок в информационных векторах ими не обнаруживается. Несмотря на это, при организации СВК можно использовать специальные приемы при построении кода для обнаружения любых сочетаний искажений на выходах устройств. Кроме того, можно использовать данные о структуре объекта диагностирования F(x) при выборе способа взвешивания разрядов. Покажем это на примере.
Прежде всего, будем использовать следующие ключевые характеристики ЖМт-кодов. Во-первых, если взвешивать разряды информационного вектора весовыми коэффициентами из множества {20, 21,..., 2q}, q<m-1, то строящийся код будет обнаруживать пачки из ошибок в разрядах [39]. Во- вторых, можно минимизировать число контрольных разрядов в коде с учетом выбора модуля для подсчета суммарного веса W информационного вектора - числа WM=W(modM). Ни одно из значений весовых коэффициентов не должно быть кратно значению модуля М [16]. Целесообразно выбирать значение модуля из множества {20, 21,..., 2p},p > q. В этом случае гарантированно будет выполнено условие отсутствия кратных модулю значений весовых коэффициентов.
Рис. 2 Структура организации СВК по методу логического дополнения до WMm-кодов. Данное устройство снабжено четырьмя входами x1, x2, x3, x4 и пятью
В левой части рис. 2 для примера приведено комбинационное устройство F(x). выходами fi, fi, /з, fa, /5. Имеется 11 логических элементов. Структура устройства такова, что у него имеются пары зависимых выходов. Пусть рассматривается модель одиночной константной неисправности выходов логических элементов в структуре устройства F(x) (stuck-at faults). Если выходы зависимы, то ошибка на выходе логического элемента, связанного путями с этими выходами, может транслироваться на все выходы при подаче на входы устройства какой-либо из конкретных входных комбинаций. Проверить это можно с помощью следующего условия для каждой пары выходов [10]:
где yY - функция, реализуемая на выходе логического элемента GY, связанного путями с выходами fa и fb.
Если произведение производных равно нулю, то не существует входных комбинаций, на которых ошибка транслируется на оба выхода, и они являются функционально независимые. В противном случае выходы являются зависимыми. Условие (3) проверяется для всех пар функций (их число сП, n - число выходов устройства) и для всех структурно зависимых выходов (выходов, которые связаны путями с общими элементами).
Если для группы из трех выходов оказываются попарно независимыми все выходы, то вся группа является группой независимых выходов и т.д.
Учитывая деление выходов на зависимые и независимые, можно приписывать разрядам соответствующие весовые коэффициенты. Если пара выходов зависима, то нужно взвесить их двумя различными числами из множества {20, 21,..., 2q}, q < m - 1.
Шаг 1. Выделим выходы устройства F(x), которые не связаны ни с какими другими выходами. Такой выход в рассматриваемом примере один - f5. Его целесообразно сделать преобразуемым и отнести к выходам, которые формируют контрольные разряды WMm-кода [29]. Остальные выходы будут формировать информационные разряды кода. В рассматриваемом примере это /ь../4.
Может так оказаться, что не найдется выходов, независимых от остальных выходов устройства. В этом случае могут использоваться специальные схемотехнические приемы организации контроля вычислений. Например, использование резервирования в структуре объекта диагностирования с выделением одного независимого выхода, дополнительный контроль вычислений по иному диагностическому параметру, использование контроля по группам с построением нескольких СВК и др. [15, 16].
Шаг 2. Требуется определить числа, которыми будут взвешиваться разряды информационного вектора. Для этого анализируются выходы. Видно, что пара выходов f и f2 - это пара зависимых выходов. Взвесим их числами w1 = 20 и w2 = 21. Пара выходов f и f тоже является парой зависимых выходов. Так как выходы f1 иf независимы, то можно взвесить выход f3 числом w3 = 20. Ошибки на выходахf и f3 одновременно не возникают, а значит, можно считать эти выходы равнозначными. Далее, выходы f3 и f4 зависимы. Однако f4 не является зависимым с остальными выходами, а значит, ему можно приписать весовой коэффициент w4 = 21.
Таким образом, разряды взвешиваются числами [w4, w3, w2, wi] = = [21, 20, 21, 20].