Проверочная матрица. Порождающие матрицы блочных кодов

Введение

Описание процесса цифровой связи

Источник выдает сообщение, представляющее в общем случае некоторый электрический сигнал. Этот сигнал преобразуется в цифровую форму, которая является удобной для дальнейшей обработки.

Далее производится сжатие информации (кодирование источника), минимизирующее избыточность сообщения. Кодирование источника снижает затраты на передачу и хранение информации. После этого сообщение должно быть передано по зашумленному каналу. Для того чтобы сообщение дошло до потребителя в неискаженном виде, используется помехоустойчивое кодирование информации (кодирование канала). На стороне потребителя информация декодируется. Декодер канала исправляет ошибки в принятом слове, а декодер источника преобразует исправленное слово в форму, удобную потребителю.

Говоря о кодах, контролирующих ошибки, следует различать две стратегии их использования.

1. Непосредственное исправление ошибок за счет избыточности (Forward Error Correction — FEC).
2. Обнаружение ошибок с последующими запросами на повторную передачу ошибочно принятой информации (Automatic Repeat Request — ARQ).

При выборе методов кодирования и декодирования руководствуются многими факторами, взаимосвязь которых представлена на рисунке.

В общую сложность входят аппаратные и программные затраты на реализацию кодера и декодера, стоимость хранения и передачи информации и т. д. Интенсивность потока данных включает в себя передачу полезной информации, проверочных разрядов, а также запросов и повторений по этим запросам отдельных информационных блоков.

Помехоустойчивое кодирование

Общие сведения

Реальные системы передачи данных не совершенны. Применяя информационную технику, мы должны учитывать возможность возникновения ошибок при передаче и хранении информации. Это в первую очередь относится к

• хранению информации на носителях с высокой плотностью записи (магнитные носители, CD-ROM, DVD);
• передаче данных при ограниченной мощности сигнала (спутниковая и мобильная связь);
• передаче информации по сильно зашумленным каналам (мобильная связь, высокоскоростные проводные линии связи);
• каналам связи с повышенными требованиями к надежности информации (вычислительные сети, линии передачи со сжатием данных).

Во всех вышеперечисленных случаях используются коды, контролирующие ошибки.

Рассмотрим простейшую модель передачи данных с применением помехоустойчивого кодирования.

Пусть кодер источника последовательно выдает информационные слова фиксированной длины. Кодер канала заменяет каждое информационное слово u кодовым словом v . Передатчик генерирует сигналы, соответствующие кодовому слову v и посылает их в канал. Приемник производит обратное преобразование, в результате которого на декодер поступает двоичное принятое слово r . Декодер сравнивает принятое слово r со всеми возможными кодовыми словами используемого кода. Если слово r совпадает с одним из кодовых слов, то соответствующее информационное слово и выдается потребителю. Если r отличается от всех кодовых слов, то в канале произошла обнаруживаемая ошибка. Целью применения кодирования канала является достижение совпадения переданного информационного слова u и принятого информационного слова u ′.

Из данного описания можно сделать 2 вывода:

• Если в процессе передачи по зашумленному каналу кодовое слово отобразится в другое кодовое слово, не совпадающее с переданным, то происходит необнаруживаемая ошибка. Назовем ее остаточной ошибкой декодирования.
• Требуется построить коды, обладающие некоторой математической структурой, которая позволяет эффективно распознать, а в некоторых случаях и исправлять ошибки, возникающие при передаче информации по каналу связи.

Линейные блоковые коды

Важное семейство кодов образуют линейные двоичные блоковые коды. Эти коды замечательны тем, что, представляя информационные и кодовые слова в форме двоичных векторов, мы можем описать процессы кодирования и декодирования с помощью аппарата линейной алгебры. При этом компонентами вводимых векторов и матриц являются символы 0 и 1. Операции над двоичными компонентами производятся по правилам арифметики по модулю 2 .

Наиболее известным линейным кодом является блоковый код Хэмминга. Далее описание линейных блоковых кодов будет производиться на примере этого кода. В частности, будет рассмотрен (7,4)-код Хэмминга.

Кодер двоичного блокового (n , k)-кода отображает множество 2 k возможных двоичных информационных слов в множество 2 k n -мерных кодовых слов. В теории кодирования между этими множествами всегда существует взаимно однозначное соответствие.

