Изменения

|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>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=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>. == Минимальное расстояние и корректирующая способность == Линейность гарантирует, что [[Расстояние Хэмминга | расстояние Хэмминга]] <tex>d</tex> между кодовым словом <tex>c_0</tex> и любым другим кодовым словом <tex>c \neq c_0</tex> не зависит от <tex>c_0</tex>. Так как <tex>c - c_0</tex> {{---}} тоже кодовое слово, а <tex>d(c, c_0) = d(c - c_0, 0)</tex>, то :<tex>\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C,\ c \neq c_0}d(c-c_0, 0)=\min_{c \in C,\ c \neq 0}d(c, 0)=d.</tex> Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода. Минимальное расстояние кода <tex>d</tex> [[Избыточное кодирование, код Хэмминга#Определение и устранение ошибок в общем случае | однозначно определяет]] количество ошибок, которое способен обнаружить (<tex>[{{d-1}\over{2}}]</tex>) и исправить (<tex>d - 1</tex>) данный код.  == Синдромы и метод обнаружения ошибок в линейном коде == Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова <tex>\overrightarrow{r_i}</tex> соответствует наиболее вероятное переданное слово <tex>\overrightarrow{u_i}</tex>. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины. Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора <tex>\overrightarrow{r_i}</tex> вычисляется ''синдром'' <tex>\overrightarrow{s_i}=\overrightarrow{r_i} H^T</tex>. Поскольку <tex>\overrightarrow{r_i} = \overrightarrow{v_i} + \overrightarrow{e_i}</tex>, где <tex>\overrightarrow{v_i}</tex> — кодовое слово, а <tex>\overrightarrow{e_i}</tex> — вектор ошибки, то <tex>\overrightarrow{s_i}=\overrightarrow{e_i} H^T</tex>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода. == Преимущества и недостатки линейных кодов ==

* [https://scask.ru/h_book_tcod.php?id=9 3 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. {{---}} М: Связь, 1979. {{---}} 744 с., стр. 12-33]