Протоколы Internet


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


Пусть общее число бит в блоке равно N, из них полезную информацию несут в себе K бит, тогда в случае ошибки, имеется возможность исправить m бит. Таблица 2.8.1 содержит зависимость m от N и K для кодов ВСН.

Таблица 2.8.1

Общее число бит N

Число полезных бит М

Число исправляемых бит m

31

26

1

21

2

16

3

63

57

1

51

2

45

3

127

120

1

113

2

106

3

Увеличивая разность N-M, можно не только нарастить число исправляемых бит m, но открыть возможность обнаружить множественные ошибки. В таблице 2.8.2 приведен процент обнаруживаемых множественных ошибок в зависимости от M и N-M.

Таблица 2.8.2

Число полезных бит М

Число избыточных бит (n-m)

6

7

8

32

48%

74%

89%

40

36%

68%

84%

48

23%

62%

81%

Другой блочный метод предполагает “продольное и поперечное” контрольное суммирование предаваемого блока. Блок при этом представляется в виде N строк и M столбцов. Вычисляется биты четности для всех строк и всех столбцов, в результате получается два кода, соответственно длиной N и M бит. На принимающей стороне биты четности для строк и столбцов вычисляются повторно и сравниваются с присланными. При выявлении отличия в бите i кода битов четности строк и бите j – кода столбцов, позиция неверного бита оказывается определенной (i,j). Понятно, что если выявится два и более неверных битов в контрольных кодах строк и столбцов, задача коррекции становится неразрешимой. Уязвим этот метод и для двойных ошибок, когда сбой был, а контрольные коды остались корректными.

Применение кодов свертки позволяют уменьшить вероятность ошибок при обмене, даже если число ошибок при передаче блока данных больше 1.

Линейные блочные коды

Блочный код определяется, как набор возможных кодов, который получается из последовательности бит, составляющих сообщение. Например, если мы имеем К бит, то имеется 2К возможных сообщений и такое же число кодов, которые могут быть получены из этих сообщений. Набор этих кодов представляет собой блочный код. Линейные коды получаются в результате перемножения сообщения М на порождающую матрицу G[IA]. Каждой порождающей матрице ставится в соответствие матрица проверки четности (n-k)*n. Эта матрица позволяет исправлять ошибки в полученных сообщениях путем вычисления синдрома. Матрица проверки четности находится из матрицы идентичности i и транспонированной матрицы А. G[IA] ==> H[ATI].

  I A AT

[ZEBR_TAG_/table>

Если , то H[ATI] =

Синдром полученного сообщения равен

S = [полученное сообщение]. [матрица проверки четности].

Если синдром содержит нули, ошибок нет, в противном случае сообщение доставлено с ошибкой. Если сообщение М соответствует М=2k, а k =3 высота матрицы, то можно записать восемь кодов:

<


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