Вместо k бит информационного вектора в канал передается n бит кодового вектора. В этом случае говорят об избыточном кодировании со скоростью: R = n ⁄ k .

Чем ниже скорость, тем больше избыточность кода, и тем большими возможностями для защиты от ошибок он обладает. Однако, следует учитывать, что с увеличением избыточности затраты на передачу информацию также возрастают.

Описание процессов кодирования и декодирования

Исходным материалом для построения кодовых конструкций служит n -мерное двоичное векторное пространство, в котором заданы операции арифметики по модулю 2. В него вложено k -мерное линейное пространство, содержащее 2 k кодовых слов. Код С образуется с помощью 2 k комбинаций k линейно независимых базисных векторов { g 1 ,…, g k }.

Эти векторы образуют строки порождающей матрицы кода С.

Для кода C существует дуальный код C d такой, что скалярное произведение любой пары векторов, один из которых принадлежит пространству С, а другой — пространству C d , всегда равно нулю. Это значит, что векторы кода С d ортогональны векторам кода С. С другой стороны, если некоторый вектор ортогонален всем векторам кода С, то он принадлежит коду С d и наоборот. Дуальное векторное подпространство «натянуто» на n − k линейно независимые базисные векторы { h 1 ,…, h n − k }. Эти векторы образуют строки проверочной матрицы.

Рассмотрим пример порождающей и проверочной матриц (7,4)-кода Хэмминга:

Следует отметить важное свойство: как в порождающей, так и в проверочной матрице присутствует единичная матрица. Это свойство используется в процессах кодирования и декодирования.

Кодирование

Кодовое слово v и информационное слово u связаны соотношением:

где G — порождающая матрица, структура которой была описана выше.

Например, информационный вектор u = (1010) отобразится в кодовый вектор следующим образом:

Легко заметить, что последние четыре разряда кодового вектора совпадают с информационным вектором. Это свойство называется систематичностью кода.

Коды, в которых информационное слово может быть непосредственно выделено из соответствующего ему кодового вектора, называются систематическими. Порождающую матрицу любого систематического кода всегда можно путем перестановки столбцов привести к виду:

G k × n = (P k ×(n − k) I k),

где I k — единичная матрица размерности k × k .

Таким образом, в кодовом векторе систематического кода всегда можно выделить информационные и проверочные символы.

Роль проверочных символов и их использование будут подробно разъяснены ниже.

Декодирование

Задача декодера заключается в том, чтобы, используя структуру кода, по принятому слову r , восстановить переданный информационный вектор. Для рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок. Так как рассматриваемый код является систематическим, выразим каждый из трех проверочных символов через символы информационного вектора:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

Если в канале произошла ошибка, то в принятом векторе r хотя бы одно из равенств не будет выполняться. Запишем полученные проверочные соотношения в виде системы уравнений для компонент вектора r:

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

Таким образом, из первых трех столбцов порождающей матрицы G мы получили систему трех проверочных уравнений. Если в полученной системе уравнений хотя бы одна из компонент { s 0 , s 1 , s 2 } не равна нулю, то в канале произошла ошибка.

Запишем систему проверочных уравнений в общем виде. Для любого систематического кода с порождающей матрицей G , проверочная матрица определяется следующим образом:

H (n − k)× n = (I n − k P T k ×(n − k)).

Тогда систему проверочных уравнений можно записать в виде

Вектор s принято называть синдромом. Таким образом, ошибка будет обнаружена, если хотя бы одна из компонент s не равна нулю.

В качестве примера рассмотрим синдромное декодирование (7, 4)-кода Хэмминга. При передаче информационного слова u = (1010) по каналу без шума r = v = (0011010) . Можем убедиться, что в этом случае синдром равен 0 .

Если, например, в кодовом слове произошла одиночная ошибка на четвертой позиции (r = (0010010)), то синдромом является четвертая строка транспонированной проверочной матрицы.

Перебрав все возможные позиции одиночной ошибки, получим полную таблицу синдромов однократных ошибок — таблицу соответствий номера ошибочного разряда получающемуся при этом синдрому.

Можно заметить, что ошибке в i -ой позиции кодового слова соответствует синдром, образованный i -ым столбцом матрицы Н. Так как все столбцы матрицы различны, мы можем с помощью таблицы синдромов исправлять одиночную ошибку, вносимую каналом.

Разновидности ошибок

У линейных блоковых кодов имеются 3 разновидности ошибок:

