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

3. Матрица кода (n,m,d) и ее контрольная подматрица

Пусть комбинации кода (VI.1.5) отличаются одна от другой не менее чем в d позициях. Зачеркнем в (VI.1.5) d—1 произвольных столбцов, тогда в оставшейся подматрице строки будут отличаться по крайней мере в одной позиции и, следовательно, в системе линейных форм, образующих код любые содержат по крайней мере одну подсистему линейно независимых форм (см. лемму (VI.1)).

Нетрудно видеть, что справедливо обратное утверждение: если любых линейных форм системы (VI.2.1) содержат по крайней мере одну подсистему линейно независимых форм, то комбинации кода отличаются не менее чем в позициях.

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

Вопрос о зависимости или независимости линейных форм однозначно решается с помощью матрицы коэффициентов. Для линейных форм системы (VI.2.1) такая матрица порядка имеет вид

(VI.3.1)

где — коэффициент при независимой переменной- в линейной форме .

В дальнейшем (VI.3.1) будем называть матрицей кода а ее подматрицу, составленную из k по следних строк, — контрольной подматрицей кода

Матрица кода (VI.1.6) и ее контрольная подматрица имеют вид

(VI.3.2)

В свою очередь, матрица кода (VI.1.7) и ее контрольная подматрица запишутся так:

(VI.3.3)

По доказанному ранее любых линейных форм системы (VI.2.1) содержат по крайней мере одну подсистему линейно независимых форм. Поэтому в матрице кода (VI.3.1) ранг любой подматрицы порядка должен быть равен . Учитывая сказанное, теорему VI.1 можно перефразировать так:

Теорема VI.2. Для того чтобы матрица порядка представляла матрицу кода , необходимо и достаточно, чтобы в ней любая подматрица имела бы ранг .

Следствие 1 (Теоремы VI.2). Кодовое расстояние d инвариантно относительно элементарных преобразований столбцов матрицы кода (VI.3.1), а также умножения ее строк на отличный от нуля элемент поля и их транспозиции (перестановки).

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

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

Основная практическая трудность выбора матрицы (VI.3.1), удовлетворяющей условиям теоремы VI.2, заключается в выборе k последних ее строк матрицы (первые ее строк образуют единичную матрицу порядка ).

Выделим из (VI.3.1) подматрицу порядка , где попрежнему . Пусть ее строк совпадают с какими-либо из первых строк (VI.3.1), а с какими-либо из k последних строк (VI.3.1). После перестановки строк и столбцов выбранная подматрица запишется так:

(VI.3.4)

С помощью элементарных преобразований строк (VI.3.4) легко получить матрицу

(VI.3.5)

где в первых строках все последних элементов равны нулю, а в последних строках все первых элементов равны нулю.

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

Теорема VI.3. Для образования k линейных форм, определяющих k проверочных символов кода необходимо и достаточно, чтобы в матрице порядка любая подматрица порядка имела бы ранг .

Следствие 1 (Теоремы VI.3). Для того чтобы комбинации кода отличались не менее чем d в позициях, необходимо (но не достаточно), чтобы среди линейных форм существовало по крайней мере таких, которые зависели бы от переменной (для всех ) а число проверочных символов удовлетворяло условию

(VI.3.6)

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

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

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