10.2. Возможности кодов Файра исправлять ошибки

Для того чтобы код одновременно исправлял любую пачку ошибок длины или меньше и обнаруживал любую пачку ошибок длины, большей, чем но не превосходящей необходимо и достаточно, чтобы для любой пачки ошибок длины, не превосходящей не существовало в том же самом смежном классе никакой пачки ошибок длины, не превосходящей Для целей исправления ошибок достаточно положить Сделанное утверждение эквивалентно условию, состоящему в том, что никакая сумма пачки ошибок длины b и пачки ошибок длины d не является кодовым вектором. Это требование в свою очередь совпадает с условием, необходимым и достаточным для обнаружения любых двух пачек ошибок. Поэтому следующая теорема доказывает сделанное в разд. 10.1 утверждение относительно возможностей исправления и обнаружения ошибок с помошью кодов Файра.

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

а величина по меньшей мере столь же велика, как наименьшее из чисел

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

что не может делиться на Отсюда будет следовать, что многочлен ни в каком случае не делится на

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

Так как по теореме 6.19 многочлен делится на многочлен по нашему предположению, многочлен тоже делится на то многочлен должен делиться на если только он отличен от нуля. Предположим, что

и что многочлен отличен от нуля, Тогда степень старшего члена в правой части равенства (10.4) равна где степень многочлена Степень многочлена равна что меньше, чем с, так что степень слагаемого наивысшего порядка в левой части равенства (10.4) равна Следовательно,

Сопоставляя соотношения (10.2) и (10.5), получаем, что Так как то . В левой части равенства (10.4) имеется слагаемое степени потому что многочлен обязательно содержит слагаемое нулевой степени, а степень многочлена равная меньше . В правой части равенства нет слагаемых степени потому что Это противоречие позволяет заключить, что и

Теперь посмотрим, может ли многочлен делиться на Так как то степень многочлена больше степени многочлена так что многочлены взаимно просты. Кроме того, и X также взаимно просты, так что делится на тогда и только тогда, когда делится на Поскольку то Если делится на то число должно делиться на порядок корней многочлена Поэтому оно должно делиться и на — наименьшее общее кратное с и е. Но это невозможно, ибо так что многочлен не может делиться на многочлен

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

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

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