Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

5. Обнаружение пакетов ошибок циклическими кодами

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

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

Следующая теорема говорит о том, что всякий циклический (n, k)-код обнаруживает все пакеты ошибок длины (n - k) и менее. Кроме того, процент пакетов ошибок длины больше (n - k), которые не обнаруживаются кодом, очень небольшой.

Теорема 5.1. Всякий циклический (n,k)-код обнаруживает все пакеты ошибок длины (n - k) и менее.

Доказательство. Циклический (n,k)-код порождается многочленом g(x) степени (n - k). Следовательно, каждому кодовому слову соответствует либо нулевой многочлен, либо многочлен степени больше (n - k).

Пусть было передано кодовое слово v, которому соответствует многочлен v(x), а принято слово u (соответствующий многочлен u(x)). Тогда u = v + e, где e = v + u - вектор ошибок (многочлен e(x)).

Для того чтобы ошибка e была обнаружена, необходимо и достаточно, чтобы вектор u не был кодовым, т. е. многочлен g(x) не должен быть делителем соответствующего многочлена u(x). Так как v(x) - кодовый многочлен, который делится на g(x), то для того, чтобы ошибка e была обнаружена, необходимо и достаточно, чтобы вектор e не был кодовым, т. е., чтобы g(x) не делил соответствующий многочлен e(x). Таким образом, для доказательства теоремы достаточно показать, что ни один кодовый вектор не является пакетом длины (n - k) или менее.

Рассмотрим пакет e длины (n - k), т. е. e(x) = ajxj + aj-1xj-1 + ... + aj-(n-k-1)xj-(n-k-1). Вынесем xj-(n-k-1) за скобки и получим e(x) = xj-(n-k-1)(ajxn-k-1 + aj-1xj-1 + ... + aj-(n-k-1)) или e(x) = xj-(n-k-1) r(x), где r(x) = ajxn-k-1 + aj-1xj-1 + ... + aj-(n-k-1). Так как многочлен g(x) делит многочлен xn + 1, то многочлены xj и g(x) взаимно просты. Многочлен r(x) имеет степень меньше (n - k), т. е. не может делиться на многочлен степени (n - k). Поэтому многочлен e(x), соответствующий пакету длины (n - k) или менее, не делится на порождающий многочлен g(x), т. е. вектор e не является кодовым, и такая ошибка будет обнаружена.

Можно показать, что циклический (n,k)-код обнаруживает большинство пакетов ошибок длины больше (n - k).

Теорема 5.2. Доля пакетов ошибок длины b > n - k, которые не могут быть обнаружены циклическим (n,k)-кодом, равна 2-(n-k-1), если bn - k +1, и равна 2-(n-k), если bn - k +1.