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

С другой стороны, рассмотрим множество 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