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

1. Введение

Использование схем встроенного контроля (СВК) позволяет обнаруживать неисправности и ошибки в вычислениях устройствами автоматики и вычислительной техники в процессе реализации ими своих функций [1, 2]. Такое свойство крайне важно для обеспечения надежности и безопасности устройств, функционирующих в системах различного назначения, в том числе, являющихся составляющими систем управления ответственными технологическими процессами в промышленности и на транспорте [3, 4].

При синтезе СВК используются принципы дробного и кратного резервирования, а также диверсной защиты. Существуют методы, основанные на использовании внутренней избыточности – внесения ее в структуру исходного устройства (объект диагностирования), а также основанные на внесении внешней избыточности – применении внешних средств технического диагностирования. Здесь широко используются методы теории информации и кодирования в процессе выбора способа внесения избыточности [5–10].

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

Достоинства традиционного подхода к организации СВК очевидны, а вот недостатком является то, что при использовании заданного равномерного кода число вариантов синтеза СВК для устройства с конкретными параметрами является крайне малым. Это не позволяет в ряде случаев добиваться обеспечения свойства его самопроверяемости. Однако существует альтернативный подход, основанный на логической коррекции сигналов (ЛКС) в СВК, лишенный данного недостатка [14].

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

Использованию ЛКС совместно с равномерными кодами посвящено большое количество работ (однако в сотни раз меньшее, чем использованию традиционного подхода). Например, в [16–18] обсуждаются особенности применения неразделимых равномерных кодов при синтезе СВК на основе ЛКС, в [19–21] – разделимых равномерных кодов с учетом их свойств, в [22, 23] – использования свойств особых классов булевых функций совместно с ЛКС, а в [24, 25] – применения сразу же двух диагностических признаков для организации контроля вычислений на основе ЛКС. В данной статье авторы приводят результаты исследований общего числа способов синтеза СВК на основе ЛКС с применением равномерных разделимых кодов.

Исходные предпосылки и допущения

При синтезе схем встроенного контроля (СВК) на основе логической коррекции сигналов (ЛКС) с применением разделимых равномерных кодов, или (m, k)-кодов, где m и k – число информационных и проверочных символов, могут рассматриваться три основные структуры. Структура типа I подразумевает использование ЛКС для преобразования части функций, вычисляемых на выходах объекта диагностирования, в функции, описывающие проверочные символы заданного (m, k)-кода. Следует отметить, что такое преобразование оказывается единственным для заданной последовательности преобразуемых выходов объекта диагностирования в силу того, что каждому информационному вектору будет соответствовать единственный контрольный вектор (m, k)-кода. Структура типа II основана на логической коррекции сигналов только с тех выходов объекта диагностирования, которые участвуют в формировании информационных символов (m, k)-кода. Здесь преобразование не является единственным, так как для (m, k)-кода при условии m > k одному контрольному вектору может соответствовать два и более информационных векторов. Структура типа III – обобщенная структура организации СВК – основана на использовании ЛКС сразу же со всех выходов объекта диагностирования. В такой структуре возможно гораздо большее количество вариантов доопределения значений информационных и проверочных символов заданного (m, k)-кода. Эти структуры не являются новыми. Структура типа I исследовалась в работах [19, 20, 26], структура типа II рассматривалась в [27] и структура типа III – в [28, 29].

На рис. 1 приведены каскады элементов преобразования для структур всех трех типов. Во всех структурах объектом диагностирования является блок F(x), формирующий систему булевых функций f1, f2, …, fn, n = m + k. Данные функции участвуют в формировании кодовых слов выбранного на этапе проектирования СВК (m, k)-кода, описываемых функциями h1, h2, …, hn. В структурах типа I и II часть из рабочих функций объекта диагностирования корректируются, а часть – нет; в структуре типа III корректируются значения всех булевых функций. Функции логической коррекции сигналов вычисляются блоком контрольной логики G(x).

Рис. 1. Каскады элементов преобразования в структурах организации СВК на основе ЛКС с применением (m, k)-кодов.

Ясно, что могут рассматриваться и другие вариации структур организации СВК на основе ЛКС с применением (m, k)-кодов. Однако в дальнейшем изложении ограничимся только тремя основными.

