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>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>.
== Минимальное расстояние и корректирующая способность ==
