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

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

,

а выходом кодера является вектор из символов

.

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

(8.1.2)

где или , а представляют произведение и . Линейные уравнения (8.1.2)

можно также представить в матричной форме

где - порождающая матрица кода, равная

(8.1.4)

Заметим, что произвольное кодовое слово – это просто линейная комбинация векторов из ,

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

Любую порождающую матрицу кода путём проведения операций над строками (и перестановкой столбцов) можно свести к «систематической форме»:

, (8.1.6)

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

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

Пример 8.1.1. Рассмотрим код (7, 4) с порождающей матрицей

. (8.1.7)

Типичное кодовое слово можно выразить так:

где представляют четыре информационных бита, a представляют три паритетных бита, определённых так:

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

Рис. 8.1.1. Линейный регистр сдвига для получения двоичного кода (7,4)

С любым линейным кодом кодом связан дуальный код размерностью .

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

где означает вектор-столбец, состоящий из нулей, а - кодовое слово кода. Поскольку (8.1.9) справедливо для любого кодового слова кода, то следует

где - теперь матрица со всеми нулевыми элементами.

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

(8.1.11)

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

Пример (8.1.2). Для систематического кода (7, 4), генерируемого матрицей , определяемой (8.1.7), имеем согласно (8.1.11) матрицу в виде

(8.1.12)

Теперь уравнение распадается на три уравнения

(8.1.13)

Таким образом, видим, что произведение эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления Это значит, что (8.1.13) эквивалентно (8.1.8).

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

Выскажем соображение, касающееся связи минимального расстояния кода и его проверочной матрицы . Произведение с представляют линейную комбинацию столбцов . Поскольку , векторы-столбцы линейно зависимы. Допустим, что означает кодовое слово с минимальным весом линейного кода . Оно должно удовлетворять условию . Поскольку минимальный вес равен минимальному расстоянию, следует, что столбцов линейно зависимы. Альтернативно, мы можем сказать, что не более, чем столбцов линейно независимы. Поскольку ранг матрицы не больше , имеем . Следовательно, имеет верхнюю границу. Мы называем код информационных символов (во всех кодовых комбинациях) нулями. Эти. Укороченный код состоит из кодовых слов. Минимальное расстояние этих кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного кода.

Рассмотрим систематический линейный код , задаваемый порождающей матрицей , и построим матрицу вида

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

Из (6.6) следует, умножение любого кодового вектора на транспонированную матрицу дает нуль, в связи с этим матрицу (6.5) называют проверочной матрицей . Кроме того, говорят, что линейный код является нуль–пространством проверочной матрицы, либо что код ортогонален проверочной матрице.

На основании соотношений (6.4) и (6.6) имеем

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

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

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

Доказательство: Рассмотрим линейный код, задаваемый проверочной матрицей размерности в виде

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

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

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

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

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

Рассматривая структуру матриц и можно вынести следующее заключение. Обе матрицы состоят из множества линейно независимых векторов, поскольку наличие в их структуре единичной матрицы делает невозможным существование линейной комбинации строк с нулевой суммой. Следовательно, каждая из матриц может рассматриваться как базис некоторого линейного пространства. Более того, каждое из этих пространств является подпространством векторного пространства, состоящего из всех векторов длины . Учитывая сказанное выше, можно их «поменять ролями» и использовать в качестве порождающей, а – проверочной матрицы некоторого другого кода. Коды, связанные с таким преобразованием, называются дуальными друг другу. Таким образом, если исходным являлся кодом, то дуальным ему будет код.

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

Любой код с кодовым расстоянием , удовлетворяющим соотношению (6.8), называется кодом с максимальным расстоянием .

Замечание. Граница Синглтона (6.8) бесполезна для двоичных кодов, поскольку значительно уступает в точности границам Плоткина и Хэмминга. Однако, она играет значительную роль в случае –ичных кодов.

1.2.2. Проверочная матрица линейного кода

Поскольку линейный код V является подпространством, то для него существует ортогональное дополнение (или нулевое подпространство ). Ортогональное дополнение V " (n , k ) - кода V состоит из всех векторов длины n , ортогональных к каждому вектору v Î V . Векторы и называются ортогональными , если их скалярное произведение равно 0. Для двоичных векторов скалярное произведение равно сумме произведений соответствующих компонент. Например, скалярное произведение (00101, 10110) векторов 00101 и 10110 есть вектор 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как линейный код. Множество V " - называется кодом, дуальным или двойственным к V.

Ортогональное дополнение V " (n , k ) - кода V имеет размерность (n - k) ; соответственно любой его базис состоит из (n -k) векторов. Порождающая матрица Н ортогонального дополнения называется проверочной матрицей кода V .

Т. к проверочная матрица состоит из базисных векторов ортогонального дополнения, то двоичный вектор с является кодовым словом, если и только если сН T = 0. Таким образом, проверка на наличие ошибок при передаче кодового слова сводится к умножению двух матриц вместо перебора всех кодовых слов. Умножение матриц, размерность которых составляет несколько тысяч, при современной вычислительной технике выполняется очень быстро.

Проверочную матрицу можно построить путем нахождения фундаментальной системы решений для соответствующей системы уравнений. Матрица

из предыдущего раздела порождает следующую систему уравнений:

Основная матрица системы совпадает с матрицей G . Неизвестные x 1 , x 2 и x 3 , для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x 4 и x 5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:

и

Из первой системы получаем x 1 = 1, x 2 = 0, x 3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x 1 = 1, x 2 = 1, x 3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

.

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

Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема 1.3. Каждое не нулевое кодовое слово имеет вес не менее w , тогда и только тогда, когда любая совокупность из w столбцов матрицы Н

Доказательство. Для любого кодового слова с выполняется равенство сН T = 0. Пусть кодовое слово с имеет вес u . Исключим из рассмотрения нулевые компоненты вектора. Полученное равенство будет соотношением линейной зависимости u столбцов из Н . Следовательно, Н содержит множество из u линейно зависимых столбцов. Таким образом, в коде существует слово веса u , если и только если в матрице Н существует совокупность из u линейно зависимых столбцов. Таким образом, все не нулевые слова кода имеют вес не меньше w w -1 столбцов матрицы Н является линейно независимой.

Как следствие теорем 1.1 и 1.3 имеет место следующее утверждение:

Следствие. Расстояние линейного кода не менее w , если и только если любая совокупность из w -1 столбцов матрицы Н является линейно независимой.

Согласно сформулированным выше утверждениями, для того чтобы найти (п ,k )-код, исправляющий t ошибок, достаточно построить матрицу Н размерности (п - k ) × n , в которой любые 2 t столбцов линейно независимы.

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

Например,

является порождающей матрицей кода из двух слов {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). Если первые столбцов порождающей матрицы образуют невырожденную подматрицу (первые позиций образуют информационную совокупность), то для приведения к систематической форме достаточно таких операций как перестановка строк и замена строк линейными комбинациями строк. Если нет – нужно будет сначала найти информационную совокупность и перенумеровать позиции так, чтобы первые позиции стали информационными.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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