2. 7. Границы мощности кодов

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

Рассмотрим основные нижние и верхние границы относительно мощности двоичных кодов, т.е. когда алфавит канальных символов представляет собой поле Галуа GF( 2 ).

Итак, пусть С некоторый двоичный ( n , M , d ) - код, т.е. код длины n, мощности M и с минимальным расстоянием d. Обозначим через В ( n , d ) и M ( n , d ) максимальные мощности линейного и нелинейного (или линейного ) кодов соответственно длины n с минимальным расстоянием d. Эти величины фактически определяют скорость передачи информации с помощью данного кода и его корректирующие возможности.

Код С назовём оптимальным, если он имеет максимальную мощность среди всех кодов с той же корректирующей способностью и с теми же параметрами.

В общем случае имеет место неравенство

В ( n , d )  M ( n , d )  2 ⁿ ,

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

Так, например, код с проверкой на чётность С₀ длины n имеет мощность В ( n , 2 ) = 2 ^{n - 1} и является оптимальным.

В силу того, что

M ( n , 2 t ) = M ( n - 1 , 2 t - 1 ) ,

мы в дальнейшем рассмотрим лишь коды с минимальным нечётным расстоянием d = 2 t + 1.

I. Граница сферической упаковки ( граница Хэмминга ). Если существует двоичный код длины n, исправляющий t ошибок и содержащий

M ( n , 2 t + 1) кодовых слов, то должно выполняться неравенство

_t

M ( n , 2 t + 1)  2 ⁿ /  C _nⁱ .

^{i = 0}

В самом деле, если х ₁ , х ₂ , . . . , х _{M ( n , 2 t + 1)} - все кодовые слова оптимального кода, для которых d ( x _i , x _j )  2 t + 1 , i j, то сферы радиуса t с центрами в кодовых словах не пересекаются ( сферой радиуса t с центром х _i называется множество всех слов х таких, что d ( x , х _i )  t ). Так как объём V_n ^t одной сферы равен V_n ^t = 1 + C _n¹ + . . . + C _n^t , то

M ( n , 2 t + 1) V_n ^t  2 ⁿ ,

откуда и следует граница Хэмминга:

_t

M ( n , 2 t + 1)  2 ⁿ /  C _nⁱ .

^{i = 0}

Для кодов Хэмминга имеем t = 1, следовательно,

В ( n , 3 )  2 ⁿ / ( n + 1 ).

Если же n = 2 ^r - 1, то имеет место равенство:

В ( n , 3 ) = 2 ⁿ / ( n + 1 ),

т.е. код Хэмминга длины n = 2 ^r - 1 также является оптимальным.

Код, мощность которого достигается границе Хэмминга, называется совершенным кодом или же плотно упакованным кодом.

В этом смысле код Хэмминга является совершенным кодом при n =2 ^r - 1. В общем случае для существования совершенного кода длины n, с кодовым расстоянием d = 2 t + 1 необходимо выполнение равенства

1 + C _n¹ + . . . + C _n^t = 2 ^r ,

где r - некоторое натуральное число. Так, например, при n = 23 имеем:

1 + C¹₂₃ + С²₂₃ + C³₂₃ = 2¹¹ ,

т.е. t = 3, что соответствует совершенному коду G₂₃ Голея [ 23 , 12 , 7 ], исправляющего три или менее число ошибок.

II. Граница Гильберта. Имеет место неравенство

_t

M ( n , 2 t + 1)  2 ⁿ /  C _nⁱ .

^{i = 0}

Построим код с кодовым расстоянием d = 2 t + 1. Пусть х ₁ - произвольное первое кодовое слово из GFⁿ (2). Далее к коду добавим новое слово х ₂, лежащее вне шара радиуса 2 t с центром в х ₁. На следующем шаге в качестве очередного нового кодового слова выберем х ₃, не принадлежащее шарам радиуса 2 t, описанным вокруг х ₁ и х ₂ соответственно. Процедура завершается после того, когда уже выбраны х ₁ , х ₂ , . . . , х _S слов и имеет место неравенство

S V_n^{2 t}  2 ⁿ ,

или

S  2 ⁿ / V_n^{2 t} ,

где V_n^{2 t} - объём шара радиуса 2 t. Но мощность оптимального кода не меньше мощности таким образом построенного кода, следовательно,

_t

M ( n , 2 t + 1)  2 ⁿ /  C _nⁱ ,

^{i = 0}

что и соответствует нижней границе Гильберта.

Так, например, для кода Хэмминга длины n = 2 ^r - 1, имеем

В ( n , 3 )  2 ^{n + 1} / ( n ² + n + 2 ).

III. Граница Варшамова-Гильберта. Если выполняется неравенство

1 + C _{n - 1}¹ + . . . + C _{n - 1}^{d - 2} < 2 ^r ,

то существует двоичный линейный код длины n с минимальным расстоянием по крайней мере d, имеющий не более чем r проверочных символов.

Идея получения этой границы сводится к построению проверочной матрицы H размерности ( r  n ) , любые d - 1 столбцов которой линейно независимы.

IV. Граница Плоткина. Для любого ( n , M , d ) - кода С при n < 2 d справедливо неравенство

М( n , d )  2 [ d / (2d - n) ].

Доказательство этой границы предоставляется читателю.

V. Граница Джонсона. Если M( n , d , w ) мощность оптимального равновесного кода длины n, с минимальным расстоянием d и веса w, то имеет место неравенство

М( n , 2 , w )  [ n / (w ² - wn + n)]

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

2.7.1. Доказать, что М( n , d )  t /d +1, где t - общее число единиц кода.

2.7.2. Пусть s и t число нулевых и единичных разрядов соответственно для кодов С и С +1. Доказать, что

a ) (s - n) / (n - d) + 1  M(n , d)  t / d + 1;

b ) (t - n) / (n - d) + 1  M(n , d)  s / d + 1.

2.7.3. Доказать, что _{n - 1}

а ) M(n , d)  n  C ^k_{n - 1} / d + 1;

^{k = d - 1}

_n

b ) M(n , d)  n  C ^k_{n - 1} / d + 1.

^{k = d}

2.7.4. Доказать, что код С₀ является оптимальным.

2.7.5. Упаковать все слова [ 7 , 4 , 3] - кода в пространстве GF⁷(2).

2.7.6. Определить число кодовых слов веса 3 кода H_r.

2.7.7. Определить число кодовых слов веса 4 расширенного кода H_r+1.

2.7.9. Доказать границу Варшамова - Гильберта для поля GF(q):

_{d - 2}

 (q - 1) C ⁱ_{n - 1} < q ^r .

^{i = 0}

2.7.10. При каких n и t число M ( n , 2 t + 1) есть степень двойки.

2.7.11.Оптимальны ли коды (10, 38, 4), (11, 72, 4), (12, 144, 4) ?