Известия РАН. Теория и системы управления, 2023, № 6, стр. 110-123

Введение. В настоящее время беспилотные летательные аппараты (БПЛА) широко используются во многих сферах деятельности человека, в том числе и в военных конфликтах. Одним из способов борьбы с БПЛА является воздействие на БПЛА электромагнитного импульса с целью вывода из строя устройства управления [1]. Эффективным способом защиты БПЛА от воздействия электромагнитного импульса служит реализация устройства управления в виде отказоустойчивого конечного автомата.

На рис. 1 показана традиционная структурная модель конечного автомата, где X – входные сигналы (входной вектор); Y – выходные сигналы (выходной вектор); R – регистр состояний, в котором хранится код настоящего (текущего) состояния; Φ – комбинационная схема (логика), определяющая код следующего состояния (Φ: X × S → S); Ψ – комбинационная схема, формирующая значения выходных сигналов (Ψ: X × S → Y); S – множество состояний конечного автомата. Отметим, что выход регистра R соединен цепью обратной связи с входом комбинационной схемы Φ. Для автоматов Мура значения выходных сигналов формируются на основании кода настоящего состояния (Ψ: S → Y), а для автоматов Мили – на базе кода настоящего состояния и значений входных сигналов (Ψ: X × S → Y). Поэтому для автомата Мили входы X соединены с входами комбинационной схемы Ψ (на рис. 1 обозначено пунктирной линией). Тактовый сигнал clk для регистра R формируется с помощью генератора Oscillator.

В результате воздействия электромагнитного импульса сбои в структуре конечного автомата на рис. 1 могут возникать:

на входах: недопустимый входной вектор X;

в регистре R: код недопустимого настоящего состояния;

в логике Φ: формирование недопустимого кода следующего состояния;

в логике Ψ: формирование недопустимого выходного вектора;

в цепях конечного автомата: входных, выходных, обратной связи;

в цепи синхросигнала clk: отсутствие тактового сигнала;

в генераторе Oscillator: выход из строя генератора тактовых сигналов.

Кроме того, в результате воздействия электромагнитного импульса возможны неисправности автомата на поведенческом уровне: переход автомата в недопустимые состояния (invalid states), а также недопустимые переходы (invalid transition) в допустимые состояния (рис. 2).

Известно достаточно много методов построения отказоустойчивых конечных автоматов. Большинство из них посвящены противодействию одиночных неисправностей (single event upsets – SEUs), порождаемых радиационным излучением и космическими лучами, которые изменяют содержимое триггеров или ячеек памяти, при этом первичные входы всегда считаются верными. Однако электромагнитный импульс характеризуется следующими особенностями воздействия на БПЛА:

значительная продолжительность времени воздействия по сравнению с космической частицей;

воздействие сразу на все компоненты схемы;

порождает не кратковременные одиночные неисправности (SEU), а продолжительные многократные ошибки;

воздействует главным образом на цепи (входные, выходные, обратной связи);

редко изменяет содержимое регистра или ячеек памяти.

Отметим, что современные методики проектирования цифровых устройств [2] значительно отличаются от подходов, используемых несколько десятилетий назад. В последнее время значительное развитие получили языки описания аппаратуры (hardware description language – HDL), такие, как, VHDL, Verilog, SystemVerilog и др. В результате синтез устройства сводится к корректному описанию проекта на некотором языке HDL [3]. При этом отпадают традиционные этапы синтеза конечного автомата: кодирование состояний; генерация логических (булевых) уравнений для комбинационных схем Φ и Ψ; минимизация, факторизация и декомпозиция логики. Все эти действия средства синтеза выполняют автоматически. Однако в результате выполнения автоматической оптимизации логики избыточная логика, направленная на построение отказоустойчивого конечного автомата, может быть удалена из проекта. Поэтому необходимы новые подходы к проектированию отказоустойчивых конечных автоматов.

Областью исследований данной работы является проектирование отказоустойчивых конечных автоматов. Но прежде чем исправить каким-либо образом сбой конечного автомата, неисправность необходимо обнаружить. Поскольку в практике инженерного проектирования наиболее часто используется модель автомата Мура, в настоящей работе исследуются структурные модели для обнаружения неисправностей конечных автоматов Мура.

