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

С другой стороны, рассмотрим множество L, содержащее L целых чисел А, таких, что если какие-либо два числа А\ и Л2 при­ надлежат множеству L, то и любое целое число, лежащее между

ствие некоторый вектор Ж£Р, но обратное утверждение справедли­ во лишь в том случае, если M =L=P. При соблюдении этого усло­ вия будем говорить о б е з ы з б ы т о ч н о м представлении чисел в СОК.

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

Для системы со взаимно простыми основаниями М=Р, и по­ этому вопрос об избыточности представления чисел зависит от со­ отношения между L и М. Степенью избыточности представления чисел в СОК назовем величину R = P/L. Избыточность представле­ ния чисел в СОК можно использовать для обнаружения и исправ­ ления ошибок, возникающих в процессе хранения, передачи пли пре­ образования информации.

Корректирующим кодом в системе остаточных классов назовем подмножество К множества Р, состоящее из L различных векторов

Соответствие между векторами А £ Р и числами А £ L можно установить различными способами. Однако свойства кодов практи­ чески не зависят от выбора того или иного способа, а в основном определяются лишь числами L, М и Р. Поэтому в дальнейшем будем предполагать, что числу А = {а,, . . . , ат }уИ соответствует

вектор А = (о,, .. . , ат) в том и только том случае, если аі — а;

для любого і = 1, 2, ... , т. Следовательно, Л = {А }м .

В зависимости от соотношения между величинами L, М и Р в СОК все корректирующие коды можно разбить на три основных класса.

К первому классу относятся коды, соответствующие СОК со взаимно простыми основаниями. Эти коды наиболее пригодны для использования в ЦВМ, и поэтому им будет посвящена боль­ шая часть книги. Такие коды в дальнейшем будем называть ^-ко­ дами.

точных классов не являются взаимно простыми. Первые из этих ко­ дов назовем L-кодами, а вторые — RL-кодами.

40

для всех корректирующих кодов в СОК.

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

мя любыми кодовыми словами. Расстоянием d между любыми двумя векторами Ä\ и >Т2 из множества Р назовем число компонент, в ко­ торых эти векторы отличаются друг от друга. Непосредственно из

Ң2 Л)

3)d (Ді, Л ) > 0;

называют метрикой, а множество элементов, в котором задана мет­ рика, — метрическим пространством.

Величина расстояния между различными векторами множества Р изменяется в пределах от 1 до пі. Интересно отметить, что двум соседним числам А і и А2 (отличающимся на единицу) соответст­ вуют векторы Ä, и Я2, расстояние между которыми равно m для любой системы остаточных классов.

Определим операции сложения, вычитания и умножения век­ торов в пространстве Р так же, как определялись формальные мо­ дульные операции над числами, представленными в СОК (см. § 1.2). Те векторы, которым соответствуют числа, представленные в СОК, одновременно являются скалярными величинами. Таким образом, операция умножения вектора иа скаляр не отличается от умноже­ ния двух векторов. Каждому вектору из множества Р можно при­ своить определенный вес. Весом или весовой функцией W(Ä) век­ тора Я назовем число ненулевых компонент этого вектора.

Очевидно, что расстояние между двумя векторами равно весу

Приведем теперь несколько полезных свойств весовых функций,

41

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

Предположим, что один из символов кодового слова Ä изменил свое значение в результате воздействия какой-либо помехи. Полу­ ченный в результате новый (искаженный) вектор Ä' находится на расстоянии, равном единице от вектора Л . Такую ошибку можно обнаружить лишь в том случае, если вектор Ä' не является кодо­ вым словом. Поэтому все кодовые слова должны быть удалены от вектора Ä иа расстояние, большее единицы. Чем больше расстояние между кодовыми словами, тем больше ошибок может обнаружи­ вать и исправлять такой код.

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

и однозначно определяются вектором {Д}лг, вес которого равен крат­ ности ошибки. Искаженный вектор Ä' получается в результате сло­ жения (или вычитания) кодового слова и вектсра ошибки:

Л' = Л + Д.

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

Теорема 2.1.

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

сти А' — А не может быть меньше минимального расстояния кода,

т. е. должен быть больше, чем I. Следовательно, А' не может быть кодовым словом и условие (2.7) является достаточным для обна­ ружения ошибок с кратностью, не превышающей I.

Предположим теперь, что d min -< /. Тогда найдутся два таких

вектора, принадлежащих коду, разность которых Д = А' — А имеет

вес, равный или меньший I. Но поскольку А' является кодовым

словом, подобное искажение вектора А нельзя обнаружить. Следо-

42

вательно, условие (2.7) является и необходимым. Таким образом, теорема доказана.

Теорема 2.2.

Корректирующий код в СОК может исправить все совокупности

Доказательство. Искажения в векторе И исправимы лишь в том

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

ров Д! и Д2, принадлежащих множеству Е, и любых двух кодо­

вых слов Аі и Л2 справедливо выражение:

Из условия (2.8) следует, что вес разности любых двух кодо­ вых слов не может быть меньше, чем 2k + 1. В то же время, в соответствии с формулой (2.3), вес разности любых двух векто­ ров ошибок, каждый из которых содержит не более k ненулевых компонент, ие может быть больше 2k0. Поэтому для любых кодо­

вых слов А і и И2, а также векторов ошибок Д, и Д2с весом, не

превышающим k, справедливо выражение W (И) — А^фѴК (Д2—Д,). Откуда непосредственно следует справедливость неравенства (2.5).

Докажем теперь необходимость выполнения условия (2.8) для коррекции /е-кратных ошибок. Если минимальное расстояние кода меньше, чем 2Л + 1, то найдутся, по крайней мере, два кодовых слова Ж\ и Лг, разность которых имеет вес, не превышающий 2k. Соответ­

ственно всегда можно найти два таких вектора ошибок Д, н Д2, что

А I — А2 Д[ — Д2.

Следовательно, условие (2.S) не выполняется и по значению искаженного вектора нельзя однозначно получить кодовое слово, что и требовалось доказать.

Из теорем 2.1 и 2.2 следует, что корректирующий код в СОК, исправляющий любые k ошибок и, кроме того, обнаруживающий

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

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

43

или исправляемых ошибок. Минимальное расстояние кода можно определить, если известны веса кодовых слсв.

Теорема 2.3.

Минимальное расстояние корректирующего кода в системе остаточных классов равно минимальному весу ненулевых кодовых

вес которого меньше минимального расстояния кода. Но тогда рас­ стояние между вектором Л3 и нулевым кодовым словом окажется меньше минимального, чего, естественно, быть не может. Следова­ тельно, теорема доказана.

Если множество L содержит числа разных знаков, то мини­ мальное расстояние кода может быть меньше минимального веса кодовых слов. Пусть множество L содержит L\ отрицательных чи­

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

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

2.2. КОРРЕКТИРУЮЩИЕ Д-КОДЫ

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

Теорема 2.4.

Корректирующий R-код имеет минимальное расстояние d в том

44

Доказательство. Разделив число М на левую и правую части неравенства (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, минимальное расстояние кода должно равняться наименьшему весу ненулевых кодовых слов. Поэтому найдем условия, которым должен удовлет­