ГЛАВА 4. ВОЗМОЖНОСТИ ИСПРАВЛЕНИЯ ОШИБОК С ПОМОЩЬЮ ЛИНЕЙНЫХ КОДОВ

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

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

4.1. Граница Плоткина

Сумма весов кодовых слов линейного -кода с символами, взятыми из поля с элементами, равна (См. задачу 3.4.) Вес минимального по весу элемента не может превосходить

средний вес, а общее число элементов с ненулевым весом равно Отсюда следует верхняя граница для минимального веса.

Теорема 4.1. Минимальный вес кодового слова в линейном -коде равен самое большее

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

Теорема 4.2. Если то

Доказательство. Пусть это код с символами и минимальным весом содержащий кодовых слов. Совокупность Н всех кодовых слов, последним символом в которых является нуль, образует подпространство пространства поскольку сумма любых двух элементов из И принадлежит И и любое произведение элемента из И на скаляр принадлежит Можно образовать смежных классов в пространстве О по подпространству И по одному для каждого значения символа, который может появиться на месте последней компоненты; таким образом, часть всех элементов из принадлежит И. Поэтому подгруппа образует линейный код с кодовыми словами и минимальным весом, по крайней мере причем каждый из векторов этого кода оканчивается нулем. Последняя компонента может быть отброшена, и при этом получится линейный код с символами и с тем же самым числом кодовых слов и весом. Может оказаться, что в полученном коде И найдутся некоторые другие столбцы, состоящие из одних нулей. Однако каждый из них можно заменить столбцом любого другого типа, отчего минимальный вес кода не уменьшится. (Заметим, что соответствующий код состоит из повторений одного и того же информационного символа. Таким образом, при условии в коде из символов возможны ненулевые столбцы.) Следовательно,

Теорема 4.1 может быть переписана в виде

и если

то

Для случая

Применяя многократно теорему 4.2, получаем

Комбинируя неравенства 4,2 и 4.3 при получим

Рис. 4.1. Границы для минимального расстояния для наилучших кодов (длина кода предполагается очень большой).

Поскольку для кода с максимальным минимальным расстоянием где число информационных символов этого кода, то

Таким образом, верна следующая теорема.

Теорема 4.3. Если , то число проверочных символов, необходимое душ того, чтобы минимальный

вес линейного кода с символами достигал значения равно, самое меньшее,

Если d очень велико, то последними тремя слагаемыми в этом выражении можно пренебречь. Эта граница показана на рис. 4.1 для двоичного случая без учета последних трех слагаемых.

Граница Плоткина может быть выведена также для нелинейных кодов.