Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
В цифровых каналах связи при передаче информации по разным причинам (неисправность оборудования, помехи) могут возникать ошибки. Поэтому на приемной стороне используются различные способы обнаружения ошибок, а также способы, позволяющие выполнить как обнаружение, так исправление ошибки.
Если контроль передачи информации выполняется только с обнаружением ошибки, то в случае ошибки приемник запрашивает повторную передачу искаженной информации. Если же контроль выполняется с обнаружением и исправлением ошибки, то приемник сам выполняет коррекцию искаженной информации без обращения к передатчику.
Из теории кодирования информации известно, что вероятность двойной или тройной ошибки (в двух или трех битах одновременно) на один или два порядка меньше, чем вероятность возникновения одиночной ошибки. Поэтому при контроле передачи информации основное внимание уделяется обнаружению, а также обнаружению и исправлению одиночной ошибки. Различают коды, которые позволяют только обнаруживать ошибку, и коды, которые позволяют как обнаруживать, так и исправлять ее.
КОДЫ ДЛЯ ОБНАРУЖЕНИЯ ОШИБОК
КОД ГРЕЯ
При использовании обыкновенного двоичного кода изменение числа на 1 может привести к изменению двоичного числа сразу в нескольких битах, что может вызвать значительные ошибки считывания.
Погрешности считывания можно устранить, если воспользоваться невесовыми кодами, представляющими собой последовательности n-разрядных двоичных чисел, в которых каждые два соседних числа отличаются одно от другого только в одном разряде. У таких кодов много названий – коды Грея, рефлексные, отраженные, циклические, прогрессивные коды.
Частный случай, получивший наибольшее распространение, – «код Грея». Главная особенность кода Грея, обеспечившая ему широкое практическое применение, состоит в простоте его построения.
Пусть а – двоичное n-разрядное число обычной (весовой) системы счисления, b – соответствующее число в коде Грея. Тогда правило, по которому можно найти код Грея по заданному числу а, представится формулой вида:
где ⊕ – знак сложения по модулю 2; i – порядковый номер разряда в числе а; i = 1, 2, 3, …, n; счет начинается с младшего разряда. Чтобы по этому правилу найти код Грея, достаточно поразрядно сложить по модулю 2 число а с самим собой, но сдвинутым вправо на один разряд с потерей цифры младшего разряда и записью нуля в старшем разряде:
где
Например, при n = 4 последовательность кодов Грея имеет вид: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
Код Грея является невесовым в отличие от обычной двоичной системы счисления. Это значит, что образующие его двоичные числа надо рассматривать только как упорядоченные наборы нулей и единиц без присвоения им весов. Например, двоичному весовому числу 10011 (в десятичной системе – это 19) соответствует код Грея 11010, и если его считать весовым, то получится число 26 (в десятичной системе). В связи с этим каждому невесовому коду обычно присваивается та или иная величина либо с применением правила, как в случае кода Грея, либо при помощи таблицы.
Коды Грея часто используются в датчиках-энкодерах. Также они используются для кодирования номера дорожек в жестких дисках.
Примером могут служить датчики механических перемещений. Один из таких датчиков представляет собой соосно укрепленный на валу прозрачный диск с нанесенной на него кодовой маской. Коды считываются при помощи системы каких-либо фотоэлементов. Главное назначение датчика – определить положение вала, т.е. угол его поворота по отношению к некоторому исходному состоянию.
Для примера на рисунке показан диск, разделенный на 16 равных частей – секторов (на практике их обычно тысячи). Все сектора пронумерованы и каждый номер представлен в двоичном коде в виде сочетаний темных и светлых участков, расположенных на четырех концентрических кольцах.
Внутреннему кольцу поставлен в соответствие старший разряд номера, внешнему – младший. Нуль на диске обозначен светлой частью кольца, единица – зачернением. Считываются числа с диска параллельно, т.е. все четыре разряда одновременно, при помощи четырех фотоэлементов.
Главное достоинство датчика – его простота. Однако с практической точки зрения он почти непригоден. Дело в том, что параллельные коды хорошо считываются только в пределах каждого отдельного сектора, а при переходе от одного сектора к другому возникают помехи. Пусть число считывается в момент, когда под фотоэлементами проходит 15-й сектор, а за ним идет сектор с нулевым номером. Какое число получится на границе секторов? Это зависит от таких причин, как неточность изготовления маски и блока фотоэлементов, тепловая нестабильность, влияние различных вибраций и др. В общем случае на границе 15-го и нулевого секторов может быть считано любое число от 0 до 15. Помехи имеют место также при переходе от первого сектора ко второму, от третьего к четвертому, от пятого к шестому и др.
Если на рисунке вместо обычной двоичной (весовой) системы использовать код Грея, то на границах секторов всегда будет изменяться цифра только в одном каком-либо разряде. Благодаря этому в моменты перехода диска от одного кода к другому помехи появиться не могут.
КОНТРОЛЬ ЧЕТНОСТИ/НЕЧЕТНОСТИ
Наиболее часто для обнаружения ошибок используется контроль на четность/нечетность передаваемой информации. При таком контроле блок информации, передаваемый от источника к приемнику, должен содержать соответственно четное/нечетное число единиц.
Источник формирует передаваемый блок информации так, чтобы это выполнялось. Приемник проверяет выполнение этого условия. Если четность/нечетность нарушена, то считается, что произошла ошибка при передаче информации. Приемник сообщает об этом источнику, и источник заново посылает этот блок информации. Передаваемый блок информации состоит из информационных битов и одного контрольного:
|
ПЕРЕДАВАЕМЫЙ БЛОК ИНФОРМАЦИИ |
|
|
ИНФОРМАЦИОННЫЕ БИТЫ |
КОНТРОЛЬНЫЙ БИТ |
|
X1,X2,…,Xn |
K |
При контроле на четность в бит K записывается сумма по модулю 2 информационных разрядов. При контроле на нечетность записывается инверсное значение этой суммы.
Рассмотрим пример такого контроля. Пусть от источника к приемнику надо переслать 8 бит информации с контролем на четность.
Тогда пересылаемый блок информации должен содержать 9 бит.
Пример. Переслать код 01110101.
Побитное сложение по модулю для этого кода дает значение, равное 1. Тогда значение контрольного бита должно равняться 1, чтобы передаваемый код содержал четное число единиц.
|
ПЕРЕДАТЧИК |
ПРИЕМНИК |
комментарий |
|||||||||||||||||
|
информационные биты |
контрольный бит |
принятые биты |
сумма по mod 2 |
||||||||||||||||
|
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
нет ошибки |
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
есть ошибка |
КОД ДЖОНСОНА
Последовательность чисел в этом коде моделируется односторонним последовательным заполнением его разрядов вначале единицами, а затем нулями (таблица). Код Джонсона легко формируется с помощью регистров сдвига и легко дешифруется.
КОД «1 из m»
Для случая m=8 представлен в таблице. Этот код характерен тем, что в любой кодовой комбинации присутствует только одна единица, что позволяет легко находить ошибки в случае искажения кода, и не требуется его дешифрация. Данный код, как и код Джонсона, является избыточным, требующим для своего изображения больше разрядов, чем соответствующие неизбыточные коды.
|
S |
КОД ДЖОНСОНА |
КОД «1 из 8» |
|
0 |
0 0 0 0 |
0 0 0 0 0 0 0 1 |
|
1 |
0 0 0 1 |
0 0 0 0 0 0 1 0 |
|
2 |
0 0 1 1 |
0 0 0 0 0 1 0 0 |
|
3 |
0 1 1 1 |
0 0 0 0 1 0 0 0 |
|
4 |
1 1 1 1 |
0 0 0 1 0 0 0 0 |
|
5 |
1 1 1 0 |
0 0 1 0 0 0 0 0 |
|
6 |
1 1 0 0 |
0 1 0 0 0 0 0 0 |
|
7 |
1 0 0 0 |
1 0 0 0 0 0 0 0 |
КОД ХЭММИНГА ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБКИ
Исправлять ошибку при приеме информации труднее, чем ее обнаруживать. Исправление ошибки предполагает два совмещенных процесса: обнаружение факта, что есть ошибка, и определение ее места. После решения этих двух задач, исправление тривиально – надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется только метод обнаружения ошибки и повторной пересылки блока информации, содержавшего ошибку. Для спутниковых каналов с типичными для них большими задержками коррекция ошибки становится необходимой. Здесь используется код Хэмминга.
Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Блочными называются коды, в которых информационный поток символов разбивается на отрезки, и каждый из них преобразуется в определенную последовательность (блок) кодовых символов. В блочных кодах кодирование при передаче (формирование проверочных элементов) и декодирование при приеме (обнаружение и исправление ошибок) выполняются в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам.
Обычно код Хэмминга характеризуется двумя целыми числами, например, код (11,7), используемый при передаче семибитных ASCII-кодов. Такая запись говорит, что при передаче семибитного кода используется дополнительно четыре контрольных бита (7+4=11). При этом предполагается, что может иметь место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью.
При рассмотрении кода Хэмминга требуется знать, что такое кодовое расстояние. Кодовое расстояние между двумя двоичными кодами одинаковой длины определяется количеством битов, в которых эти коды отличаются.
Пример 1. Кодовое расстояние между «кодом 1» и «кодом 2» равно 1.
|
КОД 1 |
0 |
1 |
0 |
|
КОД 2 |
0 |
1 |
1 |
Пример 2. Кодовое расстояние между «кодом 1» и «кодом 2» равно 2.
|
КОД 1 |
0 |
0 |
1 |
|
КОД 2 |
1 |
1 |
1 |
Правило вычисления кодового расстояния — комбинации кодов суммируются по модулю 2, после чего подсчитывается количество единиц в полученной сумме.
Например,
|
КОД 1 |
1 |
0 |
0 |
1 |
0 |
|
КОД 2 |
1 |
0 |
1 |
1 |
1 |
|
КОД1⊕КОД2 |
0 |
0 |
1 |
0 |
1 |
Кодовое расстояние равно 2, т.к. число единиц в сумме – 2.
Можно обнаружить ошибку только, если между используемыми кодовыми комбинациями есть необходимое для этого кодовое расстояние, т.е. между соседними используемыми кодовыми комбинациями есть другие комбинации. Эти кодовые комбинации не используются для передачи информации, и их получение на приеме свидетельствует об ошибке передачи информации в канале связи. Для заданного кода минимальное кодовое расстояние – это минимальное из всех расстояний всех пар кодовых слов.
В обычном равномерном непомехоустойчивом коде число разрядов n в кодовых комбинациях определяется числом сообщений и основанием кода. Коды, у которых все кодовые комбинации разрешены к передаче, называются простыми или равнодоступными и являются полностью безызбыточными. Безызбыточные первичные коды обладают большой «чувствительностью» к помехам. Внесение избыточности при использовании помехоустойчивых кодов обязательно связано с увеличением числа разрядов (длины) кодовой комбинации.
В этом случае все множество N=2n комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, т.е. обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих. Помехоустойчивый код отличается от обычного тем, что в канал передаются не все кодовые комбинации N, которые можно сформировать из имеющегося числа разрядов n, а только их часть NК, которая составляет подмножество разрешенных комбинаций.
Если при приеме выясняется, что кодовая комбинация принадлежит к запрещенным, то это свидетельствует о наличии ошибки, т.е. таким образом решается задача обнаружения ошибок. При этом принятая комбинация не декодируется (не принимается решение о приеме сообщения). Помехоустойчивые коды называют корректирующими кодами. Корректирующие свойства избыточных кодов зависят от правила их построения, определяющего структуру кода, и параметров кода.
Например, при n=3 можно составить 8 кодов (000, 001, 010, 011, 100, 101, 110, 111).
Пусть все восемь кодовых комбинаций являются разрешенными (допустимыми), тогда кодовое расстояние между соседними комбинациями равно 1. Т.к. в данном случае отсутствует какой-либо признак, позволяющий судить о появлении ошибки в кодовой комбинации, то такой код не является помехозащищенным. Допустим, что лишь четыре из восьми кодовых комбинаций считаются разрешенными, например это комбинации 001, 010, 100 и 111. Тогда кодовое расстояние равно 2, причем искажение символа в одном из разрядов приводит к получению запрещенной кодовой комбинации (000, 011, 101 или 110), что легко выявляется при проверке. Полученный таким образом двоичный код называют кодом с обнаружением одиночной ошибки. Для кодового расстояния равного 3 в качестве разрешенных кодовых комбинаций можно принять, например, 010 и 101. При этом обеспечивается возможность не только обнаружения, но и исправления одиночной ошибки. Действительно, получение запрещенной кодовой комбинации 110 указывает на наличие ошибки, для исправления которой необходимо перейти к ближайшей из разрешенных кодовых комбинаций (в данном случае – 010). Данный код позволяет обнаруживать и двойные ошибки, так как при одновременном искажении символов в двух разрядах кодовой комбинации последняя также попадает в число запрещенных.
Первые работы по корректирующим кодам принадлежат Хэммингу, который ввел понятие минимального кодового расстояния и предложил код, позволяющий однозначно указать ту позицию в кодовой комбинации, где произошла ошибка. К «M» (message) информационным битам в коде Хэмминга добавляется «C» (control) проверочных битов для определения местоположения ошибочного бита.
Таким образом, код Хэмминга состоит из информационных и контрольных битов. Информационные биты будем обозначать через М, контрольные биты – через С:
М={M1,M2,…,Mn};
C={C1, C2,…Ck};
N=M+C – общее количество передаваемых битов в канал связи (передаваемый блок).
Сущность кода Хэмминга заключается в том, что местоположение контрольных и информационных битов определяется по правилу, которое устанавливает зависимость, позволяющую в случае ошибки определить ее местоположение, т.е. номер бита.
Основные положения для получения кода Хэмминга состоят в следующем:
1. Число, составленное из контрольных разрядов, должно указывать номер бита, в котором произошла ошибка, или 0, если нет ошибки. Исходя из этого, если произошла ошибка, проверочное С-битовое число – должно быть в диапазоне от 1 до (2С–1). Из этого следует, что 2С–1≥N; тогда 2С≥N+1; умножим левую и правую части на 2M, получим 2M×2С≥2M×(N+1), откуда 2(M+C)≥2M×(N+1), тогда 2N≥2M×(N+1); делим левую и правую части на (N+1), получаем условие
С использованием этого условия и определяется минимально необходимое число контрольных битов для передачи заданного количества информационных.
2. Контрольные биты в коде Хэмминга занимают позиции с номерами, равными 2n, где n=0,1,3,… и т.д. Причем позиции кода номеруются справа налево, начиная с 1. Информационные биты располагаются в остающихся позициях справа налево по возрастанию весов разрядов.
3. Значение каждого контрольного бита получается сложением по модулю 2 тех информационных битов, для которых в номере кодовой позиции информационных битов, записанном через контрольные разряды, значение бита равно 1. Эта формулировка будет более понятна, если посмотреть ее использование по табл. 1 или 2.
Вначале построим код Хэмминга для передачи четырехбитового кода.
Условие 1. Это условие будет выполняться при N=7:
Таким образом, для четырех информационных битов (М=4) требуются три контрольных бита (С=3).
Условие 2. Определяем местоположение информационных и контрольных битов в коде.
|
Положение информационных и контрольных битов |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
Номер позиции кода |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Условие 3. Определяем логические выражения для вычисления контрольных битов. Для этого построим таблицу.
Таблица 1
Вычисление контрольных битов для кода (7,4)
|
ПОЗИЦИЯ КОДА |
КОНТРОЛЬНЫЕ БИТЫ |
||
|
С3 |
С2 |
С1 |
|
|
3 бит (М1) |
0 |
1 |
1 |
|
5 бит (М2) |
1 |
0 |
1 |
|
6 бит (М3) |
1 |
1 |
0 |
|
7 бит (М4) |
1 |
1 |
1 |
|
СУММИРУЕМЫЕ ПО МОДУЛЮ 2 БИТЫ |
М2 М3 М4 |
М1 М3 М4 |
М1 М2 М4 |
Таким образом, передатчик вычисляет значения контрольных разрядов по следующим логическим выражениям:
С1=М1⊕М2⊕М4;
С2=М1⊕М3⊕М4;
С3=М2⊕М3⊕М4.
Приемник проверяет правильность принятого кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4;
С12=С2⊕М1⊕М3⊕М4;
С13=С3⊕М2⊕М3⊕М4.
Построим код Хэмминга для передачи семибитового кода.
Условие 1. Это условие будет выполняться при N=11:
Таким образом, для семи информационных битов (М=7), требуются четыре контрольных бита (С=4).
Условие 2. Определяем местоположение информационных и контрольных битов в коде.
|
Положение информационных и контрольных битов |
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
Номер позиции кода |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Условие 3. Определяем логические выражения для вычисления контрольных битов. Для этого построим таблицу.
Таблица 2
Вычисление контрольных битов для кода (11,4)
|
ПОЗИЦИЯ КОДА |
КОНТРОЛЬНЫЕ БИТЫ |
|||
|
С4 |
С3 |
С2 |
С1 |
|
|
3 бит (М1) |
0 |
0 |
1 |
1 |
|
5 бит (М2) |
0 |
1 |
0 |
1 |
|
6 бит (М3) |
0 |
1 |
1 |
0 |
|
7 бит (М4) |
0 |
1 |
1 |
1 |
|
9 бит (М5) |
1 |
0 |
0 |
1 |
|
10 бит (М6) |
1 |
0 |
1 |
0 |
|
11 бит (М7) |
1 |
0 |
1 |
1 |
|
СУММИРУЕМЫЕ ПО МОДУЛЮ 2 БИТЫ |
М5 М6 М7 |
М2 М3 М4 |
М1 М3 М4 М6 М7 |
М1 М2 М4 М5 М7 |
Таким образом, передатчик вычисляет значения контрольных разрядов по следующим логическим выражениям:
С1=М1⊕М2⊕М4⊕М5⊕М7;
С2=М1⊕М3⊕М4⊕М6⊕М7;
С3=М2⊕М3⊕М4;
С4=М5⊕М6⊕М7.
Приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7;
С13=С3⊕М2⊕М3⊕М4;
С14=С4⊕М5⊕М6⊕М7.
Рассмотрим примеры передачи информации с использованием кода Хэмминга для случаев, когда ошибки при передаче нет, и когда есть.
Начнем с кода (7,4).
Пример. В канал связи нужно передать следующий блок информации: 11012.
Передатчик формирует код Хэмминга:
|
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
1 |
1 |
0 |
* |
1 |
* |
* |
С1=М1⊕М2⊕М4=1⊕0⊕1=0;
С2=М1⊕М3⊕М4=1⊕1⊕1=1;
С3=М2⊕М3⊕М4=0⊕1⊕1=0,
тогда код, передаваемый в канал, будет:
|
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
Рассмотрим случай, когда не было ошибки при передаче кода.
Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4=0⊕1⊕0⊕1=0;
С12=С2⊕М1⊕М3⊕М4=1⊕1⊕1⊕1=0;
С13=С3⊕М2⊕М3⊕М4=0⊕0⊕1⊕1=0.
Поскольку значение, составленное из контрольных битов, равно нулю, ошибки нет, и код передается от приемника далее.
Рассмотрим случай, когда была ошибка при передаче кода.
Пусть ошибка произошла в третьем бите, т.е. принят код:
|
M4 4 |
M3 3 |
M2 2 |
C3 3 |
M1 1 |
C2 2 |
C1 1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4=0⊕0⊕0⊕1=1;
С12=С2⊕М1⊕М3⊕М4=1⊕0⊕1⊕1=1;
С13=С3⊕М2⊕М3⊕М4=0⊕0⊕1⊕1=0.
Поскольку, значение, составленное из контрольных разрядов, равно 0112, ошибка в бите № 3. Приемник меняет значение этого бита на противоположное.
Теперь рассмотрим код (11,7).
Пример. В канал связи нужно передать следующий блок информации: 11010102.
Передатчик формирует код Хэмминга:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
1 |
1 |
0 |
* |
1 |
0 |
1 |
* |
0 |
* |
* |
С1=М1⊕М2⊕М4⊕М5⊕М7=0⊕1⊕1⊕0⊕1=1;
С2=М1⊕М3⊕М4⊕М6⊕М7=0⊕0⊕1⊕1⊕1=1;
С3=М2⊕М3⊕М4=1⊕0⊕1=0;
С4=М5⊕М6⊕М7=0⊕1⊕1=0,
тогда код, передаваемый в канал, будет:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
Рассмотрим случай, когда не было ошибки при передаче кода.
Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7=1⊕0⊕1⊕1⊕0⊕1=0;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7=1⊕0⊕0⊕1⊕1⊕1=0;
С13=С3⊕М2⊕М3⊕М4=0⊕1⊕0⊕1=0;
С14=С4⊕М5⊕М6⊕М7=0⊕0⊕1⊕1=0.
Поскольку значение, составленное из контрольных битов, равно нулю, ошибки нет, и код передается от приемника далее.
Рассмотрим случай, когда была ошибка при передаче кода.
Пусть ошибка произошла во втором бите, т.е. принят код:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7=1⊕0⊕1⊕1⊕0⊕1=0;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7=0⊕0⊕0⊕1⊕1⊕1=1;
С13=С3⊕М2⊕М3⊕М4=0⊕1⊕0⊕1=0;
С14=С4⊕М5⊕М6⊕М7=0⊕0⊕1⊕1=0.
Поскольку значение, составленное из контрольных битов, равно 00102, ошибка во втором бите. Приемник меняет значение этого бита на противоположное.
Код Хэмминга является равномерно защищенным, исправляет ошибки как в информационных, так и в контрольных битах. С его помощью возможно исправление одиночной и обнаружение двойной ошибки. Для того чтобы обнаружить двойную ошибку, в код Хэмминга вводят дополнительный контрольный бит E0. Значение E0 вычисляется как сумма по модулю 2 всех разрядов кода Хэмминга, т.е. он дополняет код Хэмминга по четности. На стороне приемника, кроме получения контрольных разрядов, которые определяют позицию с ошибкой, вычисляется контрольный разряд E10:
E10=Е0⊕<сложенные по модулю 2 все остальные биты принятого кода>.
Если E10=0, то ошибок нет. Если значение, полученное из контрольных разрядов, не равно 0 и E10=1, то имеет место одиночная ошибка, позиция которой определяется значением контрольных разрядов. Если значение С≠0 и E10=0 , то имеет место двойная ошибка.
Рассмотрим пример для кода, исправляющего одиночную ошибку и обнаруживающего двойную.
Для кода (11,7) формат блока информации:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Е0 |
Пример. В канал связи нужно передать следующий блок информации: 11010102.
Передатчик формирует код Хэмминга:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Е0 |
|
1 |
1 |
0 |
* |
1 |
0 |
1 |
* |
0 |
* |
* |
* |
С1=М1⊕М2⊕М4⊕М5⊕М7=0⊕1⊕1⊕0⊕1=1;
С2=М1⊕М3⊕М4⊕М6⊕М7=0⊕0⊕1⊕1⊕1=1;
С3=М2⊕М3⊕М4=1⊕0⊕1=0;
С4=М5⊕М6⊕М7=0⊕1⊕1=0,
Е0=С1⊕С2⊕М1⊕С3⊕М2⊕М3⊕М4⊕С4⊕М5⊕М6⊕М7=1⊕1⊕0⊕0⊕1⊕0⊕⊕1⊕0⊕0⊕1⊕1=0,
тогда код, передаваемый в канал, будет:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Е0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
Рассмотрим случай, когда не было ошибки при передаче кода.
Тогда точно такой же код принял приемник. Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7=1⊕0⊕1⊕1⊕0⊕1=0;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7=1⊕0⊕0⊕1⊕1⊕1=0;
С13=С3⊕М2⊕М3⊕М4=0⊕1⊕0⊕1=0;
С14=С4⊕М5⊕М6⊕М7=0⊕0⊕1⊕1=0,
Е10= Е0⊕С1⊕С2⊕М1⊕С3⊕М2⊕М3⊕М4⊕С4⊕М5⊕М6⊕М7=
=0⊕1⊕1⊕0⊕0⊕1⊕0⊕1⊕0⊕0⊕1⊕1=0.
Поскольку значение, составленное из контрольных битов, равно 0, и Е10=0, ошибки нет, и код передается от приемника далее.
Рассмотрим случай, когда была одиночная ошибка при передаче кода.
Пусть ошибка произошла во втором бите (не считая Е0, т.е. в С2) и принят код:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Е0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7=1⊕0⊕1⊕1⊕0⊕1=0;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7=0⊕0⊕0⊕1⊕1⊕1=1;
С13=С3⊕М2⊕М3⊕М4=0⊕1⊕0⊕1=0;
С14=С4⊕М5⊕М6⊕М7=0⊕0⊕1⊕1=0,
Е10= Е0⊕С1⊕С2⊕М1⊕С3⊕М2⊕М3⊕М4⊕С4⊕М5⊕М6⊕М7=
=0⊕1⊕0⊕0⊕0⊕1⊕0⊕1⊕0⊕0⊕1⊕1=1.
Поскольку значение Е10=1 и значение, составленное из контрольных разрядов, равно 00102, то ошибка во втором бите. Приемник меняет значение этого бита на противоположное.
Рассмотрим случай, когда была двойная ошибка при передаче кода.
Пусть ошибка произошла во втором (т.е. в С2) и в пятом битах (т.е. М2) и принят код:
|
M7 |
M6 |
M5 |
C4 |
M4 |
M3 |
M2 |
C3 |
M1 |
C2 |
C1 |
Е0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Теперь приемник проверяет правильность передачи кода, вычисляя следующие выражения:
С11=С1⊕М1⊕М2⊕М4⊕М5⊕М7=1⊕0⊕0⊕1⊕0⊕1=1;
С12=С2⊕М1⊕М3⊕М4⊕М6⊕М7=0⊕0⊕0⊕1⊕1⊕1=1;
С13=С3⊕М2⊕М3⊕М4=0⊕0⊕0⊕1=1;
С14=С4⊕М5⊕М6⊕М7=0⊕0⊕1⊕1=0,
Е10= Е0⊕С1⊕С2⊕М1⊕С3⊕М2⊕М3⊕М4⊕С4⊕М5⊕М6⊕М7=
=0⊕1⊕0⊕0⊕0⊕0⊕0⊕1⊕0⊕0⊕1⊕1=0.
Поскольку значение Е10=0 и значение, составленное из контрольных разрядов, равно 01112≠0, то произошла двойная ошибка. Приемник не передает код далее, а запрашивает от источника повторную передачу этого блока информации.