Контроль комбинационных схем на основе кодов с суммированием с одним взвешенным информационным разрядом

Проектирование и тестирование логических устройств

УДК 681.518.5:004.052.32

Вал. В. Сапожников, д-р техн. наук,

Вл. В. Сапожников, д-р техн. наук,

Д. В. Ефанов, канд. техн. наук

Кафедра «Автоматика и телемеханика на железных дорогах», Петербургский государственный университет путей сообщения Императора Александра I

КОНТРОЛЬ КОМБИНАЦИОННЫХ СХЕМ НА ОСНОВЕ КОДОВ С СУММИРОВАНИЕМ ЕДИНИЧНЫХ И ОДНОГО ВЗВЕШЕННОГО РАЗРЯДОВ

При построении надежных и безопасных систем управления часто используют функциональный контроль технического состояния логических блоков. При организации подобных систем должно обеспечиваться свойство 100 %-го обнаружения одиночных неисправностей на выходах логических элементов внутренней структуры контролируемого объекта, что возможно за счет применения нескольких подходов: 1) дублирования; 2) использования помехоустойчивых кодов без модификации структур объектов диагностирования; 3) использования помехоустойчивых кодов с модификацией структур объектов диагностирования. Выбор кода на этапе проектирования системы функционального контроля является определяющим фактором, влияющим на основные характеристики системы. В работе приводятся результаты исследований свойств кодов с суммированием, имеющих один взвешенный информационный разряд. Эти коды, как и классические коды Бергера, обнаруживают 100 % монотонных ошибок в информационных векторах, а значит, могут быть применимы при решении задач технической диагностики, аналогичных тем, для решения которых используются коды Бергера. Более того, новые коды обладают уменьшенным количеством так называемых симметричных ошибок в сравнении с кодами Бергера. При этом, однако, взвешивание разряда приводит к появлению некоторого количества асимметричных ошибок. Приводятся условия построения взвешенного кода с суммированием, который обладает возможностью 100 %-го обнаружения ошибок нечетных кратностей и монотонных ошибок в информационных векторах. Кроме того, установлены новые свойства кодов с суммированием с одним взвешенным информационным разрядом, учет которых на практике позволит организовывать системы функционального контроля логических устройств с улучшенными характеристиками.

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

Введение

При построении надежных систем автоматики и вычислительной техники часто используются принципы помехоустойчивого кодирования. Применение кодирования подразумевает внесение избыточности в логическое устройство на аппаратном или программном уровнях, что способствует решению таких задач, как обнаружение или исправление ошибок, являющихся следствиями нарушения надежности работы самих устройств. При исправлении ошибок вносится существенная избыточность, что значительно увеличивает и сложность самого устройства, и его энергопотребление, что в конечном итоге влияет на стоимость разработки устройства и его эксплуатации. Часто в связи с этим используют коды с обнаружением ошибок, имеющие, по сравнению с кодами с исправлением ошибок, меньшую избыточность и позволяющими реализовывать логические устройства с уменьшенной сложностью технической реализации. Это способствует сокращению затрат на их изготовление и использование. Тем не менее теряется свойство исправления ошибок. На практике оказывается вполне достаточным обнаружить неисправность в момент ее проявления до возникновения следующей неисправности. Именно по этой причине системы с обнаружением отказов, базирующиеся на простых кодах с небольшой избыточностью, нашли широкое применение.

В данной статье мы опишем особенности перспективного класса кодов - кодов с суммированием единичных и одного взвешенного разрядов, -учет которых позволяет организовывать системы функционального контроля комбинационных логических схем с минимальными затратами на производство.

1 Особенности построения систем функционального контроля

Для проверки правильности вычислений в процессе работы некоторой логической схемы F(x) организуется система ее функционального контроля (рис. 1) [1-3]. В ней исходное логическое устройство, определяющее на входном векторе <x1 x2 ... x> значения системы булевых функций <f f ... f>, снабжается специальным контрольным оборудованием, включающим в себя блок контрольной логики и самопроверяемый тестер [4-9]. Блок контрольной логики G (x) формирует на тех же входных векторах, что и блок F (x), значения системы контрольных функций <gx g2 ... g>, а тестер проверяет соответствие между значениями рабочих (информационных) и контрольных функций. Тестер для изображенных на рис. 1 структур систем функционального контроля строится на основе каскадного соединения генератора контрольных разрядов G и компаратора TRC. Генератор по значениям рабочих функций <f f ... f>

a)

Рабочие

выходы

Контрольные

выходы

Рабочие

выходы

Контрольные

выходы

Рабочие

выходы

Контрольные

выходы

Рис. 1. Подходы к организации контролепригодных систем: а - дублирование; б - применение помехоустойчивых кодов без модификации структуры F

определяет значения контрольных функций <g*1 g*2 ... g*k>, а компаратор сравнивает их с одноименными функциями, вычисленными блоком G (х). При этом последние предварительно инвертируются с целью организации компаратора в виде схемы сжатия парафазных сигналов и контроля единственного парафазного сигнала на выходах компаратора.

При раздельной реализации контролируемого устройства и блока контрольной логики на этапе проектирования системы функционального контроля можно поставить в соответствие выходам схемы F(x) некоторый информационный вектор длиной т, а выходам блока G(x) - контрольный вектор длиной к [10, 11]. Это позволяет формализовать правила построения контрольного оборудования, а также установить ключевые характеристики системы функционального контроля: аппаратурную избыточность и свойства обнаружения ошибок в контролируемом устройстве.

В системах управления ответственными технологическими процессами важным является обеспечение свойства 100 %-го обнаружения одиночных неисправностей на выходах логических элементов внутренней структуры объекта диагностирования [12]. Существуют две стратегии приобретения данного свойства (см. рис. 1). Первая заключается в организации системы дублирования, что требует, однако, значительных аппаратурных затрат. Вторая состоит в использовании некоторого помехоустойчивого кода, чаще всего кода с обнаружением ошибок, который позволяет идентифицировать некоторый процент искажений на контролируемых выходах объекта диагностирования, и последующей модификации структуры самого объекта диагностирования с учетом свойств выбранного кода в контролеприродную структуру. Такие подходы при использовании кодов паритета и кодов Бергера описаны, например, в [4, 13-15]. Они дают для некоторых случаев систем функционального контроля меньшую аппаратурную избыточность, чем при организации дублирования. Структуры контролируемых логических схем могут не допускать на выходах самой схемы формирования полного множества 2т информационных векторов. Более того, кратности ошибок на выходах схем могут быть ограничены. Поэтому для реальных логических схем правильный выбор помехоустойчивого кода с учетом их структуры может обеспечить 100 %-е обнаружение одиночных неисправностей без модификации структуры контролируемой схемы. В работах [16-18] приведены примеры контрольных комбинационных схем, для которых такой выбор того или иного помехоустойчивого кода позволяет построить контролепригодную структуру.

Алгоритмы модификации структур контролируемых схем базируются на свойствах обнаружения ошибок кодами. Классическими кодами с суммированием, или кодами Бергера [19], обнаруживаются любые монотонные (однонаправленные) искажения в информационных векторах, что и используется при построении контролепригодных структур логических схем [20-24]. Монотонной является такая ошибка, которая происходит при искажении толь-

ко нулевых или только единичных разрядов. Все остальные ошибки являются немонотонными. Коды Бергера не обнаруживают лишь часть немонотонных ошибок [25], однако при модификации структур контролируемых схем используется только свойство обнаружения 100 % монотонных ошибок. Анализ показывает, что ошибки в информационных векторах можно классифицировать более детально, что позволяет уточнить алгоритмы модификации структур контролируемых схем и соответственно обеспечить создание систем со 100 %-м обнаружением всех одиночных неисправностей при минимальных аппаратурных затратах. Так, в [26] предлагается разделять немонотонные ошибки на симметричные и асимметричные. Симметричные ошибки происходят при искажениях одинакового количества нулевых и единичных разрядов, а асимметричные - при различных количествах искажаемых нулевых и единичных разрядов. Коды Бергера как раз не обнаруживают 100 % симметричных ошибок в информационных векторах, но при этом обнаруживают любые асимметричные ошибки. Классификация ошибок дается на рис. 2, а их примеры - на рис. 3. Можно и далее расширять классификацию, например, вводя степени асимметрии (по количеству искажаемых нулевых или единичных разрядов при возникновении ошибки) и уровни симметрии (кратности симметричных ошибок), хотя это вызывает существенное усложнение процедуры анализа структур контролируемых схем.

Рис. 2. Классификация ошибок в информационных векторах

а)

б)

«)

< 0 1 0 1 >  т

< 1 1 1 1 >

< 0 1 0 1 > т

< 1 0 0 1 >

< 0 1 0 1 >

т

< 1 0 1 1 >

Рис. 3. Ошибки в информационных векторах: а - монотонная; б - симметричная; в - асимметричная