1. Распознаваемая и исправляемая ошибка
   • Синдром присутствует в таблице синдромов
   • Декодер распознает и исправляет ошибку, а затем передает на приемник корректное слово
2. Распознаваемая ошибка
   • Принятое слово не соответствует ни одному из кодовых слов
   • Синдром не присутствует в таблице синдромов
   • Декодер распознает ошибку и посылает запрос на повторную передачу информационного слова.
3. Нераспознаваемая ошибка
   • Принятое слово соответствует одному из кодовых слов (не соответствующему исходному кодовому слову)
   • Синдром равен 0
   • Декодер не распознает ошибку и выдает потребителю ошибочное информационное сообщение

Заключение

Следует отметить, что эффективность конкретного кода зависит от области его применения и, в особенности, от канала связи. Если в канале отношение сигнал/шум достаточно велико, то вероятность одиночной ошибки во много раз превышает вероятность ошибок высших кратностей, поэтому, использование в таком канале кода Хэмминга с исправлением однократной ошибки может оказаться весьма эффективным. С другой стороны, в каналах, где преобладают многократные ошибки (например, в каналах с замираниями), исправление одиночных ошибок лишено смысла. При практическом выборе конкретного помехоустойчивого кода необходимо также учитывать скорость его декодирования и сложность технической реализации.

Литература

1. Вернер М. Основы кодирования . — М.: Техносфера, 2004.
2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

Олег Рыбак

Действительно с трудом можно найти адекватное объяснение. Чаще всего авторы предполагают, что читателю многое известно заранее и не стремятся пояснять, казалось бы простые моменты, в которых заключена суть. Очень рад, что наткнулся на данный материал, кое-что для себя прояснил.

Линейные коды обладают следующим свойством:

Из всего множества 2 k разрешенных кодовых слов, образующих линейную группу, можно выделить подмножества из k слов, обладающих свойством линейной независимости.

Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования (с помощью линейного выражения) любых других слов, входящих в это подмножество.

В то же время любое из разрешенных кодовых слов можно получить путем суммирования определенных линейно-независимых слов.

Таким образом, построение кодовых комбинаций линейного кода связано с линейными операциями. Для выполнения таких операций удобно пользоваться хорошо разработанным аппаратом матричных вычислений.

Для образования n -разрядных кодовых слов из k- разрядных кодируемых слов (кодирования) используют матрицу, которая называется образующей(порождающей).

Образующая матрица получается путем записи в столбец k линейно-независимых слов.

Обозначим кодируемую информационную последовательность X и будем записывать ее в виде матрицы-строки ||X|| размерностью 1* k , например:

||X||=||11001||, где k=5 .

Один из способов построения образующей (порождающей) матрицы следующий: Она строится из единичной матрицы ||I|| размерностью k*k и приписанной к ней справа матрицы добавочных (избыточных) разрядов ||МДР|| размерности k*r .

где при k =4

Такая структура ОМ обеспечивает получение систематического кода.

Порядок построения матрицы МДР будет рассмотрен ниже.

7.4 Порядок кодирования

Кодовое слово КС получается путем умножения матрицы информационной последовательности ||Х|| на образующую матрицу ||ОМ||:

Умножение выполняется по правилам матричного умножения: (ТАК наТАК)

Надо только помнить, что сложение здесь ведется по модулю 2.

допустим, образующая матрица

||ОМ||= 0010 011

и вектор-строка информационной последовательности

Так как множимая матрица имеет всего одну строку, умножение упрощается. В этом случае следует поставить в соответствие строкам образующей(порождающей) матрицы ||ОМ|| разряды матрицы информационной последовательности ||X|| и сложить те строки образующей(порождающей) матрицы, которые соответствуют единичным разрядам матрицы ||Х||.

Заметим, что ||KC|| = ||X, ДР||,

где ||X||- информационная последовательность (т.к. умножается на единичную матрицу ||I|| ),

а ||ДР|| - добавочные разряды, зависящие от матрицы добавочных разрядов ||МДР|| :

|| ДР ||= || Х || * || МДР||

7.5 Порядок декодирования

В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.

Искажение можно описать с помощью следующей формулы:

|| ПКС || = ||КС || + ||ВО ||,

где ||ВО|| - вектор ошибки - матрица-строка размерностью 1* n , с 1 в тех позициях, в которых произошли искажения.

