Как найти порождающую матрицу
Перейти к содержимому

Как найти порождающую матрицу

  • автор:

6.3. Порождающая и проверочная матрицы

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

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

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

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

.

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

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

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

, , (6.2)

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

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

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

, (6.3)

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

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

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

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

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

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

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

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

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

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

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

. (6.4)

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

. (6.5)

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

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

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

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

, (6.6)

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

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

, (6.7)

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

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

. (6.8)

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

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

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

Упражнение 6.7. Сформулируйте алгоритм нахождения порождающей матрицы по проверочной.

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

Упражнение 6.9. Постройте порождающие и проверочные матрицы для кодов из примера 6.4.

Подведем итоги этого важного параграфа.

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

Матрица используется при кодировании (формула (6.7)), матрицей можно воспользоваться при декодировании. Например, выполнение тождества (6.5) свидетельствует о том, что данная последовательность принадлежит коду.

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

Любой циклический (n, k) – код может быть задан в соответствии с определением 2, порождающим многочленом g(x) или проверочным многочленом .

Знание этих многочленов позволяет построить порождающую матрицу и матрицу проверок. Для циклического (n, k) – кода существует простой способ нахождения k линейно независимых кодовых комбинаций, образующих порождающую матрицу . Этот способ состоит в следующем. Записывается порождающий многочлен g(x). В соответствии с определением 2 комбинация, соответствующая порождающему многочлену, принадлежит циклическому (n, k) – коду. В соответствии с определением 1 циклические сдвиги комбинации, соответствующей g(x), также должны принадлежать этому же коду. Алгебраически сдвиг соответствует умножению кодовой комбинации на х. Так как степень g(x) равна nk, то подобным образом мы можем получить кодовые комбинации

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

.

Путем элементарных преобразований эта матрица может быть приведена к канонической форме.

Аналогичным образом по проверочному многочлену можно построить матрицу проверок

.

Пример 6.4. Для циклического (7,4) – кода с порождающим многочленом (см. пример 6.3.) построить порождающую матрицу.

Следовательно, порождающая матрица для данного кода имеет вид:

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

Свойство 6.1. Произведение кодовой комбинации циклического кода на произвольный многочлен дает кодовую комбинацию этого же циклического кода.

Действительно , а любое произведение такого вида равно нулю, т.е. принадлежит кодовому подпространству (раздел 6.2).

Более элементарное доказательство:

.

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

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

Коэффициент при х в произведении равен

.

Слагаемые, содержащие , появляются вследствие слагаемых в произведении , которые содержат . Но так как , т.е. , то . Равенство для можно представить в виде скалярного произведения:

.

В этом произведении первый вектор соответствует а(х). Второй вектор содержит коэффициенты b(х), расположенные в обратном порядке и сдвинутые циклически на j+1 элемент вправо.

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

.

Учитывая эту специфику необходимо при матричном описании кода коэффициенты матрицы проверок записывать в обратном порядке. В этом случае будет выполнено условие

Пример 6.5. Построить матрицу проверок для циклического (7,4) – кода из предыдущего примера.

Для построения матрицы проверок найдем проверочный многочлен

В силу того, что условие равенства нулю произведения многочленов и скалярного произведения соответствующих им векторов не совпадают, для выполнения равенства при построении матрицы компоненты векторов, соответствующих h(x), xh(x) и x 2 h(x) записываем в обратном порядке

.

В полученной матрице проверок в качестве столбцов записаны все 7 ненулевых последовательностей длины 3. Следовательно, данный код является кодом Хэмминга.

Вообще говоря, циклические коды Хэмминга строятся на основе порождающих многочленов степени m, являющихся сомножителями двучленов и не являющихся сомножителями никаких двучленов меньшей степени. Корни этих многочленов имеют порядок 2 m -1, т.е они являются примитивными элементами поля GF(2 m ). Это означает, что порождающий многочлен кода Хэмминга порождает поле GF(2 m ).