Существуют два пути решения задачи организации структуры системы функционального контроля со 100 %-м обнаружением одиночных неисправностей на выходах внутренних элементов контролируемых устройств: изучение свойств известных кодов с обнаружением ошибок и применение их на практике или же построение новых кодов с обнаружением различных видов ошибок, имеющих улучшенные показатели. Известно множество таких модификаций [27-31], позволяющих получать коды с различными характеристиками обнаружения ошибок в информационных векторах - как по виду, так и по кратности. Например, применение кодов с суммированием по модулю M не позволяет обнаружить 100 % монотонных ошибок кратностей M, 2M, ..., iM (iM < m) и 100 % симметричных ошибок в информационных векторах, но сокращает аппаратурную избыточность системы функционального контроля. Для реальных схем, в которых невозможны некоторые виды ошибок на рабочих выходах, применение модульного кода может быть вполне эффективным [32, 33].

Рассмотрим коды с суммированием единичных и одного взвешенного информационных разрядов. Взвешенному разряду соответствует вес w, -некоторое натуральное число. Все остальные правила построения остаются такими же, как у классических кодов Бергера. Такой код, как будет показано далее, обнаруживает любые монотонные ошибки в информационных векторах, имеет уменьшенное количество симметричных необнаруживаемых ошибок в сравнении с кодами Бергера, но при этом не обнаруживает некоторое количество асимметричных ошибок.

2 Классические и модифицированные коды с суммированием

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

Алгоритм 1. Получение разрядов контрольных векторов кодов Бергера.

1. Подсчитывается суммарное число единичных разрядов в информационном векторе (вес r информационного вектора).

2. Число r представляется в двоичном виде и записывается в разряды контрольного вектора.

Код Бергера обозначим как S (m, к)-код. Количество контрольных разрядов в нем к = |~ log2(m +1) -, запись l”...-] обозначает целое сверху от вычисляемого значения.

Такой подход к построению кода с суммированием определяет его возможности в обнаружении ошибок: поскольку все информационные векторы с одинаковым весом имеют одинаковые контрольные векторы, кодами Бергера обнаруживаются любые ошибки в информационных векторах, кроме симметричных. Их количество может быть рассчитано по формуле [11]:

N

S

m,

= Y

d=2

f d

m— 2

d d '2 C 2

'm^m-r

v Cr C.

d

r=—

V 2

где d - кратность необнаруживаемой ошибки (d - четное число).

Формула (1) получена на основе анализа табличной формы задания кода с суммированием, в которой все информационные векторы распределены по контрольным группам, соответствующим контрольным векторам кода. Количество ошибок подсчитывается по всем контрольным группам по каждой кратности. В табл. 1 для примера задан S (5,3)-код.

Таблица 1. S (5,3)-код

Вес

0 1 2 3 4 5

Контрольный вектор

000 001 010 011 100 101

Информационные векторы

00000 00001 00011 00111 01111 11111

00010 00101 01011 10111

00100 00110 01101 11011

01000 01001 01110 11101

10000 01010 10011 11110

01100 10101

10001 10110

10010 11001

10100 11010

11000 11100

Использование формулы (1) позволяет доказать важную особенность кодов Бергера - ими вне зависимости от длины информационного вектора не обнаруживается постоянная величина доли ошибок с четной кратностью d от общего количества ошибок данной кратностью в информационных векторах [11]:

d_

vd = 2~dQ.

