On the problem of modified codes with summation of weighted data bits with natural numbers sequence of weight indexes ge.pdf В задачах технической диагностики дискретных систем часто применяют разнообразные коды с суммированием [1-17]. Данные коды принадлежат к классу систематических - в кодовых словах таких кодов выделяют информационный и контрольный векторы с длинами т и k соответственно. Введем обозначение для кодов с суммированием - (т^)-коды. Применение (т^)-кодов в задачах технической диагностики, например при синтезе систем с обнаружением отказов [18-20], связано с внесением избыточности в структуру «базового» объекта. При этом способ построения кода напрямую определяет характеристики избыточности получаемого технического объекта, а также особенности идентифицируемых в нем неисправностей. Наиболее простым среди известных кодов с суммированием является классический код Бергера [21]. Данный код имеет k = |~log2(m + i)] разрядов в контрольных векторах (запись [...] обозначает целое сверху от вычисляемого значения), принимающих значения разрядов двоичных чисел, равных сумме единичных информационных разрядов (равных весу информационного вектора). Такие особенности построения кода Бергера приводят к крайне неравномерному распределению информационных векторов между контрольными векторами, что в конечном итоге сказывается на свойствах обнаружения им ошибок. Кодами Бергера не обнаруживается любая симметричная ошибка в информационном векторе (такая ошибка не нарушает веса информационного вектора и происходит при одинаковом количестве искажаемых нулевых и единичных разрядов [22]). Вне зависимости от длины информационного вектора кодами Бергера не обнаруживается одинаковый процент ошибок четной кратностью d от общего количества ошибок данной кратностью [23-25]. Это, к примеру, 50% двукратных и 37,5% четырехкратных ошибок в информационных векторах. С неравномерностью распределения информационных векторов между контрольными связано и большое общее количество необнаруживаемых ошибок в информационных векторах кодов Бергера. Тем не менее данные коды нашли широкое применение за счет их свойства обнаружения любых монотонных ошибок в кодовых словах [26-31]. Любые модификации классических кодов связаны с перераспределением информационных векторов между контрольными векторами, что позволяет уменьшать количество необнаруживаемых в информационных векторах ошибок. В [32] введено понятие оптимального по критерию минимума общего количества необнаруживаемых ошибок (т^)-кода с установленными значениями длин информационных и контрольных векторов и показано, что классический код Бергера далек от оптимального кода. В [33] разработан перспективный для задач технической диагностики модифицированный код Бергера, основанный на идее взвешивания разрядов информационных векторов и последующих операциях модификации значения суммарного веса информационного вектора. Данная работа посвящена изложению способа синтеза генератора, или кодера, данного оптимального кода с суммированием. 1. Модифицированный код Бергера Как отмечалось выше, способ построения оптимального (m,k)-кода базируется на первоначальном установлении неравноправия между разрядами в информационном векторе путем приписывания им различных весовых коэффициентов [10, 13, 21, 34-36], а значения разрядов контрольных векторов получаются следующим образом. Алгоритм 1. Правила построения оптимального кода с суммированием: 1. Устанавливается последовательность весовых коэффициентов разрядов информационного вектора, образующая натуральный ряд чисел, начиная с младшего разряда. 2. Вычисляется значение модуля M = 2 ^log2 (m+1)l-1. 3. Определяется значение суммарного веса единичных разрядов информационного вектора: m W = £ wifi, (1) i=1 где fi = 0 или fi = 1 - значения разрядов информационного вектора. 4. Определяется наименьший неотрицательный вычет числа W по модулю M: [W ]M = W (mod M). (2) 5. Вычисляется специальный поправочный коэффициент а как функция паритета разрядов информационного вектора, занимающих позиции с четными номерами, начиная с младшего разряда: \ f2 Ф f4 Ф... Ф fm, если m - четное; а = < (3) [f2 Ф f4 Ф... Ф fm-1, если m - нечетное. 6. Формируется значение результирующего веса информационного вектора: V = [W ]M +oM. (4) 7. Число V представляется в двоичном виде и записывается в разряды контрольного вектора. Получаемые по алгоритму 1 коды с суммированием обозначим как RWS(m,k)-коды. Они принадлежат к классу модифицированных модульно взвешенных кодов с суммированием и имеют такое же количество разрядов в контрольных векторах, как и классические коды Бергера, однако обладают улучшенными характеристиками обнаружения ошибок в информационных векторах. Пользуясь алгоритмом 1, приведем пример построения ^Ж£(4,3)-кода (табл. 1). Т а б л и ц а 1 Кодовые слова RWS(4,3)-кода № п/п Информационный вектор W Wm A V Конт рольный вектор f4 А fi fx g3 g2 g1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 1 0 2 2 1 6 1 1 0 3 0 0 1 1 3 3 1 7 1 1 1 4 0 1 0 0 3 3 0 3 0 1 1 5 0 1 0 1 4 0 0 0 0 0 0 6 0 1 1 0 5 1 1 5 1 0 1 7 0 1 1 1 6 2 1 6 1 1 0 8 1 0 0 0 4 0 1 4 1 0 0 9 1 0 0 1 5 1 1 5 1 0 1 10 1 0 1 0 6 2 0 2 0 1 0 11 1 0 1 1 7 3 0 3 0 1 1 12 1 1 0 0 7 3 1 7 1 1 1 13 1 1 0 1 8 0 1 4 1 0 0 14 1 1 1 0 9 1 0 1 0 0 1 15 1 1 1 1 10 2 0 2 0 1 0 Данный код не обнаруживает 8 двухкратных и 8 четырехкратных ошибок в информационных векторах (для сравнения: кодом Бергера при данной длине информационного вектора не обнаруживается 48 двухкратных и 6 четырехкратных ошибок [23]). Вообще RWS(m,k)-кодами идентифицируется гораздо больше ошибок малых кратностей, чем кодами Бергера. Кроме того, данный класс кодов, так же как и коды Бергера, обнаруживает любые ошибки нечетных кратностей в информационных векторах. 2. Синтез генераторов модифицированных кодов Бергера Поскольку при построении RWS(m,k)-кодов используются операции суммирования весовых коэффициентов и значений разрядов информационных векторов, в качестве элементной базы для их генераторов удобно использовать стандартные схемы сумматоров по модулю два (XOR), полусумматоров (HA) и полных сумматоров (FA) [7, 37-39]. На рис. 1 приводятся условные обозначения данных функциональных элементов. При этом в условных обозначениях полусумматора и полного сумматора на входах и выходах указаны веса разрядов двоичных чисел. S б в а Рис. 1. Условные обозначения типовых функциональных элементов: а - сумматора по модулю два; б - полусумматора; в - полного сумматора Сумматор по модулю два реализует операцию сложения двух одноразрядных чисел без переноса и вычисляет функцию s = fi ©л. Схемы полусумматора и полного сумматора предназначены для сложения двух и трех двоичных чисел. Полусумматор имеет два входа и два выхода, на которых формируется двоичное число, равное суммарному количеству единиц на его входах: fS = fi © f2; 1С = fi f 2 ■ Аналогичную полусумматору функцию выполняет полный сумматор, имея при этом, однако, три входа и два выхода, описываемых следующими формулами: fS = fi © f © f3; 1С = f1f2 V f1f3 V f2f 3 . Согласно (1) генератор RWS(m,k)-кода должен сначала подсчитать сумму весовых коэффициентов единичных разрядов информационного вектора, затем вычислить по формуле (2) наименьший неотрицательный вычет для полученного числа и прибавить к нему значение модуля при а = 1 или сохранить неизменным при а = 0. Таким образом, структурная схема генератора RWS(m,k)-кода может иметь вид, представленный на рис. 2. В генераторе выделяется четыре функциональных блока: B1 предназначен для «взвешивания» разрядов; B2 - устройство суммирования весовых коэффициентов; B3 - схема определения наименьшего неотрицательного вычета суммарного веса единичных информационных разрядов; B4 - формирователь старшего разряда контрольного вектора. Схема генератора RWS(m,k)-кода может быть построена и иным образом. Преобразуем выражение (4), подставив в него выражения (1) и (2): V = [ W ]M + aM = W (mod M ) + aM = jj J wf j(mod M ) + aM : = (■wji + w2 f2 + ... + W mfm ) (d M ) + aM = = w1 f1 (modM) + w2 f2 (modM) +... + wmfm (modM) + aM. gk gk-1 gk-2 *' • g2 g 1 Рис. 2. Структурная схема первого типа генератора RWS(m,к)-кода Из формулы (5) следует, что перед тем, как определять суммарный вес единичных информационных разрядов, можно напрямую вычислять наименьшие неотрицательные вычеты для каждого весового коэффициента. Таким образом, структурная схема генератора RWS(m,k)-кода примет вид, изображенный на рис. 3. В ней также выделяются четыре функциональных блока: B1 предназначен для «взвешивания» разрядов; B2 - устройство определения наименьших неотрицательных вычетов для каждого весового коэффициента; B3 - схема суммирования наименьших неотрицательных вычетов весовых коэффициентов единичных разрядов по установленному модулю M; B4 - формирователь старшего разряда контрольного вектора. Фактически блоки B1-B3 могут быть построены путем каскадного соединения типовых схем сложения двоичных чисел по заданному модулю M. Такая типовая схема изображена на рис. 4. На ее входы подаются два двоичных числа A = и B = , являющиеся двоичными представлениями наименьших неотрицательных вычетов по модулю M двух весовых коэффициентов. А на выходах формируется сумма чисел A и B за исключением переноса в старший разряд при переполнении -число S = . В частности, на рис. 5 изображены типовые схемы сложения двоичных чисел по модулям M = 4, 8 и 16, используемым при формировании RWS(m,k)-кодов с длинами информационных векторов m < 32. fm fm-1 f2 f1 Рис. 3. Структурная схема второго типа генератора RWS(m,k)-кода Целесообразно синтезировать генераторы по структурной схеме, приведенной на рис. 3, следующим способом. Алгоритм 2. Правила синтеза генераторов RWS(m,k)-кодов. 1. Устанавливается значение модуля M. 2. Определяется наименьший неотрицательный вычет по модулю M для каждого весового коэффициента W{: [W, ]m = W, (modM) 3. Каждое число [w, ]M представляется в двоичном виде. 4. Единичным разрядам двоичных чисел [w, ]M ставятся в соответствие значения разрядаf. 5. Осуществляется разбиение двоичных чисел [w, ]M на пары с учетом оптимального заполнения раз рядов: числа [w, ]M разбиваются на групп, каждая из которых представляет собой пару двоичных чи- 6. Выполняется сложение чисел с учетом значений их разрядов и получение двоичных чисел. устройство суммирования двоичных чисел. т 2 сел, полученных в п. 4 данного алгоритма, суммирование которых осуществляется без переносов. m 2 7. С использованием функциональных блоков сложения двоичных чисел модулю M реализуется m 2 8. Реализуется блок вычисления старшего разряда контрольного вектора. Из алгоритма 2, в частности, следует, что блоки B1 и B2 генератора не требуют функциональных элементов и содержат только провода, на которые подаются сигналы 0 или f. Более того, из п. 6 алгоритма следует, что фактически первым каскадом блока B3 будут выступать только провода с поданными на них сигналами 0 или f. Таким образом, алгоритм 2 подразумевает некоторую оптимизацию структуры генератора ЯЖБ(т,к)-кода. Продемонстрируем работу алгоритма 2 на примере синтеза генератора ЛЖ^(8,4)-кода. Определим значения наименьших неотрицательных вычетов для всех весовых коэффициентов w, и представим их в двоичном виде. После этого в каждом двоичном представлении вычета веса w все единичные разряды заменяем значениями соответствующего информационного разряда fi, а все нулевые разряды оставляем заполненными значениями 0. Результат приведен в табл. 2. Т а б л и ц а 2 Получение суммируемых двоичных чисел Весовые коэффициенты W8 w7 W6 W5 w4 w3 w2 Wj 8 7 6 5 4 3 2 1 [w ]M 1000 0111 0110 0101 0100 0011 0010 0001 Двоичное число, соответствующее весу f8000 0fff7 0ff60 0/50/5 0f400 00//з 00f20 000f1 " 8' 2 группе должны складываться без переносов (см. рис. 6). Данные двоичные числа требуется сложить по модулю M= 8 с использованием функциональных блоков, изображенных на рис. 5, б. Так как получено четыре двоичных числа, то потребуется три функциональных блока. Отдельно реализуется функция паритета а = f2 Ф f4 Ф f6 Ф f , вычисляющая старший разряд контрольного вектора ЛЖ^(8,4)-кода. Синтезированный генератор рассматриваемого кода представлен на рис. 7. На каждой его линии указаны логические сигналы 0 и 1, соответствующие вычислению значений разрядов контрольного вектора при поступлении на входы генератора информационного вектора . Далее полученные двоичные числа разбиваются на = 4 группы. При этом числа в каждой Рис. 5. Структурные схемы функциональных блоков ZM: а - сложения по модулю M = 4; б - сложения по модулю M = 8; в - сложения по модулю M = 16 в W7= < O/7/7/> w2 = < 0 0 / 0 > w3 = < о о// > + w8= w6= w5 = w4=< 0/00 > w7+w8 = wi+w6 = < О/б/б/ > w2+w5 = < О/// > W3+W4= < O/4/3/3 > (w2+w5)(mod8) = (w7+w8)(mod8) = (wi+W6)(mod8) = (w3+w4)(mod8) = Рис. 6. Получение двоичных чисел, суммируемых на входах функциональных блоков сложения по модулю M = 8 /б fi fe fi 1 0 10 /1 fi /4 /5 /з /2 0 0 0 Oil /3 /5 1 0 1 НА 2 Рис. 7. Генератор разрядов контрольного вектора ,КЖ?(8,4)-кода Поскольку все весовые коэффициенты RWS(m,k)-кода при использовании алгоритма 2 делятся на групп для их последующего суммирования, справедливо следующее положение. Утверждение 1. Генератор RWS(m,k)-кода содержит формирования старшего контрольного разряда, включающий в себя (запись [...J обозначает целое снизу от вычисляемого значения). Сформулированное выше положение о количестве функциональных элементов в структуре генератора модифицированного кода Бергера позволяет дать оценку сложности его технической реализации в зависимости от длины информационного вектора. Одним из таких показателей является количество двухвходовых элементарных логических элементов, требующихся для реализации генератора [6]. Данный показатель известен для сумматора по модулю два, полусумматора и полного сумматора [40]: LXoR = 3, Lha = 3, Lfa = 7. Зная эти данные, нетрудно оценить сложность технической реализации функциональных блоков Хм: Le 4 = 9, LE8 = 16 и LE6 = 23. В табл. 3 приводятся рассчитанные значения показателя сложности технической реализации генераторов RWS(m,k)-кодов при длинах информационных векторов m = 3^20, а на рис. 8 иллюстрируется зависимость сложности технической реализации генераторов от длины информационного вектора. Она носит линейный характер. Формализуем процедуру оценки сложности технической реализации генераторов RWS(m,k)-кодов. -1 функциональный блок Хм и блок -1 сумматоров по модулю два Из утверждения 1 ясно, что сложность технической реализации генератора определяется суммой m 2 m 2 lrws -1 -1 LX (6) Т а б л и ц а 3 Показатели сложности технической реализации генераторов RWS(m,к)-кодов m Формула генератора Количество двухвходовых элементов в структуре генератора 3 2XOR 6 4 1XOR+1Z4 12 5 1XOR+2Z4 21 6 2XOR+2Z4 24 7 2XOR+3Z4 33 8 3XOR+3Z8 57 9 3XOR+4Z8 73 10 4XOR+4Z8 76 11 4XOR+5Z8 92 12 5XOR+5Z8 95 13 5XOR+6Z8 111 14 6XOR+6Z8 114 15 6XOR+7Z8 130 16 7XOR+7Z16 182 17 7XOR+8Z16 205 18 8XOR+8Z16 208 19 8XOR+9Z16 231 20 9XOR+9Z16 234 s,. и ч- -Д • • > • -1- - * v-< >• н У У У 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Длина информационного вектора m 250 200 150 100 50 0 & § s и s s £ s й Я А Я Ш Й ° С ц; К ° S Я « й & О X £ 5 8 1 Я 5 * ° ю И о Рис. 8. Зависимость показателя сложности технической реализации генератора RWS(m,k)-кода от длины информационного вектора Величина Ls в формуле (6) зависит от количества разрядов в контрольных векторах. Каждый такой блок, за исключением случая M = 2, содержит один элемент HA, |~log2 (m +1)| - 3 элемента FA и два элемента XOR (см. рис. 4 и 5). Это объясняется тем, что на полусумматоре реализуется функция вычисления младшего разряда контрольного вектора RWS(m,k)-кода, на к-3 полных сумматорах реализуются контрольные разряды g2, g3, ..., gk-2, а на двух сумматорах по модулю два - контрольный разряд gk-1. Таким образом, сложность функционального блока ZM вычисляется по формуле к = lha + (flog2 (m +^ - 3) lfa + 2lxor . (7) Подставим (7) в (6), а также внесем туда значения LXOR = 3, LHA = 3, LFA = 7. Утверждение 2. Количество двухвходовых элементов в структуре генератора RW5'(m,k)-кода определяется выражением ^ ш 2 Л ( л ( + (( (ш + 1)]- 3) \ (7 • (|"log2 (ш +1)]- 3) + 9) + ш 2 л 3 )lfa + 2 lxor , L - 1 -1 lxor 'RWS (ш ,к) (Y ( 3 • -1 ш л -12 ш ш -1 + 3 ~2 ~2 _ ~2 _ (8) = 7 |log2 (ш +1)) Использование формулы (8) для рассмотренного выше RW5'(8,4)-кода дает следующий результат: -9. LRWS(8,4) = 7 fl0g2 (ш + l)] ш -1I-12 ш + 3 ш 2 J 2 _ 2 _ " 8" -1I-12 " 8" + 3 8 2 J 2 _ 2 _ -9 = 7 |"log2 (8 +1)) + 9 = 57. Заключение Предложенный в настоящей работе алгоритм синтеза генераторов модифицированных кодов Бергера позволяет строить данные устройства с простой структурой на основе каскадного соединения функциональных блоков сложения по модулю M. Сложность структур генераторов с увеличением длины информационного вектора возрастает линейно. Описанный способ синтеза генераторов является универсальным и может быть применен для построения генераторов как кодов с суммированием взвешенных информационных разрядов [10, 34, 4044], так и кодов с суммированием взвешенных переходов между разрядами, занимающими соседние позиции в информационных векторах [13, 35, 45-49]. Однако возможность оптимизации структур генераторов будет напрямую определяться значениями весовых коэффициентов кода.

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