Условимся в любом циклическом коде первые nk элементов кодовой комбинации, то есть коэффициенты при использовать в качестве проверочных элементов, а последние k элементов, то есть коэффициенты при , — в качестве информационных (рис. 6.1).

x 0 x 1 x 2 x n-k-1 x n-k x n-2 x n-1

a0

an-k

Избыточные элементы Информационные элементы

Структура кодовой комбинации циклического кода

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

Всякий циклический (n, k) – код приводится к этой форме следующим образом.

Пусть есть многочлен степени k-1, соответствующий комбинации простого k элементного кода, которую необходимо закодировать циклическим (n, k) – кодом. В комбинации циклического (n, k) – кода эту k — элементную комбинацию необходимо поместить на позиции информационных элементов, для чего помножим многочлен на . В результате получаем многочлен , степень которого равна n-1. Так как по определению циклического кода каждая кодовая комбинация должна делиться на порождающий многочлен g(x) степени nk, то проверим выполнение этого условия. В общем случае в результате деления получим частное qi(x) степени k-1 и остаток, степень которого не превышает nk-1. Результат деления представим в следующем виде:

.

Рассмотрим многочлен . Коэффициенты при этого многочлена являются коэффициентами остатка , а коэффициенты при степенях элементами первичной кодовой комбинации .

С другой стороны

,

то есть многочлен делится на g(x). Итак, и есть искомая кодовая комбинация циклического (n, k) – кода. Отсюда получаем правило построения порождающей матрицы циклического (n, k) – кода в канонической форме:

,

где Ik – единичная матрица размерности , соответствующая информационным элементам кодовых комбинаций, ;

— матрица размерности , j — строка, которой соответствует остатку от деления на g(x).

Матрица проверок строится на основании матрицы по правилу

.

Пример 6.6. Построить порождающую матрицу и матрицу проверок в канонической форме для циклического (7,4) – кода с порождающим многочленом . Находим частное и остаток от деления на g(x) и записываем результат деления в форме равенства

.

Из рассмотренного примера видно, что проверочная матрица циклического (n, k) – кода содержит в качестве столбцов остатки от деления на порождающий многочлен g(x).Сравнение столбцов найденной проверочной матрицы с элементами поля GF(2 3 ) показывает их полное совпадение с ненулевыми элементами GF(2 3 ). Результаты рассмотренного примера будут использованы для обоснования эквивалентности различных столбцов вычисления синдрома.

Найти порождающую матрицу

Author24 — интернет-сервис помощи студентам

Добрый вечер. Мне задана проверочная матрица H. По строкам: (101101),(100011),(111000). Нужно по ней найти порождающую матрицу G.
Как известно если H = (-P T |E) то G = (E|P).

Я не могу элементарными преобразованиями строк сделать единичную в правой части матрицы H. Помогите пожалуйста. Или можно использовать и элементарные столбцов?

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Найти КС-грамматику, порождающую язык
Не могу догадаться, как их решать. Найти КС-грамматику, порождающую язык < 1^n 0^m 1^m 0^n |.

Найти КС-грамматику, порождающую данный язык
Нужно найти КС-грамматику порождающую язык aibjckdl, причем i + 2k = j + 3l. Я уже несколько дней.

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

Регистрация: 16.04.2013
Сообщений: 11

Меняете местами 2 и 6 столбец в проверочной матрице. Правая часть станет единичной.
Левая часть = P. Т.к. левая часть симметрична от-но диагонали и код двоичный, то P= -P T . Осталось дописать слева к этой левой части единичную матрицу и сделать ещё раз замену стобцов 2-6.

G=(110110),(000111),(011100). Для проверки правильности: G*H T =0

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Ввести матрицу А, найти сумму четных элементов, построить матрицу C по заданной формуле
3)Составить программу, которая: вводит с клавиатуры A в виде матрицы и выводит на экран сумму всех.

Найти матрицу смежности и матрицу инциденции
если даны 2 графа G1(неориентированный) и G2(ориентированный) необходимо найти матрицу смежности и.