S(m, ^-кодами не обнаруживается 50 % двукратных ошибок, 37,5 % четырехкратных ошибок, 31,25 % шестикратных ошибок и т. д.

Формула (1) может быть приведена к виду [34]:

Ns

Данная формула проще, чем формула (1), однако она не дает возможности подсчета количества ошибок по каждой кратности, что при решении практических задач диагностики может иметь существеннее значение [16, 35].

Следует заметить, что S (m, к)-коды имеют еще одну важную особенность: информационные векторы между контрольными векторами распределены крайне неравномерно, а некоторые контрольные векторы могут не использоваться (см. табл. 1). Не меняя свойств обнаружения ошибок S (m, к)-кодом, но меняя правила их построения, можно добиться уменьшения количества необнаруживаемых ошибок. Например, для рассмотренного выше кода S (5,3) половину информационных векторов в контрольных группах <010> и <011> можно было бы переместить в неиспользуемые контрольные группы <110> и <111> (табл. 2). Классический код S (5,3) не обнаруживает 240 ошибок в информационных векторах, а модифицированный - 180, что в 1,33 раза меньше. Однако подобные модификации возможны не для любых длин информационных векторов и носят ограниченный характер.

Таблица 2. Модифицированный S(5,3)-код

Вес

0 1 2 3 4 5 6 7

Контрольный вектор

000 001 010 011 100 101 010 111

Информационные векто ры

00000 00001 00011 00111 01111 11111 01100 10101

00010 00101 01011 10111 10001 10110

00100 00110 01101 11011 10010 11001

01000 01001 01110 11101 10100 11010

10000 01010 10011 11110 11000 11100

Существует предел уменьшения количества необнаруживаемых ошибок в информационных векторах при заданных значениях m и k [36].

Теорема 1. Оптимальным по критерию минимума количества необнаруживаемых ошибок в информационных векторах для данных значений m и k является такой систематический помехоустойчивый код, у которого все 2m информационных вектора равномерно распределены между 2k контрольными векторами.

Число необнаруживаемых ошибок в оптимальном коде рассчитывается по формуле:

N5 = 2m

Поскольку число, рассчитанное по формуле (4), является абсолютным минимумом общего количества необнаруживаемых ошибок в информацион-

ных векторах, с ним можно сравнивать общее количество необнаруживаемых ошибок в рассматриваемых кодах:

%

m,k

N

где запись (m, k) обозначает произвольный систематический код.

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

Для сравнения: классический S (5,3)-код имеет значение коэффициента

эффективности %S

N min

7V5,3 NS

96

240

0,4, а модифицированный S (5,3)-код,

заданный в табл. 2, %

S

Nmin

5,3

N

S

96

180

= 0,533.

Улучшение свойств обнаружения ошибок кодами достигается, например, действиями по следующем алгоритму [36-38].

Алгоритм 2. Получение разрядов контрольных векторов модифицированных кодов Бергера.

1. Подсчитывается вес информационного вектора г.

2. Выбирается модуль M = 2^log2 (m+1)l 1.

3. Определяется наименьший неотрицательный вычет числа г по установленному модулю: г (modM).

4. Подсчитывается специальный поправочный коэффициент а как сумма по модулю два заранее выбранных (в общем случае произвольных) информационных разрядов.

5. Подсчитывается результирующий вес информационного вектора W = г (modM) + aM.

6. Число W представляется в двоичном виде и записывается в разряды контрольного вектора.

Получаемые по алгоритму 2 модифицированные коды Бергера обнаруживают почти вдвое больше ошибок, чем классические. Но они имеют в классе необнаруживаемых ошибки всех видов. Это накладывает ограничение на их использование при организации систем функционального контроля [16].

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

Алгоритм 3. Получение разрядов контрольных векторов взвешенных кодов Бергера.

1. Одному из разрядов в информационном векторе приписывается весовой коэффициент w - некоторое натуральное число, а всем остальным -коэффициент, равный единице.

2. Подсчитывается суммарное число взвешенных единичных разрядов в информационном векторе (вес W информационного вектора).

3. Число W представляется в двоичном виде и записывается в разряды контрольного вектора.

Полученный таким образом взвешенный код с суммированием обозначим как WS(m,k,w)-mR.

Отметим, что взвешенными могут быть несколько разрядов информационного вектора [19, 30, 39], но далее будет показано, что даже взвешивание одного из них приводит к хорошим результатам при улучшении свойств обнаружения ошибок кодом [40-42].

3 Необнаруживаемые ошибки во взвешенных кодах с суммированием

Значение весового коэффициента взвешенного информационного разряда может быть выбрано из множества wе{1; 2;...; m}, что дает возможность получения кодов с суммированием с различными распределениями необнаруживаемых ошибок по кратностям. Все коды с суммированием с одним взвешенным информационным разрядом при w > m имеют одинаковые распределения необнаруживаемых ошибок по кратностям, при этом общее их количество минимально для данного значения длины информационного вектора [42]. Минимум количества необнаруживаемых ошибок достигается благодаря смещению половины информационных векторов в контрольные группы с большим значением веса векторов, чем истинный вес г. Отсюда следует, что при w > m общее количество необнаруживаемых ошибок в WS (m, k, w)-кодах равно удвоенному общему количеству необнаруживаемых ошибок в S (m - 1, к*)-кодах (k* = k или k - 1):

NWS

В табл. 3 задан WS (5,4,5)-код. Из данной таблицы следует, что в WS (5,4,5)-коде количество необнаруживаемых ошибок в два раза больше количества необнаруживаемых ошибок в информационных векторах S(4,3)-кода.

Для объяснения того факта, что все взвешенные коды с wm > m имеют одинаковые распределения необнаруживаемых ошибок по кратностям в табл. 4 задан WS (5,4,6)-код. Из таблицы видно, что группа с весом 5 является пустой.

Таблица 3. WS (5,4,5)-код

Вес

0 1 2 3 4 5 6 7 8 9

Контрольный вектор

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Информационные векторы

00000 00001 00011 00111 01111 10000 10001 10011 10111 11111

00010 00101 01011 10010 10101 11011

00100 00110 01101 10100 10110 11101

01000 01001 01110 11000 11001 11110

01010 11010

01100 11100

Таблица 4. WS (5,4,6)-код

Вес

0 1 2 3 4 5 6 7 8 9 10

Контрольный вектор

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010

Информационные векторы

00000 00001 00011 00111 01111 10000 10001 10011 10111 11111

00010 00101 01011 10010 10101 11011

00100 00110 01101 10100 10110 11101

01000 01001 01110 11000 11001 11110

01010 11010

01100 11100

Поскольку общее количество ошибок кратностью dравно 2mC<m, а доля необнаруживаемых ошибок данной кратностью в кодах Бергера постоянна и определяется по формуле (2), общее количество необнаруживаемых ошибок кратностью d можно подсчитать следующим образом [11]:

d

Ns

Учитывая формулу (7) и то, что в WS (m, к, w > m)-коде ровно вдвое больше необнаруживаемых ошибок, чем в S (m - 1, к*)-коде, получим еще одну формулу расчета количества необнаруживаемых ошибок кратностью d в WS (m, к, w > m)-кодах:

NWS

= 2 • 2

m-d-1

Г2Г d

d m-

= 2

m-d

Г2Г d ^d '^'m-1'

Для любых значений w количество необнаруживаемых ошибок определяется выражением [42]:

wm -1

N

= 2 (cm - ОК - cm- -1)+

ir-1

WS

r=1

+ V (er - er-1 + er-wm)(er - er-1 + er-wm - i) +

/L v'-'m ^m-i' ^m-1 Л^m ^m-1 ^ ^m-1 L) ^

r=wm

m+wm -2

+ 2m cw (emTm - o-

r=m+1

В частности, для кодов Бергера формула (9) имеет вид [38]:

m

Ns (m,k)=2 em (em - о.

r=0

В качестве примера приведем расчеты по формуле (9) для рассмотренного выше WS (5,4,5)-кода:

N

WS

2(C

5r - ej-1 )(Cb - er-1 -1)+2 (er - er-1 + c;

r=1 r=5

5xc;- - e;-1 + e

-1)+

+2 ej-5(e;-5 -1) =

r=6

=(C1 - C40)(e5 - C;0 -1)+(C2 - e4)(e52 - cj -1)+(C53 - e2)^3 - e42 -1)+

+(c54 - C;3)(c54 - ej -1) + (c5 - C;4 + C40)(e55 - cj + еЦ -1) +

+c4(cj -1)+c42(c42 -1)+ej (ej -1) =

= 12 + 30 +12 +12 + 30 +12 = 108.

Расчеты общего количества необнаруживаемых WS(m,k,w)-кодами ошибок в информационных векторах для длин информационных векторов m = 1^15 представлены в табл. 5, коэффициенты эффективности этих кодов, рассчитанные по формуле (5), представлены в табл. 6.

Используя формулы (6) и (8), можно предложить более простые формулы подсчета общего количества необнаруживаемых ошибок в WS (m, k, w)-кодах в двух частных случаях - при w = m - 1 и w = m - 2:

Nws(m,k,m-1) = 2C2mm-2 - 2m + 2 = 2^ - 2m-1 +1);

d

n = 2m-d e 2 ed + ?•

lyWS(m,k,m-1) ^ W '“'m-1 ^

2016, December, vol. 2, No 4 Automation on Transport

Таблица 5. Общее количество необнаруживаемых WS (т, к, и’)-кодами ошибок в зависимости от веса взвешенного разряда

m w

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 0

2 2 0

3 12 6 4

4 54 36 26 24

5 220 164 124 110 108

6 860 680 530 460 442 440

7 3304 2710 2160 1852 1744 1722 1720

8 12614 10612 8610 7336 6790 6636 6610 6608

9 48108 41244 33964 28868 26348 25468 25260 25230 25228

10 183732 159864 133344 113352 102336 97848 96522 96252 96218 96216

11 703384 619404 522504 444984 398472 377154 369744 367844 367504 367466 367464

12 2700060 2401608 2046308 1747856 1555994 1459436 1421398 1409848 1407230 1406812 1406770 1406768

13 10392408 9322632 8015128 6871062 6092328 5669312 5485128 5421372 5404168 5400672 5400168 5400122 5400120

14 40100216 36237136 31408286 27033916 23909366 22100416 21245276 20916376 20814716 20790016 20785466 20784868 20784818 20784816

15 155084752 141043942 123148792 106446652 94014232 86416642 82568512 80953912 80396992 80241382 80206984 80201188 80200488 80200434 80200432

576 Design and test of logical devices

Автоматика на транспорте № 4, том 2, декабрь 2016

Таблица 6. Коэффициенты эффективности WS (т, к, и')-кодов в зависимости от веса взвешенного разряда

т W

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 -

2 0 -

3 0,66667 0 0

4 0,2963 0,44444 0,61538 0,66667

5 0,43636 0,58537 0,77419 0,29091 0,2963

6 0,52093 0,65882 0,36226 0,41739 0,43439 0,43636

7 0,58111 0,33063 0,41481 0,4838 0,51376 0,52033 0,52093

8 0,30442 0,36185 0,44599 0,52345 0,56554 0,57866 0,58094 0,58111

9 0,32992 0,38483 0,46732 0,54981 0,6024 0,62321 0,62835 0,3044 0,30442

10 0,35112 0,40354 0,4838 0,56913 0,63039 0,65931 0,32888 0,3298 0,32992 0,32992

11 0,36978 0,41991 0,49779 0,58451 0,65273 0,3421 0,34895 0,35076 0,35108 0,35112 0,35112

12 0,38684 0,43491 0,51042 0,59758 0,33431 0,35643 0,36597 0,36897 0,36966 0,36977 0,36978 0,36978

13 0,4028 0,44903 0,52228 0,30402 0,34288 0,36847 0,38084 0,38532 0,38655 0,3868 0,38683 0,38684 0,38684

14 0,41797 0,46253 0,26656 0,30969 0,35017 0,37883 0,39407 0,40027 0,40223 0,4027 0,40279 0,4028 0,4028 0,4028

15 0,43251 0,23767 0,2722 0,31492 0,35656 0,38791 0,40599 0,41408 0,41695 0,41776 0,41794 0,41797 0,41797 0,41797 0,41797

Проектирование и тестирование логических устройств 577

Nws

d

Nws

Формулы (11) - (14) следуют непосредственно из формул (6) и (8) и табличных форм задания WS (m, к, ш)-кодов (табл. 7 и 8).

Таблица 7. WS(5,4,4)-код

Вес

0 1 2 3 4 5 6 7 8

Контрольный вектор

0000 0001 0010 0011 I 0100 0101 0110 0111 1000

Информационные векторы

00000 00001 00011 00111 01111 10001 10011 10111 11111

00010 00101 01011 10000 10010 10101 11011

00100 00110 01101 10100 10110 11101

01000 01001 01110 11000 11001 11110

01010 11010

01100 11100

Сравним таблицы 3 и 7. Таблица задания WS(5,4,4)-кода фактически была получена «сдвигом» всех столбцов с номерами 5-10 таблицы задания Ж5(5,4,5)-кода на один столбец влево. В результате в контрольной группе № 4, где присутствовал только один вектор <01111>, появился еще один вектор -<10000>. Это привело к увеличению количества необнаруживаемых ошибок в WS(5,4,4)-коде на 2 по сравнению с WS(5,4,5)-кодом.

Таблица 8. WS(5,4,3)-код

Вес

0 1 2 3 4 5 6 7

Контрольный вектор

000 001 010 011 100 101 010 111

Информационные векто ры

00000 00001 00011 00111 01111 10011 10111 11111

00010 00101 01011 10001 10101 11011

00100 00110 01101 10010 10110 11101

01000 01001 01110 10100 11001 11110

01010 10000 11000 11010

01100 11100

Аналогично можно пояснить и формулы (13) и (14). Из сравнения таблиц 3, 7 и 8 следует, что при получении таблицы задания WS (5,4,3)-кода был фактически произведен сдвиг контрольных групп WS (5,4,5)-кода на две позиции влево или на одну позицию влево относительно таблицы задания WS (5,4,4)-кода. Для объяснения формул (13) и (14) удобнее анализировать сдвиг на одну контрольную группу (сравните таблицы 7 и 8). В группу № 3, где присутствовало Cm-2 = m -1 = 4 вектора, был добавлен C^ — = 1 вектор. В группу № 4, где находился Cm- = 1 вектор, было добавлено Clm-l = m -1 = 4 вектора. Таким образом, количество необнаруживаемых ошибок в WS (5,4,3)-коде по сравнению с аналогичной величиной в WS (5,4,4)-коде изменилось: было добавлено 2m(m -1) необнаруживаемые ошибки, но и не стало 2(m - 1)(m - 2) необнаруживаемых ошибок, которые давали группы № 3 и № 5, а также 2 необнаруживаемые ошибки из группы № 4. Разница составила:

А = 2m(m -1) - 2 - 2(m - 1)(m - 2) = 2m2 - 2m - 2 - 2(m2 - 3m + 2) = 2m2 - 2m - 2 - 2m2 + 6m - 4 = 4m - 6.

Прибавляя величину А к числу необнаруживаемых ошибок в WS (m, к, m - 1)-кодах (см. формулы (11) и (12)), получаем формулы (13) и (14) для подсчета количества необнаруживаемых ошибок в информационных векторах WS (m, к, m - 2)-кодов. Этим объясняются и дополнительные 4m - 4 необнаруживаемые ошибки в WS (m, к, m - 2)-кодах по сравнению с WS (m, к, ш)-кодами.

4 Свойства взвешенных кодов с суммированием

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

Прежде всего, установим, что в нашем случае свойства кода определяются только значением веса взвешенного информационного разряда, но не его местоположением в информационном векторе.

При рассмотрении характеристик кодов мы используем все 2m информационных вектора, а значения всех информационных разрядов принимают на 2m-1 векторах единичные значения и на таком же количестве векторов - нулевые значения. Взвешивание одного информационного разряда всегда приводит к увеличению веса 2m-1 информационных векторов на величину w - 1 (это следует из того факта, что вес имеет значение только для единичного информационного разряда). Таким образом, при взвешивании одного информационного разряда значение веса увеличивается ровно у половины информационных векторов, а у половины остается неизменным. Проведенные рассуждения являются доказательством следующего положения.

Лемма 1. Свойства кода с суммированием с одним взвешенным разрядом по обнаружению искажений в информационных векторах зависят только от того, каков вес взвешенного разряда, но никак не зависят от его местоположения в информационном векторе.

Код Бергера обнаруживает любые монотонные ошибки в информационных векторах. Это свойство объясняется тем, что одному контрольному слову соответствуют информационные векторы с одинаковым количеством единиц (одинаковым весом r). Код с суммированием с одним взвешенным разрядом всегда имеет в контрольной группе с весом r информационные векторы с весом, соответствующим номеру контрольной группы или большему, чем номер контрольной группы. В таком случае все переходы между информационными векторами одной контрольной группы будут разнонаправленными.

Лемма 2. Любой код с суммированием с одним взвешенным разрядом обнаруживает все монотонные искажения в информационных векторах.

На леммах 1 и 2 базируется следующая теорема.

Теорема 2. Код с суммированием с одним взвешенным разрядом обнаруживает любые ошибки с нечетными кратностями и все монотонные ошибки с четными кратностями, если значение веса взвешенного разряда является нечетным числом.

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

Рассмотрим взвешенный код с суммированием, имеющий длину информационного вектора, равную m. У этого кода все информационные разряды, кроме одного, имеют вес w. = 1, а один информационный разряд имеет вес w - нечетное число. Из леммы 1 следует, что местоположение взвешенного разряда не важно. Таким образом, пусть взвешен последний разряд. Тогда все информационные векторы рассматриваемого кода классифицируются на две группы - < — ... ~ 0 > и < — ... ~ 1 >, где последний разряд имеет вес w. Обозначим вес информационного вектора < — ... ~ 1 > невзвешенного кода как r 1 = r. Тогда вектор < — ... ~ 0 > будет иметь вес, равный r0 = r - 1. Исходя из этого, информационные векторы будут иметь суммарный вес, равный либо W0 = r - 1, либо W1 = r - 1 + w. Если r является четным числом, то число W0 является нечетным, а W1- четным числом, в силу того, что числа r - 1 и w. -нечетные. Напротив, если r - нечетное, то число W0 является четным, а W1 -нечетным, в силу того, что число r - 1 четное, а w. - нечетное. Таким образом, первое утверждение теоремы доказано.

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

Теорема 2 доказана.

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

Утверждение 1. WS (m, k, w)-Kodbi со значением w > m имеют одинаковые распределения необнаруживаемых ошибок по кратностям.

Доказательство. Взвесим младший контрольный разряд: w = m (см. лемму 1). Это означает, что в сравнении с классическим кодом с суммированием в распределении информационных векторов относительно контрольных векторов все кодовые векторы, имеющие в качестве младшего информационного разряда единицу, будут смещены на величину m. Данные кодовые векторы переместятся в группы r + m, где r - истинный вес информационного вектора. Из группы r = 1 сместится один кодовый вектор, при этом он будет перемещен в группу r = 1 + m, т. е. будет единственным в группе. Из последующих групп будут перемещаться ровно по Crm\ информационных векторов, каждый из которых будет занимать пустующую группу с индексом r + m. Таким образом, половина векторов из таблицы распределения будет перемещена в новые, до этого пустые, контрольные группы.

Если весу разряда придать значение w > m, это приведет к еще большему смещению информационных векторов в таблицах распределений вправо. При этом будут появляться пустые группы. Например, если w = m + 1, то единственный вектор контрольной группы с r = 1 будет перемещен в группу r = 1 + m + 1 = m + 2, а группа с r = 1 + m останется пустой. Все остальные информационные векторы будут смещены в группы с еще большими номерами. Таким образом, распределения необнаруживаемых ошибок во всех кодах с w > m будут одинаковыми.

Утверждение 1 доказано.

Сравнение между собой таблиц 1-3 еще раз подтверждает формулировку утверждения 1.

Непосредственно из утверждения 1 и леммы 1 следует такое свойство кодов с суммированием с одним взвешенным информационным разрядом.

Утверждение 2. Для любого m вне зависимости от значения w существует ровно m WS (m, k, w)-кодов с различными распределениями необнаруживаемых ошибок по кратностям.

Поскольку WS (m, k, w)-код является модификацией классического S (m, к)-кода, полученной сдвигом 2m-1 информационных векторов в контрольные группы с весом W = r + w, уменьшается количество необнаруживаемых симметричных ошибок. Однако при этом возникает возможность появления необнаруживаемых асимметричных ошибок в информационных векторах

с различным значением числа единичных разрядов (с r = W единичными разрядами и с r = W - w +1 единичными разрядами).

WS (m, k, w)-коды, в отличие от S (m, к)-кодов, не обнаруживают только часть симметричных ошибок, а не все 100 % ошибок. При этом WS (m, к, w)-коды за счет сдвига половины информационных векторов в таблице их распределения на контрольные группы обнаруживают все симметричные ошибки максимальной кратностью d = m при четном значении m и d = m - 1 при нечетном значении m.

WS (m, к, w)-коды обладают следующим интересным свойством [43].

Свойство 1. Доля необнаруживаемых симметричных ошибок в информационных векторах WS (m, k, w)-кодов от общего числа симметричных ошибок не зависит от значения w и является постоянной величиной при данном значении m.

Поскольку классическими кодами Бергера не обнаруживается 100 % симметричных ошибок в информационных векторах, с применением формул (7) и (8) можно оценить, как уменьшилось число необнаруживаемых симметричных ошибок при взвешивании информационного разряда w = m:

z d ='

N

WS

N

S

r^m-d 2 d 2 Cd Cm-1

r^m-d /~i 2 f* d 2 CdCm.

(m -1)!

d!• (m - d -1)! = m - d = 1 d m! m m

d !• (m - d)!

С увеличением длины информационного вектора значение величины Zd при фиксированной кратности необнаруживаемой ошибки возрастает, что говорит о том, что количество необнаруживаемых WS (m, k, m)-кодами ошибок по каждой кратности приближается к аналогичной величине для кодов Бергера (табл. 9). Например, для WS (8,5,8)-кодов в сравнении с S (8,4)-кодами имеем в числе необнаруживаемых 75 % двукратных, 50 % четырехкратных, 25 % шестикратных и 0 % восьмикратных симметричных ошибок.

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

Кратность асимметричных необнаруживаемых ошибок в WS

Таблица 9. Изменение количества необнаруживаемых симметричных ошибок по каждой кратности для WS (m, k, т)-кодов в сравнении с S (m, ^-кодами

m d

2 4 6 8 10 12

2 0

3 0,333333

4 0,5 0

5 0,6 0,2

6 0,666667 0,333333 0

7 0,714286 0,428571 0,142857

8 0,75 0,5 0,25 0

9 0,777778 0,555556 0,333333 0,111111

10 0,8 0,6 0,4 0,2 0

11 0,818182 0,636364 0,454545 0,272727 0,090909

12 0,833333 0,666667 0,5 0,333333 0,166667 0

13 0,846154 0,692308 0,538462 0,384615 0,230769 0,076923

14 0,857143 0,714286 0,571429 0,428571 0,285714 0,142857

15 0,866667 0,733333 0,6 0,466667 0,333333 0,2

16 0,875 0,75 0,625 0,5 0,375 0,25

17 0,882353 0,764706 0,647059 0,529412 0,411765 0,294118

18 0,888889 0,777778 0,666667 0,555556 0,444444 0,333333

19 0,894737 0,789474 0,684211 0,578947 0,473684 0,368421

20 0,9 0,8 0,7 0,6 0,5 0,4

в данной группе перейдет в вектор с нулевым младшим разрядом только при искажении младшего разряда и искажении W - (W - w) = w остальных разрядов. При большем числе искажаемых единичных разрядов в информационном векторе с весом r = W - w +1 кратность ошибки увеличивается на 2 (должен исказиться единичный и нулевой разряды для перехода в вектор с весом r = W). Отсюда вытекает следующее свойство WS (m, k, w)-кодов:

Свойство 2. WS (m, k, w)-Kod обнаруживает любые асимметричные ошибки с кратностью d < w +1.

При заданном значении длины информационного вектора максимальную эффективность взвешивания будет иметь такой вариант, при котором сдвиг половины информационных векторов произойдет в незаполненные группы. В этом случае WS (m, k, w)-кодом будут обнаруживаться любые асимметричные ошибки в информационных векторах. В S (m, ^-кодах информационные векторы есть в группах со значением веса r е {0,1,..., m}. Соответственно

сдвинуть половину векторов необходимо на величину m [44]. Отсюда следует следующее свойство.

Свойство 3. WS (m, к, wj-код будет иметь минимальное число необнаруживаемых симметричных ошибок и при этом обнаруживать все асимметричные ошибки, если w > m.

Используя табличную форму задания взвешенного кода, мы алгоритмизировали процесс подсчета числа необнаруживаемых искажений в информационных векторах по каждой группе. Процесс расчета автоматизирован, создано специальное программное обеспечение, позволяющее рассчитывать характеристики взвешенных кодов при различных длинах информационных векторов. В табл. 10 и 11 приводятся характеристики взвешенных кодов с длинами информационных векторов m = 10 и m = 11 соответственно. В первых строках табл. 10 и 11 приведен код Бергера. Взвешенные коды с суммированием, у которых число контрольных разрядов на единицу больше, чем у классических кодов Бергера, в таблице выделены серым фоном. Для них коэффициент эффективности резко падает (практически в два раза) по сравнению с максимально эффективным WS (m, к, w)-кодом. Однако с увеличением w код приближается к минимальному для него значению количества необнаруживаемых ошибок.

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

Анализ таблиц характеристик кодов с суммированием позволил установить ряд особенностей кодов с суммированием с одним взвешенным информационным разрядом:

1. С увеличением веса w при данном m уменьшается общее число необнаруживаемых искажений в информационных векторах; при этом минимум необнаруживаемых ошибок для данного m достигается, когда w = m.

2. Если в качестве веса w выступает нечетное число, то код с суммированием не имеет необнаруживаемых искажений с нечетной кратностью (см. утверждение теоремы 2).

3. WS (m, к, w)-коды с четными значениями w обнаруживают все ошибки с нечетными кратностями d < w.

4. Для данной длины информационного вектора m все взвешенные коды с четными значениями взвешенного разряда w имеют одинаковое количество искажений с четными кратностями d.

5. Взвешенный код с суммированием WS (m, к, w) обнаруживает любые искажения с нечетными кратностями, если w = m.

6. У взвешенных кодов с суммированием с одним взвешенным информационным разрядом при данном значении m всегда одинаковое количество необнаруживаемых ошибок с четными кратностями при w > d, в частности: все коды имеют одинаковое количество двукратных необнаруживаемых искажений.

Автоматика на транспорте № 4, том 2, декабрь 2016

Таблица 10. Характеристики WS (10, к, и’)-код о в

т к W Число необнаруживаемых ошибок с кратностью d, Nd N WS

1 2 3 4 5 6 7 8 9 10

10 4 1 0 23040 0 80640 0 67200 0 12600 0 252 183732 0,3511

10 4 2 0 18432 9216 48384 32256 26880 20160 2520 2016 0 159864 0,4035

10 4 3 0 18432 0 59136 0 47040 0 8568 0 168 133344 0,4838

10 4 4 0 18432 0 48384 8064 26880 8064 2520 1008 0 113352 0,5691

10 4 5 0 18432 0 48384 0 30912 0 4536 0 72 102336 0,6304

10 4 6 0 18432 0 48384 0 26880 1344 2520 288 0 97848 0,6593

10 5 7 0 18432 0 48384 0 26880 0 2808 0 18 96522 0,3289

10 5 8 0 18432 0 48384 0 26880 0 2520 36 0 96252 0,3298

10 5 9 0 18432 0 48384 0 26880 0 2520 0 2 96218 0,3299

10 5 10 0 18432 0 48384 0 26880 0 2520 0 0 96216 0,3299

Проектирование и тестирование логических устройств 585

2016, December, vol. 2, No 4 Automation on Transport

Таблица 11. Характеристики WS (11 ,k, и')-кодов

m к w Число необнаруживаемых ошибок с к эатностью d, Nd N v WS

1 2 3 4 5 6 7 8 9 10 11

11 4 1 0 56320 0 253440 0 295680 0 92400 0 5544 0 703384 0,3698

11 4 2 0 46080 23040 161280 107520 134400 100800 25200 20160 504 420 619404 0,4199

11 4 3 0 46080 0 192000 0 215040 0 65520 0 3864 0 522504 0,4978

11 4 4 0 46080 0 161280 26880 134400 40320 25200 10080 504 240 444984 0,5845

11 4 5 0 46080 0 161280 0 150528 0 38640 0 1944 0 398472 0,6527

11 5 6 0 46080 0 161280 0 134400 6720 25200 2880 504 90 377154 0,3421

11 5 7 0 46080 0 161280 0 134400 0 27120 0 864 0 369744 0,349

11 5 8 0 46080 0 161280 0 134400 0 25200 360 504 20 367844 0,3508

11 5 9 0 46080 0 161280 0 134400 0 25200 0 544 0 367504 0,3511

11 5 10 0 46080 0 161280 0 134400 0 25200 0 504 2 367466 0,3511

11 5 11 0 46080 0 161280 0 134400 0 25200 0 504 0 367464 0,3511

586 Design and test of logical devices

7. Все коды, кроме кода с w = 2, обнаруживают любые искажения с кратностью d = 3.

8. Если m - нечетное, то коды с нечетными значениями w не имеют необнаруживаемых ошибок с максимальной кратностью d = m; если m - четное, то коды с четными значениями w не имеют необнаруживаемых ошибок с максимальной кратностью d = m.

9. Для кодов, не удовлетворяющих свойству 7, при заданном значении длины информационного вектора с увеличением значения взвешенного разряда w уменьшается число необнаруживаемых искажений с кратностью d = m и становится минимальным (равным 2) при w = m - 1.

10. Код имеет максимальную эффективность для данной длины информационного вектора, если число контрольных разрядов в нем равно к =

m

= [log2(m +1)] и выполняется условие ^ wt = 2к -1.

i=1

Если сравнить между собой классические коды Бергера и код с суммированием с одним взвешенным информационным разрядом, то можно отметить тот факт, что взвешенный код имеет меньшее количество необнаруживаемых ошибок по каждой кратности. При этом наиболее существенная разница в числе необнаруживаемых ошибок взвешенного кода и кода Бергера наблюдается у так называемых «средних» значений кратностей. Например, WS (10,5,8)-код имеет в 5 раз меньше необнаруживаемых ошибок с кратностью d = 8 и в 2,5 раза меньше необнаруживаемых ошибок с кратностью d = 6, чем S (10,4)-код.

Практическим применением установленных свойств взвешенных кодов с суммированием является следующий пример. Предположим, что контролируемая схема F(x) имеет 10 выходов и эксперимент показал, что на ее выходах возможны искажения с кратностями d = 3, 4, 5. В этом случае целесообразно выбрать WS (10,4, w)-код со значением w = 5 или w = 6 - эти коды имеют минимум необнаруживаемых четырехкратных искажений и не имеют трехратных и пятикратных необнаруживаемых ошибок при к = 4; коды с большими значениями w обладают такими же свойствами обнаружения ошибок с малыми кратностями, но имеют 5 контрольных разрядов (см. табл. 10). Некоторые экспериментальные результаты с набором контрольных комбинационных схем LGSynth'89 [45, 46] изложены авторами в работе [43]. Эксперименты подтверждают установленные свойства WS (m, к, w)-кодов, а также их эффективность при организации систем функционального контроля комбинационных схем.

Заключение

Взвешивание одного разряда в информационном векторе кода с суммированием позволяет увеличить количество обнаруживаемых ошибок по сравнению с использованием классического кода Бергера. При этом изменение значе-

ния весового коэффициента взвешенного информационного разряда в пределах 1 < w < m дает возможность получения кодов с суммированием с различными характеристиками обнаружения ошибок в информационных векторах. С увеличением значения весового коэффициента при постоянной длине информационного вектора общее количество необнаруживаемых ошибок уменьшается и достигает минимального значения при w = m. Снижается некоторое количество симметричных необнаруживаемых ошибок, однако появляется некоторое количество асимметричных необнаруживаемых ошибок. Все WS (m, к, w)-коды со значениями w > m имеют минимальное общее количество необнаруживаемых ошибок, в то же время ими обнаруживаются все асимметричные ошибки. Следует отметить тот немаловажный факт, что все WS (m, к, w)-коды идентифицируют 100 % монотонных ошибок в информационных векторах, что дает возможность применения взвешенных кодов с суммированием в аналогичных задачах технической диагностики, для решения которых используются классические S (m, к)-коды. Также установлено: если значение весового коэффициента является нечетным числом, WS (m, к, w)-код обнаруживает любые ошибки с нечетными кратностями в информационных векторах, а при четных значениях весового коэффициента - все ошибки с нечетными кратностями d < w. Определены условия получения максимально эффективного WS (m, к, w)-кода с позиции использования им своих контрольных разрядов.

В заключение отметим недостаток WS (m, к, w)-кодов - при некоторых значениях весовых коэффициентов увеличивается количество разрядов в контрольном векторе, что увеличивает сложность технической реализации системы функционального контроля. Данный недостаток может быть устранен путем определения наименьшего неотрицательного вычета суммарного веса

единичных информационных разрядов по модулю M = 2^log2 (m+1)T. Эта операция уменьшает количество контрольных разрядов, но, к сожалению, вносит в класс необнаруживаемых некоторое количество монотонных ошибок в информационных векторах.

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

Библиографический список

1. Goessel M. Error Detection Circuits / M. Goessel, S. Graf. - L. : McGraw-Hill, 1994. - 261 p.

2. Дрозд А. В. Нетрадиционный взгляд на рабочее диагностирование вычислительных устройств / А. В. Дрозд // Проблемы управления. - 2008. - № 2. -С. 48-56.

3. Ubar R. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) / R. Ubar, J. Raik, H.-T. Vierhaus. Information Science Reference, Hershey. - N. Y. : IGI Global, 2011. - 578 p.

4. Согомонян Е. С.Самопроверяемые устройства и отказоустойчивые системы / Е. С. Согомонян, Е. В. Слабаков. - М. : Радио и связь, 1989. - 208 с.

5. Сапожников Вал. В. Самопроверяемые дискретные устройства / Вал. В. Сапожников, Вл. В. Сапожников. - СПб. : Энергоатомиздат, 1992. - 224 с.

6. Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes / S. J. Piestrak. - Wroclaw : Oficyna Wydawnicza Politechniki Wroclavskiej, 1995. - 111 p.

7. Nicolaidis M. On-Line Testing for VLSI - А Compendium of Approaches / M. Nico-laidis, Y. Zorian // Journal of Electronic Testing : Theory and Applications. - 1998. -Issue 12. - Pp. 7-20.

8. Mitra S. Which Concurrent Error Detection Scheme to ^oose? / S. Mitra, E. J. McCluskey // Proceedings of International Test Conference, 2000. - USA, Atlantic City, NJ, 3-5 October 2000. - Pp. 985-994.

9. Matrosova A. Designing FPGA Based Self-Testing Checkers for m-out-of-n Codes / A. Matrosova, V. Ostrovsky, I. Levin, K. Nikitin // Proceedings of the 9th IEEE International On-Line Testing Symposium (IOLTS’03), 7-9 July 2003, Kos Island, Greece. - Pp. 49-53.

10. Слабаков Е. В. Самопроверяемые вычислительные устройства и системы (обзор) / Е. В. Слабаков, Е. С. Согомонян // Автоматика и телемеханика. - 1981. -№ 11. - С. 147-167.

11. Ефанов Д. В. О свойствах кода с суммированием в схемах функционального контроля / Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 2010. - № 6. - С. 155-162.

12. Пархоменко П. П. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства) / П. П. Пархоменко, Е. С. Согомо-нян. - М. : Энергоатомиздат, 1981. - 320 с.

13. Согомонян Е. С. Построение самопроверяемых схем встроенного контроля для комбинационных устройств / Е. С. Согомонян // Автоматика и телемеханика. -1974. - № 2. - С. 121-133.

14. Аксёнова Г. П. Необходимые и достаточные условия построения полностью проверяемых схем свертки по модулю 2 / Г. П. Аксёнова // Автоматика и телемеханика. - 1979. - № 9. - С. 126-135.

15. Аксёнова Г. П. О функциональном диагностировании дискретных устройств в условиях работы с неточными данными / Г. П. Аксёнова // Проблемы управления. - 2008. - № 5. - С. 62-66.

16. Сапожников Вал. В. Применение кодов с суммированием при синтезе систем железнодорожной автоматики и телемеханики на программируемых логических интегральных схемах / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Автоматика на транспорте. - 2015. - Т. 1. - № 1. - С. 84-107.

17. Сапожников Вал. В. Исследование свойств кодов Хэмминга и их модификаций в системах функционального контроля / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Автоматика на транспорте. - 2015. - Т. 1. - № 3. -С. 311-337.

18. Сапожников Вал. В. Организация систем функционального контроля комбинационных схем на основе модифицированного кода с суммированием взвешенных переходов (окончание) / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов, В. В. Дмитриев, М. Р. Черепанова // Электронное моделирование. - 2016. -Т. 38. - № 1. - С. 87-98.

19. Berger J. M. A Note on Error Detection Codes for Asymmetric Channels / J. M. Berger // Information and Control. - 1961. - Vol. 4. - Issue 1. - Pp. 68-73.

20. Busaba F. Y. Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Errors / F. Y. Busaba, P. K. Lala // Journal of Electronic Testing: Theory and Applications. - 1994. - Issue 5. - Pp. 19-28.

21. Saposhnikov Val. V. A New Design Method for Self-Checking Unidirectional Combinational Circuits / Val. V. Saposhnikov, A. Morosov, Vl. V. Saposhnikov, M. Goes-sel // Journal of Electronic Testing: Theory and Applications. - 1998. - Vol. 12. - Issue 1-2. - Pp. 41-53.

22. Morosow A. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs / A. Morosow, Val. V. Saposhnikov, Vl. V. Saposhnikov, M. Goes-sel // VLSI Design. - 1998. - Vol. 5. - Issue 4. - Pp. 333-345.

23. Matrosova A.Yu. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error / A.Yu. Matrosova, S.A. Ostanin // Proceedings of the IEEE European Test Workshop (ITW’98), 27-29 May 1998. - Sitges, Barcelona, Spain.

24. Matrosova A. Survivable Discrete Circuits Design / A. Matrosova, V. Andreeva, Yu. Sedov // Proceedings of the 8th IEEE International On-Line Testing Workshop (IOLTW’02), 10 July 2002, Isle of Bendor, France. - Pp. 13-17.

25. Sapozhnikov Val. Modular Sum Code in Building Testable Discrete Systems / Val. Sapozhnikov, Vl. Sapozhnikov, D. Efanov // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS'2015), Batumi, Georgia, September 2629, 2015. - Pp. 181-187.

26. Сапожников Вал. В. Классификация ошибок в информационных векторах систематических кодов / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Известия вузов. Приборостроение. - 2015. - Т. 58. - № 5. - С. 333-343.

27. Dong H. Modified Berger Codes for Detection of Unidirectional Errors / H. Dong // IEEE Trans. Comput. - Vol. C-33. - June 1984. - Pр. 572-575.

28. Jha N. K. A Systematic Code for Detecting t-Unidirectional Errors / N. K. Jha, M. B. Vora // Proceedings of International Symposium Fault-Tolerant Comput. -Pittsburg, PA, June 1987. - Pp. 96-101.

29. Parhami B. New Class of Unidirectional Error-Detection Codes / B. Parhami // Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 14-16 Oct 1991 (ICCD ‘9), Cambridge, MA. - Pp. 574-577.

30. Das D. Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits / D. Das, N. A. Touba // Proceedings of the 17th IEEE VLSI Test Symposium, USA, CA, Dana Point, April 25-29, 1999. - Pp. 370-376.

31. Efanov D. On the Problem of Selection of Code with Summation for Combinational Circuit Test Organization / D. Efanov, Val. Sapozhnikov, Vl. Sapozhnikov, A. Blyudov // Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS'2013), Rostov-on-Don, Russia, September 27-30, 2013. - Pp. 261-266.

32. Sapozhnikov Val. On the Synthesis of Unidirectional Combinational Circuits Detecting All Single Faults / Val. Sapozhnikov, Vl. Sapozhnikov, D. Efanov, A. Blyudov // Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS'2014), Kyev, Ukraine, September 26-29, 2014. - Pp. 116-125.

33. Ефанов Д. В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем / Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 2015. - № 10. - С. 152-169.

34. Черкасова Т. Х. Обнаружение ошибок в системах автоматики и вычислительной техники с помощью кодов Бергера и его модификаций / Т. Х. Черкасова // Сборник трудов научно-практической конференции «Проблемы безопасности и надежности микропроцессорных комплексов» ; под ред. Вал. В. Сапожникова. -СПб.: Петербургский гос. ун-т путей сообщения, 2015. - С. 167-172.

35. Сапожников Вал. В. Обнаружение опасных ошибок на рабочих выходах комбинационных логических схем / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Автоматика на транспорте. - 2015. - Т. 1. - № 2. - С. 195-211.

36. Блюдов А. А. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов / А. А. Блюдов, Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников // Электронное моделирование. - 2012. - Т. 34. - № 6. - С. 17-29.

37. Блюдов А. А. Коды с суммированием для организации контроля комбинационных схем / А. А. Блюдов, Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 2013. - № 6. - С. 153-164.

38. Блюдов А. А. О кодах с суммированием единичных разрядов в системах функционального контроля / А. А. Блюдов, Д. В. Ефанов, Вал. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. - 2014. - № 8. - С. 131-145.

39. Сапожников Вал. В. Взвешенные коды с суммированием для организации контроля логических устройств / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Электронное моделирование. - 2014. - Т. 36. - № 1. - С. 59-80.

40. Сапожников Вал. В. Метод построения кода Бергера с повышенной эффективностью обнаружения ошибок в информационных разрядах / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов, Д. А. Никитин // Электронное моделирование. - 2013. - Т. 35. - № 4. - С. 21-34.

41. Sapozhnikov Val. Combinational Circuits Checking on the Base of Sum Codes with One Weighted Data Bit / Val. Sapozhnikov, Vl. Sapozhnikov, D. Efanov, D. Nikitin // Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS'2014), Kyev, Ukraine, September 26-29, 2014. - Pp. 126-136.

42. Сапожников Вал. В. Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов, Д. А. Никитин // Электронное моделирование. - 2015. - Т. 37. - № 1. - С. 25-48.

43. Сапожников Вал. В. Построение кодов с суммированием с наименьшим количеством необнаруживаемых симметричных ошибок в информационных векторах / Вал. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Радиоэлектроника и информатика. - 2014. - № 4. - С. 46-55.

44. Ефанов Д. В. Анализ способов построения кодов с суммированием с улучшенными характеристиками обнаружения симметричных ошибок в информационных векторах / Д. В. Ефанов // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2015. - № 4. -С. 69-81.

45. Collection of Digital Design Benchmarks. - URL: http://ddd.fit.cvut.cz/prj/Bench-marks.

46. Yang S. Logic Synthesis and Optimization Benchmarks : User Guide : Version 3.0 / S. Yang. - Microelectronics Center of North Carolina (MCNC), 1991. - 88 p.

Valery V. Sapozhnikov,

Vladimir V. Sapozhnikov,

Dmitry V. Efanov

«Automation and remote control on railways» department,

Emperor Alexander I St. Petersburg state transport university

Checking of combinational circuits, based on sum codes with one weighted data bit

During the development of safe and reliable management systems the concurrent error detection of a technical condition of logical units are commonly used. While organizing such systems the characteristic of 100 % detection of single faults at the outputs of the logical elements of the internal structure of the object under control should be provided. It is possible through using of several approaches: 1) duplication; 2) using of fault-tolerant codes without modifying the structures of objects under test; 3) using of fault-tolerant codes with modification of the structure of objects under test. The selection of a code at the design stage of concurrent error detection system is a key factor, that influence on the basic characteristics of the system. The paper presents the results of the study of properties of the sum codes with one weighted data bit. Proposed codes, as well as classical Berger codes, detect 100 % of unidirectional errors in the data vectors which means that they can be applied to solve similar tasks of technical diagnostics as Berger codes. Moreover, new codes have a reduced, in comparison with Berger codes, number of so-called symmetric errors. In this case, however, the weighting of a bit results into appearance of a certain number of asymmetric errors. The article provides conditions of formation of the weight-based sum code that is capable of a 100 % detection of errors of odd multiples and unidirectional errors in data vectors. In addition, the article defines new characteristics of sum codes with one weighted data bit, the

tracking of which in practice will allow to organize a concurrent error detection

systems for logic units devices with improved performance.

technical diagnostics; concurrent error detection system; sum code; Berger code;

bit weight; sum weight-based code; undetectable error in data vector; error detecting properties

References

1. Goessel M., Graf S. (1994). Error Detection Circuits. London, McGraw-Hill, 261 p.

2. Drozd A. V. (2008). Non-conventional point of view at operational diagnostics of compluting devices [Netraditsionnyy vzglyad na rabocheye diagnostirovani-ye vychislitel’nykh ustroystv], Management problems (Problemy upravleniya), issue 2, pp. 48-56.

3. Ubar R., Raik J., Vierhaus H.-T. (2011). Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source). Information Science Reference, Hershey - N. Y., IGI Global, 578 p.

