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

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

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

G = = .

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

H = = .

G = , H = ,

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

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

Существует, по крайней мере, два способа сведения ленточных матриц к систематическому виду. Первый наиболее надежный способ состоит в нахождении ряда остаточных многочленов. Если r_i(x) остаточный многочлен от деления x_i на порождающий многочлен g(x), то сумма элементов r_i (x) + x_i дает строки систематической матрицы 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’ :

При ошибке в символе h₀ суммы s₂ и s₃ изменятся на 1, а при ошибке в h₁ не будут равны нулю суммы s₁ и s₂. Таким образом, можно составить все коды ошибок для всех символов (табл. 2.87).

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

Источник

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

Линейные коды задаются с помощью порождающей G(x) и проверочной H(x) матриц. Эти матрицы связаны основным уравнением кодирования:

Матрица G(x) содержит k строк и n столбцов, ее элементами являются нули и единицы. В качестве строк матрицы G(x) выбираются любые ненулевые линейно независимые n-значные векторы, отстоящие друг от друга не менее чем на заданное кодовое расстояние d₀.

Векторы v₁, v₂, …, v_k называются линейно независимыми, если выполняется условие

где с_i=<0, 1>, а сложение выполняется по модулю два. То есть, каким бы образом мы не суммировали различные строки матрицы G(x), не получим суммы, равной нулю. Все множество кодовых слов состоит из строк порождающей матрицы и всевозможных комбинаций этих строк, т.е. суммы по модулю два всех строк матрицы G(x) сначала попарно, затем по три и так далее до суммы всех k строк.

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

Поскольку линейно независимые векторы могут быть выбраны произвольным образом, то, очевидно, можно построить множество матриц G(x) с одним и тем же кодовым расстоянием d₀.

Свойство линейной независимости векторов инвариантно относительно двух следующих операций (выполняя эти две операции, кодовое расстояние не меняется):

1) возможна произвольная перестановка строк и столбцов в матрице G(x);

2) замена i-й строки на сумму i-й и j-й строк и т. д. (эту операцию нельзя осуществлять со столбцами матрицы G(x)).

Производя вышеуказанные операции, любую произвольную матрицу G(x) можно привести к так называемому приведенно-ступенчатому (каноническому) виду:

где I_k –единичная подматрица размерностью k×k,

H * T – транспонированная проверочная матрица (транспонировать – значит поменять местами строки и столбцы).

Исходя из основного уравнения кодирования, проверочная матрица имеет вид

Возьмем порождающую матрицу кода (7,4). В этой матрице количество строк равно 4 (k=4), а количество столбцов 7(n=7).

Для того чтобы построить проверочную матрицу, необходимо транспонировать подматрицу G(x) * и к ней приписать единичную матрицу размером l×l. Проверочная матрица будет иметь размер l×n, l = n-k=7-4=3, т.е. матрица Н(x) имеет размер 3×7.

Источник

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

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

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

является порождающей для кода В из примера 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) свидетельствует о том, что данная последовательность принадлежит коду.

Источник

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

(1)

Матрица H=(a_ij) коэффициентов системы (1) называется проверочной матрицей линейного (n, k) кода и однозначно определяет множество кодовых векторов, являющееся правым нуль-пространством матрицы H. Код называется систематическим, если первые k символов являются информационными: , , …, , а последние n-k символов – проверочными. Проверочная матрица систематического кода элементарными преобразованиями строк приводится к виду H = , где – единичная матрица размерности n-k.

Систему (1) можно переписать в матричном виде:

Пример 1. Пусть q = 2, n = 6, k = 3, H = .

Сообщение (а₁ а ₂ а₃) кодируется вектором х = (а₁ а₂ а₃ х₄ х₅ х₆), то есть , , , а проверочные символы х₄, х₅, х₆ находятся из системы линейных уравнений, заданной проверочной матрицей H.

Имеем систему уравнений:

Если передано сообщение а = 011, то соответствующим кодовым вектором будет х = 011011. Всего имеется 2 3 кодовых векторов:

000000, 011011, 110110, 001110,

100011, 111000, 010101, 101101.

Порождающая матрица линейного кода

, где (3)

Перепишем в матричном виде:

. Транспонируя, получим:

Свойства порождающей матрицы:

1. Все кодовые слова можно получить, умножая информационный вектор на матрицу G.

(a₁, a₂, …, a_k) ∙ G = (x₁, x₂, …, x_n) C.

2. Строки матрицы G являются кодовыми словами.

Пусть .

3. Любая линейная комбинация строк матрицы G является кодовым словом, и наоборот.

4. Строки матрицы G линейно независимы.

Так как в начале матрицы G стоит единичная матрица, то её строки образуют ступенчатую систему, а значит, g₁, g₂,…, g_k линейно независимы. Из свойств 3 и 4 следует свойство 5.

5. Строки матрицы G g₁, g₂,…, g_k образуют базис линейного пространства кода С.

Пример 2. Дана проверочная матрица линейного (4,2)-кода над полем F₃ = <0,1,2>.

Скорость передачи данного кода k/n = 2/4 = ½

Матрица H имеет вид: H = . Найдём порождающую матрицу G по формуле .

, откуда .

Составим таблицу кодирования. Всего может быть 9 различных информационных сообщений (a₁,a₂): 00, 01, 02, 10, 11, 12, 20, 21, 22. Они записаны в первых двух столбцах таблицы. Соответствующие им кодовые векторы находим, умножая информационное сообщение на матрицу G:

(a₁ a₂) ∙ = (x₁ x₂ x₃ x₄)

a₁a₂x₁x₂x₃x₄000000010121020212101022111110121201202011212102222220

Аналогичные результаты можно получить, записав систему проверочных уравнений, определяемую матрицей Н, и учитывая, что , – информационные символы:

.

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

Дата добавления: 2019-02-12 ; просмотров: 1210 ; Мы поможем в написании вашей работы!

Источник