2014-02-24
1699
Принципы построения помехозащищенных кодов. Коды с
Составные коды. Код Грея.
Кроме простых числовых кодов, применяют составные, имеющие два
основания и более, Наибольшее распространение из них получили единично-десятичные и двоично-десятичные коды, которые при двоичном характере символов легко позволяют перейти к десятичной системе, широко применяемой и наиболее понятной.
В единично-десятичном коде каждая цифра десятичного числа записывается одними единицами. Например, число 325 запишется как 111 11 11111. В двоично-десятичном коде каждая
цифра от 0 до 9 десятичного числа записывается четырехразрядным двоичным кодом. Такой код позволяет образовать N = 24=16 различных комбинаций. Для обозначения десяти цифр можно использовать любые 10 комбинаций из 16, поэтому возможно большое число двоично-десятичных кодов. Наибольшее применение нашел код, в котором десятичная цифра представлена ее точным двоичным числом. Такой код
иногда обозначают 8—4—2—1 по весу двоичных цифр в каждом разряде. При этом цифры от 0 до 9 обозначают рядом двоичных чисел. Число 325 в двоично-десятичной системе может быть записано следующим образом:
0011—0010—0101.
Код ГРЕЯ. Код, рассматриваемый ниже носит название кода Грея и обладает тем свойством, что при переходе от любого его состояния к следующему изменяется лишь один разряд (бит), что позволяет предотвратить ошибки, поскольку в данном случае при переходе между двумя закодированными значениями все разряды никак не могут измениться одновременно. Если бы использовался чисто двоичный код, то при переходе, например, от 7 к 8 на входе можно было бы получить число 15. Для формирования состояний кода Грея существует простое правило: начинать нужно с нулевого состояния, а затем для получения, каждого следующего нужно выбрать самый младший разряд, изменение которого приводит к образованию нового состояния, и взять его инверсное значение.
ОО11
О11О
Коды Грея могут содержать любое число разрядов.
Для того, чтобы избежать ошибки в случае одиночных искажений, нужно увеличить кодовое расстояние до d = 2, исключив комбинации только в одном разряде (элементе). Кодовое расстояние, обозначаемое буквой d, определяется путем сложения двух комбинаций по модулю 2 (mod 2), которое обозначается знаком + и производится в соответствии с табл.
При суммировании по mod 2 двух комбинаций нули будут в тех разрядах, где символы в обеих комбинациях одинаковы, а единицы — где символы различны. Например, сложение по mod 2 двух пятиразрядных чисел дает следующий результат:
Отсюда d =3.
Для того, чтобы определить кодовое расстояние между различными кодовыми
комбинациями, составляют матрицы
Нетрудно убедиться, что при любом одиночном искажении комбинации, приведенные в табл., не могут переходить одна в другую. Следовательно, при одиночном искажении произойдет появление новой комбинации, по которой можно судить об искажении. Двойные искажения при 
обнаружить нельзя. Для получения еще большей помехоустойчивости необходимо увеличить кодовое расстояние. Так, при 
можно обнаружить любые двойные, а при 
— тройные искажения. В общем случае получим выражение 
где rоб — количество ошибок, которое можно обнаружить. Для построения помехозащищенного кода необходимо разбить все комбинации
на две группы: разрешенные (основные) с кодовым расстоянием 
; запрещенные с кодовым расстоянием 
Помехозащищенным кодом можно передать меньшее число сообщений, чем кодом, в котором используются все комбинации при одинаковом числе элементов в кодах. При одинаковом числе сообщений в комбинациях помехозащищенного кода приходится затрачивать большее число элементов. Такие коды имеют избыточность, которую оценивают коэффициентом избыточности
где n — число элементов в комбинациях кода с избыточностью; n0 — число элементов в комбинациях неизбыточного кода. При кодовом расстоянии dmin > 2 можно не только обнаружить, но и исправить ошибку. Рассмотрим две кодовые комбинации 0011 и 1000, отличающиеся тремя элементами. Допустим, при передаче комбинации 1000 произошло одиночное искажение, получим 0000 1100 1010 или 1001. Можно с уверенностью сказать, что была передана комбинация 1000, т.е. исправить ошибку. Чтобы исправить любое число ошибок rи, минимальное кодовое расстояние нужно определить по формуле 
Отсюда для исправления одиночной ошибки (rи=1) dmin = 3.Способность кода обнаруживать и исправлять ошибки определяется минимальным кодовым расстоянием из выражения 
где rоб и rи — число обнаруженных и исправленных ошибок при условии 
Среди помехозащищенных кодов различают блочные и непрерывные. К блочным кодам относятся такие, с помощью которых сообщения передаются блоками определенной длины из некоторого конечного числа символов. В непрерывных кодах нет последовательности информационных символов определенной длины. Между информационными символами по определенному закону размещают проверочные.
