3.3. СТАНДАРТНОЕ РАСПОЛОЖЕНИЕ б7

+ п - k. Таким образом, минимальный~вес кода не может быть больше \ + п -k. □

Определение 3.2.7. Любой код с минимальным расстоянием, удовлетворяюш,им равенству

называется кодом с максимальным расстоянием.

Граница Синглтона показывает, что для исправления t ошибок код должен иметь не менее 2t проверочных символов (2 проверочных символа на ошибку). Большинство кодов, даже оптимальных, имеют намного больше проверочных символов, чем требует граница Синглтона, но параметры некоторых кодов удовлетворяют границе с равенством. Коды с максимальным расстоянием имеют точно 2t проверочных символов.

3.3. СТАНДАРТНОЕ РАСПОЛОЖЕНИЕ

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

Пусть d* нечетно и d* = 2/ + 1. Внутри сферы радиуса t с центром в нулевом слове находится множество точек

So=ivd(0, v)t\.

Эта сфера содержит все принятые слова, которые декодируются в нулевое кодовое слово. Внутри сферы радиуса t с центром в кодовом слове с находится множество точек

Sc= ivd(c, v)<:/}; I

тогда

Sc = So-f с = {v-f cveSo}.

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

Стандартное расположение представляет собой способ описания всех этих сфер. Пусть О, Сг, сз, ck суть кодовых слов (ft, й)-кода. Построим таблицу, изображенную на рис. З.Ь следующим образом. В первой строке выпишем все кодовые слова-Из оставшихся в Gf" {q) слов, лежащих на расстоянии 1 от нулевого слова, выберем любое и обозначим его v. Во второй строке

Сфера бекобиробйния

Область бекойирования

0 + V,

Сг +V,

Смежный класс

Горизонтальная черта

0+Vj

Сз + v,-

O+y-f Сз-Ач,

Меры смежных классов

Cjfc +V,

C(j/c + Vj

Область межЭу Сферами, тяготеющая к Cj

Рис. 3.1. Стандартное расположение.

запишем О + v,, Сг + v,, Сз-}-vi, с+У\- Таким же,

образом строятся следующие строки. На j-u шаге выберем слово v, которое является ближайшим к нулевому и отсутствует в предыдущих строках, и запишем в /-й строке О + Vj, + v + V/, ck + Vj. Эта процедура закончится, когда после очередного шага не останется неиспользованных слов.

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

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

3.3. СТАНДАРТНОЕ РАСПОЛОЖЕНИЕ 69

/ от нулевого. Когда чешуйки заполнят всю внутренность сферы радиуса t вокруг нулевого слова, проведем в таблице горизонтальную черту. Могут остаться векторы, не занесенные в таблицу выше этой черты, и далее в стандартном расположении эти векторы будут сопоставляться ближайшим, но отчасти произвольным кодовым словам.

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

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

В качестве примера рассмотрим (5, 2)-код с порождающей матрицей

10 111 0 110 1

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

Сферы радиуса 1 не пересекаются. Имеются всего четыре сферы, шесть точек внутри каждой сферы и восемь точек вне каждой сферы.