Декодирование основано на нахождении так называемого опознавателя или синдрома ошибки -матрицы-строки ||ОП|| длиной r разрядов (r - количество добавочных или избыточных разрядов в кодовом слове).

Опознаватель используется для нахождения предполагаемого вектора ошибки.

Опознаватель находят по следующей формуле:

||ОП|| = ||ПКС||* ||ТПМ||,

где ||ПКС||- принятое и, возможно, искаженное кодовое слово;

||ТПМ||,- транспонированная проверочная матрица, которая получается из матрицы добавочных разрядов ||МДР|| путем приписывания к ней снизу единичной матрицы:

Пример ||ТПМ||:

Поскольку ||ПКС|| = ||КС|| + ||BO||, последнюю формулу можно записать в виде:

||ОП|| = ||КС|| * ||ТПМ||+||ВО|| * ||ТПМ||.

Рассмотрим первое слагаемое.

||КC|| - матрица-строка, причем первые k разрядов - информационные.

Докажем теперь, что произведение кодового слова ||КС|| на ||ТПМ|| приводит к получению нулевой матрицы ||0||.

Поскольку ||КС|| - матрица-строка, возможен упрощенный порядок умножения матриц, рассмотренных выше.

Следовательно, первое слагаемое в

||ОП|| = ||КС|| * ||ТПМ|| + ||ВО|| * ||ТПМ||

всегда равно нулю и опознаватель полностью зависит от вектора ошибки ||ВО||.

Если теперь подобрать такую проверочную матрицу ТПМ , а значит и МДР , чтобы разным векторам ошибки соответствовали разные опознаватели ОП, то по этим опознавателям можно будет находить вектор ошибки ВО, а значит и исправлять эти ошибки.

Соответствие опознавателей векторам ошибки находится заранее путем перемножения векторов исправляемых ошибок на ТПМ;

Таким ооразом, способность кода исправлять ошибки целиком определяется ||МДР||. Для построения МДР для кодов, исправляющих однократные ошибки нужно в каждой строке МДР иметь не менее 2-х единиц. При этом также необходимо иметь хотя бы одно различие между двумя любыми строчками МДР .

Полученный нами код неудобен тем, что опознаватель, хотя и связан однозначно с номером искаженного разряда, как число не равен ему. Для поиска искаженного разряда нужно использовать дополнительную таблицу соответствия между опознавателем и этим номером. Коды, в которых опознаватель как число определяет позицию искаженного разряда, были найдены и получили название кодов Хэмминга .

Построение МДР для случая исправления многократных ошибок значительно усложняется. Разными авторами были найдены различные алгоритмы построения ||МДР || для этого случая, а соответствующие коды называются именами их авторов.

Только что в качестве примера были рассмотрены простейшие корректирующие коды - код с простой проверкой на четность, позволяющий обнаруживать однократную ошибку в принятой последовательности, а также блочный итеративный код и «облачный» код, исправляющие одну ошибку с помощью набора проверок на четность. Во всех кодах в процессе помехоустойчивого кодирования формировались дополнительные разряды, присовокупляемые к исходной кодовой комбинации.

Зададим формальные (порождающие) правила, по которым осуществляется кодирование, т.е. преобразование информационной последовательности в кодовое слово.

Простейшим способом описания, или задания, корректирующих кодов является табличный способ, при котором каждой информационной последовательности просто назначается кодовое слово из таблицы кода. Например, для простейшего кода с проверкой на четность таблица соответствия исходных и кодовых комбинаций будет следующей:

Такой способ описания кодов применим для любых, а не только линейных кодов. Однако, при больших к размер кодовой таблицы оказывается слишком большим, чтобы им пользоваться на практике.

Другим способом задания линейных блочных кодов является использование так называемой системы порождающих уравнений, определяющих правило, по которому символы информационной последовательности преобразуются в кодовые символы. Для того же примера система порождающих уравнений будет выглядеть следующим образом:

Однако наиболее удобным и наглядным способом описания линейных блочных кодов является их задание с использованием порождающей матрицы, являющейся компактной формой представления системы проверочных уравнений.

Линейный блочный (л, /с)-код полностью определяется матрицей G размером к х п с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом.

Линейные блочные коды, задаваемые порождающими матрицами, будем называть матричными кодами. Обычное (каноническое) представление порождающей матрицы выглядит так:

Например, для простейшего (4, 3)-кода с проверкой на четность порождающая матрица будет иметь вид:

Пусть т - (т 1; т 2 , ..., т к) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.

Тогда соответствующим ему кодовым словом U будет

С учетом структуры матрицы G символы кодового слова и будут такими:

Иными словами, к крайних левых символов кодового слова совпадают с символами кодируемой информационной последовательности, а остальные (п - к) символов являются линейными комбинациями символов информационной последовательности.

Например, если входная последовательность кодера т = = (10 1), то с применением порождающей матрицы код будет построен так:

8 Командир послал трех разведчиков по первой дороге, трех - по второй, двух - по третьей, по четвертой пошел сам. Составить порождающую матрицу такого кода.

Ответ: по сюжету задачи сообщение, полученное командиром лично, не может быть искаженным. Поэтому ограничимся исследованием информации, передаваемой бойцами. В группе, отправившейся по одной из дорог, каждый боец должен доложить командиру либо об обнаружении объекта (обозначим такой доклад «1»), либо об отсутствии объекта («0»). При отсутствии искажений доклады каждого бойца из одной и той же группы должны совпадать. Следовательно:

Матрицу можно привести к каноническому виду, перенумеровав бойцов, т.е. по первой дороге послав первого, четвертого и пятого, по второй дороге - второго, шестого и седьмого, по третьей дороге-третьего и восьмого бойцов. Получим следующую порождающую матрицу:

