Генераторная матрица

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

Терминология [ править ]

Если G - матрица, она генерирует кодовые слова линейного кода C с помощью

{\ displaystyle w = sG}

где w - кодовое слово линейного кода C , а s - любой входной вектор. Предполагается, что как w, так и s являются векторами-строками. ^[1] Генераторная матрица для линейного кода имеет формат , где n - длина кодового слова, k - количество информационных битов (размерность C как векторного подпространства), d - минимальное расстояние кода, а q - размер конечного поля , то есть количество символов в алфавите (таким образом, q = 2 указывает на двоичный код ${\ displaystyle [п, к, d] _ {q}}$ ${\ Displaystyle к \ раз п}$ , так далее.). Количество избыточных битов обозначено . ${\ displaystyle r = nk}$

Стандартная форма для порождающей матрицы есть, ^[2]

{\ Displaystyle G = {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}

,

где - единичная матрица, а P - матрица. Когда матрица генератора имеет стандартную форму, код C является систематическим в своих первых k координатах. ^[3] ${\ displaystyle I_ {k}}$ ${\ Displaystyle к \ раз к}$ ${\ Displaystyle к \ раз (нк)}$

Генераторную матрицу можно использовать для построения матрицы проверки на четность для кода (и наоборот). Если порождающая матрица G имеет стандартную форму, то матрица проверки на четность для C имеет вид ^[4] ${\ Displaystyle G = {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}$

{\ displaystyle H = {\ begin {bmatrix} -P ^ {\ top} | I_ {nk} \ end {bmatrix}}}

,

где является транспонированной матрицы . Это является следствием того факта, что матрица проверки на четность является образующей матрицей двойного кода . ${\ displaystyle P ^ {\ top}}$ ${\ displaystyle P}$ ${\ displaystyle C}$ ${\ displaystyle C ^ {\ perp}}$

G - матрица, а H - матрица. ${\ Displaystyle к \ раз п}$ ${\ Displaystyle (нк) \ раз п}$

Эквивалентные коды [ править ]

Коды C ₁ и C ₂ являются эквивалентом (обозначается С ₁ ~ С ₂ ) , если один код может быть получен из другого с помощью следующих двух преобразований: ^[5]

произвольно переставлять компоненты, и
самостоятельно масштабировать ненулевым элементом любые компоненты.

Эквивалентные коды имеют одинаковое минимальное расстояние.

Образующие матрицы эквивалентных кодов могут быть получены друг из друга с помощью следующих элементарных операций : ^[6]

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

Таким образом, мы можем выполнять Гаусс на G . Действительно, это позволяет предположить, что образующая матрица имеет стандартный вид. Точнее, для любой матрицы G мы можем найти обратимую матрицу U такую, что , где G и генерируют эквивалентные коды. ${\ displaystyle UG = {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}$ ${\ displaystyle {\ begin {bmatrix} I_ {k} | P \ end {bmatrix}}}$

См. Также [ править ]

Код Хэмминга (7,4)

Заметки [ править ]

^ Маккей, Дэвид, JC (2003). Теория информации, выводы и алгоритмы обучения (PDF) . Издательство Кембриджского университета . п. 9. ISBN 9780521642989. Поскольку код Хэмминга является линейным кодом, его можно компактно записать в терминах матриц следующим образом. Переданное кодовое слово получается из исходной последовательности с помощью линейной операции, $\mathbf {t}$ $\mathbf {s}$
$\mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s}$
где - порождающая матрица кода ... Я предположил, что и являются векторами-столбцами. Если вместо этого они являются векторами-строками, тогда это уравнение заменяется на $\mathbf {G}$ $\mathbf {s}$ $\mathbf {t}$
$\mathbf {t} =\mathbf {sG}$
... Мне легче относиться к правому умножению (...), чем к левому умножению (...). Однако во многих текстах по теории кодирования используются правила умножения слева (...). ... Строки порождающей матрицы можно рассматривать как определяющие базисные векторы.
Перейти ↑ Ling & Xing 2004 , p. 52
↑ Роман 1992 , стр. 198
↑ Роман 1992 , стр. 200
^ Плесс 1998 , стр. 8
Перейти ↑ Welsh 1988 , pp. 54-55

Ссылки [ править ]

Линг, Сан; Xing, Chaoping (2004), Теория кодирования / Первый курс , Cambridge University Press, ISBN 0-521-52923-9
Плесс, Вера (1998), Введение в теорию кодов с исправлением ошибок (3-е изд.), Wiley Interscience, ISBN 0-471-19047-0
Роман, Стивен (1992), теория кодирования и информации , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
Валлийский, Доминик (1988), Коды и криптография , Oxford University Press, ISBN 0-19-853287-3

Дальнейшее чтение [ править ]

MacWilliams, FJ ; Sloane, NJA (1977), Теория кодов с исправлением ошибок , Северная Голландия, ISBN 0-444-85193-3

Внешние ссылки [ править ]

Генератор матрицы в MathWorld

[DrMacKayECC-1] Маккей, Дэвид, JC (2003). Теория информации, выводы и алгоритмы обучения (PDF) . Издательство Кембриджского университета . п. 9. ISBN 9780521642989. Поскольку код Хэмминга является линейным кодом, его можно компактно записать в терминах матриц следующим образом. Переданное кодовое слово получается из исходной последовательности с помощью линейной операции, $\mathbf {t}$ $\mathbf {s}$
$\mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s}$
где - порождающая матрица кода ... Я предположил, что и являются векторами-столбцами. Если вместо этого они являются векторами-строками, тогда это уравнение заменяется на $\mathbf {G}$ $\mathbf {s}$ $\mathbf {t}$
$\mathbf {t} =\mathbf {sG}$
... Мне легче относиться к правому умножению (...), чем к левому умножению (...). Однако во многих текстах по теории кодирования используются правила умножения слева (...). ... Строки порождающей матрицы можно рассматривать как определяющие базисные векторы.

[2] Перейти ↑ Ling & Xing 2004 , p. 52

[3] Роман 1992 , стр. 198

[4] Роман 1992 , стр. 200

[5] Плесс 1998 , стр. 8

[6] Перейти ↑ Welsh 1988 , pp. 54-55

[1]