8.6. Обнаружение ошибок с помощью циклических кодов

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

Обычно при обнаружении ошибок число проверочных символов будет меньше числа информационных символов. Поэтому кодирование лучше осуществлять, используя методы разд. 8.5, для чего требуется

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

Теперь проанализируем возможности обнаружения ошибок.

Теорема 8.2. На один из векторов циклического -кода не является пачкой длины или меньше. Следовательно, любой циклический -код может обнаруживать любую пачку ошибок длины или меньше.

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

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

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

Теорема 8.3. Доля пачек ошибок длины которые не будут обнаруживаться, равна , если и равна если .

Доказательство. Рассмотрим пачки длины начинающиеся с символа и заканчивающиеся символом. Каждая из них представима в виде где многочлен степени Существует способов выбора первого коэффициента, для последнего и способов выбора для каждого коэффициента между ними. Таким образом, существует всего различных многочленов

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

Степень равна , поэтому степень многочлена должна быть равна . Если то постоянная величина, отличная от нуля, и она может принимать

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

В некоторых случаях возможность обнаружения ошибок может сочетаться с другими важными свойствами специфических кодов. Например, можно построить код Боуза — Чоудхури с произвольным кодовым расстоянием который будет обнаруживать любую комбинацию из или меньше ошибок или любую пачку ошибок длины к или меньше. Может быть построен код Файра, исправляющий любую одиночную пачку ошибок длины Такой код обнаруживает любую комбинацию из двух пачек ошибок длины b или меньше или любую одиночную пачку ошибок длины к или меньше.

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

В гл. 9 показано, что можно построить двоичный код Боуза-Чоудхури с кодрвым расстоянием, равным 10, и Для него требуется 41 проверочный символ, и, следовательно, для кодирования и обнаружения ошибок необходим регистр сдвига, содержащий 41 разряд. Код может обнаруживать любую комбинацию из 9 или меньше ошибок или любую одиночную ошибку длины 41 и меньше и подавляющее большинство всех других комбинаций ошибок.