4. Sogomonyan E. S., Slabakov E. V. (1989). Self-checking devices and fault-tolerant systems [Samoproveryayemyye ustroystva i otkazoustoychivyye sistemy]. Moscow, Radio and communication (Radio i svyaz’), 208 p.

5. Sapozhnikov Val. V., Sapozhnikov Vl. V. (1992). Self-checking discrete devices [Samoproveryayemyye diskretnyye ustroystva]. St. Petersburg, Energoatomizdat, 224 p.

6. Piestrak S. J. (1995). Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wroclaw, Oficyna Wydawnicza Politechniki Wroclavskiej, 111 p.

7. Nicolaidis M., Zorian Y. (1998). On-Line Testing for VLSI - А Compendium of Approaches, Journal of Electronic Testing: Theory and Applications, issue 12, pp. 7-20.

8. Mitra S., McCluskey E. J. (2000). Which Concurrent Error Detection Scheme to Choose?, Proceedings of International Test Conference, USA, Atlantic City, NJ, 3-5 October 2000, pp. 985-994.

9. Matrosova A., Ostrovsky V., Levin I., Nikitin K. Designing FPGA based Self-Testing Checkers for m-out-of-n Codes, Proceedings of the 9th IEEE International On-Line Testing Symposium (IOLTS’03), 7-9 July 2003, Kos Island, Greece, pp. 49-53.

