19
правок
Изменения
м
Fix определения порождающей матрицы
{{Определение
|id=def1
|definition=Линейный код (англ. ''Linear code'') {{---}} [[Кодирование информации#Код | код фиксированной длины(блоковый код)]], исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.}}
Линейные коды обычно делят на блочные [[Кодирование информации#Код | блоковые коды ]] и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.<ref>[https://archive.org/details/channelcodesclas00ryan/page/n21 William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.]</ref>
По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. [[Участник:Terraqottik#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).
Векторы в <tex>C</tex> называют '''кодовыми словами'''. Размер кода {{---}} это количество кодовых слов, т.е. <tex>\mathbb{q}^k</tex>.
'''Весом''' кодового слова называют число его ненулевых элементов. '''Расстояние''' между двумя кодовыми словами {{---}} это определяется как [[Расстояние Хэмминга | расстояние Хэмминга]]. Расстояние <tex>d</tex> линейного кода {{---}} это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов. Линейный код длины <tex>n</tex>, ранга <tex>k</tex> и с расстоянием <tex>d</tex> называют <tex>[n,k,d]_q</tex>-кодом (англ. ''[n,k,d] code''). Параметр d в обозначении кода часто опускается, потому что через него не задается структура кода. В таком случае пишут просто <tex>[n,k]</tex>-код. В литературе встречается обозначение как в квадратных, так и в круглых скобках.<ref>[https://mmf.bsu.by/wp-content/uploads/2016/10/Line_code_code_seq.pdf В. А. Липницкий, Н. В. Чесалин — Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с., стр. 6]</ref><ref>[https://scask.ru/h_book_tcod.php?id=2 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с., стр. 17]</ref>
== Порождающая матрица ==
{{Определение
|id=def2
|definition=Порождающая матрица {{---}} это матрица, столбцы которой задают базис линейного кода.}}
Так как линейный код является линейным подпространством <tex>\mathbb{F}_q^n</tex>, целиком код <tex>C</tex> (может быть очень большим) может быть представлен как линейная оболочка набора из <tex>k</tex> кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы <tex>G</tex> и называют такую матрицу '''порождающей матрицей''' кода <tex>C</tex>.
где <tex>w</tex> и <tex>s</tex> {{---}} векторы-строки. Порождающая матрица линейного <tex>[n, k, d]_q</tex>-кода имеет вид <tex>k \times n</tex>. Число избыточных бит тогда определяется как <tex>r = n - k</tex>.
== Проверочная матрица ==
{{Определение
|id=def3
|definition=Проверочная матрица <tex>H</tex> линейного кода <tex>C</tex> {{---}} это порождающая матрица ортогонального дополнения <tex>C^\perp</tex>. Другими словами, это матрица, которая описывает правила, которым должны удовлетворять части кодового слова.}}
Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).
Кодовое слово <tex>c</tex> принадлежит коду <tex>C</tex> тогда и только тогда, когда <tex>Hc^\top = 0</tex> или, что то же самое, <tex>cH^\top = 0</tex>.
Проверочную матрицу можно получить из порождающей и наоборот: пусть дана порождающая матрица <tex>G</tex> в каноническом виде <tex>G = \begin{bmatrix} I_k | P \end{bmatrix}</tex>, тогда проверочную матрицу <tex>H</tex> можно получить по формуле
: <tex>H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix}</tex>,
так как <tex>G H^{\top} = P-P = 0</tex>.
== Кодирование и декодирование, примеры ==
Предположим, что имеется линия связи, по которой мы можем пересылать и принимать биты. В среднем какой-то известный процент переданных битов будет поврежден, ошибочен. Такая модель называется ''двоичным симметричным каналом''.
Блок из <tex>k</tex> символов сообщения <tex>u = u_1u_2{\ldots}u_k, u_i \in \{0, 1\}</tex> будет кодироваться в ''кодовое слово'' <tex>x = x_1x_2{\ldots}x_n, x_i \in \{0, 1\}</tex>, где <tex>n >= k</tex>; эти кодовые слова образуют код.
Первая часть кодового слова состоит из информационных битов сообщения:
: <tex>x_1 = u_1, x_2 = u_2, {\ldots}, x_k = u_k</tex>,
за которым следуют <tex>n - k</tex> ''проверочных'' битов <tex>x_{k+1}, {\ldots}, x_n</tex>. Проверочные биты выбраны так, чтобы кодовые слова удовлетворяли уравнению
: <tex>\begin{equation*}
H\left(
\begin{array}{c}
x_1\\
x_2\\
{\ldots}\\
x_n
\end{array}
\right) = Hx^{\top} = 0
\end{equation*}</tex>,
где <tex>H</tex> {{---}} [[Участник:Terraqottik#Проверочная матрица | проверочная матрица]].
=== Пример ===
Проверочная матрица
: <tex>\begin{equation*}
H = \left[
\begin{array}{c|c}
011 & 100\\
101 & 010\\
110 & 001
\end{array}
\right]
\end{equation*}</tex>
определяет код с <tex>k = 3</tex> и <tex>n = 6</tex>. Для этого кода
<tex>\begin{equation*}
A = \left[
\begin{array}{c}
011\\
101\\
110
\end{array}
\right]
\end{equation*}</tex>.
Сообщение <tex>u_1u_2u_3</tex> кодируется в кодовое слово <tex>x = x_1x_2x_3x_4x_5x_6</tex>, которое начинается с самого сообщения:
: <tex>x_1 = u_1; x_2 = u_2; x_3 = u_3</tex>,
а последующих три проверочных символа <tex>x_4x_5x_6</tex> выбираются так, чтобы выполнялось уравнение <tex>Hx^{\top} = 0</tex>.
Если сообщение <tex>u = 011</tex>, то <tex>x_1 = 0; x_2 = 1; x_3 = 1</tex>, и проверочные биты легко определяются: <tex>x_4 = 0; x_5 = 1; x_6 = 1</tex>, так что кодовое слово <tex>x = 011011</tex>.
== Минимальное расстояние и корректирующая способность ==