Работа устройств F(x) происходит при подаче на t входов множества булевых векторов длиной t. Рассмотрим общий случай, когда объект диагностирования функционирует при подаче полного множества входных комбинаций. Его мощность равна 2t. При рассмотрении (m, k)-кода будем рассматривать полное множество его кодовых слов. Его мощность будет равна 2m. Максимальное число контрольных векторов будет равно 2k. Причем, будем рассматривать только те (m, k)-коды, для которых при формировании всех 2m информационных векторов, контрольные векторы генерируются равномерно. Другими словами, каждому контрольному вектору соответствует $2^{m-k}$ информационных векторов. Такое ограничение вызвано вопросами обеспечения самопроверяемости СВК и необходимостью формирования некоторого множества кодовых слов (m, k)-кода для проверки его тестера в процессе эксплуатации (конкретное количество кодовых слов, информационных и контрольных векторов определяется при проектировании СВК с учетом особенностей реализации тестера и условий эксплуатации самопроверяемого устройства) [27–29].

Поставим следующую задачу: определить общее количество способов синтеза СВК по трем различным структурам и оценить возможности использования (m, k)-кодов при этом.

Многообразие способов синтеза схем встроенного контроля

В структуре типа I каждый информационный вектор (m, k)-кода однозначно будет определять значения проверочных символов в контрольном векторе. Для выбранных выходов m и k существует только один способ доопределения функций ЛКС. Число способов выбора k преобразуемых функций из m+k определяется величиной $C_{m+k}^k$. Число вариантов выбора последовательности размещения символов в информационном векторе определяется числом перестановок из m элементов – числом $P_m^{}$. Число вариантов выбора последовательности размещения символов в контрольном векторе определяется числом перестановок из k элементов – числом $P_k^{}$. Таким образом, общее число способов организации СВК по структуре типа I с учетом однозначного доопределения функций ЛКС равно:

 $N_I=C_{m+k}^k{P}_m^{}{P}_k^{}=\frac{\left(m+k\right)!}{k!m!}m!k!=\left(m+k\right)!$  (1)

В структуре типа II заполнение на каждом входном наборе не однозначное. Напомним, что рассматривается случай использования (m, k)-кода, при котором информационные векторы распределены между контрольными равномерно (такие коды широко распространены и используются в практике синтеза высоконадежных цифровых схем [30]). Число способов выбора m преобразуемых функций из m+k определяется величиной $C_{m+k}^m=C_{m+k}^k$. Число вариантов выбора последовательности размещения символов в контрольном векторе определяется числом перестановок из m элементов – числом $P_m^{}$. Число вариантов выбора последовательности размещения символов в контрольном векторе определяется числом перестановок из k элементов – числом $P_k^{}$. На каждой входной комбинации из 2t можно 2m–k способами доопределить функции так, чтобы был сформирован информационный вектор с необходимым контрольным. При этом должно выполняться условие: t≥k. В противном случае не удастся обеспечить формирование по разу каждого контрольного вектора. Общее число способов доопределения, таким образом, будет равно $2^t{2}^{m-k}=2^{t+m-k}$. Отсюда становится ясно, что число способов построения СВК с учетом отмеченного равно:

 $N_{II}=2^{t+m-k}{C}_{m+k}^k{P}_m^{}{P}_k^{}=2^{t+m-k}\frac{\left(m+k\right)!}{k!m!}m!k!=2^{t+m-k}\left(m+k\right)!$

 $N_{II}=2^{t+m-k}{C}_{m+k}^k{P}_m^{}{P}_k^{}=2^{t+m-k}\frac{\left(m+k\right)!}{k!m!}m!k!=2^{t+m-k}\left(m+k\right)!$ (2)

Структура типа III отличается от вышерассмотренных тем, что на каждом из 2t входных наборов можно получить любое кодовое слово из полного множества кодовых слов (m, k)-кода с учетом необходимости формирования каждого контрольного вектора хотя бы на одном входном наборе. Далее будем полагать, что доопределение будет таковым, что все контрольные векторы будут формироваться на одинаковом числе входных комбинаций, т. е. распределение формируемых контрольных векторов будет равномерно. В таком случае имеем 2t кодовых слова, распределенных равномерно между 2k контрольными векторами, или имеем 2t–k кодовых слов с одним и тем же контрольным вектором. Следует отметить естественное ограничение, как и в случае со структурой типа II, величина t ≥ k.

