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

Если окажется, что это число принадлежит множеству 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