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

Доказательство. Разделив число М на левую и правую части неравенства (2 .10), получим следующее выражение:

Число А, соответствующее любому кодовому слову Ж, по абсо­ лютной величине меньше L и поэтому не может делиться ни на ка­ кое произведение т — d + I модулей СОК. Если число А делится на некоторый модуль ри то соответствующая компонента вектора А должна равняться нулю. Поэтому число нулевых компонент векто­ ра А не может быть больше т — d и, следовательно, вес вектора А не меньше, чем d. Если все числа А имеют одинаковые знаки, то

тельных чисел. Рассмотрим множество целых положительных чисел

ством множество векторов В образует корректирующий код с ми­ нимальным расстоянием d. Но минимальные расстояния получен­ ного и исходного кодов должны быть равны по построению. Поэто­ му и в случае различных по знаку чисел А теорема справедлива.

ше d, что противоречит условию теоремы. Следовательно, теорема доказана.

Покажем теперь, что Д-код может обнаруживать и исправлять некоторое число ошибок более высокой кратности, чем та, которая допускается, в соответствии с теоремами 2.1, 2.2 и минимальным расстоянием кода. Предположим, что минимальное расстояние кода равнс rf, но в то же время имеются такие основания СОК, число

45

которых rfi d, что произведение этих модулей меньше R. Тогда любые ошибки в этих модулях можно обнаружить *.

составляющие вектора Д), через Q (rf,). Тогда число Д кратно ве­

личине MjQ (йС|)>- M /R = L и, следовательно, удовлетворяет нера­ венству

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

которые не удовлетворяют неравенству (2.12). Доля таких ошибок от' общего их числа не превышает величины 1/R. Поэтому можно утверждать, что Д-код позволяет обнаруживать все ошибки крат­

минимальным расстоянием d используется для исправления ошибок кратности k и ниже, где k = (d — 1)/2. Может ли этот код обнару­ живать или даже исправлять хотя бы часть ошибок более высокой кратности?

Пусть вектор Â', образован из кодового слова Ді в результате

принято кодом за правильное значение исходного вектора. Ошибку можно было бы обнаружить, если бы в пределах расстояния k от вектора Л'\ нашлось еще одно кодовое слово Я3. Но такой ситуа­

чтобы на расстоянии /г от вектора К' і не было ни одного кодового слова. Соответственно, если мы хотим исправить f-кратную ошибку,

ного веса t, которые можно обнаружить или исправить при помощи

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

46

Например, долю произвольных ошибок, которые не могут быть обнаружены кодом, исправляющим к ошибок при минимальном расстоянии d = 2к + 1, можно оценить исходя из следующих сооб­ ражений. Каждый вектор пространства Р можно считать геометри­ ческой точкой. Рассмотрим множество сфер радиуса к, центры которых находятся в точках, соответствующих различным кодовым

бы меньше минимального расстояния кода. Каждая сфера содержит

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

Для определения вероятности исправления данным кодом оши­

мации о возможностях каждого конкретного кода является стати­ стическое моделирование.

В табл. 2.1 и 2.2 приводятся некоторые результаты такого мо­

СОК получены из исходной путем исключения старших оснований:

47

в системе остаточных классов представлены не целые числа, а дро­

ными. Тогда степень избыточности равна или произведению конт­ рольных модулей, или половине этого произведения. Произведение контрольных оснований обозначим символом R і.

Связь между числом контрольных модулей г и минимальным расстоянием d устанавливается следующей теоремой.

Теорема 2.5.

Число контрольных модулей R-кооа с минимальным расстоя­

которых входят г контрольных оснований, естественно, меньше, чем R.

Положим теперь L = 2N, т. е. X— 1 = 1. Тогда

Л = 2 П Рп+і- i=i

48

изведения любых d — 1 оснований СОК, то минимальное расстояние кода равно числу контрольных модулей, т. е. d — г.

Итак, увеличивая или уменьшая число контрольных модулей, можно изменять минимальное расстояние кода. Если некоторая СОК расширяется путем добавления I модулей, каждый и.з которых боль­ ше модулей исходной системы, то минимальное расстояние кода автоматически увеличивается на величину /. Того же эффекта можно добиться, уменьшая число информационных модулей, т. е. переходя к вычислениям с меньшей точностью (с меньшим знаме­ нателем дробей). Следовательно, между корректирующими возмож­ ностями ^-кодов и точностью вычислений существует обратно про­ порциональная зависимость. На одной и той же ЦВМ можно одни вычисления выполнять с высокой точностью, но небольшой надеж­ ностью, а другие — с меньшей точностью, но зато с более высокой надежностью и скоростью, так как время выполнения основных операций пропорционально числу информационных модулей.

2.3. КОРРЕКТИРУЮЩИЕ L И ДІ-КОДЫ

Как уже указывалось выше, сумма, разность и произведение любых векторов L-кода являются кодовыми словами. В отличие от /?-кода в данном случае векторам, которые не являются кодовыми словами, нельзя поставить в соответствие никаких целых чисел.

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

Теорема 2.6.

Для того чтобы L-код имел минимальное расстояние d, необхо­ димо и достаточно, чтобы степень избыточности равнялась Md~l.

Доказательство. В соответствии с теоремой 2.3, минимальное расстояние кода должно равняться наименьшему весу ненулевых кодовых слов. Поэтому найдем условия, которым должен удовлет­