Число способов выбора m информационных символов из m+k символов, по-прежнему, равно $C_{m+k}^m=C_{m+k}^k$. Число вариантов выбора последовательности размещения символов в информационном векторе определяется числом перестановок из m элементов – числом $P_m^{}$. Число вариантов выбора последовательности размещения символов в контрольном векторе определяется числом перестановок из k элементов – числом $P_k^{}$. При этом на каждом входном наборе можно осуществить доопределение функций ЛКС для получения информационных символов 2m–k способами, поскольку все кодовые слова (их 2m) распределены равномерно между всеми контрольными векторами (их 2k); проверочные символы будут получены после единственным способом. Итого, имеем $2^{t-k}{2}^{m-k}=2^{t+m-2k}$ способов доопределения функций логической коррекции.

Но здесь не учитывается, что первый контрольный вектор может быть сформирован на

$C_{2^t}^{2^{t-k}}$ входных комбинациях;

второй – на $C_{2^t-2^{t-k}}^{2^{t-k}}$;

третий – на $C_{2^t-2\cdot 2^{t-k}}^{2^{t-k}}$; …;

2k-ый – на $C_{2^t-\left(2^k-1\right)\cdot 2^{t-k}}^{2^{t-k}}=C_{2^{t-k}}^{2^{t-k}}=1$.

Всего число вариантов доопределений с учетом возможных вариантов сочетаний выходов равно:

$\begin{array}{l}{C}_{2^t}^{2^{t-k}}{C}_{2^t-2^{t-k}}^{2^{t-k}}{C}_{2^t-2\cdot 2^{t-k}}^{2^{t-k}}\cdot \mathrm{...}\cdot C_{2^t-\left(2^k-1\right)\cdot 2^{t-k}}^{2^{t-k}}=\\ ={\displaystyle \prod _{i=0}^{2^k-1}{C}_{2^t-i\cdot 2^{t-k}}^{2^{t-k}}}\end{array}$

С учетом числа способов доопределения, имеем следующее общее число способов построения СВК по структуре типа III:

$\begin{array}{l}{N}_{III}=2^{t+m-2k}{C}_{m+k}^k{P}_m{\displaystyle \prod _{i=0}^{2^k-1}{C}_{2^t-i\cdot 2^{t-k}}^{2^{t-k}}}=\\ =2^{t+m-2k}{\left(m+k\right)}^{\underset{\_}{k}}{\displaystyle \prod _{i=0}^{2^k-1}{C}_{2^t-i\cdot 2^{t-k}}^{2^{t-k}}}\end{array}$ (3)

Рассмотрим отдельно произведение в формуле (3).

Введем обозначения: $a=2^{t-k},$ $b=2^t.$ Тогда 2k можно получить следующим образом: $a=\frac{2^t}{2^k}=\frac{b}{2^k}\Rightarrow 2^k=\frac{b}{a}.$  Произведение в выражении (3) с учетом введенных обозначений может быть записано в виде:

Вернемся к введенным выше обозначениями и подставим исходные выражения в формулу (4):

${\displaystyle \prod _{i=0}^{2^k-1}{C}_{2^t-i\cdot 2^{t-k}}^{2^{t-k}}}={\displaystyle \prod _{i=0}^{\frac{b}{a}-1}{C}_{b-i\cdot a}^a}=\frac{b!}{{(a!)}^{\frac{b}{a}}}=\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$  (5)

Формула (3), описывающая число способов построения СВК по структуре III, с учетом (5) приводится к виду:

 $N_{III}=2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$    (6)

Используя (1), (2) и (6), можно определить для рассматриваемого объекта диагностирования общее количество способов организации СВК на основе ЛКС с применением (m, k)-кода. В табл. 1–3 приведены результаты расчетов для некоторых значений t, m и k для всех трех структур. К примеру, при исходных данных t = 4, m = 4, k = 2 число способов организации СВК по структурам типа I, II и III равно NI = 720, NII = 46 080, NIII = 726 485760 000. Из сравнения данных такого простого примера следует, что структура типа III обладает более высокой вариативностью, чем первые две структуры: существует в 1 009008 000 раз больше вариантов ее построения, чем по структуре типа I и в 15 765750 раз, чем по структуре типа II.

Таблица 1. Число способов организации СВК по структуре типа I

Таблица 2. Число способов организации СВК по структуре типа II

Таблица 3. Число способов организации СВК по структуре типа III

