Читайте также:
|
Рассмотрим некоторый алфавит, в котором n=2 m букв. Если буквы появляются в текстах равновероятно, то минимальное количество двоичных символов на одну букву совпадает с H бит на символ и равно m (максимально плотная кодировка). При сбое декодировать такой текст невозможно. Чтобы контролировать ошибки, вводим x дополнительных двоичных позиций под каждую букву. События – ошибок в коде буквы нет, ошибка в первой позиции, ошибка во второй позиции, и так далее, ошибка в позиции m+x – считаем равновероятными. Тогда минимальное количество символов под кодирование одной буквы с контрольными символами x должно определиться количеством информации
H= log2 (1+m+x).
Но чтобы получить информацию об ошибках после кодирования буквы (или после передачи по каналу связи) нужно иметь информацию в x бит, которая была бы не менее количества информации H:
x ³ log 2 (1+m+x).
Из этого неравенства вытекает, что должно быть
2x – x –1 ³ m.
Например, если x =3, то m можно выбрать равным четырём. Итого имеем семь двоичных позиций под букву, из них четыре позиции – информационные, а три – контрольные. Обозначим эти позиции
b1 b2 b3 b4 b5 b6 b7
По Р. Хэммингу позиции
b1 b2 b4
нужно выбрать контрольными (мнемоническое правило: номера контрольных позиций это целые степени двойки 0, 1, 2), а позиции b3 b5 b6 b7 - информационными. Содержимое контрольных позиций должно определяться содержимым информационных позиций. По Р. Хэммингу контрольные позиции заполняются по правилу:
b 1 = b 3+b 5+b 7 mod 2
b 2 = b 3 +b 6 +b 7 mod 2 (Х1)
b 4 = b 5 +b 6 +b 7 mod 2
Тогда (s1 s2 s3) будет двоичным кодом той ячейки, где содержится ошибка, и этот код должен вычисляться по правилу:
s1 = b 4 + b 5 +b 6 +b 7 mod 2
s2 = b 2 + b 3 +b 6 +b 7 mod 2 (Х2)
s 3 = b 1 + b 3+b 5+b 7 mod 2
Если ошибки нет, то (s1 s2 s3)= (0 0 0).
Если в уравнениях (Х2) заменить символы
b1 b2 b3 b4 b5 b6 b7
номерами их позиций в двоичной кодировке:
1 (001) 2(010) 3(011) 4(100) 5(101) 6(110) 7(111),
то получим, что (s1 s2 s3)= (0 0 0). В этом случае из уравнений (Х2) вытекают уравнения (Х1) на правило заполнения контрольных позиций.
Пример:
Пусть некоторая буква алфавита имеет код:
b3 b5 b6 b7 = 1 0 0 1
Находим контрольные символы по формулам (Х1):
b 1 b 2 b 4 = 0 0 1
Тогда расширенная кодировка буквы имеет вид:
b1 b2 b3 b4 b5 b6 b7 = 0 0 1 1 0 0 1 (X3)
Подсчитываем s1 , s2, s3 по формулам (Х2). Получаем, что (s1 s2 s3)= (0 0 0).
Допустим, что в третьей позиции кода Х(3) возникла по какой-то причине ошибка, и код стал таким:
b1 b2 b3 b4 b5 b6 b7 = 0 0 0 1 0 0 1 (Х4)
Вычисляем s1 ,s2,, s3 для кода (Х4) по формулам (Х2). В результате имеем:
s1 = (b 4 + b 5 +b 6 +b 7 mod 2) = 0
s2 = (b 2 + b 3 +b 6 +b 7 mod 2) = 1
s 3 = (b 1 + b 3+b 5+b 7 mod 2) = 1
Получили, что (s1 s2 s3)= (011) – это двоичный адрес третьей ячейки, где возникла ошибка. Таким образом, код Р. Хэмминга позволяет прогнозировать и исправить одиночную ошибку. Код Р. Хэмминга обобщается на произвольные алфавиты и позволяет исправлять не только одиночные ошибки кодов отдельных букв, но и кратные ошибки. Кроме того, дополнительные биты в схеме Р. Хэмминга
используют и для шифрования информации. Это отдельное направление защиты информации, которое мы не рассматриваем.
Дата добавления: 2015-09-10; просмотров: 85 | Поможем написать вашу работу | Нарушение авторских прав |