Контроль передачи информации

Файл : control.doc (размер : 716,800 байт)

КОНТРОЛЬ ПЕРЕДАЧИ ИНФОРМАЦИИ

При контроле передачи информации наибольшее распро​странение получили методы информационной избыточности, использующие коды с обнаружением и коррекцией ошибок.

Если длина кода п разрядов, то таким двоичным кодом можно представить максимум 2n различных слов. Если все раз​ряды слова служат для представления информации, код назы​вается простым (неизбыточным). Коды, в которых лишь часть кодовых слов используется для представления информации, на​зываются избыточными. Часть слов в избыточных кодах является запрещенной, и появление таких слов при передаче информации свидетельствует о наличии ошибки.

Принадлежность слова к разрешенным или запрещенным словам определяется правилами кодирования, и для различных кодов эти правила различны.

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

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

Способность кода обнаруживать или исправлять “ошибки” определяется так называемым минимальным кодовым расстоя​нием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значе​ния от 1 до п. Минимальным кодовым расстоянием данного ко​да называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, от​личающихся друг от друга только в одном разряде, то мини​мальное расстояние данного кода равно 1.

Простой (не избыточный) код имеет минимальное расстоя​ние dmin — 1. Для избыточных кодов dmin > 1. Если dmin > 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка при​ведет к появлению запрещенного слова и может быть обнару​жена. Если dmin = 3, то любая одиночная ошибка создает запре​щенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле ко​дового расстояния) разрешенным словом, можно исправить одиночную ошибку.

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

dmin>r+1.(2)

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

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

dmin>2r+1.(3)

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

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

Минимальное расстояние кода dmin = 1, поэтому код с про​веркой четности обнаруживает все одиночные ошибки, а кроме того, все случаи нечетного числа ошибок (3, 5 и т. д.). При одновременном возникновении двух или любого другого чет​ного числа ошибок код с проверкой четности не обнаруживает ошибок.