Общие принципы помехоустойчивого кодирования

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

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

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

Пусть М — число знаков первичного алфавита. Длина равномерного двоичного кода к > log₂M, при этом каждый знак получает свою уникальную последовательность знаков вторичного (бинарного) алфавита. Общее число кодовых комбинаций S_p = 2^к, очевидно, S_p > М.

Например, мощность алфавита М = 64. Длина равномерного бинарного кода к > log₂M = 6. И наоборот — с помощью 6 бит можно получить 2⁶ = 64 кодовых комбинаций. Они будут считаться разрешенными.

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

8 Сколько информационных бит потребуется командиру разведчиков?

Ответ: сообщение от одного разведчика о том, что на дороге обнаружен разыскиваемый объект, будем обозначать 1, а сообщение об отсутствии объекта на дороге — 0. Для обнаружения объекта достаточно получить информацию о наличии/отсутствии объекта с трех дорог. Следовательно, количество информационных разрядов равно 3.

Возможность обнаружения и исправления ошибок в помехоустойчивых кодах достигается тем, что после первичного кодирования (установления соответствия каждому знаку первичного алфавита его кода) осуществляется вторичное кодирование, в ходе которого к к информационным битам по определенным правилам добавляются г проверочных (корректирующих) разрядов. В результате общая длина кодовой комбинации становится равной п — к + г. В дальнейшем такие коды будем называть (п, к)-кодами, а число возможных кодовых комбинаций, составленных из п разрядов, возрастает до S = 2^п. Из них не все оказываются разрешенными — их только S_p, остальные жeS_f-S-S_p комбинаций являются запрещенными.

Допустим, помехоустойчивый код содержит 6 информационных и 3 проверочных бита. Общая длина кодового слова будет равна 6 + 3 = 9 бит, а общее количество кодов S = 2⁹ = 512. Из них разрешенных кодов — 2⁶ = 64, а запрещенных — 448.

8 Командир по одной дороге идет сам, по остальным посылает разведчиков. Определить количество проверочных битов.

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

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