С исправлением ошибок

Основные принципы построения кодов Хэмминга

Коды с исправлением ошибок

Для того, чтобы код исправлял ошибки, необходимо увеличить его минимальное кодовое расстояние.

Пример. Трёхразрядный код состоит из двух допустимых комбинаций 000 и 111. В случае одиночной ошибки для первого кодового набора возможные кодовые наборы 001,010,100, для второго – 011,101,110. У каждого допустимого кодового набора “свои” недопустимые кодовые наборы. Его минимальное кодовое расстояние d_min равно 3.

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

Определение. Код называется кодом с исправлением ошибок, если всегда из неправильного кодового набора можно получить правильный кодовый набор (например, коды Хэмминга).

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

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

1. К каждому набору из m информационных разрядов (сообщению) присоединяются k разрядов p₁, p₂, …p_k проверки на чётность.

2. Каждому из (m+k) присваивается десятичное значение позиции, начиная со значения 1 для старшего разряда и кончая значением (m+k) для младшего разряда.

3. Производится k проверок на чётность числа единиц в выбранных разрядах каждого кодового набора. Результат каждой проверки на чётность записывается как 1 или 0 в зависимости от того, обнаружена ошибка или нет.

4. По результатам проверок строится двоичное число c_{k …} c₂c₁, равное десятичному значению, присвоенному местоположению ошибочного разряда, если произошла ошибка, и нулю при её отсутствии. Это число называется номером позиции ошибочного разряда.

Число разрядов k должно быть достаточно большим для указания положения любой из (m+k) возможных одиночных ошибок. Так как m+k+1-количество возможных событий, 2^k – максимальное количество кодовых комбинаций, то k должно удовлетворять неравенству 2^k³ m+k+1.

Определим максимальное значение m для заданного количества k.Обозначим количество разрядов в коде n= m+k.

Таблица 15

n		2…3	4…7	8...15	16...31	32...63
m		0...1	1…4	4…11	11…26	26…57
k		2...2	3…3	4…4	5…5	6…6

Определим теперь позиции, которые необходимо проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, то контрольное число двоичное c_k… c₂c₁ содержит только 0. Если в первом разряде контрольного числа стоит 1, то в результате первой проверки обнаружена ошибка.

Таблица 16

№ позиции возможной ошибки	Двоичный эквивалент

Окончание таблицы 16

№ позиции возможной ошибки	Двоичный эквивалент
…	…

Из табл. 16 двоичных эквивалентов для номера позиции возможной ошибки видно, что в первую проверяемую группу разрядов входят 1,3,5,7,9, 11,13,15, 17 и т.д., во вторую – 2,3,6,7,10,11,14,15,18 и т.д.

Таблица 17

Проверка	Проверяемые разряды
	1,3,5,7,9, 11,13,15, 17 …
	2,3,6,7,10,11,14,15,18 …
	4,5,6,7, 12,13,14, 15 …
	8,9,10,11, 12,13,14, 15 …
…	…

Разряды, номера которых кратны степеням 2: 1,2,4,8,16…, встречаются в каждой проверяемой группе один раз. Удобно использовать эти разряды в качестве контрольных, а остальные – информационных разрядов.

Пример. Пусть исходное сообщение 00111. Количество информационных разрядов m=5. Количество контрольных разрядов k=4. Длина кода Хэмминга равна 9. Построим код Хэмминга для исходного сообщения.

Номер позиции
Исходное сообщение
1-я контрольная группа	0
2-я контрольная группа		0
3-я контрольная группа				0
4-я контрольная группа								1
Код Хэмминга

Код Хэмминга для десятичных цифр в двоично-десятичном коде 8421 приведен в табл. 18.

Таблица 18

Десятичная цифра	p1	p2	m1	p3	m2	m3	m4

Рассмотрим способ выявления положения ошибки и её исправления.

Пример. Пусть передана последовательность 1000011. Из-за ошибки в третьем разряде принято сообщение 1010011. Положение ошибки можно определить, выполняя 3 проверки на четность.

Номер позиции								ci
Сообщение
1-я проверка на четность
2-я проверка на четность
3-я проверка на четность
Исправленное сообщение

Полученный номер позиции c₃c₂c₁= 011, т.е. ошибка в третьем разряде.

Дата добавления: 2014-12-29