Проверочная матрица линейного кода
Будем считать, что символы, из которых состоят исходное и кодовое сообщения, являются элементами некоторого конечного поля Fq, где q – мощность поля. Также будем считать, что шум заключается в замене некоторых символов на другие элементы поля Fq, что эквивалентно добавлению к кодовому вектору x = (x 1 , x 2 , …, xn), поступающему в канал, вектора ошибок e = (e 1 , e 2 , …, en). Для исправления ошибок такого рода используются линейные коды. Исходное сообщение разбивается на блоки по k символов, и каждый блок (a 1 , a 2 , …, ak) заменяется на соответствующий ему кодовый вектор (x 1 , x 2 , …, xn) длины n > k, в котором k позиций – информационные, то есть , , …, , а остальные n–k позиций – проверочные, и определяются из системы уравнений:
(1)
Матрица H=(aij) коэффициентов системы (1) называется проверочной матрицей линейного (n, k) кода и однозначно определяет множество кодовых векторов, являющееся правым нуль-пространством матрицы H. Код называется систематическим, если первые k символов являются информационными: , , …, , а последние n-k символов – проверочными. Проверочная матрица систематического кода элементарными преобразованиями строк приводится к виду H = , где – единичная матрица размерности n-k.
Систему (1) можно переписать в матричном виде:
Пусть Н – матрица размерности (n - k)´n и ранга n - k с элементами из поля Fq. Множество С всех n– мерных векторов над Fq, удовлетворяющих равенству (2), называется линейным (блоковым) кодом над Fq блоковой длины n, а также линейным ( n , k ) – кодом. Матрица Н является проверочной матрицей кода С. Если q=2, то С называют бинарным (или двоичным) кодом. Число k / n называют скоростью передачи (или информационной скоростью).
|
|
Пример 1. Пусть q = 2, n = 6, k = 3, H = .
Сообщение (а1 а 2 а3) кодируется вектором х = (а1 а2 а3 х4 х5 х6), то есть , , , а проверочные символы х4, х5, х6 находятся из системы линейных уравнений, заданной проверочной матрицей H.
Имеем систему уравнений:
Поэтому х4 = а2+а3, х5 = а1+а3 , х6 = а1+а2.
Если передано сообщение а = 011, то соответствующим кодовым вектором будет х = 011011. Всего имеется 23 кодовых векторов:
000000, 011011, 110110, 001110,
100011, 111000, 010101, 101101.
Порождающая матрица линейного кода
Пусть проверочная матрица имеет вид H = , где – единичная матрица размерности n - k. В этом случае из соответствующей СЛУ получим:
, где (3)
Учитывая, что x1=a1, x2=a2, …, xk=ak, из системы уравнений (3) получим:
Перепишем в матричном виде:
. Транспонируя, получим:
Матрица называется порождающей матрицей систематического линейного (n , k)-кода с проверочной матрицей H = .
Свойства порождающей матрицы:
1. Все кодовые слова можно получить, умножая информационный вектор на матрицу G.
|
|
(a1, a2, …, ak) ∙ G = (x1, x2, …, xn) C.
2. Строки матрицы G являются кодовыми словами.
Пусть .
Рассмотрим информационный вектор (a1, a2, …, ak) = (1, 0, …, 0)
(1, 0, …, 0) ∙ G = g1 , и по свойству 1 g1Î C.
Аналогично (0, 1, …, 0) ∙ G = g2 Î C,…, (0, 0, …, 1) ∙ G = g k Î C .
3. Любая линейная комбинация строк матрицы G является кодовым словом, и наоборот.
(a1, a2, …, ak) ∙ G = a1 ∙ g1 + a2 ∙ g2 + … + ak ∙ gk Î C по свойству 1.
Таким образом, С = L(g1, g2, …, gn) – линейная оболочка векторов g1, …, gk.
4. Строки матрицы G линейно независимы.
Так как в начале матрицы G стоит единичная матрица, то её строки образуют ступенчатую систему, а значит, g1, g2,…, gk линейно независимы. Из свойств 3 и 4 следует свойство 5.
5. Строки матрицы G g1, g2,…, gk образуют базис линейного пространства кода С.
6. В общем случае, порождающей матрицей линейного ( n , k )-кода С называется любая k× n матрица G , строки которой образуют базис пространства C кодовых слов.
Пример 2. Дана проверочная матрица линейного (4,2)-кода над полем F3 = {0,1,2}.
Напомним, что поле F3 изоморфно полю классов вычетов по модулю 3, и поэтому 1+2=0 и -1=2, -2=1.
Скорость передачи данного кода k/n = 2/4 = ½
Матрица H имеет вид: H = . Найдём порождающую матрицу G по формуле .
|
|
, откуда .
Составим таблицу кодирования. Всего может быть 9 различных информационных сообщений (a1,a2): 00, 01, 02, 10, 11, 12, 20, 21, 22. Они записаны в первых двух столбцах таблицы. Соответствующие им кодовые векторы находим, умножая информационное сообщение на матрицу G:
(a1 a2) ∙ = (x1 x2 x3 x4)
Информ.сообщ. | Код С | ||||
a1 | a2 | x1 | x2 | x3 | x4 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 2 | 1 |
0 | 2 | 0 | 2 | 1 | 2 |
1 | 0 | 1 | 0 | 2 | 2 |
1 | 1 | 1 | 1 | 1 | 0 |
1 | 2 | 1 | 2 | 0 | 1 |
2 | 0 | 2 | 0 | 1 | 1 |
2 | 1 | 2 | 1 | 0 | 2 |
2 | 2 | 2 | 2 | 2 | 0 |
Аналогичные результаты можно получить, записав систему проверочных уравнений, определяемую матрицей Н, и учитывая, что , – информационные символы:
.
В качестве порождающей матрицы этого же кода можно взять матрицу G= , строки которой – линейно независимые векторы из С. При этом изменится соответствие между информационными сообщениями и кодовыми векторами, а множество кодовых векторов С будет таким же (проверьте самостоятельно).
Дата добавления: 2019-02-12; просмотров: 2105; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!