Участник:Terraqottik - История изменений

Terraqottik: Fix определения порождающей матрицы

2021-02-22T07:18:10Z

Fix определения порождающей матрицы

Terraqottik: Добавление информации об обозначении кода

2021-02-22T07:15:55Z

Добавление информации об обозначении кода

Terraqottik: Определение расстояния между двумя кодовыми словами

2021-02-21T10:39:23Z

Определение расстояния между двумя кодовыми словами

Terraqottik: Блочные коды -> блоковые коды

2021-02-21T10:36:22Z

Блочные коды -> блоковые коды

Terraqottik: /* Кодирование и декодирование, примеры */

2021-02-18T07:54:38Z

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

Terraqottik: /* Кодирование и декодирование, примеры */

2021-02-18T07:34:24Z

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

Terraqottik: /* Проверочная матрица */

2021-02-18T07:05:17Z

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

Terraqottik: Добавлена информация о проверочной матрице

2021-02-18T07:04:36Z

Добавлена информация о проверочной матрице

Terraqottik: Добавлены ссылки

2021-02-18T06:41:26Z

Добавлены ссылки

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

2021-02-18T06:34:07Z

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

@@ Строка 23: / Строка 23: @@
 {{Определение
 |id=def2
-|definition=Порождающая матрица {{---}} это матрица, чьи столбцы формируют базис линейного кода.}}
+|definition=Порождающая матрица {{---}} это матрица, столбцы которой задают базис линейного кода.}}
 Так как линейный код является линейным подпространством <tex>\mathbb{F}_q^n</tex>, целиком код <tex>C</tex> (может быть очень большим) может быть представлен как линейная оболочка набора из <tex>k</tex> кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы <tex>G</tex> и называют такую матрицу '''порождающей матрицей''' кода <tex>C</tex>.

@@ Строка 15: / Строка 15: @@
 Векторы в <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> линейного кода {{---}} это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов.
 == Порождающая матрица ==

@@ Строка 15: / Строка 15: @@
 Векторы в <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'').
 == Порождающая матрица ==

@@ Строка 1: / Строка 1: @@
 {{Определение
 |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#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).

← Предыдущая		Версия 07:54, 18 февраля 2021
Строка 73:		Строка 73:

	где <tex>H</tex> {{---}} [[Участник:Terraqottik#Проверочная матрица \| проверочная матрица]].		где <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>.

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

@@ Строка 49: / Строка 49: @@
 так как <tex>G H^{\top} = P-P = 0</tex>.
 == Кодирование и декодирование, примеры ==
 == Минимальное расстояние и корректирующая способность ==

@@ Строка 41: / Строка 41: @@
 Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).
-Кодовое слово <tex>c</tex> принадлежит коду <tex>C</tex> тогда и только тогда, когда <tex>Hc^T = 0</tex> или, что то же самое, <tex>cH^T = 0</tex>.
+Кодовое слово <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> можно получить по формуле

@@ Строка 43: / Строка 43: @@
 Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова <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> — кодовое слово, а <matexh>\overrightarrow{e_i}</tex> — вектор ошибки, то <tex>\overrightarrow{s_i}=\overrightarrow{e_i} H^T</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>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
 == Преимущества и недостатки линейных кодов ==