Файл: Торгашев В.А. Система остаточных классов и надежность ЦВМ.pdf

Следовательно, вектор /1 может иметь d ненулевых компо­ нент, если по меньшей мере d оснований СОК содержат делители,

ным делителем основания М, можно утверждать, что произведение

оснований СОК должно делиться на величину М а = (g i'g j3. ■•

Однако по определению /.-кода R = PjM , так как L = М. Следо­ вательно, у L-кода с минимальным расстоянием d величина степени

= Md

Достаточность условия теоремы следует из того, что никакое кодовое слово не может иметь вес, меньший чем вес векторов, со­ ответствующих числам вида А = M/gu так как эти числа содержат максимально возможное число делителей основания М.

Таким образом, явно нецелесообразно применять корректирую­ щие /.-коды для обнаружения или исправления таких ошибок, ко­ торым с равной вероятностью соответствуют произвольные искаже­ ния символов СОК. Сднако если ограничить класс возможных ошибок в отдельных символах, то возможности L-кодов рас­ ширяются.

Как известно, любой линейный корректирующий код позволяет обнаруживать все ошибки, не являющиеся кодовыми словами. Если степень избыточности равна R, то доля ошибок, обнаруживаемых кодом, равна (R — 1)//?.

Критерием, позволяющим определить, относится ли некоторый вектор Л к кодовым словам, может служить условие леммы 1.1. Если существует хотя бы одна пара символов ctj и а3вектора Л,

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

ляется делителем основания р,-. Если каждый из модулей р,- имеет

представлениях остатков а,, ..., ат .

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

с двумя другими модулями СОК.

Предположим, что основания pi,,pj,ph являются попарно непро­ стыми числами. Для любого вектора А = (<і|, ..., <xm) вычислим разность остатков

50

Пример 2.2. Рассмотрим систему остаточных классов, все моду­ ли которой имеют общий делитель, равный g.

Данный код позволяет обнаруживать не только одиночные ошибки, но и искажения максимум пяти двоичных разрядов, соот­ ветствующих различным основаниям СОК. Кроме того, с помощью этого кода обнаруживаются любые ошибки, удовлетворяющие условию

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

Таким образом, корректирующие возможности такого кода до­ вольно высоки, хотя минимальное расстояние d= 1, так как, на­ пример, число Lj3 соответствует кодовому слову, у которого лишь первая компонента является ненулевой и соответственно вес этого слова w — 1.

группах, а также обнаруживать двойные ошибки в пределах груп­

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

Что касается недостатков, то здесь в первую очередь следует упомянуть тот факт, что /.-коды с приемлемой избыточностью не •позволяют исправлять, а порой и обнаруживать любые ошибки за­ данной кратности, даже одиночные. Кроме того, при использовании /.-кодов система остаточных классов, как правило, содержит до­ вольно большие по величине модули, что приводит к определенному усложнению арифметического устройства.

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

Более эффективными могут оказаться смешанные RL-коды, ко­ торые соответствуют СОК с попарно непростыми основаниями при L < М. В этом случае, изменяя отношение М/L, можно получить любые минимальные расстояния, так же как в обычном Д-коде. Но, кроме того, появляется возможность обнаруживать и исправ­ лять значительное число ошибок более высокой кратности.

Пример 2.4. Добавив к системе остаточных классов, приведен­ ной в примере 2.2, еще один модуль р8= 19-3=57, получим кор­

52

жет обнаруживать, кроме любых одиночных, 95,96% ошибок произ­ вольной кратности. Кроме того, он может исправлять практически любые одиночные ошибки и часть ошибок с кратностью 2,3 и даже 4.

Читатель, наверное, уже обратил внимание на то, что основные свойства и возможности L и RL-кодов описываются скорее каче­ ственно, чем количественно. Дело в том, что насколько известно автору, до сих пор никто не занимался достаточно серьезным изуче-. кием свойств систем остаточных классов, основания которых не являются взаимно простыми числами. Поэтому изложенный в этом, разделе, а также в предыдущей главе материал, относящийся к та­ ким системам остаточных классов, следует рассматривать лишь как первый шаг в данном направлении.

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

Что же касается L и ЯА-кодов, то эта область еше ждет своих исследователей.

2.4. ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК ПРИ ПОМОЩИ я-кодов

Для того чтобы выяснить, является ли некоторый вектор Ä ко­ довым словом Я-кода, необходимо определить величину соответ­ ствующего числа А. Если это число принадлежит множеству L, то

теристики ЯлДА) вычисляются в ходе выполнения любой немо­ дульной операции. Следовательно, попутно с выполнением любой такой операции осуществляется обнаружение ошибок. Если немо­ дульные операции встречаются в ходе решения задачи, достаточно часто, то нет необходимости вводить специальную операцию обна­ ружения ошибок, т. е. в данном случае для обнаружения ошибок

не потребуется добавочных затрат времени.

Для исправления ошибок необходимо прежде всего определить,

и определим величину числа,-соответствующего вектору {Д}

53