Примеры кодирования.

Простое кодирование с повторением.

При любом n ∈ N множество M = {0,1} можно кодировать следующим образом:

0 →0. . . 0 (n ),

1 →1. . . 1 (n ).

Декодировать принятое слово длины n можно по ”принципу большинства”: если в нем больше половины нулей, то оно декодируется как 0, в противном случае — как 1. Такое кодирование имеет большую надежность (d^∗ = n и, значит, код исправляет [(n−1)/2] ошибок), но малую скорость передачи информации (R =1/n). Кодирование из примера, состоящее в утроении каждого символа слова, есть видоизмененная форма этого кодирования, также использующее идею повторения.

Простое кодирование с проверкой на четность

Пусть k — любое натуральное число и M — множество всех слов длины k в алфавите {0,1}. Произведем кодирование этого множества, добавляя к каждому слову (a₁, ..., a_k) длины k еще один символ a_k+1 следующим образом: полагаем a_k+1 = 0, если a₁ + ... + a_k четно, и a_k+1 = 1,

если a₁ + ... + a_k нечетно. Другими словами, a_k+1 выбирается так, чтобы a₁ + ... + a_k+1 было всегда четно. Скорость R передачи информации при таком кодировании велика: R =k/k+1. Но разреженность d^∗ = 2. Следовательно, код не может исправить ни одной ошибки.

- 6 -

Он может только обнаружить одну ошибку, и именно для этой цели он и используется, при условии, однако, что частота ошибок мала. Декодер работает так: если в принятом слове x = (a₁, ..., a_k+1) сумма координат четная, то он считает, что переданное слово есть (a₁, ..., a_k+1) (и, следовательно, информационное слово есть (a₁, ..., a_k), в противном случае он отказывается от декодирования. Важно, что при таком декодировании декодер не обращается к памяти. Это кодирование используется в бухгалтерских расчётах.

Прямоугольные коды.

В случае, когда число k информационных символов представляется в виде произведения k =st, известна конструкция кодов, называемых прямоугольными кодами. Обычно, это — коды над алфавитом {0,1}. Рассмотрим случай, когда s = 2 и t = 3. К шести информационным символам

i₁, ..., i₆ добавим пять проверочных p₁, ..., p₅, которые строятся по следующему ”правилу прямоугольника”:

i1 i2 i3 i4 i5 i6	p1= i1+ i2+ i3 p2= i4+ i5+ i6
p3= i1+ i4 p4= i2+ i5 p5= i3+ i6

(p₁, p₂ — проверки по строкам, p₃, p₄, p₅ — проверки по столбцам.) Таким образом, построен ”прямоугольный” код K = {(i₁, ..., i₆, p₁, ..., p₅) | i₁, ..., i₆ ∈ {0,1}, p_i — как в таблице}.

(Иногда добавляют еще один проверочный символ p₆ = i₁ + ... + i₆.)

Кодирование с помощью этого кода выглядит так:

(i₁, ..., i₆) → (i₁, ..., i₆, p₁, ..., p₅).

Линейный код и его порождающая матрица.

Определение 1. Линейным (n, k)-кодом над полем F_q называется подпространство размерности k векторного пространства V (n, F_q). Линейный код—это линейный (n, k)-код над F_q при некоторых n, k, q. Число R =k/n называется скоростью кода.

Линейный (n, k)-код состоит из q^k векторов, а в V (n, F_q) всего qⁿ векторов. На практике значения k находятся обычно между 3 и несколькими сотнями, а типичные значения R — между 1/4 и 7/8.

Определение 2. Пусть K — линейный (n, k)-код над F_q и {g₁, . . . , g_k} — его базис. Тогда k × n-матрица

g₁

.

G=.

g_k

- 7 -

составленная из координат векторов g₁, . . . , g_k , называется порождающей матрицей кода K. Порождающая матрица кода K = {0} (который не имеет базиса) не определена.

Определение 3. Пусть K — линейный (n, k)-код и π ∈ S_n (т. е. π — любая перестановка чисел 1, . . . , n). Если каждый вектор v = (v₁, . . . , v_n) кода K заменить вектором v_π =(v_π(1), . . . , v_π(n)) (т. е. осуществить перестановку координат вектора v в соответствии с перестановкой π), то множество K_π = {v_π | v ∈ K} снова будет кодом. Для любого π ∈ S_n код K_π называется эквивалентным коду K.

Очевидно, код K_π имеет те же параметры n,k,q,d^∗, R, что и K, а порождающая матрица кода K_π получается из порождающей матрицы кода K той же перестановкой столбцов π. Подобно тому, как в теории групп, группы рассматриваются с точностью до изоморфизма, в теории кодирования

коды обычно изучаются с точностью до эквивалентности.

Теорема 1.Для любого линейного (n, k)-кода K существует эквивалентный ему код с порождающей матрицей вида

G = (I_k | P),

где I_k — единичная матрица степени k, а P — некоторая матрица размера

k × (n − k).

Доказательство. Любая порождающая матрица G₁ кода K состоит из k линейно независимых строк. Но, как известно из линейной алгебры, такую матрицу можно привести к виду (I_k | P) элементарными преобразованиями строк и перестановкой столбцов. Но элементарные преобразования

строк переводят G₁ снова в порождающую матрицу G₂ кода K (так как они не изменяют ранга матрицы), а перестановка столбцов в G₂ переводит ее в порождающую матрицу эквивалентного к K кода.

Порождающую матрицу вида G = (I_k | P) называют порождающей матрицей в систематическом виде. Название оправдывается тем, что кодирование пространства V (k, F_q) с помощью матрицы G = (I_k | P) будет систематическим.