Fault Tolerance SynchronousSequential Design for Transient and Intermittent Faults .pdf Самопроверяемая дискретная система, состоящая из самопроверяемого дискретного устройства и самотестируемого детектора кодов, позволяет обнаружить неисправность в момент ее первого проявления на наблюдаемых полюсах в режиме функционирования дискретного устройства. Такие системы используются как для обнаружения не меняющихся во времени неисправностей, так и для кратковременных неисправностей. Эти системы не позволяют неисправности распространиться за пределы самопроверяемого устройства.Часто требуется не только обнаружить неисправность в устройстве, но и сохранить его правильное функционирование. В данной работе предлагается подход к сохранению функционирования дискретного синхронного последовательност-ного устройства в присутствии неисправности и восстановлению его функционирования после прекращения действия неисправности. Рассматривается класс одиночных константных неисправностей на полюсах логических элементов комбинационной составляющей этого устройства и полюсах его d-триггеров, причем, в отличие от работ [1, 2], речь идет только о кратковременных неисправностях. Именно такие неисправности становятся актуальными в рамках новых технологий, приводящих к дальнейшему сокращению размеров элементов схем, снижению уровня питающего напряжения, повышению скорости работы дискретных систем.Устройства, которые маскируют влияние неисправности некоторого класса и способны восстановить свое функционирование после прекращения действия неисправности, будем называть устойчивыми к неисправностям рассматриваемого класса или, для краткости, устойчивыми к неисправностям. Устойчивость к неисправностям, в частности, может быть обеспечена за счет аппаратурной избыточности. Этот подход исследуется в данной работе.Предлагается специальная схема, гарантирующая устойчивость к отмеченным выше неисправностям. Вместо традиционного троирования дискретного устройства и использования схемы голосования, которая обязана быть всегда исправной, устойчивость к неисправностям обеспечивается за счет самопроверяемой дискретной системы, к которой добавляются дополнительные подсхемы. В самопроверяемой дискретной системе в условиях действия кратковременных неисправностей детектор может быть несамотесируемым. Такие детекторы, как правило, проще, чем самотестируемые. Ни к одной из подсхем не предъявляется требование быть всегда исправной, это выгодно отличает предлагаемый подход от троирования. Проведенные эксперименты показали, что рассматриваемые в работе устойчивые к неисправностям схемы требуют, как правило, меньших аппаратурных затрат, чем троирование.1. Схема, устойчивая к неисправностямИтак, пусть задано описание функционирования синхронного автомата, например STG (State Transition Graph)-описание. Требуется построить схему, обеспечивающую заданное функционирование и устойчивую к неисправностям.Сначала необходимо построить самопроверяемое синхронное последователь-ностное устройство для введенных ранее одиночных и кратковременных неисправностей. С этой целью предлагается выполнить кодирование состояний равновесным кодом, а затем заменить в полученных кодовых словах нулевые значения компонент на символ «-» (неопределенное значение). С целью сокращения аппаратурных затрат предпочтение отдается кодовым словам меньшего веса (кодовым словам с меньшим числом единичных компонент). Далее выполняется кодирование словами равновесного кода или кода Бергера выходов устройства. Поскольку в STG-описании выходы уже закодированы, то для приведения имеющихся выходных слов к кодовым словам, как правило, необходимо расширить множество выходных полюсов. Указанное кодирование - одно из средств обеспечения монотонного проявления неисправности в самопроверяемом синхронном последовательностном устройстве. Под монотонным проявлением понимается следующее. При проявлении неисправности на наблюдаемых полюсах значения сигналов некоторого подмножества этих полюсов могут смениться все с 1 на 0 или все с 0 на 1. На различных тестовых наборах для одной и той же неисправности возможны различные типы монотонного проявления неисправностей.Заметим, что при использовании равновесных кодов, как для кодирования состояний, так и для кодирования выходных слов, можно обойтись одним детектором равновесных кодов для выходов и линий обратных связей самопроверяемого синхронного последовательностного устройства. При использовании кодов Бергера для кодирования выходных слов потребуется два отдельных детектора; один для равновесных кодов, другой - для кодов Бергера. Детекторы, отличая кодовые слова от некодовых, обнаруживают тем самым монотонное проявление неисправности.Пусть функционирование синхронного автомата задано STG-описанием, представленным в табл.1.В результате кодирования состояний и выходов равновесными кодами получаем табл. 2Заменив в кодах состояний символ 0 на символ «-», получим табл. 3.Табл. 2 (3), представляющая систему частичных булевых функций, одновременно задает систему F полностью определенных функций, если единичные компоненты векторов состояний и векторов, представляющих выходные кодовые слова, интерпретировать как характеристики интервалов, заданных табл. 2 (3).Таблица 2Описание автомата системой частичных булевых функцийОписание автомата системой частичных булевых функций, монотонных по внутренним переменнымБолее того, система, представленная табл. 3, является частично монотонной по внутренним переменным. Использование частично монотонных систем позволяет сократить аппаратурные затраты на комбинационную составляющую самопроверяемого последовательностного устройства при синтезе комбинационной схемы в базисе И, ИЛИ, НЕ И, НЕ ИЛИ, НЕ с применением двухуровневого или многоуровневого факторизационного метода синтеза [3, 4] к таким системам. Факторизационные методы синтеза, примененные к частично монотонным системам, гарантируют монотонное проявление неисправностей в самопроверяемом последо-вательностном устройстве.Схема, устойчивая к неисправностям, представлена на рис.1. Схема строится в предположении, что состояния и выходные слова закодированы равновесными кодами.Самопроверяемое синхронное устройство ССУ,ylm+u...yliу 13[7Самопроверяемое синхронное устройство ССУ23иzi"...,z/'схем Ki и K2. Эта подсхема имеет s+p выходов, то есть выходы элементов И являются выходами схемы.Выходы подсхемы ИЛИ являются входами подсхемы детектора кодов (ДК-подсхемы), являющейся детектором равновесных кодов. ДК-подсхема имеет два выхода: м1,м2.Выходы подсхемы И являются входами подсхемы мультиплексора. Мультиплексор MX связывает линииyi', ym'; zi', zp' с линиямиyi, ym; zi, zp, если на входах ui и u2 мультиплексора достигаются значения 01 (10). Иначе мультиплексор связывает линииyi'', . „, ym''; zi'', . „, zp''c линиями_yi, . „, ym; zi, . „, zp.Будем иметь в виду, что yi, ., ym являются выходами синхронного дискретного устройства, устойчивого к неисправностям, zi, ..., zp - его линии обратных связей, а xi, ..., xn - входы этого устройства.Отметим, что комбинационные подсхемы Ki,K2 вместе с d-триггерами и линиями обратных связей образуют идентичные самопроверяемые синхронные устройства ССУ1, ССУ2 соответственно. Они обеспечивают монотонное проявление допустимых для этих устройств неисправностей на выходах комбинационных подсхем. В качестве допустимых неисправностей рассматриваются одиночные константные неисправности на полюсах логических элементов комбинационной составляющей, полученной одним из вышеупомянутых методов синтеза, а также одиночные константные неисправности на полюсах d-триггеров синхронного устройства.Допустимыми неисправностями подсхем ИЛИ (И) являются одиночные константные неисправности на полюсах составляющих эти подсхемы элементов. Они проявляют себя монотонным образом.Допустимые неисправности детектора кодов определяются методами его синтеза и элементной базой и также проявляют себя монотонным образом. В качестве допустимых неисправностей могут быть одиночные константные неисправности на полюсах логических элементов.Неисправности мультиплексора могут привести к замене связей некоторых линий из ряда yi', ym'; zi', zp' на одноименные линии ряда yi'', ym''; zi '', ., zp''. Допускаются также одиночные константные неисправности на линиях схемы рис. 1, кроме линий xi, ., xn; yi, ., ym; zi, ., zp. Если линия разветвляется, то неисправность имеет место на одной из ветвей линии.Покажем, что предлагаемая на рис. 1 схема продолжает исправно функционировать при появлении одной из вышеперечисленных неисправностей. Заметим, что неисправность на одной из линий исключает неисправность подсхем схемы Рис.1. При исправности линий возможна одна неисправность в одной из подсхем. Здесь всюду речь идет о кратковременных или перемежающихся неисправностях, длительность которых не превышает нескольких тактов. Считается, что в присутствии такой неисправности невозможно появление второй кратковременной или перемежающейся неисправности. В условиях таких ограничений на неисправности вместо самотестируемых детекторов кодовых слов можно использовать неса-мотестируемые детекторы.2. Исследование схемы на устойчивость к неисправностямОбозначим через Уд множество допустимых неисправностей несамотестируе-мого детектора кодов. Пусть Уили , Уи - множества допустимых неисправностей подсхем ИЛИ, И соответственно. У1,У2 - множества неисправностей подсхемССУ1,ССУ2; VL - множество неисправностей линий подсхем. Обозначим через У объединение всех этих множеств: У = Vi и У2 и Уд и Ушш и Уи и VL . Покажем, что схема устойчива к любой неисправности v из У.Рассмотрим неисправность v из У1 (У2). Напомним, что подсхема Ki(K2) реализует систему F из s+p булевых функций от n+p переменных, частично монотонную по внутренним переменным. Пусть ai, а2 - булевы векторы размерности n+p, представляющие значения входных переменных подсхемы Ki(K2), а ßi,ß2 - булевы векторы размерности m + _p , представляющие значения выходных переменных подсхемы Ki(K2), F(ai) = ßi, F(a2) = ß2.В работе [3, 4] показано, что неисправность v из У1 монотонно проявляется на выходах и линиях обратных связей самопроверяемого синхронного последова-тельностного устройства (на наблюдаемых полюсах схемы Ki (K2)). Там же показано, что эта неисправность ведет себя либо как А-неисправность, либо как В-неисправность, то есть сохраняет тип монотонного проявления на каждом из своих тестовых наборов.Обозначим через Fv систему булевых функций, реализуемую схемой Ki(K2) в присутствии неисправности v. Тогда для А-неисправности и любого тестового набора а имеем: Fv(a)< F(a); для В-неисправности и любого тестового набора а имеем: F(a)< F (а).Теорема 1. Неисправность v из У1(У2) сохраняет корректное поведение синхронного последовательностного устройства.Доказательство. В случае А-неисправности в одной из комбинационных подсхем Ki, K2 выходы подсхемы ИЛИ соответствуют реакции другой (исправной) комбинационной схемы. Это значит, что на выходах детектора кодов достигаются значения 01 (10) и на выходах мультиплексора оказываются корректные значения выходных и внутренних переменных синхронного последовательностного устройства. В случае В-неисправности в одной из комбинационных подсхем Ki,K2 происходит увеличение веса кодового слова на выходах подсхемы ИЛИ, что приводит к появлению на выходах детектора кодовых слов 00 (11). В то же время выходы схемы И представляют корректное кодовое слово исправной комбинационной схемы. Это значит, что на выходах мультиплексора достигаются корректные значения выходных и внутренних переменных синхронного последовательност-ного устройства. Будем иметь в виду, что константная неисправность на входе или выходе d-триггера проявляет себя как кратная константная неисправность на входах элементов комбинационной подсхемы Ki (K2), связанных с выходом d-триггега, оставаясь по типу проявления А-неисправностью для константы 0 на входе или выходе триггера и В-неисправностью для константы 1 на входе или выходе триггера. С прекращением действия неисправности обе комбинационные подсхемы функционируют исправно, поскольку на входы комбинационных схем, сопоставляемые линиям обратных связей, всегда поступают корректные сигналы. Теорема доказана.Будем иметь в виду, что в самопроверяемых системах обычно используются самотестируемые детекторы кодовых слов. Под этим понимается, что для всякой допустимой в детекторе неисправности существует тестовый набор среди множества кодовых слов детектора. Это свойство, как правило, нелегко обеспечить, в особенности, если речь идет о конкретном подмножестве кодовых слов, достижимых на выходах соединенной с детектором комбинационной подсхемы.Теорема 2. Неисправность v из Уд сохраняет корректное поведение синхронного последовательностного устройства.Доказательство. Из способов построения детекторов следует, что при поступлении на его входы корректных кодовых слов и при неисправности детектора (речь, как обычно, идет о допустимых для него неисправностях) на выходах детектора (в ответ на входное кодовое слово, являющееся тестовым набором для возникшей неисправности), достигаются значения 00 или 11. В силу исправности остальных подсхем схемы рис. 1 на выходах мультиплексора оказываются корректные значения синхронного последовательностного устройства. Если тестовый набор еще не поступил в присутствии неисправности и, следовательно, на выходах детектора достигаются значения 01 (10), то на выходах мультиплексора также достигаются корректные значения синхронного последовательностного устройства. Если действие неисправности прекратилось до появления тестового набора на входах ДК, то ДК становится исправным и синхронное последовательностное устройство продолжает корректную работу. В несамотестируемом детекторе возможно, что некоторая допустимая неисправность не проявляется на кодовых словах, поступающих на его входы, а проявляется лишь на некодовых словах. Тогда на выходах детектора достигаются комбинации 01 (10) и, следовательно, синхронное последовательностное устройство исправно функционирует. Поскольку следующая неисправность в любой из подсхем схемы рис.1 может появиться только по прекращении действия предыдущей неисправности, то искажение кодового слова на входах детектора, вызванное следующей неисправностью, приведет к сигналам 00 (11) на выходах детектора и к исправному функционированию синхронного последовательностного устройства. Появление очередной неисправности в детекторе приведет к уже рассмотренной ситуации, поскольку действие предыдущей неисправности прекратилось. Теорема доказана.Следствие. При действии кратковременных или перемежающихся неисправностей нет необходимости использовать самотестируемые детекторы в системе самопроверяемое синхронное последовательностное устройство - детектор кодов.Будем иметь в виду, что схемная реализация несамотестируемых детекторов кодовых слов часто оказывается более простой, чем схемная реализация самотестируемых детекторов и что самотестируемых детекторов для любого заданного подмножества кодовых слов, поступающих на детектор с выходов самопроверяемой схемы, насколько нам известно, вообще не существует.Теорема 3. Неисправность v из УиЛи сохраняет корректное поведение синхронного последовательностного устройства.Доказательство. Из построения подсхемы ИЛИ следует, что неисправность константа 0 на некотором полюсе элемента подсхемы проявляет себя как А-неис-правность, а неисправность константа 1 проявляет себя как В-неисправность. Это значит, что неисправность может привести к поступлению некодового слова на входы исправного детектора кодов. Тогда на выходах детектора кодов достигается либо комбинация 00, либо 11. В результате выходы исправной подсхемы K2 поступают на выходы мультиплексора и синхронное последовательностное устройство продолжает корректное функционирование. Возможно, что неисправность не проявится на выходах подсхемы ИЛИ вплоть до своего исчезновения. Тогда синхронное последовательностное устройство выполняет корректное функционирование при условии, что на выходах детектора кодов достигаются значения 01 ,10. Теорема доказана.Теорема 4. Неисправность v из Уи сохраняет корректное поведение синхронного последовательностного устройства.Доказательство. Из построения подсхемы И следует, что неисправность константа 0 на некотором полюсе элемента схемы проявляет себя как А-неисправ-ность, а неисправность константа 1 проявляет себя как В-неисправность. Это значит, что неисправность может привести к появлению некодового слова на выходах подсхемы И. В силу исправности подсхем Ki, K2, подсхемы ИЛИ и детектора кодов синхронное последовательностное устройство сохраняет корректное функционирование. Корректное функционирование будет также продолжаться после прекращения действия неисправности. Теорема доказана.Теорема 5. Неисправность v из VL сохраняет корректное поведение синхронного последовательностного устройства.Доказательство. Рассмотрим неисправность константа 1 на линии, связывающей выход подсхемы Ki с одноименными входами подсхем ИЛИ, И. Эта неисправность может привести к искажению кодового слова на выходах подсхемы ИЛИ и, следовательно, к достижению на выходах детектора значений 00 (11). В силу исправного функционирования подсхемы И на выходах мультиплексора достигаются корректные значения, и синхронное последовательностное устройство исправно функционирует. В случае неисправности константа 0 на той же линии на выходах схемы ИЛИ реализуется кодовое слово, а на выходах подсхемы И кодовое слово может быть искажено. Последнее обстоятельство не влияет на корректное функционирование синхронного последовательностного устройства.Рассмотрим неисправность константа 1 на линии, связывающей выход подсхемы K2 с одноименными входами подсхем ИЛИ, И. Эта неисправность может привести к искажению кодового слова на выходах подсхемы ИЛИ. Тогда на выходах детектора достигается комбинация 00 (11). В силу исправности подсхем Ki, K2 на выходах подсхемы И реализуется кодовое слово, следовательно, синхронное последовательностное устройство исправно функционирует. В присутствии неисправности константа 0 на той же линии на выходе подсхемы ИЛИ реализуется кодовое слово, а на выходе подсхемы И кодовое слово может быть искажено. Последнее обстоятельство не влияет на корректное функционирование синхронного последовательностного устройства.Неисправность константа 1(0) на одном из выходов подсхемы ИЛИ приводит к появлению на выходах детектора кодов значений 00 (11). В силу исправности подсхемы K2 и мультиплексора синхронное последовательностное устройство исправно функционирует.Неисправность константа 1 (0) на выходах подсхемы И не влияет на корректное функционирование синхронного последовательностного устройства.Неисправность константа 1(0) на одном из выходов детектора может привести к появлению на выходах детектора сигналов 11 (00). В силу исправности подсхемы K2 и подсхемы мультиплексора синхронное последовательностное устройство исправно функционирует. Теорема доказана.Замечание. Будем иметь в виду, что допустимые неисправности мультиплексора при исправности всех остальных подсхем схемы рис. 1 сохраняют исправное функционирование синхронного последовательностного устройства.Итак, мы показали, что предложенная нами схема обеспечивает корректное функционирование синхронного последовательностного устройства в присутствии любой из допустимых кратковременных или перемежающихся неисправностей, длительность которых не превышает нескольких тактов, и при условии, что каждая последующая неисправность может появиться только после прекращения действия предыдущей неисправности.В случае использовании кодов Бергера при кодировании выходных символов самопроверяемого синхронного последовательностного устройства вместо одного двухвыходного детектора кодов необходимо использовать два одновыходных детектора, добавив к выходу одного из них, например, детектору кодов Бергера, инвертор. Пусть выход инвертора есть ui, а выход детектора равновесных кодов есть u2.Рассматриваются те же самые допустимые неисправности, кратковременные или перемежающиеся, длительность которых не превосходит нескольких тактов, и в каждый момент времени возможна только одна неисправность.Схема синхронного последовательностного устройства, устойчивого к неисправностям, представлена на рис. 2.Самопроверяемое синхронное устройствоССУ,y, ,.,ym7*-илиz,',...,zpдк1дкг"2mxСамопроверяемое синхронное устройствоССУ2d,2,...,dpиz,"...,zp"Рис. 2. Схема с детектором равновесных кодов и кодов БергераВ табл. 4 приведены оценки сложности схем, устойчивых к неисправностям рассматриваемого типа по сравнению с троированием. При оценке сложности исключен из рассмотрения мультиплексор MX, а в схеме троирования - подсхема голосования. В обеих реализациях не учитывались сложности триггеров. Под сложностью схемы понимается число инверторов и двухвходовых элементов НЕ И. В приведенных в таблице схемах состояния и выходы кодировались равновесными кодами. Детекторы кодов строились декомпозиционным методом, изложенным в работе [5] и развитым применительно к двухвходовым логическим элементам. Для получения самопроверяемой реализации синхронного последова-тельностного устройства использовались частично монотонные системы, аналогичные системе, представленной табл. 3. При кодировании состояний применялся равновесный 2,п-код. Несамопроверяемые реализации получались кодированием состояний кодовыми словами минимальной длины. Затем к полученным системам функций применялся факторизационный метод синтеза, основанный на делении ДНФ. В 6-м и 7-м столбцах таблицы указано число двухвходовых элементов НЕ И и инверторов, потребовавшихся для реализации комбинационных составляющих схем, полученных кодированием кодом минимальной длины и 2,п-кодомВ табл. 4 введены следующие обозначения. n - число входов; m - число выходов;p - число конъюнкций в STG-описании;s - число состояний;q - число линий обратных связей;L - число элементов комбинационной составляющей последовательностной схемы при кодировании состояний плотным кодом;L' - число элементов схемы K1(K2) при кодировании состояний последовательностной схемы 2,п-кодомтд - число дополнительных выходов схемы K1(K2) при использовании для кодирования выходных слов равновесного п/2,п-кодаq' - число линий обратных связей последовательностной схемы при кодировании состояний 2,п-кодомС(Д) - сложность детектораС(И,ИЛИ) - сложность схем И,ИЛИNT - число элементов последовательностной схемы при троировании без учета сложности элементов голосования и сложности d-триггеров;N - число элементов схемы рис. 1 без учета сложности мультиплексора и d-триггеровИз таблицы видно, что сложность предлагаемой схемы не больше сложности трех несамотестируемых схем, используемых при троировании.ЗаключениеПредложена схемная реализация устойчивого к одиночным кратковременным неисправностям синхронного последовательностного устройства, основанная на дублировании самопроверяемого устройства и использовании несамотестируемо-го детектора кодовых слов одного из устройств. Неисправность возможна в любой из подсхем. Предлагаемая схема, как правило, лучше троирования, которое требует отсутствия неисправностей в подсхеме голосования.

Скачать электронную версию публикации