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

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

Первое − использование избыточности. Закодированные последова­тельности всегда содержат дополнительные, или избыточные, символы.

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

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

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

Возможность обнаружения и исправления ошибок в помехоустойчивых кодах достигается тем, что после первичного кодирования (установления соответствия каждому знаку первичного алфавита его кода) осуществляется вторичное кодирование, в ходе которого к k информационным битам по определенным правилам добавляются r проверочных (корректирующих) бит. В результате общая длина кодовой комбинации становится равной n = k + r – в дальнейшем такие коды будем называть (n,k)-кодами, а число возможных кодовых комбинаций возрастает до S = 2ⁿ. Из них не все оказываются разрешенными – их только S_р, остальные же S_f = S – S_р комбинаций являются запрещенными.

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