10. Slabakov E. V., Sogomonyan E. S. (1981). Self-checking computing devices and systems (review) [Samoproveryayemyye vychislitel’nyye ustroystva i sistemy (obzor)], Automation and remote control (Avtomatika i telemekhanika), issue 11, pp. 147-167.

11. Efanov D. V., Sapozhnikov Val. V., Sapozhnikov Vl. V. (2010). On sum code properties in concurrent error detection systems [O svoystvakh koda s summirovaniyem v skhemakh funktsional’nogo kontrolya], Automation and remote control (Avtoma-tika i telemekhanika), issue 6, pp. 155-162.

12. Parkhomenko P. P., Sogomonyan E. S. (1981). Basics of technical diagnostics (optimization of diagnostic algorithms and equipment) [Osnovy tekhnicheskoy diagnos-tiki (optimizatsiya algoritmov diagnostirovaniya, apparaturnyye sredstva)]. Moscow, Energoatomizdat, 320 p.

13. Sogomonyan E. S. (1974). Design of self-checking schemes of built-in control for combinational devices [Postroyeniye samoproveryayemykh skhem vstroyennogo kontrolya dlya kombinatsionnykh ustroystv], Automation and remote control (Av-tomatika i telemekhanika), issue 2, pp. 121-133.

14. Aksenova G. P. (1979). Necessary and sufficient conditions for design of fully testable convolution modulo 2 schemes [Neobkhodimyye i dostatochnyye usloviya postroy-eniya polnost’yu proveryayemykh skhem svertki po modulyu 2], Automation and remote control (Avtomatika i telemekhanika), issue 9, pp. 126-135.

