Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.1.2. Исследование кодового расстояния

Для каждого фиксированного кодового слова уравнение (2.2) означает, что сумма некоторого подмножества столбцов матрицы равна 0. Например, последовательность ( является кодовым словом -кода из предыдущего примера. При матричном умножении согласно (2.2) ненулевые элементы этой последовательности «отсеивают» первый, четвертый и шестой столбцы Н, т. е.

Поскольку аналогичное соотношение должно выполняться для любого кодового слова, можно заметить следующее. Если минимальный вес, т. е. кодовое расстояние кода, равно то должно существовать по крайней мере одно подмножество, состоящее из столбцов матрицы Н, сумма которых равна 0. С другой стороны, не может существовать ни одного подмножества из или менее столбцов, сумма которых равна 0. Если рассматривать столбцы матрицы Н как векторы, то можно сказать, что для кода с кодовым расстоянием все подмножества из столбцов Н должны быть линейно независимы. Это утверждение составляет одну из фундаментальных теорем о групповых кодах. Оно позволяет находить кодовое расстояние группового кода, заданного матрицей Н, а также строить матрицы Н, приводящие к кодам с гарантированным кодовым расстоянием. Вновь рассматривая в качестве примера -код, видим, что все столбцы различны, так что сумма двух столбцов никогда не равна 0. С другой стороны, существует по крайней мере одно множество из трех столбцов, например, состоящее из столбцов 1, 2 и 5, сумма которых равна 0. Таким образом, кодовое расстояние этого кода равно 3.

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

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

позволяющее добавить к матрице Н еще один столбец.

<< Предыдущий параграф Следующий параграф >>
Оглавление