Из сравнения же формул (1), (2) и (6) непосредственно следует, что представляет интерес исследование способов формирования алгоритмов построения СВК на основе структур типа II и III, тогда как по структуре типа I число способов определяется исключительно вариантами выбора выходов для преобразования и перестановок выходов внутри информационного и контрольного векторов.

Исследование числа способов организации схем встроенного контроля по различным структурам при увеличении числа выходов объекта диагностирования

4.1. Свойства структур, проявляющиеся при увеличении числа выделяемых информационных символов при постоянстве числа проверочных символов

Установим, как изменяется общее число вариантов построения СВК по структурам всех трех типов.

Определим, как изменится число вариантов построения СВК по структуре типа I с увеличением m на 1 при неизменном k:

 ${\delta }_I^{m+\mathrm{1,}m}=\frac{\left(\left(m+1\right)+k\right)!}{\left(m+k\right)!}=m+k+1$   (7)

Найдем, как изменится число вариантов построения СВК по структуре типа I с увеличением m на 2 при неизменном k:

  ${\delta }_I^{m+\mathrm{2,}m}=\frac{\left(\left(m+2\right)+k\right)!}{\left(m+k\right)!}=\left(m+k+1\right)\left(m+k+2\right)={\left(m+k+2\right)}^{\underset{¯}{2}}$    (8)

Обобщим (7) и (8) и найдем, как изменится число вариантов построения СВК по структуре типа I с увеличением m на произвольное $p\in \mathbb{N}$ при неизменном k:  

   ${\delta }_I^{m+p,m}=\frac{{\left(\left(m+p\right)+k\right)}^{\underset{¯}{k}}}{{\left(m+k\right)}^{\underset{¯}{k}}}=\left(m+k+1\right)\left(m+k+2\right)\cdot \mathrm{...}\cdot \left(m+k+p\right)={\left(m+k+p\right)}^{\underset{¯}{p}}$    (9)

Таким образом, справедливо следующее умозаключение.

Утверждение 1. При увеличении числа информационных символов при постоянном значении числа проверочных символов на величину $p\in \mathbb{N}$ общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа I увеличивается в ${\left(m+k+p\right)}^{\underset{¯}{p}}$ раз.

Аналогично изложенному выше найдем, как изменится число вариантов построения СВК по структуре типа II с увеличением m на 1 при неизменном k:

${\delta }_{II}^{m+\mathrm{1,}m}=\frac{2^{t+\left(m+1\right)-k}\left(\left(m+1\right)+k\right)!}{2^{t+m-k}\left(m+k\right)!}=2\left(m+k+1\right)$   (10)

Установим, как меняется число вариантов построения СВК по структуре типа II с увеличением m на произвольную величину $p\in \mathbb{N}$ при неизменном k:

 $\begin{array}{c}{\delta }_{II}^{m+p,m}=\frac{2^{t+\left(m+p\right)-k}\left(\left(m+p\right)+k\right)!}{2^{t+m-k}\left(m+k\right)!}=\\ =2^p\left(m+k+1\right)\left(m+k+2\right)\cdot \mathrm{...}\cdot \left(m+k+p\right)=2^p{\left(m+k+p\right)}^{\underset{¯}{p}}\end{array}$    (11)

