Просмотр кода страницы Корректирующий код

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

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

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

По способу работы с данными коды, исправляющие ошибки, делятся на блоковые{{Переход|#Блоковые коды}}, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные{{Переход|#Свёрточные коды}}, работающие с данными как с непрерывным потоком.

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

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

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

=== Линейные коды общего вида ===
{{main|Линейный код}}
Линейный блоковый код — такой код, что множество его кодовых слов образует <math>k</math>-мерное линейное подпространство <math>C</math> в <math>n</math>-мерном [[линейное пространство|линейном пространстве]], [[изоморфизм|изоморфное]] пространству <math>k</math>-битных [[Вектор (математика)|векторов]].

Это значит, что операция кодирования соответствует умножению исходного <math>k</math>-битного вектора на невырожденную [[Матрица (математика)|матрицу]] <math>G</math>, называемую порождающей матрицей.

Для [[ортогональное подпространство|ортогонального]] по отношению к <math>C</math> подпространства <math>C^{\perp}</math> и матрицы <math>H</math>, задающей [[базис]] этого подпространства, и для любого вектора <math>\overrightarrow{v}\in C</math> справедливо:
: <math>\overrightarrow{v}H^T=\overrightarrow{0}</math>.

==== Минимальное расстояние и корректирующая способность ====
{{main|Расстояние Хэмминга}}
Расстоянием Хэмминга (метрикой Хэмминга) между двумя кодовыми словами <math>\overrightarrow{u}</math> и <math>\overrightarrow{v}</math> называется количество отличных бит на соответствующих позициях:

: <math>d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}</math>.

Минимальное расстояние Хэмминга <math>d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})</math> является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — [[Корректирующая способность|корректирующую способность]]:

: <math>t=\left\lfloor\frac{d_\min-1}{2}\right\rfloor</math>.

[[Корректирующая способность]] определяет, сколько ошибок передачи кода (типа <math>1\leftrightarrow 0</math>) можно гарантированно исправить. То есть вокруг каждого кодового слова <math>A</math> имеем [[ε-окрестность|<math>t</math>-окрестность]] <math>A_t</math>, которая состоит из всех возможных вариантов передачи кодового слова <math>A</math> с числом ошибок (<math>1\leftrightarrow 0</math>) не более <math>t</math>. Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их ''радиусов'' <math>d_H(A,\;B)\geqslant d_\min>2t</math>.

Таким образом, получив искажённую кодовую комбинацию из <math>A_t</math>, декодер принимает решение, что исходной была кодовая комбинация <math>A</math>, исправляя тем самым не более <math>t</math> ошибок.

Например, при наличии всего двух кодовых слов <math>A</math> и <math>B</math> с расстоянием Хэмминга между ними, равным 3, ошибка в одном бите слова <math>A</math> может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову <math>A</math>, чем к <math>B</math>. Но если каналом были внесены ошибки в двух битах (в которых <math>A</math> отличалось от <math>B</math>), то результат ошибочной передачи <math>A</math> окажется ближе к <math>B</math>, чем <math>A</math>, и декодер примет решение, что передавалось слово <math>B</math>.

==== Коды Хэмминга ====
{{main|Код Хэмминга}}
Коды Хэмминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хэмминга может быть представлен в таком виде, что синдром:
: <math>\overrightarrow{s}=\overrightarrow{r}H^T</math>, 
где <math>\overrightarrow{r}</math> — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

==== Общий метод декодирования линейных кодов ====
Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова <math>\overrightarrow{r}_i</math> соответствует наиболее вероятное переданное слово <math>\overrightarrow{u}_i</math>. Однако данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора <math>\overrightarrow{r}_i</math> вычисляется ''синдром'' <math>\overrightarrow{s}_i=\overrightarrow{r}_i H^T</math>. Поскольку <math>\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i</math>, где <math>\overrightarrow{v}_i</math> — кодовое слово, а <math>\overrightarrow{e}_i</math> — вектор ошибки, то <math>\overrightarrow{s}_i=\overrightarrow{e}_i H^T</math>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

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