В статье впервые решается задача обнаружения неисправностей конечного автомата на структурном уровне. Для этого предложены структурные модели конечных автоматов, которые позволяют обнаружить многократные неисправности в различных элементах автомата и предотвратить их негативное воздействие на управляемый объект. Новизна структурных моделей заключается в следующем:

впервые рассматриваются неисправности конечного автомата, которые вызваны не космическими частицами, а электромагнитным импульсом, воздействующим на устройство управления БПЛА;

не ограничено число неисправностей в кодах состояний, во входном и выходном векторах;

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

кроме того, структурные модели выявляют недопустимые переходы автомата и переходы в недопустимые состояния;

структурные модели не только находят неисправности, но и предотвращают их негативное воздействие на управляемый объект;

объединенная структурная модель конечного автомата позволяет одновременно (параллельно) определять неисправности сразу во всех элементах конечного автомата;

структурные модели применимы при реализации конечного автомата как в программируемых интегральных схемах (ПЛИС – field programmable gate arrays –FPGAs), так и в специализированных интегральных схемах (application-specific integrated circuit – ASIC).

Главной целью работы является решение на структурном уровне задачи обнаружения многократных неисправностей различных компонентов конечного автомата Мура, которые могут быть вызваны электромагнитным импульсом.

Статья организована следующим образом. В разд. 1 рассматриваются публикации, относящиеся к проблеме проектирования отказоустойчивых конечных автоматов. В разд. 2 описывается пример автомата Мура, который используется для объяснения предлагаемого подхода. В разд. 3 представлены структурные модели конечных автоматов. Экспериментальные исследования исследуются в разд. 4. В разд. 5 приведены оценки площади и быстродействия рассматриваемых структурных моделей. В разд. 6 на конкретных примерах даны рекомендации по практическому применению структурных моделей. В Заключении подводятся итоги и указывается на направление дальнейших исследований.

1. Относящиеся работы. Проектирование отказоустойчивых вычислительных и управляющих систем, которыми являются конечные автоматы, всегда было актуальным с момента появления компьютеров. Проблема защиты конечных автоматов от космических лучей интенсивно исследовалась в конце 60-х годов прошлого столетия. Традиционным решением задачи считается кратное дублирование архитектуры конечного автомата, при этом наибольшее распространение получил метод тройного модульного резервирования (triple modular redundancy – TRM) для защиты от SEU [4]. В общем случае отказоустойчивость цифровой системы может обеспечиваться избыточностью архитектуры, увеличением времени работы и избыточностью данных [5].

Большое число работ посвящено улучшению метода TMR. Для этого в [6] используется код с исправлением одиночных ошибок (single error correction – SEC) для реализации конечного автомата, который допускает одну ошибку в логике следующего состояния и в регистре состояний. В [7] сравниваются архитектуры отказоустойчивых конечных автоматов (TRM, SEU-ITRM, duplex, EEC, модифицированная EEC и IEC), которые допускают единичные ошибки при переключении состояний.

Применение ПЛИС для проектирования конечных автоматов дает ряд преимуществ по сравнению с ASIC: низкая потребляемая мощность, небольшая стоимость, малое время выхода готового изделия на рынок, возможность перепрограммирования и др. Однако ПЛИС более подвержены SEU, вызываемые космическими частицами, чем ASIC. Поэтому фирма Xilinx выпустила специальную серию ПЛИС семейства Virtex, которая поддерживает метод TMR на аппаратном уровне [8]. В [9] предлагается в системах на кристалле (sytem-on-chip – SoC) при обнаружении ошибки в ПЛИС генерировать прерывание для микроконтроллера, который запускает процедуру частичного перепрограммирования ПЛИС. В [10] приводится метод усовершенствования TMR, который сочетает в себе дублирование со сравнением (duplication with comparison – DWC) и одновременное обнаружение ошибок (concurrent error detection – CED) на основе временной избыточности.

Отдельные работы посвящены способам кодирования состояний отказоустойчивых конечных автоматов. В [11] рассматриваются четыре способа кодирования состояний отказоустойчивых конечных автоматов: binary, one-hot, Хэмминга с расстоянием 2 (H2) и Хэмминга с расстоянием 3 (H3). Сравнивается обеспечение отказоустойчивости и использование ресурсов. В [12] исследуются способы кодирования состояний binary, one-hot и H3 для устранения SEU в регистре состояний, рекомендуется вручную задавать логику восстановления из недопустимого состояния.

