Weight-based Bose–Lin codes in concurrent error-detection circuit based on Boolean signals correction

Full Text

Введение. Устройства и современные системы критического применения в промышленности и на транспорте должны быть высоконадежными и безопасными. В этой связи первостепенной оказывается задача своевременного обнаружения неисправностей в их структурах и вызываемых тем самым ошибок в вычислениях [1–4]. Решение данной задачи связано с наделением структур составляющих, блоков и отдельных подсистем свойствами контролепригодности, самопроверяемости, отказоустойчивости и безопасного поведения при отказах [5].

Обнаружение неисправностей и их проявлений осуществляется в том числе с помощью самопроверяемых схем встроенного контроля (СВК) [6, 7]. Они могут быть синтезированы по различным принципам большим количеством способов. Широко зарекомендовали себя две типовые структуры организации СВК. Первая из них основана на использовании свойств кодов с повторением и предполагает дублирование исходного устройства и последующее сравнение сигналов на одноименных выходах с помощью самопроверяемого компаратора [8]. Вторая структура организации СВК подразумевает контроль вычислений на выходах исходного устройства по коду паритета: рассчитывается значение свертки по модулю M = 2 для сигналов с выходов контролируемого объекта и сравнивается в СВК со значением функции паритета, вычисленной по значениям входных воздействий на контролируемый объект [9]. У обеих структур есть достоинства и недостатки. Например, в структуре на основе дублирования обнаруживаются любые сочетания искажений на выходах исходного устройства, однако для ряда устройств сложно и даже невозможно обеспечить полную самопроверяемость СВК за счет особенностей структуры компаратора [10]. При этом показатели структурной избыточности для устройства с СВК оказываются существенными, что на практике может приводить к построению устройств, показатели сложности реализации которых в 3–4 раза выше, чем исходного объекта. Кроме того, при дублировании нельзя эффективно учитывать особенности моделей неисправностей, относительно которых и строятся устройства со свойствами самопроверяемости (например, учитывать покрытие любых возникающих неисправностей или наиболее вероятных), что в конечном итоге приводит к использованию излишней избыточности. У структуры, основанной на применении кода паритета, недостаток связан с тем, что любая ошибка с четной кратностью на выходах исходного устройства обнаружена не будет, что потребует специальных схемотехнических методов для построения полностью самопроверяемых структур [6, 9, 11, 12].

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

Отмеченный выше недостаток нивелируется использованием структуры с логической коррекцией сигналов (ЛКС) в СВК, предложенной, по всей видимости, профессорами Сапожниковыми в работе [13] для контроля вычислений на основе свертки по модулю M = 2 и последующего преобразования единственной контрольной функции в самодвойственную. Применение ЛКС дает возможность построения большого числа СВК с контролем вычислений по различным диагностическим признакам [14, 15].

В научной литературе уделено большое внимание синтезу СВК на базе ЛКС с применением для контроля двоичных неразделимых кодов и принадлежности формируемых функций классу самодвойственных [16–20]. Однако организации СВК на основе ЛКС с применением двоичных разделимых кодов посвящено не так много работ. Среди них отметим статью [21], в которой предложено использовать коды Бергера [22] с числом информационных символов m = 3 для контроля вычислений по группам выходов контролируемых устройств, а также работу [23], где этот способ обобщен для применения произвольных кодов Бергера и их известной модификации – кода с суммированием в кольце вычетов по заданному модулю M (остаточных кодов [24, 25]). Предложено рассматривать в качестве базовых кодов для построения СВК на основе ЛКС коды с суммированием в кольце вычетов по модулям M = 4 и 8 (они известны в мире как коды Боуза–Лина [26]).

Настоящая статья посвящена развитию теории синтеза СВК на основе ЛКС с применением свойств модифицированных кодов с суммированием – взвешенных кодов Боуза–Лина. Исследования показывают, что их использование позволяет синтезировать для исходных устройств большое количество СВК с разнообразными показателями эффективности.

1. Взвешенные коды Боуза–Лина. Коды Боуза–Лина, как и другие модульные коды, за счет своих особенностей применяются при синтезе устройств и систем, где требуется обнаружение неисправностей и ошибок в вычислениях [27]. К кодам Боуза–Лина относят разделимые коды, для которых в контрольных векторах записывается значение наименьшего неотрицательного вычета по модулю M ∈ {4, 8, 12} суммы значащих разрядов в информационных векторах (веса информационного вектора) [26]. Характеристики обнаружения ошибок кодами Боуза–Лина на случай их возникновения исключительно в информационных векторах¹ изучены в работах [28–30], во всех разрядах кодовых слов² – в работах [31, 32]. Интересным свойством кодов Боуза–Лина является то, что доля необнаруживаемых ими ошибок в информационных векторах от общего числа ошибок, возникающих в информационных векторах, не зависит от числа m и является постоянной величиной [29]. Кроме того, кодами Боуза–Лина обнаруживаются любые однонаправленные (монотонные) ошибки в информационных векторах, за исключением 100% ошибок кратностью d = jM, j = 1, 2, ... $\overline{)\_}$m/M$\overline{)\_}$, где m – число информационных символов. Эти особенности определяют широкие возможности применения данного класса кодов с суммированием при синтезе устройств и систем с обнаружением неисправностей.

Среди кодов Боуза–Лина в задачах синтеза самопроверяемых цифровых устройств наибольшее распространение получили коды, для которых при построении зафиксирован модуль M = 4 или M = 8. Такие коды имеют соответственно k = 2 и 3 проверочных символа, а при рассмотрении полного множества кодовых слов наблюдается формирование и полного множества контрольных векторов для двух и трех разрядов, что позволяет легко обеспечивать самопроверяемость тестера данного кода [33].

Исследования [34] показывают, что классические коды Боуза–Лина – это только подмножество кодов из множества так называемых взвешенных кодов с суммированием в кольце вычетов по модулю M. При построении таких кодов разрядам f_i информационных векторов предварительно приписывают некоторые весовые коэффициенты $w_i,i=\overline{\mathrm{1,}M-1},$ а затем получают суммарное значение весовых коэффициентов значащих разрядов информационного вектора в кольце вычетов по выбранному модулю – число

$W_M=\left(\sum _{i=1}^m{w}_i{f}_i\right)\left(\mathrm{mod}M\right),$

и записывают его в контрольный вектор. Введем для взвешенных кодов Боуза–Лина следующее обозначение: WS(m, k, M) коды³. Число проверочных символов определяется как k = $⌈{\log }_{2}M⌉$, число WS(m, k, M) кодов –

$N_{WS\left(m,k,M\right)}={\left(M-1\right)}^m.$ (1.1)

