2.7. Кодирование в постоянном симметричном стирающем канале

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

Если пренебречь вероятностью ошибочного приема символа, то пропускная способность стирающего канала может быть выражена через вероятность стирания  [22]:

Здесь , так как при правильно принятом символе остаточная энтропия  равна нулю, а при стертом символе — исходной энтропии . Поэтому

                   (2.52)

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

В случае, когда примененный код не позволяет исправлять более чем  стертых символов, вероятность ошибочного декодирования  при  можно приближенно определить как вероятность того, что из  символов стерты какие-либо  (пренебрегая вероятностью стирания  большего  числа символов):

         (2.53)

Заметим, что при применении кодов с большим хемминговым расстоянием можно правильно декодировать принятые кодовые комбинации даже в тех случаях, когда наряду со стертыми кодовыми символами имеются   также   ошибочно   принятые. Для   этого   достаточно (но не всегда необходимо)  выполнение условия

,                                                     (2.54)

где  — количество стертых символов;  — количество ошибочно принятых символов в кодовой комбинации.

Действительно, пусть стертыми оказались  символов, расположенных в каких-то разрядах принятой комбинации. Вычеркнем эти разряды во всех допустимых кодовых комбинациях. Тогда мы получим новое множество комбинаций (код), в котором минимальное хеммингово расстояние . Если среди нестертых символов имеются ошибочно принятые в количестве, не превышающем . То в принципе всегда возможно правильное декодирование, как было показано в § 2.5. Отсюда вытекает (2.54).

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