ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Код Хэмминга для исправления одиночных ошибок

Общие теоретические сведения

Принцип контроля с использованием корректирующих кодов

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

Для анализа свойств корректирующих кодов важное значение имеет понятие кодового расстояния. Под ним понимают количество разрядов, в которых значения одного слова отличаются от значений другого слова. В общем виде кодовое расстояние между словами A_i и A _j выражается формулой

где a_i_k- значение k-го разряда в слове A_i;

Å - символ сложения по модулю 2.

Для каждого кода существует минимальное кодовое расстояние d=min(d_ij), которое определяет свойства этого кода.

Известна следующая зависимость между числом обнаруживаемых ошибок t и минимальным кодовым расстоянием d³t+1.

Для того, чтобы код обеспечил исправление t ошибок, его минимальное кодовое расстояние должно удовлетворять условию d³2t+1.

Минимальное кодовое расстояние определяется избыточностью кода, под которой понимают отношение числа m контрольных разрядов к числу информационных n: d=m/n.

Код с проверкой на четность

Пусть требуется передать информационный набор a₁...a_k. Кодовый набор получается в результате дописывания к последовательности символа a_k+1, который назначается так, чтобы число единиц в последовательности a₁...a_k a_k+1 было четным. Если при передаче произошла одна ошибка , то число единиц в принятом наборе b₁...b_k b_k+1 станет нечетным. Это и указывает на наличие ошибки. Место ошибки найти не удается, поэтому декодирование не производится. Таким образом, код с проверкой на четность обнаруживает (но не исправляет) одну ошибку. Он также обнаруживает любое нечетное число ошибок.

Кодовые слова a₁...a_k a_k+1 содержит четное число единиц, поэтому для них справедливо соотношение

которое называется проверочным.

Код Хэмминга для исправления одиночных ошибок

Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7) используемый при передаче 7-битных ASCII-кодов. Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7+4=11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью. Например, пусть возможны следующие правильные коды (все они, кроме первого и последнего, отстоят друг от друга на расстояние 4):

При получении кода 00000111 не трудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее расстояние Хэмминга.

Рассмотрим пример передачи кода буквы s = 0x073 = 1110011 с использованием кода Хэмминга (11,7).

Номера разрядов
Контрольные разряды				*				*		*	*

Символами * помечены четыре позиции, где должны размещаться контрольные биты. Эти позиции определяются целой степенью 2 (1, 2, 4, 8 и т.д.). Контрольная сумма формируется путем выполнения операции XOR (исключающее ИЛИ) над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3. Вычислим контрольную сумму:

11=
10=
9=
5=
3=
Сумма =

Таким образом, приемник получит код:

Номера разрядов
Контрольные разряды

Просуммируем снова коды позиций ненулевых битов и получим нуль:

11=
10=
9=
8=
5=
4=
3=
2=
Сумма =

Ну а теперь рассмотрим два случая ошибок в одном из битов посылки, например, в бите 7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых бит еще раз:

11=
10=
9=
8=
7=
5=
4=
3=
2=
Сумма =

11=
10=
9=
8=
4=
3=
2=
Сумма =

В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме. Понятно, что если ошибка произойдет при передаче более чем одного бита, код Хэмминга при данной избыточности окажется бесполезен.