К примеру, при M = 4 и m = 4 формула (1.1) дает:

$N_{WS\left(\mathrm{4,}\mathrm{2,}4\right)}={\left(4-1\right)}^4=81$код.

Если рассматриваются характеристики обнаружения ошибок кодами на полном множестве их кодовых слов, то оказывается несущественным, какой из разрядов информационного вектора взвешен каким числом, важными являются только значения самих весовых коэффициентов. Поэтому WS(m, k, M) кодов с различными характеристиками обнаружения ошибок гораздо меньше, чем общее их количество, получаемое по формуле (1.1).

Остановимся на рассмотрении взвешенных кодов Боуза–Лина, при построении которых используются модули M = 4 и 8, поскольку для тестеров данных кодов довольно просто обеспечивается свойство самопроверяемости.

Рассмотрим коды WS(m, 2, 4). Если m = 1, то при подсчете наименьшего неотрицательного вычета весовой коэффициент w₁ может быть выбран из множества {1, 2, 3}. При m = 2 появляется второй разряд в информационном векторе, который также может быть взвешен числами из множества {1, 2, 3}. Таким образом, разряды информационного вектора могут быть взвешены числами из массивов [w₂, w₁] = [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3], т.е. всего шесть вариантов без учета одинаковых по числу сочетаний конкретных весовых коэффициентов (варианты [2, 1], [3, 1] и [3, 2] исключены). Далее при увеличении m до трех имеем следующие варианты взвешивания: [w₃, w₂, w₁] = [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3] (всего 10 вариантов). Процесс увеличения числа вариантов взвешивания может быть проиллюстрирован рис. 1.

 

Рис. 1. Варианты взвешивания при построении WS(m, 2, 4) кодов

 

Анализ числа вариантов взвешивания при построении WS(m, 2, 4) кодов приводит к табл. 1, по которой просматривается закономерность.

 

Таблица 1. Число WS(m, 2, 4) кодов

m	Число WS(m, 2, 4) кодов
1	M – 1 = 4 – 1
2	(4 – 1) + 3
3	((4 – 1) + 3) + 4
4	(((4 – 1) + 3) + 4) + 5
5	((((4 – 1) + 3) + 4) + 5) + 6
…	…
m	(4 – 1) + 3 + 4 + … + (m + 1)

 

Выпишем общую формулу из табл. 1:

$\begin{array}{c}{N}_{WS\left(m,\mathrm{2,}4\right)}=\left(4-1\right)+3+4+\mathrm{...}+\left(m+1\right)=\left(4-1\right)+3+4+\mathrm{...}+\left(m+1\right)+\left(1-1\right)+\left(2-2\right)=\\ =\left(4-1\right)-1-2+\frac{\left(m+1\right)\left(m+2\right)}{2}=\left(4-1\right)-1-2+\frac{\left(m+1\right)\left(m+2\right)}{2}=\frac{\left(m+1\right)\left(m+2\right)}{2}.\end{array}$ (1.2)

Анализ конечного выражения в формуле (1.2) приводит к тому, что

$N_{WS\left(m,\mathrm{2,}4\right)}=C_{m+2}^m=\frac{\left(m+2\right)!}{m!2!}=\frac{\left(m+1\right)\left(m+2\right)}{2}.$ (1.3)

Выражение (1.3) проиллюстрируем на фрагменте треугольника Паскаля (рис. 2). В нем рассмотрение случая m = 1 начинается со строки с номером M – 1 = 4 – 1 = 3 (нумерация строк – сверху вниз, начиная с 0), далее – с увеличением номера строки – по диагонали. Для m = 2 – строка № 4, m = 3 – строка № 5 и т.д. Можно заметить, что последовательность чисел формирует так называемые треугольные числа (последовательность А000217 из работы [35]).

 

Рис. 2. Число способов построения WS(m, 2, 4) и WS(m, 3, 8) кодов

 

Аналогично, но несколько сложнее рассматривается и число способов построения WS(m, 3, 8) кодов. Если m = 1, то при подсчете наименьшего неотрицательного вычета весовой коэффициент w₁ может быть выбран из множества {1, 2, …, 7}. При m = 2 появляется второй разряд в информационном векторе, который также может быть взвешен числами из множества {1, 2, …, 7}. На рис. 3 иллюстрируется процесс увеличения числа вариантов взвешивания при увеличении числа разрядов в информационном векторе.

 

Рис. 3. Варианты взвешивания при построении WS(m, 3, 8) кодов

 

Анализ числа вариантов взвешивания при построении WS(m, 3, 8) кодов приводит к табл. 2, по которой также можно установить закономерность. Читатель вправе обратить внимание на треугольник Паскаля, рассмотренный на рис. 2, и заметить, что число способов взвешивания при m = 1 соответствует второму члену в строке с номером M – 1 = 8 – 1 = 7, при m = 2 – третьему члену в строке с номером 8 и т.д. Суммируя числа по диагонали над числом способов взвешивания при m – 1 с данным числом, получаем общее число вариантов взвешивания для m и т. д. Это последовательность А000579 из [35].

 

Таблица 2. Число WS(m, 3, 8) кодов

m	Число WS(m, 3, 8) кодов
1	N1 = M – 1 = 8 – 1
2	N2 = N1 + 6 + 5 + 4 + 3 + 2 + 1 = 28
3	N3 = N2 + (28 – 7) + ((28 – 7) – 6) + (((28 – 7) – 6) – 5) + ((((28 – 7) – 6) – 5) – 4) + + (((((28 – 7) – 6) – 5) – 4) – 3) + ((((((28 – 7) – 6) – 5) – 4) – 3) – 2) = 28 + 21 + 15 + + 10 + 6 + 3 + 1 = 84
4	N4 = N3 + (84 – 28) + ((84 – 28) – 21) + (((84 – 28) – 21) – 15) + ((((84 – 28) – 21) – – 15) – 10) + (((((84 – 28) – 21) – 15) – 10) – 6) + ((((((84 – 28) – 21) – 15) – 10) – – 6) – 3) = 84 + 56 + 35 + 20 + 10 + 4 + 1 = 210
5	N5 = 210 + 126 + 70 + 35 + 15 + 5 + 1 = 462
…	…
10	N10 = 5005 + 2002 + 715 + 220 + 55 + 10 + 1 = 8008

 

Из анализа числа способов взвешивания при построении WS(m, 3, 8) кодов следует, что

$N_{WS\left(m,\mathrm{3,}8\right)}=C_{m+6}^m=\frac{\left(m+6\right)!}{m!6!}=\frac{\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+6\right)}{720}.$ (1.4)

Свойства WS(m, k, M) кодов будут определяться конкретным сочетанием весовых коэффициентов. Здесь подробно рассматривать их не будем. Некоторые примеры можно найти в работе [34].

