Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
aii«x+a2i«a+. ¦ -+aklah=ai,
а12<Хі+а22а2+. . .+ah2ah=a2,
ciin^i+а2паг+. . .+aknak=an.
65 Хотя задача отыскания этого решения и не содержит принципиальных трудностей, она может потребовать громоздких вычислений. Однако выделение информационных символов предельно упрощается, если использовать для кодирования так называемые систематические линейные коды.
Линейный (п, &)-код называется систематическим, если его порождающая матрица имеет вид
/1 ... О ... О Ри- ... р1я G= 0...1...Optl... ряа . (9)
или вид
,0 0 ... 1 Pki ... рк„
Zp11 ...Plm 1 о ... 0\
( P21 ... р2т 0 1 ... 0 j
\Phi ¦¦ ¦ Pkm 0 0...1/
(9')
т. е. если она получается приписыванием к единичной матрице порядка k некоторой матрицы из k строк и т=п—k столбцов (иначе говоря, матрицы порядка kxm). В случае (9) равенство (6) принимает вид:
/1 0 ... 0 р„ ... Pln
а=(а1а,...аА) 0V;-.0 7 .' ^
\0 0 ... 1 Pkl . . . Pkm
= (^0,...0 *а*+і...вп).
Таким образом, первые k символов любого кодового слова как раз и оказываются информационными, а остальные (они являются проверочными) связаны с информационными символами соотношениями:
?ft+i -Pu^1+P21а2+. . .+/Dftiaftl
o/i+ 2 = ^12^1+/^22^2+. - -+/Dftaaft, (10)
On=/?imai+P2ma2+. • -+Phm?h-
Равенства (10), очевидно, образуют систему проверочных соотношений систематического линейного кода. Очень важно, что всякий линейный код в некотором смысле эквивалентен систематическому (см. дополнение 9).
Дальнейшее прольет свет и на другие вопросы, поставленные выше.
56 Задачи и дополнения
1. Весом вектора и (обозначается и(н)) называют число его ненулевых координат. Понятно, что расстояние Хемминга между двумя векторами щ и H2 равно весу их разности w(iti—H2). Это позволяет упростить отыскание кодового расстояния линейного кода. Именно, справедливо следующее утверждение:
Кодовое расстояние линейного кода равно минимальному весу его ненулевых кодовых слов:
d (V) = min W (®).
veV
Предоставляем читателю доказать это утверждение.
2. Пусть двоичный линейный код V содержит хотя бы одно слово нечетного веса. Доказать, что число всех таких слов составляет тогда ровно половину от общего числа кодовых слов.
Указание. Убедиться, что множество всех кодовых слов четкого веса есть подпространство и найти смежные классы кода V по этому подпространству.
3. Рассмотрим матрицу порядка qhXn, в качестве строк которой взяты Ece кодовые векторы q-ичкого линейного (я, &)-кода. Будем предполагать, что ни один столбец этой матрицы не является нулевым (иначе, вычеркнув нулевой столбец, мы получили бы код с тем же кодовым расстоянием, но меньшей длины). Показать, что в каждом столбце этой матрицы каждый из ^элементов поля встречается ровно Qk-1 раз. Пользуясь этим, убедиться, что суммарный вес всех кодовых слов равен n{q—\)qk-\
Указание. Проверить, что множество всех кодовых слов, содержащих 0 в некоторой фиксированной позиции, есть подпространство, и найти разложение кода в смежные классы поэтому подпространству.
4. Предположим, что кодовый вектор с= (хі, х2, . . х„) имеет вес, равный W1 и Xht, хкъ, ..., Xk — его ненулевые координаты. Из
проверочных соотношений (1) получаем тогда:
^ik1Xkt +blk2xk2+ .. . цгЬ1І!гехкж = О,
bmkSb + bmkSki+ ¦ ¦ ¦ -НяііЛ = "..
Это означает, что столбцы проверочной матрицы с номерами кг, k2, . . . ¦ . ., kw линейно зависимы. Следовательно, каждому кодовому вектору веса W соответствует W линейно зависимых столбцов проверочной матрицы. Верно и обратное утверждение.
Отсюда вытекает, что кодовое расстояние линейного кода равно d тогда и только тогда, когда в проверочной матрице найдется d линейно зависимых столбцов, а всякая система из меньшего числа столбцов линейно независима.
5. Доказать, что двоичный линейный код исправляет любые одиночные ошибки тогда и только тогда, когда все столбцы его проверочной матрицы ненулевые и различные. Верно ли это для любого линейного кода?
6. Как изменится кодовое расстояние двоичного линейного кода при добавлении ко всем его словам одного проверочного символа, задающего общую проверку на четность?
57 7. Двоичный (8,4)-код задан порождающей матрицей
G =
(H)
Найти его проверочную матрицу и кодовое расстояние.
То же задание для троичного (6,3)-кода с порождающей матрицей
8. Два кода Vi и V2 называются эквивалентными, если кодовьіі слова одного кода получаются из кодовых слов другого некоторой перестановкой символов (одной и той же для всех кодовых слов). Поскольку при этом веса кодовых слов остаются без изменений, то кодовые расстояния двух эквивалентных кодов совпадают, поэтому одинаковы также их возможности исправлять или обнаруживать ошибки. Ясно, что если порождающие матрицы кодов получаются одна из другой путем перестановки столбцов, то коды эквивалентны.
Эквивалентными являются, например, коды Vi и V2 со следующими порождающими матрицами:
Однако связь между матрицами эквивалентных кодов может быть и более сложной. Причина заключается в том, что порождающая матрица данного кода определена неоднозначно.
