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

16 байт добавлено ,  10 лет назад
отмена правки 29797303 участника 194.226.252.21 (обс) Таких кавычек нет.
(отмена правки 29797303 участника 194.226.252.21 (обс) Таких кавычек нет.)
 
== Основы ==
 
В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, [[физический уровень|физическом]], [[канальный уровень|канальном]], [[транспортный уровень|транспортном]] уровнях [[Модель 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> является важной характеристикой линейного блокового кода. Она определяет другую, не менее важную характеристику — ''[[корректирующая способность|корректирующую способность]]'':
 
=== Коды Хемминга ===
Исторически "«коды Хемминга"» должны называться кодами Р.Фишера и был представлен в 1942г (Fisher R.A. The theory of confouding in factor to thr theory).
[[Код Хемминга|Коды Хемминга]] — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что ''синдром''
 
 
=== Код Рида-Маллера ===
[[Код Рида-Маллера]] [en:Reed-Muller code] — линейный двоичный блочный код. При определенном построении он может быть систематическим. В общем случае код Рида-Маллера не является циклическим. Коды Рида-Маллера задаются следующими параметрами для любых значений m и r, называемого порядком кода, меньшего, чем m:
- длина кодового слова n=2m;
- длина информационной части k=1+Cm1+…+Cmr;
- длина проверочной части n-k=1+Cm1+…+Cmm-r-1;
- минимальное кодовое расстояние dmin=2m-r.
Код Рида-Маллера определяется при помощи порождающей матрицы, состоящей из базисных векторов. Строится по правилу:
- пусть V0 — вектор, все компоненты которого равны 1;
- пусть V1, V2,…, Vm — строки матрицы, столбцами которого являются все двоичные наборы длины m. Код Рида-Маллера r-го порядка содержит в качестве базиса векторы V0, V1,…, Vm и все компонентные произведения r или меньшего числа этих векторов.
 
{{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>. Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.
 
 
=== Коды БЧХ ===
 
[[Код Боуза-Чоудхури-Хоквингема|Коды Боуза-Чоудхури-Хоквингема]] (БЧХ) являются подклассом двоичных циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.
 
 
=== Коды Рида-Соломона ===
 
[[Код Рида-Соломона|Коды Рида-Соломона]] (РС-коды) фактически являются ''недвоичными'' кодами БЧХ, то есть элементы кодового вектора являются не битами, а группами битов. Очень распространены коды Рида-Соломона, работающие с [[байт]]ами ([[октет (информатика)|октетами]]).
 
== Преимущества и недостатки линейных кодов ==
 
+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
 
- Хотя линейные коды, как правило, хорошо справляются с редкими, но большими ''пачками ошибок'', их эффективность при частых, но небольших ошибках (например, в канале с [[АБГШ]]), менее высока.
 
== Оценка эффективности ==
 
=== Энергетический выигрыш ===
 
При передаче информации по каналу связи вероятность ошибки зависит от [[Отношение сигнал/шум|отношения сигнал/шум]] на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенных системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.
 
 
== Применение ==
 
Линейные коды применяются:
* в системах [[цифровая связь|цифровой связи]], в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам;
 
== См. также ==
 
* [[Циклический код]]
 
{{rq|source}}
 
[[Категория:Теория кодирования]]
35 984

правки