Общие принципы использования избыточности в блоковых кодах

Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На вход кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из n двоичных символов, причем n > k.

Всего может быть 2k различных входных и 2n различных выходных последовательностей. Из общего числа 2n выходных последовательностей только 2k последовательностей соответствуют входным. Назовем их разрешенными кодовыми комбинациями. Остальные 2n – 2k возможных выходных последовательностей для передачи не используются. Назовем их запрещенными комбинациями.

Общие принципы использования избыточности в блоковых кодах
Рис. 4.2

Искажение информации в процессе передачи сводится к тому, что некоторые из переданных символов заменяются другими – неверными. Так как каждая из разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, то всего имеется 2k · 2n возможных случаев передачи (рис. 4.2). В это число входят:

  • 2k случаев безошибочной передачи (на рис. 4.2 обозначены жирными линиями);
  • 2k(2k – 1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам (на рис. 4.2 обозначены пунктирными линиями);
  • 2k(2n – 2k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены (на рис. 4.2 обозначены тонкими сплошными линиями).

Следовательно, часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи составляет:

2k(2n – 2k) ⁄ (2k · 2n) = 1 – 2k ⁄ 2n.

Пример 1

Определим обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (n = k + 1). Общее число выходных последовательностей составляет 2k+1, т.е. вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество 2k комбинаций, содержащих четное число единиц (или нулей).

При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1) такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого нечетного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть опознанных ошибок составляет:

1 – 2k ⁄ 2k + 1 = 1 ⁄ 2.

Рассмотрим случай исправления ошибок

Любой метод декодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на 2k непересекающихся подмножеств Mi, каждое из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству Mi, принимают решение, что передавалась разрешенная комбинация Ai. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из Ai, т. е. в 2n – 2k случаях.

Всего случаев перехода в неразрешенные комбинации 2k(2n – 2k). Таким образом, при наличии избыточности любой код способен исправлять ошибки. http://peredacha-informacii.ru/ Отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно.

(2n – 2k) ⁄ [2k(2n – 2k)] = 1 ⁄ 2k.

Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным конкретным кодом.

Большинство разработанных до настоящего времени кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (пакетов) ошибок.

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

Кратностью ошибки называют количество искаженных символов в кодовой комбинации.

При взаимно независимых ошибках вероятность искажения любых r символов в n-разрядной кодовой комбинации:

Pn(r) = Cnr· pr(1 – p)n r.

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

Следует учесть, что

Общие принципы использования избыточности в блоковых кодах ,

а Pn(r) представляет собой гипергеометрическое распределение при r = 1, 2, ... n.