Обратимся к особенностям построения схемы встроенного контроля на основе взвешенных кодов Боуза–Лина.

2. Структура организации схем встроенного контроля на базе логической коррекции сигналов с применением взвешенных кодов Боуза–Лина. На рис. 4 изображена структура организации СВК на основе ЛКС [7, 10, 16]. В ней исходным устройством, или объектом диагностирования, является блок F(x), снабженный t входами и n выходами, на которых реализуются булевы функции f₁, f₂, …, f_n. Для организации контроля вычислений организуется СВК. В ней использован принцип ЛКС, подразумевающий возможность преобразования функций f₁, f₂, …, f_n в функции h₁, h₂, …, h_n, которые обладают определенными диагностическими свойствами. Преобразования осуществляются по формуле $h_i=f_i\oplus g_i,i=\overline{\mathrm{1,}n},$ где g_i – i-я функция логической коррекции, вычисляемая блоком контрольной логики G(x). Для контроля вычислений по выбранному диагностическому признаку устанавливается тестер TSC (totally self-checking checker) [6, 7].

 

Рис. 4. Структура организации СВК на основе ЛКС

 

При организации СВК на основе ЛКС с контролем вычислений по WS(m, k, M) кодам функции h₁, h₂, …, h_n формируются таким образом, чтобы вектор их значений на каждой входной комбинации <h_n h_n–1 … h₂ h₁> принадлежал выбранному коду. Контроль соответствия информационных и проверочных символов друг другу осуществляют с помощью самопроверяемого тестера WS(m, k, M) кода.

Достоинством ЛКС является то, что для одного объекта диагностирования при выбранном способе организации СВК и установленном WS(m, k, M) коде существует большое количество вариантов формирования функций h₁, h₂, …, h_n. Это дает возможность синтеза большого количества СВК и, как следствие, оптимизации показателей их эффективности. Определим, какое количество вариантов построения СВК существует при использовании рассматриваемых WS(m, 2, 4) и WS(m, 3, 8) кодов. Для этого установим один из вариантов синтеза СВК на основе ЛКС с применением разделимых кодов, описанный в работе [23]. Подразумевается коррекция только тех рабочих функций объекта диагностирования, которые участвуют в формировании проверочных символов кода Боуза–Лина. В этом случае доопределение функций логической коррекции сигналов, формирующих проверочные символы, является однозначным.

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

$N_{WS(m,k,M)}^{CED}=C_{m+k}^k{P}_m^{}{P}_k^{}=\frac{\left(m+k\right)!}{k!m!}m!k!=\left(m+k\right)!$ (2.1)

Поскольку k = $⌈lo{g}_{2}M⌉$ в конечном выражении (2.1) значение M не присутствует. Для рассматриваемых WS(m, 2, 4) и WS(m, 3, 8) кодов формула (2.1) дает $N_{WS(m,\mathrm{2,}4)}^{CED}=\left(m+2\right)!$ и $N_{WS(m,\mathrm{3,}8)}^{CED}=\left(m+3\right)!$ число способов синтеза СВК. С учетом того, что для каждого значения m возможно различное количество вариантов взвешивания при построении кода, получаем следующее количество способов синтеза СВК на основе WS(m, 2, 4) и WS(m, 3, 8) кодов:

$N_{WS(m,\mathrm{2,}4)}^{CED*}=N_{WS(m,\mathrm{2,}4)}{N}_{WS(m,\mathrm{2,}4)}^{CED}=C_{m+2}^m\left(m+2\right)!$(2.2)

$N_{WS(m,\mathrm{3,}8)}^{CED*}=N_{WS(m,\mathrm{3,}8)}{N}_{WS(m,\mathrm{3,}8)}^{CED}=C_{m+6}^m\left(m+6\right)!$(2.3)

В табл. 3 приведены результаты расчетов по формулам (2.2) и (2.3) для малых значений m. В последней графе вычислен коэффициент ζ, показывающий, во сколько раз число вариантов построения СВК с применением WS(m, 3, 8) кода больше числа вариантов построения СВК с применением WS(m, 2, 4) кода при одинаковых значениях m.

 

Таблица 3. Число вариантов синтеза СВК на основе ЛКС с применением взвешенных кодов Боуза–Лина

m			ζ
3	1 200	30 481 920	25 401.6
4	10 800	762 048 000	70 560
5	105 840	18 441 561 600	174 240
6	1 128 960	442 597 478 400	392 040
7	13 063 680	10 685 567 692 800	817 960
8	163 296 000	261 796 408 473 600	1 603 201.6
9	2 195 424 000	6 544 910 211 840 000	2 981 160
10	31 614 105 600	167 549 701 423 104 000	5 299 840
11	485 707 622 400	4 401 987 610 116 100 000	9 063 040
12	7 933 224 499 200	118 853 665 473 135 000 000	14 981 760
13	137 305 808 640 000	3 300 474 864 292 430 000 000	24 037 401.6
14	2 510 734 786 560 000	94 299 281 836 926 600 000 000	37 558 440
15	48 373 490 221 056 000	2 772 398 886 005 640 000 000 000	57 312 360
16	979 563 176 976 384 000	83 865 066 301 670 600 000 000 000	85 614 760
17	20 801 312 169 910 300 000	2 609 683 533 740 220 000 000 000 000	125 457 640
18	462 251 381 553 562 000 000	83 509 873 079 687 100 000 000 000 000	180 659 001.6
19	10 729 097 856 059 000 000 000	2 747 035 298 673 920 000 000 000 000 000	256 036 000
20	259 644 168 116 627 000 000 000	92 849 793 095 178 400 000 000 000 000 000	357 604 000

 

Отметим, что число вариантов построения СВК на основе ЛКС по взвешенному коду Боуза–Лина существенно увеличивается при увеличении m даже на 1:

$\begin{array}{c}{\delta }_{m+\mathrm{1,}m}^{M=4}=\frac{N_{WS(m+\mathrm{1,}\mathrm{2,}4)}^{CED*}}{N_{WS(m,\mathrm{2,}4)}^{CED*}}=\frac{C_{\left(m+1\right)+2}^{\left(m+1\right)}\left(\left(m+1\right)+2\right)!}{C_{m+2}^m\left(m+2\right)!}=\frac{\frac{\left(m+3\right)!}{\left(m+1\right)!2!}\left(m+3\right)!}{\frac{\left(m+2\right)!}{m!2!}\left(m+2\right)!}=\\ =\frac{\frac{\left(m+2\right)!\left(m+3\right)}{m!\left(m+1\right)}\left(m+2\right)!\left(m+3\right)}{\frac{\left(m+2\right)!}{m!}\left(m+2\right)!}=\frac{{\left(m+3\right)}^2}{m+1}=m+5+\frac{4}{m+1};\end{array}$ (2.4)

