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