Теория кодирования

Кодовое расстояние инверсного кода равно количеству разрядов исходного кода при k<4 и равно 4 при k ³4. Например, при d=4 код может обнаруживать двойные ошибки и исправлять одиночные. Обычно этот код используется только для обнаружения ошибок. Он позволяет обнаруживать ошибки любой кратности за исключением таких, когда искажены 2 информационных символа и соответствующие им 2 контрольных, 4 информационных и соответствующие им 4 контрольных и т.д.

Коэффициент избыточности инверсного кода равен 0,5.

3.9. Код Хэмминга

В середине 1940-х годов Ричард Хэмминг  работал в знаменитых Bell Labs на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машину с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и снова запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.

Хэмминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перезагружать  свою программу из-за ненадежности перфокарт. На протяжении нескольких лет  он проводил много времени над  построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день известен как код Хэмминга.

Расстояние Хэмминга — число  позиций, в которых соответствующие  символы двух слов одинаковой длины  различны. В более общем случае расстояние Хэмминга применяется для  строк одинаковой длины любых  q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.

Пример:

d(1011101, 1001001)=2

Данный код относится к числу  систематических кодов. По существу, это целая группа кодов, при dmin = 3 исправляющая все одиночные или обнаруживающая двойные ошибки, а при dmin = 4 исправляющая одиночные и обнаруживающая двойные ошибки.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяеется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибок, запишем 0, если есть ошибка - 1. Запись полученной последовательности символов образует двоичное число.

Свойство кодов Хэмминга таково, что контрольное число указывает  номер позиции, где произошла  ошибка. При отсутствии ошибки в  коде данная последовательность будет  содержать только нули. Полученное число описывает таким образом  n=(m+k+1) событий. Следовательно, справедливо неравенство

Определим теперь позиции, которые  надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, это означает, что в результате первой проверки обнаружена ошибка. Первая проверка охватывает позиции 1, 3, 5, 7, 9, ... (в двоичной записи этих чисел младший разряд равен 1). Вторая проверка - 2, 3, 6, 7, 10...

N Проверяемые разряды

1 1, 3, 5,7, 9, 11, 13, 15, ...

2 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, ...

3 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23

4 8, 9, 10, 11, 12, 13, 14, 15, 24, ...

... ...

 

Для контроля будем использовать позиции 1,2,4,8,..., так как в данные позиции  встречаются только в одной проверяемой  группе символов

По методу Хэмминга могут быть построены  коды разной длины. Чем больше длина  кода, тем меньше относительная избыточность. Например, для контроля 48-разрядного числа, потребуется только шесть  дополнительных (контрольных) разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи.

     Пример 1. Необходимо передать слово «Привет» представленного в кодировке КОИ-8. КОИ-8 является восьмибитовой ASCII совместимой кодовой таблицей для кириллического алфавита. Соответственно каждый символ кодируется 8 битами информации, символов 6, следовательно, нам потребуется 48 бит для передачи данного сообщения. Необходимо выбрать длину информационного слова, пример длину слова равным 16 битам. Таким образом, для передачи слова «Привет» нам потребуется отправить 3 пакета, каждый из которых будет содержать 2 символа. Ниже представлена таблица, содержащая код каждого символа в таблице КОИ-8 и его бинарное представление.

Буква (символ)	Код в КОИ-8	Бинарное представление
П	F0	11110010
р	D2	11010010
и	C9	11001001
в	D7	11010111
е	C5	11000101
т	D4	11010100

 

Таким образом, мы должны передать 3 пакета, по 16 символов в каждом:

Первый пакет.

П	р
11110010	11010010

Второй пакет

и	в
11001001	11010111

Третий пакет

е	т
11000101	11010100

 

