Аналогично определяются окрестности любого порядка, индуцированные множеством S.    Примеры.
   1. Если S - это шар радиуса t в метрике Хэмминга с центром в нуле, т.е. S = { x,||x || Ј t }, то S² - это шар радиуса 2t с этим же центром при 2t < n.
   2. Если S - подгруппа Bⁿ, то S² = S.
   Нетрудно понять, что все окрестности одного и того же порядка равномощны, т.е.

   Теорема 1. Для мощности |V(S)| максимального кода, исправляющего все ошибки из множества S, справедливы неравенства

2n |A2| Ј |V(S)| Ј 2n |A1| .

(7)

   Доказательство. Верхняя граница следует прямо из определения (2), которое утверждает, что окрестности 1-го порядка точек из кода V(S) не пересекаются.
   Для доказательства нижней границы нужно лишь модифицировать процедуру Варшамова - Гилберта:
   1. пусть v - произвольная точка из Bⁿ. Положим v₁ = v и рассмотрим окрестность 2-го порядка точки v₁, т.е. A₂(v₁);
   2. в качестве v₂ выбираем произвольную точку из { Bⁿ\A₂(v₁)};
   3. в качестве v₃ выбираем произвольную точку из { Bⁿ\( A₂(v₁)ИA₂(v₂))};
   4. продолжаем эту процедуру до исчерпания всего Bⁿ.
Относительно построенного кода V(S) = {v₁v₂...v_N} справедливы следующие утверждения.
   I. Код V(S) исправляет все ошибки из S.
   Действительно, если не так, то

vi + e1 = vj + e2

или

vi = vj + (e1 + e2),

т.е. v_i О A₂(v_j), что противоречит построению.

   II. Мощность |V(S)| кода V(S) удовлетворяет неравенству

|V| і 2n |A2| .

Эта граница сразу следует из очевидных неравенств

|A2(v1) И A2(v2) И ј И A2(vN)| Ј N е i=1  |A2(vi)| Ј N|A2|

   Следствие 1. Если S - группа, то

|V(S)| = 2n |S| .

(8)

   Неравенства (7) показывают, что точность границ Хэмминга и Варшамова - Гилберта определяется отношением |A₂|/|A₁|, которое удовлетворяет очевидным неравенствам

1 Ј |A2| |A1| Ј |S|.

(9)

В частности, если S = U₁ И U₂, где U₁, U₂ - подгруппы Bⁿ и |U₂| Ј c, то при больших n

|S2| c|S|

и границы в (7) отличаются в константу раз.
   Таким образом алгебраическая структура множества S сильно влияет на точность границ в (7).
   Примеры.
   1. Пусть в канале происходит любое, но четное число ошибок. Тогда |S| = 2^n-1 и |V(S)| = 2. Действительно, точки a = (11...1) и b = (0...0) образуют код, который исправляет все ошибки из S. Если же в коде V(S) имеется не менее трех точек, то хотя бы две из них имеют вес одинаковой "четности" и не могут быть правильно идентифицированы на приемном конце.
   2. Рассмотрим канал с "разделением ошибок", т.е. после искажения канал некоторое время передает символы безошибочно.
   Определение. Канал S называется каналом с разделением ошибок уровня k, если любое слово x = (x₁x₂...x_n) О S удовлетворяет следующим неравенствам:

   Доказательство. Пусть x = (x₁x₂...x_n) - произвольное решение системы (11) и y₁ < y₂ < ... < y_m - номера всех единичных координат вектора x. Тогда

ys - ys-1 і k,        s = 2,3,...m

и если y₁=y, то

y2 = k + y + z1 ... ym = (m - 1)k + y + (z1 + z2 ... + zm-1),

где z_i і 0 и

z1 + z2 ... + zm-1 Ј n - (m - 1)k + y,

1 Ј y Ј n.

Если e_m(t) - число решений уравнения

где N = n - (m - 1)k - y.
   Для получения финального результата осталось "освободить" y и просуммировать S_m(n,k) по всем m.
   В терминах производящих функций искомый результат выглядит так.
   Пусть

   Следствие.

Fk(z) = z 1-z (zk + z - 1) .

(13)

   Для исправления ошибок в канале S можно использовать код Хэмминга для коррекции одной ошибки в каждом подслове длины k. Таким образом, мы получили код мощности (для больших n и k) порядка

|V(S)| 2n(1-[lnk/k]).

(14)

Использование (7) и (13) приводит к следующей верхней границе:

|V(S)| 2n(1-[(l)/k]),

(15)

где l = log₂ e.

     Вычислительный центр РАН