Было разработано много методов улучшения TMR, при этом используются различные способы кодирования состояний. В [13] предлагается метод двойной модульной избыточности (dual modular redundancy – DMR) и применение бита четности при реализации конечного автомата во встроенных блоках памяти FPGA. В [14] оцениваются два метода синтеза отказоустойчивых конечных автоматов: дублирование с самопроверкой и TMR. При этом используются следующие способы кодирования состояний: binary, one-hot и Грэя. В [15] предлагается улучшение метода TMR с помощью кода Хэмминга при реализации конечного автомата во встроенных блоках памяти ПЛИС. В [16] предлагается усовершенствование метода TMR от Xilinx [8]. Для этого система представляется как совокупность конечных автоматов, вводятся контрольные точки для определения неисправного домена. Когда обнаруживается неисправность, восстанавливается только неисправный домен, а остальная часть системы продолжает работать. В результате сокращается время восстановления системы после сбоя.

В некоторых методах в конечный автомат вводятся дополнительные состояния. В [17] рассматривается метод защиты конечного автомата от SEU. С этой целью в конечный автомат добавляются избыточные эквивалентные состояния для защиты состояний с высокой вероятностью возникновения сбоя. В [18] приводится метод синтеза отказоустойчивых конечных автоматов на основе кода исправления одиночных ошибок и обнаружения двойных ошибок (single error correction and double error detection – SEC-DED). Метод предусматривает возврат конечного автомата в известное безопасное состояние или состояние сброса.

В последнее время интерес к проектированию отказоустойчивых конечных автоматов по-прежнему не ослабевает. В [19] исследуется отказоустойчивость трех методов синтеза конечных автоматов: TMR, H3 и безопасный (safe) синтез. В [20] предлагаемый метод повышает отказоустойчивость конечного автомата за счет выборочного применения метода TMR в соответствии с важностью состояния. В [21] описывается квазичувствительная к задержке архитектура конечного автомата, которая сравнивается с TMR.

Рассмотрение вышеупомянутых работ показывает, что большинство методов синтеза отказоустойчивых конечных автоматов посвящено усовершенствованию метода TMR для исправления SEU в регистре состояний. При этом предполагается, что первичные входы, логика формирования кода следующего состояния, логика формирования выходов, а также дополнительная логика обнаружения и исправления ошибок сбоев не имеют.

В то же время отличные от традиционных структурные модели конечных автоматов являются очень эффективными для повышения быстродействия, уменьшения стоимости реализации и потребляемой мощности при реализации конечных автоматов на ПЛИС [22]. В настоящей работе исследуются структурные модели конечных автоматов Мура для обнаружения многократных неисправностей в различных элементах конечного автомата и предотвращения их негативного воздействия на управляемый объект.

2. Демонстрационный пример. В качестве примера рассмотрим конечный автомат Мура, граф которого показан на рис. 3. Наш автомат имеет пять состояний, три входа и три выхода. Вершины графа соответствуют состояниям S₀, …, S₄, а дуги графа – переходам автомата. Вблизи каждой дуги графа записывается входной вектор, который инициирует данный переход. Вблизи каждой вершины графа записывается выходной вектор, который формируется в данном состоянии. Здесь дефис (“–”) может принимать любое значение бита: 0 или 1.

Допустимые переходы между состояниями (табл. 1) и допустимые выходные векторы в каждом состоянии (табл. 2) можно определить непосредственно по графу автомата. Допустимые входные векторы в каждом состоянии указывает разработчик на основании поведения устройства. Пусть для нашего автомата допустимые входные векторы заданы с помощью табл. 3.

3. Структурные модели конечных автоматов для обнаружения неисправностей. Структурные модели конечных автоматов для обнаружения неисправностей и предотвращения негативного воздействия неисправностей на управляемый объект показаны на рис. 4, где TVI – структура для обнаружения недопустимых входных векторов для всего автомата; VI – структура для обнаружения недопустимых входных векторов в каждом состоянии; VS – структура для обнаружения недопустимого кода настоящего состояния; VNS – структура для обнаружения недопустимого кода следующего состояния; VT – структура для обнаружения недопустимых переходов; TVO – структура для обнаружения недопустимых выходных векторов для всего автомата; VO – структура для обнаружения недопустимых выходных векторов в каждом состоянии.