$\begin{array}{c}{\delta }_{m+\mathrm{1,}m}^{M=8}=\frac{N_{WS(m+\mathrm{1,}\mathrm{3,}8)}^{CED*}}{N_{WS(m,\mathrm{3,}8)}^{CED*}}=\frac{C_{\left(m+1\right)+6}^{\left(m+1\right)}\left(\left(m+1\right)+6\right)!}{C_{m+6}^m\left(m+6\right)!}=\frac{\frac{\left(m+7\right)!}{\left(m+1\right)!6!}\left(m+7\right)!}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\\ =\frac{\frac{\left(m+6\right)!\left(m+7\right)}{m!\left(m+1\right)6!}\left(m+6\right)!\left(m+7\right)}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\frac{{\left(m+7\right)}^2}{m+1}=m+13+\frac{36}{m+1}.\end{array}$ (2.5)

В табл. 4 представлена зависимость показателей ${\delta }_{m+\mathrm{1,}m}^{M=4}$ и ${\delta }_{m+\mathrm{1,}m}^{M=8}$ от числа m. С ростом m значения данных показателей также возрастают. Как следует из формул (2.4) и (2.5), рост является линейным.

 

Таблица 4. Зависимость показателей ${\delta }_{m+1,m}^{М=4}$ и ${\delta }_{m+1,m}^{М=8}$ от числа m

m	${\delta }_{m+1,m}^{М=4}$	${\delta }_{m+1,m}^{М=8}$
3	9	25
4	9.8	24.2
5	10.667	24
6	11.571	24.143
7	12.5	24.5
8	13.444	25
9	14.4	25.6
10	15.364	26.273
11	16.333	27
12	17.308	27.769
13	18.286	28.571
14	19.267	29.4
15	20.25	30.25
16	21.235	31.118
17	22.222	32
18	23.211	32.895
19	24.2	33.8
20	25.190	34.714

 

Формулы (2.4) и (2.5) могут быть обобщены на случай рассмотрения кодов с m и m + p информационными символами:

$\begin{array}{l}{\delta }_{m+p,m}^{M=4}=\frac{N_{WS(m+p,\mathrm{2,}4)}^{CED*}}{N_{WS(m,\mathrm{2,}4)}^{CED*}}=\frac{C_{\left(m+p\right)+2}^{\left(m+p\right)}\left(\left(m+p\right)+2\right)!}{C_{m+2}^m\left(m+2\right)!}=\frac{\frac{\left(\left(m+p\right)+2\right)!}{\left(m+p\right)!2!}\left(\left(m+p\right)+2\right)!}{\frac{\left(m+2\right)!}{m!2!}\left(m+2\right)!}=\\ =\frac{\frac{\left(m+2\right)!\left(\left(m+2\right)+1\right)\left(\left(m+2\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+2\right)+p\right)}{m!\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)2!}}{\frac{\left(m+2\right)!}{m!2!}\left(m+2\right)!}\times \\ \times \frac{\left(m+2\right)!\left(\left(m+2\right)+1\right)\left(\left(m+2\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+2\right)+p\right)}{\frac{\left(m+2\right)!}{m!2!}\left(m+2\right)!}=\\ =\frac{{\left(\left(\left(m+2\right)+1\right)\left(\left(m+2\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+2\right)+p\right)\right)}^2}{\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)}=\frac{{\left({\left(\left(m+2\right)+p\right)}^{\underset{¯}{p}}\right)}^2}{{\left(m+p\right)}^{\underset{¯}{p}}};\end{array}$ (2.6)

$\begin{array}{l}{\delta }_{m+p,m}^{M=8}=\frac{N_{WS(m+p,\mathrm{3,}8)}^{CED*}}{N_{WS(m,\mathrm{3,}8)}^{CED*}}=\frac{C_{\left(m+p\right)+6}^{\left(m+p\right)}\left(\left(m+p\right)+6\right)!}{C_{m+6}^m\left(m+6\right)!}=\frac{\frac{\left(\left(m+p\right)+6\right)!}{\left(m+p\right)!6!}\left(\left(m+p\right)+6\right)!}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\\ =\frac{\frac{\left(m+6\right)!\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)}{m!\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)6!}}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}\times \\ \times \frac{\left(m+6\right)!\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\\ =\frac{{\left(\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)\right)}^2}{\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)}=\frac{{\left({\left(\left(m+6\right)+p\right)}^{\underset{¯}{p}}\right)}^2}{{\left(m+p\right)}^{\underset{¯}{p}}}.\end{array}$

$\begin{array}{l}{\delta }_{m+p,m}^{M=8}=\frac{N_{WS(m+p,\mathrm{3,}8)}^{CED*}}{N_{WS(m,\mathrm{3,}8)}^{CED*}}=\frac{C_{\left(m+p\right)+6}^{\left(m+p\right)}\left(\left(m+p\right)+6\right)!}{C_{m+6}^m\left(m+6\right)!}=\frac{\frac{\left(\left(m+p\right)+6\right)!}{\left(m+p\right)!6!}\left(\left(m+p\right)+6\right)!}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\\ =\frac{\frac{\left(m+6\right)!\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)}{m!\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)6!}}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}\times \\ \times \frac{\left(m+6\right)!\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)}{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}=\\ =\frac{{\left(\left(\left(m+6\right)+1\right)\left(\left(m+6\right)+1\right)\cdot \mathrm{...}\cdot \left(\left(m+6\right)+p\right)\right)}^2}{\left(m+1\right)\left(m+2\right)\cdot \mathrm{...}\cdot \left(m+p\right)}=\frac{{\left({\left(\left(m+6\right)+p\right)}^{\underset{¯}{p}}\right)}^2}{{\left(m+p\right)}^{\underset{¯}{p}}}.\end{array}$ (2.7)

В формулах (2.6) и (2.7) символом $x^{\underset{¯}{p}}$ обозначена убывающая факториальная степень $x^{\underset{¯}{p}}=x!/\left(x-p\right)!$[36].

С практической точки зрения интерес также представляет рассмотрение случая сравнения числа вариантов построения СВК на основе ЛКС с применением WS(m + 1, 2, 4) и WS(m, 3, 8) кодов. Для таких кодов общее число разрядов в кодовых словах одинаково, и их можно применить при синтезе СВК для объектов диагностирования с одинаковым числом выходов. Пользуясь (2.2) и (2.3), запишем отношение числа вариантов построения СВК на основе ЛКС и WS(m, 3, 8) и WS(m+1, 2, 4) кодов:

