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

107 байт добавлено ,  8 лет назад
викификация
(викификация)
 
=== Коды обнаружения и исправления ошибок ===
Корректирующие коды  — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием [[помехи|помех]], а также при её хранении.
 
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную ''избыточную'' информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
 
== Формальное определение ==
'''Линейный код''' длины ''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>-битных [[вектор (математика)|вектор]]ов.
 
Это значит, что операция кодирования соответствует умножению исходного <math>k</math>-битного вектора на невырожденную [[матрица (математика)|матрицу]] <math>G</math>, называемую ''порождающей матрицей''.
 
Пусть <math>C^{\perp}</math> — [[ортогональное подпространство]] по отношению к <math>C</math>, а <math>H</math> — матрица, задающая [[базис]] этого подпространства. Тогда для любого вектора <math>\overrightarrow{v} \in C</math> справедливо:
 
== Свойства и важные теоремы ==
 
=== Минимальное расстояние и корректирующая способность ===
''[[Расстояние Хэмминга|Расстоянием Хемминга]]'' (''метрикой Хемминга'') между двумя кодовыми словами <math>\overrightarrow{v_1}</math> и <math>\overrightarrow{v_2}</math> называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе <math>\overrightarrow{v_1} \oplus \overrightarrow{v_2}</math>.
 
=== Код Рида-Маллера ===
[[{{не переведено 5|Код Рида-Маллера]]|Код [[:en:Рида-Маллера||Reed-Muller code]]}} — линейный двоичный блочный код. При определённом построении он может быть систематическим. В общем случае код Рида-Маллера не является циклическим. Коды Рида-Маллера задаются следующими параметрами для любых значений m и r, называемого порядком кода, меньшего, чем m:
— длина кодового слова n=2<sup>m</sup>;
— длина информационной части k=1+C<sub>m</sub><sup>1</sup>+…+C<sub>m</sub><sup>r</sup>;