Циклическим кодом является [[линейный код]], обладающий следующим свойством: если <math>\overrightarrow{v}</math> является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово <math>\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})</math> представляется в виде полинома <math>v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}</math>. При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на <math>x</math> [[сравнение по модулю|по модулю]] <math>x^n-1</math>.

Чаще всего используются двоичные циклические коды (то есть <math>v_0,\;v_1,\;\ldots</math> могут принимать значения 0 или 1).

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

С помощью порождающего многочлена осуществляется кодирование циклическим кодом. В частности:
* ''несистематическое кодирование'' осуществляется путём умножения кодируемого вектора на <math>g(x)</math>: <math>v(x)=u(x)g(x)</math>;
* ''систематическое кодирование'' осуществляется путём «дописывания» к кодируемому слову остатка от деления <math>x^{n-k}u(x)</math> на <math>g(x)</math>, то есть <math>v(x)=x^{n-k}u(x)+[x^{n-k}u(x)\,\bmod\,g(x)]</math>.

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

Таким образом, вид многочлена <math>g(x)</math> задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

{|class="wikitable"
!Название кода
!Степень
!Полином
|-
|CRC-12
|12
|<math>x^{12}+x^{11}+x^{3}+x^{2}+x+1</math>
|-
|CRC-16
|16
|<math>x^{16}+x^{15}+x^{2}+1</math>
|-
|CRC-[[CCITT]]
|16
|<math>x^{16}+x^{12}+x^{5}+1</math>
|-
|CRC-32
|32
|<math>x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1</math>
|}

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

==== Коды коррекции ошибок Рида — Соломона ====
{{main|Код Рида — Соломона}}
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с [[байт]]ами ([[октет (информатика)|октетами]]).

Математически коды Рида — Соломона являются кодами [[Код Боуза — Чоудхури — Хоквингема|БЧХ]].

=== Преимущества и недостатки блоковых кодов ===
Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими ''пачками ошибок'', их эффективность при частых, но небольших ошибках (например, в канале с [[Аддитивный белый гауссовский шум|АБГШ]]), менее высока.

== Свёрточные коды ==
{{main|Свёрточный код}}
[[Файл:ECC NASA standard coder.svg|350px|thumb|right|Свёрточный кодер (<math>k=7,\;R=1/2</math>)]]

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

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

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

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

== Каскадное кодирование. Итеративное декодирование ==
{{Якорь|Каскадное кодирование}}Преимущества разных способов кодирования можно объединить, применив '''''каскадное кодирование'''''. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается ''код-произведение''.

Например, популярной является следующая конструкция: данные кодируются кодом Рида — Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят [[турбо-код]]ы и [[LDPC-код]]ы (коды Галлагера).

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

=== Граница Хэмминга и совершенные коды ===
{{main|Граница Хэмминга}}
Пусть имеется двоичный блоковый <math>(n,k)</math> код с [[Корректирующая способность|корректирующей способностью]] <math>t</math>. Тогда справедливо неравенство (называемое границей Хэмминга):
: <math>\sum_{i=0}^t {n\choose i}\leqslant 2^{n-k}.</math>
Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, [[код Хэмминга|коды Хэмминга]]. Часто применяемые на практике коды с большой [[Корректирующая способность|корректирующей способностью]] (такие, как [[Код Рида — Соломона|коды Рида — Соломона]]) не являются совершенными.

== Литература ==
{{викиучебник|Помехоустойчивое кодирование}}
* {{Книга:Блейхут Р.: Теория и практика кодов}}
* Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
* {{Книга:Морелос-Сарагоса Р.: Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение}}

[[Категория:Кибернетика]]
[[Категория:Теория кодирования]]
[[Категория:Обнаружение и устранение ошибок]]