Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
\1 О О ... -1/
Наконец, проверочная матрица двоичного кода Хемминга длины 7, как это следует из соотношений (5) § 9, выглядит так:
/О о о і і і к # = ( 0 110 0 11. (2)
\1 0 1 0 1 О 1/
Имеется и другой способ матричного задания линейного кода. Он основан на том, что во всяком подпространстве линейного пространства можно выбрать базис, т. е. такую линейно независимую систему векторов, через которые линейно выражаются все вообще векторы подпространства. Пусть
«і=(aii, d12, . . . , а1п),
а2=(а21, а22, . . . , а2п), (3)
®k — (akl> aM, • ¦ . , fljm)
— базисные векторы линейного кода. Тогда всевозможные кодовые векторы исчерпываются линейными комбинациями
«,«t+ssfli-f. . .+ocftoft, (4)
где коэффициенты CL1 — любые элементы исходного поля.
Таким образом, система базисных векторов (3) полностью определяет линейный (п, &)-код. Матрица 0, составленная из них,
faW Cia ••• Glr \
O=Ia:1, у. ), (5)
Vfcl ац2 ¦¦ ¦ akn / называется порождающей матрицей кода. Заметим, что базис можно выбрать не единственным образом, поэтому порождающая матрица G определена неоднозначно. Последнее, впрочем, верно и в отношении проверочной матрицы Я.
Легко указать порождающую матрицу кода с повторением; она имеет вид:
В качестве базисных векторов двоичного кода с общей проверкой на четность могут быть взяты, например, следующие п—1 векторов:
является порождающей матрицей этого кода.
При использовании линейного кода для передачи сообщений полезно знать и порождающую, и проверочную матрицу. С помощью порождающей матрицы удобно кодировать сообщения. Поскольку линейный (п, к)-код с порождающей матрицей (5) имеет qk кодовых слов (любой из k коэффициентов в (4) можно выбрать q способами), он позволяет закодировать все сообщения длины k в алфавите из q символов. Если /4=0^2. . .aft — такое сообщение (а; — информационные символы), то самое удобное — сопоставить ему кодовый вектор а, совпадающий с линейной комбинацией (4) строк порождающей матрицы. Вектор а нетрудно записать в матричном виде, используя правило умножения матриц:
G=(l 1 1. . .1).
a, = (1 1 0 0 ... 0), a2 = (l 0 1 0 ... 0), а, = (1 0 0 1 ... 0),
а„_г = ( 1 0 0 0... 1).
Поэтому матрица
а—А ¦ G=(CC1)X3,. .as)
(6)
?hi aSs akn/
53 Пример. Пусть дана порождающая матрица двоичного линейного кода:
/1 1 1 0 0 0 0\ г_ 10 0 1 1 О О I
° — \ 0 10 10 10 г \1 1 0 1 0 0 1/
Этот код содержит 24=16 кодовых слов, которыми можно закодировать все двоичные сообщения длины 4. Если, например, /4 = (0101), то для соответствующего кодового вектора имеем:
/1 1 1 0 о 0 0\
«-(»¦ol) =(0100101).
Vl 10 10 0 1/
О роли проверочной матрицы мы скажем в дальнейшем —¦ она используется в основном при декодировании полученных сообщений и для исправления ошибок.
Выясним, как связаны порождающая и проверочная матрэицы, и как по одной из них найти другую. Обратимся к соотношениям (1). Всякая строка порождающей матрицы, являясь кодовым вектором, удовлетворяет каждому из соотношений (1), т. е. для любых і и /
bndji+biidji+. . .+binajn=0. (7)
Другими словами, любая строка порождающей и любая строка проверочной матриц ортогональны друг другу. Матричная запись равенств (7) выглядит так:
C-Ht=0
(0 означает здесь нулевую матрицу).
Заметим также, что из соотношений (1) вытекает равенство
VHT=0,
справедливое для каждого кодового вектора v.
Для отыскания порождающей матрицы нужно фактически найти k=n—т линейно независимых решений системы (I). Эти решения как раз и будут строками порождающей матрицы.
Пример. Найдем порождающую матрицу кода Хемминга длины 7 с проверочной матрицей (2). В данном случае требуется найти 4 независимых решения следующей
64 системы:
X2 + X3 + X11+X^ = O,
Xi +X3 +X5 +X7 = O-Разрешаем систему относительно неизвестных хі, х^, Xi:
Xj =X3+Х5+X7,
X2=X3 + Xe+.х7, (8)
Xi Х5 I Xe I X7 *
Неизвестным X3, X8, х„, х7 можно придавать любые значения; тогда из равенств (8) могут быть определены оставшиеся неизвестные хі, хі, х4. Придавая поочередно одному из неизвестных Xs, х5, х„, х7 значение 1, а остальным — 0, получим 4 решения:
«,=(1110000), «,=(1001100), «,=(0101010), «4=(1101001),
которые, как читатель может убедиться, линейно независимы. Составленная из этих решений матрица
/1 1 1 0 0 0 0\ ( 10 0 1 1 о о\ I 0 1 0 1 0 1 о I \1 10 10 0 1/
и является искомой порождающей матрицей.
По поводу сказанного в этом параграфе возникает множество вопросов. Например, как, зная порождающую и проверочную матрицы, выяснить корректирующие способности данного кода; как реализовать эти способности (т. е. каким должен быть алгоритм декодирования, исправляющий или обнаруживающий ошибки); как, наконец, после исправления ошибок выделить информационные символы?
Остановимся вначале на последнем вопросе. Пусть, исправив ошибки, мы получили некоторый кодовый вектор а=(аї, а2, ... , ап). Тогда соответствующие ему информационные символы «і, а2, , , . , ah определяются из равенства (6). Иными словами, вектор (о^, а2, . . . , ah) есть решение (как можно показать,— единственное) системы линейных уравнений:
