4.6. Границы для кодов, исправляющих или обнаруживающих пачки ошибок

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

Теорема 4.6. Линейный код, который не содержит пачек длины d или меньше в качестве кодовых слов, должен иметь по крайней мере d проверочных символов.

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

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

- Доказательство. Необходимость следует из теоремы 4.6. Достаточность следует из того факта, что все пачки ошибок длины d или меньше обнаруживают код, у которого первые символов — информационные, а последние d символов — проверочные символы, выбранные так, чтобы обращалась в нуль сумма любого из d наборов символов, образованного одним из первых d символов и всеми символами, которые расположены в кодовой последовательности через d символов друг от друга, начиная с первого, включенного в набор. Тогда на каждый фиксированный проверочный символ оказывает влияние самое большее один из ненулевых символов пачки ошибок длины d или меньше, и, таким образом, каждая такая пачка

ошибок будет обнаружена наряду со многими другими комбинациями ошибок. Ч. т. д.

Проверочная матрица для такого кода при показана на рис. 4.2, а метод ее практической реализации, основанный на использовании регистров сдвига, иллюстрируется рис. 4.3. Это элементарный пример циклического кода. Циклические коды изучаются в гл. 8.

Рис. 4.2. Проверочная матрица для двоичного группового -кода, обнаруживающего все пачки ошибок длины 5 или меньше.

Рис. 4.3. Регистр сдвига для вычисления результатов проверок на четность для кода, изображенного на рис. 4.2.

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

Доказательство. Любой вектор, имеющий форму пачки ошибок длины или меньше, может быть записан в виде разности двух пачек ошибок длины b или меньше (за исключением вырожденного случая, когда пачка содержит единственный ненулевой элемент). Так как, для того чтобы исправлялись все пачки ошибок длины b или меньше, необходимо, чтобы они принадлежали различным смежным классам, то их разности не могут быть кодовыми векторами. Следовательно, пачка длины или меньше не может быть кодовым вектором. Первое утверждение теоремы (в том числе для вырожденного случая) следует поэтому из теоремы 4.6,

Аналогично каждая пачка ошибок длины или меньше может быть записана как разность пачки ошибок длины d или меньше и пачки длины b или меньше. Если код одновременно исправляет

пачки ошибок длины или меньше и обнаруживает все пачки длины то пачка длины и пачка длины d должны принадлежать различным смежным классам и их сумма не должна быть кодовым словом. Второе утверждение теоремы тоже следует из теоремы 4.6. Ч. т. д.

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

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

Используя тождества

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

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

Теорема 4.9. Число проверочных символов любого линейного кода, исправляющего все пачки длины b или меньше, равно, самое меньшее,

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

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

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

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

Итзк. можпо подвести итог в форме следующей теоремы.

Теорема 4.10. Если число проверочных символов удовлетворяет неравенству

то существует линейный -код, который исправляет любую Одиночную пачку ошибок длины ,