$\begin{array}{l}\epsilon =\frac{N_{WS(m,\mathrm{3,}8)}^{CED*}}{N_{WS(m,\mathrm{2,}4)}^{CED*}}=\frac{C_{m+6}^m\left(m+6\right)!}{C_{m+2}^m\left(m+2\right)!}=\frac{\frac{\left(m+6\right)!}{m!6!}\left(m+6\right)!}{\frac{\left(m+2\right)!}{m!2!}\left(m+2\right)!}=\\ =\frac{\frac{{\left(\left(m+2\right)!\right)}^2{\left(\left(m+3\right)\left(m+4\right)\left(m+5\right)\left(m+6\right)\right)}^2}{m!6!}}{\frac{{\left(\left(m+2\right)!\right)}^2}{m!2!}}=\frac{{\left(\left(m+3\right)\left(m+4\right)\left(m+5\right)\left(m+6\right)\right)}^2}{360}.\end{array}$ (2.8)

Из формулы (2.8) становится ясно, что число вариантов построения СВК на базе ЛКС при применении WS(m, 3, 8) кодов существенно выше, чем аналогичный показатель при использовании WS(m + 1, 2, 4). Обратите внимание на то, как стремительно растет значение показателя ε с ростом значения m (см. табл. 5).

 

Таблица 5. Зависимость показателя ε от числа m

m	ε
3	25 401.6
4	70 560
5	174 240
6	392 040
7	817 960
8	1 603 201.6
9	2 981 160
10	5 299 840
11	9 063 040
12	14 981 760
13	24 037 401.6
14	37 558 440
15	57 312 360
16	85 614 760
17	125 457 640
18	180 659 001.6
19	256 036 000
20	357 604 000

 

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

3. Синтез схемы встроенного контроля на основе логической коррекции сигналов с применением взвешенного кода Боуза–Лина. 3.1 Синтез схем встроенного контроля на базе кода с модулем M = 4. Приведем пример синтеза СВК для устройства F(x), снабженного четырьмя входами и восемью выходами, на основе ЛКС с применением WS(6, 2, 4) кода с массивом весовых коэффициентов [w₈, w₇, w₆, w₅, w₄, w₃] = [1, 1, 1, 2, 2, 2]. Для этого используем методику, описанную в работе [23], для преобразования в СВК значений двух рабочих функций.

Устройство с СВК представлено на рис. 5. Основной задачей синтеза является получение описания блока контрольной логики G(x), поскольку элементы преобразования и тестер WS(6, 2, 4) кода (тестер включает в себя кодер и компаратор, образованный одним модулем сжатия парафазных сигналов TRC (two-rail checker) [38]) имеют типовые структуры. Кодеры кодов с суммированием удобно строить на элементной базе, включающей в себя полные сумматоры, полусумматоры и четвертьсумматоры (или сумматоры по модулю M = 2)⁴ [39]. На рис. 6 приведена структура кодера WS(6, 2, 4) кода, синтезированная с помощью данной элементной базы⁵.

 

Рис. 5. Структура организации СВК на основе ЛКС для 8-выходного устройства с применением WS(6, 2, 4) кода

 

Рис. 6. Кодер WS(6, 2, 4) кода: а – схема построения, б – структура

 

Изначально сигналы на выходах блоков СВК не определены. Требуется получить описание работы СВК и значения функций h₁, h₂, …, h₈ на каждой входной комбинации. Значения старших разрядов кодового слова <h₈ h₇ … h₂ h₁> получаются однозначно: h₃ = f₃, h₄ = f₄, …, h₈ = f₈. Далее по правилам построения WS(6, 2, 4) кода получают значения чисел W_M для каждого информационного вектора и записывают в вектор <h₂ h₁> соответствующее двоичное число. Значения функций коррекции получают по формулам g₂ = h₂ ⊕ f₂, g₁ = h₁ ⊕ f₁. Описание работы СВК на каждой входной комбинации дано в табл. 6.

 

Таблица 6. Сигналы на линиях СВК на основе ЛКС с применением WS(6, 2, 4) кода с массивом весовых коэффициентов [1, 1, 1, 2, 2, 2]

x4	x3	x2	x1	f8	f7	f6	f5	f4	f3	f2	f1	h8	h7	h6	h5	h4	h3	h2	h1	g2	g1
0	0	0	0	1	0	0	0	1	0	1	1	1	0	0	0	1	0	1	1	0	0
0	0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	0	1	1	0	1
0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	0	1	0	0	0	0
0	0	1	1	1	1	0	1	0	0	0	1	1	1	0	1	0	0	0	0	0	1
0	1	0	0	0	0	1	1	1	0	0	1	0	0	1	1	1	0	0	1	0	0
0	1	0	1	0	1	0	0	0	0	1	0	0	1	0	0	0	0	0	1	1	1
0	1	1	0	0	1	1	1	0	1	1	0	0	1	1	1	0	1	1	0	0	0
0	1	1	1	1	0	0	0	1	0	1	0	1	0	0	0	1	0	1	1	0	1
1	0	0	0	0	1	0	0	1	0	1	0	0	1	0	0	1	0	1	1	0	1
1	0	0	1	0	0	1	1	0	0	0	1	0	0	1	1	0	0	1	1	1	0
1	0	1	0	1	1	0	1	0	1	0	1	1	1	0	1	0	1	1	0	1	1
1	0	1	1	0	1	0	1	1	0	1	0	0	1	0	1	1	0	0	1	1	1
1	1	0	0	0	1	0	1	0	0	1	1	0	1	0	1	0	0	1	1	0	0
1	1	0	1	1	1	1	0	0	1	1	0	1	1	1	0	0	1	0	1	1	1
1	1	1	0	1	1	0	0	1	0	0	0	1	1	0	0	1	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	1	1

 

Необходимо отметить, что для обеспечения самопроверяемости необходимо выполнение трех условий:

• формирование хотя бы по одному разу тестовых комбинаций для каждого из элементов преобразования (XOR) – комбинаций из множества⁶ {00, 01, 10, 11} [40];
• формирование хотя бы по одному разу каждого контрольного вектора WS(6, 2, 4) кода – векторов {00, 01, 10, 11};
• обнаружение в СВК всех ошибок, вызываемых неисправностями блоков F(x) и G(x).

Из анализа табл. 6 следует, что условия 1 и 2 выполняются. Если бы они не выполнялись, можно было бы выбрать другие преобразуемые функции (это можно сделать в соответствии с формулой (2.1) 8! = 40 320 способами без учета возможностей иного взвешивания разрядов информационного вектора).

