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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Расстояние кода)
м (Fix определения порождающей матрицы)
 
(не показано 12 промежуточных версий этого же участника)
Строка 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#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).
  
 
== Формальное определение ==
 
== Формальное определение ==
Строка 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>.
  
 
== Минимальное расстояние и корректирующая способность ==
 
== Минимальное расстояние и корректирующая способность ==
Строка 37: Строка 118:
 
Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.
 
Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.
  
== Количество ошибок ==
+
Минимальное расстояние кода <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>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
 +
 
 +
== Преимущества и недостатки линейных кодов ==
 +
 
 +
+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
  
== Прочее ==
+
- Хотя линейные коды, как правило, хорошо справляются с редкими, но большими ''пачками ошибок'', их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.
  
 
== Примечания ==
 
== Примечания ==
Строка 48: Строка 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]. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

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

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

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

Примечания[править]

Источники информации[править]