Какими помехозащитными свойствами обладает инверсный код
Помехозащищенными, или корректирующими, кодами называются коды, позволяющие обнаружить или обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и деление этих кодов на две группы: коды с обнаружением ошибок и коды с обнаружением и исправлением ошибок.
Принципы обнаружения и исправления ошибок кодами хорошо иллюстрируются при помощи геометрических моделей. Любой n-элементный двоичный код можно представить с помощью n-мерного куба, в котором каждая вершина отображает кодовую комбинацию, а длина ребра куба соответствует одной единице. В таком кубе расстояния между вершинами (кодовыми комбинациями) измеряется минимальным количеством ребер, находящихся между ними, обозначается буквой d и называется кодовым расстоянием.
Так
им образом, кодовое расстояние – это то минимальное число элементов, в которых одна кодовая комбинация отличается от другой.
При n=1 n-мерный куб превращается в прямую длиной d=1, на одном конце которой располагается 1, а на другом 0. (n – число разрядов)
При n=2 имеем четыре возможные комбинации (N= 22 =4), которые располагаются на четырех вершинах квадрата. При этом комбинации 00 и 11, а также 10 и 01 отличаются друг от друга в двух разрядах, т.е. d =2.
Кодовое расстояние между двумя комбинациями двоичного кода равно числу единиц, полученных при сложении этих комбинаций по модулю 2, например, 10 01 = 11 и 00 11 = 11. Такое определение кодового расстояния удобно при большой разрядности кодов. Так, складывая комбинации 10110101101
10000000010
00110101111
мы определяем, что расстояние между ними d=7.
Для кода с n=3 восемь кодовых комбинаций размещаются на вершинах трехмерного куба. Этот куб строится так, что одна из его вершин лежит в начале координат. Каждой вершине куба приписывается кодовая комбинация по следующему правилу: на i-ом месте кодовой комбинации ставится 0, если проекция этой вершины на i-ую ось координат равна 0, и 1, если проекция равна 1. Например, мы хотим узнать, какую следует записать комбинацию в вершине А6. Проектируя эту вершину на ось X1, мы получим единицу.
На втором месте комбинации запишется также 1 (проекция на ось X2 равна единице). Т.к. проекция на ось X3 равна нулю (проекция в начале координат), то на третьем месте комбинации запишется 0. Вся комбинация в точке А6 – 110. Если использовать все восемь слов, то образуется двоичный код на все сочетания. Как было показано выше, такой код непомехоустойчив. Если же уменьшить число используемых комбинаций с 8 до 4, то появится возможность обнаружения одиночных ошибок. Для этого выберем только такие комбинации, которые отстоят друг от друга на расстоянии d=2, например, А0 А6 А3 А5
000 110 011 101
Если будет принята комбинация 100, отстоящая от комбинации 000, 110 и 101 на расстоянии d=1, то очевидно, что при приеме такой комбинации произошла одиночная ошибка.
Представленные комбинации построены по определенному правилу, а именно содержат четное число единиц, а принятая комбинация 100-нечетное. Можно утверждать, что комбинация 100 образовалась при искажении одного разряда одной из разрешенных комбинаций, но определить, какая именно комбинация искажена, невозможно. Поэтому такие коды называются кодами с обнаружением ошибок.
Кроме указанной выше группы комбинаций, в кубе можно найти еще одну группу комбинаций с кодовым расстоянием d=2 А7 А1 А2 А4
(111 001 010 100)
В этих кодовых комбинациях нечетное число единиц и каждая из них может быть использована для обнаружения ошибки, возникшей при передаче, т.к. при одиночном искажении в комбинации будет четное число единиц. Однако если мы хотим получить код с обнаружением одиночной ошибки, то в передаче в передаче может участвовать только одна группа, т.е. четыре комбинации из возможных 8. В противном случае мы придем к непомехоустойчивому коду, в котором будут встречаться комбинации с d=1.
Таким образом, в помехозащищенных кодах есть комбинации разрешенные, составленные по определенному правилу и есть комбинации запрещенные, не соответствующие этому правилу. Так, если из восьми комбинаций трехразрядного кода мы образовали четыре комбинации, позволяющие обнаруживать одиночную ошибку (например, 111, 001, 010 и 100), то эти комбинации будут разрешенными, а остальные четыре (000, 011, 101, 110) являются запрещенными и должны фиксироваться на приеме как искаженные. Иногда совокупность разрешенных кодовых комбинаций, которые при заданных возможных искажениях не могут перейти друг в друга, называют системой непереходящих друг в друга сигналов.
Построение помехоустойчивого кода связано с недоиспользованием кодовых комбинаций, приводящим к так называемой избыточности. Избыточность означает, что из исходных символов можно построить больше комбинаций, чем их используется в данном коде. Если еще больше ограничить число разрешенных комбинаций, то можно создать код и с исправлением ошибок.
Выберем в трехмерном кубе такие вершины, кодовые обозначения которых отличались бы друг от друга на d=3. Такие вершины расположены на концах пространственных диагоналей куба. Их может быть только четыре пары: 000 и 111 или 001 и 110, или 100 и 011, или 010 и 101. Однако из этих четырех пар для передачи можно использовать только одну любую пару, т.к. использование большего числа пар приведет к тому, что в передаче будут использоваться комбинации, отличающиеся друг от друга на d<3.
Код, образованный по такому правилу и состоящий в данном случае из двух комбинаций, может исправить одиночную ошибку или обнаруживать две ошибки без возможности их исправления.
Пусть, например, передается код, состоящий из слов 001 и 110. На приеме получена комбинация 100. Сравнение ее с исходными комбинациями показывает, что от комбинации 110 она отличается в одном (втором) разряде, а от комбинации 001 в двух разрядах. Если считать, что сделана одна ошибка, то полученную комбинацию 100 следует исправить на 110.
От разрешенной комбинации 001 отличаются на d=1 комбинации 011, 000 и 101, а от комбинации 110 – комбинации 111, 100 и 010. Они и являются своего рода комбинациями – спутниками, которые после приема можно относить к той или иной исходной комбинации.
Когда мы говорим об исправлении одиночной ошибки, то считаем, что вероятность двойной ошибки в канале связи пренебрежимо мала. Если такая вероятность достаточно велика, то код с d=3 можно использовать для обнаружения двойных ошибок, но при этом он уже исправлять одиночную ошибку не может. Действительно, если в нашем примере была принята комбинация 100, то уже нельзя утверждать, что была передана комбинация 110, т.к. при двойных ошибках это могла быть и искаженная комбинация 001.
Таким образом, дальнейшее повышение помехоустойчивости кода связано с увеличением кодового расстояния d, а это приводит к увеличению избыточности (вместо восьми комбинаций в нашем примере используются уже только две).
Корректирующая способность кода тесно связана с кодовым расстоянием:
а) при d =1 ошибка не обнаруживается;
б) при d =2 обнаруживаются одиночные ошибки;
в) при d =3 исправляются одиночные ошибки или обнаруживаются двойные.
В общем случае d=r+s+1, (3-5)
где d – минимальное кодовое расстояние;
r – число обнаруживаемых ошибок в слове;
s – число исправляемых ошибок в слове.
При этом обязательным условием является . Если r=s, то код обнаруживает 2x или исправляет x ошибок. Так в нашем примере d=3, и если r=s=1, то код может обнаружить одну ошибку и исправить ее, т.е. x=1. Если r=2, s=0, то код может обнаружить только две ошибки. Как следует из уравнения (3-5), для того чтобы код мог исправить одну ошибку и обнаружить две, необходимо, чтобы d=2+1+1=4. При том же d=4 может быть и вариант, когда r=3, s=0. Если d=5, то могут быть уже три варианта: r= s=2; r=3, s=1; r=4, s=0.
Если код только обнаруживает ошибки, то d=r+1, т.е. r=d – 1 (3-6)
Если код только исправляет ошибки, то d=2s+1, т.е. 
(3-7)
Итак, использование геометрических моделей позволяет просто строить малоразрядные корректирующие коды. Однако при длине кода n > 3 трудно уже воспользоваться геометрической моделью, т.к. такая модель должна быть многомерной. Если еще для n=4 можно вычертить четырехмерный “куб”, так называемый гиперкуб, то для n >4 это практически сделать невозможно. Поэтому для построения многоразрядных помехоустойчивых кодов используются различные правила и методики, к рассмотрению которых мы и перейдем.
Источник
Корректирующий код (также помехоустойчивый код) — код, предназначенный для обнаружения и исправления ошибок.
Основная техника — добавление при записи (передаче) в полезные данные специальным образом структурированной избыточной информации (например, контрольного числа), а при чтении (приёме) использование такой избыточной информации для обнаружения и исправления ошибки. Число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
Коды обнаружения ошибок (которые могут только установить факт ошибки) принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить бо́льшее число ошибок, чем был способен исправить). Коды, исправляющие ошибки, применяются в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам, а также в системах хранения информации, в том числе магнитных и оптических. Коды, обнаруживающие ошибки, применяются в сетевых протоколах различных уровней.
По способу работы с данными коды, исправляющие ошибки, делятся на блоковые[⇨], делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные[⇨], работающие с данными как с непрерывным потоком.
Блоковые коды[править | править код]
Блоковый код, разбивающий информацию на фрагменты длиной бит и преобразующий их в кодовые слова длиной бит обычно обозначают ; при этом число называется скоростью кода. Если исходные бит код оставляет неизменными, и добавляет проверочных, такой код называется систематическим, иначе — несистематическим.
Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из информационных бит сопоставляется бит кодового слова. Однако хороший код должен удовлетворять как минимум следующим критериям:
- способность исправлять как можно большее число ошибок,
- как можно меньшая избыточность,
- простота кодирования и декодирования.
Приведённые требования в общем случае противоречат друг другу, поэтому существует большое количество кодов, каждый из которых пригоден для определённого круга задач. Практически все используемые коды являются линейными, это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования.
Линейные коды общего вида[править | править код]
Линейный блоковый код — такой код, что множество его кодовых слов образует -мерное линейное подпространство в -мерном линейном пространстве, изоморфное пространству -битных векторов.
Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.
Для ортогонального по отношению к подпространства и матрицы , задающей базис этого подпространства, и для любого вектора справедливо:
.
Минимальное расстояние и корректирующая способность[править | править код]
Расстоянием Хэмминга (метрикой Хэмминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях:
.
Минимальное расстояние Хэмминга является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:
.
Корректирующая способность определяет, сколько ошибок передачи кода (типа ) можно гарантированно исправить. То есть вокруг каждого кодового слова имеем -окрестность , которая состоит из всех возможных вариантов передачи кодового слова с числом ошибок () не более . Никакие две окрестности двух любых кодовых слов не пересекаются друг с другом, так как расстояние между кодовыми словами (то есть центрами этих окрестностей) всегда больше двух их радиусов .
Таким образом, получив искажённую кодовую комбинацию из , декодер принимает решение, что исходной была кодовая комбинация , исправляя тем самым не более ошибок.
Например, при наличии всего двух кодовых слов и с расстоянием Хэмминга между ними, равным 3, ошибка в одном бите слова может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .
Коды Хэмминга[править | править код]
Коды Хэмминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хэмминга может быть представлен в таком виде, что синдром:
,
где — принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.
Общий метод декодирования линейных кодов[править | править код]
Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова соответствует наиболее вероятное переданное слово . Однако данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.
Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора вычисляется синдром . Поскольку , где — кодовое слово, а — вектор ошибки, то . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
Линейные циклические коды[править | править код]
Несмотря на то, что декодирование линейных кодов значительно проще декодирования большинства нелинейных, для большинства кодов этот процесс всё ещё достаточно сложен. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами.
Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.
Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .
Чаще всего используются двоичные циклические коды (то есть могут принимать значения 0 или 1).
Порождающий многочлен[править | править код]
Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему (генераторному) многочлену . Порождающий многочлен является делителем .
С помощью порождающего многочлена осуществляется кодирование циклическим кодом. В частности:
Коды CRC[править | править код]
Коды CRC (англ. cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.
Таким образом, вид многочлена задаёт конкретный код CRC. Примеры наиболее популярных полиномов:
Коды БЧХ[править | править код]
Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.
Коды коррекции ошибок Рида — Соломона[править | править код]
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).
Математически коды Рида — Соломона являются кодами БЧХ.
Преимущества и недостатки блоковых кодов[править | править код]
Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.
Свёрточные коды[править | править код]
Свёрточный кодер ()
Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных. Такие коды, как правило, порождаются дискретной линейной инвариантной во времени системой. Поэтому, в отличие от большинства блоковых кодов, свёрточное кодирование — очень простая операция, чего нельзя сказать о декодировании.
Кодирование свёрточным кодом производится с помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.
Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.
Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.
Каскадное кодирование. Итеративное декодирование[править | править код]
Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.
Например, популярной является следующая конструкция: данные кодируются кодом Рида — Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.
Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).
Оценка эффективности кодов[править | править код]
Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).
Граница Хэмминга и совершенные коды[править | править код]
Пусть имеется двоичный блоковый код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хэмминга):
Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хэмминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.
Литература[править | править код]
- Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
- Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
- Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
Источник