О синтезе монотонных комбинационных схем с обнаружением всех одиночных неисправностей

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Вопросы технической диагностики
89
УДК 681. 518. 5:004. 052. 32
О синтезе монотонных комбинационных схем с обнаружением всех одиночных неисправностей
В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов Кафедра «Автоматика и телемеханика на железных дорогах»
Аннотация. Рассматривается задача построения системы функционального контроля комбинационной логической схемы с монотонно независимыми выходами с применением модульных кодов с суммированием. Учет особенностей модульных кодов с суммированием по обнаружению ошибок в информационных векторах позволяет строить системы функционального контроля с уменьшенными аппаратурными затратами по сравнению с системами, построенными по классическим кодам Бергера. Приводятся условия, определяющие применение модульных кодов с суммированием при организации систем функционального контроля комбинационных схем с монотонно независимыми выходами.
Ключевые слова: функциональный контроль- комбинационная схема- монотонность схемы- код Бергера- модульный код с суммированием- информационный вектор- необнаруживаемая ошибка- свойства кодов по обнаружению ошибок.
1 Введение
Во многих отраслях науки и техники для повышения надежности аппаратурных составляющих используется on-line диагностирование, заключающееся в проверке правильности работы устройства или его составляющих в режиме функционирования самого устройства диагностирования [1]. Одним из вариантов организации on-line диагностирования является построение систем функционального контроля [2, 3].
В системе функционального контроля (рис. 1) контролируемое логическое устройство fx), в функции которого входит вычисление системы рабочих булевых функций Уъ f2, • ••, fm, снабжается блоком контрольной логики g (x), формирующим систему контрольных булевых функций g1, g2, …, gk. Таким образом, в произвольный момент времени на выходах обоих блоков системы функционального контроля образуется кодовый вектор & lt-f f … fm gi g2 … gk& gt-, принадлежащий некоторому заранее выбранному систе-
матическому коду [4]. Факт соответствия информационной и контрольной составляющих кодового вектора устанавливается схемой самопроверяемого тестера (СПТ). Тестер имеет два выхода z1 и z2 и при наличии сбоев в любых блоках системы функционального контроля (включая сам тестер) сигнализирует о наличии дефекта непарафазным сигналом & lt-00>- либо & lt-11>- [5].
Входы
Х2 w
Xi w ь
Рис. 1 Система функционального контроля
В качестве основы системы функционального контроля может быть выбран любой систематический код, однако на практике наибольшее распространение получили коды с суммированием [6, 7]. В таких кодах контрольное слово образуется путем суммирования значений определенных информационных разрядов, при этом суммируемые разряды могут быть взвешены [8].
Классический код с суммированием, или код Бергера [9], образуется путем подсчета числа единичных информационных разрядов (веса информационного слова) и записи полученного числа в двоичном виде в контрольное слово. Число контрольных разря-
дов в коде Бергера равно k = |& quot-log2 (m +1)"|,
где m — число информационных разрядов, а
90
Вопросы технической диагностики
запись [b~ обозначает целое сверху от b.
Обозначим код Бергера как S (n, т)-код, где n = т + к — длина кодового слова. В табл. 1 приводятся кодовые векторы S (7, 4)-кода.
Коды Бергера обладают важной особенностью, позволяющей эффективно использовать их для организации систем функционального контроля — ими обнаруживаются любые однонаправленные, или монотонные, ошибки в информационных векторах кодовых слов. При возникновении монотонной ошибки искажаются либо только нулевые разряды, либо только единичные разряды (рис. 2), при этом нарушается значение веса информационного вектора, что фиксируется схемой тестера.
На выходах произвольной комбинационной схемы f (x) могут формироваться различные информационные векторы, что определяется структурой самой схемы. При этом одиночная ошибка произвольного логического элемента или линии связи (сбой, константная неисправность, временная задержка сигнала и пр.) может привести к произволь-
ному искажению информационного вектора, в том числе и к монотонному. Известно [10, 11], что любая комбинационная схема может быть преобразована в схему с независимыми или монотонно независимыми выходами, т. е. в монотонную схему. Функциональный контроль монотонной схемы эффективно организуется по кодам Бергера.
В табл. 2 даны результаты экспериментов, проведенных с системой контрольных примеров MCNC Benchmark Circuits [12] для 20 комбинационных схем. Для каждой схемы в столбцах 2, 3, 4 и 5 указаны число входов и выходов, площадь в условных единицах и дополнительная площадь блока контрольной логики в процентах от площади исходной схемы. Площадь блока контрольной логики рассчитывалась для организации контроля исходных схем по кодам Бергера [13, 14]. Для многих примеров она значительно меньше площади самой комбинационной схемы /х) и в среднем составляет 58,15% от сложности контролируемой схемы.
ТАБЛИЦА 1. Кодовые векторы S (7, 4) и S4(6, 4) кодов
№ Информационные разряды Контрольные разряды
S (7, 4)-код S4(6, 4)-код
/1 /2 /3 /4 g1 g2 g3 g1 g2
0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 1
2 0 0 1 0 0 0 1 0 1
3 0 0 1 1 0 1 0 1 0
4 0 1 0 0 0 0 1 0 1
5 0 1 0 1 0 1 0 1 0
6 0 1 1 0 0 1 0 1 0
7 0 1 1 1 0 1 1 1 1
8 1 0 0 0 0 0 1 0 1
9 1 0 0 1 0 1 0 1 0
10 1 0 1 0 0 1 0 1 0
11 1 0 1 1 0 1 1 1 1
12 1 1 0 0 0 1 0 1 0
13 1 1 0 1 0 1 1 1 1
14 1 1 1 0 0 1 1 1 1
15 1 1 1 1 1 0 0 0 0
Вопросы технической диагностики
91
а)
Информационные Контрольные разряды разряды
& lt- 0 0 0 0 & gt-
II
& lt- 1 1 О О & gt-
& lt- 000 & gt- & lt- О 1 о & gt-
б)
Информационные Контрольные разряды разряды
& lt-0000>- & lt-00>-
& lt- 11 1 1 & gt-
& lt- О О & gt-
Рис. 2 Однонаправленные ошибки: а — в S (7, 4)-коде- б — в S4(6, 4)-коде
Систему функционального контроля можно еще больше упростить, если в качестве основы выбрать модульный код с суммированием, или SM (n, т)-код, где
М_ о1 О2 оГ1о2(т+1)]-1
е 2, 2 ,…, 2 1 — модуль представ-
ления веса информационного вектора [15]. Модульные коды с суммированием имеют меньшее количество контрольных функций за счет модульного принципа подсчета веса. Например, в табл. 1 дан код S4(6, 4), который имеет меньшее количество контрольных разрядов, чем код Бергера S (7, 4). Уменьшение числа контрольных разрядов в системе функционального контроля приводит к сокращению сложности блоков g (x) и СПТ. Недостаток SM (n, т)-кодов — увеличенное количество необнаруживаемых ошибок в сравнении с кодами Бергера, а также возможность возникновения монотонных необнаруживаемых ошибок [16, 17]. В данной статье мы приведем условия построения системы функционального контроля любой монотонной схемы по SM (n, т)-кодам.
ТАБЛИЦА 2. Сложность блока контрольной логики g (x)
Название схемы Число входов Число выходов Площадь Площадь блока g (x), %
1 2 3 4 5
cm138a 6 8 480 12
cmb 16 4 888 40
cu 14 11 1168 75
decod 5 16 744 0
ldd 9 19 2352 21
vda 17 39 19 536 12
x2 10 7 1056 62
misex1 8 7 1448 36
misex2 25 18 2448 53
rd84 8 4 3128 44
bw 5 28 3064 14
term1 34 10 7944 37
z4m1 7 4 1192 84
alu2 10 6 7264 77
dalu 75 16 35 128 38
5xp1 7 10 2432 94
clip 9 5 4088 73
c8 28 18 2320 138
ttt2 24 21 4648 116
la1 26 19 2832 137
Среднее значение 58,15
92
Вопросы технической диагностики
2 Синтез монотонных схем
Организовать систему функционального контроля произвольной комбинационной схемы можно путем преобразования самой схемы в схему с независимыми либо монотонно независимыми выходами, а затем использовать для контроля код с возможностью обнаружения всех однонаправленных искажений [10, 11, 13, 18].
Комбинационная схема называется монотонной в том случае, если любая неисправность любого элемента ее внутренней структуры вызывает искажение только одного выхода или группы выходов с однонаправленными искажениями (только 1−0 или только 0-- 1).
В [18] показано, что произвольная комбинационная схема может быть преобразована в монотонную схему. Определено понятие немонотонного элемента в комбинационной схеме. Неисправность такого элемента вызывает противоположные искажения сигналов на различных выходах схемы (как 1-& gt-0, так и 0-& gt-1). Кроме метода [18], можно использовать и другие способы получения монотонных схем, например, описанные в [10, 19]. Однако метод из [18] дает возможность получения схем с минимальной избыточностью.
Преобразование любой комбинационной схемы в монотонную схему производится следующим образом [18].
1. Определяется множество W немонотонных элементов.
2. Анализируются пути в схеме, ведущие от немонотонных элементов к выходам схемы. Если есть элемент на пути от немонотонного элемента к выходу, он также включается во множество W.
3. Каждый элемент yt е W дублируется: элемент yi удаляется и заменяется двумя копиями у0 и у1.
4. В полученной структуре входы и выходы элементов соединяются по следующим правилам:
¦ если в исходной схеме выход элемента у- соединен со входом элемента у- и соединение содержит четное число инверсий (при
этом учитываются инверсии выхода элемента уi и входа элемента у), то в преобразованной схеме соединяются элементы yi и у- с одинаковыми верхними индексами, в противном случае — с разными верхними индексами-
¦ если элемент yi не был дублирован, то его выход соединяется с обеими копиями элемента у--
¦ если выходной элемент yi на своем выходе имеет инверсию, то соответствующий выход схемы соединяется с элементом у1, в
противном случае — с у0-
¦ все элементы, не связанные с выходами схемы, удаляются.
В работе [18] показано, что на практике сложность преобразованной схемы в среднем не увеличивается более чем на 16% от сложности исходной схемы. Это значительно меньше, чем при организации контроля по методу дублирования (табл. 3). В табл. 3 представлены результаты экспериментов с 20 контрольными примерами MCNC Benchmark Circuits. Табл. 3 аналогична табл. 2, за исключением последнего столбца, где представлена дополнительная площадь в процентах от площади исходной комбинационной схемы.
Рассмотрим произвольную комбинационную схему (рис. 3). Ее логические элементы обозначены порядковыми номерами и реализуют произвольные функции алгебры логики (без привязки к конкретным логическим операциям). Монотонность схемы означает, что если в ней есть логический элемент, связанный с несколькими выходами, то все пути от него к каждому выходу содержат одинаковое по четности количество инверсий [18]. Исходя из этого, изображенная на рис. 3 комбинационная схема не является монотонной: в ней логический элемент № 2 связан со всеми четырьмя выходами, при этом пути к выходам z1 и z2 содержат нечетное количество инверсий, а пути к выходам z3 и z4 — четное.
Вопросы технической диагностики
93
ТАБЛИЦА 3. Сложность преобразованной схемы fix)
Название схемы Число входов Число выходов Площадь Дополнительная площадь преобразованной схемы fx), %
cm138a 6 8 480 0
cmb 16 4 888 8
cu 14 11 1168 20
decod 5 16 744 0
ldd 9 19 2352 6
vda 17 39 19 536 3
x2 10 7 1056 5
misex1 8 7 1448 5
misex2 25 18 2448 14
rd84 8 4 3128 20
bw 5 28 3064 63
term1 34 10 7944 6
z4m1 7 4 1192 22
alu2 10 6 7264 69
dalu 75 16 35 128 47
5xp1 7 10 2432 2
clip 9 5 4088 5
c8 28 18 2320 0
ttt2 24 21 4648 9
la1 26 19 2832 9
Среднее значение 15,65
Преобразование схемы по приведенному алгоритму приводит к увеличению сложности самого контролируемого устройства. При организации системы функционального контроля гарантированно может быть применен известный код Бергера либо с учетом характеристик по обнаружению монотонных искажений — модульный код с суммированием. Так, уменьшение модуля и выбор его из
множества M e|2,4,…, 2^log2^m+1^ *j дают
возможность сократить число контрольных разрядов по сравнению с кодом Бергера, что снижает и сложность реализации всех компонентов контрольного оборудования системы диагностирования (блока контрольной логики g (x) и тестера).
3 Новый подход к синтезу монотонных схем
Используя модульные коды с суммированием можно строить более простые системы функционального контроля. Необходимо, однако, при этом учитывать монотонные искажения, которые появляются при подсчете по модулю M веса информационного вектора. Например, из табл. 1 видно, что кодовые векторы & lt-0000>- и & lt-1111>- ?4(6, 4)-кода, различные по истинному весу, имеют одинаковый вес по модулю M = 4. Искажение кратности d = 4 каждого из этих векторов приведет к возникновению необнаруживаемой ошибки. Эта ошибка будет монотонной.
Утверждение 1. Модульные коды с суммированием имеют однонаправленные необнаруживаемые ошибки только кратностей M, 2M, …, iM (iM& lt-m) — однонаправлен-
94
Вопросы технической диагностики
ных необнаруживаемых ошибок других кратностей у модульных кодов нет.
Данное свойство объясняется тем, что при подсчете веса информационного вектора кода по модулю M все информационные слова с весами r, r + M, ., r + iM будут иметь одинаковые контрольные слова. Ошибка будет необнаруживаемой тогда и только тогда, когда информационный вектор с данным контрольным словом перейдет в информационный вектор с таким же контрольным словом. Переходы же между векторами с различным весом с одинаковыми контрольными словами будут входить, в том числе и в класс однонаправленных (монотонных). Пример монотонного перехода дан на рис. 2, б для S4(6, 4)-кода.
Определим условия применения модульных кодов с суммированием для контроля произвольных комбинационных схем до этапа преобразования их в монотонные схемы. Для этого введем следующую характеристику схемы: (а = 0 или 1) — максимальное
четное число выходов, связанных с одним логическим элементом при помощи путей с четным (а = 0) [нечетным (а = 1)] числом инверсий. Из утверждения 1 и свойств монотонных схем можно заключить следующее.
Утверждение 2. В любой монотонной схеме с m выходами все одиночные неисправности логических элементов обнаруживаются на основе применения модульного кода SM (n, m), где M = 2^log2 b| и n = т + |& quot- log2 b & quot-|, если
Cx & lt- b. (1)
Для рассматриваемой выше комбинационной схемы (рис. з) 4. x = 2 и tLx = 2. Отсюда следует, что b = 3 и контроль данной схемы целесообразно осуществлять по модульному коду S4(6, 4), а не по коду Бергера S4(7, 4).
Рассмотрим еще несколько примеров. Пусть, например, комбинационная схема имеет m = 20 выходов. Если в ней tmax = 0, то для организации ее функционального контроля наилучшее решение дает применение S2(21, 20)-кода- если tmax = 3, то S4(22, 20) —
кода- если tmax = 7, то S8(23, 20)-кода, если
Cx = 15, то S16(24, 20)-кода, и если ^ & gt- 16, необходимо брать код Бергера.
Утверждение 3. Если tmax = M, то контроль монотонной схемы может быть организован по коду SM'-(n, m), где M'- - ближайший модуль счета, больший, чем значение модуля M (M'- = 2log2 M+1).
В табл. 4 приводятся диапазоны значений tmax и наилучший вариант кодирования в этом случае.
ТАБЛИЦА 4. Наилучшие коды для монотонных схем
t" max Код
0,1 S2(n, т)
2,3 S4(n, т)
4.7 S8(n, т)
8. 15 S16(n, т)
16. 31 S32(n, т)
2^log2(tmax +1)]-1 2[l0g2(tmax+1)] j SJlog2 (ax +l)]() S 2 (n, т)
4 Свойства модульных кодов с суммированием
В [16, 17] установлены некоторые свойства по обнаружению ошибок SM (n, т)-кодами, однако они определяют только общее количество кратных необнаруживаемых искажений. Рассмотрим свойства модульных кодов с суммированием по обнаружению монотонных искажений в информационных разрядах.
С использованием специально разработанного программного обеспечения были рассчитаны числа необнаруживаемых однонаправленных искажений в информационных векторах SM (n, т)-кодов с параметрами M = 2,4,8,16 и т = 2. 20, а затем и величины и, характеризующие долю числа однонаправленных необнаруживаемых ошибок от общего количества необнаруживаемых ошибок для каждого кода (табл. 5).
Табл. 5 дополняется графиками зависимостей и от т для различных SM (n, т)-кодов (рис. 4). По данным графикам можно определить тенденции изменения значений и при изменении длин информационных векторов различных модульных кодов с суммированием. Отметим, что у всех модульных кодов
Вопросы технической диагностики
95
при m & lt- M нет однонаправленных необнаруживаемых ошибок.
Для S2(n, т)-кодов (кодов паритета) характерно монотонное уменьшение значения и от величины 0,5 до 0 с увеличением т. При этом, к примеру, доля однонаправленных ошибок в классе необнаруживаемых ошибок информационных векторов у кода S2(11, 10) составляет 10,9%, а у кода S2(21, 20) — всего 0,6%.
ТАБЛИЦА 5. Значения величин и в зависимости от т
т и
S2(n, т) S4(n, т) S8(n, т) S16(n, т)
2 0,5 0 0 0
3 0,5 0 0 0
4 0,446 429 0,35 714 0 0
5 0,375 0,83 333 0 0
6 0,303 427 0,120 968 0 0
7 0,239 583 0,138 889 0 0
8 0,186 085 0,137 918 0,159 0
9 0,142 923 0,124 081 0,748 0
10 0,108 935 0,104 116 0,1 955 0
11 0,82 598 0,83 165 0,3 737 0
12 0,62 407 0,64 233 0,5 821 0
13 0,47 038 0,48 565 0,7 827 0
14 0,35 396 0,36 291 0,9 409 0
15 0,26 606 0,26 994 0,10 351 0
16 0,19 985 0,20 077 0,10 593 3,3277−10−9
17 0,15 004 0,14 967 0,10 209 2,9 141 110−8
18 0,1 126 0,11 191 0,9 351 1,34 878 10 7
19 0,8 449 0,8 389 0,8 201 4,38 651 10 7
20 0,6 339 0,0063 0,6 926 1,12 474−10−6
У модульных кодов с суммированием с M& gt- 4 характер изменения и другой: с увеличением длины информационного вектора от значения т = M величина и сначала увеличивается, достигая некоторого максимума, а затем уменьшается до нуля. Например, для S4(n, т)-кодов максимум достигается при т = 7, а для S8(n, т)-кодов — при т = 16 (см. рис. 4). С увеличением значения M максимум доли однонаправленных ошибок в классе необнаруживаемых смещается в сторону увеличения длины информационного вектора и уменьшается по величине. Так, для S8(n, т)-кодов максимум и в 13,11 раза меньше соответствующей величины для S4(n, т)-кодов.
В табл. 6 приводятся рассчитанные характеристики S2(n, т)-кодов. Кодами
S2(n, т) не обнаруживаются однонаправленные искажения всех четных кратностей d = 2, 4, …, iM (здесь i = 1, 2,… и i & lt- т). В столбцах N и N приведены соответственно числа необнаруживаемых однонаправленных искажений в информационных разрядах и общее количество необнаруживаемых ошибок в информационных разрядах. В графе и записана доля однонаправленных ошибок от общего их количества в классе необнаруживаемых при данной длине информационного вектора т.
0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 т
Рис. 4 Зависимость и от значения т для различных модульных кодов
Ч)
ТАБЛИЦА 6. Распределение однонаправленных необнаруживаемых ошибок в кодах S2(n, т)
m Число необнаруживаемых однонаправленных ошибок кратности d К N и
2 4 6 8 10 12 14 16 18 20
2 2 2 4 0,5
3 12 12 24 0,5
4 48 2 50 112 0,4464
5 160 20 180 480 0,375
6 480 120 2 602 1984 0,3034
7 1344 560 28 1932 8064 0,2396
8 3584 2240 224 2 6050 32 512 0,1861
9 9216 8064 1344 36 18 660 130 560 0,1429
10 23 040 26 880 6720 360 2 57 002 523 264 0,1089
И 56 320 84 480 29 568 2640 44 173 052 2 095 104 0,0826
12 135 168 253 440 118 272 15 840 528 2 523 250 8 384 512 0,0624
13 319 488 732 160 439 296 82 368 4576 52 1 577 940 33 546 240 0,047
14 745 472 2 050 048 1 537 536 384 384 32 032 728 2 4 750 202 134 201 344 0,0354
15 1 720 320 5 591 040 5 125 120 1 647 360 192 192 7280 60 14 283 372 536 838 144 0,0266
16 3 932 160 14 909 440 16 400 384 6 589 440 1 025 024 58 240 960 2 42 915 650 2 147 418 112 0,02
17 8 912 896 38 993 920 50 692 096 24 893 440 4 978 688 396 032 10 880 68 128 878 020 8 589 803 520 0,015
18 20 054 016 100 270 080 152 076 288 89 616 384 22 404 096 2 376 192 97 920 1224 2 386 896 202 34 359 476 224 0,0113
19 44 826 624 254 017 536 444 530 688 309 583 872 94 595 072 12 899 328 744 192 15 504 76 1 161 212 892 137 438 429 184 0,0084
20 99 614 720 635 043 840 1 270 087 680 1 031 946 240 378 380 288 64 496 640 4 961 280 155 040 1520 2 3 484 687 250 549 754 765 312 0,0063
Вопросы технической диагностики
Вопросы технической диагностики
97
Подобные таблицы были составлены для модульных кодов с суммированием с M = 2, 4, 8, 16. Анализ характеристических таблиц позволил установить некоторые свойства модульных кодов, которые могут быть полезными при синтезе контролепригодных систем.
Свойство 1. Коды, у которых длина информационного вектора кратна модулю счета, имеют две необнаруживаемые однонаправленные ошибки максимальной кратности т.
Это свойство объясняется тем, что при т = M только два вектора с различным весом оказываются в одной контрольной группе -это векторы, состоящие только из нулей, и векторы, состоящие только из единиц. Для кода ?4(6, 4) это векторы & lt-0000>- и & lt-1111>-. Взаимные переходы друг в друга для данных векторов — это и есть однонаправленные искажения кратности т. Таких переходов два.
Свойство 2. Модульные коды с суммированием имеют одинаковое количество необнаруживаемых однонаправленных ошибок данной кратности при одинаковом числе информационных разрядов для любого М.
Из этого свойства следует, что если из табл. 6 удалить столбцы d = 2, 6, 10, 14, 18 то получим характеристическую таблицу для S4(n, т)-кодов, поэтому достаточно иметь подобную таблицу лишь для кодов с модулем M = 2. Из нее можно получить все характеристические таблицы и для других модульных кодов.
Интересным является следующее свойство.
Свойство 3. Доля однонаправленных необнаруживаемых ошибок в информационных разрядах кратности d от общего числа необнаруживаемых ошибок данной кратности не зависит от числа информационных разрядов и является постоянной величиной при любом значении М.
Значения долей монотонных необнаруживаемых ошибок в информационных разрядах кратности d от общего числа необнаруживаемых ошибок данной кратности (обозначим их ud) приведены в табл. 7.
Можно заметить, что значения величин ud для модульных кодов с суммированием с M = 2 и M = 4 с увеличением кратности необнаруживаемой ошибки образуют последовательность убывающих по одному и тому же закону чисел (табл. 8).
ТАБЛИЦА 7. Значения величин ud
Код Д (оли монотонных необнаруживаемых ошибок от общего числа необнаруживаемых ошибок
2 4 6 8 10 12 14 16 18 20
S2(n, m) 0,5 0,125 0,3 125 0,7 813 0,1 953 0,488 0,122 3,05 10−5 7,63 10−6 1,91 10−6
S4(n, m) 0 0,25 0 0,15 625 0 0,977 0 6,1 10−5 0 3,81 10−6
S8(n, m) 0 0 0 0,27 778 0 0 0 0,121 0 0
S16(n, m) 0 0 0 0 0 0 0 0,155 0 0
ТАБЛИЦА 8. Последовательности величин ud для S2(n, m) и S4(n, m) кодов
M = 2 M = 4
j d Ud j d Ud
0 2 2−1 0,5 0 4 2−2 0,25
1 4 2−3 0,125
2 6 2−5 0,3 125 1 8 2−6 0,15 625
3 8 2−7 0,7 813
4 10 2−9 0,1 953 2 12 2−10 0,977
5 12 2−11 0,488
6 14 2−13 0,122 3 16 2−14 6,110−5
7 16 2−15 3,05 10−5
8 18 2−17 7,63 T0−6 4 20 2−18 3,81-Ш-6
9 20 2−19 1,91 10−6
Ud = 2-l-jM Ud = 2−2-jM
98
Вопросы технической диагностики
Рассмотрим выражения, характеризующие величины ud для S2(n, m) и S4(n, m) ко-
дов. Для S2(n, т)-кодов ud = 2 1 jM
1
2 • 2jjM ,
а для S4(n, т)-кодов ud = 2 2 jM
1
4 • 2jM '-
Заметим также, что величина j = 0,1,…, являющаяся порядковым номером существующих кратностей необнаруживаемых однонаправленных ошибок в модульных кодах, зависит от кратности ошибки и модуля сче-
. d.
та: j =---1, здесь d — величина, кратная
M
модулю. Отсюда следует, что по формуле (2) можно подсчитать значения величины ud для S2(n, m) и S4(n, m) кодов:
1
d
2jM • M
¦ = 2-jMM-1
= 2
-m| -11 2M-d
.M) m-1 = --
M
(2)
Подсчитаем по этой формуле долю однонаправленных ошибок кратности d = 16 в классе необнаруживаемых у S4(18, 16)-кода:
2M — d 2 4−16
ud = ----= ----= 2−14 = 6,1 • 10−5.
d M 4
Свойство 3, по всей видимости, связано со свойством постоянства доли необнаруживаемых ошибок информационных разрядов кратности d от общего числа ошибок этой же кратности в информационных разрядах для модульных кодов с суммированием [16, 17]. Данную величину обозначим pd, ее значения для различных кодов с суммированием приводятся в табл. 9.
Аналогичной особенностью обладают и классические коды с суммированием, что доказано в работе [20]. Там же определено и выражение, характеризующее долю необнаруживаемых ошибок кратности d от общего числа ошибок данной кратности:
d
Pd = 2~dC]. (3)
Из формулы (3) следует, что величина pd не зависит от длины информационного вектора и одинакова для любого кода Бергера. Также можно отметить тот факт, что значение величины pd для SM (n, m)-кодов совпадает со значением этой же величины для классических S (n, m)-кодов при d & lt- M [16, 17].
Сравнивая табл. 7 и табл. 9, можно получить долю однонаправленных необнаруживаемых ошибок от общего числа ошибок в информационных векторах модульных кодов.
ТАБЛИЦА 9. Значения характеристики pd
Код Доля необнаруживаемых ошибок кратности d от общего числа ошибок той же кратности
2 4 6 8 10 12 14 16
S (n, m) 0,5 0,375 0,3125 0,27 344 0,24 609 0,22 559 0,20 947 0,19 638
S16(n, m) 0,5 0,375 0,3125 0,27 344 0,24 609 0,22 559 0,20 947 0,19 641
S8(n, m) 0,5 0,375 0,3125 0,28 125 0,26 563 0,25 781 0,25 391 0,25 195
S4(n, m) 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5
S2(n, m) 1 1 1 1 1 1 1 1
5 Характеристики тестеров модульных кодов с суммированием
Покажем эффект от сокращения сложности системы функционального контроля на упрощении структуры тестера в сравнении с тестером кода Бергера (см. рис. 1).
Тестер любого кода с суммированием строится по структуре, содержащей блок генератора контрольных разрядов и блок компаратора (рис. 5) [5]. Генератор по значени-
ям выходов блока основной логики вычисляет контрольные разряды g, g2, …, g'-k, а компаратор сравнивает сформированные разряды g[ c одноименными разрядами,
сформированными блоком контрольной логики g (x). При этом контрольные разряды от блока контрольной логики предварительно инвертируются. Таким образом, компаратор осуществляет сравнение одноименных парафазных сигналов. В случае соответствия
Вопросы технической диагностики
99
сигналов — g (х) = g (х) на выходах компаратора формируется парафазный сигнал & lt-01>- либо & lt-10>-. Любой дефект внутренней структуры тестера нарушает парафазность выходов.
Генераторы тестеров кодов с суммированием строятся с использованием стандартных функциональных модулей: полного
сумматора (FA), полусумматора (HA) и сумматора по модулю два (XOR) [5, 7, 21, 22]. На рис. 6 приведены примеры генераторов 5(7,4), S4(6,4) и S2(5,4) кодов.
4^
Рис. 5 Структура тестера кода с суммированием
Компараторы строятся на базе стандартных модулей сжатия парафазных сигналов -блоков TRC (two-rail checker) [3, 5]. Число таких модулей в схеме тестера зависит от
числа контрольных разрядов выбранного варианта кодирования и равно величине k — 1. Например, для S (7, 4)-кода потребуется 2 модуля TRC.
Сложность технической реализации схем оценивается числом входов логических элементов без учета инверсий на входах, и для рассмотренных нами функциональных блоков
равна [5]: lfa = 21, lha = 8 LXOR = 6, LTRC = 12. Учитывая это, генераторы, приведенные на рис. 7, имеют значения сложности LS (7,4) = 45, LS4(6, 4) = 36, LS2(5, 4) = 18, а компараторы соответственно — Ls (7, 4) = 24, Ls4(6, 4) = 12, Ls2(5, 4) = 0. Видно, что уменьшение значения M снижает сложность технической реализации как блоков генераторов, так и блоков компараторов. В итоге, как следствие, уменьшается и сложность тестера в целом. В табл. 10−12 приводятся значения сложности тестеров различных кодов с суммированием. В каждой таблице в нижней строке представлена величина 5 — отношение значения сложности тестера S (n, т)-кода и сложности тестера SM (n, т)-кода при данном значении числа выходов комбинационной схемы. По значению 5 можно определить, во сколько раз эффективнее применение модульного кода по сравнению с кодом Бергера.
g 3
gl
g 2
Рис. 6. Структурные схемы генераторов для кодов с суммированием с m = 4 информационными разрядами: а — для S (7, 4)-кода- б — S4(6, 4)-кода- в — S2(5, 4)-кода
100
Вопросы технической диагностики
ТАБЛИЦА 10. Сравнение характеристик сложности для тестеров S (n, m) и S8(n, m) кодов
m 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
LS (n, m) 20 33 69 82 95 120 176 189 202 215 228 258 271 284 352 365 378 391 404
LS8(n. m) 20 33 69 82 95 120 155 168 181 194 207 237 250 263 303 316 329 342 355
5 1 1 1 1 1 1 1,14 1,13 1,12 1,11 1,1 1,09 1,08 1,08 1,16 1,16 1,15 1,14 1,14
ТАБЛИЦА 11. Сравнение характеристик сложности для тестеров S (n, m) и S4(n, m) кодов
m 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
LS (n, m) 20 33 69 82 95 120 176 189 202 215 228 258 271 284 352 365 378 391 404
LS4(n, m) 20 33 48 61 74 87 104 117 130 143 156 167 180 193 222 235 248 261 274
5 1 1 1,44 1,34 1,28 1,38 1,69 1,62 1,55 1,5 1,46 1,54 1,51 1,47 1,59 1,55 1,52 1,5 1,47
ТАБЛИЦА 12. Сравнение характеристик сложности для тестеров S (n, m) и S2(n, m) кодов
m 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
LS (n, m) 20 33 69 82 95 120 176 189 202 215 228 258 271 284 352 365 378 391 404
LS2(n, m) 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114
5 3,33 2,75 3,83 3,42 3,17 3,33 4,19 3,94 3,74 3,58 3,45 3,58 3,47 3,38 3,91 3,8 3,71 3,62 3,54
6 Заключение
Зная свойства модульных кодов с суммированием по обнаружению монотонных ошибок в информационных векторах и учитывая свойства контролируемой комбинационной схемы, можно строить системы функционального контроля с уменьшенной сложностью контрольного оборудования по сравнению с системами, построенными методом [18] и методом дублирования.
Библиографический список
1. Nicolaidis M., Zorian Y. On-line Testing for VLSI — А Compendium of Approaches // Journal of Electronic Testing: Theory and Applications. -№ 12.- 1998. — Pp. 7−20.
2. Touba N. A., McCluskey E. J. Logic Synthesis of Multilevel Circuits with Concurrent Error Detection // IEEE Trans. Computer-Aided Design of Integrated Circuits and System, Vol. 16, Jul. 1997, pp. 783−789.
3. Lala P. K. Self-Checking and Fault-Tolerant Digital Design. — San Francisco: Morgan Kaufmann Publishers, 2001. — 216 p.
4. Ryan W. E., Shu Lin Channel Codes: Classical and Modern. — Cambridge University Press, 2009. — 708 р.
5. Сапожников, В. В. Самопроверяемые дискретные устройства / В. В. Сапожников, Вл. В. Сапожников. — Санкт-Петербург: Энерго-атомиздат, 1992. — 224 с. — ISBN 5−283−4 605−2.
6. Kastensmidt F. L., Carro L., Reis R. Fault-Tolerance Techniques for SRAM-based FPGAs. -Dordrecht: Springer, 2006. — 183 p.
7. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. — John Wiley & amp- Sons, 2006. — 720 p.
8. Das D., Touba N. A. Weight-Based Codes and their Application to concurrent error detection of multilevel circuits // Proc. 17th IEEE Test Symposium, California, USA, 1999, pp. 370−376.
9. Berger J. M. A note on error detection codes for asymmetric channels // Information and Control. — 1961. — Vol. 4. — Issue 1. — Pp. 68−73.
10. Согомонян, Е. С. Самопроверяемые устройства и отказоустойчивые системы / Е. С. Согомонян., Е. В. Слабаков. — Москва: Радио и связь, 1989. — 208 с. — ISBN 5−256−308−9.
11. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs / A. Morosow, V. V. Saposhnikov, Vl. V. Saposhnikov, M. Goessel // VLSI Design. — 1998. — V. 5. — Issue 4. — Pp. 333 345.
12. SIS: A System for Sequential Circuit Synthesis / E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. L. Sangiovan-ni-Vincentelli // EECS Department University of California, Berkeley Technical Report No. UCB/ ERL M92/41, 1992. — 52 p.
13. Design of Self-Checking Unidirectional Combinational Circuits with Low Area Overhead / V. V. Saposhnikov, Vl. V. Saposhnikov, A. Moro-sov, M. Goessel // Proceedings of 2nd IEEE Interna-
Вопросы технической диагностики
101
tional On-line Testing Workshop (IOLTW), Biarritz, France, 1996. — Pp. 56−67.
14. A New Design Method for Self-Checking Unidirectional Combinational Circuits / Saposhni-kov V. V., Morosov A., Saposhnikov Vl. V., Goes-sel M. // Journal of Electronic Testing: Theory and Applications. — 1998. — V. 12. — Issue 1−2 (February /April). — Pp. 41−53.
15. Bose B., Lin D. J. Systematic Unidirectional Error-detection Codes // IEEE Trans. Comput. -V. C-34, Nov. 1985. — Pp. 1026−1032.
16. Properties of code with summation for logical circuit test organization / A. Blyudov, D. Efanov, V. Sapozhnikov, Vl. Sapozhnikov // Proc. of 10th IEEE East-West Design & amp- Test Symposium (EWDTS'-2012), Kharkov, Ukraine, September 1417, 2012.- Pp. 114−117.
17. Коды с суммированием для организации контроля комбинационных схем / А. А. Блюдов, Д. В. Ефанов, В. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. — 2013. -№ 6. — С. 153−164.
18. Метод построения комбинационных са-мопроверяемых устройств с обнаружением всех
одиночных неисправностей / В. В. Сапожников, Вл. В. Сапожников, М. Гессель, А. А. Морозов // Электронное моделирование. — 1998. — Т. 20. -№ 6. — С. 70−80.
19. Матросова, А. Ю. Обнаружение несуще-
ственных путей логических схем на основе совместного анализа И-ИЛИ деревьев и SSBDD-графов / А. Ю. Матросова, С. А. Останин,
В. Сингх // Автоматика и телемеханика. — 2013. -№ 7. — С. 126−142.
20. Ефанов, Д. В. О свойствах кода с суммированием в схемах функционального контроля Д. В. Ефанов, В. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. — 2010. -№ 6. — С. 155−162.
21. Marouf M. A., Friedman A. D. Design of Self-Checking Checkers for Berger Codes // Proc. of 8th Annual International Conference on Fault-Tolerant Computing, Toulouse, 1978. — V. C-27. -Pp. 179−183.
22. Piestrak S.J. Design of Self-Testing Check-
ers for Unidirectional Error Detecting Codes / Wroclaw: Oficyna Wydawnicza Politechniki
Wroclavskiej, 1995. — 111 p. — ISSN 0324−9786.

ПоказатьСвернуть
Заполнить форму текущей работой