15. Aksenova G. P. (2008). On operational diagnostics of discrete devices under the operation with inaccurate data [O funktsional’nom diagnostirovanii diskretnykh ustroystv v usloviyakh raboty s netochnymi dannymi], Management problems (Prob-lemy upravleniya), issue 5, pp. 62-66.

16. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2015). Application of sum codes for synthesis of railway automation and remote control systems using programmable logic integrated circuits [Primeneniye kodov s summirovaniyem pri sin-teze sistem zheleznodorozhnoy avtomatiki i telemekhaniki na programmiruyemykh logicheskikh integral’nykh skhemakh], Automation on transport (Avtomatika na transporte), vol. 1, issue 1, pp. 84-107.

17. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2015). Hamming codes and its modifications research within concurrent error detection systems [Issledovaniye svoystv kodov Khemminga i ikh modifikatsiy v sistemakh funktsional’nogo kontrolya], Automation on transport (Avtomatika na transporte), vol. 1, issue 3, pp. 311-337.

18. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V., Dmitriev V. V., Cherepanova M. R. (2016). Concurrent error detection system organization for combinational circuits, based on sum code with weighted transitions (ending) [Organizatsiya sistem funktsional’nogo kontrolya kombinatsionnykh skhem na osnove modifitsirovan-nogo koda s summirovaniyem vzveshennykh perekhodov (okonchanije)], Electronic simulation (Elektronnoe modelirovanie), vol. 38, issue 1, pp. 87-98.

