Проверочная матрица линейного кода.

Напомним, что векторы a = (a₁, . . . , a_n) и b = (b₁, . . . , b_n) пространства V (n, F_q) называются ортогональными (запись: a ⊥ b), если ab = 0. (ab = a₁b₁ + . . . + a_nb_n называется скалярным произведением векторов a и b.) Очевидно, если

a ⊥ b и a ⊥ c, то a ⊥ f₁b + f₂c для любых f₁, f₂ ∈ F_q.

Определение 1. Пусть K—линейный (n, k)-код над F_q. Тогда ортогональное дополнение K^⊥ этого подпространства в V (n, F_q) является подпространством в V (n, F_q) и называется кодом, двойственным (или дуальным) коду K.

Определение 2.Пусть K — линейный (n, k)-код над F_q. Порождающая матрица двойственного кода K^⊥ называется проверочной матрицей кода K.

- 8 -

Проверочная матрица для (n, n)-кода K = V (n, F_q) не определена (так как не определена порождающая матрица кода K^⊥ = {0}).

Теорема 1. Пусть K — линейный (n, k)-код над F_q с порождающей матрицей в систематическом виде:

G = (I_k | P).

Тогда одна из проверочных матриц кода K имеет вид:

H = (−P | I_n−k).

Доказательство.

HG = (−P | I_n−k)(I_k/P)= −P + P = O

Следовательно, строки матрицы H ортогональны строкам матрицы G и, значит, лежат в K^⊥. Но так как dim(K^⊥) = n−k(Для любой матрицы над произвольным полем F ее ранг по строкам, ранг по столбцам и ранг по минорам совпадают. Это число называется рангом матрицы)и, так как матрица H имеет n−k линейно независимых строк (из-за наличия в H клетки I_n−k), то они образуют базис в K^⊥, а это означает по определению 2, что матрица H — это проверочная матрица кода K.

Проверочную матрицу вида H = (A | I_n−k) называют проверочной матрицей в систематическом виде.

Замечание 1. Произвольный элемент v кода K может быть записан в виде v = f₁G₁· +f₂G₂· +f₃G₃·, где fi ∈ F2, т. е. в виде v = (f1, f2 + f3, f1 + f2 + f1, f2, f1 + f3). О такой записи говорят, что это запись элемента кода в общем виде или, что это есть общий вектор кода K.

Замечание 2. Отметим, что если проверочная матрица линейного кода имеет систематический вид, то по ней легко можно записать общий вектор кода. Например, если взять вектор v =(i₁, i₂, i₃, p₁, p₂) кода K, то по (группа всех перестановок множества M = {1,2, ..., n} называется

симметрической группой степени n и обозначается через S_n.) Hv = O, откуда получаем p₁ =i₁ + i₃, p₂ = i₁ + i₂ + i₃, т. е. общий вектор кода K есть v = (i₁, i₂, i₃, i₁ + i₃, p₂ = i₁ + i₂ + i₃).

Декодирование линейных кодов.

K v2+K v3+K . . . vj+K	0 v2 v3 . . . vj	c2 v2+c2 v3+ c2 . . . vj+c2	c3 v2+ c3 v3+ c3 . . . vj+ c3	… … … . . . …	cgk v2+ cgk v3+ cgk . . . vj+ cgk	w(ui)≤t (t=[(d*-1)/2]
vj+1+K . . . vl+K	vj+1 . . . vl	vj+1+c2 . . . vl+c2	vj+1+ c3 . . . vl+ c3	… . . . …	vj+1+ cgk . . . vl+ cgk	w(ui)>t

- 9 -

Теорема 1. В стандартной таблице декодирования линейного (n, k)-кода K в каждом столбце до черты записаны шары радиуса t с центрами в кодовых словах. А именно, {0, v₂, . . . , v_j} = B_t(0) (шар радиуса t с центром в нуле) и B_t(0) + c_i = B_t(c_j) ∀i. (B_t(c_i) называется шаром декодирования для c_i).

Доказательство. Пусть K = {c₁, c₂, . . . , c_q^k} — линейный (n, k)-код над F_q со стандартной таблицей декодирования , которую мы обозначим через T. Очевидно, что A₁ := {v₁, v₂, . . . , v_j} ⊆ B_t(0) и A_i:= {c_i, v₂ +c_i, . . . , v_j + c_i} ⊆ B_t(c_i) (так как d(c_i, v_m + c_i) = d(0, v_m) ≤ t при m ≤ i). Так как d^∗ ≥ 2t + 1, то код K исправляет t ошибок, т. е. шары радиуса t с центрами в кодовых словах

попарно не пересекаются. В частности, A₁ ∩ A_i =ø ∀_i ≠1. Следовательно, все слова из B_t(0), не вошедшие в A₁, должны быть под чертой в T. Но v_j+1 — слово наименьшего веса из всех слов, находящихся под чертой, и w(v_j+1) > t. Таким образом, A₁ = B_t(0). Теперь∀_i A_i = A₁ + c_i = B_t(0) + c_i = B_t(c_i), так как

v_m + c_i ∈ B_t(c_i) ⇐⇒ d(v_m + c_i, c_i) ≤ t ⇐⇒ d(v_m,0) ≤ t ⇐⇒ v_m ∈ B_t(0).

Определение 1.Пусть K—линейный (n, k)-код над F_q с проверочной матрицей H и v ∈ V (n, F_q). Синдромом вектора v (относительно H) называется вектор s(v) = vH (длины n − k).

Теорема 2. Пусть K — линейный (n, k)-код в пространстве V = V (n, F_q) и H — его проверочная матрица. Два вектора пространства V = V (n, F_q) имеют один и тот же синдром относительно H ⇐⇒ они лежат в одном смежном классе по K.

Доказательство. Для любых x, y ∈ V имеем:

s(x) = s(y) ⇐⇒ xH = yH ⇐⇒ (x − y)H = 0 () ⇐⇒

H(x − y) = 0 () ⇐⇒ (x − y) ∈ K ⇐⇒

x ∈ y + K ⇐⇒ x + K = y + K.

Определение 2. Ненулевой линейный код K в пространстве V (n, F_q) называется совершенным, если шары некоторого радиуса r с центрами в кодовых словах попарно не пересекаются и покрывают все пространство V (n, F_q).

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