Участник:Terraqottik — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Изменены разделы, добавлены ссылки)
м (Fix определения порождающей матрицы)
 
(не показано 11 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition=Линейный код (англ. ''Linear code'') {{---}}  [[Кодирование информации#Код | код фиксированной длины]], исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.}}
+
|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>
+
Линейные коды обычно делят на [[Кодирование информации#Код | блоковые коды]] и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.<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#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).
 
По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. [[Участник:Terraqottik#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).
Строка 15: Строка 15:
 
Векторы в <tex>C</tex> называют '''кодовыми словами'''. Размер кода {{---}} это количество кодовых слов, т.е. <tex>\mathbb{q}^k</tex>.  
 
Векторы в <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'').  
+
'''Весом''' кодового слова называют число его ненулевых элементов. '''Расстояние''' между двумя кодовыми словами определяется как [[Расстояние Хэмминга | расстояние Хэмминга]]. Расстояние <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>\mathbb{F}_q^n</tex>, целиком код <tex>C</tex> (может быть очень большим) может быть представлен как линейная оболочка набора из <tex>k</tex> кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы <tex>G</tex> и называют такую матрицу '''порождающей матрицей''' кода <tex>C</tex>.  
Строка 28: Строка 34:
  
 
где <tex>w</tex> и <tex>s</tex> {{---}} векторы-строки. Порождающая матрица линейного <tex>[n, k, d]_q</tex>-кода имеет вид <tex>k \times n</tex>. Число избыточных бит тогда определяется как <tex>r = n - k</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>.
  
 
== Минимальное расстояние и корректирующая способность ==
 
== Минимальное расстояние и корректирующая способность ==
Строка 41: Строка 122:
 
== Синдромы и метод обнаружения ошибок в линейном коде ==
 
== Синдромы и метод обнаружения ошибок в линейном коде ==
  
 +
Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова <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>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
  
 
== Преимущества и недостатки линейных кодов ==
 
== Преимущества и недостатки линейных кодов ==
Строка 56: Строка 139:
 
* [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 wikipedia.org {{---}} Линейный код]
 
* [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 wikipedia.org {{---}} Линейный код]
 
* [https://en.wikipedia.org/wiki/Linear_code wikipedia.org {{---}} Linear code]
 
* [https://en.wikipedia.org/wiki/Linear_code wikipedia.org {{---}} Linear code]
* [https://scask.ru/h_book_tcod.php?id=9 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. {{---}} М: Связь, 1979. {{---}} 744 с., стр. 12-33]
+
* [https://scask.ru/h_book_tcod.php?id=3 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. {{---}} М: Связь, 1979. {{---}} 744 с., стр. 12-33]
 
* [http://cyber.sibsutis.ru:82/monarev/docs/nauka/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%9A%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/metodichka%201.pdf Ф.И. Соловьева {{---}} Введение в теорию кодирования]
 
* [http://cyber.sibsutis.ru:82/monarev/docs/nauka/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%9A%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/metodichka%201.pdf Ф.И. Соловьева {{---}} Введение в теорию кодирования]
 
* [https://mmf.bsu.by/wp-content/uploads/2016/10/Line_code_code_seq.pdf  В. А. Липницкий, Н. В. Чесалин {{---}} Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.]
 
* [https://mmf.bsu.by/wp-content/uploads/2016/10/Line_code_code_seq.pdf  В. А. Липницкий, Н. В. Чесалин {{---}} Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.]

Текущая версия на 10:18, 22 февраля 2021

Определение:
Линейный код (англ. Linear code) — код фиксированной длины (блоковый код), исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.


Линейные коды обычно делят на блоковые коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.[1]

По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. синдромы ошибок).

Формальное определение

Определение:
Линейный код длины [math]n[/math] и ранга [math]k[/math] является линейным подпространством [math]C[/math] размерности [math]k[/math] векторного пространства [math]\mathbb{F}_q^n[/math], где [math]\mathbb{F}_q[/math] — конечное поле (поле Галуа) из [math]q[/math] элементов. Такой код с параметром [math]q[/math] называется [math]q[/math]-арным кодом (напр. если [math]q = 5[/math] — то это 5-арный код). Если [math]q = 2[/math] или [math]q = 3[/math], то код представляет собой двоичный код, или тернарный соответственно.


Векторы в [math]C[/math] называют кодовыми словами. Размер кода — это количество кодовых слов, т.е. [math]\mathbb{q}^k[/math].

Весом кодового слова называют число его ненулевых элементов. Расстояние между двумя кодовыми словами определяется как расстояние Хэмминга. Расстояние [math]d[/math] линейного кода — это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов.

Линейный код длины [math]n[/math], ранга [math]k[/math] и с расстоянием [math]d[/math] называют [math][n,k,d]_q[/math]-кодом (англ. [n,k,d] code). Параметр d в обозначении кода часто опускается, потому что через него не задается структура кода. В таком случае пишут просто [math][n,k][/math]-код. В литературе встречается обозначение как в квадратных, так и в круглых скобках.[2][3]

Порождающая матрица

Определение:
Порождающая матрица — это матрица, столбцы которой задают базис линейного кода.


Так как линейный код является линейным подпространством [math]\mathbb{F}_q^n[/math], целиком код [math]C[/math] (может быть очень большим) может быть представлен как линейная оболочка набора из [math]k[/math] кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы [math]G[/math] и называют такую матрицу порождающей матрицей кода [math]C[/math].

В случае, если [math]\boldsymbol{G} = [I_k | P][/math], где [math]I_k[/math] — это единичная матрица размера [math]k[/math], а [math]P[/math] — это матрица размера [math]k \times (n - k)[/math] говорят, что матрица [math]G[/math] находится в каноническом виде.

Имея матрицу [math]G[/math] можно получить из некоторого входного вектора [math]s[/math] кодовое слово [math]w[/math] линейного кода [math]C[/math]

[math]w=sG[/math],

где [math]w[/math] и [math]s[/math] — векторы-строки. Порождающая матрица линейного [math][n, k, d]_q[/math]-кода имеет вид [math]k \times n[/math]. Число избыточных бит тогда определяется как [math]r = n - k[/math].

Проверочная матрица

Определение:
Проверочная матрица [math]H[/math] линейного кода [math]C[/math] — это порождающая матрица ортогонального дополнения [math]C^\perp[/math]. Другими словами, это матрица, которая описывает правила, которым должны удовлетворять части кодового слова.


Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).

Кодовое слово [math]c[/math] принадлежит коду [math]C[/math] тогда и только тогда, когда [math]Hc^\top = 0[/math] или, что то же самое, [math]cH^\top = 0[/math].

Проверочную матрицу можно получить из порождающей и наоборот: пусть дана порождающая матрица [math]G[/math] в каноническом виде [math]G = \begin{bmatrix} I_k | P \end{bmatrix}[/math], тогда проверочную матрицу [math]H[/math] можно получить по формуле

[math]H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix}[/math],

так как [math]G H^{\top} = P-P = 0[/math].

Кодирование и декодирование, примеры

Предположим, что имеется линия связи, по которой мы можем пересылать и принимать биты. В среднем какой-то известный процент переданных битов будет поврежден, ошибочен. Такая модель называется двоичным симметричным каналом.

Блок из [math]k[/math] символов сообщения [math]u = u_1u_2{\ldots}u_k, u_i \in \{0, 1\}[/math] будет кодироваться в кодовое слово [math]x = x_1x_2{\ldots}x_n, x_i \in \{0, 1\}[/math], где [math]n \gt = k[/math]; эти кодовые слова образуют код.

Первая часть кодового слова состоит из информационных битов сообщения:

[math]x_1 = u_1, x_2 = u_2, {\ldots}, x_k = u_k[/math],

за которым следуют [math]n - k[/math] проверочных битов [math]x_{k+1}, {\ldots}, x_n[/math]. Проверочные биты выбраны так, чтобы кодовые слова удовлетворяли уравнению

[math]\begin{equation*} H\left( \begin{array}{c} x_1\\ x_2\\ {\ldots}\\ x_n \end{array} \right) = Hx^{\top} = 0 \end{equation*}[/math],

где [math]H[/math] проверочная матрица.

Пример

Проверочная матрица

[math]\begin{equation*} H = \left[ \begin{array}{c|c} 011 & 100\\ 101 & 010\\ 110 & 001 \end{array} \right] \end{equation*}[/math]

определяет код с [math]k = 3[/math] и [math]n = 6[/math]. Для этого кода

[math]\begin{equation*} A = \left[ \begin{array}{c} 011\\ 101\\ 110 \end{array} \right] \end{equation*}[/math].

Сообщение [math]u_1u_2u_3[/math] кодируется в кодовое слово [math]x = x_1x_2x_3x_4x_5x_6[/math], которое начинается с самого сообщения:

[math]x_1 = u_1; x_2 = u_2; x_3 = u_3[/math],

а последующих три проверочных символа [math]x_4x_5x_6[/math] выбираются так, чтобы выполнялось уравнение [math]Hx^{\top} = 0[/math].

Если сообщение [math]u = 011[/math], то [math]x_1 = 0; x_2 = 1; x_3 = 1[/math], и проверочные биты легко определяются: [math]x_4 = 0; x_5 = 1; x_6 = 1[/math], так что кодовое слово [math]x = 011011[/math].

Минимальное расстояние и корректирующая способность

Линейность гарантирует, что расстояние Хэмминга [math]d[/math] между кодовым словом [math]c_0[/math] и любым другим кодовым словом [math]c \neq c_0[/math] не зависит от [math]c_0[/math]. Так как [math]c - c_0[/math] — тоже кодовое слово, а [math]d(c, c_0) = d(c - c_0, 0)[/math], то

[math]\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.[/math]

Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.

Минимальное расстояние кода [math]d[/math] однозначно определяет количество ошибок, которое способен обнаружить ([math][{{d-1}\over{2}}][/math]) и исправить ([math]d - 1[/math]) данный код.

Синдромы и метод обнаружения ошибок в линейном коде

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова [math]\overrightarrow{r_i}[/math] соответствует наиболее вероятное переданное слово [math]\overrightarrow{u_i}[/math]. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора [math]\overrightarrow{r_i}[/math] вычисляется синдром [math]\overrightarrow{s_i}=\overrightarrow{r_i} H^T[/math]. Поскольку [math]\overrightarrow{r_i} = \overrightarrow{v_i} + \overrightarrow{e_i}[/math], где [math]\overrightarrow{v_i}[/math] — кодовое слово, а [math]\overrightarrow{e_i}[/math] — вектор ошибки, то [math]\overrightarrow{s_i}=\overrightarrow{e_i} H^T[/math]. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Преимущества и недостатки линейных кодов

+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.

- Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Примечания

Источники информации