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

 

== Основы ==

В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, [[физический уровень|физическом]], [[канальный уровень|канальном]], [[транспортный уровень|транспортном]] уровнях [[Модель OSI|модели OSI]]).

 

 

=== Коды обнаружения и исправления ошибок ===

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием [[помехи|помех]], а также при её хранении.

 

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

 

 

=== Блоковые коды ===

Пусть кодируемая информация делится на фрагменты длиной <math>k</math> бит, которые преобразуются в ''кодовые слова'' длиной <math>n</math> бит. Тогда соответствующий блоковый код обычно обозначают <math>(n,k)</math>. При этом число <math>R = \frac{k}{n}</math> называется ''скоростью кода''.

 

 

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из <math>k</math> информационных бит сопоставляется <math>n</math> бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

* способность исправлять как можно большее число ошибок,

* как можно меньшая избыточность,

 

=== Порождающая матрица ===

Пусть [[вектор]]ы <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>,

 

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

Другим способом задания [[линейное пространство|линейных пространств]] является описание через проверочную матрицу.

 

 

== Формальное определение ==

'''Линейный код''' длины ''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>\overrightarrow{v_1}</math> и <math>\overrightarrow{v_2}</math> называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе <math>\overrightarrow{v_1} \oplus \overrightarrow{v_2}</math>.

 

Расстояние между двумя векторами <math>d(\overrightarrow{x}, \overrightarrow{y})</math> удовлетворяет равенству <math>d(\overrightarrow{x}, \overrightarrow{y}) = w(\overrightarrow{x} - \overrightarrow{y})</math>, где <math>w( \overrightarrow{t})</math> — вес Хемминга вектора <math>\overrightarrow{t}</math>. Из того, что разность любых двух кодовых слов линейного кода также является кодовым словом линейного кода, вытекает утверждение теоремы:

<math>d = \min_{\overrightarrow{c} \in C, \overrightarrow{c} \not = \overrightarrow{0}}w( \overrightarrow{c})</math>

 

''Минимальное расстояние Хемминга'' <math>d</math> является важной характеристикой линейного блокового кода. Она определяет другую, не менее важную характеристику — ''[[корректирующая способность|корректирующую способность]]'':

 

=== Коды Хемминга ===

[[Код Хемминга|Коды Хемминга]] — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что ''синдром''

 

 

=== Код Рида-Маллера ===

Код Рида-Маллера определяется при помощи порождающей матрицы, состоящей из базисных векторов. Строится по правилу:

 

{{sect-stub}}

 

=== Общий метод кодирования линейных кодов ===

Линейный код длины 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{r_i}</math> соответствует наиболее вероятное переданное слово <math>\overrightarrow{u_i}</math>. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

 

 

== Линейные циклические коды ==

Несмотря на то, что исправление ошибок в линейных кодах уже значительно проще исправления в большинстве нелинейных, для большинства кодов этот процесс все ещё достаточно сложен. [[Циклический код|Циклические коды]], кроме более простого декодирования, обладают и другими важными свойствами.

 

 

=== Порождающий полином ===

Можно показать, что все кодовые слова конкретного циклического кода кратны определенному ''порождающему полиному'' <math>g(x)</math>. Порождающий полином является делителем <math>x^n-1</math>.

 

 

=== Коды CRC ===

Коды [[CRC]] (cyclic redundancy check — циклическая избыточная проверка) являются ''систематическими'' кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления <math>x^{n-k} u(x)</math> на <math>g(x)</math>. Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

 

 

=== Коды БЧХ ===

[[Код Боуза-Чоудхури-Хоквингема|Коды Боуза-Чоудхури-Хоквингема]] (БЧХ) являются подклассом двоичных циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

 

 

=== Коды Рида-Соломона ===

[[Код Рида-Соломона|Коды Рида-Соломона]] (РС-коды) фактически являются ''недвоичными'' кодами БЧХ, то есть элементы кодового вектора являются не битами, а группами битов. Очень распространены коды Рида-Соломона, работающие с [[байт]]ами ([[октет (информатика)|октетами]]).

 

== Преимущества и недостатки линейных кодов ==

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

 

 

== Оценка эффективности ==

 

=== Энергетический выигрыш ===

При передаче информации по каналу связи вероятность ошибки зависит от [[Отношение сигнал/шум|отношения сигнал/шум]] на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенных системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

 

 

== Применение ==

Линейные коды применяются:

* в системах [[цифровая связь|цифровой связи]], в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам;

 

== См. также ==

* [[Циклический код]]

 

[[Категория:Теория кодирования]]