Структуры на рис. 4 образованы путем введения в традиционную структуру на рис. 1 следующих комбинационных схем: TVI (total valid inputs), VI (valid inputs), VS (valid states), VNS (valid next states), VT (valid transitions), TVO (total void outputs) и VO (void outputs). Каждая дополнительная комбинационная схема формирует на выходе одноименный диагностический сигнал, единичное значение которого указывает на отсутствие неисправности. Все диагностические сигналы tvi, vi, vs, vns, vt, tvo и vo управляют входом разрешения синхронизации CE (clock enable) регистра состояний R. Поэтому в случае обнаружения неисправности конечный автомат будет оставаться в состоянии state до устранения неисправности. Кроме того, в структурах VS, TVO и VO дополнительно установлен выходной регистр R_O, вход CE которого управляется сигналами vs, tvo и vo соответственно. В случае обнаружения неисправности регистр R_O позволяет сохранить на выходах автомата ранее сформированный выходной вектор Y. Отметим, что введение в структуру конечного автомата выходного регистра R_O приводит к задержке выходных сигналов автомата на один такт синхронизации. Структуры TVI, VI, VNS и VT не имеют выходного вектора R_O, поскольку обнаруживаемые этими структурами неисправности не изменяют значение выходного вектора Y. Поэтому для устранения негативного воздействия неисправностей, обнаруживаемых структурами TVI, VI, VNS и VT, достаточно остановить конечный автомат в настоящем состоянии state.

На входы каждой дополнительной комбинационной схемы поступают значения, необходимые для определения соответствующей неисправности. Так, на вход комбинационной схемы TVI поступает входной вектор X. Недопустимые входные векторы для всего автомата определяются разработчиком на основании поведения управляемого объекта. Пусть для нашего примера недопустимыми входными векторами являются 110 и 111. На вход комбинационной схемы VI поступает код настоящего состояния state, а также входной вектор X. Для нашего примера функционирование комбинационной схемы VI определено в табл. 3. На вход комбинационной схемы VS поступает код настоящего состояния state. На вход комбинационной схемы VNS поступает сформированный логикой Φ код следующего состояния next. Для нашего примера допустимыми являются коды состояний S₀,…,S₄. На вход комбинационной схемы VT поступает код настоящего состояния state, а также код следующего состояния next. Для нашего примера функционирование комбинационной схемы VT представлено в табл. 1. На вход комбинационной схемы TVO поступают значения выходов логики Ψ. Для нашего примера допустимыми являются выходные векторы, которые формируются в состояниях автомата: 100, 001, 010, 011 и 001. На вход комбинационной схемы VO поступает код настоящего состояния state и значения выходов, сформированные логикой Ψ. Для нашего примера функционирование комбинационной схемы VO приведено в табл. 2.

В табл. 4 приведены возможные причины неисправностей, которые обнаруживаются структурными моделями на рис. 4, где Φ – сбой в логике Φ; X – недопустимый входной вектор X; feedback – сбой в цепи обратной связи; Ψ – сбой в логике Ψ; R – сбой в регистре состояний R.

Все рассмотренные структурные модели конечных автоматов не нацелены для реализации на определенную элементную базу: каждая структурная модель может быть реализована как на ASIC, так и на ПЛИС.

Структуры на рис. 4 по желанию пользователя могут произвольно объединяться вместе для наиболее эффективного обнаружения неисправностей автомата. Отметим, что структура TVI покрывается структурой VI, т.е. в случае обнаружения неисправности с помощью структуры TVI, эта неисправность обязательно будет обнаружена структурой VI. Аналогично структура TVO покрывается структурой VO, а структура VNS – структурой VT. Поэтому при объединении всех рассматриваемых структур вместе структуры TVI, TVO и NVS можно опустить. На рис. 5 показана обобщенная структура VISTO, которая объединяет структуры VI, VS, VT и VO.

Диагностические сигналы tvi, vi, vs, vns, vt, tvo и vo, формируемые в структурных моделях конечных автоматов на рис. 4, могут выводиться на внешние выводы автомата для обнаружения местоположения неисправности в ASIC. При необходимости диагностические сигналы могут объединяться вместе для указания на ошибку (рис. 6), например, с целью реконфигурирования ПЛИС.