Определенный таким образом код называется линейным блочным систематическим (п, /cj-кодом с обобщенными проверками на четность.

Порождающей матрицей линейного -кода называется матрица размера , строки которой – его базисные векторы.

Например,

является порождающей матрицей кода из двух слов {000, 011}.

является порождающей для кода В из примера 6.3.

Мы знаем, что кодовые слова – линейные комбинации базисных векторов, т.е. строк матрицы . Это означает, что слова могут быть получены умножением вектора на матрицу. Итак, сообщение записывается в виде вектора и соответствующее сообщению кодовое слово вычисляется по формуле

Тем самым вектор из бит превращается в последовательность из двоичных символов, передаваемых по каналу или записываемых в память запоминающего устройства.

Обратимся к задаче декодирования.

Предположим, что для некоторого двоичного вектора все кодовые слова -кода , удовлетворяют тождеству

в котором обозначает скалярное произведение векторов и .

Про такой вектор мы скажем, что он ортогонален. Найдя такой вектор, мы могли бы проверять с помощью тождества (6.2), является ли принятая из канала последовательность кодовым словом.

Заметим, что (6.2) справедливо для всех кодовых слов, если оно справедливо для базисных векторов, т.е. если

где верхний индекс Т обозначает транспонирование.

Чем больше таких «проверок» мы найдем, тем, по-видимому, больше ошибок сумеем обнаружить и исправить.

Упражнение 6.4 . Докажите, что проверки образуют линейное пространство.

Это пространство назовем пространством, ортогональным линейному коду или проверочным пространством .

Упражнение 6.5 . Найдите размерность линейного пространства проверок.

Чтобы выполнить последнее упражнение, нужно заметить, что в матрице имеется ровно линейно независимых столбцов. Не больше (почему?) и не меньше (почему?). Зафиксируем список номеров этих столбцов и назовем этот набор чисел информационной совокупностью . Чуть позже смысл этого названия станет яснее. Выберем произвольно значения вектора на позициях, не входящих в информационную совокупность. Какими должны быть значения на позициях информационной совокупности, чтобы выполнилось (6.3)? Чтобы ответить на этот вопрос, придется решить систему линейных уравнений, причем система имеет единственное решение.

Следствием этих рассуждений является теорема

Теорема. Размерность проверочного пространства линейного -кода равна .

Базис проверочного пространства запишем в виде матрицы

называемой проверочной матрицей кода.

Проверочная и порождающая матрицы связаны соотношением

Из этого соотношения мы видим, что для любого кодового слова имеет место

Это тождество можно использовать как критерий принадлежности произвольной последовательности коду, т.е. для обнаружения ошибок.

Зная, можно найти . Для того, чтобы понять, как это сделать, заметим, что один тот же код можно задать разными порождающими матрицами, выбирая по-разному базис пространства. Больше того, заменив в любую строку на любую линейную комбинацию этой строки с другими строками, мы получаем новую порождающую матрицу того же кода.

Перестановка столбцов матрицы , вообще говоря, приводит к другому коду, но этот другой код по своим характеристикам не отличается от исходного. Коды, различающиеся только нумерацией позиций, называются эквивалентными.

Понятно, что для каждого кода найдется эквивалентный, для которого первые позиций образуют информационную совокупность, т.е. первые столбцов образуют невырожденную матрицу размера . Заменяя строки линейными комбинациями строк (метод Гаусса) полученную матрицу можно привести к виду

где – единичная матрица порядка , а – некоторая матрица размера .

Матрица вида (6.6) называется порождающей матрицей, приведенной к систематическому виду , а соответствующий код называется систематическим . Кодирование для систематического кода немного проще, чем для кода общего вида:

, (6.7)

т.е. в кодовом слове первые позиций – просто копия информационной последовательности , а остальные (проверочных) позиций получаются умножением информационного вектора на матрицу размера , что иногда существенно меньше, чем . Соответственно, и информация о систематическом коде занимает существенно меньше памяти, чем информация о линейном коде общего вида.

Для систематического кода с порождающей матрицей в форме (6.6) проверочная матрица может быть вычислена по формуле

Упражнение 6.6 . Проверьте (6.7). Подсказка: для этого нужно подставить (6.8) и (6.6) в (6.4).

Как найти проверочную матрицу для несистематического кода?

Очень просто. Нужно привести матрицу к систематическому виду и воспользоваться (6.7). Если первые столбцов порождающей матрицы образуют невырожденную подматрицу (первые позиций образуют информационную совокупность), то для приведения к систематической форме достаточно таких операций как перестановка строк и замена строк линейными комбинациями строк. Если нет – нужно будет сначала найти информационную совокупность и перенумеровать позиции так, чтобы первые позиции стали информационными.

Так как, согласно определению, линейный (л, /с)-код длины п над GF(q) является подпространством GF k (q) векторного пространства GF n (q), то должно существовать ортогональное дополнение подпространства GF k (q) линейного кода (см. подпараграф 1.7.1).

Пусть Н - матрица, строки которой соответствуют базисным векторам ортогонального дополнения g-ичного линейного кода С длины п. Тогда для любого вектора с, принадлежащего коду, справедливо:

Условие (2.10) позволяет проверить принадлежность произвольной л-после- довательности элементов GF(q) определенному g-ичному линейному коду.

Если вектор линейного кода имеет вес Хэмминга шо, то это значит, что в кодовом слове присутствует шо ненулевых символов (согласно определению веса Хэмминга, см. подпараграф 2.1.4). Тогда, согласно правилам умножения матриц, произведение вектора с со значением шо веса Хэмминга на матрицу Н т соответствует линейной комбинации шо столбцов матрицы Н. При этом равенство (2.10), очевидно, имеет место тогда и только тогда, когда шо столбцов матрицы Н линейно зависимы.

Таким образом, условием существования во множестве кодовых слов некоторого линейного кода кодового слова с весом Хэмминга шо является наличие в матрице Н линейно зависимых столбцов в количестве шо. Из этого следует также, что линейный код имеет минимальный вес (см. подпараграф 2.1.4) не менее некоторого значения шо тогда и только тогда, когда любые шо - 1 столбцов матрицы Н линейно независимы. Следовательно, согласно неравенству (2.6), для того чтобы найти линейный код с минимальным весом шо, исправляющий t ошибок, достаточно найти матрицу Н, у которой не менее чем шо - 1 = 2-t любых столбцов были линейно независимы.

Рассмотрим подробнее матрицу Н. Как было сказано выше, строками матрицы Н являются базисные векторы ортогонального дополнения линейного кода. Если множество л-последовательностей образует подпространство размерности к, то ортогональное дополнение этого подпространства будет иметь размерность п-к (см. подпараграфы 1.7.1 и 1.7.2). Подпространство размерности п - к образуют любые п-к базисных векторов. Поэтому матрица Н должна содержать п-к линейно независимых строк.

Так как матрицы G и Н принадлежат одному пространству л-последовательностей, то число столбцов матрицы Н равно числу столбцов матрицы G. Таким образом, матрица Н имеет размер (л - к) х л. Все столбцы матрицы Н, как уже было сказано, образуют линейно независимые группы по 2t столбцов.

Согласно соотношению (2.2), любое кодовое слово линейного кода является линейной комбинацией строк порождающей матрицы G кода. При этом, очевидно, каждая строка матрицы G соответствует некоторому кодовому слову. Поэтому соотношение (2.10) можно переписать следующим образом:

Результатом произведения матриц G размера к* ли Н т размера л х (п-к) является матрица размера к х (л - к), состоящая из нулевых элементов.

Матрица Н размера (п-к)х л, строками которой являются базисные векторы ортогонального дополнения подпространства линейного кода, называется проверочной матрицей линейного кода.

Согласно соотношению (2.4), порождающая матрица систематического линейного кода состоит из единичной матрицы порядка к и матрицы проверочных символов размера к х (л - к), которая, в свою очередь, является расширением единичной матрицы. Как показано в приложении 1, умножение двух матриц можно выполнить, разделив перемножаемые матрицы на матрицы меньшего размера (блоки) с последующим умножением отдельных блоков перемножаемых матриц. Тогда для матриц G и Н можно записать:

Число столбцов в блоках А и В матрицы Н 7 должно соответствовать числу строк в блоках Ек и Р матрицы G (по правилам умножения матриц). Результирующая матрица должна иметь размер /с * (л - к). Очевидно, что если положить А = -Р и В = Ел_/с, то матрица Н будет удовлетворять уравнению (2.11).

Таким образом, матрица Н т является расширением матрицы -Р и помимо матрицы - Р матрица Н содержит единичную матрицу порядка п - к. Матрица Н т является результатом транспонирования матрицы Н.

Результатом повторного транспонирования матрицы является исходная матрица. Поэтому матрица Н может быть получена путем транспонирования матрицы Н т. Так как для любого элемента а поля GF[ 2) справедливо а = - а, то для двоичного линейного кода справедливо Р--Р.

Матрица Н двоичного линейного кода будет иметь следующий вид:

Матрица Р, входящая в состав матрицы G и содержащая проверочные символы, может быть получена путем транспонирования матрицы Р т, входящей в состав матрицы Н.

Таким образом, построение линейного кода сводится к поиску матрицы Н. По заданной матрице Н легко найти матрицу G.

Пример 2.1.4. Рассмотрим построение двоичного линейного кода - кода над GF(2), исправляющего одну ошибку кодового слова с информационной последовательностью размера к = 3 бита.

Согласно соотношению (2.9), для кода с максимальным расстоянием r = 2-t = = 2. Тогда л = /с + г = 3 + 2 = 5. Однако, как будет показано в следующем подпараграфе, линейный двоичный (5,3)-код не способен исправлять одиночную ошибку кодового слова. При этом минимальное число избыточных символов для данного случая г = 3, а рассматриваемый код - двоичный линейный (6,3)-код.

Таким образом, в данном случае матрица Н содержит проверочную матрицу размера /сх(л-/с) = 3*3и единичную матрицу порядка п-к= 3.

Все столбцы матрицы Н должны образовывать линейно независимые группы по два столбца и линейно зависимую группу из трех столбцов. Такому условию отвечают, например, последовательности 101, 110 и 011 над GF(2). Указанные последовательности образуют столбцы матрицы Р т, входящей в состав матрицы Н. Остальные элементы матрицы Н соответствуют единичной матрице порядка 3:

Дописав к единичной матрице порядка 3 матрицу Р, полученную транспонированием матрицы Р т, получим матрицу G:

Рассмотрим теперь процесс формирования и структуру кодового слова двоичного линейного (6, 3)-кода с порождающей матрицей вида (2.12):

Три первых символа кодового слова (ci - Сз) содержат информационные символы (/ 1 - г"з), сформированные в результате умножения матрицы информационной последовательности i на единичную матрицу порядка 3, входящую в состав матрицы G. Оставшиеся символы кодового слова (С4 - Сб) содержат проверочные символы (t^ - tz), полученные в результате умножения матрицы информационной последовательности на матрицу проверочных символов Р, также входящую в состав матрицы G.

Нетрудно проверить, что в случае (6, 3)-кода из примера 2.1.4 минимальное число ненулевых символов среди всех кодовых слов равно трем (кодовые слова 001101, 010011,100110 и 111000). Таким образом, d* = 3 и, согласно соотношению (2.5), код должен исправлять одну ошибку кодового слова. Как будет показано в следующем подпараграфе, это действительно так.