19. Berger J. M. (1961). A Note on Error Detection Codes for Asymmetric Channels // Information and Control, vol. 4, issue 1, pp. 68-73.

20. Busaba F. Y., Lala P. K. (1994). Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Errors, Journal of Electronic Testing: Theory and Applications, issue 5, pp. 19-28.

21. Sapozhnikov Val. V., Morosov A., Sapozhnikov Vl. V., Goessel M. (1998). A New Design Method for Self-Checking Unidirectional Combinational Circuits, Journal of Electronic Testing: Theory and Applications, vol. 12, issue 1-2, pp. 41-53.

22. Morosow A., Sapozhnikov Val. V., Sapozhnikov Vl. V., Goessel M. (1998). SelfChecking Combinational Circuits with Unidirectionally Independent Outputs, VLSI Design, vol. 5, issue 4, pp. 333-345.

23. Matrosova A.Yu., Ostanin S.A. (1998). Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error, Proceedings of the IEEE European Test Workshop (ITW’98), 27-29 May 1998, Sitges, Barcelona, Spain.

24. Matrosova A., Andreeva V., Sedov Yu. (2002). Survivable Discrete Circuits Design, Proceedings of the 8th IEEE International On-Line Testing Workshop (IOLTW’02), 10 July 2002, Isle of Bendor, France, pp. 13-17.