С увеличением m на 1 при неизменном k для структуры типа III число способов построения СВК изменяется на величину:

  ${\delta }_{III}^{m+\mathrm{1,}m}=\frac{2^{t+\left(m+1\right)-2k}\left(\left(m+1\right)+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}=2\left(m+k+1\right)$ (12)

С учетом полученных ранее закономерностей (см. формулу 9), установим, как меняется число вариантов построения СВК по структуре типа III с увеличением m на произвольную величину $p\in \mathbb{N}$ при неизменном k.

$\begin{array}{l}{\delta }_{III}^{m+p,m}=\frac{2^{t+\left(m+1\right)-2k}\left(\left(m+1\right)+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}=\\ =2^p{\left(m+k+p\right)}^p\end{array}$  (13)

Утверждение 2. При увеличении числа информационных символов при постоянном значении числа проверочных символов на величину $p\in \mathbb{N}$ общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структурам типа II и III увеличивается в $2^p{\left(m+k+p\right)}^{\underset{¯}{p}}$ раз.

4.2. Свойства структур, проявляющиеся при увеличении числа выделяемых проверочных символов при постоянстве числа информационных символов

Рассмотрим, как меняется общее количество способов синтеза СВК на основе ЛКС с применением заданного (m, k)-кода в случае изменения числа выделяемых проверочных символов при постоянстве числа информационных символов.

Анализ (7)–(9) приводит к следующему умозаключению.

Утверждение 3. При увеличении числа проверочных символов при постоянном значении числа информационных символов на величину $p\in \mathbb{N}$ общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа I увеличивается в ${\left(m+k+p\right)}^{\underset{¯}{p}}$  раз.

Установим, как меняется число вариантов построения СВК по структуре типа II с увеличением k на произвольную величину $p\in \mathbb{N}$ при неизменном m:

  $\begin{array}{c}{\delta }_{II}^{k+p,k}=\frac{2^{t+m-\left(k+p\right)}\left(m+\left(k+p\right)\right)!}{2^{t+m-k}\left(m+k\right)!}=\\ =2^{-p}\left(m+k+1\right)\left(m+k+2\right)\cdot \mathrm{...}\cdot \left(m+k+p\right)=2^{-p}{\left(m+k+p\right)}^{\underset{¯}{p}}\end{array}$   (14)

Выражение (14) доказывает следующее положение:

Утверждение 4. При увеличении числа проверочных символов при постоянном значении числа информационных символов на величину $p\in \mathbb{N}$ общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа II изменяется в $2^{-p}{\left(m+k+p\right)}^{\underset{¯}{p}}$ раз.

Пользуясь (6), найдем, как меняется число вариантов построения СВК по структуре типа III с увеличением k на произвольную величину $p\in \mathbb{N}$ при неизменном m:

   $\begin{array}{c}{\delta }_{III}^{k+p,k}=\frac{2^{t+m-2\left(k+p\right)}\left(m+\left(k+p\right)\right)!\frac{2^t!}{{\left(2^{t-\left(k+p\right)}!\right)}^{2^{k+p}}}}{2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}=\\ =2^{-2p}{\left(m+k+p\right)}^{\underset{¯}{p}}\frac{{\left(2^{t-k}!\right)}^{2^k}}{{\left(2^{t-\left(k+p\right)}!\right)}^{2^{k+p}}}=\frac{{\left(2^{t-k}!\right)}^{2^k}{\left(m+k+p\right)}^{\underset{¯}{p}}}{4^p{\left(2^{t-k-p}!\right)}^{2^{k+p}}}\end{array}$  (15)

Выражение (15) приводит к такому положению:

Утверждение 5. При увеличении числа проверочных символов при постоянном значении числа информационных символов на величину $p\in \mathbb{N}$ общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа III изменяется в

 $\frac{{\left(2^{t-k}!\right)}^{2^k}{\left(m+k+p\right)}^{\underset{¯}{p}}}{4^p{\left(2^{t-k-p}!\right)}^{2^{k+p}}}$ раз.

Отметим, что могут быть установлены аналогичные свойства структур типов I, II и III, проявляющиеся при увеличении числа проверочных символов при постоянстве числа информационных символов (m, k)-кода, а также проявляющиеся при изменении как чисел m, так и k.

4.3. Сравнение числа способов синтеза СВК на основе структур различных типов

Найдем отношение величины NII к NI:

${\chi }_{II,I}=\frac{N_{II}}{N_I}=\frac{2^{t+m-k}\left(m+k\right)!}{\left(m+k\right)!}=2^{t+m-k}$              (16)

Выражение (16) доказывает следующее положение:

Утверждение 6. Общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа II для одних и тех же t, m и k больше в $2^{t+m-k}$ раз, чем аналогичное число для структуры типа I.

Найдем отношение величины NIII к NI:  

   ${\chi }_{III,I}=\frac{N_{III}}{N_I}=\frac{2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{\left(m+k\right)!}=2^{t+m-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$                         (17)

Конечное выражение в (17) свидетельствует о следующем:

Утверждение 7. Общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа III для одних и тех же t, m и k больше в $2^{t+m-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$ раз, чем аналогичное число для структуры типа I.

И, наконец, найдем отношение величины NIII к NII:

    ${\chi }_{III,II}=\frac{N_{III}}{N_{II}}=\frac{2^{t+m-2k}\left(m+k\right)!\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{2^{t+m-k}\left(m+k\right)!}=2^{-k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$    (18)

Становится ясным следующее:

Утверждение 8. Общее число способов построения СВК на основе ЛКС с применением заданного (m, k)-кода по структуре типа III для одних и тех же t, m и k больше в

 $2^{-k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}$ раз, чем аналогичное число для структуры типа II.

Установим, как изменяется значение χΙΙ, Ι c увеличением m на 1:

   ${\chi }_{II,I}^{m,m+1}=\frac{2^{t+\left(m+1\right)-k}}{2^{t+m-k}}=2$          (19)

Обобщим результат и определим, как изменяется значение χΙΙ, Ι c увеличением m на произвольное $q\in \mathbb{N}$:

${\chi }_{II,I}^{m,m+q}=\frac{2^{t+\left(m+q\right)-k}}{2^{t+m-k}}=2^q$   (20)

Аналогично определим, как изменяется значение χΙΙΙ, Ι c увеличением m на 1:

   ${\chi }_{III,I}^{m,m+1}=\frac{2^{t+\left(m+1\right)-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{2^{t+m-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}=2$       (21)

Обобщим результат и определим, как изменяется значение cIII, I c увеличением m на произвольное $q\in \mathbb{N}$:

   ${\chi }_{III,I}^{m,m+q}=\frac{2^{t+\left(m+q\right)-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}{2^{t+m-2k}\frac{2^t!}{{\left(2^{t-k}!\right)}^{2^k}}}=2^q$    (22)

Из сравнения (20) и (22) следует, что при увеличении m на произвольное натуральное число q значения величин cII, I и cIII, I изменяются одинаково. Из (18) следует, что величина cIII, II c увеличением m на произвольное натуральное число q не меняется.

Утверждение 9. Величины cII, I и cIII, I не зависят от числа m и при увеличении на q изменяются одинаково в 2q раз.

Утверждение 10. Величина cIII, II не зависит от числа m и при увеличении на q не изменяется.

Отмеченные в настоящем разделе свойства структур типа I, II и III могут учитываться на практике при выборе способа организации СВК на основе ЛКС с применением заданного (m, k)-кода.

Учет числа способов реализации СВК на практике

Рассмотрим примеры применения полученных в исследовании зависимостей.

Пример1. Даны устройства F1(x) и F2(x) с одинаковым числом входов t = 4 и n1 = 10 и n2 = 12 выходами. Определить число способов организации СВК на основе ЛКС с применением (m, k)-кода, удовлетворяющего введенным ранее ограничениям, по структурам типа I, II и III при k = 2 и установить, во сколько раз больше способов построения СВК для устройства F2(x), чем для устройства F1(x), для каждой из структур.

Рассматриваемый пример можно дополнить рис. 2, где приведены устройства и их параметры.

Рис. 2. Заданные устройства F₁(x) и F₂(x).

Используем формулы (1), (2) и (6) и определим числа NI, NII, NIII для структур трех типов, организуемых для устройства F1(x):

     $N_{II}=2^{4+8-2}\left(8+2\right)!=3715891200$

   $N_I=\left(8+2\right)!=10!=3628800$

  $N_{III}=2^{4+8-2\cdot 2}\left(8+2\right)!\frac{2^4!}{{\left(2^{4-2}!\right)}^{2^2}}=58 583 811 686 400 000$  

Аналогично для F2(x) имеем:

$N_I=\left(10+2\right)!=12!=479 001 600$

$N_{II}=2^{4+10-2}\left(10+2\right)!=1 961 990 553 600$

$N_{III}=2^{4+10-2\cdot 2}\left(10+2\right)!\frac{2^4!}{{\left(2^{4-2}!\right)}^{2^2}}=30 932 252 570 419 200 000$

Читатель может найти те же данные в табл. 1–3.

С использованием формулы (8), найдем значение следующего выражения:

   ${\delta }_I^{\mathrm{10,}8}={\left(8+2+2\right)}^{\underset{¯}{2}}=\left(8+2+1\right)\left(8+2+2\right)=11\cdot 12=132$

Далее используем (11) при p = 2:

   ${\delta }_{II}^{\mathrm{10,}8}=2^2{\left(8+2+2\right)}^{\underset{¯}{2}}=2^2\left(8+2+1\right)\left(8+2+2\right)=4\cdot 11\cdot 12=528$  

Формула (13) для рассматриваемого случая p = 2 дает аналогичный результат:

${\delta }_{III}^{\mathrm{10,}8}=2^2{\left(8+2+2\right)}^{\underset{¯}{2}}=528$

Пример 2. Дано устройство F(x) с числом входов t = 4 и выходов n = 16. Требуется установить число способов синтеза СВК на основе ЛКС по структурам всех трех типов с учетом контроля всех выходов на основе (m, k)-кода, удовлетворяющего введенным ранее ограничениям, при k = 2, а также при делении выходов на два подмножества одинаковой мощности и контроля каждого из них на основе аналогичных структур, а также определить, во сколько раз больше окажется число способов синтеза СВК в случае контроля всех выходов на основе одного кода.

Рассматриваемый пример можно проиллюстрировать рис. 3.

Рис. 3. Принцип организации контроля вычислений по рассматриваемому примеру.

Используем те же формулы (1), (2) и (6) и определим числа NI, NII, NIII для структур трех типов, организуемых для устройства F(x) при его контроле на основе заданного кода:

   $N_I=\left(14+2\right)!=16!=20922789888000$

  $N_{II}=2^{4+14-2}\left(14+2\right)!=1371195958099968000$

  $N_{III}=2^{4+14-2\cdot 2}\left(14+2\right)!\frac{2^4!}{{\left(2^{4-2}!\right)}^{2^2}}=21 617932676 414570496\cdot {10}^6$

Разобьем выходы на две группы по 8 выходов в каждой и организуем контроль каждой из них на основе всех трех структур. Получаем следующее число способов организации СВК:

  $N_I={\left(\left(6+2\right)!\right)}^2={\left(8!\right)}^2=1625702400$

  $N_{II}={\left(2^{4+6-2}\left(6+2\right)!\right)}^2=106542032486400$

 $N_{III}={\left(2^{4+6-2\cdot 2}\left(6+2\right)!\frac{2^4!}{{\left(2^{4-2}!\right)}^{2^2}}\right)}^2=264819675286078\cdot 10{}^{14}$

Таким образом, число вариантов организации СВК на основе ЛКС и рассматриваемого (m, k)-кода по структурам типа I и II больше числа вариантов организации СВК для двух выделяемых подмножеств в 12 870 раз. Для структуры типа III число вариантов организации СВК, наоборот, уменьшилось в 1 225 раз.

Могут быть рассмотрены и иные примеры, демонстрирующие эффективность использования установленных в настоящей статье свойств структур типов I, II и III.

Заключение

Большое число способов организации СВК на основе ЛКС с применением (m, k)-кодов позволяет на практике не только синтезировать различные по показателям структурной избыточности устройства с обнаружением неисправностей, но и гораздо проще обеспечивать их самопроверяемость, чем при использовании традиционной структуры, подразумевающей единственную реализацию для выбранного кода (при условии заданных элементной базы и способов синтеза контрольных элементов).

Наибольшей вариативностью обладает структура типа III, позволяющая синтезировать гигантское количество СВК на основе ЛКС с применением (m, k)-кодов. Несколько меньшей вариативностью обладает структура типа II и наименее вариативной является структура типа I, где число способов организации СВК определяется только числом вариантов выбора преобразуемых выходов и перестановками внутри групп преобразуемых и непреобразуемых выходов.

Установленные в ходе исследования закономерности позволяют на практике оценивать общее количество способов синтеза СВК на основе ЛКС с применением (m, k)-кодов и выбирать наилучшие из них для реализации самопроверяемых цифровых устройств.

Наличие большого числа способов синтеза СВК на основе ЛКС является одновременно и достоинством и недостатком, поскольку даже при малых значениях m = 8…10 процедура выбора наилучшего способа по заданному критерию (например, структурной избыточности СВК или равномерности формирования тестовых комбинаций для ее элементов) трудоемка. На практике целесообразно искать квазиоптимальные варианты организации СВК.

Следует также отметить, что здесь не рассматривались некоторые возможные ограничения на процедуру синтеза СВК, например, формирование неполного множества входных воздействий на объект диагностирования или же возможность использования только подмножества кодовых слов заданного (m, k)-кода для организации контроля и пр. Все эти способы будут являться частными случаями рассмотренных и могут быть исследованы дополнительно.

Использование ЛКС с применением (m, k)-кодов – это тот подход, который может оказаться весьма эффективным при синтезе устройств с обнаружением неисправностей для использования в составе систем управления ответственными технологическими процессами.