Условие 3 можно проверить только при синтезе СВК на конкретной элементной базе по определенному методу (далее этого делать не будем, но при синтезе реального самопроверяемого устройства условие 3 должно быть выполнено).

Синтезируем самопроверяемое устройство и оценим показатели сложности его технической реализации. Будем использовать оценку в метрике числа входов логических элементов внутренней структуры устройства, которая имеет корреляцию с числом транзисторов, занимаемых устройством на кристалле [41]. При синтезе структур применим двухуровневую оптимизацию функций по методу Карно (также не будем использовать скобочных форм при сокращении записей булевых функций). На практике могут применяться и иные методы оптимизации функций и систем функций [42]. Однако в контексте настоящей статьи это не столь принципиально. Отметим, что могут использоваться и другие метрики, например непосредственно число транзисторов, необходимых для реализации устройства, или условный показатель площади, занимаемой устройством на кристалле. Последний показатель применяется в известном интерпретаторе SIS, позволяющем автоматически выполнять процедуры оптимизации булевых функций и структур дискретных устройств, синтезированных в конкретных элементных базисах, и решать некоторые задачи их тестирования [43, 44].

Оптимизация функций, формируемых на выходах объекта диагностирования F(x), дает следующий результат (сами процедуры оптимизации здесь не приведены ввиду их тривиальности):

$f_8={\overline{x}}_4{\overline{x}}_3{\overline{x}}_1\vee {\overline{x}}_4{x}_2{x}_1\vee x_4{x}_2{\overline{x}}_1\vee x_4{x}_3{\overline{x}}_2{x}_1;$

$f_7=x_4{\overline{x}}_1\vee {\overline{x}}_3{x}_2{x}_1\vee x_3{\overline{x}}_2{x}_1\vee {\overline{x}}_4{\overline{x}}_2{x}_1\vee x_3{x}_2{\overline{x}}_1;$

$f_6=x_4{\overline{x}}_2{x}_1\vee {\overline{x}}_4{x}_2{\overline{x}}_1\vee {\overline{x}}_4{x}_3{\overline{x}}_1;$

