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

37 байт убрано ,  10 лет назад
викификация, орфография с помощью AWB
(викификация, орфография с помощью AWB)
 
=== Коды обнаружения и исправления ошибок ===
Корректирующие коды  — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием [[помехи|помех]], а также при её хранении.
 
Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную ''избыточную'' информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
* простота кодирования и декодирования.
 
Нетрудно видеть, что приведенныеприведённые требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.
 
Практически все используемые коды являются [[линейное отображение|линейными]]. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую легкость кодирования и декодирования.
 
== Линейные пространства ==
 
=== Порождающая матрица ===
Пусть [[вектор]]ы <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>\mathbb{C}</math> — линейное k-мерное пространство над полем <math>\mathbb{F}_q</math> и <math>\mathbb{W}</math> — ортогональное дополнение <math>\mathbb{C}</math>. Тогда по одной из теорем линейной алгебры, размерность <math>\mathbb{W}</math> равна <math>r = n - k</math>. Поэтому в <math>\mathbb{W}</math> существует r [[базис]]ных [[Вектор_Вектор (математика)|векторов]]. Пусть <math>\overrightarrow{h}_1 = ({{h_1}_1},...,{{h_1}_n}), \overrightarrow{h}_2 = ({{h_2}_1},...,{{h_2}_n}),..., \overrightarrow{h}_r = ({{h_r}_1},...,{{h_r}_n})
</math> [[базис]] в <math>\mathbb{W}</math>.
 
Тогда любой [[Вектор_Вектор (математика)|вектор]] <math>\overrightarrow{v} \in C</math> удовлетворяет следующей [[Система линейных уравнений|системе линейных уравнений]]:
 
<math>
 
== Формальное определение ==
'''Линейный код''' длины ''n'' и ранга ''k'' является линейным подпространством ''C'' размерности ''k'' векторного пространства <math>\mathbb{F}_q^n</math>, где <math>\mathbb{F}_q</math> — конечномерное поле из ''q'' элементов. Такой код с параметром q называется q-арным кодом (напр. если ''q''&nbsp; =&nbsp; 5 — то это 5-арный код). Если ''q''&nbsp; =&nbsp; 2 или ''q''&nbsp; =&nbsp; 3, то код представляет собой '''двоичный код''', или '''тернарный''' соответственно.
 
'''Линейный (блоковый) код''' — такой код, что множество его ''кодовых слов'' образует <math>k</math>-мерное линейное подпространство (назовем его <math>C</math>) в <math>n</math>-мерном [[линейное пространство|линейном пространстве]], [[изоморфизм|изоморфное]] пространству <math>k</math>-битных [[вектор]]ов.
 
== Свойства и важные теоремы ==
 
=== Минимальное расстояние и корректирующая способность ===
''[[Расстояние_ХэммингаРасстояние Хэмминга|Расстоянием Хемминга]]'' (''метрикой Хемминга'') между двумя кодовыми словами <math>\overrightarrow{v_1}</math> и <math>\overrightarrow{v_2}</math> называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе <math>\overrightarrow{v_1} \oplus \overrightarrow{v_2}</math>.
 
''Минимальное расстояние '' <math>d</math> линейного кода является минимальным из всех [[Расстояние Хэмминга|расстояний Хемминга]] всех пар кодовых слов.
Корректирующая способность определяет, какое максимальное число ошибок в одном кодовом слове код может ''гарантированно'' исправить.
 
Поясним на примере. Предположим, что есть два кодовых слова A и B, расстояние Хемминга между ними равно 3. Если было передано слово A, и канал внесвнёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову A, чем B. Но если каналом были внесены ошибки в двух битах, декодер может посчитать, что было передано слово B.
 
Число обнаруживаемых ошибок — число ошибок, при котором код может судить об ошибочной ситуации. Это число равно
 
=== Код Рида-Маллера ===
[[Код Рида-Маллера]] [[: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>;
 
=== Порождающий полином ===
Можно показать, что все кодовые слова конкретного циклического кода кратны определенномуопределённому ''порождающему полиному'' <math>g(x)</math>. Порождающий полином является делителем <math>x^n-1</math>.
 
С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:
Коды [[CRC]] (cyclic redundancy check — циклическая избыточная проверка) являются ''систематическими'' кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления <math>x^{n-k} u(x)</math> на <math>g(x)</math>. Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.
 
Таким образом, вид полинома g(x) задаетзадаёт конкретный код CRC. Примеры наиболее популярных полиномов:
 
{|border
 
=== Энергетический выигрыш ===
При передаче информации по каналу связи вероятность ошибки зависит от [[Отношение сигнал/шум|отношения сигнал/шум]] на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенныхопределённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.
 
Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.