5.2. Веса кодовых слов в коде Хэмминга

В этом разделе выводятся формулы для числа векторов всех весов в двоичном и недвоичном кодах Хэмминга. Эти формулы полезны при вычислении вероятности необнаружения ошибки в тех случаях, когда код используется только для обнаружения ошибок. Веса для кода Хэмминга, образованного словами длины над полем из элементов, находятся при помощи соответствия между

соотношениями линейной зависимости столбцов проверочной матрицы И и кодовыми векторами веса w (теорема 3.1). Число кодовых векторов веса у обозначается через

Любой вектор из символов кратен некоторому столбцу матрицы , и, следовательно, прибавляя кратное некоторого столбца матрицы любую ненулевую линейную комбинацию из векторов можно превратить в линейную комбинацию, равную 0. Новая линейная комбинация будет иметь обычно слагаемых, однако может случиться так, что вновь прибавленное слагаемое взаимно уничтожится с одним из старых слагаемых. Это произойдет тогда и только тогда, когда первоначальная линейная комбинация из векторов состояла из равной нулю линейной комбинации из у — 2 векторов и одного дополнительного слагаемого. Кроме того, возможно (но не в случае двоичного кода), что вновь прибавленное слагаемое окажется подобным одному из слагаемых и приведется, но не взаимно уничтожится с ним. Это случится тогда и только тогда, когда первоначальная линейная комбинация из векторов состояла из равной нулю линейной комбинации из векторов и дополнительного слагаемого, которое приводится, но не взаимно уничтожается с одним из слагаемых, входящих в линейную комбинацию, равную нулю.

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

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

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

минимальный вес равен 3, то На основании этих результатов и соотношения (5.1) можно вычислить затем

Имеется также явное решение. Пусть

тогда если змножить соотношение (5,1) на и просуммировать по от до учитывая, что , то получим следующее дифференциальное уравнение:

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

Число кодовых векторов веса можно найти как коэффициент этого многочлена, стоящий при Для случая двоичного кода

Для двоичного кода, исправляющего все одиночные ошибки и обнаруживающего все двойные ошибки, веса векторов легко найти, если вспомнить, что этот код был получен добавлением к каждому вектору нечетного веса символа 1, а к каждому вектору четного веса символа 0. Таким образом, число векторов веса равно 0, если нечетно, и равно если у четно. Нечетные и четные слагаемые можно отделить друг от друга, используя для четных слагаемых и для нечетных слагаемых. Тогда производящей функцией для кода с расстоянием, равным 4, является функция

Подставляя сюда из соотношения (5.5) и увеличивая на 1 из-за дополнительного проверочного соотношения, находим

Наконец, интересно заметить, что вероятность необнаружения ошибки находится как

для кода с расстоянием, равным 3, и задается для кода с расстоянием, равным 4, тем же выражением с заменой на

Пример. Пусть задан двоичный код Хэмминга длины испрат вляющий одну ошибку. Тогда

Следовательно, этот код содержит одно кодовое слово веса 0, семь слов веса 3, семь слов веса 4 и одно слово веса 7. Для кода с расстоянием, равным 4, получаемого добавлением к коду, исправляющему одну ошибку, проверочного соотношения, задаваемого суммой всех символов, и

Поэтому этот код состоит из одного кодового слова веса 0, четырнадцати слов веса 4 и одного слова веса 8.