Теперь  необходимо подсчитать контрольную  сумму. Контрольными битами являются все  степени двойки, т.е. в нашем случае контрольными будут биты: 1, 2, 4, 8, 16. Таким  образом, размер сообщения увеличиться  с 16 бит до 21 бита. Значение каждого  контрольного бита зависит от значения информационных бит (т.е. от бит из которых  состоит передаваемое сообщение), каждый контрольный бит с номером  N контролирует все последующие N бит, через каждые N бит, наглядно это может быть представлено с помощью таблицы 2 для первого пакета передаваемого сообщения. В первой строке представлен порядковый номер каждого бита. Во второй строке представлен бинарный код, передаваемого сообщения, подчеркнутые биты являются контрольными, до подсчета контрольной суммы примем их равными 0. В последующих строках символом «X» обозначены те биты, которые контролируют контрольный бит, который обозначен в левом столбце, т.е., например, бит с номером 9 отслеживается контрольными битами 1 и 8.

Пакет 1 Символы  «Пр».

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
	0	0	1	0	1	1	1	0	0	0	0	0	1	1	0	0	1	0	0	1	0
1	X		X		X		X		X		X		X		X		X		X		X
2		X	X			X	X			X	X			X	X			X	X
4				X	X	X	X					X	X	X	X					X	X
8								X	X	X	X	X	X	X	X
16																X	X	X	X	X	X

 

Теперь  необходимо вычислить значение каждого  контрольного бита и получить контрольную  сумму. Для этого берём каждый контрольный бит и смотрим, сколько  среди контролируемых им битов имеют  значение 1, получаем некоторое число  N и если это число четное, то значение данного контрольного бита 0, если нечетное соответственно 1. Стоит отметить что можно принять и обратное правило если N четное число, присваивать контрольному биту значение 1, в противном случае – 0.

Вычислим  контрольную сумму для пакета 1. Сумма единичных битов, охватываемых контрольным битом с номером 1 равно  следовательно значение контрольного 1 контрольного бита равно 1, проделаем данную операцию для остальных контрольных битов.

, контрольный бит 2=0.

, контрольный  бит 4=0.

 контрольный  бит 8=0.

, контрольный  бит 16=0.

Таким образом, мы получили контрольную сумму для  передаваемого пакета: 10000. Передаваемый пакет принимает вид: 101011100000110010010.

 

После передачи сообщение необходимо декодировать, и, если это необходимо, исправить  ошибки. Декодирование сообщение  заключается в повторном вычислении контрольной суммы. Если контрольные  суммы сообщений совпадают, то пакет  пришел без ошибки, в противном  случае необходимо исправить в нем  ошибки. Предположим что сообщение  пришло нам с ошибкой: 6 бит передался  неправильно, соответственно и контрольная  сумма для полученного сообщения  не совпадает с контрольной суммой отправленного сообщения. Как можно  увидеть из таблицы, 6 информационный бит контролируется 2 и 4 контрольными битами, соответственно контрольная  сумма для принятого пакета примет вид: 11100. Теперь, для того чтобы узнать позицию ошибочного бита мы должны сложить номера позиций неправильных контрольных бит в нашем случае это 2+4=6, т.е. бит принятый с ошибкой, бит под номером 6. Стоит учитывать, что это простейший алгоритм, который  может исправить только одну ошибку в каждом передаваемом пакете.

 

Пакет 2 символы  «ив»

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
	0	0	1	0	1	0	0	0	1	0	0	1	1	1	0	0	1	0	1	1	1
1	X		X		X		X		X		X		X		X		X		X		X
2		X	X			X	X			X	X			X	X			X	X
4				X	X	X	X					X	X	X	X					X	X
8								X	X	X	X	X	X	X	X
16																X	X	X	X	X	X

 

, контрольный  бит 1=1.

, контрольный бит 2=1.

, контрольный  бит 4=0.

 контрольный  бит 8=0.

, контрольный  бит 16=0.

 

Контрольная сумма: 11000, передаваемое сообщение: 111010001001110010111

 

Пакет 3 символы  «ет»

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
	0	0	1	0	1	0	0	0	0	1	0	1	1	1	0	0	1	0	1	0	0
1	X		X		X		X		X		X		X		X		X		X		X
2		X	X			X	X			X	X			X	X			X	X
4				X	X	X	X					X	X	X	X					X	X
8								X	X	X	X	X	X	X	X
16																X	X	X	X	X	X