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

Не только обнаружить, но и исправить ошибку можно с помощью кодов, ко­торые строятся следующим образом. Пусть есть m-значный двоичный код. Общее число комбинаций

N = 2^m.

Каждый из таких кодов отличается один от другого хотя бы одним знаком. Дополним код еще одним знаком, а число кодовых комбинаций оставим не­изменным, тогда

N = 2^m=1/2*2ⁿ

и можно так подобрать кодовые комбинации, что они будут отличаться дву­мя знаками. При этом используется только половина всех возможных комби­наций от 2ⁿ, вторая половина образует запрещенные комбинации: любое по­явление одиночной ошибки превращает ее в запрещенную и тем самым ошибка обнаруживается. Дополним теперь код таким количеством знаков, которое даст возможность двум кодовым комбинациям отличаться тремя знаками при неизменном числе N = 2 ^m. Такой код позволит не только обна­ружить, но и исправить одиночную ошибку. Действительно, если произошла одиночная ошибка в какой-то комбинации, то эта комбинация от других бу­дет отличаться на два знака, а от своей — на один, и ее легко исправить. Определим общее число дополнительных знаков, необходимых для выявления и исправления одиночных ошибок. Пусть из общего числа позиций п для пере­дачи информации используется фиксированное число позиций т. Другие пози­ции k = п — т используются как проверочные. Символы, которые ставятся на k проверочных позициях, определяются при кодировании проверкой на четность каждой k -ой группы информационных символов. Сигнал кодируется так, чтобы в результате любой из проверок выходило четное число. На приемном конце на некоторых позициях появляются единицы вместо нулей и нули вместо еди­ниц. При приеме также проводится проверка на четность.

Построим код, который разрешал бы обнаружить и исправить одиночную ошибку. Пусть принята кодовая комбинация с ошибкой или без нее. Сделаем в ней последовательно k проверок. После каждой проверки запишем 0, если результат свидетельствует об отсутствии ошибки на позициях, т. е. сумма единиц четная. Результат свидетельствует о наличии ошибки, если сумма единиц нечетная и тогда записывается 1. Запись справа налево полученной последовательности единиц и нулей дает двоичное число. Отсутствию ошиб­ки в принятой кодовой комбинации будет отвечать число, составленное из нулей. Проверочное число должно описывать (т + k + 1) событий. Следова­тельно, число k определяется на основе неравенства 2 >т + k + 1, и поскольку

2ⁿ п = т + k, то 2^m --. п + 1

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

Определим позиции, которые надлежит проверить в любой из k проверок. Если ошибок нет, то на всех позициях, которые проверяются, будет 0, если в низшем разряде числа стоит 1, то это означает, что вследствие первой про­верки выявлена ошибка.

Таблица 1-

		Таблица 1.6.	Соотношения для корректирующих кодов
n	т	k	n	m	k

Будем при первой проверке проверять те номера позиций, двоичные пред­ставления которых имеют в первом разряде единицы, т. е.

1 = 0001; 3 = 0011; 5 = 0101; 7 = 0111; 9 = 1001 и т.д.

Таким образом, первая проверка охватывает позиции 1, 3, 5, 7, 9. Для второй проверки выберем такие позиции, двоичные представления которых имеют единицу во втором разряде — отвечающие числам 2, 3, 6, 7, 10. Для третьей проверки выберем позиции, двоичные представления которых имеют единицу в третьем разряде, т. е. имеем 4, 5, 6, 7, 12, 13, 14.

Такой выбор позиций, которые проверяются, дает возможность определить номер позиции, в которой возникла одиночная ошибка. Если возникла ошибка на одной из позиций первой проверки, то в проверочном числе в низшем (правом) разряде появится единица. Дальнейшую расшифровку проверочного числа дает вторая проверка: если среди всех позиций второй проверки ошибок нет, то появится ноль. Таким образом, любая одиночная ошибка на любой позиции может быть устранена проверками, которые дают проверочное число, равное номеру позиции, на которой возникла ошибка. Выбор для проверки позиций 1, 2, 4, 8... обеспечивает появление хотя бы одной из этих позиций в каждой проверке, и это позволяет независимо от знаков числа, которое передается, получить в каждой проверке четное число единиц.

Таким образом, основные принципы построения кодов Хемминга с исправ­лением ошибок состоят в следующем. К каждому набору из m информаци­онных разрядов присоединяется k разрядов p₁, p₂...p_kпроверки на четность. Потом присваиваются десятеричные значения позиции любому с (m + k) разрядов кодового набора, начиная со значения 1 для старшего разряда и кончая значением (m + k) для младшего разряда. Проводится k проверок на четность числа единиц в выбранных разрядах каждого кодового набора. Ре­зультат проверки на четность записывается как 1 или 0 в зависимости от того, выявлена ошибка или нет. По результатам этих проверок строится двоичное число с_ь с₂,...c _k равное десятеричному значению присвоенного местоположе­ния ошибочного разряда. При отсутствии ошибки записывается ноль. Это число называется номером позиции. Для определения контрольных разрядов независи­мо друг от друга через информационные разряды первые размещают на позици­ях 1, 2, ...2^k-1 Минимальное расстояние для кода Хемминга равняется трем. Корректирующую способность кода можно повышать и дальше: строя коды для выявления r-ой кратной и исправления 5-ой кратной ошибок. При этом бу­дет расти число дополнительных знаков и общая длина кодовой комбинации

(при неизменном N = 2^m). Очевидно, что d = 1 + r + s, r>s.

Возможности разных кодов видны из табл. 1.7.

Таблица 1.7. Возможности корректирующих кодов

d	г	S	Возможности кода
	0.		Отличие одной комбинации от другой
			Выявление одиночной ошибки
			Выявление и исправление одиночной ошибки
			Выявление двукратной о,шибки
			Выявление двукратной и исправление одиночной ошибки
			Выявление трехразовой ошибки
			Выявление и исправление двукратной ошибки
			Выявление трехразовой и исправление одиночной ошибок
			Выявление четырехразовой ошибки

Пусть, например, передана последовательность 1101001, но из-за ошибки в пятой позиции принята последовательность 1101101. Положение ошибки можно определить путем выполнения трех проверок на четность (табл. 1.8).

Таблица 1.8. Определение положения ошибки в коде

Таким образом, полученный номер позиции равен 101, что означает наличие ошибки в пятой позиции. Для ее исправления необходимо заменить пятый разряд его дополнением, после чего будем иметь правильное сообщение 1101001.

Дата добавления: 2015-07-08