4. Экспериментальные исследования. Все рассмотренные структурные модели для нашего примера конечного автомата Мура были описаны на языке Verilog в стиле с тремя процессами [3]. В результате были созданы следующие проекты конечного автомата Мура для нашего примера: based_FSM – базовая структурная модель конечного автомата Мура (рис. 1); TVI_FSM – конечный автомат с проверкой допустимых входных векторов для всего автомата (рис. 4,а); VI_ FSM – конечный автомат с проверкой допустимых входных векторов в каждом состоянии (рис. 4,б); VS_FSM – конечный автомат с проверкой допустимого кода настоящего состояния (рис. 4,в); VNS_FSM – конечный автомат с проверкой допустимого кода следующего состояния (рис. 4,г); VT_FSM – конечный автомат с проверкой допустимых переходов между состояниями (рис. 4,д); TVO_FSM – конечный автомат с проверкой допустимых выходных векторов для всего автомата (рис. 4,е); VO_FSM – конечный автомат с проверкой допустимых выходных векторов в каждом состоянии (рис. 4,ж); VISTO_FSM – конечный автомат с объединением всех рассмотренных проверок (рис. 5).

Для оценки параметров предлагаемых структурных моделей все проекты были реализованы с помощью средства Quartus Prime версии 22.4 на ПЛИС семейства Cyclone 10 LP. Результаты экспериментальных исследований приведены в табл. 5, где L – число используемых LUT (look-up table) или площадь; F – максимальная частота функционирования (в мегагерцах) или быстродействие; L_b и F_b – аналогичные параметры для базовой структурной модели автомата Мура; L/L_b и F/F_b – отношения соответствующих параметров.

Анализ табл. 5 показывает, что по стоимости реализации (площади) наиболее затратной является структура VISTO, которая приводит к увеличению площади на 109%. Затем по убыванию используемой площади следуют структуры VT (увеличение площади на 73%), VI (увеличение площади на 36%) и TVI (увеличение площади на 9%). Отметим, что структуры VO, VS, VNS и TVO не приводят к увеличению площади ПЛИС по сравнению с базовой структурой.

По быстродействию наиболее затратной также является структура VISTO, которая приводит к уменьшению быстродействия на 38%. Затем следуют структуры VT (уменьшение быстродействия на 35%) и TVI (уменьшение быстродействия на 8%). Кроме того, для структур VO, VS, TVO и VISTO выходные сигналы формируются с задержкой на один такт синхронизации по сравнению с базовой структурой. В то же время для структур VS и TVO быстродействие увеличивается на 36%, а для структуры VO – на 28%. Отметим также, что для структуры VI, несмотря на увеличение площади на 36%, быстродействие увеличивается на 10%, при этом отсутствует задержка выходных сигналов на один такт синхронизации. Структура VNS по площади и по быстродействию совпадает с базовой структурой.

Рассмотрение одного примера конечного автомата не позволяет в полной мере оценить предлагаемые структурные модели. Поэтому были проведены исследования структурных моделей на эталонных примерах конечных автоматов центра MCNC [23]. Результаты таких исследований представлены в табл. 6 и 7.

В табл. 6 приведены результаты сравнения площади эталонных конечных автоматов в случае использования предлагаемых структурных моделей по сравнению с базовой структурой, где i – число входов; o – число выходов; s – число состояний конечного автомата; C_b – площадь (число LUT) базовой структуры конечного автомата; C – площадь реализации конечного автомата в случае применения одной из предложенных структурных моделей; C_b/C – отношение соответствующих параметров; mid – среднеарифметическое значение параметра. Эталонные примеры конечных автоматов Мили предварительно были приведены к конечным автоматам Мура с помощью метода [24].

Отметим, что для структур VS и VNS площадь реализации совпадает.

