Протоколы Internet


Коррекция ошибок - часть 2


/p>

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

Позиция бита:

11

10

9

8

7

6

5

4

3

2

1

Значение бита:

1

1

1

1

0

0

1

1

1

1

0

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

11 =

1011

10 =

1010

09 =

1001

08 =

1000

05 =

0101

04 =

0100

03 =

0011

02 =

0010

s =

0000

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

11 =

1011

10 =

1010

09 =

1001

08 =

1000

07 =

0111

05 =

0101

04 =

0100

03 =

0011

02 =

0010

s =

0111

 

11 =

1011

10 =

1010

09 =

1001

08 =

1000

04 =

0100

03 =

0011

02 =

0010

s =

0101

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

В общем случае код имеет N=M+C бит и предполагается, что не более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М=4, а N=7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Теперь попытаемся вычислить значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:

С1 = М1 + М2 + М4

С2 = М1 + М3 + М4

С3 = М2 + М3 + М4

Для определения того, доставлено ли сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):

С11 = С1 + М4 + М2 + М1

С12 = С2 + М4 + М3 + М1

С13 = С3 + М4 + М3 + М2

Результат вычисления интерпретируется следующим образом.

С11

С12

С13

Значение

1

2

4

Позиция бит

0

0

0

Ошибок нет

0

0

1

Бит С3 не верен

0

1

0

Бит С2 не верен

0

1

1

Бит М3 не верен>

1

0

0

Бит С1 не верен>

1

0

1

Бит М2 не верен

1

1

0

Бит М1 не верен

1

1

1

Бит М4 не верен

<


Начало  Назад  Вперед



Книжный магазин