Линейный код: различия между версиями

16 байт добавлено ,  6 лет назад
Нет описания правки
== Линейные пространства ==
 
=== Порождающая матрицакотоматрица ===
Пусть [[вектор (математика)|векторы]] <math>\overrightarrow{x_1} = (x_{11},..,x_{1n}), \overrightarrow{x_2} = (x_{21},..,x_{2n}),.., \overrightarrow{x_k} = (x_{k1},..,x_{kn})</math> являются [[базис]]ом линейного пространства <math>C</math>. По определению [[базис]]а, любой вектор <math>\overrightarrow{v} \in C</math> можно представить в виде линейной комбинации базисных векторов:
<math>\overrightarrow{v} = {c_1}\overrightarrow{x_1} + {c_2}\overrightarrow{x_2} + ... + {c_k}\overrightarrow{x_k}</math>,
и векторами <math>\overrightarrow{v} \in C</math>. Перечисляя все векторы коэффициентов <math>\overrightarrow{c} = ({c_1},{c_2},..,{c_k}) </math> можно получить все векторы <math>\overrightarrow{v} \in C</math>. Иными словами, матрица <math>G</math> порождает линейное пространство.
 
=== Проверочная матрицакотоматрица ===
Другим способом задания линейных пространств является описание через проверочную матрицу.
 
 
== Формальное определение ==
'''Линейный кодкот''' длины ''n'' и ранга ''k'' является линейным подпространством ''C'' размерности ''k'' векторного пространства <math>\mathbb{F}_q^n</math>, где <math>\mathbb{F}_q</math> — [[конечное поле]] из ''q'' элементов. Такой код с параметром q называется q-арным кодом (напр. если ''q'' = 5 — то это 5-арный код). Если ''q'' = 2 или ''q'' = 3, то код представляет собой '''двоичный код''', или '''тернарный''' соответственно.
 
'''Линейный (блоковый) код''' — такой код, что множество его ''кодовых слов'' образует <math>k</math>-мерное линейное подпространство (назовем его <math>C</math>) в <math>n</math>-мерном [[линейное пространство|линейном пространстве]], [[изоморфизм|изоморфное]] пространству <math>k</math>-битных [[вектор (математика)|вектор]]ов.
Если минимальное расстояние линейного (n, k)-кода равно d, то любые <math>l \leqslant d - 1</math> столбцов проверочной матрицы H линейно независимы и найдутся d линейно зависимых столбцов.
 
=== КодыКоты Хемминга ===
Исторически «коды Хемминга» должны называться кодами Р. Фишера - они были им представлены в 1942г (Fisher R.A. The theory of confouding in factor to thr theory).
[[Код Хемминга|Коды Хемминга]] — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что ''синдром''
будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.
 
=== КодКот Рида-Маллера ===
{{не переведено 5|Код Рида-Маллера|Код Рида-Маллера||Reed-Muller code}} — линейный двоичный блочный код. При определённом построении он может быть систематическим. В общем случае код Рида-Маллера не является циклическим. Коды Рида-Маллера задаются следующими параметрами для любых значений m и r, называемого порядком кода, меньшего, чем m:
— длина кодового слова n=2<sup>m</sup>;
{{заготовка раздела}}
 
=== Общий метод кодированиякотирования линейных кодовкотов ===
Линейный код длины n с k информационными символами является k-мерным линейным подпространством, поэтому каждое кодовое слово является ''линейной комбинацией'' базисных векторов <math>\overrightarrow{g_1} = (g_{11},..,g_{1n}), \overrightarrow{g_2} = (g_{21},..,g_{2n}),.., \overrightarrow{g_k} = (g_{k1},..,g_{kn})</math> подпространства:
 
Это соотношение есть '''правило кодирования''', по которому информационное слово <math>\overrightarrow{m} = ({m_1},..,{m_k})</math> отображается в кодовое <math>\overrightarrow{c} = ({c_1},..,{c_n})</math>
 
=== Общий метод обнаружения ошибок в линейном кодекоте ===
Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова <math>\overrightarrow{r_i}</math> соответствует наиболее вероятное переданное слово <math>\overrightarrow{u_i}</math>. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.
 
Анонимный участник