Таблица 6 показывает, что наименее затратными по площади являются структуры TVO и TVI (увеличение площади в среднем на 3%). Однако структура TVI позволяет определить недопустимые входные векторы для всего конечного автомата, которых может вообще не быть, поскольку большинство конечных автоматов не имеют ограничений на входные векторы. Недопустимых выходных векторов для всего конечного автомата, которые определяет структура TVO, тоже может быть немного или вообще не быть. Следующими по аппаратным затратам следуют структуры VS и VNS (увеличение площади в среднем на 12%), затем следуют структуры VO и VT (увеличение площади в среднем на 16%), а самой затратной по площади является структура VT (увеличение площади в среднем на 26%).

В табл. 7 приведены результаты сравнения быстродействия конечных автоматов в случае использования предлагаемых структурных моделей по сравнению с базовой структурой, где F_b – максимальная частота функционирования (в мегагерцах) базовой структуры конечного автомата; F – максимальная частота функционирования конечного автомата в случае применения одной из предложенных структурных моделей; F/F_q – отношение соответствующих параметров; mid – среднеарифметическое значение параметра.

Таблица 7 показывает, что быстродействие структур TVI, VI, VNS, VT полностью совпадает с быстродействием базовой структуры конечного автомата. Быстродействие структур VS и TVO возрастает в среднем на 30% по сравнению с базовой структурой, а быстродействие структуры VO возрастает в среднем на 24% по сравнению с базовой структурой конечного автомата.

5. Оценка площади и быстродействия предлагаемых структурных моделей. В случае реализации конечного автомата в ПЛИС на основе LUT площадь дополнительной комбинационной схемы можно определить с помощью следующего выражения:

