Вопрос 4. Линейные коды

Линейные коды ^[1] образуют некоторый подкласс в классе всех кодов. Почти все известные блоковые и древовидные коды являются ко­дами этого типа.

Можно построить линейные коды, символы которых являются элементами произвольного множества, однако почти все основные результаты в теории кодирования получены в предполо­жении, что символы кода являются элементами конечного поля, в частности при q = 2.

Для двоичных линейных кодов общепринято название групповой код. Кроме того, линейные блоковые коды иногда называют групповыми алфавитами.

Совокупность всех наборов элементов (векторов) длины п образует векторное пространство V. Задано оно может быть квадратной матрицей W_{n x n}, строками которой являются n базисных (линейно-независимых) векторов w₁ - w_n, например:

Все векторное пространство является линейной комбинацией этих базисных векторов

(4.1)

 Коэффициенты a_i в выражении (4.1) принадлежат полю F_q.

 

Некоторое множество векторов длины n называется линейным блоковым кодом тогда и только тогда, когда, оно является подпространством V’ векторного пространства V всех набо­ров длины п.

Линейные коды могут быть заданы матрицами. Матрица G_{k x n}, k ≤ n для задания кода может содержать некоторые строки матрицы W. Если k = n, то код будет представлять собой все пространство V и кодовое расстояние его будет d = 1.

Пример:

Любое множество базисных векторов линейного кода V’ рассматриваемое как строки матрицы G, называемой порождаю­щей матрицей кода V’.

Пространство строк (совокупность всех линейных комбинаций вектор–строк матрицы) матрицы G является линейным кодом V’, и вектор является кодовым вектором тогда и только тогда, когда он является линейной комбинацией строк матрицы G.

Если размерность векторного пространства V’ равна k, то число строк матрицы G (которое равно рангу G, потому что строки матрицы должны быть линейно независимыми) равно k (это будет количество информационных разрядов).

Различные линейные комбинации дают различные кодовые векторы, и так как имеется k коэффи­циентов с q (при q=2 это 0 и 1) возможными значениями для каждого, то простран­ство V содержит всего q^k кодовых векторов.

Такой код называется (п, k)-кодом.

Нулевое пространство V” пространства V’ – совокупность всех наборов длины n, ортогональных подпространству V’, образующее подпространство V”. Ортогональность подпространству означает ортогональность всем его векторам, т.е. скалярное произведение со всеми векторами равно нулю.

Если V’ есть подпространство размерности k, то его нулевое пространство является векторным пространством V” размерности n – k и его порождающей матрицей H_n-k,n является совокупность строк матрицы W, не вошедших в матрицу G:

Следует помнить, что V’ +V” ≠ V, а имеет место V’ +V” Ì V.

Кроме того, существует подпространство Δ = V – (V’ +V”). В него входят вектора, не принадлежащие подпространствам V’ и V”, но и не ортогональные им.

Пример:

, , , тогда вектор (1, 1) не принадлежит ни одному из них, но и не ортогонален ни одному из них.

Если V” есть нулевое пространство для V’, и вектор v’ принадлежит V’ то он ортогонален каждой строке матрицы H (а значит и всем векторам пространства V”), т. е.

.                                             (4.2)

Матрица Н назы­вается проверочной матрицей кода V’, т.е. проверить принадлежность вектора v’ пространству V’ можно по (4.2).

Соотношения (4.2) справедливы для любого вектора v’ из про­странства V’. В частности, они справедливы для k базисных век­торов матрицы G. Эти k уравнений можно записать как

,                                             (4.3)

где 0 обозначает нулевую матрицу размерности k x (п — k).

Код V’ обладает избыточностью и может быть использован для помехоустойчивой передачи информации.

Сообщение I _{1 x k} = (i₁, i₂, …, i_k) преобразуется в помехоустойчивое сообщение
C = v’ Î V’ следующим образом:

.                                   (4.4)

На приемной стороне безошибочность принятого вектора C проверяется по (4.2):

.

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

Если ошибки нет, то обратным преобразованием

 ,                    (4.5)

где                                                                       

получают передаваемое сообщение I _{1 x k}.

 

В.КНЯЗЕВ

[1] Речь идет просто о кодах, а можно ли их использовать в качестве помехоустойчивых – это уже другой вопрос.