25. Sapozhnikov Val., Sapozhnikov Vl., Efanov D. (2015). Modular Sum Code in Building Testable Discrete Systems, Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS'2015), Batumi, Georgia, September 26-29, 2015, pp. 181-187.

26. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2015). Classification of errors in data vectors of systematic codes [Klassifikatsiya oshibok v informatsion-nykh vektorakh sistematicheskikh kodov], News of Higher Educational Institutions. Instrument Engineering (Izvestiya vuzov. Priborostroyeniye), vol. 58, issue 5, pp. 333-343.

27. Dong H. (1984). Modified Berger Codes for Detection of Unidirectional Errors, IEEE Trans. Comput., vol. C-33, June 1984, pp. 572-575.

28. Jha N. K., Vora M. B. (1987). A Systematic Code for Detecting t-Unidirectional Errors, Proceedings of International Symposium Fault-Tolerant Comput., Pittsburg, PA, June 1987, pp. 96-101.

29. Parhami B. (1991). New Class of Unidirectional Error-Detection Codes, Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, 14-16 October 1991 (ICCD ‘9), Cambridge, MA, pp. 574-577.

30. Das D., Touba N. A. (1999). Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits, Proc. of the 17th IEEE VLSI Test Symposium, USA, CA, Dana Point, April 25-29, 1999, pp. 370-376.

31. Efanov D., Sapozhnikov Val., Sapozhnikov Vl., Blyudov A. (2013). On the Problem of Selection of Code with Summation for Combinational Circuit Test Organization, Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS'2013), Rostov-on-Don, Russia, September 27-30, 2013, pp. 261-266.

32. Sapozhnikov Val., Sapozhnikov Vl., Efanov D., Blyudov A. (2014). On the Synthesis of Unidirectional Combinational Circuits Detecting All Single Faults, Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS'2014), Kyev, Ukraine, September 26-29, 2014, pp. 116-125.

33. Efanov D. V., Sapozhnikov Val. V., Sapozhnikov Vl. V. (2015). Application of modular weighted-based sum codes for building of concurrent error detection (CED) systems of combinational logic circuits [Primeneniye modul’nykh kodov s summirovaniyem dlya postroyeniya sistem funktsional’nogo kontrolya kombinatsionnykh logicheskikh skhem], Automation and remote control (Avtomatika i telemekhanika), issue 10, pp. 152-169.

34. Cherkasova T. Kh. (2015). Error detection in automation and computing systems by using Berger codes and its modifications [Obnaruzheniye oshibok v sistemakh avtomatiki i vychislitel’noy tekhniki s pomoshch’yu kodov Bergera i yego modi-fikatsiy], Proceedings of science and practical conference «Safety and reliability problems of microprocessor-based complexes» (Sbornik trudov nauchno-prak-ticheskoy konferentsii: «Problemy bezopasnosti i nadezhnosti mikroprotsessornykh kompleksov»); under the editorship of Vl. V. Sapozhnikov. St. Petersburg, PSTU (PGUPS), pp. 167-172.

35. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2015). Detection of critical errors at operational outputs of combinational logic circuits [Obnaruzheniye opas-nykh oshibok na rabochikh vykhodakh kombinatsionnykh logicheskikh skhem], Automation on transport (Avtomatika na transporte), vol. 1, issue 2, pp. 195-211.

36. Blyudov A. A., Efanov D. V., Sapozhnikov Val. V., Sapozhnikov Vl. V. (2012). Formation of modified Berger code with minimum number of undetectable errors of data bits [Postroyeniye modifitsirovannogo koda Bergera s minimal’nym chislom neobnaruzhivayemykh oshibok informatsionnykh razryadov], Electronic simulation (Elektronnoe modelirovanie), vol. 34, issue 6, pp. 17-29.

37. Blyudov A. A., Efanov D. V., Sapozhnikov Val. V., Sapozhnikov Vl. V. (2013). Sum codes for organization of combinational circuits control [Kody s summirovaniyem dlya organizatsii kontrolya kombinatsionnykh skhem], Automation and remote control (Avtomatika i telemekhanika), issue 6, pp. 153-164.

38. Blyudov A. A., Efanov D. V., Sapozhnikov Val. V., Sapozhnikov Vl. V. (2014). On sum codes of unit bits in concurrent error detection systems [O kodakh s summirovaniyem yedinichnykh razryadov v sistemakh funktsional’nogo kontrolya], Automation and remote control (Avtomatika i telemekhanika), issue 8, pp. 131-145.

39. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2014). Weight-based sum codes for logic devices testing organization [Vzveshennyye kody s summirovaniyem dlya organizatsii kontrolya logicheskikh ustroystv], Electronic simulation (Elektronnoe modelirovanie), vol. 36, issue 1, pp. 59-80.

40. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V., Nikitin D. A. (2013). Method of formation of Berger code with improved efficiency of error detection in data bits [Metod postroyeniya koda Bergera s povyshennoy effektivnost’yu obnaruzheniya oshibok v informatsionnykh razryadakh], Electronic simulation (Elektronnoe modelirovanie), vol. 35, issue 4, pp. 21-34.

41. Sapozhnikov Val., Sapozhnikov Vl., Efanov D., Nikitin D. (2014). Combinational Circuits Checking on the Base of Sum Codes with One Weighted Data Bit, Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS'2014), Kyev, Ukraine, September 26-29, 2014, pp. 126-136.

42. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V., Nikitin D. A. (2015). Investigation of properties of sum codes with one weighted data bit in concurrent error detection systems [Issledovaniye svoystv kodov s summirovaniyem s odnim vzveshennym informatsionnym razryadom v sistemakh funktsional’nogo kontrolya], Electronic simulation (Elektronnoe modelirovanie), vol. 37, issue 1, pp. 25-48.

43. Sapozhnikov Val. V., Sapozhnikov Vl. V., Efanov D. V. (2014). Formation of sum codes with minimum total number of undetectable symmetrical errors in data vectors [Postroyeniye kodov s summirovaniyem s naimen’shim kolichestvom neobnaruzhivayemykh simmetrichnykh oshibok v informatsionnykh vektorakh], Radioelectronics and informatics (Radioelektronika i informatika), issue 4, pp. 46-55.

44. Efanov D. V. (2015). Analysis of formation methods of sum codes with improved characteristics of detection of symmetrical errors in data vectors [Analiz sposobov postroyeniya kodov s summirovaniyem s uluchshennymi kharakteristikami obnaru-zheniya simmetrichnykh oshibok v informatsionnykh vektorakh], Bulletin of Tomsk State University. Management, computer science and informatics (Vestnik Tomskogo gosudarstvennogo universiteta. Upravleniye, vychislitel’naya tekhnika i informatika), issue 4, pp. 69-81.

45. Collection of Digital Design Benchmarks [http://ddd.fit.cvut.cz/prj/Benchmarks/].

46. Yang S. (1991). Logic Synthesis and Optimization Benchmarks: User Guide: Version 3.0. Microelectronics Center of North Carolina (MCNC), 88 p.

Статья представлена к публикации членом редколлегии Р. Убаром Поступила в редакцию 17.09.2015, принята к публикации 29.10.2015

САПОЖНИКОВ Валерий Владимирович - доктор технических наук, профессор кафедры «Автоматика и телемеханика на железных дорогах» Петербургского государственного университета путей сообщения Императора Александра I.

e-mail: port.at.pgups1@gmail.com

САПОЖНИКОВ Владимир Владимирович - доктор технических наук, профессор кафедры «Автоматика и телемеханика на железных дорогах» Петербургского государственного университета путей сообщения Императора Александра I.

e-mail: sapozhnikov-at@yandex.ru

ЕФАНОВ Дмитрий Викторович - кандидат технических наук, доцент кафедры «Автоматика и телемеханика на железных дорогах» Петербургского государственного университета путей сообщения Императора Александра I. e-mail: TrES-4b@yandex.ru

© Сапожников Вал. В., Сапожников Вл. В., Ефанов Д. В., 2016