Построить ПЛ-грамматику, порождающую L
Язык над алфавитом Σ = , состоящий из всех слов, которые имеют четную длину тогда и только.

Построить грамматику, порождающую язык
Построить грамматику, порождающую язык L(G)= ()

Или воспользуйтесь поиском по форуму:

Как найти порождающую матрицу

Откуда же берутся порождающие матрицы G? Порождающая матрица получается путем последовательного сдвига соответствующего порождающего многочлена g(x) по разрядам вправо. Последовательному сдвигу вправо отвечает умножение g(x) на x i :

G = = .

Порождающая матрица G имеет размерность (k – 1) · m, поскольку для сдвига берутся степени x i в пределах 0 < i < k – 1, а степень порождающего многочлена g(x) равна m. Мы знаем, что каждому порождающему многочлену соответствует проверочный многочлен h(x), который удобно записать в порядке убывания степеней:

g(x) = g0 + g1x + g2x 2 + . + gmx m ,

h(x) = hkx k + hk–1 x k–1 + . + h0,

причем x n + 1 = g(x)h(x), где, напомним, n — общее число символов, k — число информационных, а m — число проверочных символов в кодовом слове. Если существует порождающая матрица G, то должна существовать и соответствующая ей проверочная матрица H. Действительно, такую матрицу можно получить путем последовательного сдвига проверочного многочлена h(x) влево:

H = = .

Предположим, у нас есть конкретный порождающий многочлен g(x) = 1 + x 2 + x 3 . Проверочный многочлен h(x) находится простым делением многочлена x 7 + 1 на заданный многочлен g(x); в результате имеем: h(x)= = x 4 + x 3 + x 2 + 1. В соответствии с вышеприведенными определениями, находим конкретный вид порождающей G и проверочной H матриц:

G = , H = ,

GH* = (HG*)* = 0.

Последнее равенство говорит о том, что матрицы G и H ортогональны относительно друг друга (звездочка означает операцию транспонирования матрицы).

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

G’ = (Ek · k | Gm · k), H’ = (Hk · m | Em · m),

где Ek · k и Em · m — единичные матрицы.

Существует, по крайней мере, два способа сведения ленточных матриц к систематическому виду. Первый наиболее надежный способ состоит в нахождении ряда остаточных многочленов. Если ri(x) остаточный многочлен от деления xi на порождающий многочлен g(x), то сумма элементов ri (x) + xi дает строки систематической матрицы G. Аналогичным способом находятся строки проверочной матрицы H. Второй способ заключается в том, чтобы найти соответствующие линейные комбинации строк или столбцов исходных матриц ленточного типа. Найдем G и H для предыдущего случая:

Эти две систематические матрицы можно было бы получить путем сложения векторов-столбцов исходных ленточных матриц (напоминаем, счет столбцов для G матрицы начинается с нуля, а для H матрицы — с шести).

G’ : 0′ = 1 + 2, 1′ = 1 + 5, 2′ = 3, 3′ = 0, 4′ = 1, 5′ = 4 + 1, 6′ = 6;

H’ : 0′ = 5, 1′ = 3, 2′ = 4, 3′ = 2, 4′ = 6, 5′ = 1, 6′ = 0.

Теперь поясним, как составить проверочные соотношения и определить коды ошибок si по известной проверочной матрице. С этой целью выпишем три равенства, отвечающих строкам матрицы H’ :

При ошибке в символе h0 суммы s2 и s3 изменятся на 1, а при ошибке в h1 не будут равны нулю суммы s1 и s2. Таким образом, можно составить все коды ошибок для всех символов (табл. 2.87).

При одновременном появлении ошибок в двух символах, например в h5 и h6, коды ошибок будут складываться; в данном случае он становится таким же, как и при одиночной ошибке в символе h1. Поэтому, характеризуя код с точки зрения помехозащищенности, мы должны сказать, что он обнаруживает и исправляет любые одиночные ошибки, а также обнаруживает, но не исправляет двойные ошибки.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *