И порождающей матрицей

10 0 0 0

0 10 0 0

0 0 10 0

0 0 0 10

0 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

10 0 0 0

0 10 0 0

0 0 10 0

0 0 0 10

0 0 0 0 1

1 о I I

2 о 2 1 2 2

Второй пример носит более практический характер. Предположим, что ЭВМ и периферийное устройство связаны кабелем, по которому параллельно передаются 4 бита. Четыре бита представляют один 6-10-символ, и передается последовательность таких информационных символов. Нам бы хотелось объединить символы в блоки и защитить каждый блок от одиночных ошибок. Взяв 9 = 16 и m = 2, мы видим, что можно было бы получить (17, 15)-код Хэмминга над полем GF (16) при условии, что такое поле существует. Но поле GF (16) уже было приведено на рис. 2.1 (хотя мы еще не проверили, что оно удовлетворяет аксиомам поля). Используя это поле, можно построить порождающую матрицу (17, 15)-кода Хэмминга над GF (16) и с ее помощью выписать следующие соотношения для проверочных символов:

Pi = h + «2 + is Н-----Н «14 + i

Р-г = к + 22 + Stg Н-----h £«14 + ftis.

После каждого блока из 15 информационных символов ставятся эти два проверочных символа. Используя это, декодер может исправлять одиночные ошибки в блоке из 17 символов. Конечно, все это имеет смысл только в том случае, когда поле GF (16) существует и задано так, как на рис. 2.1. Прежде чем проводить только что описанное построение в некотором поле GF \q), мы должны доказать, что такое поле существует, и задать в нем сложение и умножение.

3.5. СОВЕРШЕННЫЕ И КВАЗИСОВЕРШЕННЫЕ КОДЫ

Представьте себе маленькие сферы с центрами во всех кодовых словах; все эти сферы имеют один и тот же (целеочисенный) радиус. Пусть теперь радиус сфер увеличивается (оставаясь целыми чис-

лами) до тех пор, пока дальнейшее увеличение радиуса будет невозможно без пересечения сфер. Значение этого радиуса равно числу исправляемых кодом ошибок. Этот радиус называется радиусом сферической упаковки кода. Теперь позволим радиусу увеличиваться далее (оставаясь при этом целым числом) до тех пор, пока каждая точка пространства не окажется внутри хотя бы одной сферы. Такой радиус называется радиусом покрытия кода.

Радиус упаковки и радиус покрытия кода могут совпадать; если это так, то построение стандартного расположения закончится в тот момент, когда исчерпаются все векторы внутри сфер радиуса t. Все точки пространства содержатся внутри этих сфер, и ни одна точкане остается вне сфер.

Определение 3.5.1. Совершенный код есть код, для которого сферы некоторого одинакового радиуса вокруг кодовых слов, не пересекаясь, покрывают все пространство.

Совершенный код удовлетворяет границе Хэмминга из задачи 1.5 с равенством. Код Хэмминга, имеющий длину п = (f?" - - \)l{q - 1), является совершенным. Это происходит 1Ютому, что внутри каждой сферы радиуса 1 содержится 1 -j- п (q - I) = q" точек, и число точек в пространстве, деленное на число сфер, равно qn/qk = qin поскольку п - k = т. Совершенные коды (в случаях, когда они существуют) обладают замечательными свойствами, и с ними приятно иметь дело, но они столь редки, что имеют ограниченное практическое значение.

Определение 3.5.2. Квазисовершенный код - это код, у которого сферы радиуса / вокруг каждого кодового слова не пересекаются и все слова, не лежащие внутри какой-либо из этих сфер, находятся на расстоянии t + 1 хотя бы от одного кодового слова.

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

3.6. ПРОСТЫЕ Г ПРЕОБРАЗОВАНИЯ ЛИНЕЙНОГО 2КОДА

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

3.6. ПРОСТЫЕ ПРЕОБРАЗОВАНИЯ ЛИНЕЙНОГО КОДА 75

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

Длину кода п можно увеличить за счет увеличения k или п - k. Мы будем называть такие преобразования удлинением и расширением кода соответственно и объединим оба этих понятия более общим понятием увеличения кода. Под увеличением кода мы понимаем увеличение длины или за счет расширения, или за счет удлинения. Шесть основных преобразований кода выглядят следующим образом.

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

Удлинение кода. Увеличение длины кода путем добавления новых информационных символов, что приводит к увеличению обоих размеров порождающей матрицы на одно и то же число.

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

Укорочение кода. Уменьшение длины кода удалением информационных символов, что приводит к уменьшению обоих размеров порождающей матрицы на одно и то же число.

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

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

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

Любой двоичный (п, k, d*)-Kon, с нечетным минимальным расстоянием можно расширить до (« + 1, А, d* + 1)-кода добавлением к каждому кодовому слову суммы всех его компонент в качестве проверки на четность. Так происходит потому, что в случае, когда исходное слово имеет нечетный вес, к нему будет добавляться единичный символ. Следовательно, все кодовые слова веса d* становятся кодовыми словами веса d* +1. Если Н -