$f_4={\overline{x}}_3{\overline{x}}_2{\overline{x}}_1\vee x_4{\overline{x}}_3{x}_2{x}_1\vee {\overline{x}}_4{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_4{x}_3{x}_2{x}_1\vee x_4{x}_3{x}_2{\overline{x}}_1;$

$f_3=x_4{x}_3{\overline{x}}_2{x}_1\vee {\overline{x}}_4{x}_2{\overline{x}}_1\vee {\overline{x}}_3{x}_2{\overline{x}}_1;$

$f_2=x_4{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_4{\overline{x}}_3{\overline{x}}_2\vee x_3{x}_1\vee {\overline{x}}_4{x}_3{x}_2\vee x_4{x}_2{x}_1;$

$f_1=x_3{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_4{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_4{\overline{x}}_3{x}_2{x}_1\vee x_4{x}_3{x}_2{x}_1\vee x_4{\overline{x}}_3{\overline{x}}_2{x}_1\vee x_4{\overline{x}}_3{x}_2{\overline{x}}_1.$

Отсюда следует, что сложность реализации блока F(x) в метрике числа входов внутренних логических элементов определяется величиной L_F(x) = 146 усл. ед. Оптимизация функций, реализуемых на выходах блока G(x), приводит к следующему результату:

$g_2=x_4{x}_1\vee x_3{\overline{x}}_2{x}_1\vee x_4{\overline{x}}_3{x}_2;$

$g_1=x_3{x}_1\vee {\overline{x}}_4{x}_1\vee x_2{x}_1\vee x_4{\overline{x}}_3{\overline{x}}_1.$

Сложность реализации блока G(x) определяется величиной L_G(x) = 24 усл. ед. Показатель сложности реализации устройства с СВК находится по формуле

$L_{CED}=L_{F\left(x\right)}+L_{G\left(x\right)}+2L_{XOR}+L_{G\left(f\right)}+L_{TRC}+2L_{NOT},$ (3.1)

где L_CED – показатель сложности реализации устройства с СВК на основе выбранного кода Боуза–Лина⁷, L_XOR = 6 усл. ед. – показатель сложности одного элемента XOR, L_NOT = 1 усл. ед. – показатель сложности инвертора в TSC⁸, L_G(f) = 32 усл. ед. – показатель сложности кодера в TSC, L_TRC = 12 усл. ед. – показатель сложности TRC в TSC. Показатели для кодеров получаются с учетом того, что показатель сложности полного сумматора оценивается величиной L_FA = 14 усл. ед., а полусумматора – L_HA = 6 усл. ед. Данные величины можно найти непосредственно по внутренним структурам сумматора, полусумматора и модуля TRC [33].

Из выражения (3.1) имеем:

$L_{CED}=146+24+2\cdot 6+32+12+2\cdot 1=228$усл. ед.

Для оценки полученной величины и сравнения используем структуру дублирования. Для нее показатель сложности реализации вычисляется по формуле [23]:

$L_D=2L_{F\left(x\right)}+n{L}_{NOT}+\left(n-1\right)L_{TRC},$ (3.2)

где n – число выходов устройства F(x). Следуя за (3.2), запишем:

$L_D=2\cdot 146+8\cdot 1+\left(8-1\right)\cdot 12=384$усл. ед.

Оценим эффективность использования WS(6, 2, 4) кода для синтеза СВК на основе ЛКС по сравнению с применением дублирования:

$\mu =\frac{L_{CED}}{L_D}\cdot 100\%.$ (3.3)

Вычислим показатель μ для рассматриваемого примера:

$\mu =\frac{228}{384}\cdot 100\%=59.375\%.$

Таким образом, устройство, синтезированное на основе ЛКС с преобразованием только тех выходов объекта диагностирования, которые формируют проверочные символы в контрольном векторе WS(6, 2, 4) кода, оказывается более чем в 1.5 раза эффективнее по показателю сложности технической реализации, чем при дублировании.

3.2. Синтез схемы встроенного контроля на базе кода с модулем M = 8. Синтезируем СВК на основе ЛКС для примера из разд. 3.1 с применением другого кода Боуза–Лина – WS(5, 3, 8) кода с массивом весовых коэффициентов [w₈, w₇, w₆, w₅, w₄] = [1, 1, 2, 2, 2]. Структура организации СВК будет выглядеть так, как это представлено на рис. 7.

 

Рис. 7. Структура организации СВК на основе ЛКС для 8-выходного устройства с применением WS(5, 3, 8) кода

 

Отличие структуры рис. 7 от структуры рис. 5 состоит только лишь в том, что символ h₃ здесь является проверочным для WS(5, 3, 8) кода и формируется с применением логической коррекции: h₃ = g₃ ⊕ f₃. Также отличается тестер в структуре СВК: он включает в себя кодер WS(5, 3, 8) кода с показателем сложности L_{G( f )} = 32 усл. ед., изображенный на рис. 8, и два модуля TRC.

 

Рис. 8. Кодер WS(5, 3, 8) кода с массивом весовых коэффициентов [1, 1, 2, 2, 2]: а – схема построения, б – структура

 

Описание работы СВК дается в табл. 7, по которой синтезируется блок G(x). Блок F(x) синтезирован так же, как и в предыдущем примере. При синтезе блока G(x) предварительно оптимизируем функции g₃, g₂ и g₁:

$g_3={\overline{x}}_4{\overline{x}}_3{x}_2\vee {\overline{x}}_3{x}_2{x}_1\vee {\overline{x}}_4{x}_3{\overline{x}}_2{\overline{x}}_1\vee x_4{x}_3{\overline{x}}_2{x}_1\vee x_4{x}_3{x}_2{\overline{x}}_1;$

$g_2=x_4{\overline{x}}_3{x}_1\vee {\overline{x}}_4{x}_2{\overline{x}}_1\vee x_4{x}_2{x}_1\vee {\overline{x}}_4{x}_3{\overline{x}}_2{x}_1;$

$g_1=x_3{x}_1\vee {\overline{x}}_4{x}_1\vee x_2{x}_1\vee x_4{\overline{x}}_3{\overline{x}}_1.$

 

Таблица 7. Сигналы на линиях СВК, реализованной на основе ЛКС с применением WS(5, 3, 8) кода с массивом весовых коэффициентов [1, 1, 2, 2, 2]

x4	x3	x2	x1	f8	f7	f6	f5	f4	f3	f2	f1	h8	h7	h6	h5	h4	h3	h2	h1	g3	g2	g1
0	0	0	0	1	0	0	0	1	0	1	1	1	0	0	0	1	0	1	1	0	0	0
0	0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	0	1	1	0	0	1
0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	0	0	1	0	1	1	0
0	0	1	1	1	1	0	1	0	0	0	1	1	1	0	1	0	1	0	0	1	0	1
0	1	0	0	0	0	1	1	1	0	0	1	0	0	1	1	1	1	0	1	1	0	0
0	1	0	1	0	1	0	0	0	0	1	0	0	1	0	0	0	0	0	1	0	1	1
0	1	1	0	0	1	1	1	0	1	1	0	0	1	1	1	0	1	0	0	0	1	0
0	1	1	1	1	0	0	0	1	0	1	0	1	0	0	0	1	0	1	1	0	0	1
1	0	0	0	0	1	0	0	1	0	1	0	0	1	0	0	1	0	1	1	0	0	1
1	0	0	1	0	0	1	1	0	0	0	1	0	0	1	1	0	0	1	1	0	1	0
1	0	1	0	1	1	0	1	0	1	0	1	1	1	0	1	0	1	0	0	0	0	1
1	0	1	1	0	1	0	1	1	0	1	0	0	1	0	1	1	1	0	1	1	1	1
1	1	0	0	0	1	0	1	0	0	1	1	0	1	0	1	0	0	1	1	0	0	0
1	1	0	1	1	1	1	0	0	1	1	0	1	1	1	0	0	0	1	1	1	0	1
1	1	1	0	1	1	0	0	1	0	0	0	1	1	0	0	1	1	0	0	1	0	0
1	1	1	1	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	1	1

 

 

Отсюда следует, что сложность реализации блока G(x) оценивается величиной L_G(x) = 53 усл. ед.

Показатель сложности реализации устройства с СВК будет определяться как

$L_{CED}=L_{F\left(x\right)}+L_{G\left(x\right)}+3L_{XOR}+L_{G\left(f\right)}+2L_{TRC}+3L_{NOT}.$ (3.4)

По формуле (3.4) имеем:

$L_{CED}=146+53+3\cdot 6+32+2\cdot 12+3\cdot 1=276$усл. ед.

Используя (3.3), сравним полученный показатель для структуры на основе ЛКС с дублированием:

$\mu =\frac{276}{384}\cdot 100\%=71.875\%.$

Устройство, синтезированное на базе ЛКС с преобразованием только тех выходов объекта диагностирования, которые формируют проверочные символы в контрольном векторе WS(5, 3, 8) кода, также оказывается эффективнее по показателям сложности технической реализации, чем при использовании дублирования. Однако, как показывает анализ табл. 7, для тестера не формируются две комбинации – <010> и <111>, что не дает возможности реализации полностью самопроверяемой СВК. В данном случае можно применить тестер, реализуемый на высоконадежных элементах, как “последний сторож”, и обеспечивать обнаружение неисправностей в объекте диагностирования и в других составляющих СВК [5].

Еще одним вариантом обеспечения самопроверяемости является подбор других весовых коэффициентов. В соответствии с формулой (1.4) можно взвесить разряды информационного вектора WS(5, 3, 8) кода следующим числом способов: $N_{WS8\left(\mathrm{5,}3\right)}=C_{5+6}^5=462.$ И это без учета перестановок выходов! Исследования показывают, что самопроверяемая СВК дает WS(5, 3, 8) код с массивом весовых коэффициентов [w₈, w₇, w₆, w₅, w₄] = [2, 3, 4, 4, 2].

В табл. 8 представлены сигналы на линиях СВК, реализованной на основе ЛКС с применением WS(5, 3, 8) кода с массивом весовых коэффициентов [w₈, w₇, w₆, w₅, w₄] = [2, 3, 4, 4, 2]. Кодер данного кода изображен на рис. 9. Показатель сложности его реализации равен L_{G( f )} = = 32 усл. ед. Сложность реализации блока G(x), полученного аналогичным предыдущему способом, определена величиной L_G(x) = 56 усл. ед., поскольку он описывается функциями:

$g_3=x_4{\overline{x}}_1\vee x_4{x}_3{\overline{x}}_2\vee {\overline{x}}_4{\overline{x}}_3{\overline{x}}_2\vee {\overline{x}}_2{x}_3{x}_2;$

$g_2={\overline{x}}_4{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_3{\overline{x}}_2{\overline{x}}_1\vee {\overline{x}}_4{\overline{x}}_3{\overline{x}}_1\vee x_4{x}_3{x}_1\vee x_4{x}_3{x}_2\vee x_3{x}_2{x}_1\vee x_4{x}_3{x}_1;$

$g_1={\overline{x}}_4{\overline{x}}_2\vee x_4{x}_1\vee {\overline{x}}_3{\overline{x}}_2\vee x_3{x}_2{\overline{x}}_1.$

 

Таблица 8. Сигналы на линиях СВК, реализованной на основе ЛКС с применением WS(5, 3, 8) кода с массивом весовых коэффициентов [2, 3, 4, 4, 2]

x4	x3	x2	x1	f8	f7	f6	f5	f4	f3	f2	f1	h8	h7	h6	h5	h4	h3	h2	h1	g3	g2	g1
0	0	0	0	1	0	0	0	1	0	1	1	1	0	0	0	1	1	0	0	1	1	1
0	0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	1	1	1	1	0	1
0	0	1	0	1	0	1	0	0	1	0	0	1	0	1	0	0	1	1	0	0	1	0
0	0	1	1	1	1	0	1	0	0	0	1	1	1	0	1	0	0	0	1	0	0	0
0	1	0	0	0	0	1	1	1	0	0	1	0	0	1	1	1	0	1	0	0	1	1
0	1	0	1	0	1	0	0	0	0	1	0	0	1	0	0	0	0	1	1	0	0	1
0	1	1	0	0	1	1	1	0	1	1	0	0	1	1	1	0	0	1	1	1	0	1
0	1	1	1	1	0	0	0	1	0	1	0	1	0	0	0	1	1	0	0	1	1	0
1	0	0	0	0	1	0	0	1	0	1	0	0	1	0	0	1	1	0	1	1	1	1
1	0	0	1	0	0	1	1	0	0	0	1	0	0	1	1	0	0	0	0	0	0	1
1	0	1	0	1	1	0	1	0	1	0	1	1	1	0	1	0	0	0	1	1	0	0
1	0	1	1	0	1	0	1	1	0	1	0	0	1	0	1	1	0	0	1	0	1	1
1	1	0	0	0	1	0	1	0	0	1	1	0	1	0	1	0	1	1	1	1	0	0
1	1	0	1	1	1	1	0	0	1	1	0	1	1	1	0	0	0	0	1	1	1	1
1	1	1	0	1	1	0	0	1	0	0	0	1	1	0	0	1	1	1	1	1	1	1
1	1	1	1	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	1	1

 

Рис. 9. Кодер WS(5, 3, 8) кода с массивом весовых коэффициентов [2, 3, 4, 4, 2]: а – схема построения, б – структура

 

Пользуясь (3.4), находим:

$L_{CED}=146+56+3\cdot 6+32+2\cdot 12+3\cdot 1=279$усл. ед.

С применением (3.3) оценим полученный показатель для сравнения с показателем сложности реализации структуры на основе дублирования:

$\mu =\frac{279}{384}\cdot 100\%=72.656\%.$

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

Возможность выбора способа взвешивания позволяет на практике добиваться самопроверяемости СВК, а приведенные в данном разделе статьи примеры демонстрируют эффективность использования взвешенных кодов Боуза–Лина при синтезе самопроверяемых устройств.

Заключение. Взвешенные коды Боуза–Лина представляют собой обобщенный класс кодов с суммированием с простыми схемами кодеров, что позволяет их эффективно применять при синтезе СВК. В статье установлено, что число способов взвешивания для построения помехозащищенного кода определяется величинами $N_{WS\left(m,\mathrm{2,}4\right)}=C_{m+2}^m$ и $N_{WS\left(m,\mathrm{3,}8\right)}=C_{m+6}^m$. Таким образом, для заданного m может быть построено большое количество кодов, обладающих различными характеристиками обнаружения ошибок и разными по сложности схемами кодеров. Использование ЛКС для синтеза СВК позволяет построение огромного числа вариантов самопроверяемых устройств и выбора среди них наилучшего по характеристикам. Исследования показывают, что такое количество способов построения устройств в большинстве случаев дает возможность синтеза полностью самопроверяемых структур даже в тех случаях, когда этого не удается добиться использованием типовой структуры на основе дублирования.

Установленные в статье особенности, связанные с изменением числа способов построения СВК на базе ЛКС при помощи взвешенных кодов Боуза–Лина с различными значениями M, могут учитываться при выборе способа реализации самопроверяемых цифровых устройств. Результаты, полученные в работе, могут быть обобщены для случаев произвольных значений модуля, в том числе тех, которые дают наиболее просто обеспечивать самопроверяемость СВК, – модулей

$M\in \left\{2^1,2^2,\mathrm{...,}{2}^{⌈{\log }_2\left(1+\sum _{i=1}^m{w}_i\right)⌉-1}\right\}.$

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

Использование ЛКС совместно с взвешенными кодами Боуза–Лина представляется перспективным направлением в вопросах реализации устройств и систем с обнаружением неисправностей.

 

¹ В такой постановке задача актуальна в тех приложениях кодов Боуза–Лина, в которых устройства вычисления информационных и проверочных символов физически разделены.

² В данной постановке задача актуальна в тех приложениях кодов Боуза–Лина, в которых одно из вычислительных устройств влияет на значения информационных и проверочных символов.

³ WS – от англ. weight-based sum code.

⁴ Полные сумматоры обозначены на рисунках как FA (от англ. full-adder), полусумматоры – как HA (от англ. half-adder). У входов и выходов сумматоров и полусумматоров указаны значения весов разрядов. Такие обозначения используются в ряде изданий, например в работе [26].

⁵ Здесь и далее кодеры синтезированы по методике, подразумевающей уменьшение числа первичных складываемых двоичных чисел, соответствующих весовым коэффициентам, за счет группировки чисел, для сложения которых не требуется операция переноса (у таких чисел в разрядах складываются 0 и значение конкретного информационного символа). Далее кодер синтезирован в виде устройства сложения нескольких двоичных чисел.

⁶ Для тестирования элемента XOR в канонической реализации [39] требуется подать на его входы все четыре входные комбинации. Если используется не каноническая реализация, то число тестовых комбинаций может быть уменьшено: тестовыми являются комбинации либо из подмножества {00, 01, 11}, либо из {00, 01, 10}, либо из {00, 10, 11}, либо из {01, 10, 11}. Но далее рассматривается именно каноническая реализация XOR, так как все остальные реализации будут ее частными случаями, а результаты исследований авторов легко применяются и в этих случаях.

⁷ Нижний индекс CED – от англ. concurrent error-detection.

⁸ Два инвертора устанавливаются либо на выходах G(x), либо на выходах G( f ) для работы в парафазной логике элемента сравнения TRC.

About the authors

Y. I. Yelina

Peter the Great Saint Petersburg Polytechnic University

Author for correspondence.
Email: eseniya-elina@mail.ru
Russian Federation, St. Petersburg

D. V. Efanov

Peter the Great Saint Petersburg Polytechnic University; Russian University of Transport

Email: TrES-4b@yandex.ru
Russian Federation, St. Petersburg; Moscow

References

Supplementary files