Читайте также:
|
При контроле передачи информации наибольшее распространение получили методы информационной избыточности, использующие коды с обнаружением и коррекцией ошибок.
Если длина кода n разрядов, то таким двоичным кодом можно представить максимум 2^n различных слов. Если все разряды слова служат для представления информации, код называется простым (неизбыточным). Коды, в которых лишь часть кодовых слов используется для представления информации, называются избыточными. Часть слов в избыточных кодах является запрещенной, и появление таких слов при передаче информации свидетельствует о наличии ошибки.
Коды разделяются на равномерные и неравномерные. В равномерных кодах все слова содержат одинаковое число разрядов. В неравномерных кодах число разрядов в словах может быть различным. В вычислительных машинах применяются преимущественно равномерные коды.
Равномерные избыточные коды делятся на разделимые и неразделимые. Разделимые коды всегда содержат постоянное число информационных (т. е. представляющих передаваемую информацию) и избыточных разрядов, причем избыточные занимают одни и те же позиции в кодовом слове. В неразделимых кодах разряды кодового слова невозможно разделить на информационные и избыточные.
Способность кода обнаруживать или исправлять “ошибки” определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значения от 1 до n. Минимальным кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1.
Простой (не избыточный) код имеет минимальное расстояние dmin — 1. Для избыточных кодов dmin > 1. Если dmin > 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена. Если dmin = 3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле кодового расстояния) разрешенным словом, можно исправить одиночную ошибку.
В общем случае, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие:
dmin>r+1
Дата добавления: 2014-12-23; просмотров: 44 | Поможем написать вашу работу | Нарушение авторских прав |