где n – число входов LUT; r – ранг (число входов) дополнительных комбинационных схем; ]A[ – наибольшее целое число, большее или равное числу A.

Для рассматриваемых структурных моделей ранги дополнительных комбинационных схем приведены в табл. 8, где i – число входов; o – число выходов; k – число битов кодов состояний конечного автомата.

Отметим, что ранги дополнительных комбинационных схем зависят от числа k битов кодов состояний конечного автомата, т.е. от способа кодирования состояний. Поэтому, например, площадь реализации предлагаемых структурных моделей будет разная в случае использования кодирования one-hot и binary.

Оценка стоимости реализации предлагаемых структурных моделей для нашего примера представлена в табл. 9, где r – ранг дополнительной схемы (или схем) в случае кодирования one-hot; C_c – вычисленная площадь (в числе LUT) дополнительной комбинационной схемы (или схем); C_q – реальная площадь реализации, определенная с помощью средства Quartus; C_b – площадь базовой структуры конечного автомата. Отметим, что для нашего примера конечного автомата Мура в случае кодирования one-hot имеем i = 3, o = 3, k = 5 и C_b = 11.

Таблица 9 показывает, что на реальную площадь реализации C_q значительное влияние оказывает используемое средство синтеза. Поэтому вычисленное значение площади (C_c + C_b) может быть как больше, так и меньше реальной площади реализации. Например, для нашего примера вычисленное значение площади для большинства структур превышает или равно реальной площади реализации, исключениями являются структуры VT и VISTO.

Площадь дополнительных комбинационных схем, вычисленная, согласно (5.1), может применяться для выбора наиболее подходящей структурной модели среди других предлагаемых структурных моделей обнаружения неисправностей конечного автомата.

Быстродействие дополнительных комбинационных схем в случае реализации конечного автомата на ПЛИС, основанных на LUT, можно оценить с помощью числа l уровней LUT, необходимых для их реализации [25]:

где r – ранг комбинационной схемы.

Однако поскольку сложность комбинационных схем Φ и Ψ значительно больше дополнительных схем для диагностики неисправностей, то дополнительные комбинационные схемы на быстродействие конечного автомата не влияют, а быстродействие конечного автомата определяется комбинационными схемами Φ и Ψ (для конечного автомата Мура наиболее сложной является комбинационная схема Φ). Кроме того, введение дополнительного выходного регистра R_O в ряде случаев приводит даже к увеличению быстродействия конечного автомата. Например, для нашего примера увеличение быстродействия наблюдается для структур VS, TVO и VO (табл. 5).

6. Примеры практического использования рассматриваемых структурных моделей. Выбор структурных моделей конечных автоматов и их объединение выполняется разработчиком устройства управления на основе их характеристик. Следующие факторы должны быть приняты во внимание при выборе структурных моделей:

неисправности, которые обнаруживаются моделью;

аппаратные издержки, вычисленные, согласно (5.1);

быстродействия дополнительных комбинационных схем, определяемые согласно (5.2);

допустимость задержки выходных сигналов на один такт синхронизации и др.

Рассмотрим выбор наиболее подходящей структурной модели для определения неисправностей на конкретных примерах. В табл. 10 приведены свойства предложенных структурных моделей, которые могут быть приняты во внимание при выборе наиболее подходящей структурной модели конечного автомата Мура из нашего примера.

Например, пусть для нашего примера конечного автомата Мура необходимо выбрать структурную модель, которая позволяет обнаружить наибольшее количество неисправностей и не допускается задержка выходных сигналов на один такт синхронизации, при этом желательно минимизировать увеличение площади и снижение быстродействия конечного автомата. Поскольку для конечного автомата не допускается задержка выходных сигналов на один такт синхронизации, согласно табл. 10, выбирать следует из структур TVI, VI, VNS и VT. Структуру TVI исключаем, поскольку она определяет только одну неисправность (недопустимый входной вектор X). Структуры VNS и VT позволяют выявить наибольшее число неисправностей (табл. 4). Структура VNS не увеличивает площадь и не снижает быстродействие (табл. 5) по сравнению с базовой структурой, поэтому для реализации выбираем структуру VNS. В результате решаем задачу, не увеличивая площадь и не снижая быстродействие конечного автомата.

При выборе структуры для реализации следует также учитывать количество и сложность обнаруживаемых неисправностей. Пусть, например, для нашего примера конечного автомата Мура поставлена та же задача, но допускается задержка выходных сигналов на один такт синхронизации. Согласно табл. 4, все возможные причины неисправностей можно обнаружить путем объединения любых моделей из двух групп структур: {VNS и VT} и {TVO и VO}. Из группы {VNS и VT} выбираем структуру VNS, которая по сравнению со структурой VT не увеличивает площадь и не снижает быстродействие (табл. 5). Из группы {TVO и VO} выбираем структуру VO, которая позволяет обнаружить более сложные неисправности, чем структура TVO. Поэтому задача решается объединением структур VNS и VO.

Пусть необходимо наиболее точно определить следующие причины неисправностей: недопустимый входной вектор X, сбой в логике Φ, сбой в логике Ψ или сбой в регистре состояний R. Недопустимый входной вектор X определяется с помощью структуры TVI или VI (табл. 4); выбираем структуру VI, которая обнаруживает более сложные неисправности (недопустимые входные векторы в каждом состоянии). Сбой в логике Φ можно определить с помощью структуры VNS или VT; выбираем структуру VNS, которая не увеличивает площадь и не снижает быстродействие. Сбой в логике Ψ можно определить с помощью структуры TVO или VO; выбираем структуру VO, которая обнаруживает более сложные неисправности (недопустимые выходные векторы в каждом состоянии). Сбой в регистре состояний R можно обнаружить с помощью любой структуры, за исключением структуры TVI; выбираем структуру VS, которая однозначно указывает на сбой в регистре R или в цепи обратной связи. Поэтому задача решается объединением следующих структур: VI, VNS, VO и VS.

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

Если необходимо наиболее точно указать местоположение и причину неисправности (например, при реализации конечного автомата в ASIC), то для реализации следует объединить все структуры, а диагностические сигналы tvi, vi, vs, vns, vt, tvo и vo вывести на внешние выводы конечного автомата.

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

недопустимые входные векторы для всего автомата;

недопустимые входные векторы в каждом состоянии;

недопустимый код настоящего состояния;

недопустимый код следующего состояния;

недопустимые переходы между состояниями;

недопустимые выходные векторы для всего автомата;

недопустимые выходные векторы, формируемые в каждом состоянии.

Приведена также обобщенная структурная модель конечного автомата, позволяющая обнаружить все перечисленные выше неисправности. Кроме того, рассмотренные структурные модели позволяют обнаружить многократные сбои в логике Φ формирования кода следующего состояния, в логике формирования значений выходных сигналов Ψ, в регистре состояний R, а также в цепи обратной связи. Предлагаемые структурные модели конечных автоматов не только обнаруживают неисправности, но и предотвращают их негативное воздействие на управляемый объект.

Будущие исследования будут направлены на разработку структурных моделей, которые допускают исправление сбоев конечного автомата.