Analysis of formation methods of sum codes with improved characteristics of detection of symmetrical errors in data vect.pdf Принципы помехоустойчивого кодирования используются при передаче информации и при синтезе надежных систем управления [1-7]. Часто для этих целей применяют коды с суммированием [810]. Простота их построения (данные коды являются систематическими, т.е. значения разрядов контрольного вектора вычисляются по заранее установленным правилам суммирования разрядов информационного вектора) определяет их частое приложение в задачах технической диагностики при аппаратном и программном контроле технического состояния [11-15]. На рис. 1 приведена структура системы функционального контроля, организованная по кодам с суммированием. Блок F(x) является контролируемым логическим устройством и имеет m выходов f f2 ... fm, соответствующих выходному рабочему вектору (информационному вектору длины m). Для организации контроля технического состояния в систему вносится избыточность: блок F(x) снабжается специализированным контрольным оборудованием в составе блока контрольной логики G(x) и самопроверяемого тестера (TSC). Блок контрольной логики G(x) имеет k выходов и вычисляет значения системы контрольных функций (формирует контрольный вектор длины k), а самопроверяемый тестер проверяет факт соответствия значений разрядов информационного и контрольного векторов, которое устанавливается на этапе проектирования системы функционального контроля. При наличии неисправностей в любом из блоков системы функционального контроля на ее контрольных выходах формируется непарафазный сигнал или [9]. От выбранного на этапе проектирования системы функционального контроля кода с суммированием зависят такие важные характеристики самой системы, как аппаратурная избыточность и свойства обнаружения ошибок в блоке F(x). Они, в свою очередь, напрямую влияют на энергопотребление системы и быстродействие [16]. Известно большое количество правил построения кодов, которые можно свести в диаграмму, приведенную на рис. 2. Между разрядами информационного вектора может быть установлено неравноправие, что делается приписыванием им различных последовательностей весовых коэффициентов [w1, w2, ..., wm], либо же все информационные разряды могут быть равноправными [17, 18]. При построении кодов анализируется вес информационного вектора W, для него может определяться наименьший неотрицательный вычет по заранее установленному модулю M, а могут также проводиться некоторые модификации [19-24]. Рис. 2. Классификация кодов с суммированием Данная работа посвящена изложению нескольких способов построения модифицированных кодов с суммированием, позволяющих улучшить возможности обнаружения ошибок классическими кодами с суммированием. При этом сохраняются все основные особенности классических кодов с суммированием. 1. Задача построения кода с суммированием с улучшенными характеристиками обнаружения ошибок в информационных векторах Классический код с суммированием, или код Бергера [17], содержит в разрядах контрольного вектора двоичный эквивалент количества единичных разрядов информационного вектора (веса r информационного вектора). Исходя из этого, количество разрядов контрольного вектора кода Бергера k = |log2 (m + 1)], где m - длина информационного вектора, а запись [...] обозначает целое сверху от вычисляемого значения. Обозначим код Бергера как £(т,£)-код. Каждому информационному вектору с весом r соответствуют контрольные векторы с одинаковыми значениями разрядов. Поскольку всего существует Cm информационных векторов с весом r, их распределение между контрольными векторами с различными значениями разрядов крайне неравномерно (с увеличением значения т оно стремится к нормальному распределению). Например, в табл. 1 приведены все информационные векторы 5(5,3)-кода, распределенные между контрольными векторами. От того, как распределены информационные векторы между контрольными векторами, зависят свойства обнаружения ошибок кодом. Любая ошибка в информационном векторе, переводящая его в информационный вектор с тем же контрольным вектором, кодом обнаружена не будет. £(т^)-кодами не обнаруживается 100% разнонаправленных ошибок четной кратностью в информационных векторах, которые происходят при одинаковом количестве искажений 0 и 1 (так называемые симметричные ошибки [25]). В [26] предложена формула расчета количества необнаруживаемых ошибок в информационных векторах кодов Бергера: ^ Рабочие выходы ------------------------ Контрольное оборудование Рис. 1. Структура системы функционального контроля ^ Контрольные / 2 выходы ( d m- d d ZCrC 2 C m m d = 2 d r=- V 2 я-1) Nm = Z 2 m-r (1) Т а б л и ц а 1 Распределение информационных векторов 8(5,3)-кода между контрольными векторами Вес 0 1 2 3 4 5 6 7 Контрольный вектор 000 001 010 011 100 101 110 111 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 Данная формула позволяет подсчитать общее количество необнаруживаемых ошибок для S(m,k)-кода по каждой четной кратности d. В [27] эта формула приведена к виду Nm = C2mm - 2m. (2) Используя формулу (2) для S(5,3)-кода, получаем N5 = C55 - 25 = C,50 - 25 = - - 32 = 220. 5 2-5 10 5!- 5! Основной особенностью S(m,k)-кодов, определяющей их широкое применение при построении надежных систем автоматики, является стопроцентное обнаружение монотонных ошибок в информационных векторах (при таких ошибках искажаются либо только 0, либо только 1). С использованием данного свойства в [8, 28, 29] разработаны методы синтеза систем функционального контроля со стопроцентным обнаружением одиночных неисправностей в контролируемых схемах. Следует, однако, отметить, что S(m,k)-коды неэффективно используют свои контрольные разряды: контрольные векторы с близким к 0 и m значением веса соответствуют малому количеству информационных векторов, а значит, дают малое количество необнаруживаемых ошибок; некоторые контрольные векторы, в зависимости от значения m, могут не формироваться, а значит, и не использоваться (табл. 1). В [30] приводится способ построения кода Бергера с улучшенными характеристиками обнаружения ошибок в информационных векторах, но он приводит к появлению некоторого количества монотонных необнаруживаемых ошибок, а значит, накладывает ограничения на применение данных кодов при построении надежных систем автоматики [31, 32]. Информационные векторы, меняя правила построения кода, можно перераспределить между контрольными векторами так, чтобы сохранялись все основные свойства классических кодов с суммированием. Например, некоторым информационным векторам из групп, соответствующих контрольным векторам со значением веса, близким к m/2, можно поставить в соответствие неиспользуемые контрольные векторы (см. табл. 2). Количество необнаруживаемых ошибок уменьшится, а свойства стопроцентного обнаружения монотонных ошибок сохранятся. Например, S(5,3)-кодом не обнаруживается 240 ошибок в информационных векторах, а кодом, которому соответствует табл. 2, - 180 ошибок, что в 1,33 раза меньше. При этом все необнаруживаемые ошибки будут являться симметричными. Т а б л и ц а 2 Перераспределение информационных векторов 8(5,3)-кода между контрольными векторами Вес 0 1 2 3 4 5 6 7 Контрольный вектор 000 001 010 011 100 101 110 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 2. Способы модификации кодов с суммированием Формализованные правила построения кодов с суммированием с улучшенными характеристиками обнаружения симметричных ошибок в информационных векторах даны в нескольких работах, например [27, 33, 34]. Каждый из описанных способов основан на «сдвиге» части информационных векторов в группы, соответствующие контрольным векторам, большего веса, чем истинный вес информационных векторов. В [27] описывается процедура подсчета модифицированного веса W информационного вектора следующим образом (автор данной работы называет данный «сдвиговый» код комбинированным кодом Бергера). Алгоритм 1. Получение контрольного вектора комбинированного кода Бергера. 1. Подсчитывается вес m-1 информационного разряда (информационного вектора за исключением одного информационного разряда - вектора ). 2. Вычисляется функция паритета по всем разрядам информационного вектора: a = f ®f2 ©... ®fm. 3. Старшему разряду контрольного вектора соответствует значение функции паритета а, а оставшимся младшим разрядам - значение веса m-1 информационного разряда. Обозначим код, получаемый по алгоритму 1, как КБ(т,к)-код.. Для информационных векторов длины m = 5 применение алгоритма 1 дает распределение информационных векторов между контрольными векторами, показанное в табл. 3. Общее количество необнаруживаемых ошибок в KS(m,k)-кодах в два раза больше, чем в соответствующих «^^-^к^-кодах (к*=к или к-1), и его можно определить по формуле [27]: Nm = 2C2T-2 - 2m. (3) Для приведенного в табл. 3 К£(6,3)-кода формула (3) дает такой результат: о, N5 = 2C5-12 - 25 = 2C4 - 25 = 2--:--32 = 108. 5 2 8 4!- 4! Полученный результат для S*(m,k)-кода в 2,037 раза меньше, чем для ^да^-кода. Т а б л и ц а 3 Распределение информационных векторов комбинированного К8(6,3)-кода между контрольными векторами Вес 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Контрольный вектор 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 00000 10001 00011 10111 01111 10000 00001 10011 00111 11111 10010 00101 11011 00010 10101 01011 10100 00110 11101 00100 10110 01101 11000 01001 11110 01000 11001 01110 01010 11010 01100 11100 Информационные векторы классического кода Бергера были перераспределены между контрольными векторами, что дало новый код. Фактически половина информационных векторов с функцией паритета а = f1 © f ©... © fm, равной 1, поменяли свои места - они оказались сдвинутыми на 8 контрольных групп «вправо», а оставшаяся половина информационных векторов сохранила свои позиции (см. табл. 3). При этом добавился один контрольный разряд, а характер распределения был сохранен: информационные векторы неравномерно распределены между контрольными векторами, контрольные разряды используются неэффективно, часть из контрольных векторов никогда не формируется. Для подсчета коэффициента а можно выбирать различные сочетания информационных разрядов вместе с тем разрядом, для которого не применяется правило 1 алгоритма 1. Это даст возможность получения нового множества кодов с суммированием с различными распределениями необнаруживаемых ошибок по кратностям и видам. При этом основные свойства кодов Бергера могут и не сохраниться. Правила построения, выбранного в качестве основы системы функционального контроля кода с суммированием, определяют и способ построения тестера. Тестер в структуре, приведенной на рис. 1, состоит из генератора (кодера или шифратора) контрольных разрядов, выходы которого соединяются с входами компаратора. Последний осуществляет сравнение одноименных контрольных функций вычисленными блоками генератора и G(x). Компаратор имеет стандартную структуру и строится на основе каскадного соединения k-1 модуля сравнения парафазных сигналов [35]. Структура же генератора определяется правилами построения кода с суммированием. Для синтеза генератора KS(m,k)-кода требуется использование счетчика единиц m-1 разряда и формирование функции паритета. На рис. 3 изображены схемы генераторов S(5,3)-кода и К5(6,3)-кода. Младший разряд счетчика единиц m-1 разряда является функцией паритета [9, 10], а значит, достаточно использовать один сумматор по модулю 2 для формирования старшего контрольного разряда. Общая структура генераторов KS(m,k)-кодов дана на рис. 4. Анализ показывает, что KS(m,k)-код сохраняет свойства обнаружения ошибок, если коэффициент а равен единственному неконтролируемому информационному разряду (см. рис. 5). Это следует из свойства функции сложения по модулю 2 - она принимает равное количество единичных и нулевых значений на всех 2m входных наборах. Свойства кода никак не меняются, а сложность технической реализации генератора уменьшается. Это позволяет предложить другой алгоритм построения модифицированного кода с суммированием. Алгоритм 2. Получение контрольного вектора модифицированного кода Бергера. 1. Подсчитывается вес m-1 информационного разряда (информационного вектора за исключением одного информационного разряда - вектора ). 2. Старшему разряду контрольного вектора соответствует значение неконтролируемого информационного разряда, а оставшимся младшим разрядам - значение веса m-1 информационного разряда. Код, полученный по алгоритму 2, обозначим как МБОп^-код,. В табл. 4 дается распределение информационных векторов между контрольными векторами М£(5,4)-кода, при этом а = f5. Информационные векторы KS(m,k)-кода распределены иначе, чем у MS(m,k)-кодa, однако общий характер сохранен. Генератор М£(5,4)-кода изображен на рис. 6, его можно сравнить с генераторами, приведенными на рис. 3. Нетрудно заметить, что тот же результат дают и другие алгоритмы «сдвига» информационных векторов, например описанные в [21]. Они изоморфны тем правилам, которые описаны в [27]. Например, процедура построения MS(m,k)-кодa может быть описана следующим образом. Алгоритм 3. Построение взвешенного кода с суммированием. 1. Информационному вектору ставится в соответствие вектор весовых коэффициентов [1, 1, ..., 1, 0]. 2. Подсчитывается вес W информационного вектора. 3. Число W представляется в двоичном виде и записывается в младшие разряды контрольного вектора. 4. В старший разряд контрольного вектора записывается значение разряда, для которого вес wm = 0. Этот же результат дает взвешивание одного информационного разряда. Коды с суммированием с одним взвешенным информационным разрядом детально описаны в [36, 37]. f5 f4 --I-4f f2 f1 -l-H- 1 1 1 1 1 HA FA 21 21 1 1 HA 2 б f f5 f f f1 f-H- 1 1 1 FA 21 1 HA 21 2 2 HA 42 2 2 2 FA 4 2 g1 TT g3 g2 g4 g3 g2 g1 Рис. 3. Генераторы кодов с суммированием: а - £(5,3)-кода; б - К£(6,3)-кода gi-l gkrl ••• gl g 1 Рис. 4. Структура генераторов К£(га,£)-кодов Рис. 5. Структура генераторов М£(га,£)-кодов Т а б л и ц а 4 Распределение информационных векторов М3(5,4)-кода между контрольными векторами Вес 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Контрольный вектор 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 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 2 2 Д4 4 2 g4 g3 g2 gl Рис. 6. Генератор М5(5,4)-кода Анализируя алгоритм модификации кодов Бергера, приведенный в [30], можно предложить аналогичный приведенным выше способ построения кода с суммированием. Алгоритм 4. Построение модифицированного кода Бергера. 1. Вес информационного вектора подсчитывается по модулю кода Бергера: M = 2 ^log2 2. Вычисляется значение поправочного коэффициента а, равное значению одного произвольного информационного разряда. 3. Определяется модифицированный вес информационного вектора: W = r+aM. 4. Число W представляется в двоичном виде и записывается в разряды контрольного вектора. Общее количество необнаруживаемых ошибок для кодов, построение которых ведется по алгоритмам 2-4, также может быть определено по формуле (3). Следует заметить, что приведенные способы построения модифицированных кодов Бергера улучшают свойства обнаружения ошибок в информационных векторах кодом, однако в большинстве случаев приводят к увеличению количества контрольных разрядов на единицу по сравнению с кодом Бергера. Утверждение 1. Модифицированный код Бергера будет всегда обнаруживать 100% любых видов ошибок в информационных векторах, кроме некоторой доли симметричных ошибок, которая, однако, будет меньше, чем у кодов Бергера, и при этом будет иметь такое же количество контрольных разрядов при выполнении следующего условия: m = 2 (t е{1,2,...}). (4) Формулировка утверждения 1 следует непосредственно из алгоритмов 1-4. Только в одном случае, когда сохраняется условие (4), не потребуется при модификации кода добавления еще одного контрольного разряда. В самом деле, в табличной форме задания кода с суммированием (табл. 4) заполняются только m+1 контрольные группы, при этом общее их количество равно 2[log2(m+1)] = „Г1оВ2(2+1)П (5) = 2 = 2 где t = log2 m . Подставим в (5) значение t: 2t+1 = 2log m+1 = 2 • 2logm = 2m. (6) Из выражения (6), таким образом, следует, что количество контрольных групп при выполнении условия (4) будет равным 2m. Изначально заполнены m+1 группы. В контрольной группе, соответствующей максимальному весу информационного вектора, в группе с номером m будет присутствовать только один информационный вектор. При модификации по любому из предложенных алгоритмов сдвигается вправо по таблице задания кода (см. табл. 4) ровно половина информационных векторов, /з /2 Л Л А 1 1 2 1 1 НА включая и данный вектор, заполняя тем самым оставшуюся m-1 группу. Добавления нового контрольного разряда не требуется. Этим объясняется утверждение 1. Определим, во сколько раз уменьшается количество симметричных необнаруживаемых ошибок у модифицированных кодов Бергера с увеличением длины информационного вектора: Cm 2m (7) 2C2 m-2 2 Перейдем к пределу: ( 2m )! m! • m! - 2m f-мп rs m lim & = lim--2m-- • = lim - (2m - 2)! - 2m (m -1)! (m -1)! m2C - 2m 2m-2 Z' (2m )2 2 - 2m V^e-2" (2m)2m+2 1 „ / m+- /--m +- \j2ne-mm 2 •V2ne-mm 2 { 1V m+- 2 --2m m = lim- • = lim - V^e-2"-2 (2m - 2) 2m-2+- 2 2m-2+- 2 (2m - 2) --2m --2m V2^e-m-1 (m -1)-1+2 •Jhie-m-1 (m - 1)-1+2 (m - 1) 2m+-2 (2m ) -1 (2m )2 Г 1V m+- 2 m 2 2m+1 2m+1-2m-1 2 2 m 2 1 1 m +-+m +- 2 2 m = lim- • = lim - • = lim - > 2m- 2+- 2 • 2 2 (2m - 2 )2 2m-2+-2 (2m - 2) (m -1)2 -1 m-1+-+m-1+1 2 2 2m|(m-1) (m -1) = 2 lim, M= 2limi -1 = 2. 1 1 1 2m+- - 2 2 m 2 (8) 2m+-1-2m+2- - = lim 2 2 2 1 m^w = lim- 1 > 2m-2+- 2 • 2 2 m (m -1)m 4m -1 Таким образом, справедливо следующее положение. Утверждение 2. Отношение количества необнаруживаемых симметричных ошибок в классических и модифицированных кодах Бергера с увеличением длины информационного вектора уменьшается и в пределе при m ^ да стремится к 2. Таким образом, модифицированные коды Бергера примерно в два раза эффективнее обнаруживают ошибки, чем классические коды Бергера. Анализируя схемотехнические особенности контрольного оборудования систем функционального контроля, заметим, что генераторы модифицированных кодов Бергера являются более простыми, чем генераторы классических ^(га,^)-кодов. Но в системе функционального контроля во всех случаях, кроме случая (4), блок контрольной логики G(x) будет реализовывать еще одну контрольную функцию, а компаратору, соответственно, потребуется на один модуль сравнения парафазных сигналов больше, чем компаратору классического кода Бергера. В табл. 6 приводятся результаты экспериментальных исследований модифицированных кодов Бергера в сравнении с классическими кодами Бергера в системах функционального контроля на ряде контрольных комбинационных схем из набора LGSynth89 [38]. В эксперименте оценивалась сложность технической реализации систем функционального контроля, организованных по кодам с суммированием (табл. 5). Показателем сложности технической реализации является площадь, занимаемая устройством на кристалле. Для анализа данного показателя была выбрана библиотека функциональных элементов stdcell2_2.genlib. Контрольные комбинационные схемы в LGSynth89 представлены в виде файлов списочной формы задания структуры логического устройства - net-листа. С использованием специально разработанного программного обеспечения были получены net-листы всех блоков системы функционального контроля, а затем с применением известного интерпретатора SIS [39] получены значения площадей в условных единицах. В последней графе табл. 5 представлено значение величины Z - отношение площадей систем функционального контроля, организованных по классическим и модифицированным кодам Бергера. Анализ данного коэффициента показывает, что использование модифицированных кодов Бергера эффективно по показателю сложности технической реализации в том случае, если выполняется полученное выше условие (4). Этот результат был ожидаем, однако не следует забывать, что характеристики обнаружения ошибок в системах функционального контроля, организованных по модифицированным кодам Бергера, улучшены, а увеличение сложности есть «цена» за это свойство. Т а б л и ц а 5 Сложность технической реализации систем функционального контроля Контрольная комбинационная схема Число выходов Площадь системы функционального контроля S(m,k)-код MS(m,k)-код Z cm42a 10 8928 10712 0,833 f51m 8 13112 10152 1,292 pm1 13 16144 20880 0,773 x2 7 4096 4856 0,843 z4ml 4 4192 2976 1,409 Общий недостаток всех приведенных алгоритмов заключается в том, что не дает возможности построения кода, эффективно использующего свои контрольные разряды. Повышение эффективности возможно за счет применения модулей представления веса, меньших, чем модуль кода Бергера. Например, в табл. 6 дается распределение информационных векторов между контрольными векторами МБ(т,к)-кода, у которого для подсчета веса информационного вектора используется модуль М = 2^log2Применение модуля дает уменьшение количества контрольных разрядов. Но при этом появляется некоторое количество монотонных ошибок, все они имеют кратность d = М (векторы, допускающие монотонные ошибки, в табл. 6 выделены серым фоном). Это свойство можно использовать при построении надежных устройств автоматики и вычислительной техники [32]. Т а б л и ц а 6 Распределение информационных векторов М3(5,3)-кода между контрольными векторами Вес 0 1 2 3 4 5 6 7 Контрольный вектор 000 001 010 011 100 101 110 111 00000 00001 00011 00111 10111 10000 10001 10011 01111 00010 00101 01011 11011 11111 10010 10101 00100 00110 01101 11101 10100 10110 01000 01001 01110 11110 11000 11001 01010 11010 01100 11100 Заключение В статье приводятся способы модификации кода Бергера, позволяющие построить модифицированный код с суммированием, обладающий основным свойством кода Бергера - способностью идентифицировать все монотонные ошибки. Модифицированные коды Бергера обнаруживают, кроме того, некоторое количество симметричных ошибок (коды Бергера не обнаруживают стопроцентных симметричных ошибок [25, 32, 40]). Это свойство можно использовать для уменьшения избыточности систем функционального контроля при применении известных алгоритмов модификации контролируемых схем [8, 28, 29]. Предложенные алгоритмы построения модифицированных кодов с суммированием, в отличие от описанных в [27], дают более простые структуры генераторов кодов с суммированием и в некоторых случаях более простые структуры систем функционального контроля. Установлено, что максимальный эффект при обнаружении ошибок в информационных векторах кодов при минимальных аппаратурных затратах достигается для кодов с длинами информационных векторов m = 2 (t е {1,2,...}). Стоит отметить, что описанные коды с суммированием не являются оптимальными в смысле использования контрольных разрядов, а значит, правила построения кодов могут быть «усовершенствованы», например, могут быть использованы свойства реальных схем, на выходах которых формируются не все 2m информационных векторов, и код может формироваться для некоторого множества информационных векторов.

Скачать электронную версию публикации