Матрица генератора

Для матриц генератора в теории вероятностей см. матрицу скорости перехода .

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

Терминология

Если G является матрицей, она генерирует кодовые слова линейного кода C по формуле

$w=sG$

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

Стандартная : форма порождающей матрицы

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

где $I_{k}$ это $k\times k$ единичная матрица и P представляет собой $k\times (n-k)$ матрица. Когда порождающая матрица имеет стандартную форму, код C является систематическим в своих первых k позициях координат.

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

$H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}$,

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

G представляет собой $k\times n$ матрица, а H является $(n-k)\times n$ матрица.

Эквивалентные коды

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

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

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

Матрицы-образующие эквивалентных кодов можно получить друг из друга с помощью следующих элементарных операций :

1. обмениваться строками
2. масштабировать строки ненулевым скаляром
3. добавить строки в другие строки
4. переставлять столбцы и
5. масштабировать столбцы с помощью ненулевого скаляра.

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

См. также

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

Ссылки

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

Дальнейшее чтение

• МакВильямс, ФДж ; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Северная Голландия, ISBN  0-444-85193-3

Внешние ссылки

• Матрица генератора в MathWorld