книги из ГПНТБ / Торгашев В.А. Система остаточных классов и надежность ЦВМ

Следовательно, вектор /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

Если окажется, что это число принадлежит множеству L, то можно утверждать, что именно в исключенном модуле произошла ошибка. Если же число не попадет в интервал L, то перейдем к вектору {А}м ір, и будем выполнять аналогичные действия до тех пор,

смогли локализовать ошибку. Это означает, что ошибка не являет­

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

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

Поэтому рассмотрим еще один метод, использующий свойства

соответствуют искаженным символам кодового слова. Тогда, если

где X = LjN\ R , = MjN\ A' — число, соответствующее искажен­ ному кодовому слову.

Доказательство. Положим А' = А + Д, где А — кодовое слово,

а Д — вектор ошибки. По условию теоремы все ненулевые состав­

ляющие вектора Д соответствуют тем основаниям СОК, которые входят в произведение Q. Поэтому Д = qMjQ, где q — целое по­ ложительное число, меньшее Q.

Следовательно:

Рассмотрим теперь разность А — |Л '|іѵ. Поскольку положитель­ ная величина | Л' | л<7Ѵ, а число А лежит в интервале (— (X— 1) JV, N), то данная разность должна удовлетворять нера­ венству

Прибавим ко всем частям этого неравенства величину ХМ, получен­ ное выражение умножим на QIN и подставим в это произведение значение А из формулы (2.15). Тогда:

54

Но по определению позиционной характеристики

*лг (Л') - [A'IN] = (А' — [ А' IN )IN.

Поэтому, вычисляя остатки от деления всех членов неравенства

женные символы.

Итак, для локализации ошибок в системе остаточных классов достаточно последовательно проверять справедливость неравенства (2.14) при Q = рй Q = pif,j (где і, } — 1, 2, ..., т; і Ф j ) и т. д. Если для какого-нибудь произведения оснований СОК это неравен­ ство окажется справедливым, то следует определить величину чис­ ла Л, представленного в сокращенной СОК, в которой отсутствуют модули, входящие в состав данного произведения. При попадании числа А в интервал L можно утверждать, что именно в этих мо­ дулях произошли ошибки и истинные значения искаженных симво­ лов в этом случае можно определить расширяя СОК. до исходной величины. Если же число не попадает в интервал L, то следует перейти к проверке другой комбинации оснований. Проверку нера­ венства (2.14) можно выполнять в СОК. с основанием Ru и если в некоторое произведение Q входят t модулей, то для такой провер­ ки потребуется t + 1 модульная операция, а не п операций, как

впредыдущем случае.

Втех случаях, когда по каким-либо причинам переход к вы­

числениям в сокращенной СОК нежелателен, можно за счет неко­

если произведение контрольных модулей не меньше произведения

;= i

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

таких кодовых слова Л, и Аг и два вектора ошибки Д, и Д2, что

™ЛГ ( 4 ) = 14V (^2), '

где а { = Ді + Д„ А2 = А2 + А,.

Подставляя эти значения А'г и А2 в выражения, соответствую­ щие позиционным характеристикам, получим следующее равенство:

55

вес которого не превышает величины 2k = d — 1. Поэтому

или

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

два различных вектора Ді и Д2, соответствующих одному значению позиционной характеристики. Что и требовалось доказать.

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

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

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

Пусть А' = А + А и яд- = (А' — 1А’ \jv)/N.

56

Выполним еще одно эквивалентное преобразование этого выражения:

№+ A - ] A ' M Q

Иногда удобнее вычислять ошибку с обратным знаком для того, чтобы вместо вычитания прибавлять ее к искаженному числу. Тогда, обозначив б = Ttjv + А., получим следующее выражение:

Итак, для того чтобы определить вектор ошибок, сначала сле­ дует вычислить все остатки, соответствующие представлению вели­ чины \ÖQ\R в исходной СОК, с основанием М с помощью расши­

рения системы с основанием R ь Для этого потребуется t модуль­ ных операций. Кроме того, необходимо еще выполнить операции вычитания и умножения на константы.

Пусть Q = Q„QK, где Q« — произведение информационных мо­ дулей, которым соответствуют ошибки; QK— произведение иска­ женных контрольных модулей. Тогда

18Q ltf,/Q — I SQii IRIIQJQ "'

В этих случаях для вычисления вектора ошибки следует в фор­ мулах (2.21) и (2.22) заменить Q на QH и Я г на /?,/QK.

В некоторых случаях, зная вес вектора {лл'}#,. можно оценить

число ошибок, воспользовавшись следующей теоремой. Теорема 2.9.

Если минимальное расстояние R -кода равно d и вес одного из векторов {Ч/ѵ}# аЛи {KN + 1}/?, равен t > !г, то число оши­

бок, исказивших кодовое слово А, не меньше, чем d — t.

Доказательство. Предположим сначала, что А является поло­ жительным числом. Тогда числу \А — |Л'|,ѵ| соответствует кодовое слово, вес которого не может быть меньше, чем d, если А ф ( \ А '\ к . С другой стороны, из формулы (2.20) следует, что

\Ѵ (N T.N ~ & ) = W (A — \A 'lN ) > d -

57

Воспользовавшись выражением (2.3), получим следующее не­ равенство:

W (Д) > W (NnN — Д) — № (АГтсд,) > d — t,

так как

W (ІѴпдг) = W {ядг}^.

Если число Л отрицательно, то величине ЛГ + А — | А' |Лг соот­ ветствует некоторое кодовое слово. Поэтому

процедура их исправления резко упрощается. В этом случае можно воспользоваться следующей теоремой.

Так же как и в предыдущем случае, это неравенство справедливо лишь тогда, когда N + А — \А ‘ |дг=0. Поэтому {Д} М={(«лг + 1)^}Л '

Теорема доказана. Следствие 2.10.1.

Если выполняются условия теоремы 2.10, то ошибки встречают­ ся лишь в контрольных модулях.

58

не менее k + 1 не нулевых компонент, то в символах, соответ­ ствующих информационным основаниям, произошла по мень­ шей мере одна ошибка.

у которого в символах, соответствующих модулям рз и рт, произо­ шли ошибки Д а з = 4 ; Д<Х7=10. Тогда

і= 1, 2, 3.

Вданном случае величина б умножается только на информа­ ционные основания, так как нам заведомо известно, что если ошиб­ ка является одиночной, то, в соответствии со следствием 2.10.2, она

не может произойти в каком-либо из контрольных модулей.

№. = {8,9,11,2,1}^;

{8і}/?,/п = {6>8- 4' !}/?,/и; {В7}^. = {9,1°, І2 ,16,2}^;

{В>}/?,/11 = {6>8>8>^Я ./П ’

№ , = {4. 4, 4,7,1}^;

= {°>°> 2>°}/?,/іг

59