11. ЛИНЕЙНЫЕ ИЛИ ГРУППОВЫЕ КОДЫ
Большинство рассмотренных выше кодов обладало следующим свойством: сумма (и разность) двух кодовых слов также являлась кодовым словом. Для кода с повторением это свойство очевидно. Ясно оно и для кода с общей проверкой на четность, потому что сумма двух слов с четным числом единиц есть также слово с четным числом единиц.
В § 9 был рассмотрен код Хемминга с системой проверочных соотношений (5). Обобщим теперь этот пример, выбрав в качестве кодового алфавита некоторое конечное поле Р. Каждое слово х1х2. . ,хп этого алфавита будем отождествлять с вектором (хи х2, ... , хп) п-мерного пространства Ьп (в котором координаты векторов являются элементами /•). Вектор, соответствующий кодовому слову, будем называть кодовым. Систему проверочных соотношений запишем в виде системы уравнений:
с коэффициентами Ьи из Р. Код, состоящий из всех слов Х1Х2- • •хп, для которых справедливы соотношения (1), называют кодом с проверками на четность.
Для такого кода выполняется следующее свойство: если векторы (о,, а г, ... , ап) и (Ьи Ъ2 Ъп) являются кодовыми, а значит, решениями системы (1), то и их сумма (й1-г +Ъи а2+Ь2, . , . , ап+Ьп) также является решением этой системы и потому кодовым вектором. Справедливо и другое свойство решений системы (1): если а — элемент поля Р и («ь а2, ... , ап) — решение системы (1), то и вектор (ааи аа2, . . ■ , сшп) также является решением системы (1).Вместе эти свойства означают, что код с проверками на четность образует линейное подпространство в пространстве Ьп всех п-буквенных слов. По этой причине коды с проверками на четность называют линейными кодами (двоичные линейные коды называют также групповыми). Если кодовое подпространство в пространстве Ьп имеет размерность к, то употребляют для большей определенности термин линейный (я, й)-код.
Имеется очень много причин, по которым линейные коды являются важнейшими в теории кодирования. Одна из них связана с удобствами в обнаружении и исправлении ошибок, как это видно из примера, рассмотренного в § 9. Другая причина — это возможность компактного задания кода. Действительно, в случае линейного кода нет необходимости указывать полный список кодовых слов, ведь код вполне определен системой линейных уравнений (1) или матрицей этой системы (проверочной матрицей)'.
В дальнейшем мы будем предполагать, что строки этой матрицы линейно независимы.
К числу других достоинств линейных кодов, которые связаны с предыдущими, относятся простые алгоритмы кодирования и декодирования, легко реализуемые электронными переключательными схемами. Вообще, можно сказать, что бурное развитие теории кодирования, которое происходило в последние десятилетия, объясняется главным образом тем, что к линейным кодам приложим хорошо развитый аппарат линейной алгебры и теории конечных полей.
Оба отмеченных свойства проверяются непосредственной подстановкой в систему (1) векторов
Возвращаясь к рассмотренным ранее кодам, легко найдем их проверочные матрицы. Так, для кода с общей проверкой на четность имеем одно проверочное соотношение Хг+Х2+. . .0"» соответственно этому проверочная матрица состоит из одной строки и имеет вид
Наконец, проверочная матрица двоичного кода Хемминга длины 7, как это следует из соотношений (5) § 9, выглядит так:
Имеется и другой способ матричного задания линейного кода. Он основан на том, что во всяком подпространстве линейного пространства можно выбрать базис, т. е. такую ли- I нейно независимую систему векторов, через которые линейно выражаются все вообще векторы подпространства. Пусть
где коэффициенты а1 — любые элементы исходного поля.
Из проверочных соотношений для кода с повторением получаем следующую проверочную матрицу! — базисные векторы линейного кода. Тогда всевозможные кодовые векторы исчерпываются линейными комбинациями называется порождающей матрицей кода.
Таким образом, система базисных векторов (3) полностью определяет линейный (п, А')-код. Матрица О, составленная из них,Заметим, что базис можно выбрать не единственным образом, поэтому порождающая матрица О определена неоднозначно. Последнее, впрочем, верно и в отношении проверочной матрицы Н.
Легко указать порождающую матрицу кода с повторением; она имеет вид:
В качестве базисных векторов двоичного кода с общей проверкой на четность могут быть взяты, например, следующие п—I векторов:
Поэтому матрица является порождающей матрицей этого кода.
При использовании линейного кода для передачи сообщений полезно знать и порождающую, и проверочную матрицу. С помощью порождающей матрицы удобно кодировать сообщения. Поскольку линейный (п, /г)-код с порождающей матрицей (5) имеет цк кодовых слов (любой из к коэффициентов в (4) можно выбрать ц способами), он позволяет закодировать все сообщения длины к в алфавите из ц символов. Если А~аха2. . .ай — такое сообщение (аг — информационные символы), то самое удобное — сопоставить ему кодовый вектор а, совпадающий с линейной комбинацией (4) строк порождающей матрицы. Вектор а нетрудно записать в матричном виде, используя правило умножения матоиц:
О роли проверочной матрицы мы скажем в дальнейшем — она используется в основном при декодировании полученных сообщений и для исправления ошибок.
Выясним, как связаны порождающая и проверочная матрицы, и как по одной из них найти другую. Обратимся к соотношениям (1). Всякая строка порождающей матрицы, являясь кодовым вектором, удовлетворяет каждому из соотношений (1), т. е. для любых ( и /
Другими словами, любая строка порождающей и любая строка проверочной матриц ортогональны друг другу. Матричная запись равенств (7) выглядит так:
(0 означает здесь нулевую матрицу).
Заметим также, что из соотношений (1) вытекает равенство
справедливое для каждого кодового вектора г>.
Для отыскания порождающей матрицы нужно фактически найти к=п—т линейно независимых решений системы (1). Эти решения как раз и будут строками порождающей матрицы.
Пример. Пусть дана порождающая матрица двоич ного линейного кода:
Этот код содержит 24=16 кодовых слов, которыми можно закодировать все двоичные сообщения длины 4. Если, например, А=(0101), то для соответствующего кодового вектора имеем:
Пример. Найдем порождающую матрицу кода Хемминга длины 7 с проверочной матрицей (2). В данном случае требуется найти 4 независимых решения следующей которые, как читатель может убедиться, линейно независимы. Составленная из этих решений матрица и является искомой порождающей матрицей.
По поводу сказанного в этом параграфе возникает множество вопросов. Например, как, зная порождающую и проверочную матрицы, выяснить корректирующие способности данного кода; как реализовать эти способности (т. е. каким должен быть алгоритм декодирования, исправляющий или обнаруживающий ошибки); как, наконец, после исправления ошибок выделить информационные символы'
Остановимся вначале на последнем вопросе. Пусть, исправив ошибки, мы получили некоторый кодовый вектор а=(«1, а2, ... , ап). Тогда соответствующие ему информационные символы ах, а2, ... , сск определяются из равенства (6). Иными словами, вектор (а1( а2, ... , ак) есть решение (как можно показать,— единственное) системы линейных уравнений:
системы:
Разрешаем систему относительно неизвестных хи х2, хА:
Неизвестным х3, х6, хв. х7 можно придавать любые значения; тогда из равенств (8) могут быть определены оставшиеся неизвестные хи х2, хй. Придавая поочередно одному из неизвестных х3, х5, хе, х7 значение 1, а остальным — 0, получим 4 решения:
Хотя задача отыскания этого решения и не содержит принципиальных трудностей, она может потребовать громоздких вычислений. Однако выделение информационных символов предельно упрощается, если использовать для кодирования так называемые систематические линейные коды.
Линейный (п, к)-код называется систематическим, если его порождающая матрица имеет вид т. е. если она получается приписыванием к единичной матрице порядка к некоторой матрицы из к строк и т=п—к столбцов (иначе говоря, матрицы порядка кХт). В случае (9) равенство (6) принимает вид:
Равенства (10), очевидно, образуют систему проверочных соотношений систематического линейного кода. Очень важно, что всякий линейный код в некотором смысле эквивалентен систематическому (см. дополнение 9).
Таким образом, первые к символов любого кодового слова как раз и оказываются информационными, а остальные (они являются проверочными) связаны с информационными символами соотношениями:
Дальнейшее прольет свет и на другие вопросы, поставленные выше.
Задачи и дополнения
I. Весом вектора и (обозначается и(«)) называют число его ненулевых координат. Понятно, что расстояние Хемминга между двумя векторами щ и и2 равно весу их разности
позволяет упростить отыскание кодового расстояния линейного кода. Именно, справедливо следующее утверждение:
Кодовое расстояние линейного кода равно минимальному весу его ненулевых кодовых слов:
Предоставляем читателю доказать это утверждение.
Пусть двоичный линейный код V содержит хотя бы одно слово нечетного веса. Доказать, что число всех таких слов составляет тогда ровно половину от общего числа кодовых слов.
Указание. Убедиться, что множество всех кодовых слов четного веса есть подпространство и найти смежные классы кода V по этому подпространству.
Рассмотрим матрицу порядка дкХп, в качестве строк которой взяты все кодовые векторы <?-ичного линейного (п, /г)-кода. Будем предполагать, что ни один столбец этой матрицы не является нулевым (иначе, вычеркнув нулевой столбец, мы получили бы код с тем же кодовым расстоянием, но меньшей длины). Показать, что в каждом столбце этой матрицы каждый из ^элементов поля встречается ровно раз. Пользуясь этим, убедиться, что суммарный вес всех кодовых слов ра-
Это означает, что столбцы проверочной матрицы с номерами к2, . .. . . ., Ащ; линейно зависимы. Следовательно, каждому кодовому вектору веса и) соответствует ю линейно зависимых столбцов проверочной матрицы. Верно и обратное утверждение.
Отсюда вытекает, что кодовое расстояние линейного кода равно й тогда и только тогда, когда в проверочной матрице найдется й линейно зависимых столбцов, а всякая система из меньшего числа столбцов линейно независима.
Доказать, что двоичный линейный код исправляет любые одиночные ошибки тогда и только тогда, когда все столбцы его проверочной матрицы ненулевые и различные. Верно ли это для любого линейного кода'
Как изменится кодовое расстояние двоичного линейного кода при добавлении ко всем его словам одного проверочного символа, задающего общую проверку на четность?Найти его проверочную матрицу и кодовое расстояние.
То же задание для троичного (6,3)-кода с порождающей матрицей далее, вычитая из первой строки вторую, приходим к матрице
Получающиеся при этих преобразованиях матрицы также порождают
Эквивалентными являются, например, коды У* и У2 со следующими порождающими матрицами:
и
Однако связь между матрицами эквивалентных кодов может быть и более сложной. Причина заключается в том, что порождающая матрица данного кода определена неоднозначно.
9. В предыдущем примере код эквивалентен систематическому коду У2. Это не исключение, а правило, поскольку справедливо следующее утверждение:
Всякий линейный код эквивалентен систематическому коду.
Доказательство, которое рекомендуется продумать читателю, основывается, в сущности, на известном современному школьнику методе Гаусса исключения неизвестных.
Последовательность действий, приводящих произвольный код к систематическому, продемонстрируем на примере матрицы (11) (задача 7).
7. Двоичный (8,4)-код задан порождающей матрицей
Вычитая из четвертой строки матрицы (11) первую, получим:исходный код. Осуществим теперь перестановку столбцов, чтобы слева получить единичную матрицу — пятый столбец поставим на место второго, восьмой — на место третьего, седьмой — на место четвертого столбца. В итоге получим порождающую матрицу систематического кода
И. Пусть V — произвольный линеинын (п, к)-код. Рассмотрим множество V' всех векторов пространства ортогональных каждому из кодовых векторов »^ К. Нетрудно проверить, что V' является подпространством в и, следовательно, может рассматриваться как линейный код. Код V' называется дуальным к исходному коду V.
Убедиться, что если О и Н — порождающая и проверочная матрицы кода V, то они служат соответственно проверочной и порождающей матрицей дуального кода V".
Простейший пример кодов, дуальных друг к другу,— это код с повторением и код с общей проверкой на четность,
12. Одним из способов получения кодов, обладающих большим кодовым расстоянием, а значит, и высокой корректирующей способностью, является комбинирование двух или нескольких кодов. Примером такого комбинирования является рассматриваемая здесь конструкция. Она дает код, который является обобщением матричного кода из § 8 с проверками на четность по строкам и столбцам.
Пусть дано слово, содержащее к=к^к2 информационных символов. Разобьем множество этих символов на к2 блоков по /г1 символов в каждом и запишем результат в виде квадратной матрицы порядка к2У.ку.
В первой строке этой матрицы выписаны по порядку символы первого блока, во второй — символы второго и т. д.
Рассмотрим теперь произвольный систематический линейный код Vх длины гц с к± информационными символами и с тем же самым кодовым алфавитом. Строки матрицы (12) закодируем указанным кодом — для этого к каждой строке припишем пх—проверочных символов таким образом, чтобы выполнялись проверочные соотношения кода VI.
10. Показать, используя соотношения (7), что для систематического кода с порождающей матрицей (9) в качестве проверочной можно взять следующую матрицу:
Далее каждый столбец получившейся матрицы порядка к2У. п1.
закодируем точно таким же способом с помощью линейного (п2, к2У кода У2-
В результате получим матрицу порядка п^Хп^:
Выписывая элементы этой матрицы «по строкам», мы и составим кодовое слово, отвечающее исходному слову. Оно, очевидно, однозначно определяется матрицей (12).
Построенный код называется произведением кодов V^ и У2 и обозначается У^®У2.
Пусть теперь к, к^, к2— числа информационных символов кодов и а п, п 1, п2— длины этих кодов. Из построения кода УлбОУ» сразу же вытекает, что
и
Менее очевидно аналогичное соотношение между кодовыми расстояниями й, й2 тех же кодов: -с^. Доказательство этого факта предоставляем читателю.
Предлагаем читателю также выяснить, какова связь между количеством ошибок, исправляемых кодами Уй У2 и У1®У2.
соответствует следующее кодовое слово кода
Проиллюстрируем сказанное примером. Пусть к= 8, к^—4, к%=2. В качестве кода Ух возьмем (7,4)-код Хемминга, записав предварительна его порождающую матрицу в систематической форме:
в качестве У2— (3,2)-код с общей проверкой на четность. Составим кодовое слово кода У1@У2, соответствующее исходному слову 00101110 с восемью информационными символами. Запишем его в виде матрицы порядка 2X4:
В результате кодирования строк (7,4)-кодом Хемминга (см. правило (6)) получим матрицу порядка 2X7:
Кодирование столбцов этой матрицы сводится к добавлению в каждом столбце символа общей проверки на четность. Получившейся в итоге матрице порядка 3X7